Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-04-07
2003-05-27
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C711S117000
Reexamination Certificate
active
06570877
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of data communications networks. More particularly, the present invention relates to a method and apparatus for implementing a facility within a component of a data communications network that tracks packet flows with a content addressable memory (CAM) for managing and processing the contents of that CAM.
2. The Background
In switched packet data communications systems, packets are received, modified and transmitted by network node devices known as routers, switches and switching routers. Regardless of the nomenclature, such network node devices typically utilize forwarding engines to maintain flow information relating to each related stream of packets. Flow information for a particular packet flow should be maintained in a local memory at the network node while the packet flow is extant on the network. Flow information should be purged from the memory when the packet flow has stopped so that the memory does not become full. For example, if a user on a computer network is contacting a particular web server on the Internet, the communications from that web server to the user constitute a particular “flow”. When the user switches to another web server, those communications constitute a different “flow”. The information stored by the Forwarding Engine may be used to reconfigure or rewrite a packet so that it is forwarded to the next node in its journey through the data communications network. It may also be used to provide statistical or accounting data, it may also be used for bridging and learning as well as a plethora of other applications. Once the user disconnects from the first web server, that flow is no longer useful and packets will stop coming through the network node device which match that flow. It is that flow information which should be purged eventually.
With the growth in the use of networks such as LANs, (local area networks), WANs (wide area networks), the Internet and corporate intranets, the processing rates of packets through nodes on the networks have increased drastically and need to increase even more in order to meet future anticipated demand for communications speed and volume. Furthermore, the diversity of different flows has increased so that there are drastically more flows to keep track of than there were in the past. Furthermore, flows appear and terminate much more quickly than in the past due to the variety of services available on such networks. Finally, it is becoming more important to be able to gather statistical and accounting information relating to the various flows for network maintenance, design and accounting purposes.
One solution is to keep track of these flows in large tables of Random Access Memory (RAM) or Static RAM (SRAM). Such tables can store forwarding information for packet flows based upon the packet's Layer 2 and/or Layer 3 information. They can also store statistical information relating to such flows and permit it to be updated frequently. When such a solution is used, the “learning” function, whereby portions of new flows are written into the memory, is typically performed by packet processing hardware. This is because of the inherent speed advantage that hardware has over CPU (central processing unit)-processed software solutions. In the learning function the table stored in memory is modified to add information taken from newly detected packet flows. Because the table can be large (having hundreds of thousands of entries or more) and the flow entries may contain hundreds of bits of information, it is desirable to hash the entries based upon a reduced number of the flow bits and therefore scatter the entries pseudo-randomly throughout the table.
Once a Forwarding Table is established, however, it is important to be able to manage it. Even a table with millions of possible entries will eventually become full if no mechanism exists to purge entries every once in awhile. Traditionally, such routines have been executed in software by a CPU associated with the network node device.
A CPU has a limited number of instruction cycles that it may accomplish in a given amount of time. Some of the time the CPU is free to access the Forwarding Table, some of the time it is not free to access the Forwarding Table. Given the speed at which modern network node devices operate, it is simply impractical for a software routine under the control of a CPU to serially access each entry in a Forwarding Table and then act on it. Accordingly, a need exists for a mechanism whereby a large, table of packet forwarding information may be managed quickly by a CPU without causing a significant impact on system throughput or responsiveness.
SUMMARY OF THE INVENTION
A hardware search engine facility is provided to allow CPU search and update of a Forwarding Table CAM under the control of software running on the CPU. The hardware search engine provides one or more comparand-mask pairs which allow for a match, exclusion or magnitude comparison on specific entry values and/or the option to ignore or “don't care” certain bits of the entry. Control registers may be set in software to specify a start address and stop address in the CAM for the search. An indication of valid or invalid entries may be provided as well. Once the search is initiated by software, the search engine will read the entries sequentially starting from the programmed start address. It will perform a compare using the comparand-mask pair and attempt to identify a match. The locations in the CAM which match the search criteria may be put into a CPU-accessible memory. If the memory fills up before it can be read by the software, the search may be halted until the memory is emptied. A programmable action may instead, or in addition, be set to take place in the event of a match. Such programmable actions may include, but are not limited to, marking the entry, deleting the entry, change status bits corresponding to the entry, rewriting some of the entry, and the like.
REFERENCES:
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5339311 (1994-08-01), Turner
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5408472 (1995-04-01), Hluchyj et al.
patent: 5414705 (1995-05-01), Therasse et al.
patent: 5430715 (1995-07-01), Corbalis
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5513172 (1996-04-01), Shikama et al.
patent: 5570361 (1996-10-01), Norizuki et al.
patent: 5621721 (1997-04-01), Vatuone
patent: 5649109 (1997-07-01), Griesmer et al.
patent: 5699521 (1997-12-01), Iizuka et al.
patent: 5752242 (1998-05-01), Havens
patent: 5787253 (1998-07-01), McCreery et al.
patent: 5883893 (1999-03-01), Rumer et al.
patent: 5893162 (1999-04-01), Lau et al.
patent: 5913037 (1999-06-01), Spofford et al.
patent: 5920886 (1999-07-01), Feldmeier
patent: 5920900 (1999-07-01), Poole et al.
patent: 5922051 (1999-07-01), Sidey
patent: 5938736 (1999-08-01), Muller et al.
patent: 6065064 (2000-05-01), Satoh et al.
patent: 6115378 (2000-09-01), Hendel et al.
patent: 6141738 (2000-10-01), Munter et al.
patent: 6178414 (2001-01-01), Beckmann et al.
patent: 6289414 (2001-09-01), Feldmeier et al.
patent: 6356551 (2002-03-01), Egbert
patent: 2002/0010793 (2002-01-01), Noll et al.
Hao Che. “Adaptive Resource Management for Flow-Based IP/ATM Hybird Switching Systems.” IEEE/ACM Transactions on Networking, vol. 6, No. 5. Oct. 1998.
Kloth Raymond J.
Morishige Kevin D.
Pullela Venkateshwar Rao
Cisco Technology Inc.
Ferris Derrick W
Marcelo Melvin
Ritchie David B.
Thelen Reid & Priest LLP
LandOfFree
Search engine for forwarding table content addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Search engine for forwarding table content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search engine for forwarding table content addressable memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3033654