Data structure for range-specified algorithms

• US 20050050060A1
• Filed: 08/27/2003
• Published: 03/03/2005
• Est. Priority Date: 08/27/2003
• Status: Abandoned Application

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Zhang, Yun, Damm, Gerard, Krishnamurthy, Anand, Tang, Yiyan, Wang, Yuke, Bou-Diab, Bashar, Qian, Lie
• Application Number:
  US10/648,791
• Publication Number:
  US 20050050060A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 Rule management

Abstract

A disjoint graph structure for packet classification in communication systems is presented. The disjoint graph is comprised of two types of data structures; an elementary interval tree (EIT) and a disjoint interval tree (DIT). The disjoint graph is constructed based on a range-specified rule set finding particular application in the classification of data packets. Each rule in the rule set has an equal number of fields and each field specifies a range referred to as an integer interval having a lower and an upper bound. The disjoint graph has the same number of layers as there are fields in each rule. The layers are comprised of nodes, and each node has an associated rule set selected from the range-specified rule set. The disjoint graph enables packet classification in only one pass through the tree. The EIT and DIT structures are also presented in detail.

Claims

1. A method of creating a tree-like data structure for use in carrying out range specified rule evaluations, the data structure having a rule specified rule set where each rule in the rule set has an equal number of fields and each field specifies a range having an upper and lower bound, there being the same number of layers in the structure as there are fields in each rule set, the method comprising:

creating a first layer of the structure made up of a set of non-overlapping ranges; and

creating one or more additional layers each made up of sets of non-overlapping ranges and sets of overlapping ranges;

wherein range specified rule evaluations are carried out by one pass through the data structure.

2. The method as defined in claim 1 wherein the data structure is a disjoint graph with the non-overlapping ranges representing elementary intervals and the overlapping ranges are disjoint intervals.

3. The method as defined in claim 2 wherein the range specified rule evaluations relate to packet classification in communications systems.

4. A system for creating a tree-like data structure for use in carrying out range specified rule evaluations, the data structure having a rule specified rule set where each rule in the rule set has an equal number of fields and each field specifies a range having an upper and lower bound, there being the same number of layers in the structure as there are fields in each rule set, the system comprising:

means for creating a first layer of the structure made up of a set of non-overlapping ranges; and

means for creating one or more additional layers each made up of sets of non-overlapping ranges and sets of overlapping ranges;

wherein range specified rule evaluations are carried out by one pass through the data structure.

5. The system as defined in claim 4 wherein the data structure is a disjoint graph with the non-overlapping ranges representing elementary intervals and the overlapping ranges are disjoint intervals.

6. A tree-like data structure stored on a computer readable medium for use in carrying out range specified rule evaluations, the data structure having a rule specified rule set where each rule in the rule set has an equal number of fields and each field specifies a range having an upper and lower bound, there being the same number of layers in the structure as there are fields in each rule set, the tree-like data structure having a first layer made up of a set of non-overlapping ranges;

and one or more additional layers each made up of sets of non-overlapping ranges and sets of overlapping ranges;

wherein range specified rule evaluations are carried out by one pass through the data structure.

7. The tree-like data structure as defined in claim 6 wherein the data structure is a disjoint graph with the non-overlapping ranges representing elementary intervals and the overlapping ranges are disjoint intervals for performing evaluations relating to packet classification in communications systems

8. A method of creating an augmented binary tree structure from a range specified rule set, each rule in the rule set having an equal number of fields and each field specifying a range having an upper and lower bound forming a set of intervals, the method comprising:

projecting end points of each interval of the set of intervals onto a line, the end points dividing the line into non-overlapping elementary intervals; and

forming the tree structure such that each node of the tree contains a single elementary interval, an indication of original intervals associated with the elementary interval, and pointers to any adjacent nodes in the tree.

9. The method as defined in claim 8 wherein the augmented binary tree structure is used for stabbing queries.

10. The method as defined in claim 8 wherein the augmented binary tree structure is an elementary interval tree for use in packet classification of computer-based communications systems.

18. An augmented binary tree structure created in accordance with the method of claim 8 stored on a computer readable medium for classifying packets.

11. A system for creating an augmented binary tree structure from a range specified rule set, each rule in the rule set having an equal number of fields and each field specifying a range having an upper and lower bound forming a set of intervals, the method comprising:

means for projecting end points of each interval of the set of intervals onto a line, the end points dividing the line into non-overlapping elementary intervals; and

means for forming the tree structure such that each node of the tree contains a single elementary interval, an indication of original intervals associated with the elementary interval, and pointers to any adjacent nodes in the tree.

12. The system as defined in claim 11 wherein the augmented binary tree structure is used for stabbing queries

13. The system as defined in claim 11 wherein the augmented binary tree structure is an elementary interval tree for use in packet classification of computer-based communications systems.

15. The method as defined in claim 11 for use in packet classification in a computer based communications system.

14. A method of creating a disjoint interval tree from a range specified rule set each rule in the rule set having an equal number of fields and each field specifying a range having an upper and lower bound forming a set of intervals, the method comprising:

combining overlapping intervals of the set of intervals to form larger intervals that are disjoint to each other; and

evaluating the overlapping intervals to find the maximum disjoint intervals for the set of intervals.

19. A disjoint interval tree created in accordance with the method of claim 14 stored on a computer readable medium for classifying packets.

16. A system for creating a disjoint interval tree from a range specified rule set each rule in the rule set having an equal number of fields and each field specifying a range having an upper and lower bound forming a set of intervals, the method comprising:

means for combining overlapping intervals of the set of intervals to form larger intervals that are disjoint to each other; and

means for evaluating the overlapping intervals to find the maximum disjoint intervals for the set of intervals.

17. The system as defined in claim 16 for use in packet classification in a computer based communications system.