Data structure using a tree bitmap and method for rapid classification of data in a database

• US 6,560,610 B1
• Filed: 08/10/1999
• Issued: 05/06/2003
• Est. Priority Date: 08/10/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Washington University In St Louis
• Inventors: Eatherton, William N., Dittia, Zubin
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): Black, Linh
• Application Number:
  US09/371,907
• Time in Patent Office: 1,365 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 707/500-542, 709/1, 709/200-203, 709/238, 709/247, 709/310-318, 709/328-332
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

In random access memory, a data structure of trie elements of compact and fixed size is provided in order to store elements of a hierarchical prefix-type data structure such that the data structure can be searched quickly. A trie element according to the invention contains the data in one stride of the search through the prefix-type data structure. According to the invention, the trie element may contain 1) a description of the tree structure associated with the trie element, 2) a description of the links to the next level trie element, and 3) a pointer to the storage location of the next level trie element. The prefix structure has a first level trie element, and at least one second level trie element. The trie element includes a first code of the first level trie element describing the prefixes contained in the first level trie element, a second code specifying paths between the first level trie element and all children of the first level trie element (such children are second level trie elements), and a pointer for linking the first level trie element with one of the second level trie elements. Each of the first and second trie elements and the pointer are of a fixed, predefined size.

Claims

1. A computer-readable medium having stored thereon a data structure for identifying prefixes based on a trie representation of said prefixes, the trie representation being grouped in to strides of a number of tree levels greater than one, the data structure comprising:

a first level trie element; and

a second level trie element;

wherein each of the first and second level trie elements includes;

a first code field for storing a first code representing each of a plurality of nodes within a corresponding stride of said each of the first and second level trie elements, the first code identifying each of the plurality of nodes of the corresponding stride as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the corresponding stride, the lowest-level subset including a plurality of said plurality of nodes;

a second code field for storing a second code for identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes; and

a pointer field for storing a single link to a next level trie element;

wherein the next level trie element of the first level trie element is the second level trie element.

2. The data structure of claim 1, wherein said prefixes correspond to information for controlling routing of packet data.

3. The data structure of claim 2, wherein said prefixes are derived to match lookup data derived from packet headers, said packet headers including one or more fields from the set of:

source address, destination address, protocol type, source port, and destination port.

4. The data structure of claim 1, further comprising one or more additional second level trie elements, each containing said first code, said second code and said pointer;

and

wherein the second level trie element and said one or more additional second level trie elements are stored in a single contiguous block of memory in the computer-readable medium.

5. The data structure of claim 1, further comprising a result array corresponding to the first level trie element;

wherein the result array is stored separately, but contiguous with the second level trie element.

6. The data structure of claim 5, wherein the first code of the first level trie element includes a tree bitmap, and said result array is indirectly accessed based on the tree bitmap.

7. The data structure of claim 5, wherein the result array and the second level trie element are each accessed by the single link stored in the pointer field in the first level trie element.

8. The data structure of claim 1, wherein different random access memory types of the computer-readable medium are disposed for storing different trie level elements.

9. The data structure of claim 1, wherein each of the first and second level trie elements is split into two parts, a first part containing the first code and a second part containing the second code, and further including a second pointer for linking the second code with the first code.

10. The data structure of claim 1, wherein selected ones or all of the first and second level trie elements are segmented.

17. The data structure of claim 1, wherein the first code field is of a first fixed and predetermined size;

the second code field is of a second fixed and predetermined size; and

the pointer field is of a third fixed and predetermined size.

18. The data structure of claim 1, wherein the first code includes a tree bitmap including a node identifying bit for each of the plurality of nodes.

19. The data structure of claim 1, wherein said trie representation is a binary trie representation.

20. The data structure of claim 19, wherein the second code includes a child bitmap of n bits, m is the number of nodes in the lowest-level subset of the plurality of nodes, and n equals two raised to the power of m.

21. The data structure of claim 1, wherein further comprising a result array corresponding to the first level trie element;

wherein the result array includes an entry for only said identified prefix nodes of the plurality of nodes of the first level trie element.

22. The data structure of claim 21, wherein the first code includes a tree bitmap including an identifying bit for each node of the plurality of nodes, and a position of within the tree bitmap of an identified prefix node indicates a position within the result array for the identified prefix node.

