Route lookup engine

• US 6,711,153 B1
• Filed: 12/13/1999
• Issued: 03/23/2004
• Est. Priority Date: 12/13/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: Cherian, Sanjay G., Hebb, Andrew T.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/459,441
• Time in Patent Office: 1,562 Days
• Field of Search: 370/351, 370/389, 370/413, 370/395.31, 370/395.32
• US Class Current: 370/351
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04Q 2213/13097 Numbering, addressing
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13204 Protocols
• CPC Class Codes: H04Q 2213/13216 Code signals, frame structure
• CPC Class Codes: H04Q 2213/1329 Asynchronous transfer mode, ATM
• CPC Class Codes: H04Q 2213/13299 Bus
• CPC Class Codes: H04Q 2213/1332 Logic circuits
• CPC Class Codes: H04Q 2213/13367 Hierarchical multiplexing, add-drop multiplexing
• CPC Class Codes: H04Q 2213/13384 Inter-PBX traffic, PBX networks, e.g. corporate networks
• CPC Class Codes: H04Q 2213/13389 LAN, internet
• CPC Class Codes: H04Q 2213/13399 Virtual channel/circuits
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

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.

Claims

1. A route lookup engine comprising:

an IP lookup table memory including at least one trie for at least one network;

a lookup controller in communication with said IP lookup table memory and capable of searching said IP lookup table memory to obtain a next hop index; and

a forwarding processor interface in electrical communication with said lookup controller, said forwarding processor interface providing a search key to said lookup controller for said lookup controller to begin searching said IP lookup table, said forwarding processor interface receiving said next hop index from said lookup controller.

2. The route lookup engine of claim 1 wherein the at least one network is a virtual private network.

3. The route lookup engine of claim 1 further comprising a processor interface in communication with said lookup controller and performing table updates to said IP lookup table memory.

4. The route lookup engine of claim 1 further comprising a lookup key memory disposed between said forwarding processor interface and said lookup controller.

5. The route lookup engine of claim 4 wherein the lookup key memory is a FIFO memory.

6. The route lookup engine of claim 1 further comprising a next hop result memory disposed between said lookup controller and said forwarding processor interface.

7. The route lookup engine of claim 6 wherein the next hop result memory is a FIFO memory.

8. The route lookup engine of claim 1 further comprising a control/status register in communication with said processor interface, said forwarding processor interface and said lookup controller.

9. The route lookup engine of claim 1 wherein said lookup controller performs a unicast lookup.

10. The route lookup engine of claim 1 wherein said lookup controller performs a multicast lookup.

11. The route lookup engine of claim 1 wherein said search key comprises an IP address.

12. The route lookup engine of claim 1 wherein said lookup memory comprises a Dram.

13. The route lookup engine of claim 1 wherein said at least one trie comprises a variable stride trie.

14. The route lookup engine of claim 1 wherein said lookup controller performs prefix expansion and capture when searching said IP lookup table memory.

15. A method for operating a route lookup engine comprising steps of:

receiving a route lookup request;

performing a route lookup comprising the steps of;

determining if the lookup is the first one for said request;

using current block data for said request when the lookup is the first lookup for said request, using prior block data when the lookup is not the first lookup for said request;

determining if said block data indicates a leaf, and when said block data does not indicate a leaf performing the steps of;

providing a route table lookup address comprising a route lookup engine root from said block data plus an address comprising a zero bit concatenated with a destination address concatenated with a source address minus the current order data from said block data;

performing a read from said lookup table, said read providing new block data;

setting the current order data to the present current order data plus the order data from the new block data;

returning to said step of determining if the lookup is the first one for said request;

performing the following steps when said block data does indicate a leaf;

determining if the indirect bit is set in said block data and when said indirect bit is set performing the steps of;

providing a route table lookup address comprising a route table lookup engine route from said block data;

performing a read from said lookup table, said read providing new block data;

storing results if said indirect bit does not equal a one and the type bit does not equal node; and

performing the step of storing results when said indirect bit is not set.

16. The method of claim 15 wherein the step of setting the current order data further comprises the step of indicating an error condition when said current order data is less than or equal to sixty-four.

17. The method of claim 15 wherein the step of setting the current order data further comprises the step of setting a multicast bit when said current order is greater than thirty-two.

18. The method of claim 15 wherein the step of storing results if said indirect bit does not equal a one and the type bit does not equal node further comprises the step of indicating an error condition if said indirect bit equals a one or said type bit equals a node.

19. The method of claim 15 wherein said step of performing a route lookup comprises performing a unicast lookup.

20. The method of claim 15 wherein said step of performing a route lookup comprises performing a multicast lookup.

21. A method for operating a route lookup engine comprising the steps of:

receiving a route lookup request;

performing a route lookup comprising the steps of;

determining if the lookup is the first one for said request;

using current block data for said request when the lookup is the first lookup for said request, using prior block data when the lookup is not the first lookup for said request;

determining if said block data indicates a leaf, and when said block data does indicate a leaf performing the steps of;

determining if an indirect bit is set in said block data and when said indirect bit is set performing the steps of;

providing a route table lookup address comprising a route table lookup engine route from said block data;

performing a read from said lookup table, said read providing new block data;

storing results if said indirect bit does not equal a one and the type bit does not equal node; and

performing the step of storing results when said indirect bit is not set.