郭烜成 林暉 葉秀彩 許傳豐

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

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

中圖分類(lèi)號(hào)： 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ù)平面不再相互依賴(lài)[1]。傳統(tǒng)的網(wǎng)絡(luò)設(shè)備是一個(gè)封閉的系統(tǒng)，其數(shù)據(jù)層面和控制層面是緊耦合的[2]，如圖1所示。

隨著用戶(hù)需求的增加，網(wǎng)絡(luò)急需更多的可編程能力來(lái)解決新業(yè)務(wù)快速部署的問(wèn)題。為獲取更多的網(wǎng)絡(luò)可編程能力，高效且可行的途徑就是將數(shù)據(jù)層面及控制層面相互分離，通過(guò)開(kāi)放的可編程的接口來(lái)實(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ò)開(kāi)支，大幅度提升網(wǎng)絡(luò)互連。軟件定義廣域網(wǎng)具有范圍大、覆蓋廣的特性，現(xiàn)有的單控制器集中式控制的部署策略在很大程度上限制了網(wǎng)絡(luò)的靈活性和可擴(kuò)展性，繼而出現(xiàn)了多控制器部署。如何實(shí)現(xiàn)邏輯上集中物理上分散的多控制器部署是多控制器部署問(wèn)題的關(guān)鍵?，F(xiàn)有的方案是將網(wǎng)絡(luò)劃分為多個(gè)不相交的子域，每個(gè)子域由獨(dú)立的控制器集中控制，即從一開(kāi)始就通過(guò)不同的特征確定分區(qū)，再確定控制器的最優(yōu)部署位置[3]。部署后由于流量分布的不確定性，往往會(huì)出現(xiàn)“大象流”和“小象流”的情況，導(dǎo)致子域內(nèi)控制器超載。先前的控制器部署策略已達(dá)不到更好的效果，故提出了根據(jù)流的大小對(duì)交換機(jī)進(jìn)行動(dòng)態(tài)遷移的解決方案。

1 相關(guān)工作

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

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

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

在軟件定義網(wǎng)絡(luò)交換機(jī)動(dòng)態(tài)遷移方面，Rath 等[9]提出了基于博弈的控制器優(yōu)化部署方法，該方法將每一個(gè)控制器當(dāng)作一個(gè)游戲參與者，通過(guò)參與游戲計(jì)算自身的收益并根據(jù)收益情況關(guān)閉控制器來(lái)實(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ò)分成多個(gè)不相交的子域，再將傳播時(shí)延作為優(yōu)化目標(biāo)對(duì)每個(gè)子域進(jìn)行控制器的部署[11～13]。對(duì)于具有多個(gè)節(jié)點(diǎn)以及多條鏈路的物理網(wǎng)絡(luò)來(lái)說(shuō)，其拓?fù)鋱D可以通過(guò)一個(gè)無(wú)向圖G（V，E）表示[14]，其中V是交換機(jī)的集合，E是交換機(jī)間物理鏈路的集合。兩個(gè)節(jié)點(diǎn)m，n之間的距離可以表示為d（m，n）（m，n∈V）。整個(gè)網(wǎng)絡(luò)可分為k個(gè)區(qū)域，每個(gè)網(wǎng)絡(luò)分區(qū)定義為SDNi（Vi，Ei）。該定義滿(mǎn)足式（1）和式（2），分別表示分區(qū)的覆蓋區(qū)域?yàn)檎麄€(gè)網(wǎng)絡(luò)，分成的每個(gè)區(qū)互不相交。

5 結(jié)語(yǔ)

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