基于拜占庭容錯提高SDN控制層可靠性的研究

李軍飛 胡宇翔 鄔江興

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)(lijunfei90@qq.com)

基于拜占庭容錯提高SDN控制層可靠性的研究

李軍飛 胡宇翔 鄔江興

(國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002)(lijunfei90@qq.com)

軟件定義網(wǎng)絡(luò)(software defined network， SDN)提出了控制與轉(zhuǎn)發(fā)分離的設(shè)計(jì)結(jié)構(gòu)，實(shí)現(xiàn)了開放的可編程網(wǎng)絡(luò)接口，為網(wǎng)絡(luò)提供了更細(xì)粒度的管理.然而，SDN在為網(wǎng)絡(luò)應(yīng)用帶來創(chuàng)新與便利的同時，也面臨著一些新的問題.針對SDN網(wǎng)絡(luò)中控制層的可靠性問題，提出了一種容忍拜占庭錯誤的方法.首先，結(jié)合SDN網(wǎng)絡(luò)的特性，具體闡述了在應(yīng)用拜占庭容錯算法時的網(wǎng)絡(luò)結(jié)構(gòu)、工作流程和異常處理等，并對其中的多控制器位置部署問題建立分析模型;然后，針對該多控制器部署問題，設(shè)計(jì)了啟發(fā)式求解算法;最后，通過仿真實(shí)驗(yàn)對該容錯方法和部署算法進(jìn)行驗(yàn)證.實(shí)驗(yàn)結(jié)果表明:該容錯方法能夠有效處理控制器中的錯誤，提高控制層的可靠性，但對系統(tǒng)的性能會造成一定程度的影響.同時，該部署算法能夠有效降低處理OpenFlow請求的傳輸延遲.

軟件定義網(wǎng)絡(luò)；OpenFlow；拜占庭容錯；可靠性；控制器部署

隨著網(wǎng)絡(luò)應(yīng)用的快速發(fā)展，傳統(tǒng)的網(wǎng)絡(luò)交換設(shè)備承載著越來越多的控制邏輯，已難以適應(yīng)虛擬化、云計(jì)算、大數(shù)據(jù)及相關(guān)業(yè)務(wù)發(fā)展對數(shù)據(jù)高速傳輸、資源靈活配置、協(xié)議快速部署的需求.軟件定義網(wǎng)絡(luò)(software defined network， SDN)提出了控制與轉(zhuǎn)發(fā)分離的設(shè)計(jì)結(jié)構(gòu)，實(shí)現(xiàn)了開放的可編程網(wǎng)絡(luò)接口，為網(wǎng)絡(luò)提供了更細(xì)粒度的管理，引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛研究.然而，SDN在為網(wǎng)絡(luò)應(yīng)用帶來創(chuàng)新與便利的同時，也面臨著一些新的問題，如控制器的安全性[1]、交換機(jī)的轉(zhuǎn)發(fā)效率[2]以及流表的一致性[3]等，制約了其在應(yīng)用網(wǎng)絡(luò)中的廣泛部署.

例如，相對于傳統(tǒng)的網(wǎng)絡(luò)，SDN采用集中式控制，使得網(wǎng)絡(luò)的管理更為簡捷和高效，但同時也引入了新的安全威脅.其中，SDN控制器大多是部署在計(jì)算機(jī)上，其智能化程度更高，但往往也具有更多的漏洞，降低了針對控制器的攻擊難度.另一方面，SDN控制器負(fù)責(zé)整個網(wǎng)絡(luò)的管理和維護(hù)，其一旦出現(xiàn)錯誤，將對整個網(wǎng)絡(luò)的正常運(yùn)行造成影響，具有更大的危害性.

針對SDN控制層存在的上述可靠性問題，OpenFlow v1.2[4]協(xié)議提出了多控制器的方法，多個控制器之間構(gòu)成主備冗余的關(guān)系.在主控制器由于發(fā)生錯誤而停止工作時，選擇其中的一個從控制器轉(zhuǎn)變?yōu)橹骺刂破?然而，在實(shí)際應(yīng)用中，控制器更多的是發(fā)生拜占庭錯誤(Byzantine fault)，而不僅是造成宕機(jī)的良性錯誤(Benign fault).拜占庭錯誤具有一定的隱蔽性，它是在控制器對外表現(xiàn)仍能工作的情況下，對交換機(jī)的請求輸出任意錯誤響應(yīng)，或按照攻擊者的意圖輸出具有破壞性的響應(yīng).因此，目前SDN網(wǎng)絡(luò)中的主備切換機(jī)制還難以發(fā)現(xiàn)和處理拜占庭錯誤，給控制層的可靠性造成了嚴(yán)重的威脅.

借鑒已有系統(tǒng)處理拜占庭錯誤的方法，如冗余文件系統(tǒng)[5]、分布式計(jì)算系統(tǒng)[6]等，本文嘗試著將拜占庭容錯算法(Byzantine fault tolerance， BFT)引入到SDN網(wǎng)絡(luò)中，希望能夠引起相關(guān)研究者的興趣.BFT算法需要多個控制器之間協(xié)同工作，對輸出給交換機(jī)的響應(yīng)進(jìn)行表決，以檢測出部分控制器出現(xiàn)的異常并予以及時處理，從而達(dá)到增強(qiáng)控制層可靠性的效果.

