基于匹配动作表模型的可编程数据平面流表归并

凌致远，陈 晓，宋 磊

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京 100190； 2.中国科学院大学,北京 100049)

0 引 言

随着下一代互联网的发展，软件定义网络(Software Defined Networking， SDN)被广泛应用于企业广域网和数据中心网络[1]。SDN作为一种新兴的网络结构，它将控制平面与数据平面解耦[2]。数据平面由交换机等转发单元组成，负责将报文转发到下一跳；控制平面则由控制器组成，负责实时维护全局网络状态。

匹配动作表(Match-Action Table， MAT)[3]在现有的SDN技术中得到了广泛使用，OpenFlow[4]作为SDN技术的基石，率先使用MAT作为其数据平面编程模型[5]。匹配动作表又称为流表，将数据包处理流程抽象为匹配字段和执行动作。MAT模型的动作集可以实现对数据包字段的修改和数据包整体的转发，还能实现诸如条件分支等简单程序逻辑[6]。但OpenFlow是一种协议相关的SDN技术，仅支持对其标准[7]内已有的协议字段进行解析和处理，无法及时满足新兴或私有网络协议的需求[8]。

为了解决上述问题，协议无感知转发(Protocol Oblivious Forwarding， POF)[9-10]和协议独立的数据包编程处理器(P4)[11-12]等新的SDN技术被相继提出。这些SDN技术沿用了MAT编程模型，但允许网络编程人员以比OpenFlow规范更灵活的方式对网络进行编程。协议字段由诸如{偏移，长度}的结构组成，由此网络编程人员可以对任意协议字段进行解析和处理[13]。然而这种灵活的数据平面编程方式会带来一些问题：待处理的数据包可能带有不同长度的数据包头，因此这些数据包中特定协议字段的偏移也会不同，控制平面需要下发多个匹配域偏移不同的流表去完成数据流的解析，这对有限的数据平面资源造成了很大的浪费[14]。

在数据平面资源优化方面，国内外已经有了相关的研究[15-18]。这些研究主要集中于2种思路：减少表项数量降低数据平面设备软硬件资源占用和提高网络内整体数据平面资源利用率。在第一种思路下，Jia等人[19]提出了基于K相似贪婪树(K Similar Greedy Tree， KSGT)算法的SDN交换机流表空间优化方案，对OpenFlow空闲超时方案进行了优化，与现有解决方案相比，可以节省约60%流表项的资源占用；Kim等人[20]利用了OpenFlow的Vacancy事件，当交换机内流表可用空间小于一定阈值时，向控制器发出告警并通过LRU算法清理部分非活跃表项，从而减少表项占用的资源，并降低了控制消息的数量，Wu等人[21]在FPGA上实现了相似的算法；Mimidis-kentis等人[22]将流表项分为硬件表项和软件表项，优先级或命中率较高的表项安装在硬件上，从而提升交换机整体转发性能，并减少软件部分占用的资源；Shirali-shahreza等[23]通过预测TCP流的RST/FIN包来加速表项的清除，在命中率降低不到1.5%的条件下，减少了16%～62%的平均流表空间占用率；还有一些方法对流表进行拆分和压缩，实现了流表的高效存储[24-25]；更进一步地，有的研究基于数据中心网络实时流量特征动态设定表项的生存周期，从而高效利用流表的空间[26]。基于第二种思路，乔思祎等人[27-28]提出了一种“共享流表”的方法，利用负载均衡的思想，将单台交换机的流表负载分摊到网络中相邻的节点，提高了网内交换机整体的资源利用率。

本文采用上述方法外的另一种思路，即通过减少数据平面的流表数量来降低资源占用。根据数据包动态偏移的思想，本文提出一种基于MAT模型的可编程数据平面流表归并方案，在数据包查询流表时通过执行特定动作动态地调整数据包的起始偏移，使不同数据包同一协议字段的偏移保持一致，实现匹配域相同的流表的归并，从而降低数据平面设备的资源占用。

1 基于MAT模型的可编程数据平面流表归并方案

1.1 问题描述

