鄭鵬飛，尤佳莉，王勁林，曾學文

（1.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，100190，北京；2.中國科學院大學，100049，北京）

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

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

文獻［11］指出，多租戶云的內部網絡共享問題有3個無法同時滿足的目標，分別是最小保證、公平分配和最大利用。本文提出一種平衡3個目標的FairNet策略。該策略由主機和鏈路的帶寬分配算法組成，分別在主機上實現了最小保證和最大利用，在鏈路上實現了公平分配和最大利用。仿真實驗結果表明，相比于其他算法，FairNet策略能更好地適應不同的網絡通信模式，同時獲得較好的鏈路和網絡公平性。

1 問題建模

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

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

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

此外，在實際網絡中，一個租戶的帶寬需求矩陣很難進行估計和測量，這導致公平分配的公平性無法準確定義。已有算法普遍利用權重代替帶寬需求矩陣定義公平分配，即目標①變?yōu)?/p>

2 算法描述

本文提出一種多租戶云的內部網絡共享策略——FairNet策略，由主機和鏈路的帶寬分配算法組成。

2.1 主機帶寬分配算法

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

定義虛擬機為

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

主機h∈VH進行資源分配時需要滿足條件

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

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

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

圖1 虛擬機流量控制算法示意圖

2.2 鏈路帶寬分配算法

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

每一個虛擬機在鏈路上的權重為

式中：β∈［0，1］。以式（11）取代式（9）計算虛擬機的權重，因為式（9）計算的權重可能會發(fā)生變化，而在相關鏈路上同步權重變化代價很大。這樣，一個虛擬機集合I的權重為

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

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

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

3 實驗與結果分析

3.1 不同通信模式的實驗

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

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

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

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

接下來將評估租戶內部通信變化和虛擬機權重的影響。由于1對多模式每個租戶僅有1個發(fā)送端，容易觀察實驗結果，因此實驗采用1對多模式。

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

圖3 不同通信模式場景的實驗結果

圖4 租戶B內部通信變化對算法的影響

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

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

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

3.2 主機帶寬保證實驗

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

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

圖7 小規(guī)模場景示意圖和實驗結果

3.3 小規(guī)模場景實驗

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

4 結 論

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

［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／.