姚琳元 陳 穎 宋 飛 張宏科

?

基于時延的軟件定義網(wǎng)絡(luò)快速響應(yīng)控制器部署

姚琳元*陳 穎 宋 飛 張宏科

(北京交通大學(xué)下一代互聯(lián)網(wǎng)互聯(lián)設(shè)備國家工程實驗室 北京 100044)

目前大多數(shù)針對軟件定義網(wǎng)絡(luò)(SDN)中控制器的部署方案均重點考慮傳輸時延(PD)對性能的影響，忽略了發(fā)送時延(TD)對于部署效果的影響。該文提出基于時延的網(wǎng)絡(luò)快速響應(yīng)控制器部署方案。首先，在合理考慮傳輸和發(fā)送兩類時延的基礎(chǔ)上，完善了已有的平均時延/最大時延最小化模型，并對兩種模型是否存在最優(yōu)解進行了理論證明；其次，利用模糊集理論得出了一種時延優(yōu)化模型；第三，結(jié)合是否考慮發(fā)送時延提出了兩種部署算法：傳輸算法和輸送算法。為了測試方案的性能，選取實際網(wǎng)絡(luò)拓撲及數(shù)據(jù)進行驗證。結(jié)果表明輸送算法在網(wǎng)絡(luò)的響應(yīng)速度及穩(wěn)定性方面優(yōu)于傳輸算法，時延優(yōu)化模型在總時延方面較平均時延/最大時延最小化模型效果更優(yōu)。

軟件定義網(wǎng)絡(luò)；部署；控制器；時延

1 引言

軟件定義網(wǎng)絡(luò)(Software-Defined Network, SDN)是由美國斯坦福大學(xué)Cleanslate研究組[1]提出的一種基于集中控制的新型網(wǎng)絡(luò)架構(gòu)[2]。在不改變傳統(tǒng)IP數(shù)據(jù)包轉(zhuǎn)發(fā)行為的基礎(chǔ)上，SDN將傳統(tǒng)路由器/交換機的數(shù)據(jù)轉(zhuǎn)發(fā)與邏輯控制進行分離，實現(xiàn)數(shù)據(jù)域與控制域的解耦[3,4]。在數(shù)據(jù)域中，SDN定義為交換機(Switch)負責(zé)數(shù)據(jù)包的接收、存儲和轉(zhuǎn)發(fā)。在控制域中，SDN定義為控制器(Controller)負責(zé)網(wǎng)絡(luò)的頂層設(shè)計，與交換機連接；收集網(wǎng)絡(luò)信息，實現(xiàn)全局處理；通過控制交換機的流表項指導(dǎo)交換機對數(shù)據(jù)包的處理，實現(xiàn)網(wǎng)絡(luò)的集中管理，為用戶提供更好、更便捷的網(wǎng)絡(luò)服務(wù)[5,6]。

良好的上網(wǎng)體驗，要求網(wǎng)絡(luò)暢達、快速，而合理、方便地部署控制器顯得尤為重要。當(dāng)今，核心網(wǎng)設(shè)備的部署已趨于固定，重新搭建網(wǎng)絡(luò)拓撲不符合綠色、節(jié)能、便捷等現(xiàn)代網(wǎng)絡(luò)理念[7]。在已鋪設(shè)的網(wǎng)絡(luò)架構(gòu)基礎(chǔ)上進行優(yōu)化，與現(xiàn)有網(wǎng)絡(luò)實現(xiàn)良好的硬件連接和邏輯連接是SDN發(fā)展的必然趨勢。與此同時，SDN在設(shè)計之初就確定了數(shù)據(jù)轉(zhuǎn)發(fā)與控制相分離的基本思想，采用集中式管理，實現(xiàn)網(wǎng)絡(luò)的一致性，勢必要求網(wǎng)絡(luò)的快速響應(yīng)[8]。在已有網(wǎng)絡(luò)的基礎(chǔ)上，考慮控制器的部署位置是實現(xiàn)網(wǎng)絡(luò)快速響應(yīng)的有效方式之一。

