基于博弈論的SDN主控制器重選機制

樊自甫，周凱恒，姚 杰

(重慶郵電大學 下一代網(wǎng)絡研究所，重慶 400065)

0 引言

軟件定義網(wǎng)絡(Software Defined Network, SDN)[1]是近年來新興的網(wǎng)絡技術(shù)，它將控制平面與轉(zhuǎn)發(fā)平面相分離，控制平面由單獨的主機構(gòu)成的控制器來運行，并且可以控制整個網(wǎng)絡的交換機。該結(jié)構(gòu)使得控制器可以掌握全局網(wǎng)絡視圖，并且還能進一步通過定義南向接口來設(shè)計可編程交換機，但是，在SDN中資源耗盡型事件(例如Packet-In報文)可能導致單一的控制器過載[2]，因此，目前研究提出了分布式控制結(jié)構(gòu)來解決這個問題。分布式控制主要有兩種結(jié)構(gòu)：扁平結(jié)構(gòu)[3]，從水平方向上擴展；垂直結(jié)構(gòu)[4]，從頂層的根控制器到葉控制器。這兩種分布式結(jié)構(gòu)很好地克服了集中式單控制器的缺點；然而網(wǎng)絡的流是突發(fā)并且分布不均勻的，固定的控制器配置很難使控制器適應網(wǎng)絡的復雜狀況。

OpenFlow (OF)[5]協(xié)議在1.3版本中突出每個交換機可以有三種角色：主控制器(Master)、從控制器(Slave)和等價控制器(Equal)。等價控制器與主控制器有相同的權(quán)限，但從控制器只能讀取交換機狀態(tài)，不能控制交換機。控制器的角色是可以根據(jù)網(wǎng)絡狀態(tài)來變化的。通過調(diào)整控制器角色的狀態(tài)，可以實現(xiàn)對網(wǎng)絡的控制，從而達到負載均衡。

Dixit等[6]提出了一種分布式控制器結(jié)構(gòu)“ElastiCon”，這種結(jié)構(gòu)使控制器池里的剩余控制器可以根據(jù)網(wǎng)絡狀態(tài)增加和減少，以此來遷移控制器之間的負載，但是并沒有詳細描述負載狀態(tài)如何評估，以及目的控制器如何選擇。

Bari等[7]同樣突出了一種彈性結(jié)構(gòu)，它可以在不同的網(wǎng)絡狀態(tài)下改變控制器的數(shù)量和位置，并且完成交換機和控制器之間的重部署，但是該方法沒有說明遷移需要考慮的因素。

Cheng等[8]提出了一種基于博弈論的動態(tài)SDN控制架構(gòu)，但是該方案中缺少博弈觸發(fā)機制，沒有在具體實驗中進行驗證。

本文在控制器負載均衡上研究主控制器重選模型，并使用基于博弈論的機制來選擇主控制器。假設(shè)一些高負荷主控制器為了避免過載，一些交換機必須重新選擇主控制器，而另一些低負荷的控制器可能正好想要成為其他交換機的主控制器，因此低負荷區(qū)域就有了主控制器重競選的沖突。本文使用博弈論來解決這種沖突，主要有以下幾個部分:

本文根據(jù)利用度的變化設(shè)計了一種基于博弈論的交換機遷移機制——GAME-SM。通過將交換機遷移過程建模為輕載控制器競爭被遷移交換機的博弈過程，將該資源效用最大化問題等價為博弈參與者的收益最大化問題。最后本文基于Floodlight[9]控制器并用Mininet[10]進行軟件仿真。

1 博弈論模型

1.1 博弈域

一般來說，認為交換機遷移發(fā)生在相鄰控制器之間以節(jié)省通信消耗。通過本地重選主控制器，可以實現(xiàn)交換機的遷移。為了保證控制器的一致性，假定任何控制器同一時間只能參加一場博弈。由此提出了博弈域(Game-playing Field, GF)的概念。同一般的運行域相比，博弈域是一種臨時松散的并有著特殊目標的聯(lián)合體，并且能夠隨時解散。GF模型如圖1所示。

圖1 博弈域系統(tǒng)模型 Fig. 1 Game-playing field system model

如圖1所示，每個交換機都被它們的主控制器所控制，整個系統(tǒng)呈現(xiàn)為分布式結(jié)構(gòu)，不同的主控制器分別控制各自的交換機。當某個控制器過載時，它需要選擇新的控制器來接受它的主控制器角色，同時鄰近的低負載控制器也會競爭主控制器權(quán)，這時就會進行主控制器重選博弈。

