Multiplex communications – Network configuration determination
Reexamination Certificate
1998-06-25
2003-02-18
Ton, Dang (Department: 2661)
Multiplex communications
Network configuration determination
C370S408000
Reexamination Certificate
active
06522632
ABSTRACT:
BACKGROUND OF THE INVENTION
A prefix search is used in networking to route and classify packets. The route to be used for a packet and its classification are determined by finding the longest matching prefix in a set. For example a packet using IPv6 (internet protocol version 6) has a 128-bit destination address. A router determines the output port over which such a packet should be routed by searching a set of variable-length binary strings to find the longest string that matches a prefix of the destination address. For classification purposes, other fields of the header, such as the port number, may also be included in the string to be matched.
To illustrate the problem of prefix search, consider the list of prefix character strings shown in
FIG. 1
in alphabetical order. The principle is the same with binary strings. Given a search string, such as “cacea”, the goal is to find the longest stored string that exactly matches a prefix of this string. Although a simple linear search of the list finds that this string falls between “cab” and “cad”, one must scan several strings backward from this point to find that the longest matching prefix is “ca” In actual routing tables, which may contain hundreds of thousands of entries, the matching prefix may be far from the point where the linear search fails. An optimized data structure is needed to efficiently find the matching prefix.
A prior method for performing longest prefix matching employs a data structure called a trie. A trie for the prefix list of
FIG. 1
is shown in FIG.
2
. As shown, the trie is a tree structure in which each node of the tree resolves one character of the string being matched. Each internal node consists of a list of characters. Associated with each character is an outgoing link either to another internal node, a rectangle in the figure, or to a leaf node, a circle in the figure. A slash at the start of a node indicates that a prefix leading to that node with no additional characters is part of the list. Each leaf node holds the result data associated with the prefix leading to that leaf node, and in the figure, the leaf nodes are labeled with these prefixes. The result data might, for example, be the output port associated with a data packet and a flow-identifier.
To search the trie, one starts at the root node, node
1
in the figure, and traverses the tree by following the outgoing link at each node corresponding to the next character in the string to be matched. When no matching outgoing link can be found, the longest matching prefix has been found. For example, given the string “cacea” we start at node
1
. The “c” directs us to node
4
. The “a” directs us to node
8
. As we cannot find a match for the next character, “c”, at node
8
, we follow the link associated with the slash to the leaf node associated with the longest matching prefix, “ca”. Note that if prefix “ca” were not in the list, we would need to backtrack at this point to node
4
for prefix “c”.
Another prior method for prefix matching is to perform binary search on a table. However, as described by Radia Perlman, Interconnections, Bridges and Routers, Addison Wesley, 1992, pages 233-239, and shown in
FIG. 3
, since binary search will find the closest matching string, rather than the longest matching prefix, we must make two modifications to the list to apply this technique. First, we insert two entries for every entry in the list that encloses other entries, that is, that would serve as a longest matching prefix for another prefix in the list but for the other prefix itself being in the list. One of those entries is terminated by the symbol 0, which comes alphabetically before all characters, and one by the symbol 1, which comes alphabetically after all characters. These two entries act as parentheses enclosing all entries that contain the prefix. Second, we attach to each entry in the list not ending in a 0 a pointer to the nearest enclosing entry.
FIG. 3
shows the list of
FIG. 1
augmented in this manner. Note that the prefix “ca” has been replaced by the two entries “ca
0
” and “ca
1
” that bracket all entries containing the prefix “ca” and that all of these entries have a pointer back to “ca
0
”.
To search the augmented list of
FIG. 3
for the longest matching prefix, one searches for a string equal to a prefix of the target or the alphabetically closest pair of strings. Strings ending in “0” or “1” never exactly match a prefix of the target string because “0” and “1” do not match any character of the target string. If the search finds an exact prefix of the target string, the result data associated with the string is retrieved. Otherwise, the search found the closest pair of stored strings, Sa and Sb. In this case there are three possibilities:
1. If Sa ends in a “0” symbol, then the longest matching prefix is this string with the “0” removed.
2. If Sb ends in a “1” symbol, then the longest matching prefix is this string with the “1” removed.
3. Otherwise, an enclosing pointer from Sa is followed to find a string ending in a “0” symbol which encloses Sa and the nearest match is that string with the “0” symbol removed.
For example, a search for “cacea” will end between “cab” and “cad”. Since this is not an exact match, “cab” does not end in “0”, and “cad” does not end in “1”, the pointer from “cab” is followed back to “ca
0
” giving the longest matching prefix, “ca”. Similarly a search for “cb” will end between “ca
1
” and “cc” and follow the pointer from “ca
1
” back to the common prefix, “c”.
SUMMARY OF THE INVENTION
While the trie structure and binary search strategy work, they are not well suited for implementation in a hardware search engine. The trie requires a memory access for every character of a string and possible backtracking if a match is not found. This makes it inefficient in terms of memory bandwidth usage. The binary search strategy requires storing two result pointers for the majority of prefixes, one for a direct match and one to the enclosing string or its associated result. This makes it inefficient in terms of memory usage.
The present invention relies on a data structure, an augmented tree, that stores prefix sets in a manner that enables efficient searching and a hardware engine for searching the augmented tree. The augmented tree stores the prefix set with enclosing prefixes in a tree structure similar to a B-tree, a tree with a radix greater than one previously used to efficiently search for exact matches by optimizing the tree node size to the size of data blocks retrieved from storage discs.
In accordance with the invention, a prefix search data structure comprises a tree structure having internal nodes for identifying subsequent nodes from prefix search keys. Leaf nodes each comprise a set of prefix keys to be compared to a prefix search key. The sets of prefix keys of plural leaf nodes together form a list of prefix keys including enclosing prefix key pairs.
In preferred embodiments, the internal nodes include partitioning nodes, each comprising a set of prefix keys to be compared to a prefix search key. Prefix keys from one node point to subsequent nodes through a common pointer and indexes. Each internal node may also comprise a node-size parameter that defines the size of that node and a child-node-size parameter that defines the size of fixed size child nodes to which the common pointer of the internal node points.
Each of plural leaf nodes may comprise a single enclosing pointer associated with an enclosing prefix key which encloses a prefix key of the leaf node. Preferably, a common pointer of each leaf node is a result pointer to a block of results for the node, and the enclosing pointer points to a result in a block of results for another node. Each leaf node may comprise a node-size parameter that defines the size of the leaf node as well as the size of the results block.
Individual nodes can be sized to optimize memory timing. In particular, the data retrieved for any node may correspond to the size of the data block most efficiently retrieved from memory storage. Preferably, each of
Carvey Philip P.
Dally William J.
Dennison Larry R.
Mann William F.
Waters Gregory M.
Avici Systems
Hamilton Brook Smith & Reynolds P.C.
Ton Dang
LandOfFree
Apparatus and method for efficient prefix search does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for efficient prefix search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for efficient prefix search will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3115672