1 相關(guān)工作

SDN控制層是SDN網(wǎng)絡(luò)中的核心部分，負(fù)責(zé)數(shù)據(jù)層的管理和維護(hù)，但由于其采用集中式控制，在出現(xiàn)錯誤或遭受攻擊時，對網(wǎng)絡(luò)造成的危害更大.例如，Diego等人[1]分析總結(jié)了SDN網(wǎng)絡(luò)中的7類安全問題，其中5類存在于控制層面，且具有更強(qiáng)的破壞性.因此，控制層可靠性的研究是目前SDN領(lǐng)域中的熱點(diǎn)，研究者從不同的角度來分析和解決集中式控制帶來的安全缺陷.

系統(tǒng)結(jié)構(gòu)上，Casado等人[7]提出了FortNOX架構(gòu)，它是基于OpenFlow控制器NOX的軟件擴(kuò)展，提供了身份認(rèn)證和安全約束機(jī)制.FortNOX使得NOX控制器能夠?qū)崟r地檢查流表項(xiàng)中的沖突，及時發(fā)現(xiàn)具有破壞意圖的上層惡意應(yīng)用.然而，該結(jié)構(gòu)僅是針對單個控制器內(nèi)的安全問題，并不能解決控制器節(jié)點(diǎn)的失效問題.同時，Shin等人[8]提出了基于模塊化組合的FRESCO架構(gòu)，通過調(diào)用腳本API來監(jiān)測代碼運(yùn)行或發(fā)現(xiàn)安全威脅.因此，F(xiàn)RESCO的防護(hù)效果取決于模塊化庫的功能強(qiáng)弱，同樣也難以應(yīng)對節(jié)點(diǎn)失效的安全問題.

具體應(yīng)用上，Hu等人[9]研究了多控制器部署位置的問題，提高了SDN網(wǎng)絡(luò)在單控制器節(jié)點(diǎn)失效情況下的可恢復(fù)力.Jagadeesan等人[10]提出了網(wǎng)絡(luò)分塊控制的思想，使得單個控制器在被攻破的情況下，整個網(wǎng)絡(luò)依然有安全保證.Hu等人[11]在SDN網(wǎng)絡(luò)中引入了防火墻的技術(shù)，結(jié)合SDN的特性，通過精確檢測和規(guī)則過濾，提高了網(wǎng)絡(luò)的抗攻擊能力.

另外，Li等人[12]提出了一種新穎的控制方法，多個冗余的控制器之間相互協(xié)作，打破傳統(tǒng)的主備切換的方式，使得控制層具有容忍拜占庭錯誤的能力.然而，文獻(xiàn)[12]重點(diǎn)研究了交換機(jī)與控制器之間多對多的對應(yīng)關(guān)系，僅簡單介紹了該算法的容錯原理，沒有結(jié)合SDN網(wǎng)絡(luò)的具體場景對其工作機(jī)制和實(shí)現(xiàn)方法做進(jìn)一步的研究.而且，該研究沒有給出BFT算法對SDN網(wǎng)絡(luò)在性能方面上造成的影響.

2 基于拜占庭容錯的SDN架構(gòu)

2.1 工作流程

與傳統(tǒng)SDN控制層處理OF(OpenFlow)請求的方式不同，基于BFT算法的SDN網(wǎng)絡(luò)需要多個控制器之間協(xié)同處理，對輸出響應(yīng)進(jìn)行表決，以防止異常控制器對網(wǎng)絡(luò)造成破壞.該容錯方法不僅能夠應(yīng)對造成控制器宕機(jī)的良性錯誤，而且也能夠抵抗由于外部攻擊或自身錯誤導(dǎo)致的控制器輸出異常的拜占庭錯誤.同時，基于BFT算法的SDN網(wǎng)絡(luò)需要多個控制器相互協(xié)作，彼此之間相互檢測對方是否發(fā)生錯誤，但不需要復(fù)雜的差錯檢驗(yàn)機(jī)制來驗(yàn)證自身是否出現(xiàn)錯誤.

2.1.1 算法流程

對于要容忍f個控制器錯誤的SDN網(wǎng)絡(luò)，典型的BFT算法通常需要3f+1個控制器，構(gòu)成處理OF請求的冗余系統(tǒng).其中，3f+1個控制器構(gòu)成的集合稱為群視圖，記為v.BFT算法的流程如圖1所示:

Fig. 1 The procedure of BFT in SDN圖1 SDN網(wǎng)絡(luò)中BFT算法的流程

圖1中，of表示交換機(jī)發(fā)出的OF請求，ppre，pre，commit，reply表示BFT算法運(yùn)行的狀態(tài)，v表示控制器以自己的視角所看到的群視圖，n是對當(dāng)前of消息的編號，D(of)表示OF消息的摘要.BFT算法大致分為5個步驟：

1) 主控制器接收到交換機(jī)發(fā)送的OF請求，驗(yàn)證其正確性.若正確，則給請求分配序列號n，系統(tǒng)進(jìn)入pre-prepare階段，并對外廣播該請求.

