基于時延優化的軟件定義網絡控制層部署策略

樊自甫，姚 杰，楊先輝

(重慶郵電大學 下一代網絡應用技術研究所，重慶 400065)(*通信作者電子郵箱542438256@qq.com)

0 引言

隨著網絡信息技術的飛速發展，傳統網絡架構無法滿足日益增長的網絡帶寬以及數據分析等業務需求，亟須一種新型的支持動態擴展的創新網絡架構，軟件定義網絡(Software Defined Network, SDN)隨之應運而生。SDN是由美國斯坦福大學Cleanslate研究組提出的一種基于集中控制的新型網絡架構,通過把網絡的控制面和轉發面分離，用集中控制器取代了原來的路由協議自協商方式，極大地提升了網絡的管控效率，開放了網絡能力。

在SDN架構中，控制器負責整個網絡的集中化控制，對于把握全網資源視圖、改善網絡數據交付都具有非常重要的作用。隨著SDN在大規模網絡中的部署[1]，單一集中式的控制器已無法滿足來自全網所有交換機的流處理請求，SDN在大規模網絡中的部署面臨著來自控制平面擴展性方面的嚴峻挑戰[2]。在SDN中引入多臺控制器是解決SDN性能瓶頸、難以橫向擴展以及可靠性問題的主流趨勢。然而，這種由多臺控制器構成的分布式SDN控制層也帶來了一些新的思考。其中一個核心問題是如何確定控制器的數量、部署位置以及如何劃分每個控制器的管理區域，即SDN控制層的部署問題。

1 相關工作

針對SDN控制層的部署問題，當前學術界主要從最小化傳播時延、提升網絡可靠性以及均衡各控制器負載等幾個方面展開。由于網絡設備間的時延將會影響到轉發規則的安裝次序以及不同控制器間的狀態同步，進而引發控制邏輯的不一致，大量研究者在考慮控制層部署問題時將時延作為首要優化目標。

文獻[3]首次提出了SDN控制層的部署問題，并指出在傳播時延占主導地位的廣域網中，控制層的部署策略將嚴重影響到網絡的收斂時間。作者在文章中引入了平均傳播時延及最壞情況下的傳播時延兩種時延指標，采用真實的Internet 2拓撲分析了不同的控制器數量以及部署位置對交換機與控制器間傳播時延產生的影響。文獻[4]在最小化平均傳播時延模型的基礎上，將交換機的處理時延納入考慮范圍，并依據模糊集理論建立了一種新的時延優化模型。文獻[5]采用譜聚類算法將廣域網拓撲分區處理，繼而在各個分區中找到合理的控制器部署位置，該算法在一定程度上降低了廣域網中的傳播時延。文獻[6]同時考慮了流表建立時間以及控制器間的同步時延，對最小化時延模型作了進一步的優化。文獻[7]采用K-Critical算法，通過構建robust樹解決控制層的部署問題，該算法在保證網絡時延的同時一定程度上提升了控制層的魯棒性。

以上文獻對SDN控制層的部署研究作出了一定的貢獻，但僅僅只考慮了正常網絡狀態下時延對控制層的影響。本文以時延作為主要優化目標，并將網絡中的鏈路故障因素納入考慮范圍。首先，以最壞情況時延作為控制層部署策略的衡量指標，綜合考慮網絡正常運行以及單鏈路故障等多種網絡狀態下的最壞情況時延，提出了一種新的時延指標，即網絡狀態時延并以此作為優化目標建立相應的數學模型。其次，提出了兩種解決上述模型的啟發式算法——基于貪婪算法的控制層部署算法(Controller Placement Algorithm based on Greedy Algorithm， GA-CPA)和基于粒子群算法的控制層部署算法(Controller Placement Algorithm based on Particle Swarm Optimization， PSO-CPA)。最后，利用真實網絡拓撲數據進行仿真，對兩種部署算法得到的最佳部署方案以及網絡狀態時延進行對比、分析。

2 數學模型建立

2.1 前提假設

依據SDN控制層關鍵技術的當前研究成果及控制層部署問題的主流研究思路作出以下幾點合理假設。

假設1 由于帶外模式通常會帶來可靠性的下降，而且在工程上也難以實現。在大規模SDN中，控制網絡的建立通常采用帶內連接模式[8]，因此，本文研究場景設定為采用帶內連接的廣域SDN。

