鄭鵬飛，尤佳莉，王勁林，曾學(xué)文

（1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，100190，北京；2.中國科學(xué)院大學(xué)，100049，北京）

不同于計(jì)算資源和存儲資源，多租戶云很難為網(wǎng)絡(luò)資源提供定量的服務(wù)保障，這是因?yàn)榫W(wǎng)絡(luò)流在傳輸過程中會影響經(jīng)過鏈路上的其他網(wǎng)絡(luò)流，且造成的影響被傳播到一個(gè)區(qū)域乃至整個(gè)網(wǎng)絡(luò)。并非所有的網(wǎng)絡(luò)協(xié)議都像TCP一樣對網(wǎng)絡(luò)比較友好，網(wǎng)絡(luò)流之間的競爭非常普遍。幾乎所有的應(yīng)用都依賴網(wǎng)絡(luò)通信，而一個(gè)多租戶云的內(nèi)部網(wǎng)絡(luò)流量占據(jù)其所有網(wǎng)絡(luò)流量的80%［1］，因此，多租戶云的內(nèi)部網(wǎng)絡(luò)共享問題值得深入研究。

目前，基于資源預(yù)留的算法［2-4］要求在租戶分配虛擬機(jī)的時(shí)候就預(yù)留所需的帶寬，這些帶寬不能被其他租戶使用，導(dǎo)致資源利用不充分。一些系統(tǒng)使用 一 般 處 理 器 共 享 （general processor sharing，GPS）理想模型［5］及其近似算法［6-7］，以網(wǎng)絡(luò)流為對象進(jìn)行公平調(diào)度，租戶可以通過增加網(wǎng)絡(luò)流的數(shù)量來獲取更多的帶寬。Seawall和AF-QCN根據(jù)目的虛擬機(jī)或交換機(jī)返回的擁塞信號調(diào)整源虛擬機(jī)的發(fā)送速度，算法未考慮目的虛擬機(jī)，且租戶可以通過增加虛擬機(jī)間的連接數(shù)量來提升競爭力［8-9］。Gate-Keeper通過在虛擬機(jī)監(jiān)視器（virtual machine monitor，VMM）中增加流量控制模塊限制虛擬機(jī)的進(jìn)出口帶寬在一個(gè)可接受的范圍內(nèi)，算法只考慮了主機(jī)上的網(wǎng)絡(luò)競爭［10］。NetShare［1］中，每條鏈路都依據(jù)租戶的靜態(tài)權(quán)重進(jìn)行帶寬分配，該方法不能反映租戶對不同鏈路的需求差異。FairCloud在鏈路或者整個(gè)網(wǎng)絡(luò)上按照正在通信的虛擬機(jī)規(guī)模計(jì)算租戶應(yīng)該獲得的帶寬比例［11］，其中，鏈路級別的公平算法不能很好地實(shí)現(xiàn)網(wǎng)絡(luò)公平，網(wǎng)絡(luò)級別的公平算法需要監(jiān)視整個(gè)網(wǎng)絡(luò)所有網(wǎng)絡(luò)流的狀態(tài)，在實(shí)現(xiàn)上代價(jià)較大。

文獻(xiàn)［11］指出，多租戶云的內(nèi)部網(wǎng)絡(luò)共享問題有3個(gè)無法同時(shí)滿足的目標(biāo)，分別是最小保證、公平分配和最大利用。本文提出一種平衡3個(gè)目標(biāo)的FairNet策略。該策略由主機(jī)和鏈路的帶寬分配算法組成，分別在主機(jī)上實(shí)現(xiàn)了最小保證和最大利用，在鏈路上實(shí)現(xiàn)了公平分配和最大利用。仿真實(shí)驗(yàn)結(jié)果表明，相比于其他算法，F(xiàn)airNet策略能更好地適應(yīng)不同的網(wǎng)絡(luò)通信模式，同時(shí)獲得較好的鏈路和網(wǎng)絡(luò)公平性。

1 問題建模

