应用于协议无感知转发交换机的流缓存方法

1 引言

软件定义网络(Software Defined Networking,SDN)通过解耦控制与转发功能为网络提供可编程能力，使得网络资源与计算、存储资源一样可以自动感知和管理。OpenFlow[1]使用匹配动作表(Match Action Table,MAT)描述交换机转发行为，是最为流行的一种SDN实现。然而OpenFlow面临协议扩展问题，难以满足更多的网络协议、带状态的数据转发等复杂需求。协议无感知转发(Protocol Oblivious Forwarding,POF)[2]拓展了OpenFlow，通过｛类型，偏移，长度｝的字段描述方式与扩展的指令动作，实现了对任意协议字段的支持。借助POF，交换机无需理解特定的报文格式，新的网络应用的开发不再需要修改交换机代码，新技术、新业务的迭代速度将得到极大的提升[3]。

这个想法得到了各位班委的认可，于是“先锋车站”的筹备工作就此开始了。小刘给每个小组画一辆不一样的车型，并在车上标出小组名字和组员名字；班级文化部着手画车轨和站牌。在每周的评比中，优秀小组被评为“先锋列车”，向终点前进一站，每个站都有相应等级的奖励，一个月总结一次。而小刘则是这个“车站”的管理员，为确保先锋车站的每一辆车都是崭新的，如果哪个小组的车有破损，或需要重新设计，都可以找小刘帮忙。

网络协议数据面一般不会在包头域进行算术操作，只是做一些TTL和CRC的计算，而POF流表混合了解析与转发功能，可以处理解析过程中的状态变化，这给应用流缓存带来了困难。PVS[11]对每个流表单独应用流缓存，规避了这个问题，但也导致了匹配次数增加、空间利用率降低等问题。

针对POF协议的限制，本文提出一种应用于POF交换机的流缓存方法，通过识别匹配和动作的依赖关系，得到匹配字段的绝对位置，用以预先解析报文。为确保流缓存的加速效果，根据匹配类型与表项数量选择应用流缓存的流表。此外，本文对比了单流表缓存与多流表缓存对转发性能的提升，并提出了根据网络流量实际情况的自适应切换策略。通过扩展POFSwitch[12]实现所提方法，并用实际规则与流量数据进行验证，应用流缓存后，交换机报文转发速率提升了220%。

2 POF流缓存

2.1 POF交换机的报文处理流程

POF基于MAT模型，报文进入交换机后首先匹配第1个流表，匹配成功则执行报文处理动作，并根据需要将报文数据(通过Goto-Table动作)交给下一个流表处理。POF使用｛类型，偏移，长度｝描述协议字段，“类型”包括报文数据和元数据，对于报文数据字段，“偏移”为相对于协议首部的偏移。报文在POF流表中是逐层处理的，报文偏移(packet offset)用于指示当前协议首部的位置。每一层协议由1个或多个流表处理，通过移动报文偏移，实现字段解析功能。如图1所示，报文包含3层协议首部，分别由3个流表处理，Move-Packet-Offset动作移动报文偏移指向下一层协议首部。若需要同时处理多层协议，使用元数据传递协议字段。

POF与OpenFlow在报文处理上主要有两点不同，第一，POF允许动作使用任意字段修改报文数据，而OpenFlow规定了数据路径一致性(pipeline consistency)，动作使用和修改的字段只能是匹配字段；第二，POF通过字段描述和报文偏移实现字段解析，不需要专门的解析器(parser),OpenFlow的匹配字段基于既有经验定义，由专门的解析器提取报文字段。

2.2 POF流缓存的匹配字段

应用流缓存需要满足两个条件，其一，流缓存匹配的字段能够识别流；其二，这些字段能够预先提取。流的定义依赖于具体的应用，在MAT模型下，称报文匹配的(流表，表项)序列为匹配路径，匹配路径一致的报文，属于同一条流。

OpenFlow可以预先解析匹配字段，并且通过数据路径一致性，保证了预解析的字段能够确定报文匹配路径。基于此，OVS使用预解析的匹配字段识别流，匹配字段相同的报文，其匹配路径也相同。而匹配字段不同的报文，其匹配路径也可能相同，称这种方式识别的“流”为小流(microflow)。

图1 POF流表的报文处理流程

