软件定义广域网中控制器部署与交换机动态迁移策略

郭烜成 林晖 叶秀彩 许传丰

摘 要：在软件定义广域网（SD-WAN）部署中，由于广域网（WAN）覆盖范围极大这一特性，单控制器部署策略无论在容量、负载还是安全方面都无法满足其需求，多控制器的部署成为必然趋势。而多控制器部署后整体网络的静态配置很难适应动态的网络流变化，从而造成控制器的负载不均衡，整体网络性能降低。针对上述问题，提出一种多控制器部署算法SC-cSNN，以有效减小控制器和交换机之间的传播时延;并提出一种基于时延、控制器容量以及控制器安全等特征的交换机动态迁移算法，以有效解决控制器超负载问题。仿真实验结果表明，SC-cSNN控制器部署算法的平均最大时延优于现有的基于k-means和基于谱聚类的控制器部署算法，交换机动态迁移算法从多特征的角度有效地解决了SD-WAN控制器负载不均衡的问题。

关键词：软件定义广域网;谱聚类;控制器部署;k邻近算法;交换机动态迁移

中图分类号： TP393

文献标志码：A

Abstract： Due to the wide coverage of the Wide Area Network （WAN）， the single-controller deployment of Software Defined-Wide Area Network （SD-WAN） cannot meet its needs in capacity， load and security， the deployment of multiple controllers becomes necessary. However， the static configuration of the whole network after the deployment of multiple controllers was difficult to be adapted to the change of dynamic network flow， which can easily lead to load unbalance of controllers， reducing the network performance. To solve this problem， a multi-controller deployment algorithm named SC-cSNN （Spectral Clustering-closeness of the Shared Nearest Neighbors） was proposed to reduce the propagation delay between the controller and the switch， and a dynamic switch migration method based on features such as time-delay， capacity and security was proposed to solve the problem of controller overload. Simulation results indicate that compared with existing controller deployment algorithms based on k-means and spectral clustering， the multi-controller deployment algorithm and the dynamic switch migration method can effectively minimize the average maximum delay between the controller and the switch and solve the problem of controller overload.

Key words： Software Defined-Wide Area Network （SD-WAN）; spectral clustering; controller deployment; k-Nearest Neighbor （kNN） algorithm; switch dynamic migration

0 引言

軟件定义网络（Software Defined Network， SDN）是一种逻辑上集中控制的新型网络架构。与传统网络相比，软件定义网络的最大区别在于数据平面与控制平面的解耦合，控制平面和数据平面不再相互依赖[1]。传统的网络设备是一个封闭的系统，其数据层面和控制层面是紧耦合的[2]，如图1所示。

随着用户需求的增加，网络急需更多的可编程能力来解决新业务快速部署的问题。为获取更多的网络可编程能力，高效且可行的途径就是将数据层面及控制层面相互分离，通过开放的可编程的接口来实现网络控制。软件定义网络架构正完美地契合了该特性，其架构如图2所示。

软件定义广域网（Software Defined-Wide Area Network， SD-WAN）是将软件定义网络的特性应用于管理广域网中。相比传统广域网，软件定义广域网能有效降低网络开支，大幅度提升网络互连。软件定义广域网具有范围大、覆盖广的特性，现有的单控制器集中式控制的部署策略在很大程度上限制了网络的灵活性和可扩展性，继而出现了多控制器部署。如何实现逻辑上集中物理上分散的多控制器部署是多控制器部署问题的关键。现有的方案是将网络划分为多个不相交的子域，每个子域由独立的控制器集中控制，即从一开始就通过不同的特征确定分区，再确定控制器的最优部署位置[3]。部署后由于流量分布的不确定性，往往会出现“大象流”和“小象流”的情况，导致子域内控制器超载。先前的控制器部署策略已达不到更好的效果，故提出了根据流的大小对交换机进行动态迁移的解决方案。

1 相關工作

近年来，软件定义网络多控制器部署问题以及交换机动态迁移问题引起了越来越多学者的关注[4]。

对于多控制器部署问题，目前主流的解决方案是将网络划分为多个不相交的子域，每个子域放置一个控制器或控制器集进行控制。在该问题上，时延、部署代价、控制器容量、负载均衡均可作为优化目标，其中，时延最为学者所关注。最早提出控制器部署问题的学者Heller 等[5]主要以平均时延和最大时延作为优化目标，采用了贪心算法进行部署。文献[6]中提出了

网络聚类粒子群优化（Network Clustering Particle Swarm Optimization， NCPSO）控制器部署算法，该算法以最小时延以及负载均衡作为部署依据，将节点分区和粒子群算法相结合进行部署。文献[7]中提出了在每个子域中放置一个控制集合，该控制器集合由主控制器及其从属控制器组成，该方案提升了整个架构的可伸缩性，解决了控制器的过载问题。Wang等[8]以传播时延和排队时延作为优化目标提出了改进的k-means算法，该算法从一个分区开始逐次增加分区数量来进行迭代从而确定每个分区中的控制器位置。

在软件定义网络交换机动态迁移方面，Rath 等[9]提出了基于博弈的控制器优化部署方法，该方法将每一个控制器当作一个游戏参与者，通过参与游戏计算自身的收益并根据收益情况关闭控制器来实现负载均衡。Yao 等[10]根据控制器的负载情况提出了向邻居域迁移控制器的方法，以达到负载均衡的目标。

2 软件定义广域网中多控制器部署

2.1 控制器部署模型

