Multiple parallel packet routing lookup

Details Multiple parallel packet routing lookup Multiple parallel packet routing lookup

2006-01-24

2006-01-24

Kizou, Hassan (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320

Reexamination Certificate

active

06990099

ABSTRACT:
The invention provides a method and system for routing information lookup for packets using a routing protocol such as IP. Routing information which has been determined responsive to the packet header, which includes a destination address, a source address, and an input interface for the packet. Routing lookup is performed in response to at least one set of selected routing information, using a lookup table which includes tags both for the routing information and for a bitmask length (thus indicating the generality or scope of the routing information for the routing lookup). The lookup table is structured so that addresses having the most common bitmask length are addressed first, but that more specific addresses are still considered when they are present. It has been discovered that most internet addresses can be found by reference to 24-bit or 21-bit IP addresses, after which 16-bit, 12-bit, and finally 32-bit IP addresses are considered. Lookup flags indicate when a relatively uncommon but more specific 32-bit IP address match is available. A memory controller pipelines the lookup requests to a hash table memory, flushes superfluous requests when a lookup result is found, and handles cases relating to 32-bit IP address matches.

REFERENCES:
patent: 3389377 (1968-06-01), Cole
patent: 3402398 (1968-09-01), Koemer et al.
patent: 3483528 (1969-12-01), Koemer et al.
patent: 3518631 (1970-06-01), Lindquist et al.
patent: 3602899 (1971-08-01), Lindquist et al.
patent: 3868642 (1975-02-01), Sachs
patent: 4456957 (1984-06-01), Schieltz
patent: 5249292 (1993-09-01), Chiappa
patent: 5253251 (1993-10-01), Aramaki
patent: 5274631 (1993-12-01), Bhardwaj
patent: 5280500 (1994-01-01), Mazzola et al.
patent: 5291482 (1994-03-01), McHarg et al.
patent: 5305311 (1994-04-01), Lyles
patent: 5307343 (1994-04-01), Bostica et al.
patent: 5319644 (1994-06-01), Liang
patent: 5331637 (1994-07-01), Francis et al.
patent: 5345445 (1994-09-01), Hiller et al.
patent: 5345446 (1994-09-01), Hiller et al.
patent: 5353283 (1994-10-01), Tsuchiya
patent: 5361256 (1994-11-01), Doeringer et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5396491 (1995-03-01), Newman
patent: 5408469 (1995-04-01), Opher et al.
patent: 5430715 (1995-07-01), Corbalis et al.
patent: 5477541 (1995-12-01), White et al.
patent: 5485455 (1996-01-01), Dobbins et al.
patent: 5491687 (1996-02-01), Christensen et al.
patent: 5555244 (1996-09-01), Gupta et al.
patent: 5583862 (1996-12-01), Callon
patent: 5600798 (1997-02-01), Cherukuri et al.
patent: 5724351 (1998-03-01), Chao et al.
patent: 5751971 (1998-05-01), Dobbins et al.
patent: 5754547 (1998-05-01), Nakazawa
patent: 5781772 (1998-07-01), Wilkinson, III et al.
patent: 5898686 (1999-04-01), Virgile
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5914953 (1999-06-01), Krause et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061712 (2000-05-01), Tzeng
patent: 6078590 (2000-06-01), Farinacci et al.
patent: 6122279 (2000-09-01), Milway et al.
patent: 6212183 (2001-04-01), Wilford
patent: 6434144 (2002-08-01), Romanov
patent: 6512766 (2003-01-01), Wilford
patent: 6895442 (2005-05-01), Khanna
patent: 2001/0012295 (2001-08-01), Wilford
patent: 2002/0184221 (2002-12-01), Ahmad et al.
patent: 2004/0062208 (2004-04-01), Brown et al.
patent: 2004/0236720 (2004-11-01), Basso et al.
patent: 2005/0100012 (2005-05-01), Kaxiras et al.
Girish P. Chandranmenon and George Varghese, Member IEEE. “Trading Packet Headers for Packet Processing”, 1996 IEEE/ACM Transactions on Networking, vol 4, No. 2, Apr. 1996.
Willibald Doeringer, Member, IEEE, Gunter Karjoth, and Mehdi Nassehi, Member IEEE. IEEE/ACM “Routing on Longest-Matching Prefixes”, Transactions on Networking, vol. 4, No. 1, Feb. 1996.
Tong-Bi Pei and Charles Zukowski, “Putting Routing Tables in Silicone”, IEEE Network Magazine, Jan. 1992.
“Pluris Massively Parallel Routing”. (White Paper).
Paul F. Tsuchiya, “A Search Algorithm for Table Entries with Non-contiguous Wildcarding”. Bellcore.

Affiliated with

Also associated with

Rating

Multiple parallel packet routing lookup does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiple parallel packet routing lookup, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple parallel packet routing lookup will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3580710