Longest prefix match for IP routers

Details Longest prefix match for IP routers Longest prefix match for IP routers

2006-09-19

2006-09-19

Lim, Krisna (Department: 2153)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

C370S395320

Reexamination Certificate

active

07111071

ABSTRACT:
A method of searching a database for a prefix representing a destination address including loading two trees of tables, each tree of tables having a large table at a root branching to small tables and traversing the two tables of trees in parallel to find a match of an entry to the prefix. An entry includes a router pointer representing the destination address and a pointer to a next small table. The small tables include prefix match fields for indexed table entries, a population count of pointers and hidden prefix entries that hold shorter prefix route entry pointers.

REFERENCES:
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5917821 (1999-06-01), Gobuyan et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 5983223 (1999-11-01), Perlman
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061712 (2000-05-01), Tzeng
patent: 6067574 (2000-05-01), Tzeng
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6212184 (2001-04-01), Venkatachary et al.
patent: 6307855 (2001-10-01), Hariguchi
patent: 6308219 (2001-10-01), Hughes
patent: 6493347 (2002-12-01), Sindhu et al.
patent: 6516319 (2003-02-01), Benayoun et al.
patent: 6526055 (2003-02-01), Perlman
patent: 6539369 (2003-03-01), Brown
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6563823 (2003-05-01), Przygienda et al.
patent: 6567404 (2003-05-01), Wilford
patent: 6658482 (2003-12-01), Chen et al.
patent: 6691218 (2004-02-01), Brown
patent: 6778532 (2004-08-01), Akahane et al.
Knox et al., “Parallel searching techniques for routing table lookup,” Apr. 1, 1993, INFOCOM '93 Proceedings, Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking: Foundation for the Future, vol. 3, pp. 1400-1405.
Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” html version of http://subjects.ee.unsw.edu.au/tele4352/packet—classification.doc, pp. 1-17.
Hayashi et al., “High-Speed Table Lookup engine for IPv6 Longest Prefix Match,” 1999, Global Telecommunications Converence, 1999, vol. 2, pp. 1576-1581.
Kobayashi et al., “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing,” Jun. 2000 IEEE International Conference on Communications, vol. 3, pp. 233-239.
Degermark et al., “Small Forwarding Tables for Fast Routing Lookups,” 1997 ACM 0-89791-905-X/97/0009, pp. 3-14.

Affiliated with

Also associated with

Rating

Longest prefix match for IP routers does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Longest prefix match for IP routers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest prefix match for IP routers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3572721