基于合作博弈的數(shù)據(jù)中心骨干網(wǎng)帶寬分配策略

孟　飛　蘭巨龍　胡宇翔

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

?

基于合作博弈的數(shù)據(jù)中心骨干網(wǎng)帶寬分配策略

孟飛蘭巨龍胡宇翔

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

摘要數(shù)據(jù)中心(data center, DC)之間通過部署流量工程來提高連接各個數(shù)據(jù)中心骨干網(wǎng)的利用率，雖然效率提升顯著，但對不同類型匯聚流的帶寬分配的公平性沒有考慮.將多個匯聚流對帶寬分配的競爭行為建模為一個合作博弈，通過尋求此博弈的納什談判解(Nash bargaining solution, NBS)來確定優(yōu)化的帶寬分配策略CGBA(cooperation game based bandwidth allocation)，權(quán)衡各匯聚流的最小帶寬保證與帶寬分配的公平性.在Mininet平臺上進(jìn)行實驗仿真并和典型的帶寬分配策略對比，結(jié)果表明CGBA不但可保證各匯聚流的最小帶寬需求，還確保了各類流對帶寬資源競爭的公平性.

關(guān)鍵詞數(shù)據(jù)中心；合作博弈理論；納什談判解；帶寬分配；Mininet

隨著云計算技術(shù)的迅速發(fā)展，數(shù)據(jù)中心(data center, DC)已成為一種重要的信息通信基礎(chǔ)設(shè)施，它采用虛擬化技術(shù)將海量的計算、存儲、網(wǎng)絡(luò)等物理資源高度整合為一個共享虛擬資源池[1]，實現(xiàn)資源的高效共享.為了提高數(shù)據(jù)中心服務(wù)的性能和可靠性，數(shù)據(jù)中心通常分布在地理位置相距很遠(yuǎn)的世界各地，彼此之間通過高速骨干網(wǎng)絡(luò)互連[2-3].這些骨干網(wǎng)絡(luò)通常屬于同一個在線服務(wù)提供商(online service providers， OSPs)，如Google的G-scale[4]，這些網(wǎng)絡(luò)的建設(shè)成本巨大且其中發(fā)生數(shù)據(jù)丟包是不可接受的[5]，因此，高效合理地分配利用數(shù)據(jù)中心骨干網(wǎng)帶寬資源且保證數(shù)據(jù)流的傳輸服務(wù)質(zhì)量(quality of service， QoS)十分必要.

目前，對于數(shù)據(jù)中心骨干網(wǎng)帶寬分配的研究已經(jīng)成為學(xué)術(shù)界的一個重要研究課題，并取得了大量研究成果.LBAPS[6]，NetStitcher[7]都是通過感知帶寬使用狀況，前者優(yōu)先把待傳輸數(shù)據(jù)塊上傳到空閑帶寬大的節(jié)點(diǎn)，即通過占用空閑帶寬來減少傳輸時延；后者使用存儲-轉(zhuǎn)發(fā)算法調(diào)度數(shù)據(jù)塊，并根據(jù)帶寬使用狀況而實時調(diào)整變化.GRESE[8]是1個可以減少峰值帶寬消耗的調(diào)度算法，在流量高峰時段傳輸實時或時延敏感數(shù)據(jù)，而在非流量高峰時期傳輸非時延敏感流量，通過在不同時段對帶寬進(jìn)行分配，可使帶寬的使用代價顯著減少.以上3種方案均是通過調(diào)度策略對帶寬在時間軸上進(jìn)行的分配，雖可減少數(shù)據(jù)流傳輸?shù)膸掗_銷，但是沒有考慮不同類型數(shù)據(jù)流的帶寬需求差異，即沒有對不同數(shù)據(jù)流的差異需求區(qū)分對待.Ghosh等人[9]提出了一種數(shù)據(jù)中心骨干網(wǎng)可擴(kuò)展多類流管理策略，通過網(wǎng)絡(luò)分層實現(xiàn)管理可擴(kuò)展，根據(jù)需求的不同為每類流進(jìn)行帶寬分配，定義每類流的效用函數(shù)并以整體效用最大化為目標(biāo)，但是它沒有考慮不同流之間帶寬分配的公平性.OSPs通常通過部署流量工程合理布局流量來提高數(shù)據(jù)中心骨干網(wǎng)的鏈路帶寬利用率，例如Google的B4[5]通過使用基于OpenFlow的SDN架構(gòu)實施流量工程，把應(yīng)用流分隔部署到多條路徑上來均衡流量，鏈路的平均帶寬利用率高達(dá)70%，它使用最大最小公平(max-min fairness)[10]算法為各類流分配帶寬，提供了較高的公平性.但鑒于最大最小公平算法固有的缺陷，B4對各類流的帶寬需求差異性考慮不足，因而使得對帶寬需求較大的流的QoS保障受限.在數(shù)據(jù)中心骨干網(wǎng)鏈路帶寬分配過程中，公平和效率是要綜合考慮的2個方面，只有這樣才能在保證帶寬資源高效利用的同時為各類流提供可預(yù)測的傳輸性能，提供較高水平的QoS保障.

