一种考虑软件定义网络控制节点故障的控制器部署和交换机迁移方法

伊 鹏 刘邦舟 王文博 张少军



一种考虑软件定义网络控制节点故障的控制器部署和交换机迁移方法

伊 鹏 刘邦舟*王文博 张少军

(国家数字交换系统工程技术研究中心 郑州 450002)

在软件定义网络(SDN)中，若控制节点发生不可恢复的故障，则相关交换机需向其他控制节点迁移，这将导致网络性能下降。针对这一问题，该文提出一种考虑SDN控制节点故障的控制器部署和交换机迁移方法。与现有算法仅优化交换机迁移方法不同，该方法同时考虑控制器部署位置的影响。首先利用标号传播算法构造备选子集并划分双层子集，然后在每个子集中选取合适位置部署控制器，最后为子集内节点分配相应的master和slave控制器。实验结果表明，与现有算法相比，所提方法可有效解决交换机迁移后控制器超载的问题；通过调整参数，权衡控制器故障前后网络性能，可明显改善交换机迁移后的控制链路平均时延。

软件定义网络；控制器部署；交换机迁移；控制节点故障

1 引言

软件定义网络(Software Defined Networking, SDN)[1]将控制平面和数据平面分离，方便网络的管理和维护，但同时也导致了交换机对控制器的依赖性。SDN网络中的组件主要包括通信链路、交换机和控制器。其中，控制器故障的影响最大，若无法及时从控制器获取信息，所属交换机将无法处理流表中未指定的网络数据流[2]。为减小控制器单点故障造成的影响，当前网络多采用分布式架构[3,4]，通过部署多个控制器提高网络的可靠性。交换机可以在必要时在控制器间迁移，实现控制器的故障备份。如何保证交换机迁移后的网络性能已经成为SDN控制层面设计的一大挑战。

近年来，控制器故障恢复问题成为研究热点。如文献[5]提出一种故障检测和恢复机制SPIDER，可以快速检测SDN节点、链路故障并实现重路由；文献[6]提出ElastiCon，通过动态调整控制器的负载，保证交换机迁移前后控制器的负载均衡；文献[7]提出通过构造更鲁棒的转发树，增强控制平面的可靠性；文献[8]提出两种计算控制器备份列表的方法，其一是根据最短距离确定备份控制器，其二是根据控制器剩余容量确定备份控制器；文献[9]将原交换机迁移问题优化成为控制器的热备份及选举问题，综合考虑信息交互、失联性、负载失衡和跨域通信等代价，改善控制器负载均衡程度和交换机跨域通信问题。

过往研究大多通过优化交换机的迁移方法，降低控制链路通信时延或保证控制器负载均衡，但忽视了控制器的部署位置这一因素。如果仅对交换机迁移方法进行优化，而不考虑控制器部署位置的合理性，将使交换机迁移策略受到限制，同时也使优化效果受到影响。对此，本文提出一种考虑SDN控制节点故障的控制器部署和交换机迁移方法(Controller Placement and Switch Immigration Strategy for SDN controller failure, CPSI strategy)。CPSI主要分为2个步骤，步骤1为网络双层子集的划分，首先利用标号传播算法[10](Label Propagation Algorithm, LPA)构造备选子集，然后选取符合条件的子集构成双层子集。步骤2为控制器部署和备份，先在子集中选取合适位置部署控制器，再为节点分配相应的master和slave控制器。基于公共拓扑Internet2[11]和topology zoo[12]的仿真可发现，与现有算法相比，交换机迁移后的控制器超载问题得到明显改善；通过调整参数，可以有效地权衡控制器故障前后控制链路平均时延。

2　模型定义

控制器在网络中存在equal, master和slave 3种不同身份[13]。其中，equal仅作为一种过渡状态；master控制器对于每个交换机仅有1个，可独立控制交换机。Slave控制器对交换机仅有读权限，因此可作为master的备份，当master故障时，所属交换机迁移到相应的slave上。应用场景如图1，假设当控制器1发生的故障时，需根据备份设定，将交换机1~5迁移至2,6~9迁移至3，此时2和3成为相应交换机的master控制器。

定义4 控制链路平均时延。 大规模网络中节点间距离较远，传输距离是影响信号传播时延的主要因素，可用节点间距离衡量控制链路消息的传播时延。已知连接矩阵，设式(4)中为任意两节点间最短路径的长度，则控制链路平均时延可用网络中所有交换机到相应控制器最短路径长度的平均值表示：

(3)

(5)

针对控制器故障，交换机迁移后的网络性能优化问题，本文提出如下模型：

(7)

(8)

(10)

(11)