在数据包头部协议层数不同或协议长度可变的情况下，网络编程人员需要对每种情况做出区分。对于数据包Pkt，其可能存在的协议组合有:P1={po,p1,p2}、P2={p0,op0,p1,p2}、P3={p0,p1′,p2}。其中pm为数据包头部相对固定的协议，如以太层协议、IPv4协议；opm为可能存在的网络标签或协议，如802.1Q报文；pm′为长度可变的协议，如带有Option字段的IPv6协议。协议P2中的某字段f在协议组合P1的情况下表示为f={off,len}，那么对于P2和P3，该字段分别表示为f′={off+len(op0),len}和f″={off+len(p1′)-len(p1),len}，如图1所示。若要将字段f作为流表的匹配域，开发人员需要针对每种协议组合设计一张流表，这将造成大量冗余的流表资源开销。流表符号和定义如表1所示，流表结构如表2所示。

表1 符号和定义

图1 不同协议组合下的数据包头部结构

表2 针对不同协议组合设计的流表

可以通过如图2所示的有向无环图G(V,E)来表示上述数据包在数据平面中的处理流程。其中V(G)代表数据平面中的流表，E(G)代表数据包跳转流表的路径。由于一张流表由固定描述字段和匹配域组成，则单张流表占用的资源可以看作匹配域长度l的函数m(l)。

图2 数据包处理流程G(V,E)

假设数据包处理过程中需要匹配N级流表，且数据包从第j-1级的某一张流表跳转至第j级流表有kj条分支路径(k0=1)，记第j级流表的流表数量为sj，则有：

(1)

可以看出，一级流表的流表数与此前每一跳的分支路径数相关，前级流表跳转分支路径越多，后级流表数越多。若第j级流表的匹配域长度为lj，则第j级流表占用的资源为：

(2)

综上，数据平面中所有流表占用的资源总量为：

(3)

1.2 方案设计

扩充MAT模型的动作集，新增用于修改数据包起始偏移的动作SET_PACKET_OFFSET(SPO)和MOVE_PACKET_OFFSET(MPO)。其中，SPO直接指定数据包的起始偏移，而MPO实现前后移动数据包当前的起始偏移。在数据包元数据区新增shift字段，用于记录数据包的当前起始偏移。数据包进入数据平面时，其起始偏移为0。当数据包进入流表匹配流程时，先计算数据包的起始地址(原地址+起始偏移)，然后再比较匹配域和数据包中对应字段的值。

以一个带802.1Q标签的IPv4数据包为例，如图3所示，其在数据平面中的处理流程如下：

步骤1数据包起始偏移为0，进入Table 0查表。

步骤2Table 0匹配Ethernet Ⅱ帧头部的类型域{96,16}，数据包执行指令“MPO 18，GOTO 4”，数据包的起始偏移由0改为18 byte，进入Table 4查表。

步骤3Table 4匹配IPv4协议中目的IP地址{128,32}，进行后续流程。

值得注意的是，Table 4中目的IP地址字段的定义与以往不同：数据包起始偏移为0时，目的IP地址字段的偏移从数据包起点开始计算，为240 bit；而现在Table 4中数据包的起始偏移为18 byte，即144 bit，所以目的IP地址字段的偏移要从数据包144 bit的位置(即IPv4协议的起点)开始计算，为96 bit。

为了更丰富公司的营销体系，南通鹏越纺织有限公司应不断着眼公司的直复营销，优化促销策略。构建更及时、更直接和更完善的人员推销体系，公司与联络点建立更加完善便捷和及时的联络沟通体系。更为重要的是，面对互联网技术的竞争规则和营销手段，南通鹏越纺织有限公司应紧跟时代步伐，探索网络营销新模式。

图3 含802.1Q标签的IPv4数据包的处理流程

不含802.1Q标签的IPv4数据包处理流程类似：数据包在Table 0中执行指令“MPO 14，GOTO 4”，将数据包的起始偏移修改为IPv4协议相对于数据包起点的位置，所以在Table 4中可以正确匹配目的IP地址字段，而无需增加新的流表。

同样地，可以将流表归并后该数据包在数据平面中的处理流程抽象为如图4所示的有向无环图G′(V,E)，其中每一级流表只解析一层协议。

图4 流表归并后数据包处理流程G′(V,E)

此时流表的每一跳分支路径数不再影响后续流表的数量，且：

∀j∈{0,1,...,N},kj=1

(4)

所以流表归并后数据平面中所有流表占用的资源总量为：

(5)

流表占用资源缩减比例为：

(6)

可以看出，流表归并方案消除了流表跳转路径数k对资源消耗的影响，即当各级流表匹配域长度相对固定时，流表跳转的分支越复杂，流表归并方案的优化性能越高。需要补充的是，上述问题和方案的模型是针对单个数据包提出的，每一级流表的匹配域内容相同。对于同层不同协议(如IPv4/IPv6、TCP/UDP等)的多种数据包的情况，可以看作在上述模型中添加更多的分支，流表归并的整体思想和结果是相似的。

