Method and apparatus for physical width expansion of a longest prefix match lookup table

• US 7,913,060 B2
• Filed: 04/06/2005
• Issued: 03/22/2011
• Est. Priority Date: 06/21/2000
• Status: Expired due to Fees

• Current Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Original Assignee: Satech Group AB LLC (Intellectual Ventures LLC)
• Inventors: Brown, David A.
• Primary Examiner(s): Gu; Shawn X
• Application Number:
  US11/099,724
• Publication Number:
  US 20050175005A1
• Time in Patent Office: 2,176 Days
• Field of Search: None
• US Class Current: 711/216
• 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 unit matrix combines a plurality of lookup units to provide a longest prefix match for a search key longer than the lookup unit'"'"'s mapper key. A portion of the search key is provided to each of the plurality of lookup units in a single search request issued to the lookup unit matrix. Each lookup unit in the lookup unit matrix performs a multi-level search for the result value based on the portion of the search key forwarded as the mapper key and the result of a multilevel search in the previous lookup unit. The search results in a value corresponding to the search key stored in a single location in one of the lookup units.

Claims

1. A system comprising:

a master lookup unit comprising a direct mapper and at least one indirect mapper, wherein the direct mapper is configured to return one of a route index or a partial index in response to a search for at least a first portion of an initial mapper key comprising at least a first portion of a search key, and wherein the at least one indirect mapper is configured to return one of a route index or a partial index in response to a search for at least a corresponding subsequent portion of the initial mapper key and a partial index returned by one of either the direct mapper or another indirect mapper; and

one or more non-master lookup units configured to return at least one of a route index or a partial index in response to a search for a subsequent mapper key comprising a corresponding subsequent portion of the search key and a partial index returned by one of either the master lookup unit or another non-master lookup unit.

2. The system of claim 1, wherein at least one non-master lookup unit comprises at least one indirect mapper configured to return one of a route index or a partial index in response to a search for at least a portion of the subsequent mapper key and a partial index returned by one of either the master lookup unit or another indirect mapper of the at least one non-master lookup unit or at least one other non-master lookup unit.

3. The system of claim 1, wherein the master lookup unit is configured to return a route index when the search key corresponds to a 32-bit Internet Protocol address.

4. The system of claim 1, wherein the master lookup unit is configured to return a partial index for use by a non-master lookup unit when the search key corresponds to a 128-bit Internet Protocol address.

5. The system of claim 1, further comprising:

a forwarding engine configured to receive the search key, divide the search key into the initial mapper key and one or more subsequent mapper keys, submit the initial mapper key to the master lookup unit, and submit each subsequent mapper key to a corresponding non-master lookup unit.

6. A method comprising:

receiving an initial mapper key at a master lookup unit comprising a direct mapper and at least one indirect mapper, wherein the initial mapper key comprises at least a first portion of a search key;

searching for at least a first portion of the initial mapper key in the direct mapper, and

returning a route index in response to the search for the at least first portion of the initial mapper key resulting in the route index, and

searching the at least one indirect mapper for a key comprising a partial index and a corresponding subsequent portion of the initial mapper key in response to the search for the at least first portion of the initial mapper key resulting in the partial index; and

receiving a subsequent mapper key at a non-master lookup unit, wherein the subsequent mapper key comprises a corresponding subsequent portion of the search key and a partial index received from one of the master lookup unit or another non-master lookup unit; and

returning one of a route index or a partial index in response to a search for the subsequent mapper key in the non-master lookup unit.

7. The method of claim 6, further comprising:

dividing the search key into the initial mapper key and one or more subsequent mapper keys;

sending the initial mapper key to the master lookup unit; and

sending each of the one or more subsequent mapper keys to a corresponding non-master lookup unit.

8. The method of claim 6, wherein the non-master lookup unit comprises at least one indirect mapper, and wherein returning one of a route index or a partial index in response to a search for the subsequent mapper key in the non-master lookup unit comprises:

searching for at least a first portion of the subsequent mapper key in the at least one indirect mapper of the non-master lookup unit; and

returning the route index in response to the search for the at least first portion of the subsequent mapper key resulting in the route index; and

searching at least one subsequent indirect mapper for a key comprising the partial index and a corresponding subsequent portion of the subsequent mapper key in response to the search for the at least first portion of the subsequent mapper key resulting in the partial index.

9. The method of claim 6, wherein the search key corresponds to a 32-bit Internet Protocol address.

