METHOD AND APPARATUS FOR LOGICALLY EXPANDING THE LENGTH OF A SEARCH KEY

• US 20110082866A1
• Filed: 06/21/2001
• Published: 04/07/2011
• Est. Priority Date: 06/21/2000
• Status: Active Grant

• Current Assignee: Chartoleaux KG LLC (Intellectual Ventures LLC)
• Original Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Inventors: Brown, David A.
• Granted Patent: US 7,966,421 B2
• Time in Patent Office: Days
• US Class Current: 707/744
• 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-25. -25. (canceled)

26. 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.

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 the step of 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.

50. The method of claim 26, 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.

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

52. The method of claim 26, 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.

53. The method of claim 26, 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.

54. The method of claim 26, 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.

32. An apparatus comprising:

a forwarding engine configured to search 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.

33. The apparatus of claim 32, 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.

34. The apparatus of claim 33, 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.

35. The apparatus of claim 33, 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.

36. The apparatus of claim 33, wherein the data is stored in a lookup table.

37. The apparatus of claim 36, wherein the subtree index comprises a pointer to at least one other entry stored in the lookup table.

55. The apparatus of claim 32, further comprising:

a lookup table in communication with the forwarding engine, wherein the data is stored in a lookup table, 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.

56. The apparatus of claim 32, further comprising:

a lookup table in communication with the forwarding engine, wherein the data is stored in a lookup table, 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.

38. An apparatus comprising:

means for searching 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.

39. The apparatus of claim 38, 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.

40. The apparatus of claim 39, 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.

41. The apparatus of claim 39, 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.

42. The apparatus of claim 38 further comprising:

a means for storing the data.

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

44. 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.

45. The method of claim 44 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.

46. The method of claim 45, 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.

47. The method of claim 45, 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.

48. The method of claim 44, wherein the data is stored in a lookup table.

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