Electrical computers and digital processing systems: multicomput – Computer-to-computer data addressing
Reexamination Certificate
2002-02-01
2004-02-10
Jean, Frantz B. (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data addressing
Reexamination Certificate
active
06691171
ABSTRACT:
TECHNICAL FIELD
This invention relates to the technologies of digital data communication, digital pattern recognition, digital sorting and search processing, data compression processing and wire speed Internet network routing.
BACKGROUND OF THE INVENTION
The Internet currently has a few tens of backbone routers, each serving up to a few thousand smaller enterprise networks. The major performance bottleneck in backbone routers is the time taken to look up a route in a forwarding table. On receiving a data packet, an input port looks up the packet's destination address in its forwarding table to determine the packet's destination port. Since the forwarding table may contain a large number of routing entries, it is time consuming to match an incoming packet with these routing entries. Furthermore, to reduce database size and routing update traffic, the forwarding table typically contains a smaller set of prefixes, instead of all of the assigned Internet addresses. This requires a more complex lookup because an incoming packet may match multiple routing entries and the entry with the longest prefix match needs to be determined.
Prefixes are patterns that match the first n binary bits of a destination address, where n is a positive integer. The forwarding table stores routing entries that are typically of the form <network address/mask, port>, where “mask” is a number that specifies the first number of bits in the “network address” as the prefix to be matched for “port,” which identifies a specific destination port. The speed of a route lookup is determined by the number of memory access required to find the matching route entry, and by the speed of the memory. Data structures for the route entries in the forwarding table can be designed to reduce lookup time. A second consideration in designing forwarding table data structures is the time taken for table updates, such as prefix insertion, deletion, route change, and the like. Since a forwarding table may need to be updated relatively less frequently, conventional forwarding table data structures and address matching algorithms are usually designed to optimize route lookup at the expense of the time taken to update the table.
A common type of data structure for the forwarding table is a trie. The trie is a general-purpose data structure for storing strings, where each string is represented by a leaf in a tree structure and the value of the string corresponds to the path from the root of the tree to the leaf. A basic trie structure
101
for a set of binary strings (P
1
, P
2
, P
3
, P
4
, P
5
, P
6
, P
7
, and P
8
) is shown in FIG.
1
A. This simple structure is not very efficient. The number of nodes (N
1
to N
13
) may be large and the average depth (the average length of a path from the root to the longest matching prefix) may be long. As an improvement, Srinivasan and Varghese designed a data structure and searching algorithm called controlled prefix expansion. See V. Srinivasan and G. Varghese, “Faster IP Lookups Using Controlled Prefix Expansion,” ACM Sigmetrics'98, ACM Transactions on Computer Systems, March 1999. The data structure and search algorithm is based on a well-known fact that a smaller number of distinct prefix lengths lead to faster search for the longest prefix match. Using the controlled prefix expansion, a set of prefixes with M distinct lengths is converted to a set of prefixes with N distinct lengths, where N<M.
FIG. 1B
illustrates how the original set of prefixes in
FIG. 1A
, which has 7 distinct lengths, can be expanded into an expanded set of prefixes having 3 distinct lengths.
FIG. 1B
also shows how the expanded prefix set is placed in a multi-bit trie having a maximum path length of 3 compared to the binary trie in
FIG. 1A
that has a maximum path length of 7.
However, the controlled expansion search algorithm has the disadvantage of requiring prefix expansion for prefix lengths that are different from the N distinct lengths. Prefix expansion typically requires complicated software processing such as prefix sorting, prefix expanding, prefix restructuring, and the like when the lookup table is being updated. When prefix number reaches multi-million or more in a backbone router, the computer power consumed to handle these processing tasks will be significant. Furthermore, the controlled expansion search algorithm typically requires a special mechanism to handle multiple destinations on a same trie-walking path of multi-bit tries. One example of such a special mechanism is an auxiliary table for multiple destinations, which usually increases lookup latency and slows down performance of a lookup engine.
SUMMARY OF INVENTION
The present invention provides a method of searching for a longest prefix match for an address having a number of binary bits among a plurality of entries having different lengths of bits. The entries are associated with a trie having a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K
1
-bit trie match and at least one trie node for K
2
-bit trie match, wherein K
1
and K
2
are two different positive integers. Each of the entries corresponds to one trie node, and at least one trie node for L-bit trie match points to the first trie unit. Each trie node corresponds to a first, second, third, or fourth type of trie node. The method of searching according to an embodiment of the present invention first splits the address into at least a first key and a second key, each key including a predetermined number of address bits. Then, it determines a first matching node among the first number of trie nodes based on the address bits in the first key. Responsive to the first matching node corresponding to the first or second trie node type, the method selects the entry corresponding to the first matching node as the longest prefix match for the address. Also, responsive to the first matching node corresponding to the third or fourth trie node type, the method determines at least one second matching node in the first trie unit based upon the address bits in the second key.
According to another embodiment of the present invention, the trie further includes at least a second trie unit and the address is further split into at least a third key. The method of searching further determines the trie node type of the second matching node. Responsive to the second matching node corresponding to the first or second trie node type, the method selects the entry corresponding to the second matching node as the longest prefix match for the address. Responsive to the second matching node corresponding to the third or fourth trie node type, the method determines a third matching node in the second trie unit based upon the address bits in the third key.
According to one embodiment of the present invention, the address is an Internet address included in an Internet data packet and the entries include prefixes each associated with a destination port in an Internet router. The present invention enables fast and accurate routing of Internet data packets by using the trie structure according to the present invention.
According to still another embodiment of the present invention, a system searches for a longest prefix match for an address having a number of binary bits among a plurality of entries having different lengths of bits. The entries are associated with a trie having a first number of trie nodes for L-bit trie match, wherein L is a predetermined integer greater than 1, and at least a first trie unit including at least one trie node for K
1
-bit trie match and at least one trie node for K
2
-bit trie match, wherein K
1
and K
2
are two different positive integers. Each of the plurality of entries corresponding to one trie node, and at least one trie node for L-bit trie match points to a trie unit. Each trie node corresponds to a first, second, third, or fourth type of trie node. The system comprises at least a first memory unit and a second memory unit coupled
Fenwick & West LLP
Jean Frantz B.
Micrel Inc.
LandOfFree
Method and system for address lookup in data communication 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 system for address lookup in data communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for address lookup in data communication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3316247