Novel disjoint graph based algorithm for multi-field range-based packet classification

Packet classification is necessary for flow-based network services in Internet routers, such as NAPT, IPsec, ACL, etc. The range-based packet classification function maps input packets to the highest-priority matching rule in a given rule set specified by ranges (P. Gupta and N. McKeown, August 1999, March-April 2001). For instance, multi-field range-based packet classification maps IP packets to security policy rules in an IPsec gateway. The FIS trees based packet classification algorithm has been proposed as a software implementation option of this function. In this paper, we present a novel disjoint graph based algorithm for multi-field range-based packet classification. The novel algorithm constructs a disjoint graph using elementary interval trees and disjoint interval trees for a given rule set, where only a single path traversal is required during a search to classify a packet. Experimental results show that the disjoint graph based packet classification algorithm significantly outperforms the FIS trees based solution. In a network processor implementation with an input rule set of 700 rules, the disjoint graph based packet classification algorithm requires only 45% of the search time, 69% of the data structure buildup time, and 47% of the memory storage of the FIS trees based solution.