一種軟件定義網絡（SDN）的拜占庭容差控制器*

蔡圣龍

0 引 言

經過50多年的發展，互聯網已成為當今社會基礎而重要的信息設施，并深深影響著經濟、文化、軍事等各個領域，遠遠超出當初單純的軍事、教育科研應用的目的。但是，因為當初采用的TCP/IP架構體系和盡力而為、無QoS保證的交付方式，和今天用戶和業務的超大規模增長、接入的異構性以及物聯網、社會網絡等新應用模式的出現，使得互聯網在可擴展性、安全性、服務質量、能耗等方面，越來越不能滿足全球網絡規模的急劇擴張。

全球網絡規模的急劇擴張直接影響國際產業的變革。事實上，不管是美國的《先進制造伙伴計劃》、德國的《工業4.0》，還是我國的《中國制造2050》，都是以制造業為核心，應用包括物聯網在內的信息網絡技術，以實現信息空間和物理空間的高度融合。所以，加快信息化發展，構建未來網絡，已成為全球共識。而軟件定義網絡（Software-defined Network，SDN）已是未來組網技術的研究熱點[1]，得到了越來越多的關注。

軟件定義網絡是一種新型的網絡結構，其設計理念是將網絡的控制平面和數據平面分離，實現數據轉發和控制決策的去耦，并實現可編程控制。這種分離和去耦最吸引人的地方在于，高層的路由和流量工程管理更靈活、高效，接入控制更快捷、可靠，且降低了終端成本，同時網管無需在路由器和交換設備上將底層的控制策略翻譯成各種配置指令。但是，從目前普遍認同的SDN體系看，以上優勢都依賴SDN控制器。一旦控制器出現故障，將導致網絡崩潰，這也是軟件定義網絡反對者最大質疑之處[2]。為此，本文將設計一種拜占庭容差控制器，以解決SDN控制器的單點故障問題。

1 軟件定義網絡SDN體系

隨著OpenFlow協議的出現[3]，特別是McKeown教授在2008年Sigcomm會議上展示的OpenFlow實驗網[4]，SDN體系逐漸明晰。2011年，德國電信、Google、Microsoft、Facebook、Verizon等幾家企業聯合成立了ONF（Open Networking Foundation）組織[5]，旨在通過產業聯盟的方式推動以OpenFlow協議為代表的SDN技術的發展。圖1為基于OpenFolw的SDN架構。

圖1 基于OpenFlow的SDN架構

圖1 中，每個數據轉發平面都相當于一個站點，并運行OpenFlow控制器（OpenFlow Controller，NCA）和網絡控制應用（Network Control Application，NCA）。全局控制平面由邏輯上集中的應用（如SDN網關、全局流量工程服務器等）組成，并通過各站點的NCA集中控制整個網絡。

OpenFlow控制器上部署著流量工程代理（Traffic Engineering Agent，TEA）程序。每臺OpenFlow交換機的鏈路狀態信息通過TEA發送給SDN網關；SDN網關匯總后，再發送給流量工程服務器。而流量工程服務器把每條流映射到IP-IP隧道中，并把分配的帶寬通過SDN網關發送給OpenFlow控制器，再由OpenFlow控制器安裝到OpenFlow交換機的轉發表中，從而實現網絡流量的路徑規劃。

此外，根據Google提供的資料[6]，采用SDN技術后，流量工程完全依靠SDN/OpenFlow實現，大幅提升了網絡資源利用率，平均帶寬使用率可達95%。

可見，SDN將控制平面從網絡交換機和路由器中的數據平面分離出來，使SDN控制器實現網絡拓撲的收集、路由的計算、流表的生成及下發、網絡的管理與控制等功能，而網絡層設備僅負責流量的轉發及策略的執行。轉發與控制分離帶來了控制邏輯集中。SDN控制器擁有網絡的全局靜態拓撲、全網的動態轉發表信息、全網絡的資源利用率、故障狀態等，從而也開放了網絡能力。通過集中的SDN控制器實現網絡資源的統一管理、整合以及虛擬化后，采用規范化的北向接口為上層應用提供按需的網絡資源及服務，實現網絡能力開放、按需提供。

與傳統TCP/TP體系相比，SDN體系具有如下特征。第一，控制與轉發分離。轉發平面由受控轉發的設備組成，轉發方式和業務邏輯由運行在分離出去的控制面上的控制應用控制。第二，控制平面與轉發平面之間具有開放接口。SDN為控制平面提供開放可編程接口。通過這種方式，控制應用只需要關注自身邏輯，而不需要關注底層更多的實現細節。第三，邏輯上的集中控制。邏輯上集中的控制平面可以控制多個轉發面設備，即控制整個物理網絡，因而可以獲得全局的網絡狀態視圖，并根據全局網絡狀態視圖實現對網絡的優化控制。

2 拜占庭容錯控制器

2.1 拜占庭將軍問題

SDN技術性能優勢都依賴控制器，一旦數據轉發平面與控制平面間消息傳遞不可靠，將有可能導致網絡崩潰。因此，需要考慮控制器對數據轉發平面和控制面的容差問題，而這類問題往往可用拜占庭將軍問題（Byzantine General Problems）描述[7-10]。

