更新分离的多线程规则匹配算法  

An Update-separated Multi-thread Matching Algorithm

作　　者：李逸飞 王劲林[1,2] 陈晓 吴京洪[1,2] LI Yifei;WANG Jinlin;CHEN Xiao;WU Jinghong(National Network New Media Engineering Research Center,Institute of Acoustics,Chinese Academy of Sciences,Beijing,100190,China;University of Chinese Academy of Sciences,Beijing,100049,China)

机构地区：[1]中国科学院声学研究所、国家网络新媒体工程技术研究中心,北京100190 [2]中国科学院大学,北京100049

出　　处：《网络新媒体技术》2022年第6期10-14,47,共6页Network New Media Technology

基　　金：中国科学院C类战略性科技先导专项课题:SEANET技术标准化研究与系统研制(编号:XDC02070100)。

摘　　要：随着网络技术的不断发展,人们对于网络设备的要求也不断提升。在新兴的软件定义网络中,数据平面的网络性能则由交换机性能决定。软件定义网络中,交换机功能基于匹配动作表实现,匹配算法则决定了交换机处理数据包的性能。现有的掩码匹配实现方式往往难以兼顾匹配性能与更新性能,同时大多数匹配算法更新时均会造成查询中断,规则更新对于查询性能有着较大的影响。本文在现有算法基础上结合多线程处理思路,设计了新的匹配算法,即更新、匹配并行的多线程规则匹配算法。我们将匹配算法分为更新模块以及查询模块,通过将匹配工作与更新工作分离的方式,减小了更新工作对于匹配工作的影响。根据实验结果,改进算法将更新工作造成的匹配中断时间从毫秒级降低到微秒级,最大减少了约4个数量级。With the continuous development of network technology,people's requirements for network devices are also constantly improving.In the emerging software-defined network,the network performance of the data plane is determined by the switch performance.In the software-defined network,the switch function is implemented based on the match-action table,and the matching algorithm determines the performance of the switch to process data packets.The existing mask matching implementations are difficult to take into account both the matching performance and the update performance.And in most matching algorithms,the query will be interrupted during updating.Rule updating has a great impact on the query performance.Therefore,this paper designed a new matching algorithm based on the existing algorithm and the idea of multi-thread processing,put forward a multi-thread rule matching algorithm with updating and matching in parallel.We divide the matching algorithm into an update module and a query module.By separating the matching work and the update work,the impact of the update work on the matching work is reduced.According to the experimental results,our improved algorithm reduces the matching interruption time caused by update work from milliseconds to microseconds,and the maximum reduction is about 4 orders of magnitude.

关 键 词：软件定义网络 流表 匹配算法 更新优化 多线程 

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