0 引言

    軟件定義網(wǎng)絡(luò)(Software Defined Networking，SDN)的核心思想在于控制層和轉(zhuǎn)發(fā)層的分離,，OpenFlow^[1]協(xié)議為實(shí)現(xiàn)其倡導(dǎo)的網(wǎng)絡(luò)控制提供可編程接口,，能夠極大簡(jiǎn)化網(wǎng)絡(luò)管理工作,。隨著SDN網(wǎng)絡(luò)應(yīng)用規(guī)模的擴(kuò)大，這種集中工作模式很可能成為其在WAN中的瓶頸點(diǎn)^[2],。為提升網(wǎng)絡(luò)擴(kuò)展性,、可靠性，多控制器部署的思路逐漸受到較多的關(guān)注,。

    多控制器的部署問題可以歸納為：給定一個(gè)網(wǎng)絡(luò)拓?fù)?，需要多少個(gè)控制器能夠滿足網(wǎng)絡(luò)需求，以及如何為這些控制器尋找最優(yōu)位置進(jìn)行部署,。文獻(xiàn)[3,，4]中明確將確定控制器數(shù)量及位置的問題定義為控制器部署問題（Controller Placement Problem，CPP）,。通過文中分析可以看到,，現(xiàn)有研究方向都在向優(yōu)化目標(biāo)的選擇集中，因此控制器部署問題是一個(gè)NP難問題,。

    本文提出故障場(chǎng)景度量值的概念來尋求控制器部署的解決方案,，將節(jié)點(diǎn)間控制路徑連通度作為實(shí)施控制器放置的首要指標(biāo)。

1 相關(guān)工作

    目前對(duì)于CPP的研究主要集中在兩個(gè)方向進(jìn)行：基于時(shí)延優(yōu)化和基于可靠性優(yōu)化,?；跁r(shí)延優(yōu)化主要利用聚類思想來部署控制器及其交換機(jī)集合。該部署思想目前主要有基于平均時(shí)延,、最壞情況時(shí)延^[5]等部署方法,。基于可靠性優(yōu)化的控制器部署研究集中于控制層,，主要圍繞三方面展開：(1)路徑可靠性^[6],；(2)節(jié)點(diǎn)可靠性^[7]；(3)負(fù)載均衡^[8],。也有研究從多目標(biāo)整合優(yōu)化的角度來進(jìn)行基于可靠性部署問題的研究^[9],。

    針對(duì)SDN的可靠性研究分為數(shù)據(jù)層可靠性和控制層可靠性兩方面：(1)數(shù)據(jù)層可靠性：SHARMA S等人^[10]利用OpenFlow1.1協(xié)議的故障轉(zhuǎn)移機(jī)制來實(shí)現(xiàn)數(shù)據(jù)層的故障恢復(fù)，提出并評(píng)估兩種不同的復(fù)原方式的性能,。(2)控制層可靠性：控制層可靠性研究分為控制器及其控制路徑兩部分,。控制器的可靠性是指應(yīng)對(duì)控制器故障的可靠性保證,，這類可靠性可以通過提升控制器自身的可靠性（如使用更加可靠的硬件）或使用多個(gè)備份控制器的方式得到改善^[10],。

    現(xiàn)有OpenFlow廣域網(wǎng)部署可由兩種網(wǎng)絡(luò)類型來實(shí)現(xiàn)：帶內(nèi)網(wǎng)絡(luò)（in-band networks）和帶外網(wǎng)絡(luò)（out-of-band networks），如圖1,、圖2所示,。在帶內(nèi)網(wǎng)絡(luò)中，OpenFlow流能夠共享常規(guī)網(wǎng)絡(luò)流的相同路徑,。在基于OpenFlow的廣域網(wǎng)中使用帶內(nèi)部署更加合理,。根據(jù)OpenFlow1.3.2協(xié)議,，控制器到交換機(jī)的通信路徑實(shí)際上取決于IP路由協(xié)議。在廣域網(wǎng)中,，通常每一對(duì)設(shè)備之間具備多條可用路徑,，當(dāng)前路徑失效時(shí)，其他路徑能夠快速取代并傳輸OpenFlow信息,。因此增強(qiáng)OpenFlow控制通道的多路性能夠提升OpenFlow廣域網(wǎng)的恢復(fù)能力,。

