Methods and devices for creating, compressing and searching binary tree
AssigneeHuawei Technologies Co., Ltd.
InventorsWenyong Zhang, Hui Wang
Life of this patent
Estimating the term…
Abstract
Methods and devices for creating, compressing and searching a binary tree are provided by the present disclosure, which relates to the field of traffic classification. Binary tree compression includes: determining a number of a compression layer or a number of an intermediate node, compressing a binary tree according to the number of the compression layer or the number of the intermediate node to form at least one compression node, and creating a bitmap of the compression node. Therefore, the depth of the decision tree is reduced, the search speed is increased, rule expansion is avoided, and rule replication is reduced.
Claims8
A computer for compressing a binary tree, comprising:
- a memory;
- and a processor coupled with the memory, the processor is configured to perform operations comprising:
- determining a compression parameter according to a number of bits Nb of data read in one memory access, a number of bits Ni used by a bit index of each intermediate node in intermediate nodes, a number of bits Na used by a start address of sub-nodes of a compression node, a number of bits Nt used by a compression node type, and a number of bits used by a bitmap;
- compressing the binary tree according to the compression parameter to form the compression node;
- creating the bitmap of the compression node, wherein the compression parameter is a number n of compressed layers in one compression node, and is determined according to compressed layers in one compression node, and is determined according to
- n
- ≤
- Log
- 2
-
- (
- N
- b
- -
- N
- a
- -
- N
- t
- N
- i
- +
- 1
- +
- 1
- )
- ;
- applying the bitmap to the binary tree, wherein the binary tree represents a plurality of nodes including the intermediate nodes connected in a tree configuration, and said applying reduces the binary tree into a compressed binary tree with a reduced search depth;
- and
- applying the compressed binary tree to a packet classifier for performing routing decision for a packet at each of the plurality of nodes.
A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer, cause the computer to perform operations comprising:
- determining a compression parameter according to a number of bits Nb of data read in one memory access, a number of bits Ni used by a bit index of a intermediate node, a number of bits Na used by a start address of sub-nodes of a compression node, a number of bits Nt used by a compression node type, and a number of bits used by a bitmap;
- compressing the binary tree according to the compression parameter to form at least one compression node;
- creating the bitmap of the compression node, wherein the compression parameter is a number n of compressed layers in one compression node, and is determined according to
- n
- ≤
- Log
- 2
-
- (
- N
- b
- -
- N
- a
- -
- N
- t
- N
- i
- +
- 1
- +
- 1
- )
- ;
- applying the bitmap to the binary tree, wherein the binary tree represents a plurality of nodes including the intermediate nodes connected in a tree configuration, and said applying reduces the binary tree into a compressed binary tree with a reduced search depth;
- and
- applying the compressed binary tree to a packet classifier for performing routing decision for a packet at each of the plurality of nodes.
Dependencies are inferred from the claim text.