2) 各控制器接收到ppre消息，驗(yàn)證其相對于自身的正確性.若正確，控制器進(jìn)入prepare階段，對外廣播確認(rèn)接收到請求的prepare消息，其中，D(of)表示OF請求的摘要.

3) 各控制器接受到prepare消息，驗(yàn)證其相對于自身的正確性，并檢查其是否在當(dāng)前的群視圖.若滿足條件，且接收到2f個來自不同控制器的prepare消息，則進(jìn)入commit階段，對外廣播commit消息.

4) 各控制器接受到commit消息，驗(yàn)證其正確性，并檢查其是否在當(dāng)前的群視圖.若滿足條件，且接收到2f個來自不同控制器的commit消息，則處理該OF請求，并將響應(yīng)reply消息返回給交換機(jī).

5) 交換機(jī)接收到f+1個來自不同控制器的相同的且驗(yàn)證通過的reply消息時，則認(rèn)定該響應(yīng)為請求處理的結(jié)果.

上述流程主要是為了在多個控制器共同處理來自不同交換機(jī)的多個OF請求時，保證其處理請求順序的一致性以及返回響應(yīng)的一致性.其中，對于步驟5，由于其與目前交換機(jī)的工作方式不同，我們可以通過在交換機(jī)里加入該部分的控制邏輯，或在交換機(jī)與控制器之間加入相應(yīng)的代理器(類似于FlowVisor)來實(shí)現(xiàn)對多個輸入的表決判斷.另外，控制器之間的消息交互，可以通過東西向的接口來實(shí)現(xiàn).對于算法流程中的消息驗(yàn)證，如ai，μi s等是為了防止來自破壞者的虛假消息，以及消息在網(wǎng)絡(luò)傳輸過程中被篡改，我們可以采用公鑰密碼對消息的來源和完整性進(jìn)行驗(yàn)證.

2.1.2 容錯機(jī)制

BFT算法的主要作用就是能夠及時發(fā)現(xiàn)群視圖中控制器成員的異常，對其進(jìn)行主動恢復(fù)或切換當(dāng)前的群視圖，以防止其對系統(tǒng)的正常工作造成影響.對于SDN網(wǎng)絡(luò)中的從控制器異常，如圖1中控制器Controller 2，當(dāng)其為良性錯誤時，則停止工作，不再與其余控制器進(jìn)行交互，使得該錯誤能夠被主控制器及時發(fā)現(xiàn)；當(dāng)其為拜占庭錯誤時，則行為異常，甚至輸出具有破壞目的的響應(yīng).由于其輸出的結(jié)果與大多數(shù)控制器的結(jié)果不一致，交換機(jī)(或代理器)在擇多判決多個控制器的輸出結(jié)果時，能夠及時發(fā)現(xiàn)該控制器的異常.

對于主控制器的異常，如圖1中控制器c0，當(dāng)其為良性錯誤時，則與所管理的交換機(jī)失去連接，這些交換機(jī)嘗試連接至某一從控制器，進(jìn)而發(fā)現(xiàn)主控制器的錯誤；當(dāng)其為拜占庭錯誤時，造成其余控制器在交互時關(guān)于視圖v無法達(dá)成一致，或交換機(jī)得不到f+1個相同的輸出結(jié)果.此時，由于無法完成正常的BFT流程，可以判斷主控制器發(fā)生了異常.

2.1.3 群視圖切換

當(dāng)群視圖中異常控制器的數(shù)量達(dá)到h(h≤f)，或主控制器出現(xiàn)錯誤時，為保證控制層能夠正確處理交換機(jī)的OF請求，需要進(jìn)行群視圖切換，選擇一些功能正常的控制器作為新的視圖.如圖2所示，原群視圖v={c0,c1,c2,c3}，在主控制器c0出現(xiàn)異常時，視圖中其余的成員發(fā)起視圖切換的請求，將其對外廣播.控制器接收到視圖切換請求的消息，選取其中編號較小的控制器作為主控制器，并向其發(fā)送視圖確認(rèn)的消息.某一控制器在接收到3f個來自不同控制器的視圖確認(rèn)的消息后，則認(rèn)定為主控制器，產(chǎn)生新的群視圖v′={c0,c1,c2,c3,c4}，并向v′中的其余控制器廣播新群視圖的消息.

群視圖的切換有助于SDN網(wǎng)絡(luò)在應(yīng)用BFT算法能夠容忍f個錯誤的基礎(chǔ)上，進(jìn)一步增強(qiáng)網(wǎng)絡(luò)的可靠性和安全性.但同時也意味著，網(wǎng)絡(luò)中要有更多的控制器，以在視圖切換時有正常的控制器可供使用.進(jìn)一步地，可以在該網(wǎng)絡(luò)中引入主動恢復(fù)機(jī)制[14]，使得即使在有限數(shù)量的控制器下，控制層依然可以在不同的時刻進(jìn)行群視圖切換.

Fig. 2 The procedure of change quorum view圖2 群視圖的切換過程

2.2 網(wǎng)絡(luò)結(jié)構(gòu)

