基于时序与集合的SDN流表更新策略

刘振鹏，李明，王鑫鹏，任少松，李小菲

(1. 河北大学 电子信息工程学院，河北 保定 071002；2.河北大学 信息技术中心，河北 保定 071002)

软件定义网络(SDN)中流表更新一致性问题是一个重要的问题[1-3]，在SDN主流的南向接口OpenFlow协议[4]中由于控制器与各交换机间存在时延，交换机更新没有顺序性，可能导致数据包同时按照新旧规则进行处理，可能导致数据包的丢失，甚至造成网络拥塞.

针对此问题，研究人员提出许多方案，文献[5]提出基于中间流表的流表更新一致性方案，该方案基于新旧流表提出新的中间流表.中间流表将所有数据包发送至控制器，然后在交换机中写入中间流表.等待一个端到端时延，然后在交换机中写入新流表，最后将上传数据包发送回网络中.该方案引入中间流表，新流表更新过程中，数据包发送至控制器，更新完成后发回网络.文献[6]提出基于额外标签的流表更新一致性方案，该方案以额外的数据标签(VLAN)来将新旧规则分类，旧流表的VLAN=0，新流表的VLAN=1，设置数据包的包头信息为VLAN=0，新规则写入交换机后更新数据包包头信息(由0更新为1)，更新完成后，所有数据包按照新规则处理，旧规则删除即完成更新.文献[7]提出了基于分类的流表更新一致性策略，该策略利用软件定义网络集中控制特性，首先对新旧流表和交换机进行分类，将入口交换机的数据包上传至控制器，等待一个端到端时延后更新新路径交换机上的流表，完成后更新入口交换机的流表，新路径完成后将旧路径交换机流表删除，最后将之前向控制器上传的数据包发回网络中.由于将数据包上传后，完成所有交换机流表更新后下发数据包，所以数据包在任意时刻只按一种流表进行处理.文献[8]提出了基于分类和时序的SDN流表更新一致性方案，该方案首先在新路径交换机上安装新流表，更新入口交换机后数据包即按新流表处理，一个端到端时延后旧路径的旧流表被删除，更新过程即完成.

交换机流表空间占用也是一个易被忽视的问题[9-10]，交换机流表的空间是有限的，可造成流表空间溢出[11-12]等严重问题.为此提出基于时序与集合的流表更新一致性方案，在保证流表更新过程中的控制负载的情况下，减小交换机空间负载，降低交换机流表空间溢出问题发生的概率.

1 基于时序与集合的流表更新策略

1.1 方案设计

假设所有流表规则更新涉及到的交换机集合为C，在流表更新中可以就交换机的流表更新时间将交换机进行分类，所用符号描述如表1.

表1 符号及其描述

流表的更新过程是控制器对交换机转发规则的修改，首先要保证的是数据包的不丢失，以及保证交换机对数据流的转发规则唯一性，方案步骤如下.

第1阶段：准备阶段，控制器在这个阶段分析新旧转发规则，准确定义交换机集合C，以及B、N、V.

第4阶段：在数据流上传至控制器开始，延迟时长tmax(tmax为网络内最长端到端时延)，以保证在上传开始前已转发的数据流最终到达，防止丢包.然后开始更新新旧路径共用交换机集合V中的对应流表和安装入口交换机流表.

在该方法中，可以在保证控制负载的前提下，减小交换机负载，降低交换机流表空间溢出等问题的出现.

1.2 算法描述

输入: G(V,L) //数据中心网络拓扑 B={s01,s02,…,s0a} //新路径交换机集合N N={s11,s12,…,s1b} //旧路径交换机集合B R0i //旧路径交换机对应流表输出: R1j //新路径交换机流表 1)V=B∩N //定义新旧路径共用交换机集合为V2)G=(N-V) //定义G为V对N的补集3)for(s1j in G) //判断新路径交换机是否为集合G的元素4)update R1j //更新集合G中的交换机流表5)delete R00 //删除入口交换机流表,这里有R00=R10,6)等待最长端到端时延tmax7)n=08)while n≤len(V)9)v=V[n]10)update R1j //更新v对应的交换机的新流表11)n+=112)endwhile //更新共用交换机流表13)update R10 //更新入口交换机新流表14)Delivery packet // 下发数据包 15)F=(B-V) //F为V对B的补集16)for (s0i in F) //判断交换机为旧路径剩余交换机17) delete R0i //删除交换机旧流表18) return R1j

2 一致性证明

方案保证流表更新规则的一致性，在证明中借鉴相关研究的思路，对流表更新的一致性证明.

F(x)=F0(x),

(1)

第2阶段:保持新旧路径共用交换机流表不变，开始时刻为t0，t0时刻开始更新除新旧路径共用交换机V的新路径交换机N(即集合N对集合V的补集)，此阶段数据包处理规则不变，此时的处理规则不变，即为式(1)，仍按旧规则处理.

(2)

F(x)=c，

(3)

更新完成时间为t3，此阶段完成后新路径更新完毕.

(4)

F(x)=F1(x).

(5)

以上过程中对应数据包的状态分为2种：上传至控制器和转发.在转发过程中，其新旧规则并未同时转发数据包，在逻辑上保证了流表更新的一致性.

3 仿真实验

