技術探索

軟體定義網路之多域控制器協議機制

2015-08-28

中文摘要

　　在多網域的軟體定義網路（SDN）環境中，每一個控制器皆需要經常地做訊息交換的動作，而在現實環境中，網路中可能存在著一些錯誤的元件而導致正常的控制器無法獲得正確的訊息進而發生系統錯誤。因此，為了改為上述的問題，本論文提出了一個較健全的控制器協議機制。透過協議機制的運作，可讓系統中所有正常的控制器可以有效地獲得一個共同的分數值，進而透過此值來維持系統的正常運作。除此之外， 允許網路中之故障控制器數量上限為(n -1)/3的條件下，此n個控制器的系統可利用O(n2) 的時間複雜度及使用O(n2)的空間複雜度即可得到上述的正確共同分數值。

Abstract

　　In multi-domain SDN environments, the controllers need to exchange information frequently.In real situation, there may have some faulty controllers. Besides, the connection between controllers may be disturbed. All this faulty components may cause that fault -free controllers getting the wrong information, and the network cannot work well. Hence, in this paper, a robust controllers’ negotiation mechanism has been proposed. Based on the mechanism, all fault -free controllers can efficiently and robustly to get a common score about the information which are needed to b e shared by at most three rounds of score exchange phases. Moreover, when there are at most (n-1)/3 allowable faulty controllers, the time complexity and the space complexity of generating the correct score are O( n2) and O(n2) respectively, where n presents the number of total controllers.

關鍵詞(Key Words)

軟體定義網路 (Software-Defined Network；SDN)
異質軟體定義網路多域控制器( Multi-domain SDN-based controller)
控制器協議設計 (Controller Negotiation Scheme)

1. 前言

　　近年來，由史丹佛大學所提出的軟體定義網路（Software-Defined Networking；SDN）概念啟發了許多研究學者重新思考目前網路的管理與設計方式。在軟體定義網路中定義了三個層級的架構，分別為： 應用層、控制層及基本建設層，其整體架構如圖１ 所示。在此架構中，將控制面和資料面各自區隔至控制層和基本建設層。除此之外，新的網路服務可獨自由應用層取得而不受另外兩層的約束。目前較受歡迎的南向應用程式介面是由Open Networking Foundation (ONF) 所提出之OpenFlow協定[1]。在此架構中，控制器和Openflow 的交換器彼此之間是透過OpenFlow協定來進行溝通。截至目前為止，應用方面使用了RESTFul 的應用程式介面來與控制器進行溝通，然而RESTFul 應用程式介面對於軟體定義網路的南向介面而言仍不是一個標準協定。至今， 仍未有公認的北向應用程式介面，但ONF卻有一個北向工作群組致力於開發一個共同的北向框架和機制，而非定義所有通用的北向應用程式介面。

圖 1 軟體定義網路架構圖 1 軟體定義網路架構

　　軟體定義網路架構為一個新的網路演進，其透過了在網域裡經由中央控制器來管理網路系統的概念，使應用和網路設備方面之設計及使用皆可獨立運作。目前此研究主題不但為教育學者[3]爭相研究之主題，其亦獲得業界之青睞。根據SDN Market Sizing Report [4]表示，Venture Capital (VC)基金會於2009年花費少於千萬美金於建構公司內之軟體定義網路，但其所帶來的軟體定義網路市場則於2013年增加至5億美金，獲利能力為成本之50倍。除此之外，根據報告指出，整體軟體定義網路的收益，將於2018年提升至350億美金，可知此架構的重要性。

　　軟體定義網路環境的開發正引起越來越多研究者的興趣與關注，目前大部分的研究仍著重於單一控制器之軟體定義網路架構，然而，在此架構下將發生一些問題，如規模和效能議題，除此之外，當此單一控制器發生問題時，稱此類控制器為故障控制器， 則系統將無法正常運作，因此多域控制器軟體定義網路架構將成為軟體定義網路架構之新趨勢。多域控制器之間之對話及協議，將可提供比單一控制器網路更多的整體視圖。在多域控制器架構中，控器制之間的對話代表著訊息、協議的溝通和資訊的改變，在某些狀況下，控制器之間必須共同做出一些決策，因此，在多控制器的軟體定義網路環境下建構一個更健全、有效的協議模式將成為本篇論文的重點。

　　本篇論文的第二章節將介紹過去關於多域控制器軟體定義網路環境的相關成果。健全、有效的對話及協議模式相關演算法將於第三章說明。而於論文最後將介紹相關結論。

2. 文獻探討

