多核处理器 [基于多核处理器的L7-Filter规则匹配改进算法]

　　摘要:针对多核处理器的体系结构和网络数据流在时间上的局部性特点,提出了一种基于多核处理器的分链动态适应算法。该算法通过对网络数据流进行类型分类并根据网络数据流的时间局部性对规则链进行动态优化,从而有效减少了多核处理器下L7-Filter对网络数据流的匹配次数,显著提升了规则匹配效率。仿真实验结果表明:在网络数据包个数相同条件下,所提算法在性能上约有7%的提高。随着网络数据包个数的增加,性能优越性更加明显。
　　关键词:多核处理器;网络数据流;L7-Filter;时间局部性;数据包分类;动态优化
　　中图分类号: TP301.6;TP393.02文献标志码:A
　　Improved L7-Filter�s pattern matching algorithm based on multi-core processors
　　英文作者名YU Tao*, WU Wei-dong
　　英文地址(College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan Hubei 430065, China)
　　Abstract: According to the architecture of multi-core processors and the temporal local characteristics of network data flow, a division and dynamic adaptation algorithm was proposed based on multi-core processors. Classifying network data flow by the type and optimizing chain of rules dynamically by the temporal locality of network flow, the count of the multi-core�s L7-Filter matching network data flow were reduced effectively and the processing efficiency was improved dramatically. The simulation result shows that given the number of packets in the same conditions, the algorithm has about 7 percent improvement of the multi-core processing performance. With the increasing number of network packets, the performance superiority becomes more obvious.
　　Key words: multi-core processor; network data flow; L7-Filter; temporal locality; packet classification; dynamic optimization
　　0引言
　　随着网络爆炸式的增长以及高速以太网的出现(如10GbE),网络流量也随之高速增长,这就对网络服务质量(Quality of Service, QoS)[1]提出了更高的要求。传统的数据包分类技术主要是基于数据包头部信息做出分类决策。然而,当前的许多网络应用会有意或无意利用头部信息隐藏真实的行为,如对等网(Peer-to-Peer, P2P)和超文本传输协议(HyperText Transfer Protocol, HTTP)，它们会在连接建立的过程中通过动态分配端口号等方式来调整IP头部信息。
　　L7-Filter是Linux上QoS框架的一个重要组件。它区别于传统的基于数据包头部信息的分类方法,采用了深度数据包检测(Deep Packet Inspection, DPI)[2]技术,是基于应用层数据来对数据包分类从而提高网络服务质量。单核心处理器下的L7-Filter无论是在处理性能还是硬件资源利用率上效果都很理想。
　　然而随着网络服务器中多核处理器的大规模部署[3],多核处理器下的L7-Filter并没有表现出应有的性能提升。针对这些问题,文献[4]提出基于接收端调节(Receive Side Scaling, RSS)[5]技术的核心绑定技术,很好地解决了多核处理器上因多核心计算迁移所产生的Cache一致性问题[6],提高了多核处理器下的L7-Filter数据包分类处理性能。但是,这种方法在具体到每一个匹配核心上采用的仍然是传统的线性搜索查找算法,时间复杂度为O(n),最坏情况下要匹配N×d次计算才可以得出分类结果（其中N为规则条数,d为规则维数），这种方法在时间效率方面存在固有的缺陷。文献[7]提出的对规则集动态优化只对规则集本身进行探讨,但却没有充分考虑网络数据流本身的特性。文献[8]虽然介绍了一系列规则集优化算法来提高核心的处理性能,但存在实现复杂度较高等问题。
　　本文利用网络数据流在时间上的局部性特点,并结合多核处理器的特性,对网络数据包分类算法进行改进,提出了一种基于多核处理器的分链动态适应算法(简称DDA算法)。
　　1L7-Filter
　　L7-Filter是基于网络应用层数据对数据包分类的方法。核心思想是利用正则表达式搜索的方法[9]对目标数据包的应用层数据进行搜索并分类,然后将分类的结果交给系统上层为服务质量作进一步处理,如带宽分配等。多核处理器下的原始L7-Filter体系结构如图1所示。
　　文献[4]提出的核心绑定技术中采用了RSS技术。利用这种技术,在一个CPU核心上绑定预处理线程,如图1中的①。该线程主要做包括数据包在多处理器核心上的调度等工作。预处理核心在把数据包向匹配核心调度时的单位是以单个连接为单位的。系统其余的每个处理核心上都绑定一个数据包分类线程,如图1中的②。
　　这种利用RSS技术的方法很好地解决了由操作系统对负载强制调度及负载均衡调度带来的CPU核心间Cache拷贝产生的对L7-Filter性能影响的问题。
　　然而,文献[4]的改进算法具体到每个匹配线程(核心)时,采用的是将规则以正则表达式的方式描述并将所有的规则组织成一条规则链表。每当对一个数据包做匹配操作时,就线性地从规则链头搜索到链尾,明显地存在着效率不高的弱点。另一方面,在数据包分类处理中也没有充分利用规则链本身的特性以排除肯定不符合的匹配操作,这样就会无故地增加核心的计算次数从而浪费CPU资源。特别是当网络流量比较大时,这两点不足更加明显。
　　通过分析传统的查找算法,可以归纳出它具有以下两点关键特征:1)待查找的数据有明确的值大小,从而确立与比对目标值的大小关系;2)比对目标之间存在着明确的值大小关系以建立查找模型,如二分查找树等。
　　图片图1L7-Filter数据流程
　　然而在L7-Filter模型中,规则采用的是正则表达式串,其本质上是一个字符串,数据包也是如此,这两者都不具备上述两个关键特征。基于这样的事实,决定了传统的查找算法已不再适合L7-Filter的模型。
　　第3期 余涛等:基于多核处理器的L7-Filter规则匹配改进算法计算机应用 第32卷2DDA算法模型
　　2.1时间流指数
　　在L7-Filter体系结构中,对内核网络栈的数据包的调度是以连接为基本单位的,定义1给出了连接的定义。
　　定义1连接是由数据包的传输层协议、源地址、源端口、目的地址、目的端口组成的唯一字符串,其特性有:1)区别传统连接的概念,即不以TCP和UDP来划分是否为连接;2)连接不区分方向性,即源地址、源端口和目的地址、目的端口的地位是对等的,如图2所示。
　　
　　根据定义1易知,conn1和conn5是同一连接,由于conn1和conn2在协议上不同,所以不是同一连接,其他同理。
　　另外,通过对实际网络流量的观察以及对入侵检测数据集MIT DARPA 2000[10]的统计分析得出互联网流量在一定的时间内表现出一定的局部性。
　　这种局部性可以通过定义1连接的概念对网络数据流进行统计并计算其时间流(Time-Flow, T-F)指数以获得定量分析。定义2给出T-F指数的定义。
　　定义2T-F指数。在单位时间t内,流经该网络设备接口j上的流量均值f与该设备上的路由条目数均值ε和该设备上活动端口平均数乘积的比值,T-F指数可由式(1)计算:
　　F(j)=1tn∑nj=0f(j)ε(j)*p(j)(1)
　　其中: f(j)、p(j)和ε(j)分别表示单位时间t内,网络设备j上流量均值、路由条目均值和该设备使用中活动端口均值;n为该网络设备上物理网卡的总数。
　　通过文献[11]及T-F指数的计算易知,这种流量的局部性表现在:在一段时间范围内,适用于同一网络应用协议的流量比较集中,这些流量在数据包规则匹配上的表现就是频繁地命中某一小部分特定规则。
　　2.2Linux的Slab层技术及多处理器核心亲和性
　　多核心处理器的亲和性[12]是指在处理器核心计算过程中,相关的任务尽可能地位于同一核心进行计算,这样就可以减小进程迁移使数据在核心间拷贝所带来的负载。实现进程固定于某一特定CPU的技术叫CPU硬亲和力。在Linux 2.6内核中,通过内核提供的接口可以很容易地把进程(或线程)固定在某个特定的处理器核心上运行。
　　在Linux内核实现中实现了一种叫作Slab[13]层的技术。该技术主要是为了减少数据对象频繁高速地分配和回收对系统性能的影响,其思想是让内核把不同对象分为不同的高速缓存组,每个组中都只包含一种对象,每种对象也仅只对应一个高速缓存组。利用内核所提供的任务与核心绑定接口将每个高速缓存组绑定到一个固定的核心上,这样就可以解决在多核处理器上操作系统对任务强制调度和负载均衡所带来的Cache一致性问题。
　　另外,由于受到对象数据缓存组大小的限制,网络中的一个数据包可能会被划分为几小段以连接的方式存放在对应的对象数据缓存组中,这样就使得对一个数据包的匹配分类可能需要进行几个阶段,最后的结果由这几次计算的结果综合得到。这时基于连接的网络数据包对象数据缓存组使得核心每次处理时都是处理来自同一连接的数据包(段),而核心绑定技术的思想又可以保证同一连接的数据包(段)都尽量只在一个处理核心上进行计算,通过这两个处理就很好地解决了在多核处理器上由于操作系统对任务强制调度和负载均衡所带来的Cache一致性问题。
　　本文中以式(1)计算的T-F指数和Linux下的Slab层技术为理论基础,结合多核心绑定技术为每一个核心绑定一个数据包匹配线程,而被固定的每个线程都对应一个数据资源链表,该链表即为Slab层技术中的对象数据缓存组,存放的是来自内核网络栈中钩子函数所发送过来的网络数据包。
　　2.3DDA算法实现
　　基于2.1节的T-F指数和2.2节的Slab层技术的理论基础,给出基于Linux下的Slab技术和多处理器核心亲和性的新L7-Filter体系结构如图3所示。
　　在图3所示的DDA算法核心中主要分为两个步骤:1)数据包在多核心上调度分配,见图3中的①;2)处理核心规则链动态适应,见图3中的②。
　　图片图3基于DDA算法的L7-Filter体系结构
　　2.3.1多处理核心数据包分链(DIV)算法
　　在图3的第①步中,当有网络流过来时,通过内核钩子程序就可以很容易地以固定字节大小的形式获取网络流中的数据包。然而，不足在于文献[2]中并没有充分利用网络流中的数据包的运输层协议特性。因为规则链中的规则可以根据将要匹配成功的数据包的运输层协议对其进行分类,而网络流中的数据包也可以基于运输层特定性进行分类。经过这样的分类后这样就可以明显减少匹配次数。对数据包和规则分类前后如图4所示。
　　图片图4数据包及规则链分类
　　从图4(a)可发现,从网络流来的数据包无论是TCP类还是UDP类都要经过处理器核心中规则链的所有规则处理,而规则链中TCP类规则不可能和UDP类数据包匹配成功,同理易知其他情况。这样就浪费了处理器的处理时间。
　　而在图4(b)中,DIV算法的核心思想就是利用Libnids[14]库的不同回调函数对数据包按照运输层协议进行分类调度,同时对处理器核心中的规则进行分类,这样就可以保证TCP类的数据包只和TCP规则链中的规则进行匹配计算,UDP同理。
　　关于DIV算法的性能分析,本文作如下假设:在对数据包按运输层协议分类时,数据包Pi为TCP类数据包的概率为PTCP,为UDP类数据包的概率为PUDP。图4(a)的规则链长度为N,图4(b)中TCP规则链长度为NTCP,UDP规则链长度为NUDP,则N、NTCP和NUDP三者关系为:
　　
　　规则比较平均时。另外,无论是对数据包分类调度还是对规则链规则的分类都只是发生在系统初始化阶段,这部分工作对后续的规则匹配没有任何性能上的损失。
　　另外一个问题就是数据包在核心间的调度问题。数据包调度问题就是为数据包查找其所属连接队列的问题。对于一个系统而言,处理器核心数目较小且固定,当一个数据包从网络流中被调度出来后就提取数据包头部信息组成连接串(见定义1)并在核心间顺序查找对应的连接对象缓存组。同时每个连接对象缓存组都维护着自己特有的连接字符串。当两者连接字符串相同时就将数据包放入该连接对象缓存组,这个连接对象缓存组是匹配线程的数据资源,匹配线程又和核心绑定在一起,这样就完成了数据包在多核处理器上的调度过程。一旦在所有的处理核心上都找不到这样的连接对象缓存组时,就在负载较少的核心上新建这样一个对象缓存组并附接到负载较少核心的对象缓存组上。
　　2.3.2多处理核心规则链动态适应(MDYA)算法
　　从2.2节介绍的Slab层技术和核心亲和性可知,当利用核心绑定技术为多核处理器核心绑定一个数据包处理线程后,处理的过程如图3中的②。核心Core1和Core2共享一条规则链。通过具体分析每个处理器核心上数据包的分类过程发现:模式规则的匹配过程,本质上仍然是一个利用规则链线性查找对该数据包所属应用程序进行分类的过程,不同点在于这里采用了正则表达式的查找方式。
　　根据T-F指数的计算式(式(1))可知,网络数据流在一定的时间范围内表现出一定的局部性,即在一定时间内数据包隶属于同一网络应用协议(对应于规则链的规则)有较高的概率。所以MDYA算法的核心思想就是通过对规则进行基于规则权重因子的计算动态调整图4中(b)的规则链,规则权重因子较大的规则应尽量放在规则链的前面,这样就可以相对减少查找比较的次数。
　　MDYA算法提到的规则权重因子的计算需考虑3种因素:1)规则命中频率ρ,即规则近期被命中的概率(初始为0);2)命中时效性γ,即数据包命中规则距上次命中经历的时长(以未命中次数递增计,初始为0);3)规则当前位置值τ(初始值为以字典序构建规则树时获得的位置值,从1开始计)。规则权重因子计算公式如式(3)所示:
　　W(i)=「(nτi-γi)*ρi�(3)
　　其中:规则当前位置值τ越靠前其位置值较越小,最小值为1。当命中规则i时,ρi按照式(4)进行修正:
　　ρ(i)=(ρ(i)+1n)*F(j)(4)
　　其中F(j)为计算T-F指数。运用式(4)对ρi进行修正的原因是为了加快调整的速度，以使算法能尽可能快地产生效果。
　　基于规则权重因子的MDYA算法使得规则在链中局部模糊有序。简化模型如图5所示,在TCP规则链中,规则R1与规则R3满足如下关系式:
　　|W(R1)-W(R3)|>ε
　　其中:W(R1)是关于规则R1的权重因子计算函数(如2.3.2节式(3)所述),ε是相关于当前流经网络设备的网络连接数的权值。当相邻两条规则满足上述关系式,就预测R1在当前具有更高的访问权重,继而将该规则向前移动1位。
　　图片图5规则学习模型
　　在简化模型中,为了降低分析难度,假设ε的值取1,权重因子计算函数只计算访问频数。如简化模型中所述,在前N次数据包模式匹配操作中对N个规则的每一个规则Ri都访问了一次,这时每个规则的权重因子都为1。假设在接下来的N/2次规则匹配中都对规则Rn匹配成功,这使得规则Rn的权重因子变为N/2。由于这里ε的值为1,而过去的N/2次规则匹配操作中,其余的规则无一次命中,所以它们的权重因子都仍为1,这样就使得每次匹配成功后规则Rn在规则链中的位置相对向前移动一位。
　　递推易得:经过N/2次学习,规则Rn的位置就由规则链的最后一位移到了中间位置,同时这样的移位学习操作的结果是在每一步中进行,学习的结果立即就能被后面的规则匹配操作所利用。随着网络数据包的不断计算,规则链最终会逐步有序,最后在一定的时间内达到稳定。
　　另外,在多核处理器调度算法设计[15]中,并发与临界区加/解锁对数据的一致性和系统性能起着至关重要的作用。MDYA算法中,为了解决因每个处理器核心独享规则树带来的空间复杂度急剧增加(可能从1增加到n)的问题,采用每两个核心共享一棵规则树的方法。
　　MDYA算法核心思想中,采用的是将当前规则与其前面相邻一位(非全局)规则的权重因子进行比较(局部模糊有序)调整,同时每两个核心共享一条规则链,这样使得学习后的规则能立即在多处理器核心间进行共享优化结果并相互学习。MDYA算法的可行性在于:1)局部模糊有序操作的时间代价远远小于精确有序。就平均时间性能最佳的快速排序而言,每做一次规则匹配操作就意味着要消耗掉O(n log n)的时间用在规则精确排序上,这对于网络数据包规则匹配操作本身而言,是很大的时间消耗;2)计算出来的规则精确有序仅仅是对过去数据包计算出的T-F指数的一种体现,该指数对未来的数据包匹配有一定的指导意义,但这种意义并不是绝对的;3)在多核处理器中,若采用精确有序的排序操作将会使得对临界区资源加/解锁的频率变得异常频繁,这将严重影响多核处理器的处理性能。
　　在上述简化模型中,定义临界区为调整规则位置段,对临界区资源的访问采用GetLock和ReleaseLock这样的加/解锁的方式实现共享读和互斥写。
　　DDA算法正是结合DIV算法和MDYA算法。DDA算法可明显提升多核处理器的数据包匹配性能。下面给出DDA算法的流程。
　　算法基于多核处理器的分链动态适应DDA算法。
　　
　　3算法性能分析
　　3.1实验环境配置
　　软件环境为Linux 2.6.32内核,GCC版本是4.3.2;CPU是Intel Xeon系列四核心CPUX3350,主频为2.66GHz。实验中仿真网络数据流量采用的是入侵检测项目MIT DARPA数据集[10]。优化算法时间的测量采用的是在代码中硬编码(嵌入代码)的方法获得处理时间。
　　3.2算法执行时间分析
　　表1为实验结果统计表。在本次实验设计中,以8×104个数据包为单位,分了5组实验,每组实验进行10次,表1记录了10次实验测得的多核处理器的处理时间,最后对每组的统计结果求平均值。
　　3.2.1CPU执行效率分析
　　图6是CPU处理时间直方图,从中可看出:当数据包个数为8×104时,减少时间几乎为0,而随着数据包个数的增加,在处理时间上均有减少,而且减少的幅度是和数据包个数的增加成正比的。
　　图片图6CPU处理时间直方图
　　3.2.2算法性能提升分析
　　算法改进前后节约时间及提升百分比如表2所示。
　　表格(有表名)表2DDA算法性能提升统计表
　　数据包个数节约时间/s提升百分比/%8×1040.146 2.016×1041.017 6.224×1041.374 6.732×1042.060 8.240×1041.948 6.7
　　从表2可看出：当数据包个数增加到16×104以后,这时无论是节约的绝对时间还是提升的百分比,都有明显增加。当数据包个数达到40×104时,这是算法性能的提升率趋向于稳定。通过上面的分析可知,整个算法经历了规则初始学习(性能提升很少)、规则学习逐步完成(性能提升明显)、规则学习逐步稳定(性能提升稳定)的过程。
　　4结语
　　本文对L7-Filter的工作机制做了简要介绍,并说明了文献[4]对传统单核服务器上L7-Filter的改进方法及存在的不足。通过规则所采用的运输层协议对规则链进行分类,具体到每条规则链上利用网络数据流的流量统计模型与动态适应相结合的方法使得规则局部有序。在实验论证的基础上,证明了这种改进的模式匹配算法在CPU利用率和数据包的处理性能上的优越性。同时,由于整个规则的学习需要大规模网络流量的支持,所以本文算法在网络流量较小的情况下性能不理想,甚至较以往有一定的损耗,这部分损耗主要是核心间为了互斥并发访问规则链所带来的加/解锁操作。另外,为了降低核心间互斥并发访问规则链所带来的加/减锁操作影响,需要使每两个核心共享一条规则,这相对于改进前全局公用一条规则链而言,增加了算法的空间复杂度。以上两点的不足,也正是以后研究的一个重点。
　　参考文献:
　　[1]林闯,王元卓,任丰原. 新一代网络QoS研究[J]. 计算机学报,2008,31(9);1525-1535.
　　[2]KUMAR S, TURNER J, WILLIAMS J. Advanced algorithms for fast and scalable deep packet inspection[C]// Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking And Communications Systems. New York: ACM Press, 2006: 81-92.
　　[3]曹折波,李青. 多核处理器并行编程模型的研究与设计[J].计算机工程与设计,2010,31(13);2999-3003.
　　[4]GUO DANHUA, LIAO GUANGDENG, BHUAN L N. A scalable multithreaded L7-Filter design for multi-core servers [C]// Proceedings of the 4th ACM/IEEE Symposium on Architecture for Networking and Communications Systems. New York: ACM Press, 2008: 60-68.
　　[5]Windows Hardware Development Center. Receive Side Scaling(RSS) [EB/OL].[2011-10-20].http://msdn.省略/en-us/windows/hardware/gg463253.aspx.
　　[6]所光,杨学军. 多核处理机系统Cache管理技术研究现状[J]. 计算机工程与科学,2010,32(7):65-68.
　　[7]WALDVOQEL M. Multi-dimensional prefix matching using line search [C]// Proceedings of the 25th Annual IEEE Conference on Local Computer Networks. Washington, DC: IEEE Computer Society, 2000:200-207.
　　[8]HAMED H, AL-SHAER E. On autonomic optimization of firewall policy organization [J]. Journal of High Speed Networks,2006,15(3):209-227.
　　[9]丁晶,陈晓岚,吴萍. 基于正则表达式的深度包检测算法[J]. 计算机应用,2007,27(9):2184-2193.
　　[10]MIT DARPA intrusion detection data sets[EB/OL]. [2010-10-10].http://www.ll.mit.edu/IST/ideval/data/2000/2000_data_index.html.
　　[11]杨赞,杨林,王宝林,等. 依据流统计特性的文分类规则动态优化[J].计算机应用研究,2011,28(5):1878-1882.
　　[12](美)约翰逊,(美)威曾格,(美)普拉瓦提. Linux服务器性能调整[M]. 韩智文,译.北京:清华大学出版社,2004:23-24.
　　[13](美) LOVE R. Linux内核设计与实现[M].3版. 陈莉君,康华,译.北京:机械工业出版社,2011:143-148.
　　[14]Libnids[CP/OL]. [2010-10-10].http://libnids.省略/.
　　[15]徐卫志,宋风龙,刘志勇,等. 众核处理器片上同步机制和评估方法研究[J].计算机学报,2010,33(10):1777-1787.

推荐访问:多核 匹配 算法 处理器