Dense mode coding scheme

• US 8,023,519 B2
• Filed: 11/04/2009
• Issued: 09/20/2011
• Est. Priority Date: 09/30/2002
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Mosaid Technologies Incorporated (MOSAID Technologies Inc. (f/k/a Conversant Intellectual Property Management))
• Inventors: Brown, David A., Gillingham, Peter B.
• Primary Examiner(s): Sam; Phirin
• Application Number:
  US12/612,443
• Publication Number:
  US 20100049870A1
• Time in Patent Office: 685 Days
• Field of Search: None
• US Class Current: 370/408
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

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.

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.

2. The apparatus as in claim 1, wherein the bits selected by the decoder reside at a lower level of the subtree than a bit in the subtree corresponding to the index value.

3. The apparatus as in claim 1, wherein the subtree descriptor information includes at least one bit corresponding to a node beneath a root node of the subtree and above a leaf node of the subtree.

4. The apparatus as in claim 1, wherein the subtree descriptor information includes a respective bit for each of the nodes in the subtree.

5. The apparatus as in claim 4, wherein the decoder is a thermometer decoder;

and

wherein the thermometer decoder includes decoder circuitry for decoding each level of the subtree.

6. The apparatus as claimed in claim 1, wherein the decoder comprises:

a binary decoder to receive the index value as input and to produce decoder output bits;

a first array of gates, each gate of which operates on a corresponding decoder output bit from the binary decoder and a subtree bit from the subtree descriptor information; and

a second array of gates, each gate of which operates on an output of one of the first array of gates and an output of an adjacent gate in the second array of gates to produce a decoder output.

7. The apparatus as in claim 6, wherein the decoder includes logic circuitry to modify the decoder output in response to detecting a condition in which the subtree bit indicates that there is no corresponding pointer in the mapper storage for the node identified by the index value.

8. 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.

9. The apparatus as in claim 8, wherein the bitmap information includes a bit value for each of the multiple nodes in the subtree.

10. The apparatus as in claim 8, wherein the route information includes a respective forwarding route for a given node in the subtree, the given node being located at a level in the subtree beneath the root node and above the leaf node of the subtree.

11. The apparatus as in claim 10, wherein a state of a respective bit value for the given node in the subtree indicates that the given node in the subtree has a corresponding route in the route information on which to forward the data.

12. 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.

13. 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.

14. The method as in claim 13, wherein the bitmap information includes a bit value for each of multiple nodes in the tree.

15. 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.

16. The method as in claim 15, wherein the bitmap information includes a respective bit value for each node in the subtree.

17. The method as in claim 15 further comprising:

processing the portion of the bitmap information to derive the offset value, the offset value representing a number of nodes in a respective portion of the subtree having corresponding routes in the route information.

18. The method as in claim 15 further comprising:

utilizing a thermometer decoder to decode the index value and generate the bit pattern.

19. The method as in claim 15 further comprising:

generating a count value indicating a number of nodes in the subtree beneath the index value that have a corresponding route in the route information; and

utilizing the count value as the offset value, the offset value being used to select the route on which to forward data.

20. 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.

21. The apparatus as in claim 20, wherein the decoder is a thermometer decoder.

22. The apparatus as in claim 20, wherein the offset value generator includes adder circuitry to receive the bits selected by the decoder and produce the offset value.

23. The apparatus as in claim 20, wherein the bits selected by the decoder correspond to nodes in the tree beneath the node as specified by the index value.

24. The apparatus as in claim 23, wherein the offset value represents a summation of the nodes in the tree beneath the node, which is specified by the index value, that have a corresponding pointer in the mapper storage.

25. The apparatus as in claim 20, wherein each of the pointers specifies a corresponding route on which to forward data for a respective node in the tree.