Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2003-02-14
2008-10-07
Mizrahi, Diane (Department: 2165)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07433871
ABSTRACT:
The present invention provides a data-structure to store a search database and provides techniques to build this datastructure given a list of prefixes (P) and to search this database efficiently for a best matching prefix for an address D. The data-structure can be stored in standard memory (14), where values are stored associated with memory address locations. The data structure includes representations of addressable linked tables (FIG.3b). The representations are related to a binary search trie (FIG.1) and each linked table (T) has at least one entry. Entries in a table span more than one level of the binary search trie. The spanning feature relates to compression of a binary search trie into a finite number of levels (and hence tables). The finite number is less than the number of levels in the binary search trie. Hence the search algorithm is restricted to a finite, and predetermined number of search accesses to the tables to obtain a best-match result.
REFERENCES:
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061679 (2000-05-01), Bournas et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6223172 (2001-04-01), Hunter et al.
patent: 6256055 (2001-07-01), Oyamada
patent: 6526055 (2003-02-01), Chiu et al.
patent: 6581106 (2003-06-01), Dardini et al.
patent: 6947931 (2005-09-01), Bass et al.
patent: 2001/0040895 (2001-11-01), Templin
patent: 2008/0022403 (2008-01-01), Chen et al.
Zoran S. Perisic et al., “Protocols for Quality of Service Menagement on Internet”, Sep. 2001, IEEE publication, pp. 451-454.
Furquan Ansari et al., A Framework for Handling Route Changes and Aggregation in IPSOFACTO, 1998, IEEE pp. 3751-3756.
Stefan Nilsson et al. “Fast address lookup for Internet routers”, (Sep. 24, 1999), Swedish Institute of Computer Science, www.nada.kth.se, pp. 1-12.
Arne Andersson et al., “Dynamic Ordered Sets with Exponential Search Trees”, (Jun. 2007) AT&T Labs, Research, ACM, vol. 54, No. 3, Article 13, pp. 1-40.
De Coster Luc
Deforche Koen
Olbrechts Jan
Gordon & Jacobson, PC
Mizrahi Diane
TranSwitch Corporation
LandOfFree
Efficient ipv4/ipv6 best matching prefix method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient ipv4/ipv6 best matching prefix method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient ipv4/ipv6 best matching prefix method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4012247