軟件定義廣域網(wǎng)中控制器部署與交換機(jī)動態(tài)遷移策略

郭烜成 林暉 葉秀彩 許傳豐

摘 要：在軟件定義廣域網(wǎng)（SD-WAN）部署中，由于廣域網(wǎng)（WAN）覆蓋范圍極大這一特性，單控制器部署策略無論在容量、負(fù)載還是安全方面都無法滿足其需求，多控制器的部署成為必然趨勢。而多控制器部署后整體網(wǎng)絡(luò)的靜態(tài)配置很難適應(yīng)動態(tài)的網(wǎng)絡(luò)流變化，從而造成控制器的負(fù)載不均衡，整體網(wǎng)絡(luò)性能降低。針對上述問題，提出一種多控制器部署算法SC-cSNN，以有效減小控制器和交換機(jī)之間的傳播時延;并提出一種基于時延、控制器容量以及控制器安全等特征的交換機(jī)動態(tài)遷移算法，以有效解決控制器超負(fù)載問題。仿真實(shí)驗(yàn)結(jié)果表明，SC-cSNN控制器部署算法的平均最大時延優(yōu)于現(xiàn)有的基于k-means和基于譜聚類的控制器部署算法，交換機(jī)動態(tài)遷移算法從多特征的角度有效地解決了SD-WAN控制器負(fù)載不均衡的問題。

關(guān)鍵詞：軟件定義廣域網(wǎng);譜聚類;控制器部署;k鄰近算法;交換機(jī)動態(tài)遷移

中圖分類號： TP393

文獻(xiàn)標(biāo)志碼：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 引言

軟件定義網(wǎng)絡(luò)（Software Defined Network， SDN）是一種邏輯上集中控制的新型網(wǎng)絡(luò)架構(gòu)。與傳統(tǒng)網(wǎng)絡(luò)相比，軟件定義網(wǎng)絡(luò)的最大區(qū)別在于數(shù)據(jù)平面與控制平面的解耦合，控制平面和數(shù)據(jù)平面不再相互依賴[1]。傳統(tǒng)的網(wǎng)絡(luò)設(shè)備是一個封閉的系統(tǒng)，其數(shù)據(jù)層面和控制層面是緊耦合的[2]，如圖1所示。

隨著用戶需求的增加，網(wǎng)絡(luò)急需更多的可編程能力來解決新業(yè)務(wù)快速部署的問題。為獲取更多的網(wǎng)絡(luò)可編程能力，高效且可行的途徑就是將數(shù)據(jù)層面及控制層面相互分離，通過開放的可編程的接口來實(shí)現(xiàn)網(wǎng)絡(luò)控制。軟件定義網(wǎng)絡(luò)架構(gòu)正完美地契合了該特性，其架構(gòu)如圖2所示。

軟件定義廣域網(wǎng)（Software Defined-Wide Area Network， SD-WAN）是將軟件定義網(wǎng)絡(luò)的特性應(yīng)用于管理廣域網(wǎng)中。相比傳統(tǒng)廣域網(wǎng)，軟件定義廣域網(wǎng)能有效降低網(wǎng)絡(luò)開支，大幅度提升網(wǎng)絡(luò)互連。軟件定義廣域網(wǎng)具有范圍大、覆蓋廣的特性，現(xiàn)有的單控制器集中式控制的部署策略在很大程度上限制了網(wǎng)絡(luò)的靈活性和可擴(kuò)展性，繼而出現(xiàn)了多控制器部署。如何實(shí)現(xiàn)邏輯上集中物理上分散的多控制器部署是多控制器部署問題的關(guān)鍵?，F(xiàn)有的方案是將網(wǎng)絡(luò)劃分為多個不相交的子域，每個子域由獨(dú)立的控制器集中控制，即從一開始就通過不同的特征確定分區(qū)，再確定控制器的最優(yōu)部署位置[3]。部署后由于流量分布的不確定性，往往會出現(xiàn)“大象流”和“小象流”的情況，導(dǎo)致子域內(nèi)控制器超載。先前的控制器部署策略已達(dá)不到更好的效果，故提出了根據(jù)流的大小對交換機(jī)進(jìn)行動態(tài)遷移的解決方案。

1 相關(guān)工作

近年來，軟件定義網(wǎng)絡(luò)多控制器部署問題以及交換機(jī)動態(tài)遷移問題引起了越來越多學(xué)者的關(guān)注[4]。