式(6)是模型的目标函数，最小化交换机迁移后网络的控制链路平均时延，其中决策变量为控制器连接矩阵和交换机迁移矩阵；式(7)给出了、和三者间的函数关系，其中为交换机迁移后的连接矩阵；式(8)通过限制控制器故障前的控制链路平均时延，可实现对控制器故障前后控制链路平均时延的有效权衡；式(9)保证在控制器不发生超载；式(10)保证网络中的交换机在任何情况下都只分配给1个master控制器；式(11)约束了连接状态矩阵的值，保证其只存在1或0，即连接或不连接两种状态。

3 算法分析

3.1算法描述

本节介绍CPSI算法，分为2个步骤：一是双层子集的划分(表1)；二是控制器的部署和分配(表2)。此处引入子集的概念，本质上子集与子域相同，但为区分算法过程中使用的中间变量和最终的交换机划分结果，本文将CPSI算法步骤中出现的交换机集合命名为子集，而将最终结果中的交换机集合命名为子域。

步骤1 CPSI算法主要流程如下。利用LPA算法[10]构造备选子集，选取控制链路平均时延最小的子集构造双层子集。LPA算法计算复杂度与网络规模仅呈线性关系，因此利用LPA可在有限时间内构造足够规模的备选子集。为控制两层子集间的相似度，现定义子集搜索范围参数和子集平均相似度。其中，限制备选子集的选取范围；衡量任一子集与相邻子集间的平均相似度，其中和表示重叠部分分别占两个子集的比例，表示任意两个子集间的相似度：

(13)

(14)

算法首先利用LPA算法，将网络划分成多个子集(行2)，并选取负载不超过控制器最大容量的子集加入备选子集(行3~4)。重复这一过程至备选子集达到设定的规模；然后将控制器按照容量大小降序排列(行9)，并依次循环选取(行11)，优先部署大容量控制器；将备选子集中的子集按平均相似度的大小升序排列(行12)，并在前元素中选取控制链路平均时延最小且负载尽可能大的子集加入双层子集(行13~14)；将已经被包含两次的节点从备选子集和待选节点集合中删除(行17~21)，保证每个节点只属于两个子集；重复以上步骤至所有的节点都已经被包含两次(行10)；最后输出生成的双层子集划分结果(行23)。如表1所示。

步骤2 在子集中搜索使控制链路平均时延最小的位置来部署控制器(行2)，从而保证交换机迁移后网络的性能；由于每个节点同时属于两个子集(行6)，故分别计算到这两个子集中控制器的最短距离，选取其中距离近的控制器作为master，距离远的作为slave(行7~11)，遍历网络中的所有节点(行5)，完成控制器的分配；最后根据master和slave的分配情况构造连接矩阵以及交换机迁移矩阵(行13)。如表2所示。

3.2复杂度分析

步骤1中，行2基于LPA算法对网络进行子域划分，其时间复杂度为[10]，行3~7的最大循环次数为，行1~8的最大循环次数为，则行1~8的时间复杂度为；行9排序的时间复杂度为；行12计算平均相似度并排序的时间复杂度为，行14的时间复杂度为，行17~22次循环的时间复杂度为，行10~22的最大循环次数为，其时间复杂度为。故步骤1的整体时间复杂度为。步骤2中，行1~4分别在每个子集中选取合适位置部署控制器，时间复杂度为；行5~12分别为每个节点分配控制器，时间复杂度为，故步骤2的整体时间复杂度为。综上，CPSI算法的时间复杂度为。

表1 划分双层子集

表2控制器的部署及分配

4 实验结果分析

4.1 实验环境及参数

针对本文实验的软硬件环境及相关参数设定，做出如下说明：

(1)硬件环境为基于Intel Core i7-3770 CPU 3.40 GHz, RAM 4 GB的个人台式电脑；相关算法均在MATLAB 2013软件上进行模拟仿真。

(2)为简化实验过程，在不影响实验结果的前提下，做出以下设定：每个交换机的负载大小仅影响其所在子域的负载，为其分配对应容量的控制器即可，对算法其他部分的计算无影响，因此可设所有交换机的负载均为；控制器容量仅影响子域与控制器的分配，对算法其他部分的计算无影响。因此，为保证任一控制器的故障均不会造成超载问题，所有控制器的总容量至少为当前网络总负载的2倍，故实验中可设每个控制器的容量均为。交换机负载和控制器容量在实际应用中可根据实际情况具体设定。

4.2 仿真分析