根据上述原理，本文重新设计了流表，最终得到的数据包匹配流程与流表归并前的对比如图5所示。其中，流表归并前一共需要13张流表：Table 0的匹配域是Ethernet Ⅱ帧头部的类型域字段和802.1Q标签的类型域字段，用于区分数据包的类型(是否为VLAN/QinQ报文)，并根据分类结果进入不同的流表；Table 1～Table 6匹配IPv4/v6协议的源目的IP地址，考虑了是否为VLAN、QinQ报文的情况；Table 7～Table 12匹配TCP协议源目的端口号后转发数据包，同样考虑了是否为VLAN、QinQ报文的情况。流表归并后流表的数量则从13张减少到了4张：Table 0的匹配域不变，用于区分数据包的类型，并根据分类结果通过调整MPO指令的参数来修改数据包的起始偏移，随后进入下一张流表；Table 1和Table 2分别匹配IPv4和IPv6协议的源目的IP地址，并通过MPO指令将调整数据包的起始偏移至TCP协议起点后，进入下一张流表；Table 3匹配TCP协议的源目的端口号后转发数据包。

图5 新旧方案数据包处理流程对比

2 实验与分析

2.1 实验环境

为了验证基于MAT模型的可编程数据平面流表归并方案在实际应用中的合理性和有效性，本文在X86平台的POF交换机上进行了验证测试，分析了不同类型的流量面对本方案的应用效果，测试平台软硬件信息如表3所示。

表3 测试平台软硬件参数

使用Spirent SPT-C50作为流量发生器，环境拓扑如图6所示。测试设计了3级流表，分别用于L2解析、源目的IP地址匹配、源目的TCP端口匹配，如图7所示。其中L2解析和TCP端口匹配流表的匹配域总长度均为32 bit，源目的IP地址匹配流表分为IPv4流表和IPv6流表，匹配域总长度分别为64 bit和256 bit。

图6 环境拓扑

图7 流表配置

2.2 数据包平均转发延时测试

本文测试流量包含IPv4/IPv6报文和IPv4/IPv6 VLAN报文，每种报文长度和数量相同。使用测试仪器以500 pps的发包速率向交换机循环发送，统计了流表归并前后的数据包平均转发时延、流表内存使用量和平均指令执行数，结果如表4所示。

表4 测试结果

2.3 测试结果与分析

从表4可以看出，流表归并前后流表内存使用量差距较大，这是流表数量大幅减少的结果。经计算，流表归并后节省了约69%的内存。POF交换机建表时按最大匹配域长度分配内存，所以根据式(6)预测流表占用资源缩减率时可以忽略参数m(l)，最终在实验环境下绘制出流表资源缩减率和第二级流表分支数的曲线，如图8所示。可以看出，测试得到的结果和预测结果几乎相同。

图8 流表资源缩减率预测曲线与实验结果

此外还发现流表归并后数据包在交换机处理流程中平均执行指令数增多，但数据包平均转发时延有少量提升。经分析验证，其原因主要有2点：

1)流表归并后增加的MPO指令在几个CPU时钟内就可以完成执行，对数据包转发时延的增加可以忽略不计；

2)POF交换机的批处理查表机制会遍历所有的流表，如果当前批次的数据包中有数据包需要查某张流表，就会执行一轮查表循环。流表归并前不同的报文会进入不同的流表查询，所以需要查询的流表数量更多，执行的查表循环轮数更多。而流表归并后不同的报文会进入相同的流表，整体查表次数更少。且查表所需时间比MPO指令执行时间长很多，所以从最终结果看流表归并后数据包转发平均时延会更小。

3 结束语

本文从流表数量的层面入手，提出了一种基于MAT模型的可编程数据平面流表归并方案，缓解了协议无感知的可编程数据平面应对复杂网络数据包头部协议组合时存在的流表冗余问题，通过减少流表数量大幅节约了数据平面的流表资源开销。本文在POF交换机上完成了方案的验证和测试，实验结果表明，所提流表归并方案能够大幅缩减数据平面的流表资源消耗，且小幅提升数据包的平均转发时延。

未来的研究工作将在本文提出的方案基础上结合表项管理机制进一步对流表空间进行优化和研究。