23. The data structure of claim 22, wherein the second code includes a child bitmap including a trie path identifying bit for each possible trie path that could extend from one of the plurality of nodes to a child node in a next-level stride.

24. The data structure of claim 21, wherein the entry includes an indication of one or more actions to be taken.

25. The data structure of claim 24, wherein said one or more actions to be taken include forwarding to an indicated next hop address or a modification of a header of a packet.

26. The data structure of claim 1, wherein the second code includes a child bitmap including a trie path identifying bit for each possible trie path that could extend from one of the plurality of nodes to a child node in a next-level stride.

11. A method for searching through a prefix-type data structure stored in trie elements having predefined strides of size greater than one, a stride being a number of levels in a tree grouped together, the prefix structure having a first level trie element and a plurality of second level trie elements, each trie element being a description of data in one of the strides, the method comprising:

a) providing a first code of the first level trie element, the first code representing each of a plurality of nodes within a corresponding stride of the first level trie element, the first code identifying each of the plurality of nodes of the corresponding stride as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the corresponding stride, the lowest-level subset including a plurality of said plurality of nodes;

b) providing a second code identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes; and

c) providing a single pointer linking the first level trie element with the plurality of second level trie elements,

the method further comprising;

d) examining the first code and the second code to extract parameters indicative of termination at a leaf or indicative of a second level trie element;

e) if termination is indicated, fetching a result value;

f) if a second level trie element is indicated, proceeding according to the corresponding pointer and parameters to an indicated child element; and

g) repeating steps a) though f) at a next lower level until termination.

12. The method of claim 11, wherein prefixes identified by said trie elements comprise packet header information.

13. In a networking environment wherein packets comprise multiple fields in each header containing information pertinent to classifying and handling packet traffic, a method for use in networking equipment including routers for implementing packet classification filters, the method including the steps of:

classifying each packet of said packet traffic according to predefined filters as one or more of an exact match, a prefix match and a range match by examination of said multiple fields of said header; and

processing packet traffic that is neither exact match or prefix match by content addressable memory (CAM) techniques, said CAM techniques being executable concurrently with a prefix search.

14. The method of claim 13, wherein said prefix search comprises a tree-bitmap prefix search.

15. The method of claim 14, wherein said tree bitmap search comprises searching through a prefix-type data structure stored in trie elements having predefined strides, a stride being a number of levels in a tree accessed in a single read operation, the prefix structure having a first level trie element and at least one second level trie element, each trie element being a description of data in one of the strides, the method comprising:

a) providing a first code of said first level trie element describing.the prefixes contained therein;

b) providing a second code specifying paths between said first level trie element and said second level trie elements, if any; and

c) providing a pointer for linking said first level trie element with a selected one of said second level trie elements,

the method further comprising;

d) examining said first code and said second code to extract parameters indicative of termination at a leaf or indicative of a second level trie element;

e) if termination is indicated, fetching a result value;

f) if a second level trie element is indicated, proceeding according to the corresponding pointer and parameters to an indicated child element; and

g) repeating steps a) though f) at a next lower level until termination.

16. The method of claim 14, wherein said tree bitmap prefix search comprises applying filters based on information in a destination address field, a source address field, a protocol field, a destination port field and a source port field to create a trie containing a compact representation of selected ones of the filters in exact match form and in prefix match form.

27. A computer-readable medium having stored thereon a data structure for identifying prefixes based on a trie representation of said prefixes, the trie representation being grouped in to strides of a number of tree levels greater than one, the data structure comprising:

a first trie element,

a tree bitmap element;

a result array element; and

a child array element;

wherein the tree bitmap element includes;

a first code field for storing a tree bitmap representing each of a plurality of nodes within the stride corresponding to the first trie element, and the tree bitmap identifying each of the plurality of nodes as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the stride corresponding to the first trie element, the lowest-level subset including a plurality of said plurality of nodes; and

a result array pointer field for storing a result array element link to the result array element;

wherein the first trie element includes;

a second field for storing a child bitmap for identifying which extending trie paths exist between the lowest-level subset of the plurality of nodes and one or more strides identified in the child array element and which extending trie paths do not emanate from the lowest-level subset of the plurality of nodes;

a tree bitmap pointer field for storing a tree bitmap element link to the tree bitmap element; and

a child array pointer field for storing a child array link to the child array element;

