Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-28
2004-02-24
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S401000
Reexamination Certificate
active
06697363
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to communications networks and more particularly to a method and apparatus for longest matching prefix determination in communications networks.
BACKGROUND OF THE INVENTION
Data communications networks utilize addresses to forward packets of information between users. As data communication networks continue to evolve, the number of addresses supported, the amount of traffic, and the speed with which the traffic is traveling are all increasing. As such, routers in such communications networks must determine sources and destinations of endstations associated with traffic more quickly than in the past.
Routing data packets in Internet Protocol (IP) networks requires determining the best matching prefix corresponding to the source and destination addresses for the packet, which may also be referred to as determining a longest prefix match (LPM) for the addresses. Routers that forward packets typically include a database that stores a number of address prefixes and their associated forwarding decisions that indicate where the data should be sent next (next hops). When the router receives a packet it must determine which of the prefixes in the database is the best match for the packet.
Binary tries have commonly been used for determining the LPM for data packets.
FIG. 1
illustrates a basic binary trie structure that includes a set of binary prefixes. The example trie illustrated in
FIG. 1
corresponds to a six-bit address space that is used to simplify the discussion. The shaded circles indicate valid prefixes. The binary trie illustrated in
FIG. 1
contains a default route corresponding to the root of the trie and a plurality of valid prefixes that may only be partially specified (e.g. 000XXX), or fully specified (e.g. 000100). Bits included in the address to be resolved are used to make branching decisions at each of the nodes within the trie, where 0 bits cause a branch to the left and one bits cause a branch to the right. As is illustrated, the binary prefix 000XXX is a valid prefix, as is the prefix 000100. Although a packet that has an address that matches the prefix 000100 would also match the valid prefix 000XXX, the longest matching prefix is 000100, and thus 000100 is the prefix which must be selected for the address.
FIG. 2
illustrates a prior art technique for simplifying the basic binary trie illustrated in FIG.
1
.
FIG. 2
illustrates a Patricia trie that flattens the basic binary trie in areas where decisions at nodes within the trie structure cannot result in more than one possible prefix determination. In other words, nodes within the trie structure that are traversed in route to a valid prefix with no further decision making required are compressed out. Such path compression can reduce the average number of memory accesses required to determine the LPM for an address to log
2
N accesses, where N is the number valid prefixes stored in the trie. However, in the worst case when a path cannot be compressed, Patricia trees may require L memory accesses to resolve an LPM, where L is equal to the number of bits in the address, which may be 32 bits in some applications such as IP version 4 and 128 bits for IP version 6. The variability in the number of memory accesses requires presents problems for high-speed router design. Furthermore, even if all LPM determinations could be made with log
2
N memory accesses, the memory bandwidth requirements would still make router design impractical when high link rates must be supported.
Another trie processing method that attempts to reduce the time it takes to determine the appropriate prefix is to create a multi-way branching trie that processes multiple bits of the address in a single step. This is illustrated in
FIG. 3
, where a trie that exists in a 32-bit address space has been broken into a set of steps, or strides. As is illustrated, the strides may be selected to be of varying bit lengths. Thus, 4-bit strides, 8-bit strides, and even 16-bit strides may be employed to traverse the trie structure. For each stride, a portion of the address is compared with sets of bits corresponding to that stride to determine if a LPM has been resolved or if one or more additional strides must be traversed in order to determine the LPM.
In order to be able to process a number of address bits in a stride, prefix expansion must be performed so that there is a valid prefix for each binary value at the cut depth for the stride, where the cut depth is determined by the size of the stride.
FIG. 4
shows the root level of a 5-bit portion of a trie structure after prefix expansion. The cut depth is the bottom set of prefixes of the trie structure illustrated in FIG.
4
and is shown surrounded by a long rectangular box. In order to have valid prefixes at all of the nodes at the cut level, new nodes may have to be created at the cut depth in order to make the trie complete. Values for newly created nodes are then propagated from parent nodes. Propagation of a prefix value to a newly created node is illustrated via the arrows originating from parent nodes. One example is the labeled parent node that propagates a valid prefix to the three labeled propagated nodes. As can be seen, the highest level, or root node also serves as a parent node to some of the nodes at the cut level.
Those nodes in the trie structure of
FIG. 4
that represent a final prefix match and a resolved forwarding decision are represented by a shaded circle, whereas those nodes that indicate the next stride must be accessed in order to continue towards determination of a forwarding decision are represented by shaded squares. Thus, shaded circles represent a point at which the search for prefix match is terminated, whereas shaded squares indicate that the prefix match must exist at a deeper level in the overall trie structure and therefore the search is extended.
Because 2
N
valid prefixes are typically stored to process an N-bit stride, larger strides require a great deal of memory, which can be a limiting factor in the stride size chosen. Smaller strides require, on average, more memory accesses to ascertain the forwarding decisions. Thus, there is a trade-off between the amount of memory required to store the data for a trie structure and the number of memory accesses required to completely traverse the trie structure to the appropriate end prefix.
Therefore, a need exists for a method and apparatus that reduces the memory required to store values associated with strides in trie structures such that prefix matching can be performed using a minimal number of memory accesses.
REFERENCES:
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6396842 (2002-05-01), Rochberger
patent: 6590898 (2003-07-01), Uzun
patent: WO 00/02347 A2 (2000-01-01), None
Masanori Uga and Kohei Shiomoto, “A Fast and Compact Longest Match Prefix Look-Up Method Using Pointer Cache for Very Long Network Address”, Computer Communications and Networks, 1999. pp. 595-602, Eight International Conference on Boston, MA, USA Oct. 11-13, 1999 (1999-10-11), IEEE, Piscataway, N.J.
Scalable High Speed IP Routing Lookups, 1998.
Small Forwarding Tables for Fast Routing Lookups, Oct. 1997.
Scalable High Speed IP Routing Lookups, Oct. 1997.
Implementing a Dynamic Compressed Trie, May 10, 1998.
LandOfFree
Method and apparatus for longest matching prefix... 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 matching prefix..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for longest matching prefix... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302814