Methods and systems for data packet routing

摘要

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.

主权项

1. 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 replacing a search node of the data tree with a hash node, when a number of branches for the search node is greater than the identified optimum depth, the hash node comprising buckets having entries of hashed branches of the search node, wherein replacing the search node with the hash node comprises:
hashing branches of the search node using a first hash function,classifying the hashed branches into the buckets, each of the buckets having at least one branch; andhashing the at least one branch assigned to the buckets using a second hash function to assign an individual location in respective buckets, wherein the second hash function is different from the first hash function.