Method and apparatus for performing a binary search on an expanded tree

• US 20010056417A1
• Filed: 05/22/2001
• Published: 12/27/2001
• Est. Priority Date: 05/22/2000
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Cao, Jun, Ng, Eric, Smith, Brandon Carl
• Granted Patent: US 6,826,561 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and apparatus for searching an electronically stored table of information including a plurality of table entries and facilitating high speed searching of a table to provide a longest matching entry. The table searching method uses at least one memory unit having a table of information including a plurality of data entries. The table of information has a plurality of search keys associated with the plurality of data entries and the plurality of search keys form a tree structure based on a prefix length for each of the search keys. The plurality of search keys are expanded such that each of the plurality of search keys has two lowest level search keys associated therewith that cover a lowest level of the tree structure. A binary search of the lowest level search keys is performed based on a search value to determine a longest prefix match. A data entry of the plurality of data entries is output based on said longest prefix match. The method is also applicable to routing data in an internet router where the routing of data packets depends on address information stored in the table of information.

Claims

1. A table searching method, the method comprising the steps of:

providing at least one memory unit having a table of information including a plurality of data entries, with said table of information having a plurality of search keys associated with the plurality of data entries and with the plurality of search keys forming a tree structure based on a prefix length for each of the search keys;

expanding the plurality of search keys such that each of the plurality of search keys is a lowest level search key or has two lowest level search keys associated therewith that cover a lowest level of the tree structure and bracket a range on said lowest level;

performing a binary search of the lowest level search keys based on a search value to determine a longest prefix match; and

outputting a data entry of said plurality of data entries based on said longest prefix match;

wherein, in the expanding step, a lower valued one of said two lowest level search keys is increased by one to shift said bracketed range.

2. A table searching method as recited in

claim 1

wherein said step of providing at least one memory unit comprises providing at least one memory unit with said table of information having a plurality of search keys based on a subset of Internet Protocol Destination Addresses and wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address.

3. A table search method as recited in

claim 2

wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 32 bits.

4. A table search method as recited in

claim 2

wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 128 bits.

5. A table search method as recited in

claim 1

wherein said step of providing at least one memory unit comprises providing at least one memory unit having a plurality of virtual tables of information, each having a plurality of data entries, and the method further comprises:

determining a virtual tag based on said search value and setting one of said plurality of virtual tables as said table of information based on said virtual tag.

6. table search method as recited in

claim 1

wherein said step of performing a binary search comprises performing the binary search in a plurality of stages.

7. A table search method as recited in

claim 1

further comprising updating the data entries in said table of information.

8. A table search method as recited in

claim 7

wherein said step of updating the data entries in said table of information is performed concurrently with said step of performing a binary search.

9. A table search method as recited in

claim 7

wherein said step of updating the data entries in said table of information comprises the steps of:

determining a shift in the data entries when a new data entry is added or when an existing data entry is deleted;

comparing the shift with a predetermined value;

determining an insertion point of said new data entry when said new data entry is added or a deletion point of said existing data entry when said existing data entry is deleted, based on a result of said comparing step; and

inserting the new data entry at the insertion point or deleting a duplicate data entry at the deletion point.

10. A method of routing data on an internet router, the method comprising the steps of:

receiving an incoming data packet;

processing said incoming data packet to determine a search value;

providing at least one memory unit having a table of information including a plurality of data entries, with said table of information having a plurality of search keys associated with the plurality of data entries and with the plurality of search keys forming a tree structure based on a prefix length for each of the search keys;

expanding the plurality of search keys such that each of the plurality of search keys is a lowest level search key or has two lowest level search keys associated therewith that cover a lowest level of the tree structure and bracket a range on said lowest level;

performing a binary search of the lowest level search keys based on said search value to determine a longest prefix match; and

routing said incoming data packet based on a data entry of said plurality of data entries determined by said longest prefix match;

wherein, in the expanding step, a lower valued one of said two lowest level search keys is increased by one to shift said bracketed range.

11. A method of routing data as recited in

claim 10

wherein said step of providing at least one memory unit comprises providing at least one memory unit with said table of information having a plurality of search keys based on a subset of Internet Protocol Destination Addresses and wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address.

12. A method of routing data as recited in

claim 11

wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 32 bits.

13. A method of routing data as recited in

claim 11

wherein said step of performing a binary search comprises performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 128 bits.

14. A method of routing data as recited in

claim 10

wherein said step of providing at least one memory unit comprises providing at least one memory unit having a plurality of virtual tables of information, each having a plurality of data entries, and the method further comprises:

determining a virtual tag based on said search value and setting one of said plurality of virtual tables as said table of information based on said virtual tag.

15. A method of routing data as recited in

claim 10

wherein said step of performing a binary search comprises performing the binary search in a plurality of stages.

16. A method of routing data as recited in

claim 10

further comprising updating the data entries in said table of information.

17. A method of routing data as recited in

claim 16

wherein said step of updating the data entries in said table of information is performed concurrently with said step of performing a binary search.

18. A method of routing data as recited in

claim 16

wherein said step of updating the data entries in said table of information comprises the steps of:

