Patent ID: 7072885
Filing Date: 2006-07-04
Classification: G06F,Y10S

Abstract:
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.