博弈論[11]是應(yīng)用數(shù)學(xué)的一個分支，適合于研究具有競爭或?qū)剐再|(zhì)的各種行為.在帶寬分配過程中，不可避免地會存在多個任務(wù)對有限帶寬資源的競爭，而博弈論又恰好能有效地解決多個自私個體之間的競爭問題，從而達(dá)到全局任務(wù)效用值最優(yōu).合作博弈納什談判解(Nash bargaining solution, NBS)已廣泛用于解決資源分配中效率和公平的權(quán)衡[12].受文獻(xiàn)[12-14]啟發(fā)，本文將數(shù)據(jù)中心骨干網(wǎng)鏈路上多類匯聚流對共享帶寬的競爭分配問題建模為一個合作博弈，各匯聚流之間競爭帶寬并以最大化整體效用為目標(biāo)，通過設(shè)計集中式的帶寬分配算法來尋求該博弈問題的納什談判解，得到優(yōu)化的帶寬分配策略，并將該策略稱為基于合作博弈的帶寬分配(cooperation game based bandwidth allocation, CGBA).最后基于Mininet[15]對所設(shè)計的模型進(jìn)行實驗仿真驗證，并與現(xiàn)有典型策略的實驗結(jié)果對比以表明其優(yōu)勢.

1基于合作博弈的帶寬分配模型

1.1網(wǎng)絡(luò)模型

Fig. 1　Network architecture.圖1　網(wǎng)絡(luò)架構(gòu)

如圖1所示，本文的網(wǎng)絡(luò)架構(gòu)采用2層控制架構(gòu)，該結(jié)構(gòu)目前已被大多數(shù)基于SDN的數(shù)據(jù)中心網(wǎng)絡(luò)所普遍采用[4-5,14].網(wǎng)絡(luò)中有2種類型控制器:多個本地控制器和1個全局控制器，前者對所屬單個數(shù)據(jù)中心(DC)進(jìn)行管理，不同DC之間相互獨(dú)立，地位相同；1個集中式全局控制器管理整個網(wǎng)絡(luò).數(shù)據(jù)中心間通過可編程邊界網(wǎng)關(guān)(programmable border gateways)互連，數(shù)據(jù)中心內(nèi)部虛擬機(jī)(virtual machine, VM)流量在邊界網(wǎng)關(guān)匯聚分類，兩DC間的通信可簡化為分屬的兩網(wǎng)關(guān)間的通信.本文基于博弈理論的思想對數(shù)據(jù)中心骨干網(wǎng)鏈路上多個匯聚流的帶寬分配問題進(jìn)行建模分析.帶寬資源被多條流共享，在進(jìn)行帶寬分配時除了要使帶寬資源整體利用率最大化外還要對各個不同類型數(shù)據(jù)流提供最小帶寬保障及保證分配的公平性，合作博弈的解——納什談判解(NBS)可有效權(quán)衡公平性和效率的關(guān)系，因此基于合作博弈模型分析解決此問題更為合適.

Fig. 2　N flow contend the share bandwidth.圖2　N條匯聚流競爭鏈路帶寬資源

定義2. 矩陣F=(fij)N×M表示DC骨干網(wǎng)中各匯聚流的分布，二進(jìn)制變量fij定義如下：

(1)

1.2博弈建模

(2)

定理1. 存在唯一滿足定義3中條件的解，且是下述問題的最優(yōu)解：