使用G=（V，E，T）代表多租戶云，其中，V、E、T分別是設(shè)備、鏈路、租戶的集合。設(shè)備包括虛擬機(jī)、主機(jī)和交換機(jī)，VV、VH、VS分別是虛擬機(jī)、主機(jī)、路由器的集合，有V=VV∪VH∪VS。對于租戶t∈T，它的虛擬機(jī)集合表示為?VV。

因此，不同的租戶處于競爭狀態(tài)，P要在租戶之間合理地分配帶寬。P有3個(gè)目標(biāo)：①公平分配。理想的公平性是根據(jù)租戶帶寬需求按比例進(jìn)行分配，即

目標(biāo)①、②、③無法同時(shí)得到滿足。資源預(yù)留策略［2-4］實(shí)現(xiàn)了最小保證，保留比例與需求一致時(shí)公平分配也得到滿足，但是容易造成資源浪費(fèi)，無法達(dá)到最大利用；資源競爭策略［5-11］保證某種程度的公平性，滿足最大利用，但是無法提供最小保證。因此，P必須在3個(gè)目標(biāo)之間進(jìn)行權(quán)衡。

此外，在實(shí)際網(wǎng)絡(luò)中，一個(gè)租戶的帶寬需求矩陣很難進(jìn)行估計(jì)和測量，這導(dǎo)致公平分配的公平性無法準(zhǔn)確定義。已有算法普遍利用權(quán)重代替帶寬需求矩陣定義公平分配，即目標(biāo)①變?yōu)?/p>

2 算法描述

本文提出一種多租戶云的內(nèi)部網(wǎng)絡(luò)共享策略——FairNet策略，由主機(jī)和鏈路的帶寬分配算法組成。

2.1 主機(jī)帶寬分配算法

以往的算法沒有指出權(quán)重設(shè)置的原則。觀察虛擬機(jī)的CPU、內(nèi)存、存儲等資源，可以發(fā)現(xiàn)這些資源都有定量的性能參數(shù)，參數(shù)的值既代表了虛擬機(jī)的需求，也代表了系統(tǒng)做出的服務(wù)質(zhì)量承諾。因此，帶寬也不應(yīng)該例外，虛擬機(jī)和租戶的網(wǎng)絡(luò)權(quán)重能夠從一些確定的帶寬參數(shù)推導(dǎo)得到。

定義虛擬機(jī)為

式中：cv，mv，sv分別代表 CPU、內(nèi)存、存儲分別表示保證帶寬和最大帶寬。主機(jī)的所有流量只與其上的虛擬機(jī)有關(guān)，容易為每個(gè)虛擬機(jī)提供最小帶寬保證，這就是的物理含義。是虛擬機(jī)帶寬的上限，取決于虛擬化技術(shù)和系統(tǒng)的設(shè)置。

主機(jī)h∈VH進(jìn)行資源分配時(shí)需要滿足條件

主機(jī)能夠確保每個(gè)虛擬機(jī)的保證帶寬，又允許剩余帶寬被全部共享，最小保證和最大利用同時(shí)得到滿足。增加了帶寬限制的虛擬機(jī)分配問題并非本文討論的重點(diǎn)，我們將它作為未來的工作。

根據(jù)虛擬機(jī)模型（6）對帶寬的要求，F(xiàn)airNet策略在VMM中實(shí)現(xiàn)了虛擬機(jī)帶寬分配算法，如圖1所示。該算法包括限速器、隊(duì)列和調(diào)度器3種組件，每一個(gè)虛擬機(jī)都有一個(gè)限速器和隊(duì)列，調(diào)度器是每個(gè)主機(jī)一個(gè)。虛擬機(jī)v的數(shù)據(jù)包發(fā)送后，首先經(jīng)過限速器，限速器采用流量限速算法［12-13］限制虛擬機(jī)的速度不超過bMv，超出限制的數(shù)據(jù)包被丟棄，而允許通過的數(shù)據(jù)包被隊(duì)列緩沖。調(diào)度器按照下式計(jì)算虛擬機(jī)權(quán)重，調(diào)度不同的隊(duì)列，以決定輸出的數(shù)據(jù)包

