Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1998-07-31
2001-10-23
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C370S392000
Reexamination Certificate
active
06308219
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to routing table lookup.
2. Related Art
In a computer network, routing devices receive messages at one of a set of input interfaces, and forward them on to one of a set of output interfaces. It is advantageous for such routing devices to operate as quickly as possible, to keep up with the rate of incoming messages. In a packet routing network, each packet includes a header, including information used for routing the packet to an output interface for forwarding to a destination device (or to another routing device for further forwarding). Header information used for routing can include a destination address, a source address, and other information such as a destination device port, a source device port, a protocol, packet length, and a priority for the packet. Header information used by routing devices for other administrative tasks can include information about access control, accounting, quality of service, and other purposes.
One problem in the known art is that there can be a relatively large number of possible destinations, and therefore a correspondingly large number of possible output interfaces (herein called “routes”), one of which is to be associated with the incoming packet. It is advantageous for the routing devices to match the associated output interface with the incoming packet as quickly as possible. Due to the nature of routing in computer networks, it is also advantageous for the routing devices to match the associated output interface with the longest possible sub-string of the header information (such as the destination address or a combination of the destination address and the source address).
One method in the known art is to use a branching tree, which differentiates among possible routes in response to each individual bit of the header information. A variant of this method is to generate an M-way branching tree (herein called an “M-trie,” which has up to M possible branches at each node). An M-trie differentiates among possible routes in response to groups of bits in the header information.
One problem in the known art is that using M-tries generates frequent references to memory to access the nodes of the M-trie. The access speed of the memory thus provides a limitation on the speed of the routing device. Moreover, some of the nodes of the M-trie near its root are relatively more frequently referenced than other nodes. The access speed of the memory for repeated references to the same location thus provides a second limitation on the speed of the routing device.
Accordingly, it would be desirable to provide a method and system for rapid access to one or more M-tries for responding to header information. This advantage is achieved in an embodiment of the invention in which the M-tries are stored in a plurality of memory banks, some of which duplicate parts of the M-tries that are frequently referenced.
SUMMARY OF THE INVENTION
The invention provides a method and system for rapid access to one or more M-tries for responding to header information. The M-tries are stored in a plurality of memory banks, which are accessed in parallel to provide relatively greater access throughput. Parts of the M-tries that are (or are expected to be) frequently referenced are stored in multiple banks of the memory, to provide concurrent simultaneous access to those parts of the M-tries for parallel lookup of multiple routes.
In a preferred embodiment, regions of the multiple banks of the memory can be dynamically reallocated to provide improved access throughput to those multiple banks. The invention can be applied to routing decisions in response to destination addresses, to combinations of destination and source addresses (either for unicast or multicast routing), to access control decisions, to quality of service decisions, to accounting, and to other administrative processing in response to header information.
REFERENCES:
patent: Re. 33900 (1992-04-01), Howson
patent: 4131767 (1978-12-01), Weinstein
patent: 4161719 (1979-07-01), Parikh et al.
patent: 4316284 (1982-02-01), Howson
patent: 4397020 (1983-08-01), Howson
patent: 4419728 (1983-12-01), Larson
patent: 4424565 (1984-01-01), Larson
patent: 4437087 (1984-03-01), Petr
patent: 4438511 (1984-03-01), Baran
patent: 4439763 (1984-03-01), Limb
patent: 4445213 (1984-04-01), Baugh et al.
patent: 4446555 (1984-05-01), Devault et al.
patent: 4456957 (1984-06-01), Schieltz
patent: 4464658 (1984-08-01), Thelen
patent: 4499576 (1985-02-01), Fraser
patent: 4506358 (1985-03-01), Montgomery
patent: 4507760 (1985-03-01), Fraser
patent: 4532626 (1985-07-01), Flores et al.
patent: 4644532 (1987-02-01), George et al.
patent: 4646287 (1987-02-01), Larson et al.
patent: 4677423 (1987-06-01), Benvenuto et al.
patent: 4679189 (1987-07-01), Olson et al.
patent: 4679227 (1987-07-01), Hughes-Hartogs
patent: 4723267 (1988-02-01), Jones et al.
patent: 4731816 (1988-03-01), Hughes-Hartogs
patent: 4750136 (1988-06-01), Arpin et al.
patent: 4757495 (1988-07-01), Decker et al.
patent: 4763191 (1988-08-01), Gordon et al.
patent: 4769810 (1988-09-01), Eckberg, Jr. et al.
patent: 4769811 (1988-09-01), Eckberg, Jr. et al.
patent: 4771425 (1988-09-01), Baran, et al.
patent: 4819228 (1989-04-01), Baran, et al.
patent: 4827411 (1989-05-01), Arrowood, et al.
patent: 4833706 (1989-05-01), Hughes-Hartogs
patent: 4835737 (1989-05-01), Herrig et al.
patent: 4879551 (1989-11-01), Georgiou et al.
patent: 4893306 (1990-01-01), Chao et al.
patent: 4903261 (1990-02-01), Baran et al.
patent: 4922486 (1990-05-01), Lidinsky et al.
patent: 4933937 (1990-06-01), Konishi
patent: 4960310 (1990-10-01), Cushing
patent: 4962497 (1990-10-01), Ferenc et al.
patent: 4962532 (1990-10-01), Kasirai et al.
patent: 4965767 (1990-10-01), Kinoshita et al.
patent: 4965772 (1990-10-01), Daniel et al.
patent: 4970678 (1990-11-01), Sladowski et al.
patent: 4979118 (1990-12-01), Kheradpir
patent: 4980897 (1990-12-01), Decker et al.
patent: 4991169 (1991-02-01), Davis et al.
patent: 5003595 (1991-03-01), Collins et al.
patent: 5014265 (1991-05-01), Hahne et al.
patent: 5020058 (1991-05-01), Holden et al.
patent: 5033076 (1991-07-01), Jones et al.
patent: 5034919 (1991-07-01), Sasai et al.
patent: 5054034 (1991-10-01), Hughes-Hartogs
patent: 5059925 (1991-10-01), Weisbloom
patent: 5072449 (1991-12-01), Enns et al.
patent: 5088032 (1992-02-01), Bosack
patent: 5095480 (1992-03-01), Fenner
patent: 5115431 (1992-05-01), Williams et al.
patent: 5128945 (1992-07-01), Enns et al.
patent: 5136580 (1992-08-01), Videlock et al.
patent: 5166930 (1992-11-01), Braff et al.
patent: 5199049 (1993-03-01), Wilson
patent: 5206886 (1993-04-01), Bingham
patent: 5208811 (1993-05-01), Kashio et al.
patent: 5212686 (1993-05-01), Joy et al.
patent: 5224099 (1993-06-01), Corbalis et al.
patent: 5226120 (1993-07-01), Brown et al.
patent: 5228062 (1993-07-01), Bingham
patent: 5229994 (1993-07-01), Balzano et al.
patent: 5237564 (1993-08-01), Lespagnol et al.
patent: 5241682 (1993-08-01), Bryant et al.
patent: 5243342 (1993-09-01), Kattemalalavadi et al.
patent: 5243596 (1993-09-01), Port et al.
patent: 5247516 (1993-09-01), Bernstein et al.
patent: 5249178 (1993-09-01), Kurano et al.
patent: 5253251 (1993-10-01), Aramaki
patent: 5255291 (1993-10-01), Holden et al.
patent: 5260933 (1993-11-01), Rouse
patent: 5260978 (1993-11-01), Fleischer et al.
patent: 5268592 (1993-12-01), Bellamy et al.
patent: 5268900 (1993-12-01), Hluchyj et al.
patent: 5271004 (1993-12-01), Proctor et al.
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5274635 (1993-12-01), Rahman et al.
patent: 5274643 (1993-12-01), Fisk
patent: 5280470 (1994-01-01), Buhrke et al.
patent: 5280480 (1994-01-01), Pitt et al.
patent: 5280500 (1994-01-01), Mazzola et al.
patent: 5283783 (1994-02-01), Nguyen et al.
patent: 5287103 (1994-02-01), Kasprzyk et al.
patent: 5287453 (1994-02-01), Roberts
patent: 5291482 (1994-03-01), McHarg et al.
patent: 5305311 (1994-04-01), Lyles
patent: 5307343 (1994-04-01), Bostica et al.
patent: 5309437 (1994-05-01), Perlman et al.
patent: 5311509 (1994-05
Caldwell Andrew
Campbell III Sam G.
Cisco Technology Inc.
Maung Zarni
Skjerven Morrill & MacPherson LLP
LandOfFree
Routing table lookup implemented using M-trie having nodes... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing table lookup implemented using M-trie having nodes..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing table lookup implemented using M-trie having nodes... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2561652