POF的字段解析混合在流表中，无法预先提取匹配字段，而且POF并未要求数据路径一致性，仅依靠匹配字段不能完全确定匹配路径。在POF流表中，匹配字段与动作之间存在着依赖关系，如图2所示。若流表T的匹配字段值依赖于动作a的执行，比如动作a修改报文偏移，改变了匹配字段位置，则流表T与动作a存在依赖关系。若动作a依赖于动作b的 执行结果，比如动作b修 改了动作a的输入字段，则动作a与动作b存在依赖关系。通过遍历所有可能的匹配路径，识别其中的依赖关系，搜集影响流表匹配的字段，这些字段可以预解析，也能识别流。本文即采用这些字段用于流缓存匹配，所识别的“流”也是小流，除非特指，后文所指的流均为小流。

图2 匹配字段与动作间的依赖关系

2.3 POF流缓存数据路径

根据上一节的分析，通过识别依赖关系，搜集影响流表匹配的字段可实现流缓存匹配。POF中存在部分流表，表项数量少、匹配速度快，应用流缓存不一定能得到加速效果。选择适宜流缓存的流表，得到图3所示的流缓存数据路径。当报文进入流缓存时，提取报文字段用于流缓存匹配，若匹配成功，则执行所属流的动作，否则进行流表匹配，记录其匹配路径，当报文离开流缓存时，作为新流缓存下来。

以流表为节点，表项为弧，合并重弧(multiple arcs)，得到弱连通的有向无环图G。G中有且仅有1个节点的入度为0，其他节点入度大于或等于1。选择应用流缓存的流表，得到多个弱连通的子图｛Gi｝。如图4所示，选择流表T1,T2,T3,T4应用流缓存，构成子图G1=｛T1,T3,T4｝与G2=｛T2｝，设T1,T2,T3,T4的匹配字段集合分别为F1,F2,F3,F4。以入口流表为单位，对G1与G2分别应用流缓存。对于G1，通过识别匹配路径中的依赖关系，得到T1处决定匹配T3时F3值的字段集合F3′，与T1处决定匹配T4时F4值的字段集合F4′，合并F1,F3′,F4′得到F。当报文进入T1时，使用F预解析字段，用于流缓存匹配。对于G2，则对T2单独应用流缓存。称G2这种单个流表应用流缓存的方式为单流表缓存，G1这种多个流表组合应用流缓存的方式为多流表缓存。

图3 POF流缓存数据路径

图4 应用流缓存的流表

当动作使用字段值修改报文偏移时，无法预知其具体值，只能得到F3′的可能位置，若范围过大，甚至包含整个报文数据，此时，宜对T3使用单流表缓存。

3 依赖关系的识别

字段与动作的依赖关系反映了字段解析过程与报文分类过程。识别流表中的依赖关系，是POF应用流缓存的必要前提。

在MAT数据路径中，报文处理包括字段解析、多次流表匹配与动作执行，受表项数量与匹配字段的限制，流表匹配成为了交换机转发性能的瓶颈[4]。为提高流表匹配性能，Yingchareonthaworn-chai等人[5]提出PartitionSort匹配算法，通过最大独立集的分组方式划分规则，避免规则重叠对流表更新性能的影响，却牺牲了流表匹配性能。Katta等人[6]提出CacheFlow方法，通过缓存流行规则，缓解TCAMs (Ternary Content Addressable Memories)容量受限的问题，然而TCAMs更新慢且复杂，缓存缺失的开销会非常高。作为最流行的OpenFlow交换机，Open VSwitch (OVS)[7]使用流缓存避免了上述问题，通过记录流的首个报文的匹配结果，用一次精确匹配代替多次流表匹配，加速后续报文的处理。网络流量通常都具有很强的时间局部性[8]，同一条流的报文常常会一起出现，通过流缓存可以显著提升转发性能。OVS衍生的交换机大多都沿用了流缓存设计，如SoftFlow[9]和PISCES[10]。

(1) 动作会修改字段值，不改变字段定义，如Set-Field,Algorithm等。

(2) 动作会移动报文偏移，改变报文数据字段的位置，如Goto-Table,Move-Packet-Offset。

(3) Add-Field与Delete-Field，会添加或删除字段，同时改变字段位置。

(4) 动作不会对字段造成影响，如Output,Drop等。

(5) Apply-Actions与Group，为其他动作的集合。

给定字段集合F，与动作存在依赖关系的条件是：对于(1)类动作，输出字段与F中的字段重叠；对于(2)类动作，F中存在报文数据字段；对于(3)类动作，F中存在字段位于添加或删除的位置之后；对于(4)类动作，集合中存在影响F的动作。