2 故障場(chǎng)景模型描述

    本文的優(yōu)化目標(biāo)在于合理選取控制器的部署位置，具備限制同時(shí)故障發(fā)生數(shù)的能力,，在失效場(chǎng)景中控制路徑減少的情況下,，使失聯(lián)節(jié)點(diǎn)數(shù)最小化，從而保證系統(tǒng)可靠性,。將網(wǎng)絡(luò)拓?fù)淠Ｐ突癁镚(V，E),，其中V表示節(jié)點(diǎn)設(shè)備,，E表示節(jié)點(diǎn)間的網(wǎng)絡(luò)鏈路，文中符號(hào)參數(shù)定義如表1所示,。

2.1 故障場(chǎng)景度量值建模

    在故障場(chǎng)景f_k中,，為便于實(shí)驗(yàn)分析，使用平均鏈路失效概率來衡量該故障場(chǎng)景的整體失效概率,。

    遍歷所有可能的故障場(chǎng)景,，尋找使式(3)具有最小值的節(jié)點(diǎn)i作為控制器部署位置，此時(shí)能夠確保節(jié)點(diǎn)i對(duì)控制路徑具有最低的故障發(fā)生概率,。

    式（4）～式（7）是約束條件,。式（4）是故障場(chǎng)景度量值的取值范圍；式（5）表示控制器處于活躍狀態(tài)時(shí),，c_i取值為1,，否則為0；式（6）表示在故障場(chǎng)景f_k中該節(jié)點(diǎn)與所有節(jié)點(diǎn)路徑連通度小于設(shè)定閾值,，則f_k(C_i)為1,，否則為0；式（7）表示出現(xiàn)故障f_k時(shí),，其所有的鏈路失效概率取值在0～1之間,；式（8）表示首先為每個(gè)控制器分配r個(gè)交換機(jī)，如果有剩余,，再根據(jù)節(jié)點(diǎn)連通度大小將其分配給某個(gè)控制器,。

2.2 基于路徑連通度的域內(nèi)交換機(jī)選取策略

    本文考慮尋找節(jié)點(diǎn)連通度最大的節(jié)點(diǎn)作為交換機(jī)集合來增強(qiáng)該控制器的控制路徑連通效能。

    定義1　控制路徑連通度,。選定每個(gè)控制器放置節(jié)點(diǎn)后,，優(yōu)先選取與控制器節(jié)點(diǎn)路徑連通度最大的前r個(gè)交換機(jī)作為該控制器域內(nèi)交換機(jī)集合,。用控制器部署位置與節(jié)點(diǎn)間不相交路徑平均數(shù)定義路徑連通度，表示如下：

    設(shè)定路徑連通度閾值m_thre,，當(dāng)節(jié)點(diǎn)路徑連通度小于m_thre時(shí),，即認(rèn)為節(jié)點(diǎn)間連通度不足。

2.3 控制路徑選取策略

    所有路徑具有相同失效概率時(shí),，為提高流運(yùn)轉(zhuǎn)效率,，應(yīng)尋找最大剩余帶寬路徑，選擇該路徑作為首要控制路徑并將其他路徑作為備份路徑,。

    定義2　最大剩余帶寬路徑,。式（10）實(shí)現(xiàn)選擇節(jié)點(diǎn)a與節(jié)點(diǎn)b之間最大剩余帶寬路徑p，如下所示：

    路徑的帶寬容量取決于組成該路徑鏈路中的最小帶寬鏈路,，如下式所示：

    路徑p剩余帶寬B_res(p)由路徑p可用帶寬減去已占用帶寬B_al(p)求得：

3 控制器部署算法

    本節(jié)設(shè)計(jì)基于貪婪的控制器放置算法實(shí)現(xiàn)控制器部署,。便于與現(xiàn)有的隨機(jī)放置算法和Survivor^[6]方法進(jìn)行對(duì)比。 

3.1 基于貪婪的控制器放置算法

    基于貪婪的控制器放置算法(Greedy-Based Controller Placement,，GBCP)使用聚類思想尋找控制器及其域內(nèi)管控節(jié)點(diǎn)集合,。在完成所有迭代后，如果存在剩余節(jié)點(diǎn),，通過計(jì)算剩余節(jié)點(diǎn)與各個(gè)控制器之間的連通性關(guān)系,，再將其分配至各個(gè)控制器域。

    基于貪婪的控制器放置算法（GBCP）：

    輸入：G=(V,，E),，控制器數(shù)m，故障場(chǎng)景集合F,；

    輸出：C,，S_u。

(1)i=0,，V₁=V

