Rule set partitioning based packet classification method for Internet

• US 20080243748A1
• Filed: 01/31/2006
• Published: 10/02/2008
• Est. Priority Date: 01/31/2005
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Lin, Yong Hua, Liang, Zhi Yong, Ge, Yi, Wang, Yan Qi, Zheng, Kai
• Granted Patent: US 7,747,553 B2
• Time in Patent Office: Days
• 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 rule set partitioning based packet classification method for Internet, comprising:

performing Horizontal Cut for the rule set; and

performing Vertical Cut for the rule set.

2. The method according to claim 1, wherein said step of performing Horizontal Cut for the rule set comprising:

determining the field for partitioning a rule layer based on a target algorithm, and selecting the partition manner of the Horizontal Cut.

3. The method according to claim 2, wherein, Horizontal Cut is performed according to the selected partition manner of the Horizontal Cut, thereby obtaining more than one rule layers, each rule layer being a Horizontal subset.

4. The method according to claim 3, wherein in one rule layer, there is no overlap between the rules on the field for Horizontal Cut.

5. The method according to claim 3, wherein 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.

6. The method according to claim 5, wherein the total number of said combined plurality of Horizontal subsets is equal to the total number of said pre-designated Horizontal subsets.

7. The method according to claim 2, performing Vertical Cut in each of the Horizontal subsets.

8. The method according to claim 7, said predefined principle is a principle of maximizing Vertical subsets.

9. The method according to claim 7, said predefined principle is a principle of reducing replication.

10. The method according to claim 8, said step of performing Vertical Cut further comprising:

maximizing the total number of the generated Vertical subsets on the premise that replication will not be generated.

11. The method according to claim 10, wherein, further comprising:

forming a Hash table that can index the Vertical subsets for lookup.

12. The method according to claim 11, wherein, further comprising:

realizing rule storage in each Vertical subset respectively according to the target algorithm.

13. The method according to claim 9, said step of performing Vertical Cut further comprising:

determining a maximum replication threshold, and performing said Vertical Cut based on this threshold, to minimize the number of the rules that produce replication and make the number lower than this threshold.

14. The method according to claim 13, wherein, further comprising:

forming a Hash table that can index the Vertical subsets for lookup.

15. The method according to claim 14, wherein, further comprising:

realizing rule storage in each Vertical subset respectively according to the target algorithm.

16. The method according to claim 2, wherein said determined field for partitioning a rule layer is selected from those fields which are not used by the target algorithm.

17. The method according to claim 2, wherein said target algorithm is an EGT algorithm.

18. The method according to claim 17, wherein taking a source address field and a destination address field as the main classification basis, and selecting a source port or a destination port as the field for partitioning a rule layer, the partitioning manner of said Horizontal Cut being a range interval based partitioning.

19. A method for performing a lookup by using the rule subset obtained from the method according to any one of claims 1-18, comprising:

searching a Hash table based on keys to find a set of the multiple Vertical subsets corresponding to the keys;

searching the multiple Vertical subsets in parallel or serially; and

selecting the ultimate search result from the search results of the multiple Vertical subsets based on the priority.