Method and apparatus for set intersection rule matching
First Claim
1. A computer-implemented method for checking a rule table, the method comprising:
- (a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, and wherein each of said segments comprises a number of positions;
(b) storing rule vectors in said rule table, wherein said storing comprises;
(i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer;
(ii) receiving a value of a parameter of a rule vector pointed to by said second variable, wherein said third variable is set to the received value;
(iii) setting a bit in the rule table to a logical “
1”
, wherein the bit is identified by a row pointed to by the second variable, at a segment pointed to by the third variable, and in a position pointed to by the first variable;
(iv) increasing the value of the second variable by one; and
(v) while the value of the second variable is smaller than the number of rows going to and continuing processing from operation (ii);
(c) comparing a received data vector to at least one of the stored rule vectors; and
(d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors.
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for of high-speed and memory efficient rule matching, the rule matching being performed on an m-dimensional universe with each dimension bound by a given range of coordinate values, and a set of rules that apply to an undetermined number of coordinates in that universe. More specifically, a high-speed computer based packet classification system, uses an innovative set intersection memory configuration to provide efficient matching of packets flowing through a network system to a specific process flow based on a packet tuple. The system also provides classification of packets as they flow through a network system. More particularly, this system correlates these flowing packets with previously received packets, along with identifying the packets so that they are handled efficiently. The ability to correlate packets to their corresponding process flows permits the implementation of service aware networks (SAN) that are capable of handling network situations at the application level.
-
Citations
91 Claims
-
1. A computer-implemented method for checking a rule table, the method comprising:
-
(a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, and wherein each of said segments comprises a number of positions; (b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer; (ii) receiving a value of a parameter of a rule vector pointed to by said second variable, wherein said third variable is set to the received value; (iii) setting a bit in the rule table to a logical “
1”
, wherein the bit is identified by a row pointed to by the second variable, at a segment pointed to by the third variable, and in a position pointed to by the first variable;(iv) increasing the value of the second variable by one; and (v) while the value of the second variable is smaller than the number of rows going to and continuing processing from operation (ii); (c) comparing a received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A rule table checking system that comprises:
-
an accessible memory; and a controller in communication with the accessible memory, wherein said controller is configured to provide rule table checking using a method comprising; (a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, and wherein each of said segments comprises a number of positions; (b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer; (ii) receiving a value of a parameter of a rule vector pointed to by the second variable, wherein a third variable is set to the received value; (iii) setting a bit in the rule table to a logical “
1”
, wherein the bit is identified by a row pointed to by the second variable, at a segment pointed to by the third variable, and in a position pointed to by the first variable;(iv) increasing the value of the second variable by one; and (v) while the value of the second variable is smaller than the number of rows, going to and continuing processing from operation (ii). (c) comparing a received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. Computer software that is utilized in a rule table checking system, the software comprising:
-
a computer accessible medium having software instructions; and wherein said software instructions provide rule table checking using a method comprising; (a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, and wherein each of said segments comprises a number of positions; (b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer; (ii) receiving a value of a parameter of a rule vector pointed to by the second variable, wherein a third variable is set to the received value; (iii) setting a bit in the rule table to a logical “
1”
, wherein the bit is identified by a row pointed to by the second variable, at a segment pointed to by the third variable, and in a position pointed to by the first variable;(iv) increasing the value of the second variable by one; and (v) while the value of the second variable is smaller than the number of rows, going to and continuing processing from operation (ii); (c) comparing a received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54)
-
-
55. A computer-implemented method for checking a rule table having stored rule vectors, the method comprising:
-
(a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, and wherein each of said segments comprises a number of positions; (b) comparing a received data vector to at least one stored rule vector, wherein said comparing comprises; (i) utilizing a first variable as a row counter, a second variable as a parameter pointer, and a third variable as a segment pointer; (ii) receiving a value of a rule vector parameter pointed to by said second variable, wherein said third variable is set to said received value; (iii) performing a logical AND operation between said second variable and an identified segment in the rule table, wherein the identified segment is in a row pointed to by said first variable, and at a segment pointed to by said third variable; (iv) setting said second variable to the result of the logical AND operation; (v) incrementing the value of said first variable by one; and (vi) while the value of said first variable is smaller than the number of rows, going to and continuing processing from operation (ii); and (c) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70)
-
-
71. A computer-implemented method for checking an modified rule table, the method comprising:
-
(a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, wherein each of said segments comprises a number of positions, and wherein at least one of said segments comprise a “
don'"'"'t care”
segment that identifies a “
don'"'"'t care”
state;(b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer; (ii) receiving a value of a parameter of the rule vector pointed to by said second variable, wherein said third variable is set to the received value; (iii) if a value of said third variable is a “
don'"'"'t care”
designator, setting a bit pointed to by said first variable in said “
don'"'"'t care”
segment to a logical “
1”
;
otherwise, setting a bit in another segment of said rule table to a logical “
1”
, wherein the bit is identified by a row pointed to by said second variable, at a segment pointed to by said third variable, and in a position pointed to by said first variable;(iv) increasing the value of said second variable by one; and (v) while the value of said second variable is smaller than the number of rows, going to and continuing processing from operation (ii); (c) comparing a received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (72, 73, 74, 75, 76, 77, 78, 79)
-
-
80. A computer-implemented method for checking an extended rule table having parameters with a range of values, the method comprising:
-
(a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, wherein each of said segments comprises a number of positions; (b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer, (ii) receiving a value of the parameter of said rule vector pointed to by said second variable, wherein said third variable is set to said received value; (iii) wherein, if the received value is a range of values, then the method further comprises; updating a cross reference table with a new sub-rule number for each value in the range of values, including recursive access if necessary; and setting a bit in the rule table to a logical “
1”
, wherein the bit is in a row pointed to by said second variable, at the segment pointed to by a current value of said third variable, and in a position pointed to by said first variable, wherein said setting is repeated while cycling through the range of values;(iv) increasing the value of said second variable by one; and (v) while the value of said second variable is smaller than a number of rows, going to and continuing processing from operation (b) (ii); (c) comparing a received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (81, 82, 83, 84, 85, 86)
-
-
87. A computer-implemented method for checking a modified rule table having parameters with a range value, the method comprising:
-
(a) providing a two dimensional rule table having a number of rows, wherein each of said rows comprises a number of segments, wherein each of said segments comprises a number of positions; (b) storing rule vectors in said rule table, wherein said storing comprises; (i) utilizing a first variable as a rule number position pointer, a second variable as a row counter, and a third variable as a segment pointer; (ii) receiving a value of the parameter of said rule vector pointed to by said second variable, wherein said third variable is set to said received value; (iii) wherein, if a value of the parameter of the rule vector pointed to by said second variable is a single value, then setting both said third variable and a fourth variable to the value of the parameter;
otherwise, if the value of the parameter of the rule vector is a range of values, then setting said third variable to a low value of the range of values, and setting said fourth variable to a high value of the range of values;(iv) setting a bit in the rule table to a logical “
1”
, wherein said bit is identified by a row pointed to by said second variable, at a segment pointed to by said third variable, and in a position pointed to by said first variable;(v) increasing the value of said third variable by one; (vi) while the value of said third variable is not larger than the value of said fourth variable going to and continuing processing from operation (iv); (vii) increasing the value of said second variable by one; and (viii) while the value of said second variable is smaller than the number of rows, going to and continuing processing from operation (iii); (c) comparing said received data vector to at least one of the stored rule vectors; and (d) returning a rule number indicator if a match is found between said received data vector and at least one of the stored rule vectors. - View Dependent Claims (88, 89, 90, 91)
-
Specification