依赖关系贯穿于整个匹配路径，为搜集影响匹配路径的字段，需记录当前动作对字段的影响。围绕字段，按照解析路径的逆序识别依赖关系，使用相对偏移判断字段之间的位置关系。用g(F)表示经过动作影响后的字段集合，对于(1)类动作，输出字段不会被更早的动作影响，应删除F中与输出字段重叠的部分，g(F)应包含动作的输入字段；对于(2)类动作，按照移动报文偏移的反方向修改F中报文数据字段的相对偏移，比如字段f的偏移值为o，若动作前移报文偏移dbit，则g(f)的偏移值为o-d，若移动的偏移值来自字段，则用范围表示g(f)的偏移值，若动作前移报文偏移，则g(f)的偏移值变为 (-∞,o]；对于(3)类动作，若动作为Add-Field，则应删除F中与添加字段重叠的部分，同时减小添加位置之后的字段偏移，若动作为Delete-Field，则应增加F中包含删除位置的字段的长度，同时增加删除位置之后的字段偏移。若动作对字段无影响，则g(F)=Ø。

表1描述了依赖关系识别算法，表项e包含多个动作，采用逆序与字段F进行比较，若动作影响了字段，则更新字段定义，合并输入字段，判断下一个动作。

表1 依赖关系识别算法

4 流表的选择

并非所有POF流表都适用于流缓存。令流缓存命中率为ρ，流表的表项数量为N，流表匹配算法的时间性能为f(N)，流缓存匹配采用哈希实现，时间性能为O(k),k为匹配字段的长度。设引入流缓存前的流表匹配的时间性能为C=f(N)，则引入流缓存后的时间性能为C′=(1-ρ)f(N)+O(k)。当C′<C时，流表可以通过流缓存获得加速效果。不同的匹配类型，通常采用不同的匹配算法，表2给出了几种匹配类型的典型匹配算法。

表2 几种典型的匹配算法

对于LM和EM，由于f(N)=O(k)，故而C′≥C，应用流缓存后得不到加速效果。对于LPM和MM，取f(n)=lgn，计算C′<C，得到

取Thr=2k/ρ，当表项数量N>Thr时，LPM和MM流表可以通过流缓存获得加速效果，其中缓存命中率ρ可以根据经验得到。

5 多流表缓存与单流表缓存

通过式(1)选择的流表，既可以应用多流表缓存，也可以应用单流表缓存。为比较二者的适用情况，定义流表应用流缓存的收益为w=C-C′=ρ⋅f(N)-O(k)，选择收益高的流缓存方式。流表的匹配字段构成报文空间U=｛0,1｝k，网络中的报文符合齐夫分布，即。其中K为报文的种类，K≫1。参数α>0,α越小，则报文分布越均匀。设不同报文空间上，报文的参数α相同。当流缓存空间有限，而流量无限时，采用最近最常使用替换算法，可保留前n个概率最高的流，n≤K。这n条流所占比例为。得到缓存命中率

ρ(n)为单调递增的凹函数。

设G为应用流缓存的流表构成的一个弱连通子图，包含T1,T2,⋅⋅⋅,Tl共l个流表，其中T1为其他流表的父流表，流表的匹配字段集合为F1,F2,⋅⋅⋅,Fl，长度为k1,k2,⋅⋅⋅,kl，对应空间为U1,U2,⋅⋅⋅,Ul，报文种类为K1,K2,⋅⋅⋅,Kl，流缓存空间大小为|S|。单流表缓存中，每个流表占用一部分缓存空间，包含的流的数量为n1,n2,⋅⋅⋅,nl≥0，有。单流表缓存的整体收益为

多流表缓存中，匹配字段为F，长度为k，对应报文空间U，含有K条流，有k≥k1。所有流表共用流缓存空间，缓存命中率相同为ρ，且kn=|S|，整体收益为

分配缓存空间使单流表缓存整体收益最大，等效为最优化问题。

易知-Ws()为1阶导数连续的凸函数，约束函数1阶导数连续，可行域为超平面与半空间的交集，为凸集。问题式(5)的局部最优解*即为全局最优解[13]，应满足式(6)：

其中，为拉格朗日函数，。

以0<α<1为例。求解式(6)，可得到ni=，其中，故单流表缓存的整体收益为

而多流表缓存的整体收益为

计算式(7)与式(8)，选择整体收益最大的缓存方法。在实际环境中，由于无法事先获得不同流表的报文种类Ki，无法直接比较。此时可优先采用多流表缓存，利用数据流算法[14]记录每个流表的流数量，以及多流表缓存的流数量。当时，退化为单流表缓存。

基于前述分析，得到选择流缓存流表的算法，如表3所示，采用深度优先搜索遍历所有可能的匹配路径。为减少重复搜索，第2行去除所有(3)类动作，合并动作相同的表项。第3～5行判断当前流表是否应用流缓存。第11～12行识别表项与子流表之间的依赖关系，用F′(Y)记录决定子流表匹配字段值的字段集合，F(Y)表示流表Y处决定后续解析路径的字段集合。第13～16行，在遍历子孙流表后，用F(X)记录合并的字段，用于后续的依赖关系判断。

