Data structure for range-specified algorithms
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5)
-
-
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. - View Dependent Claims (7)
- and one or more additional layers each made up of sets of non-overlapping ranges and sets of overlapping ranges;
-
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. - View Dependent Claims (9, 10, 18)
-
-
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. - View Dependent Claims (12, 13, 15)
-
-
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. - View Dependent Claims (19)
-
-
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. - View Dependent Claims (17)
-
Specification