　　相較於傳統的交換器功能，網路作業系統(network operation system；NOS)的管理功能皆從交換器抽離而成為一個集中管理的模式，而管理者則稱為控制器（Controller）。在此模式中，所有的管理活動，如網路拓撲發掘、繞徑策略、流量管理等等皆由集中的控制器所管理。當一個新的流量流向新的網域位置時，軟體定義網路架構下的相關流量資訊將透過傳送packet-in message的方式詢問控制器該未知流量的相關資訊，此時，控制器將記錄繞徑資訊至流量表格（flow table），包含來源、目的端的MAC位置、IP和PORT資訊，緊接著，控制器將根據流量表格以指定交換器來負責轉傳資訊。

　　在進階的集中式管理架構中，一個網域中存在一個控制器，此控制器必須控制所有的交換器、流量和網路狀態。然而，在軟體定義網路架構環境中， 每一個控制器必須控制多少個交換器，而其效能又為何等議題是一個重要且有趣的議題[5]。隨著網路技術的演進，軟體定義網路的概念勢必被運用至校園網路、企業網路甚至是更廣範的網路環境中，因此， 多個控制器的架構在管理上將更加的複雜。基於前述理由，目前亦有許多多域控制器軟體定義網路架構相關的研究紛紛被提出。在2010年時，Yu,Minlan 等學者提出了一個使用DIFANE 技術[6]，並以流量為依據的可擴展網路，在DIFANE架構中，控制器將賦予一些授權規則給相關之交換器，而未被授權的控制器則僅需處理一些資料面的封包。換句話說，被授權之交換器仍然與控制器分享一些責任，以協助增加其擴展性。不同於設計被用來協助控制器的授權交換器來說Onix架構[7]則為一個分散式的控制平台，其為Google、NEC、Nicira Networks和UC Berkeley所共同發表之平台。在Onix架構中，控制面被視為一個分散式系統，一個Onix物件使用了Network Information Base(NIB)來挑述一個網路拓撲環境架構圖，此架構圖包含了相關網域中的所有網路的成員。SH Yegane等學者於2012年提出了兩階層的軟體定義網路控制器架構， 此架構名為Kandoo[8]。在此架構中，每一個區域性的控制器負責處理其子網域下可用的交換器，而最頂層之控制器則負責控制所有區域性之控制器，因此，軟體定義網路的網路架構更具擴展性。2013年Google提出了一個全網路架構軟體的廣域網路，稱為B4 [9]，此架構建構於其自身之資料中心環境下。在B4架構下，每一個平台皆代表一個資料中心，在每一個平台中，皆包含了一個甚至是多個的控制器，而每個控制器使用了Paxos [10]技術來推舉出一個控制器代表負責管理平台中的交換器。在B4架構外還包含了一個邏輯性的集中式TE伺服器和一個軟體定義網路的閘道， 則主要是被用來週期性的收集所有網路平台控制器的交通資訊， 緊接著即可做出一些與交通流量管理工作相關之決策。其他與多域控制器軟體定義網路相關的研究成則可參考其它論文[11] [12] [13]。

　　針對軟體定義網路雖有許多不錯的成果，但是目前仍存在許多未解的問題。過去大部分的研究討論了分散式控制面的架構，但其仍共享由同一個操作者或是同質服務提供者所提供之儲存體如記憶體或分散式資料庫[7] [9][13]。除此之外， 在階層式控制器架構中，最頂層之控制器可能會發生元件損壞的狀況，其亦有相當大的工作負載量，如何在多域控制器軟體定義網路下提升系統的正確性及效能即成為一個相當重要的關鍵問題。

在本篇論文中， 我們提出了一個多域控制器軟體定義網路下之健全且有效的協議模式，論文的主要貢獻包括：

  1. 在多域控制器網域下提出一個可提升系統效能及正確性之健全協議演算法。
  2. 可允許網路中之故障控制器數量上限為，而時間和空間複雜度皆為O(n2)
  3. 所需要之分數訊息交換回合數為回合。
  4. 論文所提出之模式可讓每一個控制器皆能記錄網路拓撲狀況，可減少空間複雜度。

3. 協議模式

在此章節中，我們將介紹完整的控制器間協議模式的細節。

3.1 控制器的網路拓撲型態

　　在傳統的網路環境中已存在著許多成熟的協定， 如Link Layer Topology Discovery(LLDP) [15] [16]和Border Gateway Protocol(BGP) [17][18]，以支援網路元素亦或是獨立系統做為確認網路拓撲型態之依據。在多域控制器的軟體定義網路下則可利用控制器間的簡單的數字分數(score)交換做為依據，而這些分數訊息包括了：Hello、 Update、 Error和Bye等。基本上，每一個分數訊息之函意如下:

  • Hello： 控制器將使用Hello分數訊息來告知其鄰近的控制器其仍然正常運作中。
  • Update：控制器透過此訊息做為更新網域狀態資訊之依據。
  • Error：當網路發生非預期之事件時，則透過Error訊息告知鄰近之控制器。
  • Bye：透過Bye訊息告知其他控制器其本身將離開此網路架構。

