軟件定義廣域網中控制器部署與交換機動態遷移策略

郭烜成 林暉 葉秀彩 許傳豐

摘 要：在軟件定義廣域網（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/.