Page 1 of 4
Transforming a Set of Network Classification Rules Into an Equivalent Non-Intersecting Set
The most common problem in networking program is that of classification.
Given a packet p we perform tests on its header and based on the test result we decide on the action to perform. The tests are performed on the header fields which depending on the networking protocol can be source IP, destination ip, source port, destination port, etc.
Each of this test and the corresponding action is actually a classification rule. Each field is called a coordinate and the number of fields is the dimension of the rule.
A packet satisfies a rule if it satisfies the rule tests. We consider two types of tests:
≤≤lx1. Interval test which have the form h where x is the tested field l,h are constants (the interval endpoints.
2. Mask&value test which has the form x&m=v x is the tested field m the mask and v the value.
It can happen that a packet satisfies more than one rule; in such a case we say that the rules, which the packet satisfies, intersect. To determine which action is to be performed we define a priority relation φ and require that intersecting rules are related by this priority. The action of the highest priority rule is chosen.
For a set of rules R and a packet p we define the action of R on p to be the action of the highest priority rule in R which p satisfies.
Two sets of rules are equivalent if they perform the same action for every packet.
Handling rules with intersection complicates a networking program. In this patent we present an algorithm for transforming a set of rules into an equivalent non-intersecting set.
Algorithm 1 Interval labeling. We start with a set of one-dimensional Rules R.
1. Set S as an empty set of rules.
2. Sort all the endpoints in the intervals which are the rule conditions
3. Set q to be the smallest lower endpoint. Mark it as checked. Let t be the next endpoint.
4. Add to S all rules for which q is the low bound of their interval.
5. Remove from S all rules for which q is the high end of their interval.
6. Label the interval starting with q and ending with t by the names of all rules in
S.
7. If there are more unchecked lower endpoints set q as smallest unchecked point and continue with step 4
8. Remove all unlabeled intervals
9. End
We say that a set of rules is non-intersecting if no two rules in the set intersect.
Algorithm 2 Non-intersecting rules for 1 dimensional interval rules. We start with a consistent set of rules R and generate an equivalent set of rules R' of
Page 2 of 4
non-intersecting rules.
1. Perform algorithm 1 denote by S the resulting set of labeled interval.
2. Set R' as empty.
3. For each labeled interval add to R' a rule such that the rule condition is the interval and the action is the action of the rules with the highest priority that labels it.
Algorithm 3 Equivalent non-intersecting rules for a given set R of interval rules.
1. For each coordinate perform algorithm 1. Denote the resulting sets of...