當(dāng)使用的調(diào)度器為GPS［5］時(shí)，能夠確保虛擬機(jī)v獲得不小于的保證帶寬。實(shí)際系統(tǒng)可以使用加權(quán)公平排隊(duì)（weighted fair queuing，WFQ）［6］等 GPS的近似算法。

圖1 虛擬機(jī)流量控制算法示意圖

2.2 鏈路帶寬分配算法

FairNet策略在交換機(jī)上為每一條鏈路實(shí)現(xiàn)基于租戶權(quán)重的帶寬分配算法。鏈路上的流量組成遠(yuǎn)比主機(jī)復(fù)雜，且?guī)捦蛔阋詽M足所有租戶的需求，因此，算法放棄最小保證。

每一個(gè)虛擬機(jī)在鏈路上的權(quán)重為

式中：β∈［0，1］。以式（11）取代式（9）計(jì)算虛擬機(jī)的權(quán)重，因?yàn)槭剑?）計(jì)算的權(quán)重可能會發(fā)生變化，而在相關(guān)鏈路上同步權(quán)重變化代價(jià)很大。這樣，一個(gè)虛擬機(jī)集合I的權(quán)重為

考慮鏈路的一個(gè)傳輸方向，租戶t∈T在其上傳輸了流量，流量的發(fā)送端和接收端的虛擬機(jī)集合分別為X和Y，權(quán)重分別為和，則t的權(quán)重為

當(dāng) H（x，y）=x+y，算法等價(jià)于 PS-L［11］。該形式?jīng)]有考慮發(fā)送端和接收端的帶寬需求不平衡所帶來的影響。考慮鏈路帶寬無限大的極限情況，每個(gè)租戶獲得的帶寬由發(fā)送端和接收端帶寬需求中較小的那個(gè)決定，而需求較大的另一端的剩余帶寬需求被浪費(fèi)了。帶寬資源有限時(shí)，租戶獲得的實(shí)際帶寬應(yīng)滿足式（2）的公平性要求，與極限情況比例一致。因此，H（x，y）應(yīng)由 min（x，y）決定權(quán)重的主要部分。FairNet策略中使用的H（x，y）為

式中：γ≥0，用于調(diào)節(jié)帶寬需求不平衡的影響。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 不同通信模式的實(shí)驗(yàn)

在NS-3［14］仿真器上對不同通信模式進(jìn)行實(shí)驗(yàn)。仿真場景如圖2所示，包含2個(gè)交換機(jī)S0、S1，它們間的鏈路為L。每一個(gè)交換機(jī)上連接有若干主機(jī)，每一個(gè)主機(jī)上有一個(gè)虛擬機(jī)。所有鏈路帶寬均為1Gb／s。圖2a是1對多的通信模式，租戶A的虛擬機(jī)A0向A1傳輸數(shù)據(jù)，租戶B的虛擬機(jī)B0同時(shí)向虛擬機(jī)Bi（i=1，…，N）傳輸數(shù)據(jù)。將圖2a的數(shù)據(jù)傳輸全部反向，則變?yōu)榱硕鄬?通信模式，如圖2b所示。圖2c是多對多的通信模式，租戶A的虛擬機(jī)AMi（i=1，…，5）向ARi（i=1，…，5）傳輸數(shù)據(jù)，租戶B的虛擬機(jī)BMi（i=1，…，P）向BRj（j=1，…，10-P）傳輸數(shù)據(jù)。實(shí)驗(yàn)中的通信均采用TCP協(xié)議，且不限制單條連接的傳輸速度，因此，租戶A、B的帶寬取決于在瓶頸鏈路L上的競爭情況。

圖2 不同通信模式場景示意圖

