Method and system for compressing a search tree structure used in rule classification
AssigneeInternational Business Machines Corporation
InventorsEverett Corl, Gordon Davis, Marco Heddes, Piyush Patel, Ravinder Sabhikhi
Life of this patent
Estimating the term…
Abstract
The present invention relates to a method and system for compressing a tree structure. The method of the present invention includes providing a compressed format block for representing a plurality of levels of the tree structure, where the plurality of levels comprises a set of nodes. The method also includes compressing each node in the set of nodes into the compressed format block, such that the plurality of levels is traversed in a single memory access.
Claims28
A method for compressing a tree structure comprising:
- (a) providing a compressed format block for representing a plurality of levels of the tree structure, wherein the plurality of levels comprises a set of nodes;
- and
- (b) compressing each node in the set of nodes into the compressed format block, such that the plurality of levels is traversed in a single memory access.
A computer-readable medium containing a program for compressing a tree structure comprising:
- (a) providing a compressed format block for representing a plurality of levels of the tree structure, wherein the plurality of levels comprises a set of nodes;
- and
- (b) compressing each node in the set of nodes into the compressed format block, such that the plurality of levels is traversed in a single memory access.
A classification system comprising:
- at least one communications network;
- a switch in each of the at least one communications networks;
- storage in the switch for storing a plurality of multi-field classification rules;
- and
- a network processor in the switch for classifying packets of information, wherein the network processor is programmed to compress a tree structure by providing a compressed format block for representing a plurality of levels of the tree structure, wherein the plurality of levels comprises a set of nodes, and compressing each node in the set of nodes into the compressed format block, such that the plurality of levels is traversed in a single memory access.
Dependencies are inferred from the claim text.