(3)

NBS的存在性與唯一性證明見文獻(xiàn)[11].

將目標(biāo)函數(shù)取對數(shù)，式(3)等價于：

(4)

由定理1可知，CGBA博弈的NBS是下述全局最優(yōu)問題的解：

(5)

定理2. 存在αi≥0，βi≥0(i∈{1,2,…,N})和γm≥0(m∈{1,2,…,M})，使得?i∈{1,2,…,N}，?m∈{1,2,…,M}有

(6)

(7)

(8)

(9)

證明. 利用拉格朗日乘子方法分析最優(yōu)化問題式(5)，其拉格朗日函數(shù)定義為

(10)

其中,αi，βi，γm為非負(fù)的拉格朗日乘子.求關(guān)于bi的一階導(dǎo)數(shù)，并根據(jù)Karush-Kuhn-Tucker(KKT)[16]條件，則有式(6)～(9)成立.

證畢.

“互補(bǔ)問題”作為一類新的數(shù)學(xué)模型，是1964年美國Cottle[17]在其博士學(xué)位論文中提出的.非線性互補(bǔ)問題(nonlinear complementarity problem， NCP)是研究非線性互補(bǔ)條件的問題，其定義為：映射S:n→n，求向量x∈n，滿足x≥0,S(x)≥0,xTS(x)=0，非線性互補(bǔ)問題記為NCP(S)，其中n表示n維歐氏空間，n中的矢量均為列矢量，xTy表示x與y的內(nèi)積.

NCP函數(shù)的定義為：函數(shù)φ:2→，對?x,y∈2，φ(x,y)=0，當(dāng)且僅當(dāng)x≥0,y≥0,xTy=0.因為NCP函數(shù)可自動保證非線性互補(bǔ)條件的成立，利用某些NCP函數(shù)，我們可將互補(bǔ)問題轉(zhuǎn)化為等價的方程組.對于任意一個NCP函數(shù)φ(·,·)，非線性互補(bǔ)問題NCP(S)可等價地轉(zhuǎn)化為方程組：

(11)

本文選擇Mangasarian[18]提出的NCP函數(shù)φ(a,c)=|a-c|3-a3-c3，這個函數(shù)關(guān)于a，c是光滑的.利用這個NCP函數(shù)將不等式約束問題的KKT條件，即式(6)～(9)，轉(zhuǎn)化為等價光滑方程組：

(12)

后續(xù)的問題就是如何選擇簡單適當(dāng)?shù)乃惴ㄈデ蠼膺@個光滑方程組.帶一維搜索的Newton法克服了傳統(tǒng)Newton法的局部收斂缺點(diǎn)，使此方法具有全局收斂性的同時保持了傳統(tǒng)Newton法的簡單、收斂快的優(yōu)點(diǎn).共軛梯度法(conjugate gradient， CG)[19]是帶有特殊性質(zhì)的共軛方向法，僅需利用一階導(dǎo)數(shù)信息，在產(chǎn)生共軛向量計算新向量時，只要用一個相鄰的前面的向量，所需存儲和計算量很少.為了不失效率而又保持收斂性，對Newton方程運(yùn)用CG法迭代，在達(dá)到系統(tǒng)的某些非精確近似解時終止迭代，用非精確一維搜索 Newton-CG法來求解大型非線性光滑方程組，算法描述如下:

算法1. 基于Newton-CG算法的帶寬分配計算.

輸入：初始點(diǎn)z0∈R2N+M、流分布矩陣F=(fij)N×M、帶寬需求向量D=(D1,D2,…,DN)、鏈路帶寬容量Cm(m∈{1,2,…,M})、迭代次數(shù)k=0、參數(shù)ηk和精度ε；

輸出：帶寬分配計算結(jié)果b=(b1,b2,…,bN).

① if ‖F(xiàn)(zk)‖≤ε，結(jié)束，else轉(zhuǎn)②；

② 用CG算法解線性方程組

③ 令xk+1=xk+αkpk，其中αk滿足

Wolfe或Armijo后退準(zhǔn)則等；

④k=k+1，轉(zhuǎn)①.