在運(yùn)行BFT算法時，交換機(jī)可以以任一控制器為主控制器，且可以在其之間動態(tài)切換，因此，交換機(jī)與控制器之間要實(shí)現(xiàn)多對多的連通.另一方面，控制器之間為了實(shí)現(xiàn)處理請求和網(wǎng)絡(luò)視圖的一致性，需要相互通信，因此，控制器之間是要相互連通的.如圖3所示，對于帶外通信(Out-Band)的SDN網(wǎng)絡(luò)，要實(shí)現(xiàn)BFT算法，不僅控制器之間需要互相連通，而且交換機(jī)與其群視圖(quorum view)內(nèi)的控制器也要全部實(shí)現(xiàn)互連；對于帶內(nèi)通信(In-Band)的SDN網(wǎng)絡(luò)，其OF控制流和控制器之間的數(shù)據(jù)流可以通過數(shù)據(jù)平面中的路徑傳輸，大大降低了網(wǎng)絡(luò)互連的復(fù)雜度，但同時也增加了通信的延遲和開銷.

Fig. 3 The SDN network based on BFT圖3 基于BFT算法的SDN網(wǎng)絡(luò)結(jié)構(gòu)

另外，在具體設(shè)計(jì)基于BFT算法的SDN網(wǎng)絡(luò)結(jié)構(gòu)時，有3點(diǎn)值得注意：1)控制器之間的網(wǎng)絡(luò)拓?fù)渚哂休^強(qiáng)的連通性，即單個控制器故障不會影響其余控制器間的通信；2)交換機(jī)與控制器之間具有較近的拓?fù)渚嚯x，以降低控制流的傳輸時延；3)控制器之間的網(wǎng)絡(luò)連接具有較高的可靠性，保證BFT算法的通信效率，以提高服務(wù)請求的處理速度.

2.3 CDB問題

分析上述基于BFT算法的SDN網(wǎng)絡(luò)，為了提高其控制層的可靠性，帶來了大量的控制器冗余及通信開銷.所以，在部署該網(wǎng)絡(luò)時，我們需要考慮交換機(jī)與控制器之間的連接關(guān)系，以盡可能地提高網(wǎng)絡(luò)的性能，減小該方法帶來的負(fù)面影響.例如，文獻(xiàn)[12]針對帶外通信的SDN網(wǎng)絡(luò)，研究了交換機(jī)與控制器之間多對多的對應(yīng)關(guān)系，以滿足運(yùn)行BFT算法的通信延遲、控制器負(fù)載等約束條件.對于帶內(nèi)通信的SDN網(wǎng)絡(luò)，研究者更多地關(guān)注控制器位置的部署，以提高網(wǎng)絡(luò)的彈性[15]和可靠性[16].同樣，其對BFT算法的運(yùn)行效率也具有重要的影響，因此，本文我們將重點(diǎn)研究BFT算法下多控制器的位置部署(controllers’ deployment with BFT, CDB)問題.

為了便于表述和計(jì)算，結(jié)合圖1(b)，我們首先針對基于BFT算法的SDN網(wǎng)絡(luò)，給出4點(diǎn)模型假設(shè)：

1) 控制層具有n個控制器，設(shè)定其能容忍f個錯誤.為了使得在發(fā)生錯誤時，BFT算法能夠切換群視圖，需要n>3f+1.

2) 對于交換機(jī)si，為了減低OF請求的傳輸延遲，選擇距離其最近的控制器j作為主控制器pi，即?ch∈C,δi j≤δi h.

3) 對于主控制器pi，為了降低控制器之間的通信延遲，選擇距離其最近的2f個控制器，構(gòu)成基于BFT算法交換機(jī)i的控制器集合φi，即?cj∈φi,ch?φi∧ch∈C,γi j≤γi h.

4) 為了降低單個交換機(jī)失效對控制層造成的影響，假定一個交換機(jī)上最多部署一個控制器，即?ci,cj∈C且i≠j,ψ(i)≠ψ(j).

CDB問題可以針對不同的優(yōu)化目標(biāo)，如傳輸時延、通信開銷、資源利用率等，分別對應(yīng)著不同的目標(biāo)函數(shù).本文將以傳輸時延為例，研究SDN網(wǎng)絡(luò)中控制器的優(yōu)化部署，以期提高BFT算法下處理OF請求的速度.

3 CDB問題的求解

3.1 計(jì)算過程

對于一個具有m個交換機(jī)的SDN網(wǎng)絡(luò)，其數(shù)據(jù)層的網(wǎng)絡(luò)拓?fù)淇梢杂绵徑泳仃嚤硎緸镚=(ai j)m×m.其中，ai j是邊〈si,sj〉的權(quán)重，表示該路徑上的傳輸延遲，當(dāng)si與sj無直接連接時，ai j=+∞.進(jìn)而，可以使用Dijkstra算法求得任意2個交換機(jī)間的最短距離，即G′=(di j)m×m.對于CDB問題，在給定常量矩陣G′和變量函數(shù)ψ(i)的情況下，根據(jù)2.3節(jié)中的假設(shè)，可以計(jì)算出表1中的中間量pi，φi，δi j，γi j.例如：

控制器在運(yùn)行BFT算法時，處理交換機(jī)si的一次OF請求需要經(jīng)歷5個階段，如圖2所示.對于request階段，其路徑傳輸延遲為

