Multi-level table lookup
First Claim
Patent Images
1. A device for identifying an item that is an optimal match for a search key, the device comprising:
- a first search stage, comprising an input for receiving a signal corresponding to a first part of the search key, a first output for developing a first control signal indicating whether the item can be identified from the first part of the search key, and a second output for developing a first item identifier signal identifying the item if the item can be identified from the first part of the search key and for developing a second control signal if the item cannot be identified from the first part of the search key;
a second search stage for identifying the item based on the second control signal and a second part of the search key, comprising a first input coupled-to the second output of the first search stage, a second input for receiving a signal corresponding to the second part of the search key, and the first output for developing a second item identifier signal identifying the item; and
a demultiplexor for selecting a select one of the first item identifier signal and the second item identifier signal based on the first control signal.
1 Assignment
0 Petitions
Accused Products
Abstract
A multi-level table is searched for an item in an item database matching a search key. For example, a multi-level search table is searched for an identifier of an Internet Protocol prefix stored in a prefix database which most closely matches an Internet Protocol address. The search table may be modified in response to changes to the item database while the table is being searched. Default item identifier tables may be used to store default item identifiers which reduce the complexity of update operations.
-
Citations
40 Claims
-
1. A device for identifying an item that is an optimal match for a search key, the device comprising:
-
a first search stage, comprising an input for receiving a signal corresponding to a first part of the search key, a first output for developing a first control signal indicating whether the item can be identified from the first part of the search key, and a second output for developing a first item identifier signal identifying the item if the item can be identified from the first part of the search key and for developing a second control signal if the item cannot be identified from the first part of the search key;
a second search stage for identifying the item based on the second control signal and a second part of the search key, comprising a first input coupled-to the second output of the first search stage, a second input for receiving a signal corresponding to the second part of the search key, and the first output for developing a second item identifier signal identifying the item; and
a demultiplexor for selecting a select one of the first item identifier signal and the second item identifier signal based on the first control signal. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
the second search stage comprises a second search table memory; and
the second control signal comprises an addressing signal for partially addressing the second search table memory.
-
-
12. The device of claim 11, wherein the second search table memory stores a second search table, entries in the second search table corresponding to ranges of Internet Protocol addresses, the entries storing prefix identifiers for developing the second item identifier signal.
-
13. The device of claim 1, further comprising:
default memories for storing default values of items.
-
14. The device of claim 1, wherein the demultiplexor comprises a first control input coupled to the first output of the first search stage, a first data input coupled to the second output of the first search stage, and a second data input coupled to the output of the second search stage, and wherein the demultiplexor selects the first prefix identifier signal if the first control signal indicates that the prefix can be identified from the first part of the destination address, and selects the second prefix identifier signal otherwise.
-
15. The device of claim 1, wherein the second search stage operates simultaneously with the first search stage.
-
16. A computer-implemented method for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key, the method comprising the steps of:
-
searching a first level of the search table with a first part of the search key, when an entry in the first level of the search table corresponds to the first part of the search key, identifying the entry corresponding to the first part of the search key as the best matching entry, and if the entry contains an item identifier, providing a first level output identifying the item identifier in the entry as the best-matching item identifier; and
providing a first level output representing a first default value when an entry corresponding to the first part of the search key is not found, wherein a default value is the first shorter portion of a part of the search key corresponding to the entry in the search table, otherwise, searching a subsequent level of the multi-level search table with the first default value and a second part of the search key for the best-matching item identifier using information associated with the entry that is descriptive of the subsequent level and of the first default value to provide as subsequent level output one of a subsequent level item identifier and a subsequent level default value, and selecting the first level output or the subsequent level output as the item identifier matching the search key. - View Dependent Claims (17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
if the entry indicates a default item identifier, identifying as the best-matching item identifier a default item identifier corresponding to the search key.
-
-
25. The method of claim 24, wherein the item comprises a prefix of an Internet Protocol address, and wherein the search key comprises an Internet Protocol address.
-
26. The method of claim 24, wherein:
-
the default item identifier is stored in a table of default item identifiers; and
the default item identifier is located in the table of default item identifiers using the search key.
-
-
27. The method of claim 16, further comprising:
generating an exception if the item identifier is associated with exception information descriptive of the search key.
-
30. The computer-implemented method of claim 16 for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key, further comprising a computer-implemented method for updating a multi-level search table in response to addition of an item to an item database, the item corresponding to a level of the multi-level search table, the item addition updating method comprising:
-
updating the level of the search table; and
updating a default table corresponding to the level of the search table.
-
-
31. The method of claim 30, wherein the item comprises an Internet Protocol address prefix and wherein the search key comprises an Internet Protocol address.
-
32. The method of claim 31, wherein entries in the default table correspond to ranges of Internet Protocol addresses corresponding to the level of the search table, and wherein entries of the default table contain default prefixes for the ranges of Internet Protocol addresses.
-
33. The method of claim 30, wherein entries of a first level of the multi-level search table contain a default value, and wherein other levels of the multi-level search table contain a default value designator.
-
34. The method of claim 30, wherein updating is pipelined.
-
35. The computer-implemented method of claim 16 for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key, further comprising a computer-implemented method for updating a multi-level search table in response to deletion of an item from an item database, the item corresponding to a level of the multi-level search table, the item deletion updating method comprising:
-
updating the level of the search table; and
updating a default table corresponding to the level of the search table.
-
-
36. The method of claim 35, wherein the item comprises an Internet Protocol address prefix and wherein the search key comprises an Internet Protocol address.
-
37. The method of claim 36, wherein entries in the default table correspond to ranges of Internet Protocol addresses corresponding to the level of the search table, and wherein entries of the default table contain default prefixes for the ranges of Internet Protocol addresses.
-
38. The method of claim 35, wherein entries of a first level of the multi-level search table contain a default value, and wherein other levels of the multi-level search table contain a default value designator.
-
39. The method of claim 34, wherein updating is pipelined.
-
40. The method of claim 35, further comprising detecting whether the prefix is the only prefix in the item database that is more specific than a range of Internet Protocol addresses corresponding to an entry in the multi-level search table.
-
23. A computer-implemented method for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key, the method comprising the steps of:
-
identifying an entry in a first level of the search table corresponding to the search key;
if the entry contains an item identifier, identifying the best-matching item identifier the item identifier contained in the entry;
otherwise, searching a subsequent level of the multi-level search table for the best-matching item identifier using information associated with the entry that is descriptive of the subsequent level and of a first default value, and wherein the item comprises a prefix of an Internet Protocol address, the search key comprises an Internet Protocol address, and entries in the multi-level search table correspond to ranges of Internet Protocol addresses, and wherein if a prefix database contains a prefix corresponding to all Internet Protocol addresses within a range, then the entry in the search table corresponding to the range identifies the prefix; and
otherwise, the entry in the search table corresponding to the range identifies a part of a subsequent level of the search table corresponding to the destination address.
-
-
28. A data structure tangibly stored on a computer-readable medium, the data structure representing a multi-level search table for identifying a best-matching prefix identifier identifying a prefix corresponding to a destination address, the data structure comprising:
-
a plurality of levels of search tables, entries of the search tables corresponding to ranges of Internet Protocol addresses, wherein;
if a prefix database contains a prefix corresponding to all Internet Protocol addresses within a range, then an entry in the search table corresponding to the range identifies the prefix; and
otherwise, the entry in the search tablecorresponding to the range identifies a part of a subsequent level of the search table corresponding to the destination address; and
a plurality of levels of default prefix tables, entries of the default prefix tables corresponding to default prefixes for ranges corresponding to entries in the search tables. - View Dependent Claims (29)
if a prefix corresponding to all and only all of the addresses within the range is contained in a prefix database, then the default prefix of the range is the prefix; and
otherwise, the default prefix of the range is the first prefix in the prefix database that is less specific than the prefix.
-
Specification