Method and apparatus for logically expanding the length of a search key

• US 7,966,421 B2
• Filed: 06/21/2001
• Issued: 06/21/2011
• Est. Priority Date: 06/21/2000
• Status: Expired due to Fees

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Inventors: Brown, David A.
• Primary Examiner(s): Shingles; Kristie D
• Application Number:
  US09/886,659
• Publication Number:
  US 20110082866A1
• Time in Patent Office: 3,652 Days
• Field of Search: 709/242, 709/245, 707/3, 707/6, 707/206, 707/207, 707/212, 707/216, 707/706, 707/770, 707/773, 711/108, 711/216, 370/254, 370/351, 370/389
• US Class Current: 709/245
• 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/74591 using content-addressable memories [CAM]

Abstract

A lookup table provides a longest prefix match for a search key longer than a lookup table'"'"'s mapper key. The lookup table performs a multi-level search in one or more mappers for the result value based on a portion of the search key provided as the mapper key. The lookup table is searched in multiple passes with successive portions of the search key until the result value is found.

Claims

1. A method comprising:

searching data stored in a computer readable media for a first initial search result using at least a first portion of a first key; and

if the first initial search result is a route index corresponding to the first key, then returning the route index; and

if the first initial search result is a subtree index for an iterative search, then performing an iterative search of the data stored in the computer readable media, the iterative search comprising;

searching the data for an iterative search result using a subsequent key comprising the subtree index found in a preceding search and at least a next portion of the first key; and

if the iterative search result is a route index corresponding to the first key, then returning the route index; and

if the iterative search result is a subtree index for a next search, then performing the iterative search again.

2. The method of claim 1, further comprising:

searching the data for a second initial search result using at least a first portion of a second key, wherein searching the data for the second initial search result is at least partially performed in parallel with searching the data for the iterative search result.

3. The method of claim 2, wherein the first key, the second key, or both the first and second keys comprise at least one of either a 32 bit IPv4 address or a 128 bit IPv6 address.

4. The method of claim 2, wherein the first key, the second key, or both the first and second keys further comprise a prefix corresponding to a Virtual Private Network identifier.

5. The method of claim 1, wherein the data is stored in a lookup table.

6. The method of claim 5, wherein the subtree index comprises a pointer to at least one other entry stored in the lookup table.

7. The method of claim 1, wherein the data is stored in a lookup table comprising a plurality of mappers, the lookup table is configured to return in a single search of the lookup table a route index corresponding to a mapper key, and the iterative search is performed if a length of the first key is greater than a length of the mapper key and the first initial search result is a subtree index for an iterative search.

8. The method of claim 7, wherein the length of the mapper key is 40 bits and the length of the first key is at least 64 bits.

9. The method of claim 1, wherein the data is stored in a lookup table comprising a plurality of mappers including a direct mapper and at least one indirect mapper, searching the data for the first initial search result comprises searching both the direct mapper and said at least one indirect mapper using the first portion of the first key, and performing the iterative search of the data comprises searching again said at least one indirect mapper using the subsequent key without searching again the direct mapper.

10. The method of claim 1, wherein the data is stored in a lookup table comprising a plurality of mappers including a direct mapper and at least one indirect mapper and said at least one indirect mapper is configured to store data corresponding to at least two mapper levels.

11. The method of claim 1, further comprising:

receiving a command indicating that the iterative search should be performed using the subtree index found in the preceding search and the at least next portion of the first key.

12. An apparatus comprising:

a memory storing data;

a forwarding engine configured to search the data for a first initial search result using at least a first portion of a first key, wherein the forwarding engine is configured to return a route index if the first initial search result is a route index corresponding to the first key, and wherein the forwarding engine is configured to perform an iterative search if the first initial search result is a subtree index, wherein the iterative search comprises;

searching the data for an iterative search result based on a subsequent key comprising the subtree index found in a preceding search and at least a next portion of the first key; and

if the iterative search result is a route index corresponding to the first key, then returning the route index; and

if the iterative search result is a subtree index, then performing the iterative search again.

13. The apparatus of claim 12, further comprising:

a controller configured to at least partially search in parallel the data for the iterative search result and a second initial search result using at least a first portion of a second key.

14. The apparatus of claim 13, wherein the first key, the second key, or both the first and second keys comprise at least one of either a 32 bit IPv4 address or a 128 bit IPv6 address.

15. The apparatus of claim 13, wherein the first key, the second key, or both the first and second keys further comprise a prefix corresponding to a Virtual Private Network identifier.

16. The apparatus of claim 13, wherein the data is stored in a lookup table in the memory.

17. The apparatus of claim 16, further comprising a means for storing the data.

18. The apparatus of claim 12, further comprising:

wherein the data is stored in a lookup table in the memory, the lookup table comprises a plurality of mappers including a direct mapper and at least one indirect mapper, said at least one indirect mapper is configured to store data corresponding to at least two mapper levels, and the lookup table includes a pointer selector configured to cause a search of an appropriate mapper level to be performed in said at least one indirect mapper based on a command received from the forwarding engine.

19. The apparatus of claim 12,

wherein the data is stored in a lookup table in the memory, the lookup table comprises a plurality of mappers, the lookup table is configured to return in a single search of the lookup table a route index corresponding to a mapper key, and the iterative search is performed if a length of the first key is greater than a length of the mapper key and the first initial search result is a subtree index for an iterative search.

20. An apparatus comprising:

means for storing data;

means for searching the data for a first initial search result using at least a first portion of a first key, wherein said means is configured to return a route index if the first initial search result is a route index corresponding to the first key, and wherein said means is configured to perform an iterative search if the first initial search result is a subtree index, wherein the iterative search comprises;

searching the data for an iterative search result based on a subsequent key comprising the subtree index found in a preceding search and at least a next portion of the first key; and

if the iterative search result is a route index corresponding to the first key, then returning the route index; and

if the iterative search result is a subtree index, then performing the iterative search again.

21. The apparatus of claim 20, further comprising:

means for at least partially searching in parallel the data for the iterative search result and a second initial search result using at least a first portion of a second key.

22. The apparatus of claim 21, wherein the first key, the second key, or both the first and second keys comprise at least one of either a 32 bit IPv4 address or a 128 bit IPv6 address.

23. The apparatus of claim 21, wherein the first key, the second key, or both the first and second keys further comprise a prefix corresponding to a Virtual Private Network identifier.

24. The method of claim 23 wherein the subtree index comprises a pointer to at least one other entry stored in the lookup table.

25. The apparatus of claim 20, wherein the subtree index comprises a pointer to at least one other entry in the means for storing the data.

26. A method comprising:

searching data stored in a computer readable media for an iterative search result using a subtree index found in a preceding search of the computer readable media and at least a next portion of a first key; and

if the iterative search result is a route index corresponding to the first key, then returning the route index; and

if the iterative search result is a subtree index for a next search, then performing said searching data for an iterative search result again.

27. The method of claim 26, further comprising:

searching the data for a second initial search result using at least a first portion of a second key, wherein searching the data for the second initial search result is at least partially performed in parallel with searching the data for the iterative search result.

28. The method of claim 27, wherein the first key, the second key, or both the first and second keys comprise at least one of either a 32 bit IPv4 address or a 128 bit IPv6 address.

29. The method of claim 27, wherein the first key, the second key, or both the first and second keys further comprise a prefix corresponding to a Virtual Private Network identifier.

30. The method of claim 26, wherein the data is stored in a lookup table.

31. The method of claim 30, wherein the subtree index comprises a pointer to at least one other entry stored in the lookup table.