假設2 為進一步降低時延，同時增強控制網絡的可靠性與安全性，控制器采用co-locate方式部署，即控制器的部署位置從網絡中所有交換機位置及其鄰近位置中選取，邏輯上可將控制器與其直接相連的交換機視為同一位置，因此，可以忽略兩者間的傳播延時。

假設3 由于控制網絡的首要目的是快速、有效地傳遞控制信息，本文假定控制信息的主備路徑均通過最短路徑生成。此外，考慮到跨域通信的影響，當鏈路出現失效，若本域內存在另外一條可達路徑，默認此路徑為鏈路失效恢復所采用的備份路徑。

假設4 通過對現有網絡故障相關資料的梳理，發現大多數網絡故障由極少量網絡元件的失效引發，文獻[9]通過對多個骨干網的實際測量指出，約70%的網絡故障是由于單條鏈路的失效引起，多條鏈路同時失效的概率極低，因此，本文主要考慮單鏈路失效引發的網絡故障。

2.2 控制層部署問題模型

對于給定的廣域SDN可以通過無向圖G(V,E)表示，其中V={v1,…,vi,…,vn}代表網絡中所有交換機節點的集合，E={e1,…,ei,…,em}表示交換機節點間的雙向鏈路集合。控制器集合通過C={c1,…,ci,…,ck}表示，其中C?V，即控制器的部署位置從交換機節點位置中選取。假設網絡中需要部署的控制器數量為k，通過區域劃分可以將網絡G(V,E)分為k個互無交集的SDN控制域，每個控制域由一臺控制器管理，即G={D1,…,Dj,…,Dk}。對于控制域Di內的控制器ci，其管理的交換機集合為Θci={vi1,…,vij,…,vil}。用d(vij,ci)表示網絡正常狀態下交換機vij與其所屬的控制器ci通過最短路徑通信產生的傳播時延。d′(vij,ci)表示鏈路故障狀態下交換機vij與控制器ci通過最短路徑通信產生的傳播時延。假定每條鏈路的狀態僅考慮正常與故障情況，定義S={s0,s1,…,sj,…,sm}為網絡狀態集合，其中包含一個所有鏈路均正常工作的網絡正常狀態s0,以及m個相互統計獨立的單鏈路故障狀態{s1,s2,…,sm}。假設每條鏈路均有一定的概率出現故障，對于鏈路集合E中的鏈路ei，其故障概率可用pei表示。

由于網絡中的鏈路故障將會導致部分交換機與控制器間的傳播時延劇烈惡化，甚至難以滿足正常通信的需求，因此，本文將網絡中所有交換機與其所屬控制器間通過最短路徑通信所獲得的傳播時延的最大值，即最壞情況時延[3]作為主要衡量指標，其表達式如下：

(1)

由于每條鏈路僅有兩種狀態，因此，對于鏈路集合中的第i條鏈路ei，其正常工作的概率為(1-pei)，那么，網絡正常工作的概率可表示為：

(2)

在該狀態下經過概率加權后的最壞情況時延Lwc(s0)可表示為：

(3)

在考慮鏈路故障狀態時，對各條鏈路的故障概率作標準化處理，鏈路ei的歸一化故障概率可通過式(4)獲得：

(4)

那么，由于鏈路ei失效而導致的網絡故障，其概率可表示為：

(5)

在采用SDN架構的網絡中，交換機與控制器間的通信路徑通過鏈路層發現協議(Link Layer Discovery Protocol， LLDP)建立。一旦鏈路故障發生，故障鏈路兩端的交換機嘗試通過其相鄰交換機向控制層作出故障報告，由控制層重新為其計算控制信息的通信路徑或通過自愈收斂。這意味著，只要交換機與控制器間仍有任意一條路徑存在，交換機就不會失去控制，因此，當鏈路發生故障，此時經過概率加權后的最壞情況時延可通過式(6)獲得：

(6)

此外，在一種極端場景下，由于網絡中某條鏈路發生故障導致該鏈路相關交換機與控制器失聯成為孤立節點，即該交換機無法與控制器再次取得聯系。針對這種情況可采用1+1備份的方式保證網絡的可靠性[10]，因此不在本文考慮范圍。

