Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-09-18
1999-11-30
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707 3, 707100, 39520075, 39520048, 395892, G06F 1730
Patent
active
059959711
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.
REFERENCES:
patent: 5500609 (1996-03-01), Kean
patent: 5519858 (1996-05-01), Walton et al.
patent: 5524254 (1996-06-01), Morgan et al.
patent: 5768632 (1998-06-01), Husted et al.
Aho et al., "Chapter 3--Trees", Data Structures and Algorithms, (.COPYRGT. 1983, Addison-Wesley Publishing Company, Inc.), pp. 75-106.
Bailey et al., "Pathfinder: A Pattern-Based Packet Classifier", Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI) USENIX Association, Nov. 14-17, 1994, pp. 115-123.
Bell et al., "Longest-match String Searching for Ziv-Lempel Compression", Software-Practice and Experience, vol. 23, No. 7, Jul. 1993, pp. 757-771.
Devroye, "A Note on the Probabilistic Analysis of Patricia Trees", Random Structures and Algorithms, vol. 3, No. 2, 1992, pp. 203-214.
Doeringer et al., "Routing on Longest-Matching Prefixes", IEEE/ACM Transactions on Networking, vol. 4, No. 1, Feb. 1996, pp. 86-97.
Knuth, The Art of Computer Programming, vol. 3-Sorting and Searching, (.COPYRGT.1973, Addison-Wesley Publishing Company, Inc.), pp. 490-499.
McCanne et al., "The BSD Packet Filter: A New Architecture for User-level Packet Capture", Proceedings of the 1993 Winter USENIX Conference, San Diego, California, Jan. 25-29, 1993, pp. 259-269.
Merrett et al., "Dynamic Patricia", Proceedings of the International Conference on Foundations of Data Organization, 1985, pp. 19-29.
Mogul et al., "The Packet Filter: An Efficient Mechanism for User-level Network Code", Operating Systems Review, vol. 21, No. 5, 1987, pp. 39-51.
Morrison, "Patricia-Practical Algorithm to Retrieve Information Coded in Alphanumeric", Journal of the Association for Computing Machinery, vol. 15, No. 4, Oct. 1968, pp. 514-534.
Wu et al., "Fast Text Searching Allowing Errors", Communications of the ACM, vol. 35, No. 10, Oct. 1992, pp. 83-91.
Wu et al., "AGREP-A Fast Approximate Pattern-Matching Tool", Proceedings of the Winter 1992 USENIX Conference, San Francisco, California, Jan. 20-24, 1992, pp. 153-162.
Yuhara et al., "Efficient Packet Demultiplexing for Multiple Endpoints and Large Messages", USENIX-1994 Winter, San Francisco, California, Jan. 17-21, 1994, pp. 153-165.
Zobel et al., "Finding Approximate Matches in Large Lexicons", Software-Practice and Experience, vol. 25, No. 3, Mar. 1995, pp. 331-345.
U.S. application No. 08/933,476, Douceur et al., filed Sep. 18, 1997.
Bar Ofer
Bernet Yoram
Douceur John R.
Black Thomas G.
Micdrosoft Corporation
Michaelson Peter L.
Mizrahi Diane D.
LandOfFree
Apparatus and accompanying methods, using a trie-indexed hierarc does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and accompanying methods, using a trie-indexed hierarc, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and accompanying methods, using a trie-indexed hierarc will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1687317