EP1515501A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Data structure for range-specified algorithms
Assignee: Alcatel Lucent SAS
•
Filing: 2004-08-24
•
Granted: —
•
Expires: 2024-08-24
Abstract
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.
Inventors
- 👤 Gerard Damm
- 👤 Bashar Bou-Diab
- 👤 Yuke Wang
- 👤 Yiyan Tang
- 👤 Anand Krishnamurthy
- 👤 Lie Qian
- 👤 Yun Zhang
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-29 13:56
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/48; H04L45/302; H04L45/308; H04L45/74; H04L45/742; H04L63/00; H04L63/02; H04L63/0227; H04L63/0263
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
122 words
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.
Claim 2
Dependent Claim
29 words
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.
Claim 3
Dependent Claim
20 words
The method as defined in claim 2 wherein the range specified rule
evaluations relate to packet classification in communications systems.
Claim 4
Independent Claim
126 words
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.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Dependent Claim
121 words
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.
Claim 7
Dependent Claim
41 words
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
Claim 8
Independent Claim
107 words
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.
Claim 9
Dependent Claim
18 words
The method as defined in claim 8 wherein the augmented binary tree
structure is used for stabbing queries.
Claim 10
Dependent Claim
27 words
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.
Claim 11
Independent Claim
111 words
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.
Claim 12
Dependent Claim
18 words
The system as defined in claim 11 wherein the augmented binary tree
structure is used for stabbing queries
Claim 13
Dependent Claim
27 words
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.
Claim 14
Independent Claim
80 words
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.
Claim 15
Dependent Claim
18 words
The method as defined in claim 11 for use in packet classification in a
computer based communications system.
Claim 16
Independent Claim
84 words
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.
Claim 17
Dependent Claim
18 words
The system as defined in claim 16 for use in packet classification in a
computer based communications system.
Claim 18
Dependent Claim
23 words
An augmented binary tree structure created in accordance with the method
of claim 8 stored on a computer readable medium for classifying packets.
Claim 19
Dependent Claim
22 words
A disjoint interval tree created in accordance with the method of claim 14
stored on a computer readable medium for classifying packets.
References Cited (Backward Citations)
US6539394B1
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.