Treq=δi jv，j=ψ(pi)，

(1)

Table1 Symbols in CDB Problem表1 CDB問題中的符號

Treq=δi jv，j=ψ(pi)，

SymbolMeaningGtopologyofdataplaneCcontrollersetsiswitchiαitheamountofOFsentbyswitchicicontrolleripimastercontrollerofswitchi?icontrollersetofswitchibasedonBFTδijtheshortestdistancebetweenswitchiandcontrollerjγijtheshortestdistancebetweencontrolleriandcontrollerjψ(i)positionthatdeployscontrolleri

其中，v表示信號在鏈路中的傳輸速度.對于pre-prepare階段，主控制器需要與群視圖內(nèi)的其余控制器通信，我們選擇其中延遲最大的路徑做為該階段的傳輸延遲，即:

Tppre=max(γh j)v，
j=ψ(pi),h∈φi.

(2)

對于prepare階段和commit階段，群視圖內(nèi)的任意1個控制器均需要通信，同理，該階段的傳輸延遲為

Tpre=Tcom=max(γr t)v，r,t∈φi.

(3)

對于返回響應(yīng)的reply階段，其傳輸延遲為

Trep=max(δi q)v，q∈φi.

(4)

由式(1)～(4)求和可得，處理交換機(jī)si的一次OF請求的總路徑延遲為

考慮到各個交換機(jī)產(chǎn)生OF請求的數(shù)量不同，我們采用該SDN網(wǎng)絡(luò)處理OF請求的平均傳輸延遲時間T作為度量指標(biāo)，表示為

即:

(5)

因此，該CDB問題可以形式化描述為：在給定數(shù)據(jù)層網(wǎng)絡(luò)拓?fù)鋱DG的情況下，求控制器的部署位置ψ(i)，使得式(5)中的平均傳輸延遲T取得最小值，以提高SDN網(wǎng)絡(luò)中運(yùn)行BFT算法的效率.

3.2 求解算法

算法1. DGA算法.

輸入: 數(shù)據(jù)層網(wǎng)絡(luò)拓?fù)銰、控制器數(shù)量n、BFT容錯上限f；

輸出: 較好適應(yīng)度子代的基因序列x.

①x=[y1,y2,…,ym],P(t)={x1,x2,…,xp}；

② 初始化P(0);*初始化種群*

③ fort=0 toKdo

④ fori=0 topdo

⑤F(i)=T(G,n,f,xi)；*評估個體適應(yīng)度*

⑥ end for

⑦ fori=0 topdo*種群選擇*

⑨ end for

⑩ fori=0 top2 do*種群交叉*

在該DGA算法中，染色體x表示為(y1,y2,…,ym)，與式(5)中控制器的部署位置ψ(i)相對應(yīng).其中，若yi=1，表示交換機(jī)i處部署有控制器，否則，yi=0.因此，染色體x是一個長度為m的01序列.P(t)為種群空間，包含有p個個體，個體的適應(yīng)度F采用OF請求的平均傳輸延遲T來度量(行⑤).然后，根據(jù)適應(yīng)度F，對種群中的個體按照一定的概率，依次進(jìn)行選擇、交叉和變異(行⑦～)，以期獲得適應(yīng)度更好的子代.

對于交叉變異之后的子代種群P3，其中的部分個體可能會出現(xiàn)異常，使得x中yi=1的數(shù)量不等于n(行)，即其所對應(yīng)控制器的總量不等于n.對于子代中異常的個體，采用解碼法對其進(jìn)行糾正，刪除或增加x中yi=1的項(xiàng)(行)，使其總量為n.在對x進(jìn)行修正時，我們以貪心函數(shù)D作為衡量指標(biāo)(行～)，即該交換節(jié)點(diǎn)與其余節(jié)點(diǎn)距離的總和，修改其中對應(yīng)D(i)較小的yi=1項(xiàng)為yi=0，或?qū)?yīng)D(i)較大的yi=0項(xiàng)修改為yi=1.該DGA算法依次對種群進(jìn)行迭代進(jìn)化，直至循環(huán)T次，最后選擇末代種群P(T)中適應(yīng)度最好的個體作為輸出(行).

4 實(shí)驗(yàn)驗(yàn)證與分析

4.1 實(shí)驗(yàn)環(huán)境

4.1.1 仿真實(shí)驗(yàn)

為了驗(yàn)證上述方法的有效性，我們采用C++語言實(shí)現(xiàn)了一個仿真器，來模擬SDN網(wǎng)絡(luò)中多個控制器之間運(yùn)行BFT算法.該仿真器基于Internet2 OS3E網(wǎng)絡(luò)拓?fù)洌琌S3E是一個遍布美國大部分地區(qū)的用于先進(jìn)科學(xué)研究的SDN網(wǎng)絡(luò)[17].如圖4所示，OS3E具有34個節(jié)點(diǎn)和42條鏈路，每個節(jié)點(diǎn)表示1個獨(dú)立的大學(xué)或組織.對于該網(wǎng)絡(luò)中的鏈路距離，我們采用文獻(xiàn)[15]中的測試數(shù)據(jù)，如圖4中節(jié)點(diǎn)A(Sunnyvale)和B(Los Angeles)間的鏈路距離為503 182 m.

