Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-20
2003-02-25
Nguyen, Steven (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395320, C711S216000
Reexamination Certificate
active
06526055
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to network packet routing and, specifically, to a method and apparatus for routing packets in a network in accordance with a longest prefix match of the destination address of the packet.
In many network systems, information transmitted through the network is organized in “packets.” Each packet is transmitted by a sender node and routed from node to node in the network until it reaches a destination node specified in the packet. Each node that receives a packet must be able to decide which node should next receive that packet. This determination is generally done using a “forwarding table” in the node. The node looks at the destination address of each individual packet and routes the packet to another node in accordance with the routing table and the packet's destination address. This process is repeated in successive nodes until the packet reaches its destination.
In conventional networks, each node contains a forwarding table that maps an address prefix of a destination address in received packets to respective ports in the network. Routers, switches, ISs (Intermediate Systems), IMPs (Interface Message Processors), gateways and other similar elements also contain forwarding tables, and the term “router” is used herein to refer to any node that routes or forwards received packets. If a received packet's destination address has length W, the prefixes in the forwarding table may have lengths anywhere in the range 0 to W inclusive. For example, if a forwarding table contains routing information for prefixes of 1, 10, 100, 10010, and 111, a destination address of 10111 in a received packet has a longest prefix match of 10, since 10 is the longest prefix in the forwarding table that completely matches the destination address. When a packet arrives at a router, the router finds the longest prefix match in the router's forwarding table and forwards the received packet accordingly. A longest matching prefix in the forwarding table needs to be found in a timely manner, since packets generally are routed in real-time and a router's performance is based on how quickly it can forward a packet.
As an example, two conventional methods for performing address lookup in forwarding tables are binary search and TRIE (each of which is documented in Perlman, “Interconnection: Bridges and Routers,” pp 233-239, published by Addison Wesley 1992). Neither of these methods provide an ideal solution to the problem of finding a longest prefix match. Straightforward binary search, for example, does not work for address prefix lookups because the address prefixes can have different lengths. Therefore, a destination address may not match the prefixes in accordance with their alphabetized order. In the example above, if a forwarding table contains prefixes in alphabetized order of 1, 10, 100, 10010, and 111, an address of 10111 in a received packet will match the forwarding table prefix 10, even though it would be alphabetized after the prefix 10010. Because the forwarding table can have prefixes of varying lengths, finding a longest matching prefix in a forwarding table that matches a received destination address in as short a time as possible can be problematic. Similarly, while the TRIE method works correctly as a forwarding method, it lacks efficiency in routers where extremely high speeds are a requirement.
SUMMARY OF THE INVENTION
Various embodiments of the present invention can be implemented in hardware, software, or some combination of the two. In the described embodiments of the present invention, a node receives a packet that contains a destination address. The node then checks a router database to determine a longest prefix match for the destination address and further determines a port associated with the longest prefix match in the router database. The router database contains comparison values based on forwarding information specific to the router. A method in accordance with the present invention involves two parts: a first part looks at the routing information associated with a particular router and determines the data in the router database for that router. A second part searches the router database whenever a packet is received to determine a longest prefix match for a destination address in the received packet. The received packet is then routed to the port associated with the longest prefix match.
It is an important aspect of the present invention that a node routes a received packet in as little time as possible. Thus, while creation of the router database itself is not particularly time-critical, the actual process of searching the router database must be done very quickly. In the described embodiments of the present invention, a quick search is possible partly because of the way the router database is organized and partly because the search can involve parallel comparisons and/or parallel loads. In certain embodiments, the increase in speed is also due to specialized hardware/software used to search the router database.
Specifically, the described embodiments of the present invention allows lookup of a particular destination address prefix of size 0 through W to be performed in O(log
k
N), where N is the number of “padded prefixes” in the router database. In the described embodiments, the routing information for each node includes several prefix/port pairs, which are used to determine the content of the router database for the node. In general, there are twice as many “padded prefixes” in the router database as there are prefixes in the router's forwarding information (there may sometimes be fewer than twice as many padded prefixes, as described below in detail in connection with various embodiments of the invention).
Specifically, the router database is organized into a comparison table having a number of “entries.” Each “entry” contains up to k−1 values (or k values, in other embodiments). As used herein, “k” is the number of parallel elements required to compare the values in one entry in a router database to a received address (when the invention is implemented in hardware). Each of the values in a comparison table entry contains a “padded prefix.” A corresponding table includes a pointer to a “next entry” of data in the comparison table and may include additional information, such as port information. When a destination address in a packet is first received by a router, the values of a first one of the entries in the router database are loaded into the router to determine a port corresponding to the received destination address. As mentioned above, each entry in the comparison table has up to k−1 (or k) values.
Certain embodiments of the invention allow the k−1 (or k) values in a router database entry to be compared to the destination address in parallel. While the described embodiment can also be implemented on a general purpose computer, or on a computer having multiple processors, at least one embodiment of the present invention is implemented using hardware allowing very fast, parallel comparison of the values in a router database entry against the received destination address. For example, a described hardware implementation uses k comparisons. Another described hardware implementation uses k−1 comparisons. A described software implementation uses k−1 comparisons.
The comparison of the values in a first entry of the router database against the destination address identifies a next entry in the comparison database, which is, in turn, loaded and compared to the destination address. This process of loading a “next entry” from the comparison table and performing fast k-ary compares against the destination address is repeated until there are no more “next entries” in the database. At this point, a longest prefix match has been found and the packet is routed to a port associated with the longest prefix match in the router database.
In at least one described embodiment, creation of the router database proceed as follows. (Each router has associated routing i
Chiu Dah Ming
Perlman Radia J.
Nguyen Steven
Squire Sanders & Dempsey L.L.P.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for longest prefix address lookup 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 for longest prefix address lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for longest prefix address lookup will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3124225