文獻[9]首次提出了SDN網(wǎng)絡(luò)中控制器的部署問題：(1)網(wǎng)絡(luò)中需要多少個控制器；(2)怎么部署控制器。為實現(xiàn)定量分析，作者首先定義了兩個測試參數(shù)平均時延和最大時延；然后，利用真實拓撲結(jié)構(gòu)進行分析，包括：控制器數(shù)量對時延的影響，平均時延與最優(yōu)時延的對比等；最后，引入交換速度、環(huán)保護和網(wǎng)絡(luò)恢復(fù)3個網(wǎng)絡(luò)時間參數(shù)，綜合考慮網(wǎng)絡(luò)對時延的需求，提出一個控制器即可滿足當(dāng)下網(wǎng)絡(luò)的響應(yīng)要求。在分析過程中，文獻[9]只考慮了傳輸時延，忽略了發(fā)送時延對網(wǎng)絡(luò)響應(yīng)速率的影響。

文獻[10, 11]分別從網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)彈性兩個角度對控制器的部署進行了分析、建模。文獻[10]提出了一個新的參量，即可預(yù)期控制鏈路虧損百分比(Expected Percentage of Control Path Loss)，并從可靠性的角度對SDN中控制器的部署進行了分析。文獻提出了4種不同的部署算法，利用真實拓撲對算法進行了驗證，其中模擬退火法(Simulated Annealing)優(yōu)于其他算法；認為控制器的數(shù)量應(yīng)適當(dāng)選擇，過多或過少都會影響網(wǎng)絡(luò)的可靠性。文獻[11]從網(wǎng)絡(luò)彈性和容錯的角度對SDN中控制器的部署進行了分析，應(yīng)用帕累托優(yōu)化理論，實現(xiàn)網(wǎng)絡(luò)彈性和網(wǎng)絡(luò)容錯的權(quán)衡；通過對OS3E拓撲及拓撲動物園(Topology Zoo)中的大量拓撲進行分析，認為保證網(wǎng)絡(luò)的連續(xù)，網(wǎng)絡(luò)中至少要有20%的節(jié)點設(shè)置為控制器。

文獻[12]充分利用固定式網(wǎng)絡(luò)微積分結(jié)構(gòu)，建立數(shù)學(xué)模型，解決了SDN在部署過程中的可擴展性問題。文中將控制器分為本地控制器(Local Controller)和超級控制器(Root Controller)，利用數(shù)學(xué)模型從本地控制器中獲取固定格式的事件時延和緩存長度，利用經(jīng)典的排隊理論解決了邊界和最差條件下的兩種部署情況。另外，文獻[12]建立了一個控制器互動分析模型，該模型給出了控制器的進程、流量控制函數(shù)，利于網(wǎng)絡(luò)設(shè)計人員計算出控制器的時延和緩存需求。對于下一步工作，文章提出了兩個方向的目標：(1)采用隨機網(wǎng)絡(luò)微積分的方法對SDN中的部署問題進行研究，完成相關(guān)仿真和實驗工作；(2)在參照邊界條件的同時，考慮均衡條件下的平均值。

通過對相關(guān)控制器部署方案的研究，本文提出了一種基于傳輸時延和發(fā)送時延的網(wǎng)絡(luò)快速響應(yīng)控制器部署方案。首先，完善平均時延和最大時延最小化模型，在此基礎(chǔ)上，推導(dǎo)出時延優(yōu)化模型；其次，提出了解決上述模型的基于傳輸時延和發(fā)送時延的輸送算法(Transmission and Propagation Algorithm, TPA)以及基于傳輸時延的傳輸算法(Propagation Algorithm, PA)；最后，利用實際拓撲數(shù)據(jù)，完成數(shù)據(jù)仿真，得出不同模型最佳部署方案以及對應(yīng)的平均時延、最大時延和總時延，并與相關(guān)部署方案進行了對比、分析。

2 模型假設(shè)及理論證明

網(wǎng)絡(luò)時延的主要衡量標準分為平均時延和最大時延[9]，本節(jié)從傳輸時延和發(fā)送時延兩個角度，研究平均時延和最大時延，分析網(wǎng)絡(luò)響應(yīng)速度。具體工作如下：首先設(shè)定基本假設(shè)，定義基本的參考變量，完成數(shù)學(xué)化描述，推導(dǎo)出參數(shù)間的數(shù)學(xué)關(guān)系；在此基礎(chǔ)上，對現(xiàn)有的平均時延模型和最大時延模型進行完善，添加發(fā)送時延變量，得出平均時延最小化模型和最大時延最小化模型，并利用優(yōu)化理論對上述模型是否存在最優(yōu)解進行理論證明[14]；最后從上述模型中提煉出時延優(yōu)化模型，引入模糊集理論[15]，給出時延優(yōu)化模型的解決方案。下文的公式表示同時考慮傳輸時延和發(fā)送時間的數(shù)學(xué)分析模型，與第3節(jié)中TPA對應(yīng)；去除所述模型中發(fā)送時延變量的數(shù)學(xué)分析模型，與第3節(jié)中PA對應(yīng)，限于篇幅，本節(jié)不做說明。