本算法的計算復(fù)雜度主要集中在步驟②③，在使用CG算法求解線性方法組時，終止條件‖rk‖≤ηk‖F(xiàn)(zk)‖使得算法計算量減少，計算復(fù)雜度降低；在進(jìn)行迭代求解時，僅需知道前面一個向量，存儲空間可重復(fù)利用，算法空間復(fù)雜度低.非精確的一維Newton搜索算法簡單，全局收斂速度快，計算復(fù)雜度低.因此，本算法的計算復(fù)雜度和空間復(fù)雜度均較低.本算法的實質(zhì)是用共軛梯度法解Newton方程，具有單步收斂性，高穩(wěn)定性，關(guān)于共軛梯度法的收斂性證明可參見文獻(xiàn)[20].

2集中式帶寬分配算法

在進(jìn)行帶寬分配時，控制器需要監(jiān)測底層網(wǎng)絡(luò)資源使用狀況，網(wǎng)絡(luò)狀態(tài)信息的獲取是由各交換機(jī)上報本地控制器，然后再上報全局控制器而得到的.CGBA部署在集中式全局控制器上計算全網(wǎng)的帶寬分配結(jié)果，其中，算法1計算得到帶寬分配結(jié)果，算法2控制帶寬分配的迭代收斂.得到結(jié)果后全局控制器向特定的某條流的源、目的DC本地控制器下發(fā)結(jié)果，本地控制器再向相關(guān)交換機(jī)下發(fā)配置命令，通過對特定隊列的流表的配置實現(xiàn)數(shù)據(jù)包轉(zhuǎn)發(fā)速率控制.

Fig. 3　The simulation topology.圖3　仿真拓?fù)鋱D

算法2. 集中式帶寬分配控制.

輸出：帶寬分配向量b=(b1,b2,…,bN).

① for 所有的流：?i∈{1,2,…,N}，do

⑤ 在集中式控制器中運(yùn)行算法 1；

⑥ end while

⑦ end for

由于要保持全網(wǎng)信息的一致性，SDN網(wǎng)絡(luò)中控制器會周期性地向交換機(jī)節(jié)點(diǎn)下發(fā)詢問信息，因此通過在下發(fā)詢問信息時捎帶控制器對節(jié)點(diǎn)的帶寬配置信息則避免了對節(jié)點(diǎn)配置時的一部分額外開銷.

本算法的計算復(fù)雜度主要在步驟④⑤，算法最多迭代S次，因此其計算復(fù)雜度最大為S倍的算法1的計算復(fù)雜度，S為定值且算法1復(fù)雜度低，則本算法計算復(fù)雜度較低.

3CGBA的仿真實驗與性能分析

3.1實驗場景建立

類比Falloc[12]建立實驗仿真驗證環(huán)境，在基于OpenFlow的Mininet仿真平臺上對CGBA進(jìn)行仿真驗證.建立同圖1所示架構(gòu)的網(wǎng)絡(luò)拓?fù)?，為不失一般性同時為簡便分析起見，建立3個相互連通的DC域，即存在3條鏈路；此網(wǎng)絡(luò)中共有5條流，則M=3，N=5.如圖3所示，3個交換機(jī)相互連通，每個交換機(jī)連接4個主機(jī)對外等價于一個DC域，鏈路的帶寬向量為C=(1 Gbps，2 Gbps，3 Gbps).在進(jìn)行帶寬分配時，要從效率和公平2方面綜合比較分配策略的性能，效率主要從對各流的最小帶寬的保障考慮，根據(jù)對需求的滿足程度衡量效率的高低，定義平均帶寬分配滿足度(satisfaction degree,SD)為

(13)

其中，SD越接近于1，說明對各流的帶寬分配滿足較好，效率越高；反之則效率越低.對公平性的考量，選用文獻(xiàn)[21-22]中的公平指數(shù)(fairness index,FI)來進(jìn)行評價，本文公平指數(shù)的定義為

(14)

其中，F(xiàn)I越接近于1, 說明公平性越高; 反之，則說明公平性越低.

在資源飽和場景(所有鏈路均能滿足其上的全部流的帶寬需求之和)中，全部流需求都會獲得滿足，沒必要進(jìn)行帶寬博弈，按需分配即可，因此本文重點(diǎn)研究資源匱乏(至少存在一條鏈路的帶寬容量不能滿足其上的所有流的帶寬需求之和)的情況，并將CGBA和其他策略進(jìn)行對比.

