多种群粒子群的SDN控制器故障恢复算法

朱国晖，刘茹文，杨 瑛

西安邮电大学 通信与信息工程学院，西安 710121

软件定义网络（software defined network，SDN）实现了控制平面与数据平面分离，采用了中心化的控制器对网络进行集中式管理[1]，相比于传统网络，有效地提高了网络的灵活性。SDN在快速发展的同时也面临着一些挑战，如控制器的可扩展性，SDN的故障恢复等[2]。其中SDN的故障恢复是不可忽视的问题，SDN网络中的故障主要存在于数据平面和控制平面。在控制平面中，一旦控制器出现故障，若没有其他正常工作的控制器来接管失控的交换机，则会影响整个故障控制器所管理的网络域内的信息传输。因此为了避免因单控制器故障而造成网络性能下降的现象，在SDN网络中大多都采用分布式的架构[3-4]，在整个网络中同时部署多个控制器，每个网络域内都有一个子控制器来管理域内的所有交换机。当某个子控制器发生故障时，该控制器下的失控交换机可以迁移到其他正常工作的子控制器上，从而保证网络的正常运行。那么在交换机迁移过程又如何在控制器不发生超载的情况下，最小化交换机到控制器之间的平均传播时延成为了研究的热点问题。

文献[5]提出了基于控制时延可靠性的控制器部署策略以提升网络的可靠性。文献[6]针对大规模SDN网络，采用改进的标签传播算法（LPA）将网络划分成多个子域，然后在子域中分别部署控制器。文献[7]提出了一种蝙蝠算法进行多控制器的部署，算法在迭代时不断地优化平均控制时延，限制控制器负载利用率保证了控制器间的负载均衡。文献[8]提出了基于负载均衡的多控制器部署算法。以上文献均是针对控制器部署问题展开研究，没有考虑到控制器发生故障的情况。

文献[9]提出了一种主从模式的高可用动态部署算法，通过在邻域内选取从控制器来接管失控交换机，保证了故障恢复时延较短。文献[2]提出了一种带内通信场景下平面式的多控制器容错架构，单控制器控制单个自治域，在可接受的时间内完成控制器故障的快速恢复。文献[10]提出了一种SDN控制器节点故障恢复的部署策略，采用熵权多目标决策方法，对控制器进行故障恢复从而保证网络的正常运行。文献[11]提出了一种启发式控制器故障恢复算法，该算法在保证控制器不发生超载的情况下，控制备份控制器的激活数量，节省修复开销。但是算法的执行效率不高，不能很快地完成失控交换机的迁移过程。文献[12]提出了一种基于控制网络生存性的备份控制器放置方法，没有考虑到备份控制器的数量和负载容量。文献[13]提出了一种基于共享机制的备份控制器部署方法即多个网络域共享一定数目的备份控制器，考虑了备份控制器的数目和备份控制器的放置能够合理地利用网络资源，但是会导致部分控制器超载现象。

目前，粒子群优化算法可以解决备份控制器的部署问题，但在解决这个问题时，容易陷入局部最优，算法的复杂度高，使得故障恢复时间较长。为了更好地部署备份控制器，本文把机械臂路径规划中的多种群粒子群算法应用在SDN控制器故障恢复的场景中。多种群粒子群算法是一种具有预选择与交互机制的精英种群引导的算法[14]。

多种群粒子群算法将每个备份控制器当作粒子，经过迭代演化得到备份控制器的最优位置，使得备份控制器与待迁移交换机的平均传播时延最短。

本文主要工作如下：

（1）在多控制器网络环境下，若一个子网络域内的控制器发生故障，首先采用备份控制器的挑选算法，从其他正常的子控制器中挑选出能够容纳失控交换机负载的备份控制器集合。

（2）提出了一种基于多种群粒子群的备份控制器调整算法，通过设置不同的子种群数，观察对备份控制器部署的影响，并选出了该算法的最优参数，为证明多种群蚁群算法在求解备份控制最优位置时，能够很快跳出最优解，使得故障恢复时间较短，并将该算法与其他故障恢复算法进行对比实验。

1 模型建立

