Method and apparatus for performing a binary search on an expanded tree
First Claim
1. A method of routing data in a network device, the method comprising the steps of:
- determining a search value;
providing at least one memory unit having a table of information, with said table of information having a plurality of search keys associated with a 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; and
performing a binary search of the lowest level search keys based on said search value to determine a 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 and a data entry of said plurality of data entries determined by said longest prefix match is used to route data.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 Claims
-
1. A method of routing data in a network device, the method comprising the steps of:
-
determining a search value; providing at least one memory unit having a table of information, with said table of information having a plurality of search keys associated with a 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; and performing a binary search of the lowest level search keys based on said search value to determine a 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 and a data entry of said plurality of data entries determined by said longest prefix match is used to route data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A network device comprising:
-
means for determining a search value; at least one memory unit having a table of information, with said table of information having a plurality of search keys associated with a 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; wherein, said expanding means increases a lower valued one of said two lowest level search keys by one to shift said bracketed range and the network device is configured to make a routing decision based on a data entry of said plurality of data entries determined by said longest prefix match. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
Specification