通過上述分析，提出一個新的時延指標，即網絡狀態時延(Network States Latency， NSL)，其公式如下：

(7)

由此，可得出本文模型：

minLNSL(S)

(8)

(9)

(10)

yvici,xvicj∈{0,1}

(11)

Di∩Dj=?

(12)

Θc1∪Θc2∪…∪Θck=V

(13)

其中式(8)為本文的優化目標，即最小化網絡狀態時延(NSL)。該模型可視為一種多目標優化，即通過合理的部署策略保證較多網絡狀態下的最壞情況時延最小；式(9)將網絡中的控制器數量限制為k個；式(10)確保網絡中每個交換機有且只有一個控制器對其進行管理；式(11)為二元約束變量，若控制器ci部署于交換機vi的位置上，yvici為1，反之則為0；若交換機vi所屬的控制器為cj，二元變量xvicj為1，反之則為0式(12)確保劃分后的控制區域互不相交；式(13)則保證了控制區域的劃分應覆蓋網絡中的所有交換機。

3 模型求解算法設計

最小化最壞情況時延的控制層部署問題[3]，可視為一類設施選址問題。這一類問題已被證明為NP-hard問題，難以在多項式時間內求解[11]。由于本模型是基于最小化最壞情況時延模型的一種改進，因此提出兩種啟發式算法，分別為基于貪婪算法的控制層部署算法(GA-CPA)以及基于粒子群算法的控制層部署算法(PSO-CPA)對模型進行求解。

3.1 基于貪婪算法的控制層部署算法

基于貪婪算法的控制層部署算法(GA-CPA)通過迭代的方式依次完成k個控制器的部署以及每個控制區域的劃分。其中每一次外層循環的輸入均基于上一次循環的最終輸出結果。其具體步驟如下所示。

算法1 基于貪婪算法的控制層部署算法(GA-CPA)。

1)輸入網絡拓撲G(V,E)、控制器數量k、候選控制器位置集合C*←V、鏈路故障概率Pei← 0、當前控制器集合C← ?、控制器ci所控制的交換機集合Θci← ?；

2)計算網絡正常狀態下任意兩交換機節點間的最短路徑d(vi,vj)，生成最短路徑矩陣matrixD[vi][vj]；

3)在C*中隨機選取控制器的部署位置，根據最近鄰原則完成控制區域劃分，依據式(3)計算網絡正常狀態下經概率加權后的最壞情況時延Lwc(s0)；

4)為鏈路ei賦予故障概率pei，重新生成最短路徑矩陣，根據式(6)計算此鏈路故障狀態下經概率加權后的最壞情況時延Lwc(si)；

5)遍歷鏈路集合E，依據式(7)計算該部署方案下的網絡狀態時延LNSL(S)；

6)遍歷控制器候選位置集合C*，重復步驟2)至步驟5)，選擇網絡狀態時延最小的位置作為首個控制器c1部署的位置；

7)更新控制器候選位置集合C*← {C*-c1}，更新當前控制器位置集合C← {C+c1}，在C*中選擇第二個控制器的部署位置，直至k個控制器均完成部署，輸出k個控制區域以及每個區域中控制器所在的位置，算法結束。

3.2 基于粒子群算法的控制層部署算法

依據實際問題，將粒子群中的粒子映射為控制器的部署方案。假設網絡中部署k個控制器，那么粒子pi擁有一個k維的位置屬性Xi=(xi1,xi2,…,xij,…,xik)與一個k維的速度屬性Vi=(vi1,vi2,…,vij,…,vik)，其中控制器cj表示為粒子pi的第j維分量，其位置屬性與速度屬性分別為xij、vij。對于粒子pi，其局部最優解可表示為Pbesti=(pbesti1,pbesti2,…,pbestij,…,pbestik)。全局最優解則通過對比每個局部最優解獲得，可表示為Gbest=(g1,g2,…,gj,…,gk)。粒子的適應度函數通過式(7)獲得。

算法通過對粒子中每一維度的位置、速度更新，實現粒子的運動。式(14)、(15)分別表示粒子pi中第j維分量的位置與速度在第n+1次更新時的方式：

(14)

(15)

(16)

算法2 基于粒子群算法的控制層部署算法(PSO-CPA)。