對比算法包括文獻(xiàn)［11］歸納或提出的Per-S（即Per-Source）、Per-D（即 Per-Destination）、Per-SD、PS-L、PS-N。所有算法均使用 WFQ［6］作為調(diào)度算法。虛擬機(jī)的保證帶寬和最大帶寬分別為0.4Gb／s和1Gb／s，PS-L和PS-N以保證帶寬作為虛擬機(jī)權(quán)重，因此，圖2中所有虛擬機(jī)的權(quán)重均相等。

實(shí)驗(yàn)結(jié)果如圖3所示。1對多和多對1通信模式中，PS-S和PS-D的曲線發(fā)生了對調(diào)，說明這2種算法不具有對稱性；Per-SD、PS-L、PS-N隨著N 的增大，租戶B的帶寬越來越多，最終接近其在L上能達(dá)到的最大帶寬1Gb／s，相應(yīng)地，租戶A的帶寬越來越小，直至為0，這對租戶A不公平，而FairNet策略較好地保護(hù)了租戶A在L上的帶寬。多對多模式中，PS-S、PS-D依然不具有對稱性；PS-L和PS-N將A、B的帶寬維持在1∶1的比例，沒有考慮發(fā)送端、接收端虛擬機(jī)數(shù)量的差異；Per-SD、FairNet策略則根據(jù)發(fā)送端、接收端的情況對租戶的帶寬分配做了相應(yīng)的調(diào)整。因此，F(xiàn)airNet策略更好地符合了不同通信模式的需求，算法參數(shù)γ用于調(diào)節(jié)接收端、發(fā)送端帶寬需求不平衡對算法的影響。

接下來將評估租戶內(nèi)部通信變化和虛擬機(jī)權(quán)重的影響。由于1對多模式每個(gè)租戶僅有1個(gè)發(fā)送端，容易觀察實(shí)驗(yàn)結(jié)果，因此實(shí)驗(yàn)采用1對多模式。

首先測量租戶內(nèi)部通信變化對算法的影響。在1對多通信模式下，N=6，B1、B2、B3在第4～5s間分別發(fā)起與B4、B5、B6的通信。圖4是實(shí)驗(yàn)結(jié)果。PS-L和FairNet策略僅根據(jù)鏈路狀態(tài)計(jì)算租戶權(quán)重，L上的帶寬分配未發(fā)生變化；PS-N是以整個(gè)網(wǎng)絡(luò)的狀態(tài)計(jì)算租戶權(quán)重的，Bi（i=1，…，6）產(chǎn)生流量后分走了一部分權(quán)重，導(dǎo)致租戶B在L上的權(quán)重變小，租戶A的帶寬增加。一個(gè)租戶內(nèi)部通信的變化影響另外一個(gè)租戶的服務(wù)質(zhì)量，顯然是不合理的。

圖3 不同通信模式場景的實(shí)驗(yàn)結(jié)果

圖4 租戶B內(nèi)部通信變化對算法的影響

最后，測量虛擬機(jī)權(quán)重對算法的影響。在1對多通信模式下，N=8，除B0外的虛擬機(jī)保證帶寬為0.1Gb／s，其他參數(shù)不變。實(shí)驗(yàn)過程中，將B0的保證帶寬從0.1Gb／s增加到0.8Gb／s，實(shí)驗(yàn)結(jié)果如圖5所示。PS-L和PS-N在本場景中實(shí)驗(yàn)結(jié)果相同，被歸并為一條曲線。從實(shí)驗(yàn)結(jié)果可以得出結(jié)論：PS-L／PS-N獲得的權(quán)重隨保證帶寬的增加線性增加，F(xiàn)airNet策略與PS-L／PS-N的差距隨著B0保證帶寬的增加越來越小，只有當(dāng)發(fā)送端、接收端的權(quán)重接近時(shí)，3種算法的結(jié)果才接近。產(chǎn)生此趨勢是因?yàn)镕airNet策略考慮了發(fā)送端、接收端帶寬需求不平衡的影響，而PS-L／PS-N只是簡單地將權(quán)重相加。此外，從圖5可以看出，β決定了虛擬機(jī)帶寬中保證帶寬外的部分對租戶權(quán)重的影響。

