0 引言

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

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

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

1 相關(guān)工作

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

    針對SDN的可靠性研究分為數(shù)據(jù)層可靠性和控制層可靠性兩方面：(1)數(shù)據(jù)層可靠性：SHARMA S等人^[10]利用OpenFlow1.1協(xié)議的故障轉(zhuǎn)移機(jī)制來實(shí)現(xiàn)數(shù)據(jù)層的故障恢復(fù),，提出并評估兩種不同的復(fù)原方式的性能。(2)控制層可靠性：控制層可靠性研究分為控制器及其控制路徑兩部分,?？刂破鞯目煽啃允侵笐?yīng)對控制器故障的可靠性保證，這類可靠性可以通過提升控制器自身的可靠性（如使用更加可靠的硬件）或使用多個備份控制器的方式得到改善^[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)中,，通常每一對設(shè)備之間具備多條可用路徑,，當(dāng)前路徑失效時，其他路徑能夠快速取代并傳輸OpenFlow信息,。因此增強(qiáng)OpenFlow控制通道的多路性能夠提升OpenFlow廣域網(wǎng)的恢復(fù)能力,。

2 故障場景模型描述

    本文的優(yōu)化目標(biāo)在于合理選取控制器的部署位置,，具備限制同時故障發(fā)生數(shù)的能力，在失效場景中控制路徑減少的情況下,，使失聯(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ò)鏈路,，文中符號參數(shù)定義如表1所示,。

2.1 故障場景度量值建模

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

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

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

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

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

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

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

2.3 控制路徑選取策略

    所有路徑具有相同失效概率時，為提高流運(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è)計基于貪婪的控制器放置算法實(shí)現(xiàn)控制器部署。便于與現(xiàn)有的隨機(jī)放置算法和Survivor^[6]方法進(jìn)行對比,。 

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

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

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

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

    輸出：C，S_u,。

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

(2)for u in V₁

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

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

(5)通過式(9)選取出與節(jié)點(diǎn)u連通度最大的前r個點(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)計算v 和集合C中各控制器的連通性關(guān)系，并將其分配至連通度最大的控制器域中,；

(13)end for

(14)end for

3.2 其他算法介紹

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

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

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

4 性能評估

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

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

    圖3是控制器數(shù)目與控制路徑損失率之間的對應(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ù)目不斷地增加又會造成控制器與交換機(jī)之間的路徑連通度降低,，控制路徑損失也相應(yīng)地增加,。因此實(shí)際網(wǎng)絡(luò)拓?fù)渲械目刂破鞑渴鹦柚?jǐn)慎選擇控制器的數(shù)目。

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

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

5 結(jié)語

    本文利用最大化控制路徑可靠性的思想來解決SDN中的控制器部署問題。使用故障場景度量值的方法來保證控制路徑失效率最小化,，并權(quán)衡可靠性與時延的關(guān)系,。通過使用不同的放置算法進(jìn)行實(shí)驗(yàn)，得到以下結(jié)論：控制器部署的性能取決于使用的控制器部署方法,；必須合理選擇控制器數(shù)目,；基于可靠性優(yōu)化得到的最優(yōu)控制器部署，其產(chǎn)生的時延在控制器響應(yīng)時間限制范圍內(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] 姚琳元，陳穎,，宋飛,，等.基于時延的軟件定義網(wǎng)絡(luò)快速響應(yīng)控制器部署[J].電子與信息學(xué)報，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.

作者信息:

毛  明，陳庶樵,，崔世建

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