Synthesis, properties and industrial applications of amino acid surfactants(To be continuted) 11 10

1)輸入網絡拓撲G(V,E)、控制器數量k、算法循環次數上限tmax、最大慣性權重wmax、最小慣性權重wmin。

2)初始化粒子與種群。隨機選取k個位置部署控制器，依據最近鄰原則將其余交換機節點分配給距其最近的控制器從而形成一種部署方案，隨機選取N種部署方案形成粒子數目為N的種群。

3)初始化粒子速度。對于粒子pi，以其位置屬性中的任一維度xij為核心，向其直接相連的交換機節點隨機選擇一次。記錄xij到所選擇節點的方向與距離作為粒子在該維度上的初始化速度方向與速度大小。粒子的速度由所有維度的速度構成，表示為Vi=(vi1,…,vij,…,vik)。

4)初始化局部最優解。將每個粒子的初始位置設置為局部最優解Pbesti←Xi。

5)初始化全局最優解。在局部最優解中選取適應度最好的粒子位置作為全局最優解Gbest←Xbest。

7)依據式(15)完成粒子位置更新。

8)局部最優解更新。根據式(7)計算當前位置的適應度，并與更新前粒子所在位置的適應度進行對比。若獲得更好的適應度，則更新局部最優解；反之，則不變。

9)全局最優解更新。

10)檢查全局最優解與當前迭代次數。若全局最優解達到收斂或當前迭代次數已達上限，算法結束；反之，返回步驟6)，進入下一次算法循環。

4 實驗仿真

4.1 仿真環境及參數設置

為驗證本文所提控制層部署策略的有效性，采用Matlab對相關參數進行實驗仿真。實驗采用的拓撲選自真實的Internet2[13]網絡拓撲，該網絡由美國多所高校及知名研究機構共同構建，旨在推進下一代網絡建設。圖1給出了Internet2網絡拓撲的抽象視圖。

圖1 Internet2拓撲

Internet2拓撲包括34個城市級網絡節點以及41條鏈路。實驗將交換機節點從1至34進行編號，每條鏈路的傳輸時延以節點間的距離乘2/3倍光速計算。實驗中控制器采用co-locate方式進行部署，即控制器的部署位置在所有交換機位置中選取。考慮到網絡鏈路的故障概率具有差異性，實驗對于各鏈路的故障概率參數設置為區間[0,0.15]內的隨機浮點數，其均值為0.04。

4.2 仿真結果分析

圖2給出了兩種算法與隨機部署算法(RANdom Controller Placement Algorithm， RAN-CPA)在不同控制器數量下對于網絡狀態時延的對比結果。由圖2可知，隨著控制器數量的增加，兩種算法所獲得的網絡狀態時延均呈下降趨勢，且PSO-CPA整體優于GA-CPA，而RAN-CPA性能最差。當控制器數目為1時，由于GA-CPA的每次部署循環均采用了遍歷的手段，因此可獲得實際上的全局最優解，從而優于PSO-CPA。

圖2 不同控制器數量下的網絡狀態時延

圖3 不同控制器數量下的時延收益

最小化網絡狀態時延模型的目標是通過合理的控制層部署策略保證較多網絡狀態下的最壞情況時延最小。圖4給出了部署3個控制器時兩種算法所得最壞情況時延的累積分布，其中PSO-CPA與GA-CPA將控制器分別部署于圖1中編號27，14，7以及27，15，10的節點之上。由圖4可知，在不同的網絡狀態下最壞情況時延將在8.19 ms至30.03 ms范圍內大幅度波動，PSO-CPA與GA-CPA可以分別保證約44%及35%的網絡狀態下最壞情況時延不高于8.19 ms，即對于兩種算法而言，分別約18與15種鏈路故障狀態不會對最壞情況時延產生影響；而在15 ms范圍內，該比值可分別達到95%與88%。由此可見，在鏈路發生故障時不同的控制層部署方案在保障最壞情況時延方面存在著優劣，而合理的部署策略可以使更多的鏈路故障狀態下最壞情況時延所受影響較小。

圖4 最壞情況時延累積分布

5 結語

