Method and apparatus for physical width expansion of a longest prefix match lookup table
View Patent ↗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.
1. A lookup matrix comprising:
a master lookup unit comprising a plurality of mappers which are indexed by portions of a first portion of a search key to output a route index for the search key or partial indexes to subsequent mappers; and
at least one non-master lookup unit comprising a plurality of mappers which are indexed by portions of a next portion of the search key and a partial index from a prior lookup unit to output the route index for the search key or another partial index to a subsequent non-master lookup unit.
2. The lookup matrix as claimed in claim 1 wherein the route index corresponding to the search key is stored in a single location in one of the lookup units.
3. The lookup matrix as claimed in claim 1 wherein the length of the search key is variable.
4. The lookup matrix as claimed in claim 1 wherein the length of the search key is expandable dependent on the number of non-master lookup units.
5. The lookup matrix as claimed in claim 4 wherein the search key includes a 32-bit IPv4 address.
6. The lookup matrix as claimed in claim 5 wherein the route index corresponding to the search key is found after a first search of the plurality of mappers.
7. The lookup matrix as claimed in claim 4 wherein the search key includes a 128-bit IPv6 address.
8. The lookup matrix as claimed in claim 1 wherein the partial index is a subtree index.
9. A method for providing a longest prefix match for a search key comprising the steps of:
providing a first portion of the search key to a master lookup unit to index entries stored in a plurality of mappers in the master lookup unit, each entry storing a route index or a partial index to a subsequent mapper; and
providing next portions of the search key to at least one non-master lookup unit with partial indexes from prior lookup units to index entries in the lookup unit, each entry storing the route index or a partial index for a subsequent mapper.
10. The method as claimed in claim 9 further comprising the step of:
returning the route index corresponding to the search key stored in a single entry in one of the plurality of lookup units.
11. The method as claimed in claim 9 wherein the length of the search key is variable.
12. The method as claimed in claim 11 wherein the search key includes a 32-bit IPv4 address.
13. The method as claimed in claim 12 , wherein the route index corresponding to the search key is returned after a first search of the plurality of mappers.
14. The method as claimed in claim 11 wherein the search key includes a 128-bit IPv6 address.
15. The method as claimed in claim 9 wherein the length of the search key is expandable by adding another non-master lookup unit.
16. The method as claimed in claim 9 wherein the partial index is a subtree index.
17. A lookup unit comprising:
a master lookup unit comprising a plurality of mappers which are indexed by portions of a first portion of a search key and partial indexes to output a route index for the search key or partial indexes to subsequent mappers; and
lookup means indexed by next portions of the search key and partial indexes to output the route index corresponding to the search key or partial indexes to subsequent lookup means.
18. The lookup unit as claimed in claim 17 wherein the route index corresponding to the search key is stored in a single location in one of the plurality of mappers.
19. The lookup unit as claimed in claim 17 wherein the length of the search key is variable.
20. The lookup unit as claimed in claim 19 wherein the search key includes a 32-bit IPv4 address.
21. The lookup unit as claimed in claim 20 wherein the route index corresponding to the search key is found after a first search of the plurality of mappers.
22. The lookup unit as claimed in claim 19 wherein the search key includes a 128 bit IPv6 address.
23. The lookup unit as claimed in claim 17 wherein the partial index is a subtree index.
24. A lookup matrix providing a route index for a search key comprising:
a first lookup unit which receives a first portion of the search key to index an entry which stores the route index or a partial index to a next mapper; and
at least one next lookup unit which receives a next portion of the search key and a partial index to index a next entry which stores the route index corresponding to the search key or a next partial index to the next lookup unit.
25. An apparatus for providing a route index corresponding to a search key comprising:
a forwarding engine which receives the search key and divides the search key into a plurality of portions; and
a lookup matrix coupled to the forwarding engine, which receives the portions of the search key from the forwarding engine, the lookup matrix comprising:
a master lookup unit comprising a plurality of mappers which are indexed by portions of a first portion of the search key to output a route index for the search key or partial indexes to subsequent mappers; and
at least one non-master lookup unit comprising a plurality of mappers which are indexed by portions of a next portion of the search key and a partial index from a prior lookup unit to output the route index for the search key or another partial index to a subsequent non-master lookup unit.