Fig. 4 The topology of OS3E network圖4 OS3E的網(wǎng)絡(luò)拓?fù)?/p>

該仿真器中部署n(n≤10)個控制器，控制器之間可以構(gòu)成不同規(guī)模的群視圖，以運(yùn)行不同容錯上限(f=1，2，3)的BFT算法.對于每個控制器，設(shè)定其以概率p發(fā)生錯誤，其中拜占庭錯誤的比例為b，即拜占庭錯誤發(fā)生的概率為b×p.對于交換機(jī)，在采用傳統(tǒng)的主備切換方法控制時，我們認(rèn)為控制層在出現(xiàn)以下2種情況時該交換機(jī)發(fā)生異常：1)正在工作的主控制器出現(xiàn)拜占庭錯誤，由于主備切換機(jī)制無法檢測拜占庭錯誤而發(fā)生異常；2)出現(xiàn)良性錯誤的控制器的數(shù)目達(dá)到n個，由于控制層無法進(jìn)行有效的切換而發(fā)生異常.在采用BFT算法控制時，當(dāng)交換機(jī)群視圖內(nèi)出現(xiàn)錯誤的控制器達(dá)到f+1個，則認(rèn)定該交換機(jī)出現(xiàn)異常.

4.1.2 原型測試系統(tǒng)

另外，為了測試該BFT算法對系統(tǒng)性能的影響，我們基于OpenDayLight[18]開發(fā)了簡單的原型系統(tǒng)，在其東西向接口上實(shí)現(xiàn)控制器之間的協(xié)作.負(fù)責(zé)控制器之間相互協(xié)作的BFT協(xié)議，是基于BFT-SMART[19]開源代碼來實(shí)現(xiàn)的.

測試環(huán)境中包括2臺服務(wù)器，其間通過10 Gb/s鏈路相連，每臺服務(wù)器均配有2顆Intel Xeon E7-8891處理器(10核20線程、3.7 GHz),64 GB的內(nèi)存.服務(wù)器上運(yùn)行Hypervisor，安裝有多個Ubuntu 14.04.1的操作系統(tǒng).其中1臺服務(wù)器運(yùn)行Cbench[20]，用于模擬SDN的數(shù)據(jù)層，向控制層發(fā)送OF消息；另一臺服務(wù)器則同時啟動多個操作系統(tǒng)，每個操作系統(tǒng)上運(yùn)行1個OpenDayLight控制器，且控制器之間能夠運(yùn)行BFT算法.對于Cbench，我們采用固定的配置，模擬的網(wǎng)絡(luò)中具有64個Switch，每個Switch連接有105個Host.

4.2 測試數(shù)據(jù)

4.2.1 BFT算法的可靠性

基于上述測試環(huán)境，我們首先驗(yàn)證BFT算法對SDN網(wǎng)絡(luò)可靠性的影響.在控制器數(shù)目n=10的情況下，對比分析主備切換Custom,BFT容錯上限為f=1,f=2,f=3這4種方法的容錯效果，均以SDN網(wǎng)絡(luò)中異常交換機(jī)的個數(shù)u作為其衡量指標(biāo).為降低隨機(jī)過程帶來的偶然性，每個實(shí)驗(yàn)均重復(fù)1 000次，計(jì)算u的平均值.

如圖5所示，在拜占庭錯誤比例b=70%固定的情況下，測試不同的控制器出錯所對應(yīng)的網(wǎng)絡(luò)可靠性.

Fig. 5 The reliability of SDN under different fault probability圖5 不同錯誤率下SDN網(wǎng)絡(luò)的可靠性

從圖5中可以得出：1)對于這4種方法，其異常交換機(jī)的個數(shù)u均隨著錯誤概率p的增大而增加，即主備切換機(jī)制和BFT算法的可靠性均與控制器的出錯概率有關(guān)；2)對比主備切換機(jī)制和BFT算法，在b=70%的情況下，BFT的容錯能力要優(yōu)于主備切換機(jī)制；3)在不同p值下，容錯上限f越大的BFT算法，其可靠性均越高.

在控制器出錯概率p=0.6固定的情況下，測試不同的拜占庭錯誤比例b所對應(yīng)的網(wǎng)絡(luò)可靠性，結(jié)果如圖6所示:

Fig. 6 The reliability of SDN under different Byzantine-fault percentage圖6 不同拜占庭錯誤比例下SDN網(wǎng)絡(luò)的可靠性

分析其中的數(shù)據(jù)，可以得出：1)BFT算法能夠有效應(yīng)對拜占庭錯誤，其可靠性與拜占庭錯誤的比例無關(guān)；2)主備切換機(jī)制的可靠性隨著拜占庭錯誤比例的增大而降低，在b值較大時，其容錯能力大幅度降低；3)在不同的b值下，BFT算法的f值越大，其容錯能力均越高.

