Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1997-09-15
2001-08-14
Maung, Zarni (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C709S234000, C709S233000, C707S793000
Reexamination Certificate
active
06275861
ABSTRACT:
This application has been filed with a microfiche appendix of 169 frames on 2 sheets comprising a preliminary user manual for apparatus related to the invention. A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
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 processin
Chaudri Imran
Seetharam Srini Wishnu
Allen Kenneth R.
Maung Zarni
PMC-Sierra Inc.
Romero Almari
Townsend and Townsend / and Crew LLP
LandOfFree
Method and apparatus to identify flows in data systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to identify flows in data systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to identify flows in data systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2519451