DENSE MODE CODING SCHEME
First Claim
Patent Images
1. An apparatus comprising:
- mapper storage to store pointers for nodes in a subtree;
subtree descriptor information including bits corresponding to nodes in the subtree, a state of each bit in the subtree descriptor information indicating whether a pointer for a corresponding node in the subtree is stored in the mapper storage; and
mapper address logic to receive an index value identifying a node in the subtree, the mapper address logic including a decoder to select bits in the subtree descriptor information as delineated by the index value, the mapper address logic including an adder to sum the bits selected by the decoder to calculate an offset to a pointer in the mapper storage.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
26 Claims
-
1. An apparatus comprising:
-
mapper storage to store pointers for nodes in a subtree; subtree descriptor information including bits corresponding to nodes in the subtree, a state of each bit in the subtree descriptor information indicating whether a pointer for a corresponding node in the subtree is stored in the mapper storage; and mapper address logic to receive an index value identifying a node in the subtree, the mapper address logic including a decoder to select bits in the subtree descriptor information as delineated by the index value, the mapper address logic including an adder to sum the bits selected by the decoder to calculate an offset to a pointer in the mapper storage. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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.
-
-
9. An apparatus comprising:
-
bitmap information representing a subtree of multiple nodes, the multiple nodes corresponding to routes on which to forward data in a network, the bitmap information including bit values indicating whether a node in the subtree has an associated route for routing of data, the bitmap information including a respective bit value for at least one node in the subtree between a root node of the subtree and a leaf node of the subtree; a storage resource to store route information associated with the multiple nodes present in the subtree; and mapper logic to receive an index value identifying a node in the subtree, the mapper logic configured to select, based on the index value, which portion of the bitmap information to process to identify a route in the stored route information on which to forward the data. - View Dependent Claims (10, 11, 12)
-
-
13. An apparatus comprising:
-
bitmap information including bit values, the bit values indicating which nodes in a tree are nodes having associated routes for routing of data, the bitmap including at least one bit value corresponding to a node between a root node and a leaf node of the tree; and address mapper logic to;
i) derive a count value based on a number of nodes in the tree having associated routes for routing of data, and ii) identify, based on the count value as an index, a route amongst the associated routes on which to forward the data.
-
-
14. A method comprising:
-
storing bitmap information in a storage device, the bitmap information representing a tree, the tree including multiple nodes corresponding to routes on which to forward data in a network, the bitmap information including bit values indicating whether a node in the tree has an associated route for routing of data, the bitmap information including a respective bit value for at least one node in the tree that resides below a root node of the tree and above a leaf node of the tree; storing route information associated with the multiple nodes in the tree; receiving an index value identifying a node in the tree; and selecting, via use of the index value, which portion of the bitmap information to process to identify a route in the route information on which to forward the data. - View Dependent Claims (15)
-
-
16. A method comprising:
-
storing bitmap information in a storage device, the bitmap information representing a subtree, the subtree including multiple nodes corresponding to routes on which to forward data in a network, the bitmap information including bit values indicating whether a node in the subtree has an associated route for routing of data; storing route information associated with the multiple nodes in the subtree; receiving an index value identifying a node in the subtree; and generating, via use of the index value, a bit pattern delineating the portion of the bitmap information to produce an offset value, the offset value indicative of a route in the route information on which to forward the data. - View Dependent Claims (17, 18, 19, 20)
-
-
21. An apparatus comprising:
-
mapper storage to store pointers for nodes in a tree; tree descriptor information including a bit for each node in the tree, a state of the bit for a corresponding node in the tree indicating whether a pointer for the corresponding node is stored in the mapper storage; mapper address logic including; input to receive an index value identifying a node in the tree; a decoder to select bits in the tree descriptor information depending on a setting of the index value; and an offset value generator to derive, based on the bits in the tree descriptor information selected by the decoder, an offset value to select a pointer in the mapper storage. - View Dependent Claims (22, 23, 24, 25, 26)
-
Specification