软件定义网络中控制数据平面一致性的验证

朱梦迪，束永安

（安徽大学计算机科学与技术学院，合肥 230601）

（∗通信作者电子邮箱2524098773@qq.com）

0 引言

软件定义网络（Software Defined Network，SDN）是一种将控制平面与数据平面分离的新型网络架构。控制平面通过北向接口协议集中管理网络应用程序，通过南向接口协议管控数据平面所有硬件设备的转发行为［1］。

与传统网络不同的是，SDN 是一个流规则驱动的网络［2］。网络应用程序、操作人员可以制定网络策略，对应接口会将其转化成一组逻辑流规则，然后控制器通过北向接口将逻辑流规则部署到交换机内，最后网络设备根据交换机内的流表项对数据包进行处理，实现对应的网络策略。

在SDN 中，目前有以下几方面原因，会导致数据包的转发行为与控制层流规则不一致。OpenFlow 协议［3］的Barrier命令不能百分之百保证控制器下发到数据层的每个流规则全部可以正确安装［4-6］；网络故障中的很大一部分原因是由于数据层的硬件问题及软件错误［7］；SDN 的控制平面与数据平面之间采用异步通信发送信息，一些网络更新命令（如OpenFlow协议的FlowMod 命令）会使得交换机在更新流表时存在延迟，无法及时更新［5，8］；最后，网络管理员的错误配置，和攻击者使用一些工具（如ONIE（http：//onie.org/）），均有可能修改交换机内部的流表项，导致数据层没有实现相应的网络策略。

为了解决控制层与数据层流规则不一致的问题，文献［9-13］均提出各自的方法，用于检测多个应用程序引起的网络策略冲突，但是这些方法只能处理控制层流规则冲突的问题，却无法检测到数据层的流量转发是否符合控制层的策略要求。因此，文献［14］将数据层的可执行文件作为自制的检测工具的输入，用于检测数据平面是否不合理的网络配置，但检测机制无法对网络状态进行实时监测；所以，文献［15］使用探测数据包，对数据平面的信息进行收集和记录，可以动态监控转发链路上是否出现故障交换机，但该种方法探测数据包的生成时间较长，无法快速地发现数据层的错误。

继而，文献［16］提出VeriDP 检测模型，该模型截取数据流中的数据包，在采样数据包中添加标签字段，无需单独生成探测数据包，但该方法的缺点在于控制平面需要提前保存所有正确的转发路径信息，过于消耗内存资源。文献［17］提出2MVeri 模型，但算法时间复杂度相对较高，系统开销相对较大。因而，本文提出了验证控制与数据平面的一致性（Verifying control-data plane Consistency，VeriC）检测模型，不仅解决了内存消耗大与过滤器误报的问题，又在准确找出发生错误的交换机的前提下降低系统开销。

1 VeriC检测模型系统设计

VeriC 检测模型由VeriC 模型对应服务器中的验证子系统、定位子系统以及交换机的数据包处理子系统共同实现。控制器和交换机通过OpenFlow 协议交互的信息，均会被拦截并保存在模型服务器内。

VeriC模型借助管道技术实现数据包处理子系统的功能，由交换机的快速路径技术完成，并且与OpenFlow 所用的管道是分离的［16］。VeriC在入口交换机上对数据包进行采样，在数据包的转发过程中对数据包进行标记，每经过一个交换机，更新采样数据包标签字段，随后将更新后的标签值发送到VeriC服务器，分别存储在上报的标签值PTg［i］（rePorted Tag）和上报布隆过滤器值BFp（reported Bloom Filter）。

VeriC模型对通过南向接口协议交互的消息进行拦截，当被采样数据包在出口交换机标记动作完成后，模型服务器根据初始二维向量、正确的转发表、交换机ID以及每个交换机对应的二维矩阵，计算出一组正确的标签值CTg（Corrected Tag）和正确的布隆过滤器值BFc（corrected Bloom Filter）。每组流规则对应CTg［i］和BFc，PTg［i］和BFp均会被发送到验证子系统进行一致性检测；若存在异常，标签值组被进一步发送到到定位子系统，对故障的交换机进行定位。VeriC模型结构如图1所示。