本文以一个简单的多控制器构架图为示例进行分析说明，如图1所示主控制器控制整个SDN网络域，同时作为控制器1、2、3的通信桥梁，掌握整个网络域中的动态信息。控制器1、2、3分别掌管自己所管辖的网络域。假设控制器1出现了故障，则需要将该控制器所管理的网络域内的失控交换机重新托管给其他正常工作的控制器管理。

图1 一个简单的多控制器架构图Fig.1 Simple multi-controller architecture of SDN

将SDN网络构建成一张无向图G=(V,E)，其中V代表网络中交换机的集合V=(v1,v2,…,vn),n=|V|表示交换机的个数；E代表网络中的链路集合；将网络划分成q个子网络域，每个子网域内包含任意p(1≤p≤n)个交换机，整个网络包含1个主控制器和q个子控制器组成，C表示控制器集合C=(c1,c2,…,cm)，整个网络有m=||C个控制器；任意两个子域间互不重叠，并且每个交换机只属于某个子网络域。

定义1（交换机与控制器的连接矩阵X）X=[xi,j]n×n表示控制器与交换机之间的映射关系，如公式（1）所示：

定义3（交换机与控制器之间的直线距离d(vi,cj)）在SDN网络中，计算两个节点的距离需要考虑到地面弧度[15]。假设地球为一个半径为r的球体，节点vi、cj的经度分别为αi、αj，节点vi、cj的纬度分别为βj、βj。且规定计算经度时，东经为正，西经为负；计算纬度时，南纬90°为正纬度值，北纬90°为负纬度值[17]，交换机与控制器之间的直线距离d(vi,cj)如公式（3）所示：

定义4（交换机与控制器之间的平均传播时延Lavg）在SDN网络中，交换机与控制器的物理距离是影响传播时延的主要因素，实验过程中假设每个交换机到控制器之间的传输速度v都一样，因此平均传播时延Lavg可以用所有交换机vi∈S到相应控制器cj∈C最短传输时间的平均值来表示，如公式（4）、（5）所示：

其中，t(vi,cj)表示任意两个节点间（交换机与控制器）最短传输时间。

定义5（每个控制器剩余负载Rj）本文不考虑控制器之间的差异性，所有控制器都有相同的负载容量、处理能力等。由于控制器负载可近似由Packet-In消息的计算开销组成，所以上述控制器使用的负载均用当前Packet-In消息到达速率来表示[2]。本文通过主控制器集中计算当前每个控制器剩余负载，其计算公式如式（6）所示：

目标函数如式（7）所示，最小化交换机与控制器之间的平均传播时延Lavg。约束条件（8）表示交换机迁移后的连接矩阵，k表示交换机的个数；约束条件（9）保证控制器的剩余负载大于等于0；约束条件（10）保证网络中的交换机在任何情况下只分配给一个主控制器；约束条件（12）保证了恢复过程中所有的备份控制器都属于原有的主控制器。其中yi表示控制器ci为备份控制器时值为1，否则为0。

2 算法设计

算法的总体流程图如图2所示，算法步骤如下：

图2 算法的总体流程图Fig.2 Overall flow chart of algorithm

步骤1首先挑选出能够容纳失控交换机负载的备份控制器集合。

步骤2根据Packet-In消息速率大小对失控交换机集合进行降序排列，优先为Packet-In消息速率较大的交换机进行迁移（原因是交换机产生的Packet-In消息速率越大，说明其与控制器间的数据交互越频繁，应当优先处理）。

步骤3采用多种群粒子群优化算法对备份控制器进行动态调整，其中包括：

（1）初始化

设置失控交换机受备份控制器控制的数量为0，经过实验分析设置子种群的数量为3，种群大小Number=100，实验的测试次数为100次，最终迭代次数为10 000次。学习因子c1、c2代表了粒子向自身极值和全局极值推进的加速权值，通常把c1、c2设置为2.0，代表对两个方向的同等重视，粒子的速度决定移动的方向和距离，一般设置粒子的最大飞行速度vmax为1.7[14]。

（2）局部最优