(2)for u in V₁

(3)計(jì)算u在所有已知可能的故障場(chǎng)景F中的f(C_i),，并升序排序；

(4)選擇具有最小f(C_i)的節(jié)點(diǎn)u（如有多個(gè)相同的節(jié)點(diǎn),，則隨機(jī)選擇）,，加入控制器集合C中；

(5)通過式(9)選取出與節(jié)點(diǎn)u連通度最大的前r個(gè)點(diǎn)作為該控制域內(nèi)的交換機(jī)集合S_u,；

(6)把節(jié)點(diǎn)u和集合S_u內(nèi)的所有節(jié)點(diǎn)從集合V₁中移除,；

(7)i=i+1  

(8)if i<m：返回以上for循環(huán)；

(9)else if i=m：

(10)if V₁≠φ：

(11)for v in V₁

(12)計(jì)算v 和集合C中各控制器的連通性關(guān)系,，并將其分配至連通度最大的控制器域中,；

(13)end for

(14)end for

3.2 其他算法介紹

    該兩種方案是現(xiàn)有的用來獲取m個(gè)控制器位置實(shí)現(xiàn)控制器部署的實(shí)施方案。

    （1）隨機(jī)放置算法（random）：該算法是隨機(jī)地在所有可能的V個(gè)節(jié)點(diǎn)中選取m個(gè)位置作為控制器部署節(jié)點(diǎn),。

    （2）Survivor：該方法通過明確考慮路徑多樣性從而增強(qiáng)節(jié)點(diǎn)連通性,；在控制器部署中增加容量感知機(jī)制,，主動(dòng)避免控制器的過載問題；通過控制器容量的備用剩余容量實(shí)現(xiàn)故障恢復(fù)機(jī)制,。

4 性能評(píng)估

    為方便實(shí)驗(yàn),，設(shè)定每個(gè)實(shí)驗(yàn)場(chǎng)景中所有鏈路具有相同的鏈路失效概率，因此實(shí)驗(yàn)中使用鏈路失效概率來量化故障場(chǎng)景度量值,。 

    在Internet 2,、RNP、GEANT,、GOODNET,、ARPANET19719等網(wǎng)絡(luò)拓?fù)鋵?shí)施如下實(shí)驗(yàn)內(nèi)容：（1）使用GBCP部署方法，計(jì)算出控制器數(shù)目變化與控制路徑損失率的關(guān)系,；設(shè)定所有路徑故障概率都為0.05,；（2）在GBCP部署方法得到最佳控制器數(shù)目時(shí)，通過平均路徑失效概率的變化,，觀察各部署方案的網(wǎng)絡(luò)拓?fù)渲锌刂坡窂降膿p失情況,；（3）對(duì)比使用本文提出的部署方案，每個(gè)網(wǎng)絡(luò)拓?fù)渲胁渴鸩煌瑪?shù)目的控制器對(duì)應(yīng)時(shí)延變化情況,。

    圖3是控制器數(shù)目與控制路徑損失率之間的對(duì)應(yīng)關(guān)系，其中m/n表示控制器數(shù)目m與交換機(jī)節(jié)點(diǎn)數(shù)目n之間的比率,。分析發(fā)現(xiàn),，以上5種實(shí)驗(yàn)拓?fù)涞那€變化具有相似的特征，并且m的取值在0.073n～0.164n之間具有最佳的控制路徑可靠性,。這是因?yàn)楸M管廣域網(wǎng)中通常需要較多的控制器來保證可靠性,，但控制器數(shù)目不斷地增加又會(huì)造成控制器與交換機(jī)之間的路徑連通度降低，控制路徑損失也相應(yīng)地增加,。因此實(shí)際網(wǎng)絡(luò)拓?fù)渲械目刂破鞑渴鹦柚?jǐn)慎選擇控制器的數(shù)目,。

    在實(shí)驗(yàn)（1）中已經(jīng)獲知，GBCP的部署方案在每個(gè)網(wǎng)絡(luò)拓?fù)渲卸加邢嗨频男阅鼙憩F(xiàn),，因此僅選取Internet 2(m=0.122n)測(cè)試3種部署方法得到的路徑失效概率與控制路徑損失率的關(guān)系,。圖4是路徑失效概率與控制路徑損失率之間的關(guān)系。隨著路徑失效概率的上升,，控制路徑損失率也呈現(xiàn)增加的趨勢(shì),；相同路徑失效概率時(shí)，Survivor控制路徑損失率始終最低,，random最高,。在路徑失效概率為0.1時(shí)，random控制路徑損失率高達(dá)54%,。相比隨機(jī)放置算法,，使用最大路徑連通效能的部署方案能夠降低路徑損失率,，提升控制路徑可靠性。

    現(xiàn)有研究表明,，每個(gè)控制器在200 ms時(shí)限內(nèi)可以保證流安裝時(shí)間的一致性^[11],。實(shí)驗(yàn)（1）在5種拓?fù)溥M(jìn)行實(shí)驗(yàn)的同時(shí)，對(duì)其相應(yīng)時(shí)延情況也做了統(tǒng)計(jì),。圖5,、圖6分別是控制器數(shù)目變化與平均時(shí)延^[3]和最壞情況時(shí)延^[3]的關(guān)系?？刂破鲾?shù)取值在區(qū)間（0.073n,，0.164n）之間時(shí)，平均時(shí)延最大值為18 ms,，最壞情況時(shí)延最大值為83 ms,。文中基于可靠性優(yōu)化的控制器部署方案選取最優(yōu)控制器數(shù)目后所產(chǎn)生的時(shí)延仍然在控制器可承受的性能范圍內(nèi)，從而保證SDN網(wǎng)絡(luò)在基于可靠性進(jìn)行控制器部署時(shí)不受時(shí)延約束,。

