×

Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table

  • US 6,836,771 B2
  • Filed: 01/02/2003
  • Issued: 12/28/2004
  • Est. Priority Date: 12/10/1999
  • Status: Expired due to Term
First Claim
Patent Images

1. A method for searching for a route corresponding to a key in a multi-level lookup table, comprising the steps of:

  • selecting a subtree entry by a subtree index;

    selecting one of a plurality of sparse subtree descriptors in the selected subtree entry, the sparse subtree descriptor including a plurality of node descriptors;

    converting the node descriptors in the selected sparse subtree descriptor to masked values;

    loading the masked values in memory in longest prefix order;

    searching the memory for a longest prefix match for a portion of the key; and

    selecting the route stored in another memory dependent on the address of the longest prefix match.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×