首先从每个子种群中挑选出n个粒子组成精英种群，让子种群和精英种群分别进行演化。在其子种群的演化过程中计算出每个粒子的适应度函数值，并得到子种群的个体最优值，然后把3个个体最优值进行比较，并输出一个局部最优值。在精英种群演化过程中，不断用子种群最优的粒子去替换精英种群中表现劣于子种群表现最优的粒子，更新精英种群，并形成新的精英种群，最后输出精英种群的个体最优值。

（3）全局最优

将子种群中的局部最优值和精英种群中的个体最优值进行对比分析，得到全局最优值，那么此时全局最优值就是备份控制器与待迁移交换机的最优匹配对。

（4）终止迭代

判断所有待迁移的交换机是否完成分配。

多种群粒子群优化算法中的适应度函数如公式（13）所示，在演化过程中粒子的更新速度如（14）、（15）所示：

公式（13）中f(yi)表示备份控制器的总数。公式（14）、（15）中vk表示k时刻粒子的速度，r1、r2为随机序列，且r1∈[0,1,]r2∈[0,1]，ak表示k时刻粒子的位置，ωk表示惯性权重，k=0,1,…,100。

2.1 备份控制器挑选算法

在一个子网络域中，当控制器出现故障时，其管理域内的交换机需要迁移到其他正常的子控制器上，以保证网络的正常运行。而在迁移的过程中，需要确保正常的子控制器在接管失控交换机时不出现负载震荡现象。

如图3所示，失控的交换机负载为3个单位，从图中可以看出，控制器2有足够的剩余负载可供选择，如果控制器1和控制器3去接管失控交换机将会出现剩余负载不足的情况，给网络系统带来负载震荡现象。

图3 控制器之间的负载分配Fig.3 Load distribution between controllers

因此为确保正常的子控制器在接管失控交换机时不出现负载震荡现象，需满足待迁移交换机的总负载小于正常的子控制器的剩余负载，即公式（16）表示。

算法1的具体步骤如下：

算法1备份控制器挑选算法

输入：失控交换机集合Vuc，从控制器集合Cslave输出：备份控制器集合Cbp

1.|Vuc|=n1,n1∈(0,n);|Cslave|=m1//初始化从控制器数目和失控交换机的数目

2.主控制器集中获取每个子控制器的剩余负载大小

4.挑选出能够满足条件的备份控制器。

5.output：Cbp//备份控制器集合Cbp

2.2 基于多种群粒子群的备份控制器调整算法

在算法1的基础上提出了基于多种群粒子群的备份控制器调整算法。该算法将备份控制器抽象为粒子，然后算法一直循环迭代演化，直到跳出局部最优找到全局最优解即使得失控交换机与备份控制器之间的平均传播时延最小。具体过程如算法2所示。

算法2基于多种群粒子群的备份控制器调整算法

输入：备份控制器集合Cbp，失控交换机集合Vuc

输出：失控交换机与备份控制器的匹配对集合A1

3 实验分析

3.1 实验环境

本文采用的实验环境为Intel®Core™ i5-4570 CPU@3.20 GHz，16.00 GB内存，操作系统Windows10版本（64位），算法均在MATLAB2018a软件上进行仿真实验。实验的控制器采用OpenDaylight，用到的虚拟机Mininet在软件Ubuntu16.04上进行操作，并使用cbench工具测试控制器的负载能力。

3.2 实验结果

3.2.1 多种群粒子群算法在不同子种群个数下的结果分析

首先，对多种群粒子群算法在不同参数下进行仿真，仿真结果如表1，表示在不同子种群个数下的演化结果。

表1 在不同子种群个数下的适应度比较Table 1 Comparison of fitness values in different subpopulations ms

由表1知道，只有子种群的个数为3时，求出的适应度函数值最小即备份控制器与待迁移交换机之间的平均传播时延最小。算法在迭代次数为10 000次时，适应度函数值趋于稳定。

3.2.2 仿真验证

为了验证该算法的合理性，本文采用了不同规模的网络对算法性能进行验证，实验过程中采用了5个不同规模的网络拓扑，每个拓扑的差异性体现在失控交换机的数量不一样，其中网络拓扑信息如表2所示。实验中采用cbench工具对控制器的负载容量进行了测试，结果显示本文中控制器的容量限制为5 000条packet_in消息范围内，交换机的负载保持在100条/s到200条/s的信息。