表3 流表选择算法

6 验证与分析

6.1 实验环境

为了评估流缓存的可行性与算法的有效性，本文基于POFSwitch实现了所提的POF流缓存方法，应用随机替换策略。POFSwitch分别采用二叉树和线性查找实现LPM和MM，使用单线程处理报文。POFSwitch运行的硬件环境为Linux 2.6.32 64位系统，Intel Xeon E5-2620 CPU 2.00 GHz,16 GB DDR3内存。使用PCTRL[15]作为控制器，Ixia PerfectStorm ONE作为流量发生器，环境拓扑如图5所示。测试用的流量数据来自CAIDA[16]，包含6.56M个报文，其中五元组的数量为361.3 k,IP地址对的数量为357.2 k。测试用的流表包含L2转发、L3转发和ACL表，如图6所示。其中，L3转发规则来自RouterViewer[17],ACL规则使用Class-Bench[18]生成。为便于测试交换机转发性能，为L3表和ACL表添加了默认规则，使所有流量都能经过交换机转发回流量发生器。

6.2 交换机转发性能测试

图5 环境拓扑

图6 流表配置

本文使用测试仪器以500 kpps速率循环发送流量数据，测试了不同流缓存空间下，应用流缓存前后的交换机转发性能，结果如图7所示。流表选择算法选择了L3转发表与ACL表组成多流表缓存。流缓存空间从0.5 k条流增加到512 k条流，每轮测试执行30 s，取5次测试的平均值。未应用流缓存时，交换机的转发性能为13.2 kpps。应用流表缓存后，0.5 k流缓存空间下的转发性能提升到15.5 kpps，而256 k流缓存空间下的转发性能提升到42.3 kpps，较应用流缓存前提升了220%。简而言之，应用流缓存后，交换机的转发性能得到显著提升，并随流缓存空间增大而升高。

图7 应用流缓存前后的报文转发速率对比

当流缓存空间增大到128 k后，继续增大流缓存空间，转发性能的增长幅度减缓。原因在于，128 k大小的流缓存空间，已经能缓存大部分流量，继续增大缓存空间，缓存命中率的提升有限。当流缓存空间小于256 k时，缓存空间的占用率接近100%，而256 k流缓存的空间占用率只有54.98%,512 k流缓存的空间占用率只有28.22%。据此计算，流的数量大约为150 k左右，少于五元组的数量(361.3 k)。这是由于测试仪器的发送速率远高于交换机的转发速率，Linux系统会随机丢弃报文，导致被交换机处理的流的数量减少。

6.3 多流表缓存与单流表缓存比较

本文还比较了单流表缓存与多流表缓存的转发性能。单流表缓存中，ACL表与L3表单独应用流缓存，缓存空间按流数量等比例分配。从图8可以看出，在缓存空间增加到512 k前，单流表缓存ACL表的缓存命中率低于多流表缓存，虽然L3表的命中率高于多流表缓存，但交换机转发性能主要受到ACL表匹配性能的限制。这是因为POFSwitch中，MM算法实现较LPM算法实现要慢许多。当流缓存空间增加到256 k后，继续增加流缓存空间难以继续提升多流表缓存的缓存命中率。当流缓存空间增加到512 k时，单流表缓存ACL表的缓存空间达到256 k，其缓存命中率逼近多流表缓存，二者转发速率接近。总而言之，在本实验中，等比例分配缓存空间的单流表缓存的转发性能要低于多流表缓存。

7 结束语

此前的研究验证了流缓存对于提高转发性能的有效性。然而，这些研究没有解决POF协议应用流缓存的限制，在POF交换机中无法实现多流表的匹配加速。针对这个问题，本文提出了一种应用于POF交换机的流缓存方法，通过识别流表中的依赖关系，使POF交换机能够支持多流表的匹配加速。在此基础上，本文对比了单流表缓存与多流表缓存对转发性能的提升，并提出了根据网络流量实际情况的自适应切换策略。本文基于POFSwitch与实际流量规则，对所提方法进行了验证。实验结果表明，所提流缓存方法能够提高POF交换机的转发性能。本文的研究表明，流缓存可以为可编程数据平面的提供更高的转发性能。

未来工作将进一步研究POF流缓存支持表项更新的方法，以及当流缓存的流表为非连通图时，流缓存空间的分配策略。

图8 多流表缓存与单流表缓存的转发速率与命中率对比