　　在B4 [9]架構中，在不同位置的控制器使用內部BGP (internal BGP； iBGP) 來進行對話，並使用外部BGP (external BGP；eBGP)來收集交換器的繞徑資訊和狀態。除此之外，Wun-Yuan Huang [14]等學者設計並開發了一個使用延伸LLDP 的網路拓撲環境開發系統。目前現有的環路撲型態演算法皆能有效處理多控制器軟體定義網路之狀況， 因此，在此論文中將不細部探討網路拓撲發掘方法。在38 ICT Journal No.161此，論文將假設在網路中之所有控制器，對於網路中之成員皆有一定之認知。

3.2 控制器的對話方式

　　在控制器之間，那一些訊息應該溝通或交換一直是一個被持續研究的議題。在我們的觀點裡，控制器之間的對話內容是由應用服務來決定的。就一個以服務導向之應用服務來說，維持可用的頻寬、較少的延遲或是較少的封包遺失則為決定的關鍵。另又舉一個線上會議為例，為了確保連線品質， 控制器之間的頻寬則被視為第一優先被保證的關鍵元素。簡而言之，不同的應用則控制器之間則存在著不同的對話參數，一個應用服務亦可能需要多個參數保證，因此，在本篇論文中，我們將需要溝通或交換之訊息轉換之一個分數值，並做為控制器協議之值，並依據協議模式的執行， 即可確保控制器之間可以正常運作，並維持網路系統的正確性及健全性。

3.3 控制器的協議演算法

　　在現實的環境中，系統中或許存在著一些發生錯誤的控制器，亦或是控制器之間的網路連線發生干擾或錯誤。上述的問題皆會影響著控制器間協議結果的正確性而導致系統無法正常運作。為了提升系統的正確性及有效能，本論文提出了一個較健全的控制器間協議的機制。在整體協議過程中，一共包含了兩個階段：分數交換階段和決策階段。在分數訊息交換階段中，每一個控制器將透過廣播的方式來傳遞並接收分數訊息，並將所收到的訊息儲存於每一個控制器的資料結構中，我們稱此結構為s-tree，而所需要的分數訊息交換的回合數為３ 回合。在結束了分數訊息的交換後， 緊接著每個控制器將執行決策階段，在此階段中共有三個子工作，分別為：

  1. 尋找可靠的控制器。
  2. 套用「取代程序」以更新由非可靠的控制器那所接收之分數訊息。
  3. 套用「VOTE」函式，以決定最終的分數值。

　　完成了決策階段的工作後，系統可確保每一個正常運作的控制器， 皆能獲得一個共同的分數值的狀況下正常運作，而不受故障控制器的干擾。詳細的演算法如圖２所示

圖 ２ 協議模式之演算法圖 ２ 協議模式之演算法

4. 正確性證明

4.1 多域控制器協議演算法的正確性

　　多個正常控制器間的資訊交換應該避免被故障控制器所送出的錯誤資訊所影響。在本論文協議機制中的決策階段即可將故障控制器所產生之影響移除，因此在正常控制器之間的協議即可正確達成。下列的lemmas, corollaries及theorems將證明此協議機制之正確性。因篇幅限制的緣故，詳細的證明過程請詳見[20]。

Lemma 1:

在s-tree中所有正確的節點是一致的。
Lemma 2: s-tree存在著一致的frontier。
Lemma 3:

令 α 代表一個節點。假設sub-tree的頂層節點有一致的frontier，則表示 α 是一致的。假設存在一個共用的
  frontier於以 α 為root的subtree中，則此 α 為共用的節點。
Lemma 4: 演算法可獲得可靠控制器。
Lemma 5:

被可靠控制器的多數值所取代的分數值訊息是一致的。
Corollary1:

假設一致性的frontier確實存在於s-tree中，則此s-tree的root之值是一致的。
Theorem1:

所有正常的控制器能決定出一致的可靠控制器的群組成員。
Theorem2:

任一個正常控制器的s-tree 的root 是一致的。
Theorem3: 所有的控制器皆可得到同一個協議後的分數值。

4.2 多域控制器協議演算法的複雜度