表2 网络拓扑信息Table 2 Network topology information

实验过程中为了保证实验结果的正确性，本文在每一种网络拓扑结构下进行10次实验，并取10次实验的平均值作为实验结果。

将本文提出的算法（CFRS）与BCS[11]和SBC[13]算法进行对比。BCS是备份控制器选择算法，在满足负载约束的前提下找到最少数量的备份控制器集合，节约了控制器的激活开销；SBC是一种基于共享机制的控制器故障恢复算法，多个网络域共享一定数目的备份控制器。本文综合考虑了控制器负载容量和平均传播时延，在满足控制器容量的前提下，动态调整备份控制器的位置以达到全局最优。本文分别从故障恢复时延和控制器的负载利用率两个方面验证CFRS算法的有效性。

（1）故障恢复时延

图4为不同算法的故障恢复时间对比图，横坐标表示每一个网络拓扑中失控交换机的个数，纵坐标表示每个网络拓扑在10次实验中取得的平均恢复时间。随着失控交换机数量的增加，故障恢复时间也随之而增加。本文提出的CFRS算法明显缩短了故障恢复时间。相比于BCS和SBC算法，该算法在故障恢复时延上最大减小了35%，平均减小了26%，其原因在于多种群粒子群算法根据目标函数对备份控制器的位置进行不断的优化，采用了预选和交互的机制让算法很快跳出局部最优达到全局最优，节约了搜索时间，算法效率高；而且迁移后的控制链路平均时延较低，因此故障恢复时间较短。SBC采用的粒子群算法解决备份控制的数量与位置问题，在交换机迁移的过程中容易陷入局部最优，导致故障恢复时间比较长。BCS虽然考虑了减少控制器和交换机之间的时延，但算法的执行效率比较低。

图4 故障恢复时间Fig.4 Fault recovery time

（2）备份控制器的负载性能

由于在交换机的迁移过程中容易出现负载分配不均而造成控制器超载，所以本文给出了以下两种性能指标来验证控制器的负载利用率。

指标1为备份控制器需要接管的交换机负载占总失控交换机负载的比值，用字母w1表示；指标2为备份控制器接管交换机负载占该控制器剩余负载的比值，用字母w2表示。

图5给出了备份控制器需要接管的交换机的负载占总失控交换机负载的比值结果，实验结果表明，本文所提的CFRS算法中，每个备份控制器所接管的失控交换机的个数基本一致。其原因是该算法不断地更新每个子控制器的剩余负载，在每个子控制器不发生超载的情况下，实现了失控交换机负载的均衡分配。SCB算法没有考虑到负载均衡从而导致每个备份控制器在分配失控交换机的个数存在明显的差异，分布不均匀。

图5 占总负载比值Fig.5 Ratio to total load

图6给出了备份控制器接管交换机负载占该控制器剩余负载的比值结果，实验结果表明，三种算法使用了相同数目的备份控制器完成了失控交换机的迁移。CFRS算法中的每个备份控制器都没有出现负载震荡现象，并充分利用了每个备份控制器的剩余负载，其原因是在算法1中保证了备份控制器的负载在合理范围内，同时在算法2中实时地更新子控制器的剩余负载。SBC算法采用了共享机制的控制器故障恢复方法，其备份控制器接管交换机负载占该控制器剩余负载的比值结果偏高，导致部分备份控制器超载。而BCS算法虽然考虑到了备份控制器的负载，但是并没有对备份控制器的剩余负载进行实时更新。

图6 占剩余负载比值Fig.6 Ratio to remaining load

4 结束语

本文针对多控制器网络环境下的单一控制器发生故障问题，提出了一种基于多种群粒子群的SDN网络控制器故障恢复算法。实验结果表明，与现有的控制器故障恢复算法相比，本文所提算法在恢复时间、控制器负载利用方面均有所提升。本文局限于多控制器网络环境下的单一控制器发生故障的情况，没有考虑到多个控制器同时发生故障的情况，因此下一步的工作是当多个控制器发生故障时，继续完善故障恢复机制，进一步提高网络的可靠性。