The present invention relates to electronic circuits and to digital communication. More particularly, the present invention relates to an advanced method for handling data units (packets) within a communication device by efficiently determining a flow identification for a data unit using a simplified and protocol independent method.
The present invention has a number of applications in advanced telecommunication systems and networks. One envisioned application of the invention is in a state-of-the-art router (or layer three switch) for handling data packets. These data packets may be constructed according to a number of well-know packet transmission protocols in a layered protocol suite. Routers are packet switching devices characterized by their ability to perform intelligent routing of packets on a per-packet basis. Routers generally can handle packets or frames of data formatted according to a number of different protocols. A layer three switch is a type of router that performs layer three routing of packets largely or exclusively using dedicated logic circuitry.
Other applications of the invention include fast recursive look-up for grouping any kind of discreet data unit quickly into groups for group-based handling.
Explanation of both the prior art and the invention will be better understood with reference to specific examples, however this should not be taken to limit the invention to the particular examples described. The invention is generalizable to other similar types of communication devices or to other computing devices handling data is ways that are analogous to data handling in modern networks. The invention should therefore not be limited except as provided in the attached claims.
Networking Devices Standards
This specification presumes familiarity with the general concepts, protocols, and devices currently used in LAN networking and WAN inter networking applications such as, for example, the IEEE 802 and ISO 8802 protocol suites and other series of documents released by the Internet Engineering Task Force that are publicly available. LANs are arrangements of various hardware and software elements that operate together to allow a number of digital devices to exchange data within the LAN and also may include internet connections to external wide area networks (WANs).
Packets
In the most common LANs and WANs in use today, data is transmitted among network devices and processed within devices as series of independent packets, each packet containing at least one header having at least a destination address specifying an ultimate destination and generally also having a source address. Headers may also include other handling information such as an indication of the different protocols used to format a packet, a transmission priority, etc.
FIG. 1 depicts an example of a packet as it may be transmitted on a network. The example shown is essentially an Ethernet packet, having an Ethernet header 202 and a 48-bit Ethernet address (such as 00:85:8C:13:AA) 204, and an Ethernet trailer 230. Within the Ethernet packet 200 is contained, or encapsulated, an IP packet, represented by IP header 212, containing a 32 bit IP address 214 (such as 199.22.120.33). Packet 200 contains a data payload 220 which holds the data the user is interested in receiving or holds a control message used for configuring the network. Many other types and configurations of packets are presently known in the networking art and it is assumed that additional packet protocols will be developed in the future.
Layers
An additional background concept important to understanding network communications is the concept of layered network protocols. Modern communication standards, such as the TCP/IP Suite and the IEEE 802 standards, organize the tasks necessary for data communication into layers. At different layers, data is viewed and organized differently, different protocols are followed, and different physical devices may handle the data traffic. FIG. 2 illustrates one example of a layered network standard having a number of layers, the Physical Layer, the Data Link Layer, the Routing Layer, the Transport Layer and the Application Layer. These layers correspond roughly to the layers as defined within the TCP/IP Suite. (The 802 standard has a different organizational structure for the layers and uses somewhat different names and numbering conventions.)
An important ideal in layered standards is the ideal of layer independence. A layered protocol suite specifies standard interfaces between layers such that, in theory, a device and protocol operating at one layer can coexist with any number of different protocols operating at higher or lower layers, so long as the standard interfaces between layers are followed.
Optimizing The Handling of Data Units (Packets) within a Network Device
With an increasing number of network users needing increasing amounts of network bandwidth, there is a need for network devices to become efficient and sophisticated in their internal processing and routing of data. One mechanism known in the art for processing packets more efficiently is for network devices to identify flows in packets. A flow may be defined generally as a group of related packets that share some common characteristic which the network device may use to optimize the handling of the packets. For example, a network device may establish separate buffers for different flows so that very heavy traffic on one flow will not be allowed to cause congestion on another flow, or a network device may otherwise optimize its operation by grouping packets in flows.
In prior art systems, first the packets themselves are identified. The identification of packets is done based on the packet header. Each protocol has a header that uniquely identifies it. As described above, communication protocols frequently have encapsulated packets. That is, one protocol carried within another protocol. These are called protocol layers. In prior art systems, in order to group related packets together into flows, it is necessary to determine and identify multiple layers of protocols. The flow can be coarsely defined at a higher layer, requiring the identification of the outer protocol(s). A flow can also be defined at a finer layer of granularity by identifying multiple layers of encapsulated protocols.
Once a flow is identified, packets belonging to that flow can be isolated from other packets. The isolation of a flow permits the network device to process the flow independently from other packets. It also shields the flow from harmful effects caused by other flows.
Within the art it is becoming common to construct networking devices that perform layer three routing tasks using dedicated logic circuits. These devices are sometimes referred to as layer three switches. One task that these devices attempt to perform using fast dedicated logic is identifying and assigning packets to flows. In one such known system, for example, flows are identified by the system looking for packets flowing from a particular source address to a particular destination address. If a specified number of packets are received in a specified period of time having the same source and destination address, the system will establish a flow for those packets and may attach a flow identification field to those packets, allowing special handling of those packets within that device or by other networking devices in the network.
There is a trade-off, however, to be had between very fast layer three routing (or other processing of data units) done by dedicated hardware, and the flexibility that may be required in different networking operations. This flexibility is often achieved by using modifiable software to control data handling. Modern networks are often called on to carry a wide variety of network traffic under a wider variety of protocols, all over the same network hardware. Therefore, a networking device hard-wired to determine a flow based on a source and destination address at a IP or IPX layer may not be able to establish a different flow should it be desired based on an Ethernet address of a packet. The device also may not be able to be reconfigured to handle the inevitable changes to network protocols or new protocols that are developed.
What is needed is a mechanism that would allow a high performance communication device to perform routing or sorting functions very quickly in hardware while allowing the operation of the routing function and flow assignment be specified and configured programmably so that it can be easily changed and can flexibly respond to different requirements of different network protocol layers.