A Flow Adaptive Multi-Dimensional Packet Classification Algorithm

The most important function of the data plane in software defined network (SDN) is to classify packets by using tens of packet header fields, namely multi-dimensional packet classification, which is highly extended from the most commonly used five-tuple fields in the contemporary packet classification. The number of dimensions is still increasing with the development of SDN. In this paper, we analyzed the drawbacks of the classification algorithms directly extended from five-tuple packet classification and surveyed the existed algorithms used in practical systems, such as Open vSwitch. Then we presented a flow adaptive algorithm based on bit vector for multi-dimensional packet classification, especially designed for tens of header fields. This algorithm first classifies packet against each header field separately, correlates them and optimizes the search speed by dynamically re-order different fields, and then intentionally skips some wildcard fields according to the locality of traffic flow. The packet classification on different header fields may exploit specific design algorithm according to different matching methodologies of header fields. Experimental results on the Open vSwitch platform, which is an implementation of OpenFlow protocol in SDN, show that the proposed algorithm achieves about two times speedup in user mode than the current algorithm in Open vSwitch, and over 40% speedup than other algorithms directly extended from five-tuple classifications.