图1 VeriC模型结构Fig.1 VeriC model structure

2 详细设计

2.1 数据包处理系统

2.1.1 数据包采样

在数据包处理系统中，首先要对交换机中数据包进行采样［17］。在入口交换机，使用数据包字段中的一个位来记录数据包是否被采样，设最近一次采样时间为，采样间隔为。若入口交换机在时间t收到数据包，数据包的采样时间满足式（1），则该数据包即为采样数据包：

2.1.2 生成交换机矩阵

数据层交换机在初始化时，控制器会为其分配一个受限制的二维矩阵，用于对交换机进行标记［17］。为了使标签信息能够准确代表数据包的转发路径，在为每台交换机分配二维矩阵时，需满足以下要求：

1）二维矩阵中的四个元素均为素数，降低矩阵的重复率；

2）相邻交换机是不可交换矩阵，即相邻交换机的矩阵信息不满足矩阵乘法交换律；

3）交换机的二维矩阵不可以相同。

2.1.3 字符注释

为了便于描述，对本文涉及的符号进行注释，如表1所示。

表1 符号注释Tab.1 Notations and related meanings

2.1.4 标记采样数据包

对于每个采样数据包，会在包头中插入BF字段和一个二维向量字段（v1，v2）。其中，BF 字段的初始值为0（见算法1 第1）～2）行），表示采样数据包经过交换机ID的集合。采样数据包每经过一台交换机，BF字段就会将新交换机的ID存储到集合中，当数据包到达出口交换机或者要执行删除操作前，将BF字段发送到控制平面进行保存（见算法1第10）～12）行）。

控制器基于采样数据包的性质，首先为二维向量字段（v1，v2）分配初始值（见算法1第3）～5）行），并将初始值上传到控制层。在控制层中，使用〈inport，outport，header〉作为索引，存储到同一采样数据包的标签值集合，其中inport 是采样数据包的入端口编号，outport 是采样数据包的出端口编号，header是采样数据包的包头信息；然后，当采样数据包经过交换机时，二维向量会与交换机对应的二维矩阵相乘，运算值会重新存储在二维向量字段中（见算法1第6）行）。二维向量字段每次完成更新后，会将标签字段发送到模型服务器进行保存（见算法1第7）～9）行）。数据包处理算法描述如下。

算法1 数据包处理算法（Packet processing algorithm）。

2.2 一致性验证以及故障定位

2.2.1 一致性验证

当采样数据包在出口交换机完成转发后，会在控制层检测控制平面与数据平面之间流规则的一致性。如果服务器中存储的BFp与BFc相同，且二维向量标签值PTg［ty-1］与控制器中的正确标签值CTg［tx-1］相等；那么，数据包的实际转发路径与控制器中期望数据包的转发路径一致（见算法2 第1）～2）行）。

若控制器中BFp与BFc标签值不同，而tx与ty的值相等，PTg［ty-1］与CTg［tx-1］也相等，则要考虑字段BF的误报情况：从BF 字段值初始值开始比较，假设在第i台交换机，发现BFp与BFc不一致，检查PTg［i］与CTg［i］或PTg［i-1］与CTg［i-1］是否相等。若相等，表示第i台交换机在更新BF字段时，出现了误报的情况，则将正确的值更新到BFp［i］中；若有一组值不相等，直接返回False（见算法2 第3）～12）行）。验证算法描述如下。

算法2 验证算法（Verification algorithm）。

2.2.2 故障交换机定位

在验证算法中，对于返回False 的标签组，会进入故障定位算法，查找发生错误的交换机。当PTg［i］与CTg［i］不一致，并且BFp［i］与BFc［i］也不相等时，i对应的交换机即为故障位置（见算法3 第1）～4）行）。对于字段BF 的误报情况，已经在验证算法中实现修正，所以PTg中的标签值基本不会出现错误情况。定位算法描述如下。

算法3 定位算法（Localization algorithm）。

