Transforming a Set of Network Classification Rules Into an Equivalent Non-Intersecting Set

Publishing Venue

IBM

Abstract

Most of the networking application deal with the issue of packet classification. This is done by providing a set of rules consisting of tests (conditions) and action. For a packet which satisfy a condition of a rule the corresponding action is perform. A common problem arise when a packet satisfy more then one rule. In this case we say the the rules intersect and we need to determine which of the actions should be perfomed. A solution to this problem is to define a priority among the rules and decide on the action based on the priority. This makes the updates to the rule set quite complex. The invention offers an alternative solution which involves the replacing of the whole rule set by an equivalent set of non-intersecting rules. This problem has been identified and currenly it is solved usually by using the order of the rules as their priority. There is no reference to the issue of managing the rules intersections.

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

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...