基于MTF启发法的OpenFlow虚拟流表高效查找算法

Efficient Lookup of Virtual OpenFlow Table Based on Move-to-front Heuristics

OpenFlow软件交换机由于成本低、配置灵活、且便于调度部署,因而广泛应用于软件定义网络试验床的构建,但在应用过程中遭遇到严重的性能瓶颈,流表查找是其中的关键一环.为此,本文应用启发式策略,提出一种面向软件交换机的OpenFlow虚拟流表高效查找算法.首先分析指出掩码遍历是影响流表查找性能的关键因素,进而基于网络流量局部性特点,应用M TF(M ove-To-Front)启发法自适应调整掩码顺序,以加快后续数据包的掩码查找命中速度.最后,借助实际网络流量样本,对本文所提算法的查找性能进行了实验评估.实验结果表明:本文所提算法的平均查找长度明显小于目前主流软件交换机中的流表查找方法,加快了OpenFlow流表查找速度,有效提升了OpenFlow软件交换机的数据转发性能.

OpenFlow software switches are extensively employed in the construction of software-defined network test bed due to their low costs, flexible configuration, and convenient deployments. When it comes to practical deployments, OpenFlow software switches are faced with heavy performance bottlenecks, where flow table lookup is a key step. This paper is thus motivated to propose an effi- cient lookup algorithm for virtual OpenFlow flow tables by applying a heuristic strategy. Firstly, we point out that mask traversals have a critical impact on the lookup performance of virtual flow tables. Then, the move-to-front heuristic is applied to self-adaptively adjust mask sequence by utilization of network traffic locality, which aims to accelerate the hit speed of mask lookups for subsequent packets. Finally, we evaluate the lookup performance of our proposed algorithm in virtue of real network traffic traces by experiments. The experimental results indicate that our proposed algorithm has a lower average search length than the flow table search methods in prevalent software switches, which speeds up flow table lookups and promotes the data forwarding of OpenFlow software switches effectively.