5 結(jié)語(yǔ)

    本文利用最大化控制路徑可靠性的思想來解決SDN中的控制器部署問題,。使用故障場(chǎng)景度量值的方法來保證控制路徑失效率最小化，并權(quán)衡可靠性與時(shí)延的關(guān)系,。通過使用不同的放置算法進(jìn)行實(shí)驗(yàn),，得到以下結(jié)論：控制器部署的性能取決于使用的控制器部署方法；必須合理選擇控制器數(shù)目,；基于可靠性優(yōu)化得到的最優(yōu)控制器部署,，其產(chǎn)生的時(shí)延在控制器響應(yīng)時(shí)間限制范圍內(nèi)。

參考文獻(xiàn)

[1] GUDE N,，KOPONEN T,，PETTIT J，et al.NOX：towards an operating system for networks[J].Acm Sigcomm Computer Communication Review,，2008,，38(3)：105-110.

[2] TOOTOONCHIAN A，GANJALI Y.HyperFlow：a distributed control plane for OpenFlow[C].Internet Network Management Conference on Research on Enterprise NETWORKING,，Washington,，DC，2010.USENIX Association,，2010.

[3] HELLER B,，SHERWOOD R，MCKEOWN N.The controller placement problem[J].Acm Sigcomm Computer Communication Review,，2013,，42(4)：7-12.

[4] UL HUQUE M T I，JOURJON G，GRAMOLI V.Revisiting the controller placement problem[C].IEEE,，Conference on Local Computer Networks,，Clearwater，F(xiàn)lorida,，USA,，2015.IEEE Computer Society，2015：450-453.

[5] 姚琳元,，陳穎,，宋飛，等.基于時(shí)延的軟件定義網(wǎng)絡(luò)快速響應(yīng)控制器部署[J].電子與信息學(xué)報(bào),，2014(12)：2802-2808.

[6] MULLER L F,，OLIVEIRA R R，LUIZELLI M C,，et al.Survivor：An enhanced controller placement strategy for improving SDN survivability[C].IEEE Global Communications Conference,，2014：1909-1915.

[7] ZHANG Y，BEHESHTI N,，TATIPAMULA M.On resilience of split-architecture networks[C].Global Telecommunications Conference(GLOBECOM 2011),，2011，2011：1-6.

[8] GUO Z,，SU M,，XU Y，et al.Improving the performance of load balancing in software-defined networks through load variance-based synchronization[J].Computer Networks,，2014,，68(11)：95-109.

[9] LANGE S，GEBERT S,，ZINNER T,，et al.Heuristic approaches to the controller placement problem in large scale SDN networks[J].IEEE Transactions on Network & Service Management,，2015,，12(1)：1.

[10] SHARMA S，STAESSENS D,，COLLE D,，et al.Enabling fast failure recovery in OpenFlow networks[C].International Workshop on the Design of Reliable Communication Networks，Drcn,，2011.Krakow,，Poland，2011：164-171.

[11] ABBAS G.Network survivability[M].Springer US,，2006.

作者信息:

毛  明,，陳庶樵，崔世建

（國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州450002）