10. The method of claim 6, wherein the search key corresponds to a 128-bit Internet Protocol address.

11. An apparatus comprising:

means for returning one of a route index or a partial index in response to a search for an initial mapper key comprising at least a first portion of a search key, wherein the means for returning one of a route index or a partial index in response to a search for an initial mapper key comprises a direct mapper and at least one indirect mapper, wherein the direct mapper is configured to return one of a route index or a partial index in response to a search for at least a first portion of the initial mapper key, and wherein the at least one indirect mapper is configured to return one of a route index or a partial index in response to a search for at least a second portion of the initial mapper key and a partial index returned by the direct mapper; and

means for returning one of a route index or a partial index in response to a search for a subsequent mapper key comprising a corresponding subsequent portion of the search key and a partial index returned by one of either the means for returning one of a route index or a partial index in response to a search for an initial mapper key or another means for returning one of a route index or a partial index in response to a search for a subsequent mapper key.

12. The apparatus of claim 11, further comprising:

means for dividing the search key into an initial mapper key and one or more subsequent mapper keys.

13. The apparatus of claim 11, wherein the means for returning one of a route index or a partial index in response to a search for a subsequent mapper key comprises:

a first indirect mapper configured to return one of a route index or a partial index in response to a search for at least a first portion of the subsequent mapper key and a partial index returned by the means for returning one of a route index or a partial index in response to a search for an initial mapper key; and

at least one subsequent indirect mapper configured to return one of a route index or a partial index in response to a search for at least a subsequent portion of the subsequent mapper key and a partial index returned by the first indirect mapper.

14. The apparatus of claim 11, wherein the search key corresponds to a 32-bit Internet Protocol address.

15. The apparatus of claim 11, wherein the search key corresponds to a 128-bit Internet Protocol address.

16. A system comprising:

a master lookup unit configured to return one of a route index or a partial index in response to a search for an initial mapper key, the initial mapper key comprising at least a first portion of a search key, wherein the master lookup unit comprises a direct mapper and at least one indirect mapper; and

one or more non-master lookup units configured to return at least one of a route index or a partial index in response to a search for a subsequent mapper key comprising a corresponding subsequent portion of the search key and a partial index returned by one of either the master lookup unit or another non-master lookup unit, wherein at least one non-master lookup unit comprises at least one indirect mapper configured to return one of a route index or a partial index in response to a search for at least a portion of the subsequent mapper key and a partial index returned by one of either the master lookup unit or another indirect mapper of the at least one non-master lookup unit or at least one other non-master lookup unit.

17. A method comprising:

receiving an initial mapper key at a master lookup unit comprising a direct mapper and at least one indirect mapper, wherein the initial mapper key comprises at least a first portion of a search key;

returning one of a route index or a partial index in response to a search for the initial mapper key in the master lookup unit;

receiving a subsequent mapper key at a non-master lookup unit comprising at least one indirect mapper, wherein the subsequent mapper key comprises a corresponding subsequent portion of the search key and a partial index received from one of the master lookup unit or another non-master lookup unit;

searching for at least a first portion of the subsequent mapper key in the at least one indirect mapper of the non-master lookup unit;

in response to the search for the at least first portion of the subsequent mapper key resulting in a route index, returning the resulting route index; and

in response to the search for the at least first portion of the subsequent mapper key resulting in a partial index, searching at least one subsequent indirect mapper for a key comprising the resulting partial index and a corresponding subsequent portion of the subsequent mapper key.

18. An apparatus comprising:

means for returning one of a route index or a partial index in response to a search for an initial mapper key comprising at least a first portion of a search key, wherein the means for returning one of a route index or a partial index in response to a search for an initial mapper key comprises a direct mapper and at least one indirect mapper; and

means for returning one of a route index or a partial index in response to a search for a subsequent mapper key comprising a corresponding subsequent portion of the search key and a partial index returned by one of either the means for returning one of a route index or a partial index in response to a search for an initial mapper key or another means for returning one of a route index or a partial index in response to a search for a subsequent mapper key, wherein the means for returning one of a route index or a partial index in response to a search for a subsequent mapper key comprises;

a first indirect mapper configured to return one of a route index or a partial index in response to a search for at least a first portion of the subsequent mapper key and a partial index returned by the means for returning one of a route index or a partial index in response to a search for an initial mapper key; and

at least one subsequent indirect mapper configured to return one of a route index or a partial index in response to a search for at least a subsequent portion of the subsequent mapper key and a partial index returned by the first indirect mapper.