Rule set partitioning based packet classification method for internet

• US 7,747,553 B2
• Filed: 01/31/2006
• Issued: 06/29/2010
• Est. Priority Date: 01/31/2005
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Yonghua, Liang, Zhi Yong, Ge, Yi, Wang, Yan Qi, Zheng, Kai
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US11/343,991
• Publication Number:
  US 20080243748A1
• Time in Patent Office: 1,610 Days
• Field of Search: None
• US Class Current: 706/47
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

The present invention provides a rule set partitioning based packet classification method for Internet. The method comprising: performing Horizontal Cut for the rule set, determining the field for partitioning a rule layer based on a target algorithm and selecting the partition manner of the Horizontal Cut, performing Horizontal Cut according to the selected partition manner of the Horizontal Cut, thereby obtaining more than one rule layers, each rule layer being a Horizontal subset, combining the rule layers to obtain a plurality of Horizontal subsets according to the total number of the pre-designated Horizontal subsets and a predefined principle, wherein the total number of said combined plurality of Horizontal subsets equals to the total number of said pre-designated Horizontal subsets; performing Vertical Cut in each of the Horizontal subsets; then forming a Hash table that can index the Vertical subsets, so that it can be used in a lookup; and realizing rule storage in each Vertical subset respectively according to the target algorithm.

Claims

1. A method for generating a partitioned rule set for use in classifying a packet for a communications network, the method comprising executing the following steps:

obtaining a rule set comprising a plurality of rules, the plurality of rules being used to classify a packet for the communications network;

partitioning the rule set into a plurality of horizontal subsets in accordance with a classification operation and a field associated with the rule set, a given horizontal subset comprising one or more rule layers, each of the one or more rule layers comprising one or more of the plurality of rules;

partitioning at least a first and a second of the plurality of horizontal subsets into a plurality of vertical subsets, wherein, within a given one of the plurality of horizontal subsets, a first vertical subset range interval of a given one of the plurality of vertical subsets is non-overlapping with a second vertical subset range interval of another given one of the plurality of vertical subsets;

creating a plurality of non-overlapping partitions across a range interval of the rule set, a given one of the non-overlapping partitions corresponding to values which are within each of a set of vertical subset range intervals comprising one vertical subset within at least the first and the second of the horizontal subsets; and

generating a hash table that indexes the plurality of vertical subsets in accordance with the plurality of non-overlapping partitions, wherein a given vertical subset is grouped together with a given partition in accordance with a corresponding range interval of the given vertical subset.

2. The method of claim 1, further comprising the step of combining a given one or more horizontal subsets into a given horizontal subset in accordance with a total number of pre-designated horizontal subsets and a predefined principle.

3. The method of claim 1, wherein a value range of the field of a given one of the one or more of the plurality of rules is represented by a rule range interval, and wherein, within any given rule layer, a rule range interval of a given one of the plurality of rules is non-overlapping with another rule range interval of another given one of the plurality of rules.

4. The method of claim 1, wherein each of the plurality of rules comprises at least one of a source network address, a destination network address, a source port, a destination port, a protocol, a priority, and an action.

5. The method of claim 1, wherein the classification operation is configured to determine the field to be used for partitioning and select a partition manner.

6. The method of claim 1, wherein the step of partitioning at least one of the plurality of horizontal subsets into the plurality of vertical subsets, further comprises at least one of maximizing a total number of the plurality of vertical subsets and minimizing a replication of one or more rules of the plurality of vertical subsets.

7. The method of claim 6, wherein the step of maximizing a total number of the plurality of vertical subsets further comprises:

generating a plurality of combinations of one or more vertical subsets;

comparing the plurality of combinations in accordance with a number of vertical subsets; and

selecting the combination of one or more vertical subsets with a highest number of vertical subsets.

8. The method of claim 6, wherein the step of minimizing a replication of one or more rules of the plurality of vertical subsets further comprises:

generating a plurality of combinations of one or more vertical subsets;

comparing the plurality of combinations in accordance with a number of rule replications; and

selecting the combination of one or more vertical subsets with a lowest number of rule replications.

