Modular packet classification

• US 20020023089A1
• Filed: 02/22/2001
• Published: 02/21/2002
• Est. Priority Date: 02/24/2000
• Status: Active Grant

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Woo, Thomas Y.
• Granted Patent: US 7,039,641 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

The novel method and system for classifying packets through the use of filters combines heuristic tree search with the use of filter buckets. This provides high performance and reasonable storage requirement, even when applied to large number of filters (from 4K to 1 million). In addition, the novel method can adapt to the input packet distribution by taking into account the relative filter usage. The capability of employing a large number of filters in a packet classifciation system is useful in providing value-added services, such as security, quality of service (QoS), load balancing, and traffic accounting.

Claims

1. A data structure for organizing a plurality of k-dimensional filters used to classify k-dimensional bit strings, k>

0, comprising;

a jump table indexed on pre-selected bit positions of pre-selected filter dimensions, said jump table pointing to a plurality of search trees;

each said search tree having one or more terminating leaf nodes which identify a relatively small set of filters.

2. The data structure according to claim 1, wherein said jump table is indexed on a pre-selected prefix length, h_j, for each filter dimension j, 1≦

j≦

k.

3. The data structure according to claim 2, wherein said trees and are constructed such that each node thereof is associated with pre-selected bit positions of at least one pre-selected filter dimension.

4. The data structure according to claim 2, wherein said search trees are 2^m-ary trees, m>

0, and constructed such that each node is associated with m consecutive bits at pre-selected bit positions of a pre-selected filter dimension.

5. The data structure according to claim 4, wherein m=1 and the search trees are constructed such that successively deeper nodes in the tree structure are associated with successive bit positions of pre-selected filter dimensions.

6. The data structure according to claim 5, wherein each non-leaf node has two child nodes, one said child node representing a set of filters having a 0 or * bit at the bit position corresponding to the non-leaf node, and the other said child node representing a set of filters having a 1 or * bit at the bit position corresponding to the non-leaf node.

7. The data structure according to claim 6, wherein the filter dimension associated with each node is selected so as to substantially minimize the depth of the corresponding tree.

8. The data structure according to claim 6, wherein the filter dimension associated with each node is selected so as to substantially maximize the balancedness of the corresponding tree.

9. A method of identifying a filter used to classify a packet having at least one corresponding field of interest, comprising:

(a) searching a jump table for an entry matching the bits at pre-selected bit positions of said at least one packet field, wherein said jump table points to a plurality of search trees, said search thereby identifying one of said search trees;

(b) traversing said identified search tree until a terminating leaf node is reached, said terminating leaf node identifying at least one filter bucket; and

(c) searching said identified filter bucket until a match is found between the bits of the at least one packet field and the bits of the filter.

10. A method of identifying a k-dimensional filter used to classify a packet having k corersponding fields of interest, k>

0, comprising;

(a) searching a jump table for an entry matching the bits at pre-selected leading bit positions of one or more pre-selected fields of said packet, wherein said jump table is indexed on pre-selected prefix lengths of pre-selected filter dimensions and points to a plurality of search trees, said search thereby identifying one of said search trees;

(b) traversing said identified search tree by comparing the bits at pre-selected bit positions of one or more pre-selected fields of said packet against the bits at pre-selected bit positions of pre-selected filter dimensions associated with each node of said tree until a terminating leaf node is reached, said terminating leaf node identifying at least one filter bucket; and

(c) searching said identified filter bucket until a match is found between the bits of the k packet fields and the bits of the k filter dimensions, if any.

11. The method according to claim 10, wherein:

said jump table is indexed on a pre-selected prefix length, h_j, of each filter dimension j, 1≦

j≦

k; and

said jump table search includes concatenating the leading h_j bits of each field of said packet and comparing said concatenation against entries in said jump table.

12. The method according to claim 11, wherein said saerch trees and are constructed such that each node thereof is associated with pre-selected bit positions of at least one pre-selected filter dimension.

13. The method according to claim 11, wherein said search trees are 2^m-ary trees, m>

0, and constructed such that each node is associated with m consecutive bits at pre-selected bit positions of one pre-selected filter dimension.

14. The method according to claim 13, wherein m=1 and the search trees are constructed such that successively deeper nodes in the tree structure are associated with successive bit positions of pre-selected filter dimensions.

15. The method according to claim 14, wherein each non-leaf node has two child nodes, one said child node representing a set of filters having a 0 or * bit at the bit position corresponding to the non-leaf node, and the other said child node representing a set of filters having a 1 or * bit at the bit position corresponding to the non-leaf node.

16. The method according to claim 15, wherein the filter dimension associated with each node is selected so as to substantially minimize the depth of the corresponding tree.

17. The method according to claim 15, wherein the filter dimension associated with each node is selected so as to substantially maximize the balancedness of the corresponding tree.

19. The method according to claim 18, wherein said broad subsets are represented by a jump table indexed on pre-selected prefix lengths of pre-selected filter dimensions, said jump table pointing to said broad filter subsets.

20. The method according to claim 19, wherein said jump table is indexed on a pre-selected prefix length, h_j, for each filter dimension j, 1≦

j≦

k.

21. The method according to claim 18, wherein each said broad filter subset is organized as a 2^m-ary tree, m>

0, said filter buckets being logically disposed at leaf nodes thereof.

22. The method according to claim 21, wherein said tree is constructed such that each node is associated with m bits at pre-selected bit positions of a pre-selected filter dimension.

23. The method according to claim 22, wherein m=1 and said tree is constructed such that successively deeper nodes thereof are associated with successive bit positions of pre-selected filter dimensions.

24. The method according to claim 23, wherein each non-leaf node has two child nodes, one said child node representing a set of filters having a 0 or * bit at the bit position corresponding to the non-leaf node, and the other said child node representing a set of filters having a 1 or * bit at the bit position corresponding to the non-leaf node.

25. The method according to claim 24, wherein the pre-selected filter dimension is the one which minimizes N* _j, where j is a bit position.

26. The method according to claim 24, wherein the pre-selected filter dimension is the one which minimizes D_j, where j is a bit position.

18. A method of converting a k-dimensional filter table, comprising:

segmenting said filters into broad subsets based on pre-selected prefix lengths of pre-selected filter dimensions; and

recursively dividing each said broad subset into one or more filter buckets.