Dense mode coding scheme
View Patent ↗A lookup table for searching for a longest prefix match for a key is disclosed. The lookup table provides a match for a key in a single search cycle. The number of matches stored in the lookup table is maximized by storing each match in only one location in the lookup table. The binary tree is divided into a plurality of levels and each level has a plurality of subtrees. A subtree descriptor stored for a subtree includes a field for each node in the subtree. The state of the field indicates whether an entry for the node is stored in the table. The bit vector allows indexing of the single match stored for the key.
1. A longest prefix match lookup table defining nodes of a tree searched for a route pointer corresponding to a route prefix match, the table comprising:
a mapper memory which stores pointers for nodes in a subtree; and
a subtree descriptor stored in a subtree memory, the subtree descriptor including a bit for each node in the subtree, the bit corresponding to the node indicating whether a pointer for the node is stored in the mapper memory, a pointer to a default route for the subtree shared by a plurality of nodes in the subtree being stored in a single entry in the mapper memory.
2. The longest prefix match lookup table as claimed in claim 1 wherein a pointer is stored for a node in mapper memory if the bit corresponding to the node in the subtree descriptor is set.
3. The longest prefix match lookup table as claimed in claim 1 wherein the subtree has a plurality of levels and the subtree descriptor includes a level descriptor for each level, each level descriptor including a bit for each node in the level.
4. The longest prefix match lookup table as claimed in claim 3 further comprising:
mapper address logic which performs a parallel search in each level descriptor for a node matching a search key and computes an offset to the pointer corresponding to the matching node.
5. The longest prefix match lookup table as claimed in claim 4 wherein the subtree descriptor further comprises:
a block pointer, the block pointer storing an index to the first pointer in the mapper memory for the subtree, the combination of the offset and the block pointer providing the index to the pointer for the matching node.
6. The longest prefix match lookup table as claimed in claim 1 wherein the default route is stored for a root node of the subtree.
7. The longest prefix, match lookup table as claimed in claim 6 wherein the default route stored for the root node is an indication to use another default route for a parent subtree.
8. A method for providing a longest prefix match lookup table comprising:
storing pointers for nodes in a subtree in a mapper memory; and
including a bit for each node in the subtree in a subtree descriptor stored in a subtree memory, the bit corresponding to the node indicating whether a pointer for the node is stored in the mapper memory, a pointer to a default route for the subtree shared by a plurality of nodes in the subtree is stored in a single entry in the mapper memory.
9. The method as claimed in claim 8 wherein a pointer is stored for a node in mapper memory if the bit corresponding to the node in the subtree descriptor is set.
10. The method as claimed in claim 8 wherein the subtree has a plurality of levels and the subtree descriptor includes a level descriptor for each level, each level descriptor including a bit for each node in the level.
11. The method as claimed in claim 10 further comprising:
performing a parallel search in each level descriptor for a node matching a search key; and
computing an offset to the pointer corresponding to the matching node.
12. The method as claimed in claim 11 further comprising:
storing an index to the first pointer in the mapper memory for the subtree in a block pointer in the subtree descriptor, the combination of the offset and the block pointer providing the index to the pointer for the matching node.
13. The method as claimed in claim 8 wherein the default route is stored for a root node of the subtree.
14. A method for encoding a subtree comprising the steps of:
allocating a subtree descriptor in memory, the subtree descriptor including a bit for each node in the subtree;
storing a pointer to a default route for the root in a single entry in mapper memory, the single entry shared by all nodes mapping to the default route;
setting the bit corresponding to a root of the subtree in the subtree descriptor indicating that the default route is stored in the mapper memory; and
setting the bit in the subtree descriptor corresponding to a node in the subtree having an entry in mapper memory other than the default route.
15. A method for obtaining a longest prefix match from a longest prefix match table comprising the steps of:
searching a subtree descriptor for the longest prefix match, the subtree descriptor including a bit for each node in a subtree, each bit of the subtree descriptor set having an entry in mapper memory, a single entry in mapper memory storing a default route for the root, the single entry shared by all nodes mapping to the default route; and
upon detecting the node corresponding to the detected node, computing a pointer to the mapper entry corresponding to the detected node dependent on the number of bits set in the subtree descriptor for nodes in the subtree below the node corresponding to the longest prefix match.