Method and system for compressing a search tree structure used in rule classification

• US 20050240604A1
• Filed: 04/27/2004
• Published: 10/27/2005
• Est. Priority Date: 04/27/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco, Davis, Gordon T., Corl, Everett A. Jr., Sabhikhi, Ravinder K., Patel, Piyush C.
• Granted Patent: US 7,366,728 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

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.

Claims

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

2. The method of claim 1 wherein the compressed format block comprises a plurality of bits corresponding to the compressed nodes in the set of nodes, wherein the plurality of bits are used to traverse the plurality of levels.

3. The method of claim 2, wherein the compressing step (b) includes:

(b1) for each node in the set, determining whether a child of the node is a leaf node;

(b2) if the child node is not a leaf node, setting a value for the corresponding bit in the compressed format block to zero (0); and

(b3) if the child node is a leaf node, setting the value for the corresponding bit to one (1).

4. The method of claim 1, wherein each compressed node is a single bit test node comprising a next bit to test value.

5. The method of claim 4, wherein the compressed format block includes a plurality of next bit to test fields corresponding to each compressed node in the set of nodes.

6. The method of claim 5, wherein the compressing step (b) further includes:

(b1) for each compressed node in the set of nodes, storing the next bit to test value in the corresponding next bit to test field in the compressed format block.

7. The method of claim 1 further comprising:

(c) storing each child node whose parent node is a compressed node in a lowest level of the plurality of levels in an order in a first contiguous block.

8. The method of claim 7, wherein the compressed format block includes a first pointer to a base address of the first contiguous block.

9. The method of claim 8 further comprising:

(d) locating the child of a lowest level compressed parent node by utilizing the first pointer to navigate to the base address of the first contiguous structure and applying an offset based on the order in which the child node is stored in the first contiguous block.

10. The method of claim 8 further comprising:

(d) storing each child leaf node whose parent node is a compressed node in an order in a second contiguous block, wherein the compressed format block includes a second pointer to a base address of the second contiguous block.

11. The method of claim 10 further comprising:

(e) locating the child leaf node of compressed parent node by utilizing the second pointer to navigate to the base address of the second contiguous structure and applying an offset based on the order in which the child leaf node is stored in the second contiguous block.

25. The method of claim 6 further comprising:

(c) decompressing the compressed format block to traverse the plurality of levels of the tree structure during a search process to identify at least one rule that matches a key derived from a packet requiring classification.

26. The method of claim 25, wherein decompressing step (c) includes:

(c1) examining a value of a first next bit to test in the compressed format block corresponding to a first node in the set of nodes;

(c2) determining a next node to traverse based on the value of the next bit to test;

(c3) if the next node is one in the set of nodes, examining the next bit to test corresponding to the next node; and

(c4) repeating steps (c2) and (c3) until the next node is one of a leaf node or a child node outside of the set of nodes.

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

13. The computer-readable medium of claim 12, wherein the compressed format block comprises a plurality of bits corresponding to the compressed nodes in the set of nodes, wherein the plurality of bits are used to traverse the plurality of levels.

14. The computer-readable medium of claim 13, wherein the compressing instruction (b) includes:

(b1) for each node in the set, determining whether a child of the node is a leaf node;

(b2) if the child node is not a leaf node, setting a value for the corresponding bit in the compressed format block to zero (0); and

(b3) if the child node is a leaf node, setting the value for the corresponding bit to one (1).

15. The computer-readable medium of claim 12, wherein each compressed node is a single bit test node comprising a next bit to test value.

16. The computer-readable medium of claim 15, wherein the compressed format block includes a plurality of next bit to test fields corresponding to each compressed node in the set of nodes.

17. The computer-readable medium of claim 16, wherein the compressing instruction (b) further includes:

(b1) for each compressed node in the set of nodes, storing the next bit to test value in the corresponding next bit to test field in the compressed format block.

18. The computer-readable medium of claim 12 further comprising:

(c) storing each child node whose parent node is a compressed node in a lowest level of the plurality of levels in an order in a first contiguous block.

19. The computer-readable medium of claim 18, wherein the compressed format block includes a first pointer to a base address of the first contiguous block.

20. The computer-readable medium of claim 19 further comprising:

(d) locating the child of a lowest level compressed parent node by utilizing the first pointer to navigate to the base address of the first contiguous structure and applying an offset based on the order in which the child node is stored in the first contiguous block.

21. The computer-readable medium of claim 19 further comprising:

(d) storing each child leaf node whose parent node is a compressed node in an order in a second contiguous block, wherein the compressed format block includes a second pointer to a base address of the second contiguous block.

22. The computer-readable medium of claim 21 further comprising:

(e) locating the child leaf node of compressed parent node by utilizing the second pointer to navigate to the base address of the second contiguous structure and applying an offset based on the order in which the child leaf node is stored in the second contiguous block.

27. The computer-readable medium of claim 19 further comprising:

(c) decompressing the compressed format block to traverse the plurality of levels of the tree structure during a search process to identify at least one rule that matches a key derived from a packet requiring classification.

28. The computer-readable medium of claim 27, wherein decompressing instruction (c) includes:

(c1) examining a value of a first next bit to test in the compressed format block corresponding to a first node in the set of nodes;

(c2) determining a next node to traverse based on the value of the next bit to test;

(c3) if the next node is one in the set of nodes, examining the next bit to test corresponding to the next node; and

(c4) repeating steps (c2) and (c3) until the next node is one of a leaf node or a child node outside of the set of nodes.

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

24. The classification system of claim 23, wherein the network processor stores each child node whose parent node is a compressed node in a lowest level of the plurality of levels in an order in a first contiguous block and stores each child leaf node whose parent node is a compressed node in an order in a second contiguous block, wherein the compressed format block includes a first pointer to a base address of the first contiguous block and a second pointer to a base address of the second contiguous block.