圖5 租戶B帶寬隨虛擬機(jī)B0保證帶寬的變化趨勢

實(shí)驗(yàn)結(jié)果表明，相比于其他算法，F(xiàn)airNet策略更合理地估計(jì)了租戶在鏈路上的權(quán)重，能夠提供更好的鏈路公平性。同時(shí)，在使用FairNet策略的系統(tǒng)中，租戶應(yīng)該充分估計(jì)業(yè)務(wù)的通信模式和通信需求，合理地選擇虛擬機(jī)配置，以避免選擇不當(dāng)而造成的資源浪費(fèi)。

3.2 主機(jī)帶寬保證實(shí)驗(yàn)

實(shí)驗(yàn)采用變形的1對多模式，N=1，不同的是，虛擬機(jī)A0和B0位于同一臺主機(jī)上。A0、A1的保證帶寬為0.3Gb／s，B0、B1的保證帶寬為0.6Gb／s，L的帶寬為10Gb／s。B0以固定的速度發(fā)送數(shù)據(jù)，而A0則盡可能快地發(fā)送數(shù)據(jù)。租戶A、B的帶寬完全取決于主機(jī)上的分配情況。實(shí)驗(yàn)結(jié)果如圖6所示，在B0的發(fā)送速度未超過保證帶寬之前，帶寬得到了保證，而超過0.6Gb／s后，與A0產(chǎn)生競爭。參數(shù)α調(diào)節(jié)虛擬機(jī)保證帶寬外部分帶寬占權(quán)重的比重，對實(shí)驗(yàn)結(jié)果整體趨勢影響不大。FairNet策略能夠確保虛擬機(jī)的保證帶寬，同時(shí)盡可能地最大化帶寬利用率。

圖6 租戶B帶寬與發(fā)送速度的關(guān)系

圖7 小規(guī)模場景示意圖和實(shí)驗(yàn)結(jié)果

3.3 小規(guī)模場景實(shí)驗(yàn)

最后，是一個(gè)小規(guī)模場景的實(shí)驗(yàn)。在該場景中，如圖7a所示，租戶A的虛擬機(jī)Ai和Ai+4（i=1，2，3，4）之間產(chǎn)生雙向通信，租戶B的虛擬機(jī)Bi和Bj（i，j=1，…，8）之間產(chǎn)生雙向通信。一個(gè)完美的帶寬分配策略應(yīng)該在任何情況下使得A和B獲得的帶寬相等。實(shí)驗(yàn)中，測量了3種配置下的帶寬分配情況，3種配置分別為：①所有鏈路均為1Gb／s；②核心鏈路10Gb／s，其他鏈路1Gb／s；③核心、匯聚鏈路10Gb／s，其他鏈路1Gb／s。實(shí)驗(yàn)結(jié)果如圖7b、圖7c、圖7d所示，其中FN-0、FN-1分別代表FairNet（γ=0）和FairNet（γ=1）），PS-N在3種情況下都獲得了最好的網(wǎng)絡(luò)公平性，而FairNet策略僅次于PS-N，優(yōu)于其他算法?？紤]到PS-N利用了整個(gè)網(wǎng)絡(luò)的網(wǎng)絡(luò)流信息，而FairNet策略僅僅利用了鏈路的局部信息，這樣的結(jié)果可以接受。同時(shí)，越是上層的鏈路發(fā)生擁塞，對公平性的影響越大，在真實(shí)系統(tǒng)中，應(yīng)該盡量地保障上層交換機(jī)鏈路的容量。

4 結(jié) 論