本文将CPSI算法和其他几种算法进行比较，由于直接研究此方向的文献较少，故借鉴了相关的控制器部署算法和交换机迁移算法。文献[4,14]分别提出了两种控制器部署方案，其中文献[4]提出了最小切算法(Min-Cut Algorithm, MCA)，将网络划分成多个子域，使得子域边界上的通信链路切数最小；文献[14]提出最小中心算法(Minimum-median Algorithm, MKA)，遍历所有可选节点，选取其中个节点部署控制器，并将交换机连接至距离最近的控制器。文献[8]提出了2种交换机迁移方案，一是基于近邻的启发式算法(Proximity-Based Heuristic, PBH)，交换机迁移至时延最短的控制器；二是基于剩余容量的启发式算法(Residual Capacity-Based Heuristic, RCBH)，交换机迁移至容量最大的控制器。

基于以上文献，本文设计了4种对照算法，最小切—近邻算法(MC-PB)，最小中心—近邻算法(MK-PB)，最小切—剩余容量算法(MC-RCB)和最小中心—剩余容量算法(MK-RCB)，分别对应两种控制器部署方案和两种交换机迁移方案构成的4种不同组合。

首先，针对交换机迁移后控制器负载的问题，在拓扑Internet2, Geant2009和Canerie上分别对上述5种算法进行研究。表3中为控制器的数量，表中数据为当网络中任一控制器发生故障后，其余控制器超载数量之和。CPSI算法中限制单个子域的最大负载(控制器作为master和slave连接的交换机负载总和)不超过控制器容量，因此不会发生超载状况。采用RCBH迁移算法的MC-RCB算法和MK- RCB算法会优先将交换机迁移至剩余容量最大的控制器，因此和CPSI算法一样都可以有效地解决交换机迁移后控制器超载的问题。但采用PBH迁移算法的MC-PB 算法和MK-PB算法由于未考虑控制器容量，故某些控制器故障将导致相邻的被迁移控制器超载。

然后，基于Internet2拓扑比较5种算法的控制链路平均时延，其中CPSI算法选取，保证故障前后网络性能相对均衡。图2(a)为基于连接矩阵的控制链路平均时延，通过比较可以发现，采用MKA算法的MK-PB和MK-RCB算法性能最好，这是由于MKA穷举了控制器部署的所有可能情况，并选择了最优解，但此算法带来巨大的运算量，不适用于复杂的网络。MCA是一种启发式算法，以性能为代价，降低了运算量。CPSI算法在此方面的性能略差，这是因为CPSI通过调整参数，权衡控制器故障前后的控制链路平均时延，通过牺牲一定故障前的网络性能，换取交换机迁移后网络性能的提升。

表3超载控制器的数量

拓扑名Internet2Geant2009Canerie k 456784567845678 CPSI000000000000000 MC-RCB000000000000000 MK-RCB000000000000000 MC-PB011011112010211 MK-PB121021101111122

最后，利用Internet2和在topology zoo中选取的20个拓扑对CPSI算法进一步验证。横坐标为实验拓扑的名称。计算当控制器个数分别为(为拓扑节点数)时，上述5种算法基于交换机迁移后连接矩阵的控制链路平均时延的均值，并做归一化处理。实验结果如图4，对于所选取的21个拓扑，CPSI算法的平均时延都低于其余4种算法，对交换机迁移后控制链路时延的优化效果明显，说明了算法在不同拓扑上的适用性。

图3 比较对CPSI控制链路平均时延的影响

图4 不同拓扑下基于迁移后连接矩阵的归一化控制链路平均时延

5 结束语

本文针对SDN控制器故障，交换机迁移，导致网络性能下降的问题，提出一种考虑控制节点故障的控制器部署和交换机迁移方法。与传统的解决思路不同，CPSI算法不仅对交换机迁移方法进行优化，还对控制器部署策略进行了相应的优化。与现有算法相比，CPSI算法通过权衡控制器故障前后的网络性能明显改善了交换机迁移后控制链路平均时延，同时有效解决了交换机迁移导致的控制器超载问题。本文在SDN控制节点故障恢复问题中考虑控制器部署位置的影响是一种新的尝试，为解决此类问题提供了新思路。

[1] RAWAT D B, DANDA B, and REDDY R. Software defined networking architecture, security and energy efficiency: A survey[J].&, 2017, 19(1): 325-346. doi: 10.1109/COMST.2016.2618874.

[2] VISSICCHIO S, VANBEVER L, and BONAVENTURE O. Opportunities and research challenges of hybrid software defined networks[J]., 2014, 44(2): 70-75.

[3] HASSA S YEGANEH S, and GANJALI Y. Kandoo: A framework for efficient and scalable offloading of control applications[C]. Proceedings of the First Workshop on Hot Topics in Software Defined Networks, New York, NY, USA, 2012: 19-24.