綜合上述分析，我們可以發(fā)現(xiàn)，相對于傳統(tǒng)的主備切換機(jī)制，BFT算法不僅能夠應(yīng)對SDN網(wǎng)絡(luò)中的良性錯誤，而且也能能夠處理主備切換機(jī)制難以解決的拜占庭錯誤.同時，隨著部署控制器數(shù)量的增加，BFT算法可以選擇更大的f值，網(wǎng)絡(luò)的可靠性將會進(jìn)一步地提高.

4.2.2 BFT算法的性能

基于4.1.2節(jié)中所述的原型系統(tǒng)，對BFT算法的性能進(jìn)行測試，測試指標(biāo)包括處理OF請求的吞吐量和平均延遲.我們對比分析主備切換Custom,以及BFT容錯上限為f=1，f=2，f=3這4種方法下控制器的性能，同樣每種方法均重復(fù)實(shí)驗(yàn)10次，每次實(shí)驗(yàn)運(yùn)行60 s，以O(shè)F消息包為統(tǒng)計(jì)單位，計(jì)算控制層的吐吞量(throughput)和處理延遲(latency)的平均值.

Fig. 7 The performance of BFT圖7 BFT算法的性能

從圖7的測試結(jié)果中可以看出，在采用BFT算法時，控制器處理OF請求的吞吐量有所下降，與傳統(tǒng)的主備切換方法相比，吞吐量最大降低24.07%(當(dāng)f=3時)，且不同f下BFT算法的吞吐量相差在16.13%以內(nèi).另一方面，采用BFT算法時，控制器處理OF請求的平均延遲增加比較明顯，是傳統(tǒng)主備切換方法的2倍多，但不同f下BFT算法的平均延遲差別較小，在6.25%以內(nèi).這是由于控制器處理OF請求所需的計(jì)算和存儲資源相對較少，系統(tǒng)中即使加入了BFT算法中的其余任務(wù)，在處理并發(fā)的OF請求時，吞吐量降低的相對較小.然而，對于處理一個OF請求，由于BFT算法的繁雜交互，使得其處理延時明顯增加.另外，由于BFT算法中控制器數(shù)目的增加并未影響OF請求的處理流程，這也使得在改變f時平均處理延遲的變化較小.

4.2.3 DGA算法的有效性

為了測試DGA算法的有效性，我們將其與最優(yōu)部署(OP)、隨機(jī)部署(RD)進(jìn)行比較，計(jì)算不同部署方法下控制器傳輸OF請求的平均延遲.對于OP，該仿真器采用窮舉的方法搜索最優(yōu)解，因此，為了使其運(yùn)行的時間可接受，CDB問題的規(guī)模選擇在n≤7的范圍內(nèi).同時，我們假定信號在鏈路中的傳輸速度v=3×108m/s.

仿真結(jié)果如圖8所示，我們可以發(fā)現(xiàn)，采用DGA算法來部署控制器，其傳輸OF的平均延遲時間T，與采用OP方法的最優(yōu)值較為接近(差距在86%以內(nèi))，均維持在100 ms以內(nèi)，遠(yuǎn)優(yōu)于RD方法的解(與最優(yōu)值相差近350%).因此，在多項(xiàng)式時間內(nèi)求解CDB問題，該DGA算法具有較好的效果.

Fig. 8 The average transmission delay time under different algorithms圖8 不同算法下的平均傳輸延遲時間T

5 總結(jié)和未來工作

本文針對SDN網(wǎng)絡(luò)中的可靠性問題，首先介紹和分析了該領(lǐng)域的相關(guān)工作和研究.然后，提出了在SDN中應(yīng)用BFT算法來增強(qiáng)可靠性的方法，并具體闡述了其網(wǎng)絡(luò)結(jié)構(gòu)、工作流程和異常處理等.再次，針對在SDN網(wǎng)絡(luò)中應(yīng)用BFT算法時存在的多控制器部署問題，給出了求解其近似最優(yōu)解的啟發(fā)式算法.最后，將該BFT算法與傳統(tǒng)的主備切換方法進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明，BFT能夠有效提高SDN網(wǎng)絡(luò)的可靠性，但對系統(tǒng)的性能會造成一定程度的影響.在未來的工作中，我們期望能夠針對該原型系統(tǒng)做進(jìn)一步的優(yōu)化，調(diào)整交互模塊與控制器的架構(gòu)，并引入并行處理機(jī)制，以減少對系統(tǒng)性能的影響.

[1]Diego K, Fernando M V, Paulo V. Towards secure and dependable software-defined networks[C] //Proc of the 3rd Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 55-60

[2]Banerjee S, Kannan K. Tag-in-tag: Efficient flow table management in SDN switches[C] //Proc of the 10th Network and Service Management (CNSM). Piscataway, NJ: IEEE, 2014: 109-117

[3]Al-Shaer E, Al-Haj S. FlowChecker: Configuration analysis and verification of federated OpenFlow infrastructures[C] //Proc of the 3rd ACM Workshop on Assurable and Usable Security Configuration. New York: ACM, 2010: 37-44

[4]Open Network Foundation. OpenFlow Switch Specification Version 1.2[S]. Reston, VA: The Internet Engineering Task Force, 2011

[5]Castro M, Liskov B. Practical Byzantine fault tolerance and proactive recovery[J]. ACM Trans on Computer Systems, 2002, 20(4): 398-461

