0 引言

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

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

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

1 相關工作

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

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

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

2 故障場景模型描述

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

2.1 故障場景度量值建模

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

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

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

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

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

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

    設定路徑連通度閾值m_thre，當節(jié)點路徑連通度小于m_thre時，即認為節(jié)點間連通度不足。

2.3 控制路徑選取策略

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

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

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

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

3 控制器部署算法

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

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

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

    基于貪婪的控制器放置算法（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é)點u（如有多個相同的節(jié)點，則隨機選擇），加入控制器集合C中；

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

(6)把節(jié)點u和集合S_u內(nèi)的所有節(jié)點從集合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中各控制器的連通性關系，并將其分配至連通度最大的控制器域中；

(13)end for

(14)end for

3.2 其他算法介紹

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

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

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

4 性能評估

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

    在Internet 2、RNP、GEANT、GOODNET、ARPANET19719等網(wǎng)絡拓撲實施如下實驗內(nèi)容：（1）使用GBCP部署方法，計算出控制器數(shù)目變化與控制路徑損失率的關系；設定所有路徑故障概率都為0.05；（2）在GBCP部署方法得到最佳控制器數(shù)目時，通過平均路徑失效概率的變化，觀察各部署方案的網(wǎng)絡拓撲中控制路徑的損失情況；（3）對比使用本文提出的部署方案，每個網(wǎng)絡拓撲中部署不同數(shù)目的控制器對應時延變化情況。

    圖3是控制器數(shù)目與控制路徑損失率之間的對應關系，其中m/n表示控制器數(shù)目m與交換機節(jié)點數(shù)目n之間的比率。分析發(fā)現(xiàn)，以上5種實驗拓撲的曲線變化具有相似的特征，并且m的取值在0.073n～0.164n之間具有最佳的控制路徑可靠性。這是因為盡管廣域網(wǎng)中通常需要較多的控制器來保證可靠性，但控制器數(shù)目不斷地增加又會造成控制器與交換機之間的路徑連通度降低，控制路徑損失也相應地增加。因此實際網(wǎng)絡拓撲中的控制器部署需謹慎選擇控制器的數(shù)目。

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

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

5 結(jié)語

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

參考文獻

[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)絡快速響應控制器部署[J].電子與信息學報，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)工程技術研究中心，河南 鄭州450002）