　　有關於本文協議機制的時間複雜度與空間複雜度正確性將根據下列三點進行評估(1)交換分數的回合數;(2)允許故障的控制器數量;(3) 在執行此協議機制下所得分數值的數量。因篇幅限制的緣故，詳細的證明過程請詳見[20]。

Lemma 6:

由多個正常控制器所傳送出來的數值等同於採用VOTE function所得的數值。
Theorem 4:

在具有n個控制器的環境下，所有的控制器僅需三回合的分數訊息交換回合數，且其為最小值。
Theorem 5

在具有n個控制器的環境下，可被允許的故障控制器數量最多為⌊(n-1)/3⌋，即可使用本協議機制取得
  正確協議分數值，且其為最大值。
Theorem 7:

在具有n個控制器的環境下，採用本協議機制可運算在O(n2)時間複雜度下得到正確的協議分數值。
Theorem 8: 在具有n個控制器的環境下，採用本協議機制可利用O(n2)空間複雜度下的儲存空間得到正確的協議分數
  值。

　　就我們所知，本文是第一個探討在多域控制器軟體定義網路中，確保正常運作的控制器皆不受故障控制器影響而達成正確協議。本文所提出的方法可於最多3個交換次數下，即可達到正確協議值，而明顯優於傳統協議問題演算法所需
⌊(n-1/3)⌋+1的交換次數， 其中n為所有控制器的數量。而運算的時間複雜度也如下表1所示，本文所提出的方法可於O(n2)即可達到正確運算值，而傳統協議問題演算法[21] [22] [23] [24][25]則至少需O(n⌊(n-1)/3⌋)的時間複雜度。

表 1 交換次數與時間複雜度比較表表 1 交換次數與時間複雜度比較表

5. 結論

　　為了確保多域控制器軟體定義網路的正確性及有效性，系統必須確保正常運作的控制器皆能不受故障控制器的影響而達成協議並正常合作， 本篇論文旨在讓所有正常運作的控制器皆能透過演算法的執行， 而獲得共同的分數訊息，進而做為決策的共同依據。


　　在本篇論文所提出的協議模式中，所有的控制器僅需三回合的分數訊息交換回合數，並透過決策階段之處理工作後， 即能確保分數訊息的一致性。論文所提出之演算法，其時間、空間複雜度皆為O(n2)，相較過去之協議演算法皆有許多的改善。

