Data packet filtering

A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

• computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,
• storing said data structures,
• finding, in said data structures, rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and
• finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

• determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row,
• observing a first element in a first row of a first column and comparing the first element to the respective row label,
• if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and
• proceeding on the basis of the second element and the respective row label in the same way as with the first element, and
• repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

A method for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, said method comprising the steps of:

• computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row,
• observing a first element in a first row of a first column and comparing the first element to the respective row label,
• if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and
• proceeding on the basis of the second element and the respective row label in the same way as with the first element, and
• repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

A method for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and the method comprising the steps of:

• determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set,
• computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and
• finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 in the low level result sequence indicating the rule matching the data packet.

A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

• a third mechanism for computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,
• memory for storing said data structures,
• a first mechanism for finding in said data structures rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and
• a second mechanism for finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

• a first mechanism for determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• a fourth mechanism for computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row, and
• a second mechanism for observing a first element in a first row of a first column and comparing the first element to the respective row label, which second mechanism is adapted
• if the element is equal to the row label, to jump to another column in the same row and to observe a second element found therein, or otherwise to jump to the row indicated by the first element and to observe a second element found in a column therein, and
• to proceed on the basis of the second element and the respective row label in the same way as with the first element, and wherein
• the second mechanism is further adapted to repeat the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

A network element comprising functionality for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, said network element comprising:

• a fourth mechanism for computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row, and
• a second mechanism for observing a first element in a first row of a first column and comparing the first element to the respective row label, which second mechanism is adapted
• if the element is equal to the row label, to jump to another column in the same row and to observe a second element found therein, or otherwise to jump to the row indicated by the first element and to observe a second element found in a column therein, and
• to proceed on the basis of the second element and the respective row label in the same way as with the first element, and wherein
• the second mechanism is further adapted to repeat the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

A network element comprising functionality for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the network element comprising memory for the rule base, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and said network element comprising:

• a first mechanism for determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• a fourth mechanism for computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set, and
• a second mechanism for computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and for finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 indicating the rule matching the data packet.

A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

• computing, for each parameter field in the rule base, a data structure indicating different values or value ranges of the parameter field and, for each different value or value range, a rule set of the rules, to which said value or value range can match,
• storing said data structures,
• finding in said data structures rule sets for the data packet, said rule sets being the rule sets corresponding to the parameter field values of the data packet, and
• finding the rule with the smallest label that is present in all said rule sets of the data packet, said rule with the smallest label indicating the rule matching the data packet.

A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

• determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• computing a table for the combination of the rule sets of the data packet, the rows of the table corresponding to the labels of the rules in the rule base, and the columns of the table corresponding to the different rule sets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of a rule of the respective rule set and equal to or larger than the label of the respective row,
• observing a first element in a first row of a first column and comparing the first element to the respective row label,
• if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and
• proceeding on the basis of the second element and the respective row label in the same way as with the first element, and
• repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row or said equal element indicating the rule matching the data packet.

A computer program product, containing computer program code for finding an element with the smallest label that is present in a plurality of finite subsets containing finite number of elements, said subsets being subsets of a set containing finite number of sequentially labelled elements, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

• computing a table for the plurality of finite subsets, the rows of the table corresponding to the labels of the elements of the set, and the columns of the table corresponding to the different subsets, and the cells of the table being filled so that each cell contains an element, which is the smallest possible label of an element of the respective subset and equal to or larger than the label of the respective row,
• observing a first element in a first row of a first column and comparing the first element to the respective row label,
• if the element is equal to the row label, jumping to another column in the same row and observing a second element found therein, or otherwise jumping to the row indicated by the first element and observing a second element found in a column therein, and
• proceeding on the basis of the second element and the respective row label in the same way as with the first element, and
• repeating the steps of observing, comparing and jumping until a row containing equal elements in all columns or the last row of the table is found, the label of said row indicating the element with the smallest label that is present in the plurality of subsets.

A computer program product, containing computer program code for finding, in a rule base, a rule matching a data packet, a data packet comprising parameter fields for identifying the data packet, the rule base comprising a plurality of sequentially labelled rules, each rule comprising one or more parameter fields, and a rule matching a data packet being a rule, whose parameter field values correspond to the parameter field values of said data packet, and wherein executing said computer program code in a computer causes the computer to execute the steps of:

• determining rule sets for the data packet, one rule set comprising the rules to which one parameter field value of the data packet can match,
• computing low level bit sequences for the data packet, each low level bit sequence corresponding to one rule set in the combination of the rule sets of the data packet, each bit of a low level bit sequence corresponding to one rule in the rule base, and a bit in a low level bit sequence being set to 0, if the corresponding rule is not present in the corresponding rule set, and a bit in a low level bit sequence being set to 1, if the corresponding rule is present in the corresponding rule set,
• computing bitwise AND for said low level bit sequences of the data packet for obtaining low level result sequence, and
• finding, in said low level result sequence, the first 1 starting from the beginning of the low level result sequence, the position of said first 1 indicating the rule matching the data packet.