拜占庭將軍問題，是可信計算中的容錯原理。該原理以數據備份作為基礎實現系統容錯，使得系統在一個或多個系統部件工作異常的情況下仍然能夠正常工作。對于SDN體系，當控制平面收到各個數據轉發平面節點不一致指令時，一種可能性是給系統另外增加一個仲裁的節點，且該節點有最高的決定權。如果仲裁的節點失效，整個系統就失效。控制平面與數據轉發平面間的信息交互式一致問題，可通過多次簡單的重復拜占庭將軍問題來解決，使得每個數據轉發平面的值都達成一致。

按照Lamport對拜占庭將軍問題求解的結果，為了容忍f個錯誤的復制品，復制品集合的大小n≥3f+1。一旦錯誤復制品的數量超過了錯誤容忍的門限值f，系統將不能再正常工作。

2.2 控制器設計

按照Lamport對拜占庭將軍問題求解的結果，本文擬采用狀態機復制技術[10]，設計一種SDN的拜占庭容錯控制器。

拜占庭容錯的關鍵在于對復制消息的共識，而基于OpenFlow的拜占庭共識機制如圖2所示。

圖2 基于OpenFlow的拜占庭共識機制

圖2 中，達成拜占庭共識需要包括如下步驟：

（1）REQUEST：通過多播方式，客戶端向每個復制站點發出申請；

（2）PRE-PREPARE：一旦主站點收到客服端請求，便分配一個序列號給主站點，并將PREPREPARE消息傳遞給其他復制站點；

（3）PREPARE：一旦第i個復制站點收到RE-PREPARE消息，它便把PREPARE消息傳遞給其他復制站點，并將RE-PREPARE和PREPARE消息添加到日志中。一旦第i個復制站點發出了PREPARE消息，它將等到來自其他復制站點規定的2f個PREPARE消息，而這些消息將用于創建法定證書；

（4）COMMIT：一旦所有站點（包括主站點）均收到規定的PREPARE消息，便向其他站點發送COMMIT消息，確保申請階段消息復制的一致性。復制站點一直收集COMMIT消息，直到達到規定的2f+1個COMMIT消息；

（5）REPLY：一旦申請得到一個復制站點應答，便對客戶端發回響應，而客戶端需要在等待f+1個一樣的申請后，才能視其為正確的行為。

根據以上機制，可設計一種拜占庭容錯控制器的通信流模型，如圖3所示。圖3中，控制器將交換機和業務代理看成實體作為客戶端。

圖3 拜占庭容錯控制器的通信流模型

3 結 語

作為未來網絡的主要技術，軟件定義網絡具有高效、靈活的特點，其采用數據轉發平面與控制平面分離的機理，可以適應今后大數據業務的發展。但可以看到，控制器單點故障等問題依然是SDN技術成熟需要面對的。基于此，本文利用拜占庭容錯技術，通過分析拜占庭共識機制，基于OpenFlow協議設計了一種拜占庭容錯控制器，下一步將開展相關實驗，以進一步驗證設計的有效性。

[1] 張朝昆,崔勇,吳建平.軟件定義網絡（SDN）研究進展[J].軟件學報,2015(01):62-81.ZHANG Chao-kun,CUI Yong,WU Jian-ping.Research Progress on Software Defined Networking(SDN)[J].Journal of Software,2015(01):62-81.

[2] Gergely P,Laszlo M,Zolt′ an Lajos ′Kis.Removing Roadblocks from SDN:Openflow Software Switch Performance on Intel DPDK[C].In Software Defined Networks(EWSDN),2013:62-67.

[3] 黃韜,劉江,劉韻潔.軟件定義網絡核心原理與應用實踐[J].通信學報,2015(03):95.HUANG Tao,LIU Jiang,LIU Yun-jie.Software Definition Network Core Principle and Application Practice[J].Journal of Communication,2015(03):95.

[4] Mckeown N,Anderson T,Balakrishnan H,et al.OpenFlow:Enabling Innovation in Campus Networks[C].Acm Sigcomm Computer Communication Review,2008(38):69-74.

[5] 王蒙蒙,劉建偉,陳杰.軟件定義網絡:安全模型、機制及研究進展[J].軟件學報,2016(04):969-992.WANG Meng-meng,LIU Jian-wei,CHEN Jie.Software Definition Network:Security Model,Mechanism and Research Progress[J].Journal of Software,2016(04):969-992.

[6] Jain S,Kumar A,Mandal S,et al.WAN[C].Acm Sigcomm,2013,43(04):3-14.

[7] 楊磊,黃浩,李仁發等.P2P存儲系統拜占庭容錯機制研究[J].計算機應用研究,2009(01):4-8.YANG Lei,HUANG Hao,LI Ren-fa,et al.Study on Byzantine Tolerance Mechanism of P2P Storage System[J].Computer Application Research,2009(01):4-8.

[8] 陳柳,周偉.面向服務計算的拜占庭容錯方案及其正確性證明[J].計算機應用,2006(02):505-510.CHEN Liu,ZHOU Wei.The Byzantine Fault-tolerant Scheme for Service-oriented Computing and Its Correctness[J].Computer Application,2006(02):505-510.

[9] 肖愛斌,楊孟飛,劉波.星載計算機拜占庭容錯設計與證[J].空間控制技術與應用,2008(08):17-22.XIAO Ai-bin,YANG Meng-fei,LIU Bo.Design and Verification of Byzantine Fault-tolerant Design[J].Space Control Technology and Application,2008(08):17-22.

[10] 陳柳,周偉.拜占庭容錯中的視圖變更算法[J].計算機與現代化,2013(10):13-15.CHEN Liu,ZHOU Wei.View Change Algorithm in Byzantine Fault Tolerance[J].Computer and Modernization,2013(10):13-15.