參考文獻

  1. (2014) Openflow switch specification(verson 1.4) [Online]. Available:https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specific ations/openflow/openflow-spec-v1.4.0.pdf.
  2. (2013) Open Networking Foundation (ONF)[Online].Available:https://www.opennetworking.org/.
  3. Nick McKeown, T.A., Hari Balakrishnan,Guru Parulkar,Larry Peterson,Jennifer Rexford,Scott Shenker,Jonathan Turner,“OpenFlow: Enabling Innovation in Campus Networks,” ACM SIGCOMM Computer Communication Review, 38(2): pp. 69-74,2008.
  4. (2014) Central, S. SDN Market Sizing Report. 2013/04 [cited 2014/01/05];[Online]. Available:http://www.sdncentral.com/sdn-market-sizing-2013-april.
  5. Brandon Heller, R.S., and Nick McKeown,“The controller placement problem,” in the first workshop on Hot topics in software defined networks(HotSDN '12). 2012. pp.7-12.
  6. Minlan Yu, J.R., Michael J. Freedman,Jia Wang, “Scalable Flow-Based Networking with DIFANE,” ACM SIGCOMM Computer Communication Review, 40(4): pp. 351-362,2010.
  7. Teemu Koponen, M.C., Natasha Gude,Jeremy Stribling, Leon Poutievskiy,Min Zhuy, Rajiv Ramanathany, Yuichiro Iwataz,Hiroaki Inouez, Takayuki Hamaz, Scott Shenker, “Onix: A Distributed Control Platform for Large-scale Production Networks,” in the 9th USENIX conference on Operating systems design and implementation (OSDI'10). 2010.
  8. Soheil Hassas Yeganeh, Y.G., “Kandoo:A Framework for Efficient and Scalable,” in the first workshop on Hot topics in software defined networks(HotSDN '12). 2012. pp.19-24.

  9. Sushant Jain, A.K., Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun
    Singh,Subbaiah Venkata, Jim Wanderer,Junlan Zhou, Min Zhu, Jonathan Zolla,Urs Hölzle, Stephen Stuart and Amin Vahdat,“B4: Experience with a Globally-Deployed Software Defined WAN,” in ACM SIGCOMM 2013 conference on SIGCOMM,(SIGCOMM’13). August 12-16, 2013: Hong Kong, China. pp. 3-14.

  10. Tushar D. Chandra, R.G., and Joshua Redstone, “Paxos Made Live - An
    Engineering Perspective,” in the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing(PODC '07). 2007: New York, NY, USA. pp.398-407.

  11. K´evin Phemius, M.B.a.J.e.e.L., “DISCO:Distributed Multi-domain SDN Controllers,” Network Operations and Management Symposium(NOMS), 2014,pp.1-4..

  12. Ganjali, A.T.a.Y. “HyperFlow: a distributed control plane for OpenFlow,” in the 2010 internet network management conference on Research on enterprise networking (INM/WREN'10). 2010. USENIX Association, Berkeley, CA, USA.

  13. Advait Dixit, F.H., Sarit Mukherjee, T.V.Lakshman, and Ramana Kompella,“Towards an elastic distributed SDN controller,” in the second ACM SIGCOMM workshop on Hot topics in software defined networking (HotSDN '13). 2013: New York,NY, USA. pp. 7-12.

  14. Wun-Yuan Huang, J.-W.H., Shu-Cheng Lin,Te-Lung Liu, Pang-Wei Tsai, Chu-Sing Yang, Fei I. Yeh, Jim Hao Chen, and Joe J.Mambretti, “Design and Implementation of an Automatic Network Topology Discovery System for the Future Internet Across Different Domains,” in the 26th International Conference on Advanced Information Networking and ApplicationsWorkshops (WAINA '12). 2012:Washington, DC, USA. pp. 903-908.

  15. J. Kempf, E. Bellagamba, A. Kern, D.Jocha, A. Takacs, and P. Skoldstrom,“Scalable fault management for OpenFlow, ”2012 IEEE International Conference on Communications (ICC), 2012, pp.6606-6610.
  16. Wei Xiao, Ruixing Wang, and Xiaohong Huang, “Design and implementation of Ethernet topology discovery algorithm, ”2012 IEEE 2nd International Conference on Cloud Computing and Intelligent Systems(CCIS), 2012, pp. 767 -770.
  17. Sapegin, Feng Cheng, and C. Meinel,“Catch the Spike: On the Locality of Individual BGP Update Bursts,” 2013 IEEE Ninth International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2013,pp. 78 – 83.
  18. Jian Mai, and Jiang Du, “BGP performance analysis for large scale VPN,” 2013 International Conference on Information Science and Technology (ICIST), 2013, pp.722-725.
  19. A. Bar-Noy, D. Dolev, C. Dwork, R. Strong,“Shifting Gears: Changing Algorithms onthe Fly to Expedite Byzantine Agreement, ”in Proceedings of the 6th annual ACM Symposium on Principles o Distributed Computing, 1987, pp. 42-51.
  20. Yen-Chiu Chiu Chen and Hui-Ching Hsieh,"A Robust Controllers' Negotiation Model in Multi-Domain SDN Environments", The SIJ Transactions on Computer Networks &Communication Engineering (CNCE), The Standard International Journals (The SIJ),Vol. 3, No. 1, pp. 10-16, 2015..[Online].Available:http://www.thesij.com/papers/CNCE/2015/January/CNCE-03010020201.pdf

  21. L. Lamport, P. Melliar-Smith, “Byzantine Clock Synchronization,” in ACM 3rd PODC
    Conf. Proc., 1984, pp. 10-16.

  22. L. Lamport, R. Shostak, M. Pease, “The Byzantine Generals Problem,” ACM Transactions on Programming Languages and Systems 4(3), pp. 382-401, 1982.

  23. M. L. Chiang, S.C. Wang, L. Y. Tseng, “The Incremental Agreement,” Information Processing Letters 107(5), pp. 165-170,2008.

  24. M. Pease, R. Shostak, L. Lamport,“Reaching Agreement in Presence of Faults,” Journal of ACM 27(2), pp. 228-234,1980.

  25. O. Brukman, S. Dolev, E. K. Kolodner, “Aself-stabilizing autonomic recover for eventual Byzantine software,” The Journalof Systems & Software, 84(12), pp.2315-2327, 2008.

作者簡介

陳昀暄

國立清華大學資訊工程博士，現任於工研院資通所寬頻網路與系統整合技術組網路通訊服務技術部工程師。專長為軟體定義網路設計、即時系統設計、雲端運算、網路應用與服務。 E-mail:amanda.chen@itri.org.tw

謝惠菁

國立清華大學資訊工程博士，現任於醒吾科技大學資訊傳播系助理教授。專長為容錯問題、平行與分散式運算、網路應用與服務。 E-mail:luckyeva.hsieh@gmail.com

回上一頁 友善列印