Multi-level table lookup

• US 6,434,144 B1
• Filed: 07/06/1998
• Issued: 08/13/2002
• Est. Priority Date: 07/06/1998
• Status: Expired due to Fees

• Current Assignee: Bestroute, Inc.
• Original Assignee: Bestroute, Inc.
• Inventors: Romanov, Aleksey
• Primary Examiner(s): Vincent, David
• Assistant Examiner(s): Phunkulh, Bob A.
• Application Number:
  US09/110,627
• Time in Patent Office: 1,499 Days
• Field of Search: 370/390, 370/392, 370/400, 370/401, 370/402, 370/395.1, 370/395.3, 370/395.31, 370/395.32, 709/238, 709/242, 711/216, 711/202, 711/206
• US Class Current: 370/392
• 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/54 Organization of routing tables

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.

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.

2. The device of claim 1, wherein the item corresponds to a range of Internet Protocol addresses.

3. The device of claim 2, wherein the item comprises an Internet Protocol address prefix.

4. The device of claim 2, wherein the range of Internet Protocol addresses includes addresses corresponding to multiple Internet Protocol address prefixes.

5. The device of claim 2, wherein the search key comprises an Internet Protocol address.

6. The device of claim 5, wherein the item that is the optimal match for the search key comprises the longest prefix in a prefix database that matches the search key.

7. The device of claim 5, wherein the first part of the search key comprises a contiguous sequence of bits in the destination address.

8. The device of claim 5, wherein the second part of the identifier comprises a contiguous sequence of bits in the destination address.

9. The device of claim 5, wherein the first search stage comprises a first search table memory.

10. The device of claim 9, wherein the first search table memory stores a first search table, wherein entries in the first search table correspond to ranges of Internet Protocol addresses, some entries in the first search table store prefix identifiers for developing the first item identifier signal, and some entries store second search stage identifiers for developing the second control signal.

11. The device of claim 5, wherein:

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.

17. The method of claim 16, wherein searching the subsequent level of the multi-level search table results in information descriptive of a second default value, and further comprising replacing the second default value with the first default value.

18. The method of claim 16, wherein the item comprises a prefix of an Internet Protocol address.

19. The method of claim 18, wherein the search key comprises an Internet Protocol address.

20. The method of claim 19, wherein the information contained in the entry identifies a part of the subsequent level of the multi-level search table corresponding to the destination address.

21. The method of claim 20, wherein the part comprises a sub-table of the subsequent level of the multi-level search table.

22. The method of claim 20, wherein the part comprises an entry of the subsequent level of the multi-level search table.

24. The method of claim 16, further comprising:

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 table

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

29. The data structure of claim 28, wherein:

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.