Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table
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.
3 Assignments
0 Petitions
Accused Products
Abstract
We present a lookup table which allows sparse subtree descriptors and dense subtree descriptors to be stored in the same memory. A subtree entry in the memory stores a dense subtree descriptor for a dense subtree or a plurality of sparse subtree descriptors for sparse subtrees. The subtree entry is indexed by a leaf in the previous subtree. The sparse subtree descriptor stores at least one node descriptor. The node descriptor describes a set of leaves in the sparse subtree having a common value. The common value is encoded in the node descriptor using run length encoding.
54 Citations
8 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
Specification