Data processing: structural design – modeling – simulation – and em – Electrical analog simulator
Reexamination Certificate
1998-08-26
2002-08-06
Breene, John (Department: 2177)
Data processing: structural design, modeling, simulation, and em
Electrical analog simulator
C707S793000, C707S793000, C707S793000, C370S408000, C370S389000, C370S413000, C709S238000
Reexamination Certificate
active
06430527
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 conesponding, 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
51
. The “c” directs us to node
54
. The “a” directs us to node
58
. As we cannot find a match for the next character, “c”, at node
58
, 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
54
for prefix “c”.
Another prior method for prefix matching is to perform binary search on a table. However, as described by Radial 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 “ca0” and “ca1” that bracket all entries containing the prefix “ca” and that all of these entries have a pointer back to “ca0”.
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 “ca0” giving the longest matching prefix, “ca”. Similarly a search for “cb” will end between “ca1” and “cc” and follow the pointer from “ca1” 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 prior application Ser. No. 09/104,314, filed Jun. 25, 1998 discloses and claims 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. The 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 accordance with the present invention, prefix search circuitry is provided on an integrated circuit. A plurality of prefix search engines are provided oil the integrated circuit, each engine performing a prefix search of a prefix search data structure based on a prefix search key.
Preferably, prefix search keys embedded in input packet descriptors are distributed from an input queue over an internal network to the plural search engines and the results of the prefix searches are forwarded to an output queue. At the output queue, the search results are ordered in the same order that the corresponding input packet descriptors arrived at the input queue. The internal network may include an input bus from the input queue to the search engines and an output bus from the engines to the output queue.
Preferably, the search engines on the integrated circuit are associated with an array of memory units, each unit dedicated to a search engine within the integrated circuit. Each search engine reads data in bursts over integrated circuit data pins dedicated to the search engine, and each search engine addresses a memory unit over integ
Carvey Philip P.
Dally William J.
Dennison Larry R.
Mann William F.
Waters Gregory M.
Avici Systems
Breene John
Hamilton Brook Smith & Reynolds P.C.
Pham Khanh
LandOfFree
Prefix search circuitry and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prefix search circuitry and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prefix search circuitry and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2885894