9. The method of claim 6, wherein the step of minimizing a replication of one or more rules of the plurality of vertical subsets further comprises:

determining a maximum replication threshold; and

partitioning at least one of the plurality of horizontal subsets into the plurality of vertical subsets in accordance with the maximum replication threshold.

10. The method of claim 1, further comprising the step of realizing rule storage in each of the plurality of vertical subsets according to the classification operation.

11. The method of claim 1, wherein the step of partitioning the rule set into the plurality of horizontal subsets is in accordance with at least one of a range interval based partitioning and a prefix level based partitioning.

12. The method of claim 1, wherein the step of partitioning each of the plurality of horizontal subsets into the plurality of vertical subsets is in accordance with at least one of a range interval based partitioning and an IB BIT based partitioning.

13. The method of claim 1, wherein the classification operation is an EGT algorithm.

14. The method of claim 13, wherein the classification operation partitions the rule set into the plurality of horizontal subsets in accordance with at least one of a source port and a destination port.

15. The method of claim 1, further comprising the steps of:

searching the hash table based on one or more keys to find a set of one or more vertical subsets corresponding to the one or more keys;

searching the set of one or more vertical subsets in parallel or serially; and

selecting a matching rule from the searched set of one or more vertical subsets in accordance with a priority.

16. The method of claim 1, wherein the partitioning of the first horizontal subset into a plurality of vertical subsets differs from the partitioning of the second horizontal subset into a plurality of vertical subsets.

17. The method of claim 1, wherein a number of vertical subsets within the first horizontal subsets differs from a number of vertical subsets within the second horizontal subsets.

18. A method for classifying a packet for a communications network, the method comprising executing the following steps:

obtaining a packet from the communications network;

classifying the packet based on a partitioned rule set, wherein the partitioned rule set is generated by;

obtaining a rule set comprising a plurality of rules, the plurality of rules being used to classify the packet for the communications network;

partitioning the rule set into a plurality of horizontal subsets in accordance with a classification operation and a field associated with the rule set, a given horizontal subset comprising one or more rule layers, each of the one or more rule layers comprising one or more of the plurality of rules;

partitioning at least a first and a second of the plurality of horizontal subsets into a plurality of vertical subsets, wherein, within a given one of the plurality of horizontal subsets, a first vertical subset range interval of a given one of the plurality of vertical subsets is non-overlapping with a second vertical subset range interval of another given one of the plurality of vertical subsets;

creating a plurality of non-overlapping partitions across a range interval of the rule set, a given one of the non-overlapping partitions corresponding to values which are within each of a set of vertical subset range intervals comprising one vertical subset within at least the first and the second of the horizontal subsets; and

generating a hash table that indexes the plurality of vertical subsets in accordance with the plurality of non-overlapping partitions, wherein a given vertical subset is grouped together with a given partition in accordance with a corresponding range interval of the given vertical subset.

19. The method of claim 18, wherein the step of partitioning at least one of the plurality of horizontal subsets into the plurality of vertical subsets, further comprises at least one of maximizing a total number of the plurality of vertical subsets and minimizing a replication of one or more rules of the plurality of vertical subsets.

20. A method for generating a partitioned rule set for use in classifying a packet for a communications network, the method comprising executing the following steps:

obtaining a rule set comprising a plurality of rules, the plurality of rules being used to classify a packet for the communications network;

partitioning the rule set into one or more horizontal subsets in accordance with a classification operation and a field associated with the rule set, a given horizontal subset comprising one or more rule layers, each of the one or more rule layers comprising one or more of the plurality of rules;

partitioning at least one of the one or more horizontal subsets into one or more vertical subsets, the one or more vertical subsets resulting in the creation of one or more partitions across a range interval of the rule set; and

generating a hash table that indexes the one or more vertical subsets in accordance with the one or more partitions, wherein a given vertical subset is grouped together with a given partition in accordance with a corresponding range interval of the given vertical subset;

wherein the step of partitioning at least one of the one or more horizontal subsets into the one or more vertical subsets, further comprises at least one of maximizing a total number of the one or more vertical subsets and minimizing a replication of one or more rules of the one or more vertical subsets.