软件定义广域网中多控制器部署策略主要采用网络分区的思想将网络分成多个不相交的子域，再将传播时延作为优化目标对每个子域进行控制器的部署[11～13]。对于具有多个节点以及多条链路的物理网络来说，其拓扑图可以通过一个无向图G（V，E）表示[14]，其中V是交换机的集合，E是交换机间物理链路的集合。两个节点m，n之间的距离可以表示为d（m，n）（m，n∈V）。整个网络可分为k个区域，每个网络分区定义为SDNi（Vi，Ei）。该定义满足式（1）和式（2），分别表示分区的覆盖区域为整个网络，分成的每个区互不相交。

5 结语

本文针对广域网中SDN控制器部署问题提出了一种SC-cSNN控制器部署算法，该方法能够尽可能地缩小平均最大时延。其次，针对SDN中交换机动态迁移问题提出了一种基于多特征的交换机迁移方法，避免由于负载不均引起的整体网络性能问题。仿真实验结果表明，SC-cSNN控制器部署算法的平均最大时延优于现有的基于k-means和基于谱聚类的控制器部署算法;基于kNN的交换机动态迁移算法从多特征的角度有效地解决了SDN控制器负载不均衡的问题。下一步研究计划将控制器排队时延、交换机转发时延纳入考虑范围，最小化其综合时延;并从控制器安全角度出发，提出一种更为安全且高性能的负载均衡方案。

参考文献：

[1] FEAMSTER N， REXFORD J， ZEGURA E. The road to SDN： An intellectual history of programmable networks [J]. ACM SIGCOMM Computer Communication Review， 2014， 44（2）： 87-98.

[2] 张朝昆，崔勇，唐翯祎，等.软件定义网络（SDN）研究进展[J].软件学报，2015，26（1）：62-81. （ZHANG C K， CUI Y， TANG H Y，et al. Stat-of-the art survey on Software-Defined Network （SDN）[J]. Journal of Software， 2015， 26（1）：62-81.）

[3] ZHANG Y， CUI L， WANG W，et al. A survey on software defined networking with multiple controllers [J]. Journal of Network and Computer Applications， 2018， 103： 101-118.

[4] WANG G D， ZHAO Y X， HUANG J， et al. The controller placement problem in software defned networking： a survey [J]. IEEE Network， 2017， 31（5）：21-27.

[5] HELLER B， SHERWOOD R， MCKEOWN N. The controller placement problem [C]// Proceedings of the First Workshop on Hot Topics in Software Defined Networks. New York： ACM， 2012： 7-12.

[6] LIU S， WANG H， YI S W， et al. NCPSO： a solution of the controller placement problem in software defined networks [C]// Proseedings of the 2015 International Conference on Algorithms and Architectures for Parallel Processing， LNCS 9530. Cham： Springer， 2015： 213-225.

[7] ZHAO Z， WU B. Scalable SDN architecture with distributed placement of controllers for WAN [J]. Concurrency and Computation： Practice and Experience， 2017， 29（16）： e4030.

[8] WANG G， ZHAO Y， HUANG J， et al. An effective approach to controller placement in software defined wide area networks [J]. IEEE Transactions on Network & Service Management， 2018， 15（1）： 344-355.

[9] RATH H K， REVOORI V， NADAF S M， et al. Optimal controller placement in software defined networks （SDN） using a non-zero-sum game [C]// Proceedings of the 2014 IEEE 15th International Symposium on World of Wireless， Mobile and Multimedia Networks. Piscataway， NJ： IEEE， 2014： 1-6.

[10] YAO L， HONG P， ZHANG W， et al. Controller placement and flow based dynamic management problem towards SDN [C]// Proseedings of the 2015 IEEE International Conference on Communication Workshop. Piscataway， NJ： IEEE， 2015： 363-368.

[11] 覃匡宇，黃传河，王才华，等.SDN网络中受时延和容量限制的多控制器均衡部署[J].通信学报，2016，37（11）：90-103. （QIN K Y， HUANG C H， WANG C H， et al. Balanced multiple controllers placement with latency and capacity bound in software-defined network[J]. Journal on Communications， 2016， 37（11）： 90-103.）

[12] SALLAHI A， ST-HILAIRE M. Optimal model for the controller placement problem in software defined networks [J]. IEEE Communications Letters， 2015， 19（1）： 30-33.

[13] KUANG H L， QIU Y W， LI R F， et al. A hierarchical K-means algorithm for controller placement in SDN-based WAN architecture [C]// Proceedings of the 10th International Conference on Measuring Technology and Mechatronics Automation. Washington， DC： IEEE Computer Society， 2018： 263-267.

[14] WANG G， ZHAO Y， HUANG J，et al. A k-means-based network partition algorithm for controller placement in software defined network [C]// Proceedings of the 2016 IEEE International Conference on Communications. Washington， DC： IEEE Computer Society， 2016： 1-6.

[15] YE X， SAKURAI T. Robust similarity measure for spectral clustering based on shared neighbors [J]. ETRI Journal， 2016， 38（3）： 540-550.

[16] BARI M F， ROY A R， CHOWDHURY S R， et al. Dynamic controller provisioning in software defined networks [C]// Proceedings of the 9th International Conference on Network and Service Management. Washington， DC： IEEE Computer Society， 2013： 18-25.

[17] HOCK D， HARTMANN M， GEBERT S， et al. POCO-PLC： Enabling dynamic pareto-optimal resilient controller placement in SDN networks [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2014： 115-116.

[18] YAO G， BI J， LI Y L， et al. On the capacitated controller placement problem in software defined networks [J]. IEEE Communications Letters， 2014， 18（8）： 1339-134.

[19] ANAND N， BABU S， MANOJ B S. On detecting compromised controller in software defined networks [J]. Computer Networks， 2018， 137： 107-118.

[20] Internet2. Layer2 services[EB/OL]. [2017-12-23].http：//www.internet2.edu/network/ose/.