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)化。基于時(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）