| 摘要 |
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.
|
