Dense mode coding scheme

Abstract

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, the table comprising:
 mapper storage to store pointers for nodes in a subtree; and   subtree descriptor information including a bit for each of multiple nodes in the subtree, a state of a bit for a corresponding node in the subtree indicating whether a pointer for the corresponding node is stored in the mapper storage.