Load balancing in IP address lookup

• US 6,917,954 B2
• Filed: 04/24/2002
• Issued: 07/12/2005
• Est. Priority Date: 05/30/2001
• Status: Active Grant

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Mosaid Technologies Incorporated (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Inventors: Ahmad, Imtiaz, Brown, David A.
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): HWANG, JOON H
• Application Number:
  US10/132,675
• Publication Number:
  US 20020184221A1
• Time in Patent Office: 1,175 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 709238-244, 711117-146, 711170-173, 717162-167, 717/104
• US Class Current: 1/1
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A load balancing mechanism maps a binary tree representation of a routing table into a set of fixed size memories. The mechanism efficiently utilizes the memory in the routing table without violating the tree precedence constraints and the memory access requirements of a pipelined system. The mechanism stores a subtree associated with a densely populated level of the binary tree in memory associated with lower levels.

Claims

1. A multi-level lookup table comprising:

a plurality of memories, a binary tree representation of a routing table mapped into the memories, with each memory associated with one level of the binary tree; and

logic which allows storage of a subtree that includes final routes and is associated with a densely populated level of the binary tree in a memory associated with a level lower than the densely populated level of the binary tree to increase the number of locations for storing routes for the densely populated level.

2. The multi-level lookup table as claimed in claim 1 further comprising:

a skip indicator stored with a subtree index to the subtree in memory associated with a higher level of the binary tree, the skip indicator indicating to the logic whether the subtree is stored in the memory associated with the densely populated level.

3. The multi-level lookup table as claimed in claim 2 wherein the skip indicator is a single bit stored in a mapper entry.

4. The multi-level lookup table as claimed in claim 2 wherein the skip indicator is a plurality of bits stored in a mapper entry.

5. The multi-level lookup table as claimed in claim 1 wherein the subtree associated with a densely populated level of the binary tree is stored in the memory associated with the lower level in the binary tree, upon detecting the number of routes stored in the memory associated with the densely populated tree is greater than a predetermined threshold.

6. The multi-level lookup table as claimed in claim 1 wherein the subtree associated with a densely populated level of the binary tree stored in a lower level memory associated with the lower level of the binary tree is moved to the memory associated with the densely populated level, upon inserting a subtree index to the subtree.

7. A method for increasing a number of routes stored in a multi-level lookup table comprising the steps of:

mapping a binary tree representation of a routing table into a plurality of memories, each memory associated with one level of the binary tree; and

storing a subtree that includes final routes and is associated with a densely populated level of the binary tree in a memory associated with the level of the binary tree lower than the densely populated level to increase the number of locations for storing routes for the densely populated level.

8. The method as claimed in claim 7 further comprising the step of:

storing a skip indicator with a subtree index to the subtree, the skip indicator indicating whether the subtree is stored in the memory associated with the densely populated level.

9. The method as claimed in claim 8 further comprising the step of:

skipping a search of the densely populated level dependent on the skip indicator.

10. The method as claimed in claim 9 further comprising the step of:

after skipping the search of the densely populated level, continuing the search in the memory associated with the level of the binary tree lower than the densely populated level.

11. The method as claimed in claim 8 wherein the skip indicator is a single bit stored in a mapper entry.

12. The method as claimed in claim 8 wherein the skip indicator is a plurality of bits stored in a mapper entry.

13. The method as claimed in claim 7 further comprising the step of:

moving the subtree associated with a densely populated level of the binary tree to a lower level memory associated with the lower level in the binary tree, upon detecting the number of routes stored in the memory associated with the densely populated tree is greater than a predetermined threshold.

14. The method as claimed in claim 7 further comprising the steps of:

moving the subtree associated with a densely populated level of the binary tree stored in a lower level memory associated with the lower level in the binary tree to the memory associated with the densely populated level, upon inserting a subtree index to the subtree.

15. A multi-level lookup table comprising:

a plurality of memories, a binary tree representation of a routing table mapped into the memories, with each memory associated with one level of the binary tree; and

logic means for storing a subtree that includes final routes and is associated with a densely populated level of the binary tree in a lower level memory associated with the lower level of the binary tree to increase the number of locations for storing routes for the densely populated level.

16. The multi-level lookup table as claimed in claim 15 further comprising:

a skip indicator stored with a subtree index to the subtree, the skip indicator indicating whether the subtree is stored in the memory associated with the densely populated level.

17. The multi-level lookup table as claimed in claim 16 wherein the skip indicator is a single bit stored in a mapper entry.

18. The multi-level lookup table as claimed in claim 16 wherein the skip indicator is a plurality of bits stored in a mapper entry.

19. The multi-level lookup table as claimed in claim 15 wherein the subtree associated with a densely populated level of the binary tree is moved to a lower level memory associated with the lower level in the binary tree, upon detecting the number of routes stored in the memory associated with the densely populated tree is greater than a predetermined threshold.

20. The multi-level lookup table as claimed in claim 15 wherein the subtree associated with a densely populated level of the binary tree stored in a lower level memory associated with the lower level in the binary tree is moved to the memory associated with the densely populated level, upon inserting a subtree index to the subtree.