wherein the result array element is configured for storing prefix matching results corresponding to prefix nodes identified in the tree bitmap; and

wherein the child array element is configured for storing children elements of the lowest-level subset of the plurality of nodes having an extending trie path identified in the child bitmap.

28. computer-readable medium having stored thereon a data structure for identifying prefixes based on a trie representation of said prefixes, the trie representation being grouped in to strides of a number of tree levels greater than one, the data structure comprising:

a first trie element;

a tree bitmap element;

a result array element; and

a child array element;

wherein the tree bitmap element includes a tree bitmap field for storing a tree bitmap representing each of a plurality of nodes within the stride corresponding to the first trie element, and the tree bitmap identifying each of the plurality of nodes as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the stride corresponding to the first trie element, the lowest-level subset including a plurality of said plurality of nodes;

wherein the first trie element includes;

a second field for storing a child bitmap for identifying which extending trie paths exist between the lowest-level subset of the plurality of nodes and one or more strides identified in the child array element and which extending trie paths do not emanate from the lowest-level subset of the plurality of nodes;

a result array pointer field for storing a result array link to the result array element;

a tree bitmap pointer field for storing a tree bitmap link to the tree bitmap; and

a child array pointer field for storing a child array element link to the child array element;

wherein the result array element is configured for storing prefix matching results corresponding to prefix nodes identified in the tree bitmap element; and

wherein the child array element is configured for storing children elements of the lowest-level subset of the plurality of nodes having an extending trie path identified in the child bitmap.

29. 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 a child bitmap, said method comprising:

(a) retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;

the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;

the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;

(b) evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;

(c) evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication;

(d) in response to said determination of the child stride, repeating steps (a), (b), and (c) with the current-level stride corresponding to the child stride with the current-level data structure for this next iteration identified based on the single link in the current iteration; and

(e) in response to said determination of the no child indication, retrieving a result based on the indication of the longest matching prefix node.

30. The method of claim 29, wherein the result is retrieved from a result array.

31. The method of claim 30, wherein the indication of the longest matching prefix node includes an address or pointer to the result.

32. A computer-readable medium containing computer-executable instructions for performing steps manipulating 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 a child bitmap, said steps comprising:

(a) retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;

the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;

the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;

(b) evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;

(c) evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication;

(d) in response to said determination of the child stride, repeating steps (a), (b), and (c) with the current-level stride corresponding to the child stride with the current-level data structure for this next iteration identified based on the single link in the current iteration; and

(e) in response to said determination of the no child indication, retrieving a result based on the indication of the longest matching prefix node.

33. The computer-readable medium of claim 32, wherein the result is retrieved from a result array.

34. The computer-readable medium of claim 33, wherein the indication of the longest matching prefix node includes an address or pointer to the result.

35. An apparatus for manipulating 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 a child bitmap, said apparatus comprising:

means for retrieving a current-level data structure element corresponding to a current-level stride, the current-level data structure element including a current-level tree bitmap, a current-level child bitmap, and a single link to a next-level data structure element;

the current-level tree bitmap corresponding to a current level stride in the tree data structure, the current-level tree bitmap including a plurality of tree bitmap bits, each of the plurality of tree bitmap bits corresponding to a particular one of a plurality of nodes, the value of a bit of the plurality of tree bitmap bits indicating a corresponding node as a prefix node or a vacant node, the plurality of nodes representing multiple tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of said tree levels in the current level stride, the lowest-level subset including a plurality of said plurality of nodes;

the current-level child bitmap corresponding to the current level stride, the current-level tree child including a plurality of child bitmap bits, each of the plurality of child bitmap bits corresponding to a particular child path of one of the lowest-level subset of the plurality of nodes, the value of a bit of the plurality of child bits indicating a presence or absence of the corresponding child path;

means for evaluating the current-level tree bitmap against a current-level portion of a search string to determine a longest matching prefix node or a no longest prefix match, and updating an indication of the longest matching prefix node in response to said determination of the longest matching prefix node;

means for evaluating the current-level child bitmap against the current-level portion of the search string to determine a child stride for a next-level or a no child indication; and

means for retrieving a result based on the indication of the longest matching prefix node in response to said determination of the no child indication.

36. The apparatus of claim 35, wherein the result is encoded in a result array;

and said means for retrieving a result includes means for parsing the result array.