2.1 基本假設(shè)和參數(shù)定義

(2)

2.2 平均時延最小化模型

2.3 最大時延最小化模型

最終數(shù)學(xué)模型為

該模型可以反應(yīng)出當(dāng)前部署方案下的網(wǎng)絡(luò)最大響應(yīng)時延，同時，以最大響應(yīng)時延作為限制條件，找到最優(yōu)部署方案，定理2是對該模型最優(yōu)解的說明。

2.4 時延優(yōu)化模型

3 部署算法

為驗證發(fā)送時延在網(wǎng)絡(luò)響應(yīng)速度以及控制器部署等方面的重要程度，本文首先參照文獻[9]，設(shè)計了PA，然后依據(jù)上文提出的傳輸時延和發(fā)送時延，設(shè)計了TPA。

兩種算法定義網(wǎng)絡(luò)節(jié)點到控制器的單向傳輸方向為數(shù)據(jù)傳輸方向，認為控制器的部署位置位于網(wǎng)絡(luò)拓撲中的網(wǎng)絡(luò)節(jié)點處，當(dāng)某網(wǎng)絡(luò)設(shè)備的位置與控制器的位置重疊時，二者的傳輸時延為0；當(dāng)部署多個控制器，需計算其中一個控制器到網(wǎng)絡(luò)節(jié)點的時延時，兩種算法設(shè)定其余控制器和與之連接的網(wǎng)絡(luò)節(jié)點處于不能通信狀態(tài)，即傳輸時延設(shè)為無窮大。PA和TPA都以迪杰斯特拉(Dijkstra)算法和貪心(Greedy)算法為基礎(chǔ)，以實際拓撲作為算法的輸入，得出不同條件下的最優(yōu)部署方案。二者的不同之處在于：

(1)PA將拓撲中的網(wǎng)絡(luò)節(jié)點視為普通點，只計算傳輸時延，通過尋找最短路徑，得到網(wǎng)絡(luò)設(shè)備到控制器的最短距離，進而獲得基于傳輸時延的最佳部署方案；為統(tǒng)一網(wǎng)絡(luò)參數(shù)，在PA的最后，增加了發(fā)送時延，表示在網(wǎng)絡(luò)運轉(zhuǎn)情況下，即有數(shù)據(jù)在網(wǎng)絡(luò)中傳輸時，網(wǎng)絡(luò)響應(yīng)時延的情況；

(2)TPA將傳輸時延和發(fā)送時延作為部署方案的參考因素，當(dāng)計算拓撲中某個網(wǎng)絡(luò)節(jié)點到控制器的響應(yīng)時延時，TPA提出將網(wǎng)絡(luò)節(jié)點以外的其他節(jié)點設(shè)置為與該網(wǎng)絡(luò)節(jié)點相同的發(fā)送時延；

(3)TPA可直接使用第2節(jié)中的3個數(shù)學(xué)模型，PA在使用上述模型時，需去掉模型中的發(fā)送時延一項。

具體算法偽代碼如表1和表2所示。

4 性能評估

圖2為利用PA和TPA求出的3種優(yōu)化模型P1, P2, P3的時延對比圖，mean表示平均時延，max表示最大時延，mm表示平均時延與最大時延的和。圖2(a)表示不考慮信息量I, PA得出的3種優(yōu)化模型分別對應(yīng)的平均時延(mean)，最大時延(max)和總時延(mm)隨控制器數(shù)量增加的變化情況；圖2(b)表示在圖2(a)得出的3種最優(yōu)部署方案下，增加I后，時延隨控制器數(shù)量增加的變化情況；圖2(c)表示使用TPA得出的3種優(yōu)化模型分別對應(yīng)的3種時延隨控制器數(shù)量增加的變化情況。從圖2可看出：

表1 PA算法

圖1 網(wǎng)絡(luò)拓撲圖

表2 TPA算法

(1)圖2(a)和圖2(c)中，3種模型得到的部署方案，在PA信息量為0或TPA情況下，時延隨控制器數(shù)量的增多而下降，控制器數(shù)量越多，網(wǎng)絡(luò)的響應(yīng)速率越快；