[6]Correia M, Costa P, Pasin M, et al. On the feasibility of Byzantine fault-tolerance mapreduce in clouds-of-clouds[C] //Proc of the 31st Reliable Distributed Systems. Piscataway, NJ: IEEE, 2012: 448-453

[7]Casado M, Koponen T, Ramanathan R, et al. Virtualizing the network forwarding plane[C] //Proc of the ACM Workshop on Programmable Routers for Extensible Services of Tomorrow. New York: ACM, 2010: 8-17

[8]Shin S, Porras P A, Yegneswaran V, et al. FRESCO: Modular composable security services for software-defined networks[C] //Proc of the ISOC Network and Distributed System Security Symp. New York: ACM, 2013

[9]Hu Yannan, Wang Wendong, Gong Xiangyang, et al. Control traffic protection in software-defined networks[C] //Proc of Global Communications Conf. Piscataway, NJ: IEEE, 2014: 1878-1883

[10]Jagadeesan N A, Pal R, Nadikuditi K, et al. A secure computation framework for SDNs[C] //Proc of the 3rd Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2014: 209-210

[11]Hu Hongxin, Han W, Ahn G, et al. FLOWGUARD: Building robust firewalls for software-defined networks[C] //Proc of the 3rd Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2014: 97-102

[12]Li He, Li Peng, Guo Song, et al. Byzantine-resilient secure software-defined networks with multiple controllers in cloud[J]. IEEE Trans on Cloud Computing, 2014, 2(4): 436-447

[13]Wang Yongjian, Pei Xiang, Li Tao, et al. Nova-BFT: A replicated state machine protocol supporting multiple fault models[J]. Journal of Computer Research and Development, 2011, 48(7): 1134-1145 (in Chinese)(王永劍, 裴翔, 李濤, 等. Nova-BFT: 一種支持多種故障模型的副本狀態(tài)機(jī)協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(7): 1134-1145)

[14]Yung M. The mobile adversary paradigm in distributed computation and systems[C] //Proc of the 2015 ACM Symp on Principles of Distributed Computing. New York: ACM, 2015: 171-172

[15]Hock D, Hartmann M, Gebert S, et al. Pareto-optimal resilient controller placement in SDN-based core networks[C] //Proc of the 25th Teletraffic Congress. Piscataway, NJ: IEEE, 2013: 1-9

[16]Hu Yannan, Wang Wendong, Gong Xiangyang, et al. On reliability-optimized controller placement for software-defined networks[J]. China Communications, 2014, 11(2): 38-54

[17]Internet2 Open Science. Scholarship and services exchange[OL]. [2015-12-10]. http://www.internet2.edu/network/ose

[18]Medved J, Varga R, Tkacik A, et al. Opendaylight: Towards a model-Driven SDN controller architecture[C] //Proc of the 2014 IEEE Int Symp on Network. Piscataway, NJ: IEEE, 2014: 1-6

[19]Bessani A, Sousa J, Alchieri E. State machine replication for the masses with BFT-SMaRt[C] //Proc of 2014 Annual IEEE/IFIP Int Conf on Dependable Systems and Networks. Piscataway, NJ: IEEE, 2014: 355-362

[20]Sherwood R, Yap K. Cbench controller benchmarker[J]. Control Engineering Practice, 2011, 19(11): 1253-1265

Research on Improving the Control Plane’s Reliability in SDN Based on Byzantine Fault-Tolerance

Li Junfei, Hu Yuxiang, and Wu Jiangxing

(National Digital Switching System Engineering & Technological R&D Center, Zhengzhou 450002)

Software defined network (SDN) proposes the architecture of separating the control logic and forwarding devices in networks, which brings the open API for freely programing and makes the network management more fine. However, while the centralized control of SDN brings innovation and convenience for network applications, it also brings other problems, for example the reliability problem and the scalability problem simultaneously. For the problem of control plane’s reliability in SDN, the method that voting deals with the same OpenFlow messages by combing multiple controllers to a quorum view is proposed to tolerate Byzantine faults, which is different from the current OpenFlow protocol. Firstly, we concretely explain the network structure, workflow and exception handling in the application of Byzantine fault-tolerance algorithm with the feature of SDN, and establish the analytical model of multi-controller’s deployment. Secondly, we design a heuristic algorithm to solve the problem of multi-controller’s deployment. Finally, to verify the fault tolerance method and deploy algorithms by simulation, experimental results show that this method can effectively deal with controllers’ faults, improving the reliability of the control layer, but it will sacrifice the system’s performance at some level. Meanwhile, the deployment algorithm can effectively reduce the transmission delay of processing OpenFlow request.

software defined network (SDN); OpenFlow; Byzantine fault tolerance; reliability; controllers’ deployment

Li Junfei, born in 1989. PhD candidate. His main research interests include SDN and network security.

Hu Yuxiang, born in 1982. PhD and associate professor. His main research interests include the next generation information network.

Wu Jiangxing, born in 1953. Professor and PhD supervisor. His main research interests include network architecture and security.

2016-01-26；

2016-08-17

國家自然科學(xué)基金項(xiàng)目(61521003) This work was supported by the National Natural Science Foundation of China (61521003).

TP393