3.2數(shù)值結(jié)果與討論

基帶寬的選取是根據(jù)每條流的歷史需求信息選取的，越接近博弈結(jié)果則求解得到最終結(jié)果的速度越快，博弈時間越短.不同的流分布對CGBA本身不產(chǎn)生影響，即不會影響CGBA的性能，因此隨機(jī)取定流分布矩陣

本文把CGBA和按比例帶寬分配策略(pro-portionalpolicy，PP)、基于優(yōu)先級的帶寬分配策略(prioritybasedpolicy，PBP)及最大最小公平分配(max-minfairness，MMF)進(jìn)行比較.這3種策略的描述如下：

3) 最大最小公平分配(MMF).若分布在帶寬容量為Ci的鏈路linki上的流為flow1，flow2，…，flown，其帶寬需求從小到大排序為D1，D2，…，Dn，那么，我們初始把Cin帶寬分配給flow1，這可能會超過flow1的需求，將超出flow1需求的那部分加上剩余沒有分配的帶寬平均分給其他流，依次按此方法處理，則bi=(1≤i≤n).該過程結(jié)束時，每條流得到的帶寬不會比自己要求的多，而且，如果其需求得不到滿足，得到的帶寬也不會比其他得到最多帶寬的流得到的少.

Fig. 4　The results of average satisfaction degree.圖4　平均帶寬分配滿足度

圖4、圖5表示基帶寬為1 Gbps，D3=D5=1 Gbps，D2=D4=D(為仿真分析簡便，其他情況僅是變量個數(shù)的增加、維度的擴(kuò)展)時，運(yùn)用4種策略分別進(jìn)行帶寬分配的所得結(jié)果.在帶寬資源充足(帶寬需求D在0到1 Gbps之間)時，即資源飽和場景中，4種策略結(jié)果相同.在帶寬資源匱乏場景中，CGBA通過合作博弈對帶寬進(jìn)行最優(yōu)分配，滿足各流的最小帶寬需求之后，剩余帶寬按照需求差異按比例分配，可以提供一個唯一且公平的帕累托最優(yōu)點(diǎn)，兼顧了不同的需求和最小性能保證，具有很高的公平性，效率和公平2方面性能均優(yōu)于其他策略.MMF是一種對低需求用戶按需保障、高需求用戶“盡力而為”保障的分配策略，因其過于追求流量公平，沒有考慮各個流之間的需求差異性，所以當(dāng)各流的需求差異較大時，對需求大的流的保障則會造成限制，反而造成MMF公平性不是很好；同時因為沒有對流需求差異加以區(qū)分，導(dǎo)致需求較大的流的帶寬分配滿足度較低(隨需求的增大呈反比例降低)，故整體QoS保障水平受限，效率較低.PP實質(zhì)上是一種按需求大小加權(quán)的分配策略，對不同需求用戶機(jī)械地“一視同仁”對待，僅根據(jù)需求的占比決定分配的大小，因此平均帶寬分配滿足度和公平指數(shù)均較低.PBP僅考慮各類流的優(yōu)先級的不同，對高優(yōu)先級的流按需滿足，而對優(yōu)先級低的流可能會造成帶寬分配“餓死”現(xiàn)象，平均帶寬分配滿足度和分配公平性在4種策略中最低.

Fig. 5　The results of fairness index.圖5　公平指數(shù)

Fig. 6　Comparison of convergence speed.圖6　收斂速度比較

按照“天下沒有免費(fèi)的午餐(no free lunch, NFL)”[23]理論，一種算法不可能在任何方面或在任何問題上都能夠提供比其他所有算法更好的性能.在我們的實驗結(jié)果中也觀察到了這點(diǎn).如圖6所示，考察在給定基帶寬為1 Gbps，flow2和flow4的帶寬需求分別為1.5 Gbps，2.5 Gbps，3.5 Gbps時3種策略的迭代收斂情況.圖6表明：選取的基帶寬合適與否影響迭代的周期，即帶寬分配博弈的時間，越接近最優(yōu)值則所需尋優(yōu)迭代次數(shù)越少，收斂越快；CGBA的收斂速度比MFF快，較PP和PBP慢,并將4種策略分別進(jìn)行50次實驗，每種策略達(dá)到博弈穩(wěn)定所需的平均計算時間如圖7所示:

Fig. 7　Comparison of computational complexity.圖7　不同策略計算復(fù)雜度比較

從圖7可以看出，CGBA的計算復(fù)雜度要明顯高于PP和PBP，但是卻低于MFF.這表明，CGBA具有較高帶寬分配滿足度和較高公平性是以犧牲一定計算復(fù)雜度為代價的，并進(jìn)一步驗證了文獻(xiàn)[23]中NFL理論的正確性.

4結(jié)束語

本文深入研究了數(shù)據(jù)中心骨干網(wǎng)絡(luò)中的帶寬分配問題，將各條流對共享帶寬的競爭分配問題建模為一個合作博弈模型，并通過尋求該博弈模型的Nash談判解NBS得到優(yōu)化的帶寬分配策略CGBA.將CGBA與3種典型的帶寬分配策略進(jìn)行了詳盡的實驗對比.實驗結(jié)論表明，CGBA在各種網(wǎng)絡(luò)場景中都能較好地提高帶寬分配的滿足度，為每條流提供最小帶寬保障，效率較高；同時可保證較高的帶寬分配公平性.本文提出的帶寬分配策略為設(shè)計性能更佳的數(shù)據(jù)中心骨干網(wǎng)絡(luò)帶寬分配系統(tǒng)提供了借鑒和理論支持.

參考文獻(xiàn)

[1]Bari M F, Boutaba R, Esteves R, et al. Data center network virtualization: A survey[J]. IEEE Communications Surveys & Tutorials, 2013, 15(2): 909-928

[2]Mahimkar A, Chiu A, Doverspike R, et al. Bandwidth on demand for inter-data center communication[C] //Proc of the 10th ACM Workshop on Hot Topics in Networks. New York: ACM, 2011: 24:1-24: 6

[3]Greenberg A, Hamilton J, Maltz D A, et al. The cost of a cloud: Research problems in data center networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 39(1): 68-73

[4]Google. Inter-datacenter WAN with centralized TE using SDN and OpenFlow[EB/OL]. 2012[2014-12-22]. https://www.opennetworking.org/images/stories/downloads/misc/googlesdn.pdf

[5]Jain S, Kumar A, Mandal S, et al. B4: Experience with a globally-deployed software defined WAN[C] //Proc of the ACM SIGCOMM 2013. New York: ACM, 2013: 3-14

[6]Huang Yongfeng, Dong Yongqiang, Zhang Sanfeng, et al. Leftover bandwidth-aware peer selection algorithm for inter-datacenter content distribution[J]. Journal on Communications, 2013, 34(7): 24-33 (in Chinese)(黃永鋒, 董永強(qiáng), 張三峰, 等. 數(shù)據(jù)中心間空閑帶寬感知的內(nèi)容分發(fā)算法[J]. 通信學(xué)報, 2013, 34(7): 24-33)