(2)圖2(b)中，考慮發(fā)送時延，在圖2(a)的最優(yōu)部署條件下，時延隨控制器數(shù)量的增多上下波動，沒有固定的變化規(guī)律，不能體現(xiàn)控制器數(shù)量增多在部署過程中的優(yōu)勢；

(3)圖2(b)和圖2(c)中，信息量相同情況下，TPA算法的3種時延明顯低于PA算法的時延。

圖3(a)，圖3(b)，圖3(c)分別代表3種模型最優(yōu)部署方案的時延情況，其中橫坐標表示控制器數(shù)量，縱坐標表示同一種算法PA或TPA下的最大時延與平均時延的比值。從圖3中可以看出：

(1)3種模型下，TPA的比值要明顯低于PA的比值，表明在網(wǎng)絡(luò)響應(yīng)平均時延相同的情況下，TPA較PA能夠?qū)崿F(xiàn)更快的網(wǎng)絡(luò)響應(yīng)，網(wǎng)絡(luò)節(jié)點到控制器的響應(yīng)時延波動范圍更小。

圖2 時延比較圖

圖3 時延比值圖

(2)通過3個子圖的對比，TPA的比值比較穩(wěn)定：控制器數(shù)量增多，平均時延下降，最大時延穩(wěn)步降低；PA的比值變動較大，無明顯規(guī)律，當(dāng)控制器數(shù)量為1時，比值最小，控制器數(shù)量增多，比值大小不一。

圖4(a)和圖4(b)分別表示PA算法(=0)和TPA算法下，3種模型的時延比較圖。從圖4可以看出，模型P3的總時延取P2, P1二者中較低項，或低于二者。

從上述分析可以看出，較PA, TPA在平均時延、最大時延和總時延更低、比值更低，可以更快實現(xiàn)網(wǎng)絡(luò)響應(yīng)；時延優(yōu)化模型較平均時延最小化模型和最大時延最小化模型在總時延更有優(yōu)勢，網(wǎng)絡(luò)的響應(yīng)時間更加集中。

5 結(jié)束語

在充分考慮傳輸時延和發(fā)送時延的前提下，本文提出了基于時延的網(wǎng)絡(luò)控制器快速響應(yīng)部署方案。已有時延模型僅考慮傳輸時延，在此基礎(chǔ)上，本文增加了發(fā)送時延，得出了平均時延最小化模型和最大時延最小化模型，并結(jié)合二者特點，創(chuàng)建了時延優(yōu)化模型，通過優(yōu)化理論和模糊理論，對模型的最優(yōu)解進行了論證。按照是否考慮發(fā)送時延，設(shè)計了PA和TPA，通過仿真結(jié)果我們發(fā)現(xiàn)，將發(fā)送時延納入考慮范圍可以增加網(wǎng)絡(luò)的響應(yīng)速度，增加網(wǎng)絡(luò)部署的穩(wěn)定性；時延優(yōu)化模型可以使網(wǎng)絡(luò)響應(yīng)時間更加集中。下一步工作將利用網(wǎng)絡(luò)仿真工具，引入節(jié)點處理時延等變量，同時從介數(shù)角度探討網(wǎng)絡(luò)中控制器的部署。

圖4 模型比較圖

[1] McKeown N, Anderson T, Balakrishnan H,.. OpenFlow: enabling innovation in campus networks[J]., 2008, 38(2): 69-74.

[2] Jain S, Kumar A, Mandal S,.. B4: experience with a globally-deployed software defined WAN[C]. The Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013: 3-14.

[3] ONF. software-defined networking: the new norm for networks, white paper[OL]. https://www.opennetworking. org, 2013. 12.

[4] Mueller J, Wierz A, Vingarzan D,.. Elastic network design and adaptive flow placement in software defined networks[C]. 2013 22nd International Conference on Computer Communications and Networks (ICCCN), California, 2013: 1-6.

[5] 周燁, 楊旭, 李勇, 等. 基于分類的軟件定義網(wǎng)絡(luò)流表更新一致性方案[J]. 電子與信息學(xué)報, 2013, 35(7): 1746-1752.

Zhou Ye, Yang Xu, Li Yong,.. Classification based consistent flow update scheme in software defined network[J].&, 2013, 35(7): 1746-1752.

[6] Dixit A, Hao F, Mukherjee S,.. Towards an elastic distributed sdn controller[C]. The Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, Hong Kong, 2013: 7-12.

