Multiplex communications – Pathfinding or routing
Reexamination Certificate
1999-12-13
2004-03-23
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Pathfinding or routing
C370S395310
Reexamination Certificate
active
06711153
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
N/A
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
Network devices such as routers must perform route lookups as part of their processing operations. A route lookup is necessary for every packet received by a router in order to determine where the packet is to be sent next. The received packets include a 32-bit wide destination address. The destination address identifies a unique address to which the packet is to be forwarded. A route lookup utilizes the destination address of the received packet in order to identify the next-hop address and exit port in a routing table. Given that the destination address is 32 bits wide, the number of possible destinations is greater than one billion. An IP address comprises a network number and a host number. The network number is of variable length and identifies a unique network. Concatenated to the network number is a host number. The host number identifies a unique host system within a particular network. A received network number part of the address is matched with multiple entries in a routing table to identify the best match. The best match is the one with the largest matching number of bits in the first part in the address. Known methods used to perform this matching are complicated and can take a long time. It would be desirable to provide a route lookup engine which can perform a route lookup quickly and efficiently.
BRIEF SUMMARY OF THE INVENTION
A Route Lookup Engine (RLE) for determining a next hop index is disclosed. The RLE receives a lookup key and performs a multi-bit trie search with prefix expansion and capture of a variable stride trie. The data that the RLE returns comprises the next hop information and status flags. The RLE uses a compact, field reusable data structure. The RLE performs both unicast and multicast IP address lookups on Virtual Private Networks. The RLE uses separate indexing and forwarding memories. The upper bound of the search time for the RLE is fixed regardless of the route table size.
REFERENCES:
patent: 5412654 (1995-05-01), Perkins
patent: 5509123 (1996-04-01), Dobbins et al.
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5842224 (1998-11-01), Fenner
patent: 5870739 (1999-02-01), Davis, III et al.
patent: 5905725 (1999-05-01), Sindhu et al.
patent: 5946679 (1999-08-01), Ahuja et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6052683 (2000-04-01), Irwin
patent: 6061712 (2000-05-01), Tzeng
patent: 6192051 (2001-02-01), Lipman et al.
patent: 6266706 (2001-07-01), Brodnik et al.
patent: 6463067 (2002-10-01), Hebb et al.
Small Forwarding Tables for Fast Routing Lookups; Mikael Degermark, Andrej Brodnik, Svante Carlsson, and Stephen Pink, Department of Computer Science and Electrical Engineering, Lulea University of Technology, Sweden (1997).
Scalable High Speed IP Routing Lookups; Jon Turner, George Varghese, Marcel Waldvogel, Aug. 21, 1997.
Classless Inter-Domain Routing (CIDR): and Address Assignment and Aggregation Strategy, Sep. 1993.
Faster IP Lookups Using Controlled Prefix Expansion; V. Srinivasan, George Varghese, Department of Computer Science, Washington University, Nov. 7, 1997.
Cherian Sanjay G.
Hebb Andrew T.
LandOfFree
Route lookup engine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Route lookup engine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Route lookup engine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3252446