Efficient ipv4/ipv6 best matching prefix method and apparatus

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFUS-PAI-O-4012247

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.