GF使并行的網(wǎng)絡博弈可以分離為不同的單獨博弈。它是一個松散的聯(lián)合體，可以隨時被建立和解散，并且不需要額外的代價去維持。實際上，控制器有很多種情況可以觸發(fā)GF。例如當網(wǎng)絡流量分布變化時，此控制器的網(wǎng)絡負載超出了容量，這時應該將幾個交換機遷移到它的鄰居控制器，并使它的負載降低到一個較低的水平。

本文根據(jù)文獻[6]提出的控制器雙門限彈性控制結(jié)構(gòu)，通過設(shè)置控制器負載上下限閾值來觸發(fā)GF。文獻[11]中將上下限閾值分別設(shè)置為控制器負載的90%和20%，因此本文中控制器負載上限設(shè)置為90%，鑒于本文仿真規(guī)模較大，為了方便驗證，于是將控制器負載下限設(shè)置為50%。系統(tǒng)將周期性地獲取每個控制器的負載信息。

1.2 本地博弈模型

在一個網(wǎng)絡G中，假設(shè)控制器c和交換機集合X={S1,S2,…,Sk}作為博弈者并向請求其鄰居參與交換機的交易活動，定義博弈者為C={c1,c2,…,cv}。用M表示包含X和c的交換機的集合，H定義為包含M所有子集的集合(包含空集和M本身)，并給出以下定義:

f=[Sc1,Sc2,…,Scj,…,Scv]是整個網(wǎng)絡G的配置，并有：

Scj∈H，Scj∩Scj′=?,?j≠j′

Scj定義為被cj控制的OF交換機集合。

簡單地重寫一下策略即:f[f1,f2,…,fj,…,fv]，fj∈H表示第j個控制器控制的交換機。F作為所有f的集合。

在本文的博弈場景中，所有博弈者從策略集合H同時選擇一種策略。L=|F|表示每個博弈者的純策略。

在每個博弈時間，任意博弈者j選擇一個策略fj，所有這些不同博弈者的策略構(gòu)成一個本地網(wǎng)絡配置f。因為網(wǎng)絡負載分布是隨時間變化的，所以每個博弈者采取的策略應該是連續(xù)傳輸?shù)模@樣每一個策略占用的都是小部分時間。由此可以寫出博弈中混合策略的均衡解決方法：博弈者j在集合H中隨機選擇一個策略rj={rj,1,rj,2,…,rj,L}，即:

(1)

結(jié)論1 主控制器重選的最優(yōu)解可以通過零和博弈中最大化每個參與者的收益等效解決。

證明 控制器j和其他控制器競爭交換機si，Pij表示對商品i的期望，鞍點平衡滿足下列不等式:

(2)

(3)

(4)

2 應用與實現(xiàn)

2.1 博弈論應用

從博弈論的角度來看，本文分配了博弈者之間主從決策的計算。給定一個有OF交換機和控制器的網(wǎng)絡，任意控制器都可以根據(jù)其控制狀態(tài)來初始建立一個博弈域。

步驟1 假設(shè)有一個控制器c和交換機集合X={S1,S2,…,Sk}初始化了一個請求給它的鄰居控制器C={c1,c2,…,cv}。如果C中的元素是空閑的(即它們沒有參加已有的博弈域)，則它們就會回復加入消息ACK給c。如果C中的元素是繁忙的(即它們參加了其他的博弈域并且沒有多域的資源來給新交換機)，則它們回復丟棄ACK給c。這種博弈域是松散建立的。

步驟2 控制器c選取一個交換機si成為它的重選主控制器，并且廣播它的信息給所有博弈域的控制器。該信息包含了交換機現(xiàn)在的控制事件。

步驟3 當交換機si加入了控制器cj，所有在博弈域的控制器根據(jù)收到的廣播信息計算利用度的改變量Δij。作為博弈者，對交換機si只有兩種選擇〈keep, reject〉。如果Δij>0，那么控制器cj就會發(fā)送“keep”來保留交換機si。

步驟5 在交換機si重新選擇主控制器后，控制器c重新計算它是否還是過載。如果這次主控制器的重選不能消除c的過載，那么將跳回步驟2繼續(xù)運行，否則將發(fā)送結(jié)束信息final來解散博弈域。

重選的流程如圖2所示。

圖2 主控制器重選過程流程 Fig. 2 Flow chart for reselection of master controller

所有控制器之間是互相連接的，這樣每個控制器可以獲得整體網(wǎng)絡的視圖，每個交換機周期性地向它們的主控制器發(fā)送信息。當某個控制器負載過高超載時，將會觸發(fā)博弈活動。過載控制器發(fā)送博弈邀請信息給鄰近控制器，進行主從轉(zhuǎn)換。

