×

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

  • US 20050071501A1
  • Filed: 10/15/2004
  • Published: 03/31/2005
  • Est. Priority Date: 05/22/2000
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×