determining a shift in the data entries when a new data entry is added or when an existing data entry is deleted;

comparing the shift with a predetermined value;

determining an insertion point of said new data entry when said new data entry is added or a deletion point of said existing data entry when said existing data entry is deleted, based on a result of said comparing step; and

inserting the new data entry at the insertion point or deleting a duplicate data entry at the deletion point.

19. A table searching apparatus comprising:

at least one memory unit having a table of information including a plurality of data entries, with said table of information having a plurality of search keys associated with the plurality of data entries and with the plurality of search keys forming a tree structure based on a prefix length for each of the search keys;

means for expanding the plurality of search keys such that each of the plurality of search keys is a lowest level search key or has two lowest level search keys associated therewith that cover a lowest level of the tree structure and bracket a range on said lowest level;

means for performing a binary search of the lowest level search keys based on a search value to determine a longest prefix match; and

means for outputting a data entry of said plurality of data entries based on said longest prefix match;

wherein, said expanding means increases a lower valued one of said two lowest level search keys by one to shift said bracketed range.

20. A table searching apparatus as recited in

claim 19

wherein said at least one memory unit comprises at least one memory unit with said table of information having a plurality of search keys based on a subset of Internet Protocol Destination Addresses and wherein said means for performing a binary search comprises means for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address.

21. A table searching apparatus as recited in

claim 20

wherein said means for performing a binary search comprises means for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 32 bits.

22. A table searching apparatus as recited in

claim 20

wherein said means for performing a binary search comprises means for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 128 bits.

23. A table searching apparatus as recited in

claim 19

wherein said at least one memory unit comprises at least one memory unit having a plurality of virtual tables of information, each having a plurality of data entries, and further comprises:

means for determining a virtual tag based on said search value and means for setting one of said plurality of virtual tables as said table of information based on said virtual tag.

24. A table searching apparatus as recited in

claim 19

wherein said means for performing a binary search comprises means for performing the binary search in a plurality of stages.

25. A table searching apparatus as recited in

claim 19

further comprising means for updating the data entries in said table of information.

26. A table searching apparatus as recited in

claim 25

wherein said means for updating the data entries in said table of information is configured such the updating of data can be performed concurrently with said step of performing a binary search.

27. A table searching apparatus as recited in

claim 25

wherein said means for updating the data entries in said table of information comprises:

means for determining a shift in the data entries when a new data entry is added or when an existing data entry is deleted;

means for comparing the shift with a predetermined value;

means for determining an insertion point of said new data entry when said new data entry is added or a deletion point of said existing data entry when said existing data entry is deleted, based on a result of said comparing step;

means for inserting the new data entry at the insertion point; and

means for deleting a duplicate data entry at the deletion point.

28. An internet router comprising:

means for receiving an incoming data packet;

means for processing said incoming data packet to determine a search value;

at least one memory unit having a table of information including a plurality of data entries, with said table of information having a plurality of search keys associated with the plurality of data entries and with the plurality of search keys forming a tree structure based on a prefix length for each of the search keys;

means for expanding the plurality of search keys such that each of the plurality of search keys is a lowest level search key or has two lowest level search keys associated therewith that cover a lowest level of the tree structure and bracket a range on said lowest level;

means for performing a binary search of the lowest level search keys based on said search value to determine a longest prefix match;

means for routing said incoming data packet based on a data entry of said plurality of data entries determined by said longest prefix match;

wherein, said expanding means increases a lower valued one of said two lowest level search keys by one to shift said bracketed range.

29. An internet router as recited in

claim 28

wherein said at least one memory unit comprises at least one memory unit with said table of information having a plurality of search keys based on a subset of Internet Protocol Destination Addresses and wherein said means for performing a binary search comprises means s for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address.

30. An internet router as recited in

claim 29

wherein said means for performing a binary search comprises means for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 32 bits.

31. An internet router as recited in

claim 29

wherein said means for performing a binary search comprises means for performing a binary search of the lowest level search keys based on an input Internet Protocol Destination Address having a length of 128 bits.

32. An internet router as recited in

claim 28

wherein said at least one memory unit comprises at least one memory unit having a plurality of virtual tables of information, each having a plurality of data entries, and further comprises:

means for determining a virtual tag based on said search value and means for setting one of said plurality of virtual tables as said table of information based on said virtual tag.

33. An internet router as recited in

claim 28

wherein said means for performing a binary search comprises means for performing the binary search in a plurality of stages.

34. An internet router as recited in

claim 28

further comprising means for updating the data entries in said table of information.

35. An internet router as recited in

claim 34

wherein said means for updating the data entries in said table of information is configured such the updating of data can be performed concurrently with said step of performing a binary search.

36. An internet router as recited in

claim 34

wherein said means for updating the data entries in said table of information comprises:

means for determining a shift in the data entries when a new data entry is added or when an existing data entry is deleted;

means for comparing the shift with a predetermined value;

means for determining an insertion point of said new data entry when said new data entry is added or a deletion point of said existing data entry when said existing data entry is deleted, based on a result of said comparing step;

means for inserting the new data entry at the insertion point; and

means for deleting a duplicate data entry at the deletion point.