對于多控制器部署問題，目前主流的解決方案是將網(wǎng)絡(luò)劃分為多個不相交的子域，每個子域放置一個控制器或控制器集進(jìn)行控制。在該問題上，時延、部署代價、控制器容量、負(fù)載均衡均可作為優(yōu)化目標(biāo)，其中，時延最為學(xué)者所關(guān)注。最早提出控制器部署問題的學(xué)者Heller 等[5]主要以平均時延和最大時延作為優(yōu)化目標(biāo)，采用了貪心算法進(jìn)行部署。文獻(xiàn)[6]中提出了

網(wǎng)絡(luò)聚類粒子群優(yōu)化（Network Clustering Particle Swarm Optimization， NCPSO）控制器部署算法，該算法以最小時延以及負(fù)載均衡作為部署依據(jù)，將節(jié)點(diǎn)分區(qū)和粒子群算法相結(jié)合進(jìn)行部署。文獻(xiàn)[7]中提出了在每個子域中放置一個控制集合，該控制器集合由主控制器及其從屬控制器組成，該方案提升了整個架構(gòu)的可伸縮性，解決了控制器的過載問題。Wang等[8]以傳播時延和排隊時延作為優(yōu)化目標(biāo)提出了改進(jìn)的k-means算法，該算法從一個分區(qū)開始逐次增加分區(qū)數(shù)量來進(jìn)行迭代從而確定每個分區(qū)中的控制器位置。

在軟件定義網(wǎng)絡(luò)交換機(jī)動態(tài)遷移方面，Rath 等[9]提出了基于博弈的控制器優(yōu)化部署方法，該方法將每一個控制器當(dāng)作一個游戲參與者，通過參與游戲計算自身的收益并根據(jù)收益情況關(guān)閉控制器來實(shí)現(xiàn)負(fù)載均衡。Yao 等[10]根據(jù)控制器的負(fù)載情況提出了向鄰居域遷移控制器的方法，以達(dá)到負(fù)載均衡的目標(biāo)。

2 軟件定義廣域網(wǎng)中多控制器部署

2.1 控制器部署模型

軟件定義廣域網(wǎng)中多控制器部署策略主要采用網(wǎng)絡(luò)分區(qū)的思想將網(wǎng)絡(luò)分成多個不相交的子域，再將傳播時延作為優(yōu)化目標(biāo)對每個子域進(jìn)行控制器的部署[11～13]。對于具有多個節(jié)點(diǎn)以及多條鏈路的物理網(wǎng)絡(luò)來說，其拓?fù)鋱D可以通過一個無向圖G（V，E）表示[14]，其中V是交換機(jī)的集合，E是交換機(jī)間物理鏈路的集合。兩個節(jié)點(diǎn)m，n之間的距離可以表示為d（m，n）（m，n∈V）。整個網(wǎng)絡(luò)可分為k個區(qū)域，每個網(wǎng)絡(luò)分區(qū)定義為SDNi（Vi，Ei）。該定義滿足式（1）和式（2），分別表示分區(qū)的覆蓋區(qū)域?yàn)檎麄€網(wǎng)絡(luò)，分成的每個區(qū)互不相交。

5 結(jié)語

本文針對廣域網(wǎng)中SDN控制器部署問題提出了一種SC-cSNN控制器部署算法，該方法能夠盡可能地縮小平均最大時延。其次，針對SDN中交換機(jī)動態(tài)遷移問題提出了一種基于多特征的交換機(jī)遷移方法，避免由于負(fù)載不均引起的整體網(wǎng)絡(luò)性能問題。仿真實(shí)驗(yàn)結(jié)果表明，SC-cSNN控制器部署算法的平均最大時延優(yōu)于現(xiàn)有的基于k-means和基于譜聚類的控制器部署算法;基于kNN的交換機(jī)動態(tài)遷移算法從多特征的角度有效地解決了SDN控制器負(fù)載不均衡的問題。下一步研究計劃將控制器排隊時延、交換機(jī)轉(zhuǎn)發(fā)時延納入考慮范圍，最小化其綜合時延;并從控制器安全角度出發(fā)，提出一種更為安全且高性能的負(fù)載均衡方案。

參考文獻(xiàn)：

[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] 張朝昆，崔勇，唐翯祎，等.軟件定義網(wǎng)絡(luò)（SDN）研究進(jìn)展[J].軟件學(xué)報，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網(wǎng)絡(luò)中受時延和容量限制的多控制器均衡部署[J].通信學(xué)報，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/.