Method for preparing a decision tree for packet processing

• US 20050278454A1
• Filed: 03/28/2003
• Published: 12/15/2005
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Rambus Inc.
• Original Assignee: SSH Communications Security Corp. (SSH Communications Security Oyj)
• Inventors: Oksanen, Kenneth
• Granted Patent: US 7,548,992 B2
• Time in Patent Office: Days
• US Class Current: 709/232
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/12 Protocol engines

Abstract

The invention relates to methods for processing data packets according to a set of rules, and especially for preparing of decision trees for selecting the correct rule for processing of a data packet. In preparation of a decision tree, a splitting point within a dimension being studied is chosen as follows. The rules are sorted to allow monotonous iteration through all range end values specified in the rules in the dimension being studied. The range end values are then iterated through in a monotonous fashion, either increasing or decreasing. At each iteration, the number of range low end values and the number of range high end values being equal to the current iteration value is counted. From these counts and the accumulated results from the corresponding counts in previous iterations, the numbers of rules with ranges in different positions relative to the current iteration value are deduced, and from these values, the goodness of the iteration value is calculated. After iteration of all range end values within the studied dimension, the iteration value with the best goodness is selected.

Claims

1. Method for selection of a splitting point value for use in preparation of a decision tree on the basis of a set of packet processing rules for processing data packets, comprising at least the steps of

selecting a splitting point candidate value from a set of rule parameter range end values in the parameter dimension being studied,

changing a first counter for each rule with a first range end value being equal to said selected candidate value,

changing a second counter for each rule with a second range end value being equal to said selected candidate value, and

computing a goodness value for said selected candidate value at least partially on the basis of the values of said first and second counters.

2. A method according to claim 1, further comprising at least the step of

repeating the steps recited in claim 1 for each unique value in a monotonous sequence in said set of rule parameter range end values.

3. A method according to claim 1, further comprising at least the step of representing the relation of rules in comparison with a splitting point candidate by

a first value representing the number of rules whose both range end values are below the splitting point candidate,

a second value representing the number of rules whose low range end value is smaller than the splitting point candidate but whose high range end value is equal to the splitting point candidate,

a third value representing the number of rules whose low range end value is equal to the splitting point candidate but whose high range end value is larger than the splitting point candidate,

a fourth value representing the number of rules whose low range end value is lower than the splitting point candidate but whose high range end value is larger than the splitting point candidate, and

a fifth value representing the number of rules whose both range end values are higher than the splitting point candidate.

4. A method according to claim 1, further comprising at least the step of representing the relation of rules in comparison with a splitting point candidate by

a sixth value representing the number of rules having a point value in the studied dimension.

5. A computer program for processing data packets according to a set of rules, comprising at least

program instructions for selecting a splitting point candidate value from a set of rule parameter range end values in the parameter dimension being studied,

program instructions for changing a first counter for each rule with a first range end value being equal to said selected candidate value,

program instructions for changing a second counter for each rule with a second range end value being equal to said selected candidate value, and

program instructions for computing a goodness value for said selected candidate value at least partially on the basis of the values of said first and second counters.

6. A computer program according to claim 5, embodied on a record medium.

7. A computer program according to claim 5, stored in a computer memory.

8. A computer program according to claim 5, embodied in a read-only memory.

9. A computer program according to claim 5, carried on an electrical carrier signal,

10. An electronic device for processing of data packets according to a set of rules, comprising at least

selecing means for selecting a splitting point candidate value from a set of rule parameter range end values in the parameter dimension being studied,

first changing means for changing a first counter for each rule with a first range end value being equal to said selected candidate value,

second changing means for changing a second counter for each rule with a second range end value being equal to said selected candidate value, and

computing means for computing a goodness value for said selected candidate value at least partially on the basis of the values of said first and second counters.

11. An electronic device according to claim 10, wherein the device is an integrated circuit.

12. An electronic device according to claim 10, wherein the device is a computer.

13. An electronic device according to claim 10, wherein the device is an IPsec node.

14. An electronic device according to claim 10, wherein the device is a firewall node.