Technique for efficiently classifying packets using a trie-indexed hierarchy forest that accommodates wildcards
First Claim
1. A method for use in a packet classifier, the classifier having a data structure with hierarchically-related pattern values stored therein, said pattern values having wildcards therein;
- wherein the data structure has a search trie and a hierarchy forest, the search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, the hierarchy forest having a plurality of pattern nodes, each having a different corresponding one of the pattern values associated therewith, and at least one hierarchy of pattern nodes with associated pattern values of increasing generality;
the method comprising the steps of;
forming a key in response to information contained in a portion of the packet;
traversing along a path through the search trie in order to reach one of the pattern nodes in said hierarchy forest, the path being defined by the key and pivot bit values associated with ones of said branch nodes;
determining whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in a different one of pattern nodes situated at an increasingly higher level of a hierarchy containing said one pattern node, so as to locate a desired one of the pattern values, stored in the hierarchy, that either identically matches or most specifically subsumes the key; and
if the key identically matches or is subsumed by the desired one pattern value;
accessing a stored classification associated with said desired one pattern value; and
returning the stored classification for the packet.
2 Assignments
0 Petitions
Accused Products
Abstract
A technique, specifically apparatus and accompanying methods, which utilizes a trie-indexed hierarchy forest ("rhizome") that accommodates wildcards for retrieving, given a specific input key, a pattern stored in the forest that is identical to or subsumes the key. The rhizome contains a binary search trie and a hierarchy forest. The search trie provides an indexed path to each unique, most specific, pattern stored in a lowest level of the hierarchy forest and also possibly to increasingly general patterns at higher levels in the pattern hierarchy. The hierarchy forest organizes the patterns into nodal hierarchies of strictly increasing generality. For use as a packet classifier, the rhizome stores wildcard-based packet classification patterns at separate corresponding pattern nodes, along with, corresponding "reference" fields associated therewith. Operationally, as each different queue is established or removed, a corresponding classification pattern is either inserted into or removed from the rhizome. A search key is formed for each packet, typically by concatenating classification fields, e.g. source and destination addresses and source and destination port designations, appearing in a header of the packet. The search key is then applied to the rhizome to determine whether that key exists therein, by virtue of either matching an identical classification pattern or being completely subsumed within a more general pattern stored therein. When such a classification is found, the classifier returns the contents of the associated reference field, which for scheduling, is a designation of a transmission queue to which the packet is to be directed.
-
Citations
53 Claims
-
1. A method for use in a packet classifier, the classifier having a data structure with hierarchically-related pattern values stored therein, said pattern values having wildcards therein;
- wherein the data structure has a search trie and a hierarchy forest, the search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, the hierarchy forest having a plurality of pattern nodes, each having a different corresponding one of the pattern values associated therewith, and at least one hierarchy of pattern nodes with associated pattern values of increasing generality;
the method comprising the steps of;forming a key in response to information contained in a portion of the packet; traversing along a path through the search trie in order to reach one of the pattern nodes in said hierarchy forest, the path being defined by the key and pivot bit values associated with ones of said branch nodes; determining whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in a different one of pattern nodes situated at an increasingly higher level of a hierarchy containing said one pattern node, so as to locate a desired one of the pattern values, stored in the hierarchy, that either identically matches or most specifically subsumes the key; and if the key identically matches or is subsumed by the desired one pattern value; accessing a stored classification associated with said desired one pattern value; and returning the stored classification for the packet. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
- wherein the data structure has a search trie and a hierarchy forest, the search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, the hierarchy forest having a plurality of pattern nodes, each having a different corresponding one of the pattern values associated therewith, and at least one hierarchy of pattern nodes with associated pattern values of increasing generality;
-
28. Apparatus for a packet classifier comprising:
-
a processor; a memory having executable instructions and a data structure stored therein, the data structure having a search trie and a hierarchy forest, said search trie being formed of a plurality of branch nodes organized into a binary search trie extending from a root node therein to said hierarchy forest, said hierarchy forest having a plurality of pattern nodes, each of said pattern nodes having a different corresponding one of the pattern values associated therewith, organized into at least one hierarchy of pattern nodes of increasing generality wherein at least one of the pattern values in the hierarchy contains a wildcard; wherein the processor, in response to the stored instructions; forms a key in response to information contained in a portion of the packet traverses along a path through the search trie in order to reach one of the pattern nodes in said hierarchy forest, the path being defined by the key and pivot bit values associated with ones of said branch nodes; determines whether the key either matches or is subsumed by a pattern value stored in said one pattern node or in a different one of pattern nodes situated at an increasingly higher level of a hierarchy containing said one pattern node, so as to locate a desired one of the pattern values, stored in the hierarchy, that either identically matches or most specifically subsumes the key; and if the key identically matches or is subsumed by the desired one pattern value; accesses a stored classification associated with said desired one pattern value; and returns the stored classification for the packet. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53)
-
Specification