在充分考慮了不同網絡狀態下傳播時延的前提下，本文提出了基于時延優化的控制層部署方案。以最壞情況時延作為控制層部署策略的衡量指標，綜合考慮了網絡正常狀態以及多種單鏈路故障狀態，提出了一種新的時延指標，即網絡狀態時延并以此作為優化目標建立相應模型。同時，提出了兩種啟發式控制層部署算法，即PSO-CPA與GA-CPA對模型進行求解。仿真結果表明本文所提兩種部署算法均能在不同程度上降低網絡狀態時延，從而保證了大部分網絡狀態下的最壞情況時延維持在較低范圍。由于本文僅考慮了單鏈路故障狀態下的時延，因此下一步工作計劃及未來研究將會考慮多鏈路失效狀態對時延的影響。

References)

[1] MCCAULEY J, PANDA A, CASADO M, et al. Extending SDN to large-scale networks [J]. Open Networking Summit, 2013, 58(2): 50-51.

[2] YEGANEH SH, TOOTOONCHIAN A, GANJALI Y. On scalability of software-defined networking [J]. IEEE Communications Magazine, 2013, 51(2): 136-141.

[3] HELLER B, SHERWOOD R, MCKEOWN N. The controller placement problem [J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 473-478.

[4] 姚琳元,陳穎,宋飛.基于時延的軟件定義網絡快速響應控制器部署[J].電子與信息學報,2014,36(12):2802-2808.(YAO L Y, CHEN Y, SONG F. Delay-aware controller placement for fast response in software-defined network [J]. Journal of Electronics and Information Technology, 2014, 36(12): 2802-2808.)

[5] XIAO P, QU W, QI H, et al. The SDN controller placement problem for WAN [C]// ICCC 2014: Proceedings of the 2014 IEEE/CIC International Conference on Communications in China. Piscataway, NJ: IEEE, 2014: 220-224.

[6] 張聯鎮,黃傳河,曾毓瓏.SDN中基于時延優化的多控制器部署方案[J].計算機工程與設計,2015,36(5):1121-1125.(ZHANG L Z, HUANG C H, ZENG Y L. Multi-controller deployment scheme based on delay optimization in SDN [J]. Computer Engineering and Design, 2015, 36(5): 1121-1125.)

[7] JIMéNEZ Y, CERVELL-PASTOR C, GARCA A J. On the controller placement for designing a distributed SDN control layer [C]// Proceedings of the 2014 International Federation for Information Processing Networking Conference. Piscataway, NJ: IEEE, 2014: 1-9.

[8] PANDA A, SCOTT C, GHODSI A, et al. CAP for networks [C]//

Proceedings of the 2013 ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 91-96.

[9] MARKOPOULOU A, IANNACCONE G, BHATTACHARYYA S, et al. Characterization of failures in an operational IP backbone network [J]. IEEE/ACM Transactions on Networking, 2008, 16(4): 749-762.

[10] ZHANG Y, BEHESHTI N, TATIPAMULA M. On resilience of split-architecture networks [C]// GLOBECOM 2011: Proceedings of the 2011 IEEE Global Telecommunications Conference. Piscataway, NJ: IEEE, 2011: 1-6.

[11] 潘銳，朱大銘，馬紹漢.k-Median近似計算復雜度與局部搜索近似算法分析[J].軟件學報,2005,16(3):392-399.(PAN R, ZHU D M, MA S H. Approximated computational hardness problem and local search approximated algorithm analysis fork-median problem [J]. Journal of Software, 2005, 16(3): 392-399.)

[12] MA L, FOROURAGHI B. A modified particle swarm optimizer for engineering design [C]// IEA/AIE 2012: Proceedings of the 2012 International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. Berlin: Springer, 2012: 187-196.

[13] Internet2. Internet2 open science, scholarship and services ex-change [EB/OL]. [2017- 03- 28]. http://www.internet2.edu/network/ose/.

This work is partially supported by the National Natural Science Foundation of China (61701064), the Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ1600424), the Doctor Research Startup Foundation of Chongqing University of Posts and Telecommunications (A2015- 41), the Science Research Project of Chongqing University of Posts and Telecommunications for Young Scholars (A2015- 62).

FANZifu, born in 1977, M. S., associate professor. His research interests include next generation network technology, communication operation management.

YAOJie, born in 1994, M. S. candidate. His research interests include next generation network technology, software defined network.

YANGXianhui, born in 1990, M. S. candidate. His research interests include next generation network technology, software defined network.