本文主要研究了多租戶云的內(nèi)部網(wǎng)絡(luò)共享問題，提出一種帶寬分配策略FairNet策略，它為虛擬機(jī)增加了2個(gè)帶寬相關(guān)的參數(shù)，分別是保證帶寬和最大帶寬，并以此為基礎(chǔ)分配帶寬。在主機(jī)上，F(xiàn)airNet策略通過限速器限制虛擬機(jī)的速度不超過最大帶寬，通過基于權(quán)重的調(diào)度器保證虛擬機(jī)至少能夠獲得與其保證帶寬參數(shù)相等的帶寬。在鏈路上，F(xiàn)airNet策略以發(fā)送端、接收端的帶寬需求的最小值作為主要部分計(jì)算權(quán)重，并按照權(quán)重分配帶寬。實(shí)驗(yàn)結(jié)果表明，F(xiàn)airNet策略考慮了租戶在發(fā)送端和接收端帶寬需求不平等的影響，能夠適應(yīng)不同的網(wǎng)絡(luò)通信模式，達(dá)到了較好的鏈路和網(wǎng)絡(luò)公平性。

［1］ LAM V T，RADHAKRISHNAN S，PAN Rong， et al.Netshare and stochastic netshare：predictable bandwidth allocation for data centers ［J］.ACM SIGCOMM Computer Communication Review，2012，42（3）：5-11.

［2］ BALLANI H，COSTA P，KARAGIANNIS T，et al.Towards predictable datacenter networks ［J］.ACM SIGCOMM Computer Communication Review，2011，41（4）：242-253.

［3］ GUO Chuanxiong，LU Guohan，WANG H J，et al.SecondNet： a data center network virtualization architecture with bandwidth guarantees ［C］∥Proceedings of the 6th International Conference on Emerging Networking Experiments and Technologies.New York，USA：ACM，2010：1-12.

［4］ XIE Di，DING Ning，HU Y C，et al.The only constant is change： incorporating time-varying network reservations in data centers ［J］.ACM SIGCOMM Computer Communication Review，2012，42（4）：199-210.

［5］ PAREKH A K，GALLAGER R G.A generalized processor sharing approach to flow control in integrated services networks：the single-node case［J］.IEEE／ACM Transactions on Networking，1993，1（3）：344-357.

［6］ DEMERS A，KESHAV S，SHENKER S.Analysis and simulation of a fair queueing algorithm ［J］.ACM SIGCOMM Computer Communication Review，1989，19（4）：1-12.

［7］ BENNETT J C R，ZHANG Hui.WF2Q：worst-case fair weighted fair queueing ［C］∥Proceedings of the 15th Annual Joint Conference of the IEEE Computer and Communications Societies Conference on the Conference on Computer Communications.Washington，DC，USA：IEEE Computer Society，1996：120-128.

［8］ SHIEH A，KANDULA S，GREENBERG A，et al.Sharing the data center network ［C］∥Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation.Berkeley，CA，USA：USENIX Association，2011：23-23.

［9］ KABBANI A，ALIZADEH M，YASUDA M，et al.AF-QCN： approximate fairness with quantized congestion notification for multi-tenanted data centers［C］∥Proceedings of the 18th Annual Symposium on High Performance Interconnects.Washington，DC，USA：IEEE Computer Society，2010：58-65.

［10］RODRIGUES H，SANTOS J R，TURNER Y，et al.Gatekeeper：supporting bandwidth guarantees for multi-tenant datacenter networks［C］∥Proceedings of the 3rd Conference on I／O Virtualization.Berkeley，CA，USA：USENIX Association，2011：6.

［11］POPA L，KUMAR G，CHOWDHURY M，et al.FairCloud：sharing the network in cloud computing［J］.ACM SIGCOMM Computer Communication Review，2012，42（4）：187-198.

［12］DEVIK M D A.HTB home［EB／OL］.（2003-07-12）［2014-02-19］.http：∥luxik.cdi.cz／～devik／qos／htb／.

［13］FLOYD S，JACOBSON V.Link-sharing and resource management models for packet networks［J］.IEEE／ACM Transactions on Networking，1995，3（4）：365-386.

［14］ NS-3Consortium.NS-3 ［EB／OL］.（2013-05-12）［2014-02-19］.http：∥www.nsnam.org／.