基于時延優(yōu)化的軟件定義網(wǎng)絡控制層部署策略

樊自甫，姚 杰，楊先輝

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

0 引言

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

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

1 相關(guān)工作

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

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

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

2 數(shù)學模型建立

2.1 前提假設

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

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

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

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

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

2.2 控制層部署問題模型

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

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

(1)

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

(2)

在該狀態(tài)下經(jīng)過概率加權(quán)后的最壞情況時延Lwc(s0)可表示為：

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

由此，可得出本文模型：

minLNSL(S)

(8)

(9)

(10)

yvici,xvicj∈{0,1}

(11)

Di∩Dj=?

(12)

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

(13)

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

3 模型求解算法設計

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

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

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

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

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

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

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

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

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

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

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

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

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

算法通過對粒子中每一維度的位置、速度更新，實現(xiàn)粒子的運動。式(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)輸入網(wǎng)絡拓撲G(V,E)、控制器數(shù)量k、算法循環(huán)次數(shù)上限tmax、最大慣性權(quán)重wmax、最小慣性權(quán)重wmin。

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

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

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

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

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

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

9)全局最優(yōu)解更新。

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

4 實驗仿真

4.1 仿真環(huán)境及參數(shù)設置

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

圖1 Internet2拓撲

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

4.2 仿真結(jié)果分析

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

圖2 不同控制器數(shù)量下的網(wǎng)絡狀態(tài)時延

圖3 不同控制器數(shù)量下的時延收益

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

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

5 結(jié)語

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

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] 姚琳元,陳穎,宋飛.基于時延的軟件定義網(wǎng)絡快速響應控制器部署[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] 張聯(lián)鎮(zhèn),黃傳河,曾毓瓏.SDN中基于時延優(yōu)化的多控制器部署方案[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.