3 实验实现与结果分析

3.1 实验设置

本文通过ns-3 模拟器（https：//www.nsnam.org/）对VeriC模型进行了验证。ns-3 是一个离散事件网络模拟器，可以在单个计算机上为用户提供模拟实验。本文实验计算机的配置如下：Intel Core i7 CPU 3.6 GHz 处理器，16 GB 内存，Ubuntu 16.04操作系统。

本文在ns-3模拟器中仿真一个k值为4的胖树结构，胖树拓扑中包含16 台主机和20 台交换机。在仿真实验中，通过式（2）来设置BF字段的存储位数。

本文使用gi（x）中的前四个比特位来设置16 位的BF，在ns-3 模拟器中通过UniformRandomVariableClass 来生成并分配给采样数据包的二维初始向量值和每台交换机的二维矩阵值［17］。

3.2 结果分析

网络拓扑构建完成之后，首先使16 台主机实现互通，完成交换机上流表项的全部安装。然后随机选择一些互通的主机对，对于每一组被选中的主机对，在流量转发的路径中随机抽取一台交换机，修改交换机内部存储的流表项，观察实验结果。已知数据层的转发路径与控制平面的不一致，通过对比VeriC的验证结果，发现采样数据包上传的实际标签值与控制平面中保存的预期标签值不一致。

本文通过相对假阴性率和绝对假阴性率来展示VeriC 的实验结果。对交换机中的流表项进行错误设置。m是设置错误流表项之后，交换机生成的数据包数量。m1是设置错误流表项之后，从入口交换机到达目的地数据包数量。m2是设置错误流表项之后，从入口交换机到达目的地，并且报文中的实际标签值与正确标签值一致的数据包数量。绝对假阴性率为m2/m，相对假阴性率为m2/m1。

本文将VeriC、2MVeri、VeriDP 三种模型的相对假阴性率和绝对假阴性率进行了对比［16-17］，VeriC 检测模型的相对假阴性率和绝对假阴性率不会因为Bloom 过滤器位数的增加而改变这是由于VeriC 检测模型，并不仅仅依据Bloom 过滤器中保存的交换机ID值，进行一致性检测，而是根据每组流规则对应CTg［i］和BFc，PTg［i］和BFp的值，检测数据层的转发行为是否与控制层一致。在两组标签值的共同作用下，消除了Bloom 过滤器的误报情况，使得一致性检测更加准确，实验结果如图2和图3所示。

VeriC 模型的定位算法，与交换机接口数、端口对的数量无关。假设一个网络中（inport，outport）对的数量为n，网络流量数为m，每台交换机的端口数为p，转发路径表中的最大跳数为h，三种检测模型的运算开销如表2所示。

由表2 可知，使用三种检测模型定位故障交换机时，VeriDP 的内存开销和算法的时间复杂度均最高，而2MVeri、VeriC 模型不需要构建路径表。2MVeri 算法的时间复杂度为是O（1）+O（ph），VeriC 算法仅为2O（h），2MVeri 模型通过矩阵的逆，定位故障交换机，当一组流规则转发的交换机数和端口数越多，算法的时间复杂度也就越高。VeriC检测模型验证算法的时间复杂度大于2MVeri 验证算法，但综合考虑，VeriC 模型算法的复杂度总和是最小的。

图2 相对假阴性率Fig.2 Relative false negative rate

图3 绝对假阴性率Fig.3 Absolute false negative rate

4 结语

本文提出了VeriC 检测模型，用于检测控制平面与数据层之间流规则的一致性。VeriC 检测模型通过对交换机的数据包进行采样，修改采样数据包，记录数据包的转发信息，完成控制平面与数据层的一致性检测，最终找出故障交换机。目前，已经在胖树结构上完成了仿真实验，实验证明VeriC 模型能100%准确地进行故障定位。

VeriC模型虽然能够完成一致性检测，但是基本条件是控制平面流规则符合一致性检查。当多个应用程序同时对网络进行操作时，生成的流规则之间可能会存在冲突。所以，未来会对控制平面流规则的一致性进行检测。