[4] ZHANG Y, BEHESHTI N, and TATIPAMULA M. On resilience of split-architecture networks[C]. Global Telecommunications Conference (GLOBECOM 2011), Houston, TX, USA, 2011: 1-6.

[5] CASCONE C, POLLINI L, SANVITO D,. SPIDER: Fault resilient SDN pipeline with recovery delay guarantees[C]. 2016 IEEE NetSoft Conference and Workshops (NetSoft), Seoul, Korea, 2016: 296-302.

[6] DIXIT A, HAO F, MUKHERJEE S,. Towards an elastic distributed SDN controller[J]., 2013, 43(4): 7-12.

[7] PENG Yuhuai, GONG Xiaoxue, GUO Lei,. A survivability routing mechanism in SDN enabled wireless mesh networks: Design and evaluation[J]., 2016, 3(7): 32-38. doi: 10.1109/CC.2016. 7559073.

[8] MULLER L F, OLIVEIRA R R, LUIZELLI M C,. Survivor: An enhanced controller placement strategy for improving SDN survivability[C]. IEEE Global Communications Conference, Austin, TX, USA, 2014: 1909-1915.

[9] 王文博, 汪斌强, 陈飞宇, 等. 一种软件定义网络中的控制器热备份及选举算法[J]. 电子学报, 2016, 44(4): 913-919. doi: 10.3969/j.issn.0372-2112.2016.04.023.

WANG Wenbo, WANG Binqiang, CHEN Feiyu,. The controller hot backup and election algorithms in software defined networks[J]., 2016, 44(4): 913-919.

[10] 刘邦舟, 汪斌强, 王文博, 等. 针对大规模软件定义网络的子域划分及控制器部署方法[J]. 计算机应用, 2016, 36(12): 3239-3243. doi: 10.11772/j.issn.1001-9081.2016.12.3239.

LIU Bangzhou, WANG Binqiang, WANG Wenbo,. Domain partition and controller placement for large scale software defined network[J]., 2016, 36(12): 3239-3243. doi: 10.11772/j.issn. 1001-9081.2016.12.3239.

[11] Internet2 Open Science, Scholarship and Services Exchange [OL]. http://www.internet2.edu/, 2016.10.

[12] KNIGHT S, NGUYEN H X, FALKNER N,. The internet topology zoo[J]., 2011, 29(9): 1765-1775.

[13] MCKEOWN N, ANDERSON T, BALAKRISHNAN H,. OpenFlow: Enabling innovation in campus networks[J]., 2008, 38(2): 69-74. doi: 10.1145/1355734.1355746.

[14] HELLER B, SHERWOOD R, and MCKEOWN N. The controller placement problem[C]. Proceedings of the First Workshop on Hot Topics in Software Defined Networks. New York, NY , USA, 2012: 7-12.

Controller Placement and Switch Immigration Strategy for SDN Controller Failure

YI Peng LIU Bangzhou WANG Wenbo ZHANG Shaojun

(&,450002,)

In Software-Defined Networking (SDN), if a controller has unrecoverable failure, the related switches immigrate to other controllers, which degrades network performance. Concerning the above problem, a strategy of controller placement and switch immigration is proposed for controller failure. Different from the present algorithms which onlyoptimize switch immigration method, the proposed strategy also considers the influence of controller placement. Firstly, Label Propagation Algorithm (LPA) is used to construct alternate domains set and partition bilayer domains. Then, one controller is placed in each domain on properly selected situation. Finally, the switches are assigned to corresponding master and slave controllers. The experimental results show that controller overloading problem is well solved compared with the present algorithms. Network performance before and after failure can be traded off by adjusting parameters, which decreases average control path latency after switch immigration.

Software-Defined Networking (SDN); Controller placement; Switch immigration; Controller failure

TP393.2

A

1009-5896(2017)08-1972-07

10.11999/JEIT161216

2016-11-10；

改回日期：2017-03-24；

2017-05-02

刘邦舟 liubangzhou@163.com

国家973计划项目(2012CB315901, 2013CB329104)，国家自然科学基金(61572519, 61502530)，国家863计划项目(2013AA013505, 2015AA016102)

The National 973 Program of China (2012CB315901, 2013CB329104), The National Natural Science Foundation of China (61572519, 61502530), The National 863 Program of China (2013AA013505, 2015AA016102)

伊 鹏： 男，1977年生，教授，研究方向为宽带信息网、可重构柔性网络.

刘邦舟： 男，1992年生，硕士生，研究方向为SDN控制器部署.

王文博： 男，1991年生，硕士，研究方向为SDN弹性控制.

张少军： 男，1989年生，博士生，研究方向为SDN控制平面可扩展性.