Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match
First Claim
1. A computer-readable medium having stored thereon a data structure, the data structure comprising:
- a first search node;
a first child array including a first internal node and a second search node; and
a first leaf array including a plurality of first leaf array entries;
wherein the first search node includes a pointer to the first child array;
wherein the first internal node includes a pointer to the first leaf array; and
wherein the second search node includes a pointer to one of the plurality of first leaf array entries.
0 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
303 Citations
37 Claims
-
1. A computer-readable medium having stored thereon a data structure, the data structure comprising:
-
a first search node;
a first child array including a first internal node and a second search node; and
a first leaf array including a plurality of first leaf array entries;
wherein the first search node includes a pointer to the first child array;
wherein the first internal node includes a pointer to the first leaf array; and
wherein the second search node includes a pointer to one of the plurality of first leaf array entries. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method performed using a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by an extending bitmap, the method comprising:
-
(a) retrieving a search node at a current level within the tree data structure;
(b) updating a current best match identifier in response to determining if a new best match exists;
(c) indexing into a current level extending bitmap to determine whether or not a matching next level node exists;
(d) in response to said determining the matching next level node exists, repeating step (a), (b) and (c) for the current level being a next level identified based on said indexing into the current level extending bitmap to determine an offset within an internal node indicted by the search node; and
(e) in response to said determining the matching next level node does not exist, performing steps including;
retrieving an internal node indicated by the current level search node; and
identifying a search result based on the current best match identifier or based on a pointer in the current level search node to a leaf node. - View Dependent Claims (12, 13)
-
-
14. An apparatus for determining a search result based on a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by an extending bitmap, the apparatus comprising:
-
means for retrieving a search node at a current level within the tree data structure;
means for updating a current best match identifier in response to determining if a new best match exists;
means for indexing into a current level extending bitmap to determine whether or not a matching next level node exists;
means for indexing into the current level extending bitmap to determine an offset within an internal node indicted by the search node;
means for retrieving an internal node indicated by the current level search node; and
means for identifying a search result based on the current best match identifier or based on a pointer in the current level search node to a leaf node. - View Dependent Claims (15, 16)
-
-
17. A computer-readable medium containing computer-executable instructions for performing steps using a tree data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one, each of the plurality of strides represented by a tree bitmap and indications of child paths represented by an extending bitmap, said steps comprising:
-
(a) retrieving a search node at a current level within the tree data structure;
(b) updating a current best match identifier in response to determining if a new best match exists;
(c) indexing into a current level extending bitmap to determine whether or not a matching next level node exists;
(d) in response to said determining the matching next level node exists, repeating step (a), (b) and (c) for the current level being a next level identified based on said indexing into the current level extending bitmap to determine an offset within an internal node indicted by the search node; and
(e) in response to said determining the matching next level node does not exist, performing steps including;
retrieving an internal node indicated by the current level search node; and
identifying a search result based on the current best match identifier or based on a pointer in the current level search node to a leaf node. - View Dependent Claims (18, 19)
-
-
20. A method for traversing a tree data structure stored in one or more computer-readable mediums based on an input search data string, the method comprising performing for each of a plurality of portions of the input search data string a set of steps including:
-
(a) receiving a search progression context of a partially completed tree traversal, the search progression context including a next node address;
(b) resuming said traversal of the tree data structure including repeatedly performing steps (i)-(iv) for traversing the tree data structure corresponding to a next one of the plurality of portions of the input string;
(i) distributing a lookup request including the next node address to one of a plurality of memory devices;
(ii) receiving a lookup result from said one of the plurality of memory devices, the lookup result including a search node;
(iii) updating a current best match identifier in response to determining if a new best match exists;
(iv) indexing into a current level extending bitmap of the search node to determine whether or not a matching next level node exists;
(v) generating a new value of the next node address; and
(c) generating a new value for the search progression context. - View Dependent Claims (21, 22, 23)
-
-
24. A computer-readable medium containing computer-executable instructions for performing a method for traversing a tree data structure based on an input search data string, the method comprising performing for each of a plurality of portions of the input search data string a set of steps including:
-
(a) receiving a search progression context of a partially completed tree traversal, the search progression context including a next node address;
(b) resuming said traversal of the tree data structure including repeatedly performing steps (i)-(iv) for traversing the tree data structure corresponding to a next one of the plurality of portions of the input string;
(i) distributing a lookup request including the next node address to one of a plurality of memory devices;
(ii) receiving a lookup result from said one of the plurality of memory devices, the lookup result including a search node;
(iii) updating a current best match identifier in response to determining if a new best match exists;
(iv) indexing into a current level extending bitmap of the search node to determine whether or not a matching next level node exists;
(v) generating a new value of the next node address; and
(c) generating a new value for the search progression context. - View Dependent Claims (25, 26, 27)
-
-
28. An apparatus for traversing nodes of one or more tree data structures based on an input data string, the apparatus comprising:
-
a tree bitmap next address mechanism for determining a memory address of a next node of a particular tree data structure of said one or more tree data structures, the next node corresponding to a portion of the input data string;
a plurality of memory devices for storing said one or more tree data structures and for returning the next node in response to a retrieval request; and
a memory manager, coupled to the tree bitmap next address mechanism and the plurality of memory devices, for distributing the retrieval request to one of the plurality of memory devices;
wherein each of said one or more tree data structures include;
a first search node;
a first child array including a first internal node and a second search node; and
a first leaf array including a plurality of first leaf array entries;
wherein the first search node includes a pointer to the first child array;
wherein the first internal node includes a pointer to the first leaf array; and
wherein the second search node includes a pointer to one of the plurality of first leaf array entries. - View Dependent Claims (29, 30, 31, 32, 33)
-
-
35. An apparatus for traversing a tree data structure stored in one or more computer-readable mediums based on an input search data string, the apparatus comprising:
-
means for receiving a search progression context of a partially completed tree traversal, the search progression context including a next node address; and
means for resuming said traversal of the tree data structure;
means for distributing a lookup request including the next node address to one of a plurality of memory devices;
means for receiving a lookup result from said one of the plurality of memory devices, the lookup result including a search node;
means for updating a current best match identifier in response to determining if a new best match exists;
means for indexing into a current level extending bitmap of the search node to determine whether or not a matching next level node exists;
means for generating a new value of the next node address; and
means for generating a new value for the search progression context. - View Dependent Claims (36, 37)
-
Specification