2.2 應用的細節(jié)

利用度的改變Δij不只是考慮si加入控制器cj的事件λ(Si)，并且還要考慮選取cj作為si的主控制器后帶來的網(wǎng)絡消耗。這里使用遷移交換機和主控制器的距離——路由跳數(shù)μij和決策與遷移時間τ來計算si加入cj帶來的網(wǎng)絡消耗。令ωij=τμij作為網(wǎng)絡消耗的權(quán)值。

一般來說，應該選擇網(wǎng)絡負擔最小的控制器作為主控制器。如果cj飽和而且在它成為si的主控制器后會超載，那么Δij就會為負值，以此代表懲罰。這里用f和f′分別代表網(wǎng)絡變化前后的配置，因此有:

Bj(f′)=Bj(f)+λ(si)

(5)

定義利用度比為:

(6)

這個比率表示交換機si的主控制器重選后的利用度與總利用度的比例。符號Θ表示策略空間，它指所有博弈者的本地負載沒有超出負荷，用下式來計算利用度的改變：

(7)

2.3 拓展的OF協(xié)議

本文修改了OF協(xié)議來增強原主控制器、可能的目標以及遷移的交換機之間的交互。所有的信息將在博弈中發(fā)送，信息如表1。

表1 拓展的OF協(xié)議Tab. 1 Extended OpenFlow protocol

3 仿真環(huán)境及結(jié)果分析

在這個環(huán)節(jié)使用Floodlight[9]作為控制器并用Mininet[10]根據(jù)實際互聯(lián)網(wǎng)服務提供商(Internet Service Provider, ISP)生成SDN來進行仿真驗證。

3.1 仿真環(huán)境

3.1.1 Floodlight控制器

Floodlight是目前主流的SDN控制器之一，它通過加載相應模塊實現(xiàn)對應的功能，可以通過自定義編輯模塊適應網(wǎng)絡的要求。本文基于Floodlight建立了博弈系統(tǒng)，結(jié)構(gòu)如圖3所示。

圖3 博弈系統(tǒng)結(jié)構(gòu) Fig. 3 GAME-SM architecture

每個控制器有4個模塊，負載測量實時檢測控制器的負載和記錄來自每個交換機的消息到達率。同時設(shè)置上限和下限兩個閾值，超過上限的控制器將會給交換機選擇模塊發(fā)送過載信號進行主控制器重選；低于下限值的控制器將會優(yōu)先成為交換機遷移的新主控制器。

決策模塊控制其他的控制器在同一GF內(nèi)進行博弈。動作執(zhí)行模塊首先接收決策模塊和交換機選擇模塊的指示，然后實現(xiàn)根據(jù)接收的信息執(zhí)行相應的動作：保留交換機、拒絕交換機以及遷移交換機。

這些模塊通過建立IGameService接口并由GameImpl服務來實現(xiàn)。其中GameImpl注冊了IFloodlightProviderService來監(jiān)聽和接收Openflow消息，控制器通過調(diào)用IFloodlightProvider與Openflow交換機進行交互。

3.1.2 Mininet平臺

Mininet可以通過Open vSwitches[12]來建立各種規(guī)模的OF網(wǎng)絡，它分別在內(nèi)核用戶空間中實現(xiàn)數(shù)據(jù)平面和控制平面。Mininet已經(jīng)被廣泛地使用來驗證控制器性能。

3.1.3 仿真環(huán)境搭建

本文的實驗基于一個真實的ISP拓撲，采取自Datacenter Network[13]，擁有427個設(shè)備和10 000臺服務器。整個拓撲使用Mininet進行仿真，其中服務器配置為:Intel Core I7處理器和16 GB DDR3 RAM，使用VMWare創(chuàng)建虛擬機，系統(tǒng)安裝Ubuntu14.04，其中一臺服務器運行Mininet，其余運行SDN控制器。

3.2 仿真結(jié)果分析

在仿真的開始，通過Iperf[14]發(fā)出大量分布不均勻的流，所有的交換機都配置一個流入口“轉(zhuǎn)發(fā)給控制器”。如果負載測量模塊檢測到一個控制器被如此多的事件超負荷運作，它將會初始化一些交換機的主控制器重選來減輕網(wǎng)絡負載。圖4表示了交換機遷移數(shù)量與決策遷移時間的關(guān)系。

圖4 不同遷移交換機數(shù)時的決策遷移時間 Fig. 4 Decision and switch migration time with different number of migrated switches