[7]Laoutaris N, Sirivianos M, Yang X, et al. Inter-datacenter bulk transfers with NetStitcher[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 74-85

[8]Thyaga N, Krishna P N P. Lowering inter-datacenter bandwidth costs via bulk data scheduling[C] //Proc of the 12th IEEE/ACM Int Symp on Cluster, Cloud and Grid Computing. New York: ACM, 2012: 244-251

[9]Ghosh A, Ha S, Crabbe E, et al. Scalable multi-class traffic management in data center backbone networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(12): 2673-2684

[10]Danna E, Hassidim A, Kaplan H, et al. Upward max min fairness[C] //Proc of the IEEE Int Conf on Computer Communications (INFOCOM 2012). Piscataway, NJ: IEEE, 2012: 837-845

[11]Osborne M J, Rubinste A. A Course in Game Theory[M]. Cambridge, MA: MIT Press, 1994: 12-30

[12]Guo Jian, Liu Fangming, Tang Haowen, et al. Falloc: Fair network bandwidth allocation in IaaS datacenters via a bargaining game approach[C] //Proc of the 21st IEEE Int Conf on Network Protocols (ICNP). Piscataway, NJ: IEEE, 2013: 1-10

[13]Vitaly A, Ruslan S. Global network modelling based on mininet approach[C] //Proc of the 2nd ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking. New York: ACM, 2013: 145-146

[14]Liu Zhongjin, Li Yong, Su Li, et al. M2cloud: Software defined multi-site data center network control framework for multi-tenant[J]. ACM SIGCOMM Computer Communication Review, 2013, 43(4): 517-518

[15]Lantz B, Heller B, McKeown N. A network in a laptop: Rapid prototyping for software-defined networks[C] //Proc of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks. New York: ACM, 2010: 19:1-19:6

[16]Ya?che H, Mazumdar R, Rosenberg C. A game theoretic framework for bandwidth allocation and pricing in broadband networks[J].IEEE/ACM Trans on Networking, 2000, 8(5): 667-678

[17]Cottle R W. Nonlinear programs with positively bounded jacobians[J]. SIAM Journal on Applied Mathematics, 1964, 14(1): 147-158

[18]Mangasarian O L. Equivalence of the complementarity problem to a system of nonlinear equations[J]. SIAM Journal on Applied Mathematics, 1976, 31(1): 89-92

[19]Hager W W, Zhang Hongchao. A survey of nonlinear conjugate gradient methods[J]. Pacific Journal of Optimization, 2006, 2(1): 35-58

[20]Chen Yu. The convergence research on conjugate gradient method[D]. Jingzhou, Hubei: Yangtze University, 2012 (in Chinese)(陳禹. 共軛梯度法的收斂性研究[D]. 湖北荊州: 長江大學(xué), 2012)

[21]Jain R, Chiu D M, Hawe W. A quantitative measure of fairness and discrimination for resource allocation in shared computer system，TR-301[R]. Saint Louis, Missouri: Washington University, 1984

[22]Chiu D M, Jain R. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[J]. Computer Networks and ISDN Systems, 1989, 17(1): 1-14

[23]Wolpert D H，Macready W G. No free lunch theorems for optimization[J]. IEEE Trans on Evolutionary Computation, 1997, 1(1): 67-82

Meng Fei, born in 1989. Master candidate. His main research interests include new network architecture, QoS.

Lan Julong, born in 1962. Professor and PhD supervisor. His main research interests include new network architecture, information security, and computer network.

Hu Yuxiang, born in 1982. Lecturer. His main research interests include new network architecture, information security.

A Cooperative Game Based Data Center Backbone Network Bandwidth Allocation Policy

Meng Fei, Lan Julong, and Hu Yuxiang

(NationalDigitalSwitchingSystemEngineering&TechnologicalR&DCenter,Zhengzhou450002)

AbstractCurrently, traffic engineering is typically deployed to improve the utilization of data centers (DC) backbone networks, which usually belongs to the same online service providers. Although the efficiency is remarkable, the bandwidth allocation fairness of different aggregate flow isn’t considered. Hence, the QoS guarantee is restricted. Because the bandwidth resource is expensive and packet loss is typically thought unacceptable, the bandwidth utilization should be maximized, at the same time, the QoS guarantee of different flow should be improved. In this paper, the problem of contending the share bandwidth is modeled as a cooperative game, and different aggregate flow compets the share bandwidth and maximizes the overall bandwidth resource utilization simultaneously, and the optimal bandwidth allocation policy, called cooperation game based bandwidth allocation (CGBA), is obtained through searching the Nash bargaining solution (NBS) of the game and balancing the tradeoff between minimum bandwidth guarantee and bandwidth allocation fairness. Simulation on a Mininet testbed shows that the proposed policy can effectively guarantee minimum bandwidth of each aggregate flow while ensuring the allocation fairness, compared with three other classical bandwidth allocation policies.

Key wordsdata centers (DC); cooperative game theory; Nash bargaining solution (NBS); bandwidth allocation; Mininet

收稿日期：2014-12-23；修回日期：2015-03-19

基金項目：國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計劃基金項目(2012CB315901，2013CB329104)；國家自然科學(xué)基金項目(61372121)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA013505)

中圖法分類號TP391

This work was supported by the National Basic Research Program of China (973 Program) (2012CB315901,2013CB329104), the National Natural Science Foundation of China (61372121), and the National High Technology Research and Development Program of China (863 Program) (2013AA013505).