Back to results
US 2014/0351282 A1Published application
Methods and Systems for Data Packet Routing
AssigneeCisco Technology, Inc.
InventorsJohn J. Williams, Jr., George Azevedo, David Lipschutz
Life of this patent
Estimating the term…
Abstract
Optimizing a bitmap data tree and a corresponding lookup operation in the bit map data tree may be provided. A number of branches for each search node of a data tree may be counted. The data tree may comprise a plurality of search nodes. Then an optimum depth for the plurality of search nodes may be identified based on the number of branches in the data tree. Next, a hash node may be added to replace a search node of the data tree when a number of branches for the search node is greater than the identified optimum depth.
Claims20
A method comprising:
- counting a number of branches for each search node of a data tree, the data tree comprising a plurality of search nodes;
- identifying an optimum depth for the plurality of search nodes based on the number of branches in the data tree;
- and
- adding a hash node to replace a search node of the data tree when a number of branches for the search node is greater than the identified optimum depth.
1 more element
A method comprising:
- constructing a bit map data tree comprising a plurality of search nodes;
- identifying an optimum depth for each of the plurality of search nodes based on a number of branches in the data tree;
- and
- replacing a search node of the data tree with a hash node when the number of branches for the replaced search node is greater than the identified optimum depth.
1 more element
An apparatus comprising:
- a plurality of input ports that receive a message having a destination address;
- a plurality of output ports that output the message based on a return route pointer;
- and
- a routing table circuit configured to receive the message having the destination address, the routing table circuit further comprising:
- at least one memory to store at least one bit map data tree, wherein the bit map data tree comprises a plurality of search nodes, wherein the routing table circuit is configured to replace at least one of the plurality of search nodes in the data tree with at least one hash node, wherein the at least one of the plurality of search nodes is replaced with the hash nodes based on an optimal depth for the plurality of search nodes in accordance with a number of branches associated with the plurality of search nodes.
2 more elements
Dependencies are inferred from the claim text.