目前关于流表更新一致性问题提出了很多的方案，方案自身的复杂程度以复杂度表示，复杂度表示方案实现的难易程度.更新时间是完成流表更新的时间，其较为直观地展现方案的可用性.控制负载是流表更新过程中对控制器产生的负载，控制负载差会直接影响控制层的运行效率[13-16].本文添加交换机负载指标.交换机流表空间有限，更新过程中对交换机流表空间占用的多少也是判断方案优劣的重要指标[17-20].

选取较为经典的4个方案[5-8]与本文提出方案进行对比，包括国外MCGEER[5]、REITBLATT[6]方案和国内2个方案[7-8]，将以本方案与上述方案进行相应性能指标对比.

3.1 实验环境

本文实验环境为虚拟机Ubuntu16.04系统环境，安装Mininet应用，Ryu控制器.

首先对比控制负载的优化情况，采用简单拓扑图1进行实验，其中s1、s2、s3、s4、s5、s6为交换机，h1、h2为主机.

图1 数据中心交换机拓扑示意Fig.1 Schematic diagram of data center switch topology

如图1所示，由h1向h2发送数据包，交换机旧路径为s1→s2→s3→s4，新路径为s1→s5→s6→s4.

3.2 实验结果

控制负载的情况可以转化为相同网络传输下上传控制器数据包的个数.进行10次实验并记录实验结果，如图2所示.

文献[5]向旧路径交换机s1、s2、s3、s4写入中间流表，中间流表即将数据包上传至控制器，全部写入完成后等一个端到端时延，之后删除旧流表写入新流表，数据包发回网络.由于引入中间流表，其更新时间较长，更新过程中上传数据包也最多.文献[6]中没有向控制器上传数据包的过程，所以整个更新过程中没有数据包上传至控制器.由于文献[7]中在上传数据包后等待一个端到端时延后再更新所有新路径交换机s5、s6、s4，而本方案只需在端到端时延后更新s4以及安装s1流表即可，所以在相同网络传输速率下，本文方案在上传时间上少于文献[8]，因此更新过程中上传数据包数量也更少.文献[8]控制负载较其他方案，只需更新入口交换机s1即可下发数据包，所以其在控制负载方面较优.

各方案和本方案在交换机s4流表存储空间占用方面的比较，如图3所示.由于几种方案的更新策略不同，新旧路径共用交换机s4存储空间相关流表个数占总更新时间比例不同.

文献[5]首先在入口交换机s1和旧路径交换机中更新中间流表，然后新路径更新新流表，整个过程中交换机s4从旧流表更新为中间流表，后更新为新流表，更新前后新旧流表并没有长时间共存，此状态时长约占更新过程的90%，效果较好.文献[6]中额外标签完成后，将新流表写入入口交换机以及新路径交换机中，更新数据包VLAN后，等待一个端到端时延即删除旧流表，其整个更新过程中交换机s4始终存有新旧2套流表，其交换机负载较大.文献[7]先将数据包上传，然后向新路径交换机下发新流表，因此s4交换机流表空间中有新旧2套流表，一个最长端到端时延后，新路径交换机删除旧流表，即s4旧流表删除，其过程中s4流表空间中有新旧2套流表时间较长，该时长占整个更新时间约为90%，交换机负载相对较大.文献[8]方案中首先向新路径交换机中安装新流表，s4中新增新流表，而后完成对s1流表的更新、下发数据包等，最后删除新路径交换机中的旧流表，此时更新过程结束.所以在整个更新完成过程中s4交换机流表空间中始终存有新旧2套流表，交换机负载较大.

图2 上传数据包对比Fig.2 Comparison of the number of uploaded data packets

图3 交换机s4流表更新时间占比Fig.3 Proportion of update time of s4 flow tables

本文方案则是一开始对s5、s6流表进行更新，而后删除s1中旧流表，并等待延时后即更新s4流表，写入新流表后随即删除旧流表，所以在整个过程中s4交换机中流表数量基本不变，且相对文献[5]没有引入中间流表，总体效果最好.

3.3 结果分析

在复杂度方面，文献[6]中的基于额外标签的流表更新一致性方案需要添加额外标签，其复杂度最大.文献[5]中基于中间流表的流表更新策略因为引入中间流表，其复杂度适中.文献[7]实现过程简单，复杂度最小.本方案与文献[8]复杂度也相对较小.

文献[6]更新过程中不需要将数据包上传至控制器，所以其更新时间最短.文献[5]由于需要更新中间流表和等待端到端时延由此更新时间也相对较长.本方案对交换机集合分别更新，其更新时间较短.

本方案在控制负载方面由于减少了上传数据包的时间，对控制器资源占用相对较小，文献[5]更新过程中可能会出现下发数据包的交换机中规则依然是中间流表的情况，交换机会将数据包重新发回控制器，所以其控制负载相对本方案较大.文献[6]更新过程中不需要将数据包上传至控制器，由此控制负载相对本方案有优势.

交换机负载本方案相对于文献[8]由于对新旧路径共用交换机的处理，保证了新旧流表不同时存在于一个交换机中.文献[6]由于对数据包和流表添加额外的标签，新旧流表持续存在于相应的交换机中，交换机负载最大.

各方案具体对比如表2.

表2 各方案比较

4 结束语

提出了一种流表更新一致性的策略，对传统更新策略进行改进，合理地保证了流表更新的一致性.该方案在与其他方案的对比中可以看出一些优势，在交换机负载可控的范围内，减小了控制负载，更新时间较快，且较其他方案来说其各项指标更均衡，有效地减小了易被忽视的交换机负载问题，总体上流表更新效果较好.