0 引言

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

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

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

1 相關工作

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

    針對SDN的可靠性研究分為數據層可靠性和控制層可靠性兩方面：(1)數據層可靠性：SHARMA S等人^[10]利用OpenFlow1.1協議的故障轉移機制來實現數據層的故障恢復，提出并評估兩種不同的復原方式的性能。(2)控制層可靠性：控制層可靠性研究分為控制器及其控制路徑兩部分?？刂破鞯目煽啃允侵笐獙刂破鞴收系目煽啃员ＷC，這類可靠性可以通過提升控制器自身的可靠性（如使用更加可靠的硬件）或使用多個備份控制器的方式得到改善^[10]。

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

2 故障場景模型描述

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

2.1 故障場景度量值建模

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

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

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

2.2 基于路徑連通度的域內交換機選取策略

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

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

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

2.3 控制路徑選取策略

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

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

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

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

3 控制器部署算法

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

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

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

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

    輸入：G=(V，E)，控制器數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)的節點u（如有多個相同的節點，則隨機選擇），加入控制器集合C中；

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

(6)把節點u和集合S_u內的所有節點從集合V₁中移除；

(7)i=i+1  

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

(9)else if i=m：

(10)if V₁≠φ：

(11)for v in V₁

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

(13)end for

(14)end for

3.2 其他算法介紹

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

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

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

4 性能評估

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

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

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

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

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

5 結語

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

參考文獻

[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，Florida，USA，2015.IEEE Computer Society，2015：450-453.

[5] 姚琳元，陳穎，宋飛，等.基于時延的軟件定義網絡快速響應控制器部署[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.

作者信息:

毛  明，陳庶樵，崔世建

（國家數字交換系統工程技術研究中心，河南 鄭州450002）