[7] Sezer S, Scott-Hayward S, Chouhan P K,.. Are we ready for SDN? Implementation challenges for software-defined networks[J]., 2013, 51(7): 36-43.

[8] Levin D, Wundsam A, Heller B,.. Logically centralized: state distribution trade-offs in software defined networks[C]. Proceedings of the First ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, New York, 2012: 1-6.

[9] Heller B, Sherwood R, and McKeown N. The controller placement problem[C]. The First ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, New York, 2012: 7–12.

[10] Hu Y, Wendong W, Gong X,.. Reliability-aware controller placement for Software-Defined Networks[C]. 2013 IFIP/IEEE International Symposium on Integrated Network Management (IM 2013), Sophia Antipolis, 2013: 672-675.

[11] Hock D, Hartmann M, Gebert S,.. Pareto-optimal resilient controller placement in SDN-based core networks[C]. IEEE 2013 25th International Teletraffic Congress (ITC), California, 2013: 1-9.

[12] Azodolmolky S, Wieder P, and Yahyapour R. Performance evaluation of a scalable software-defined networking deployment[C]. IEEE 2013 Second European Workshop on Software Defined Networks (EWSDN), Berlin, 2013: 68-74.

[13] Kurose J F and Ross K W. Computer Networking: a Top- Down Approach Featuring the Internet[M]. India: Pearson Education, 2013: 35-44.

[14] Boyd S P and Vandenberghe L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004: 43-46, 127-152.

[15] Zadeh L A, Klir G J, and Yuan B. Fuzzy Sets, Fuzzy Logic, Fuzzy Systems[M]. Singapore, World Scientific Press, 1996: 165-175.

[16] Huang D, Yang D, Zhang H,.. Energy-aware virtual machine placement in data centers[C]. 2012 IEEE Global Communications Conference (GLOBECOM), California, 2012: 3243-3249.

[17] Christian raack. Sndlib [OL]. http://sndlib.zib.de/home. action, 2013.12.

[18] Spring N, Mahajan R, and Wetherall D. Measuring ISP topologies with rocketfuel[J]., 2002, 32(4): 133-145.

姚琳元： 男，1988年生，博士生，研究方向為下一代互聯(lián)網(wǎng)網(wǎng)絡(luò)層關(guān)鍵技術(shù).

陳 穎： 女，1987年生，碩士生，研究方向為下一代互聯(lián)網(wǎng)網(wǎng)絡(luò)層關(guān)鍵技術(shù).

宋 飛： 男，1983年生，副教授，碩士生導(dǎo)師，研究方向為下一代互聯(lián)網(wǎng)網(wǎng)絡(luò)層、傳輸層關(guān)鍵技術(shù).

張宏科： 男，1957年生，教授，博士生導(dǎo)師，研究方向為下一代互聯(lián)網(wǎng)架構(gòu)、協(xié)議理論與技術(shù)、移動互聯(lián)網(wǎng)絡(luò)路由、傳感器網(wǎng)絡(luò)技術(shù)等.

Delay-aware Controller Placement for Fast Responsein Software-defined Network

Yao Lin-yuan Chen Ying Song Fei Zhang Hong-ke

(,,100044,)

Most of Controller placements take the Propagation Delay (PD) as the important consideration in Software-Defined Network (SDN), ignoring the influence of the Transmission Delay (TD) on the network performance.This paper provides a delay-aware controller placement for fast response. First, the Controller placement is formulated as an optimization problem based on PD and TD. Average delay and maximum delay minimization models are updated, of which the processes about the optimal solution are circumstantiated. Further, delay optimization model is deduced by fuzzy set theory. Finally, according to whether or not considering TD, two placement algorithms, Transmission and Propagation Algorithm (TPA) and Propagation Algorithm (PA), are presented. In order to measure the performance of the solutions, a factual network topology is chosen and the simulation result shows that TPA superiorities over PA in terms of response speed and network stability, the total delay of delay optimization model is less than the others.

Software-Defined Network (SDN); Placement; Controller; Delay

TP393

A

1009-5896(2014)12-2802-07

10.3724/SP.J.1146.2014.00211

姚琳元 11111020@bjtu.edu.cn

2014-02-19收到，2014-05-20改回

國家自然科學(xué)基金(61301081)，高等學(xué)校博士學(xué)科點專項科研基金(20120009120005)和中央高?？蒲袠I(yè)務(wù)費專項基金(2014JBM010)資助課題