基于時延的軟件定義網絡快速響應控制器部署

姚琳元 陳 穎 宋 飛 張宏科

?

基于時延的軟件定義網絡快速響應控制器部署

姚琳元*陳 穎 宋 飛 張宏科

(北京交通大學下一代互聯網互聯設備國家工程實驗室 北京 100044)

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

軟件定義網絡；部署；控制器；時延

1 引言

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

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

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

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

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

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

2 模型假設及理論證明

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

2.1 基本假設和參數定義

(2)

2.2 平均時延最小化模型

2.3 最大時延最小化模型

最終數學模型為

該模型可以反應出當前部署方案下的網絡最大響應時延，同時，以最大響應時延作為限制條件，找到最優部署方案，定理2是對該模型最優解的說明。

2.4 時延優化模型

3 部署算法

為驗證發送時延在網絡響應速度以及控制器部署等方面的重要程度，本文首先參照文獻[9]，設計了PA，然后依據上文提出的傳輸時延和發送時延，設計了TPA。

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

(1)PA將拓撲中的網絡節點視為普通點，只計算傳輸時延，通過尋找最短路徑，得到網絡設備到控制器的最短距離，進而獲得基于傳輸時延的最佳部署方案；為統一網絡參數，在PA的最后，增加了發送時延，表示在網絡運轉情況下，即有數據在網絡中傳輸時，網絡響應時延的情況；

(2)TPA將傳輸時延和發送時延作為部署方案的參考因素，當計算拓撲中某個網絡節點到控制器的響應時延時，TPA提出將網絡節點以外的其他節點設置為與該網絡節點相同的發送時延；

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

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

4 性能評估

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

表1 PA算法

圖1 網絡拓撲圖

表2 TPA算法

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

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

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

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

(1)3種模型下，TPA的比值要明顯低于PA的比值，表明在網絡響應平均時延相同的情況下，TPA較PA能夠實現更快的網絡響應，網絡節點到控制器的響應時延波動范圍更小。

圖2 時延比較圖

圖3 時延比值圖

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

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

從上述分析可以看出，較PA, TPA在平均時延、最大時延和總時延更低、比值更低，可以更快實現網絡響應；時延優化模型較平均時延最小化模型和最大時延最小化模型在總時延更有優勢，網絡的響應時間更加集中。

5 結束語

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

圖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] 周燁, 楊旭, 李勇, 等. 基于分類的軟件定義網絡流表更新一致性方案[J]. 電子與信息學報, 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年生，博士生，研究方向為下一代互聯網網絡層關鍵技術.

陳 穎： 女，1987年生，碩士生，研究方向為下一代互聯網網絡層關鍵技術.

宋 飛： 男，1983年生，副教授，碩士生導師，研究方向為下一代互聯網網絡層、傳輸層關鍵技術.

張宏科： 男，1957年生，教授，博士生導師，研究方向為下一代互聯網架構、協議理論與技術、移動互聯網絡路由、傳感器網絡技術等.

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改回

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