圖5表示了由式(7)得到的Δij在3個不同距離下ωij的曲線圖，其中τ表示決策與遷移時間。如圖所示，效用的增長會隨著距離ωij的增長或者利用度比γ的減小而變緩。

圖5 利用度在不同下ω的變化 Fig. 5 Utility degree change in different ω

圖6表示了負載在主控制器重選前后的變化?？梢钥吹街骺刂破髦剡x后，控制器的負載更平衡了。

圖7表明了過載控制器的累計概率和響應時間，并且比較了GAME-SM與靜態(tài)分布式控制器(Distributed-CoNTroLler, D-CNTL)的差別。曲線說明超過80%的Packet-In事件在重選前有30 ms的時延，但是這種現(xiàn)象在經(jīng)過處理后得到了改善。其中GAME-SM算法的控制器響應時間在20 ms時就能處理全部的Packet-In事件，比D-CNTL算法減少了50%的時間。

圖6 控制器負載 Fig. 6 Load of controller

圖7 控制器響應時間 Fig. 7 Controller response time

4 結(jié)語

本文旨在進一步研究SDN網(wǎng)絡的彈性控制。首先設(shè)置了零和博弈模型來決定哪些控制器需進行主控制器重選；然后實現(xiàn)了基于博弈論決策的分配機制；最后，數(shù)值仿真結(jié)果說明本文的機制能夠有效地減少高負荷控制器的負載。

但是本文是基于軟件虛擬仿真，與實際真實網(wǎng)絡可能有區(qū)別，需要在未來進行實體驗證。

參考文獻(References)

[1] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks [J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[2] TOOTOONCHIAN A, GANJALI Y. HyperFlow: a distributed control plane for OpenFlow [C]// INM/WREN ’10: Proceedings of the 2010 Internet Network Management Conference on Research on Enterprise Networking. Berkeley, CA: USENIX Association, 2010: 3.

[3] KOPONEN T, CASADO M, GUDE N, et al. Onix: a distributed control platform for large-scale production networks [C]// OSDI ’10: Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010: 351-364.

[4] YEGANEH S H, GANJALI Y. Kandoo: a framework for efficient and scalable offloading of control applications [C]// HotSDN ’12: Proceedings of the 2012 1st Workshop on Hot Topics in Software Defined Networks. New York: ACM, 2012:19-24.

[5] ONF. OpenFlow switch specification [EB/OL]. [2013- 04- 25]. https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.3.2.pdf.

[6] DIXIT A, HAO F, MUKHERJEE S, et al. Towards an elastic distributed SDN controller [J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 7-12.

[7] BARI M F, ROY A R, CHOWDHURY S R, et al. Dynamic controller provisioning in software defined networks [C]// CNSM ’13: Proceedings of the 2013 9th International Conference on Network and Service Management. Washington, DC: IEEE Computer Society, 2013:18-25.

[8] CHENG G, CHEN H. Game model for switch migrations in software-defined network [J]. Electronics Letters, 2014, 50(23):1699-1700.

[9] Project Floodlight. Floodlight [EB/OL]. [2017- 05- 10]. http://www.projectfloodlight.org/floodlight/.

[10] Mininet. An instant virtual network [EB/OL]. [2017- 05- 10]. http://www.mininet.org/.

[11] 何保鋒,張軍麗.基于博弈論的SDN彈性控制機制研究[J].計算機工程與應用,2017, 53(7):128-132.(HE B F, ZHANG J L. Research on game theory-based SDN elastic control [J]. Computer Engineering and Applications, 2017,53(7):128-132.)

[12] Open vSwitch—an open virtual switch [EB/OL]. [2014- 08- 13]. http://openvswitch/.

[13] BENSON T, AKELLA A, MALTZ D A. Network traffic characteristics of data centers in the wild [C]// IMC ’10: Proceedings of the 2010 10th ACM SIGCOMM Conference on Internet Measurement. New York: ACM, 2010: 267-280.

[14] IPerf—the TCP/UDP bandwidth measurement tool [EB/OL]. [2016- 06- 08]. https://iperf.fr/.

This work was partially supported by the Ph. D. Research Startup Foundation of Chongqing University of Posts and Telecommunications (A2015-41), the Science Research Project of Chongqing University of Posts and Telecommunications for Young Scholars (A2015-62).

FANZifu, born in 1977, M. S., associate professor. His research interests include next generation network technology, communication operation management.

ZHOUKaiheng, born in 1992, M. S. candidate. His research interests include next generation network technology, SDN load balance.

YAOJie, born in 1994, M. S. candidate. His research interests include next generation network technology, SDN.