流量自适应的多维度包分类方法研究  

A Flow Adaptive Multi-Dimensional Packet Classification Algorithm

作　　者：万云凯 嵩天[1] 刘苗苗[1] 刘翼[1,2] 李丹[3] 

机构地区：[1]北京理工大学计算机学院,北京100081 [2]延安大学网络信息中心,陕西延安716000 [3]清华大学计算机科学与技术系,北京100084

出　　处：《计算机学报》2017年第7期1543-1555,共13页Chinese Journal of Computers

基　　金：国家自然科学基金(61272510;61432002;61522205);陕西省教育厅科学研究项目(14JK1825)资助~~

摘　　要：以软件定义网络为代表的新兴网络技术发展使得包分类不再局限于传统的五元组而是面向更多维度,以开放协议OpenFlow为例,网络包分类需要针对几十个维度,并且维度数量在持续增加,这种多维度包分类功能成为了软件定义网络实际应用中的性能瓶颈.该文分析了五元组包分类算法向更多维度扩展的局限性,利用网络流的局部性原理,提出了一种流量自适应的多维度包分类方法.该方法可以根据网络流量的实时分类结果动态调整多维度匹配顺序,优先匹配当前流量所需要的字段,通过忽略通配字段达到优化查找速度的目的.同时,该方法将多维度字段分组,结合具体字段类型选择最优匹配算法.在Open vSwitch中增加所提出方法,实验结果表明,该方法相比已有的包分类算法在用户态模式下性能提高约2倍,相比从五元组包分类算法扩展的方法性能提高40%以上.The most important {unction 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 speedupin user mode than the current algorithm in Open vSwitch, and over 40~ speedup than other algorithms directly extended {rom five-tuple classifications.

关 键 词：包分类 软件定义网络 流量自适应 位向量 OpenFlow 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]