基于共享資源量的動態多資源公平分配策略

張瀟璐，劉曦，李偉東，張學杰

（云南大學信息學院，云南 昆明 650091）

基于共享資源量的動態多資源公平分配策略

張瀟璐，劉曦，李偉東，張學杰

（云南大學信息學院，云南 昆明 650091）

針對云計算共享系統中多資源分配問題，提出一種基于共享資源量的動態多資源公平分配策略。該策略根據不同用戶資源需求和共享資源量建立一個線性規劃模型，同時證明該模型滿足公平分配的4個重要屬性：動態帕累托最優、激勵共享、動態無嫉妒性和防止策略性操作，而且給出一種改進的動態多資源公平分配算法來提高算法運行效率。實驗結果表明，所提動態多資源公平分配策略能夠在滿足任務資源需求的同時，盡可能保證公平分配下最大化占優資源份額，并且改進的分配算法能夠有效地提高資源的分配效率。

云計算；多資源公平分配；占優資源；共享資源量

1 引言

云計算共享系統通過虛擬化技術將多種計算資源進行整合，實現資源的共享功能，為資源的統一管理和調度提供技術保證和條件。對云共享系統而言，資源分配調度是一個至關重要的組件。云共享系統根據當前各個虛擬機節點的資源需求，對資源進行合理分配，使虛擬機節點能夠有足夠的資源完成計算任務并保證用戶之間公平有效地共享資源。因此，如何有效地將有限資源分配給各虛擬機節點，使云共享系統滿足任務資源需求的同時兼顧資源分配的公平和效率是需要解決的關鍵問題。

目前，很多工作對資源公平分配問題進行了深入而廣泛的研究。最常用的分配策略是最大最小公平模型（max-min fairness）[1]，最早用于控制網絡流量，以實現公平分配網絡帶寬。最大最小公平模型的基本思想是使資源分配的最小分配量盡可能最大化，防止任何網絡流被“餓死”，同時在一定程度上盡可能增加每個流的速率。最大最小公平模型被認為是一種很好權衡公平性和有效性的自由分配策略，由此衍生出的大量算法被應用于各種資源分配上，包括網絡帶寬、CPU、內存等，但這些公平分配的研究主要集中在單一資源類型。

在云共享系統中，每個虛擬機節點的資源都是多維的，加上用戶任務資源需求的多樣性，相對于單一資源的分配，多資源類型的分配更難做到完全的公平性。另外，用戶為了得到更多資源，可能通過需求欺騙、惡意占用等手段破壞資源分配的公平性，因此，多資源的公平合理分配顯得尤為重要。已有的多資源公平分配研究成果中，DRF（DRF,dominant resource fairness）機制[2]被廣泛應用到Hadoop Yarn[3]和Mesos[4]系統中。DRF計算每個用戶每種資源的分配數量與資源總量的比值，所有比值中的最大值為該用戶的占優資源份額（dominant share），與其相對應的資源為該用戶的占優資源（dominant resource）。DRF機制的基本思想是最大化所有用戶占優資源份額中的最小者，從而將多資源分配問題轉化為單資源分配問題。該機制擴展了最大最小公平模型，使其能夠在多種不同資源并存情況下保證分配的公平性。然而，DRF機制的提出是基于每個用戶對資源池共享相同資源量的假設，在實際情況中，每個用戶對資源的共享量可能不同，且共享量多的用戶希望得到更多的資源。因此，文獻[2]又提出加權DRF機制（weighted DRF），該機制對每個用戶都關聯一個共享資源量（權值向量），最大化用戶得到的占優資源份額與其共享資源量的比值中最小值來實現資源的公平分配。如果所有用戶的共享資源量相同，則加權DRF機制轉換為DRF機制。

加權 DRF機制解決基于不同共享資源量的公平分配問題，但在實際云共享系統中，用戶會在不同的時刻進入系統，用戶帶來的共享資源量使系統中可分配的資源總量發生動態變化，資源分配機制應該根據用戶資源需求對資源分配情況進行重新調整，確保盡可能公平分配，而靜態分配機制無法解決由用戶動態性帶來的資源分配公平性和效率問題。文獻[5]針對資源分配的動態性做出較大改進，允許用戶隨時進入系統但不離開的情形，然而研究者也是基于用戶進入云共享系統時帶來相同資源份額的假設，并未考慮實際用戶對資源共享的差異性所帶來的公平性問題，并且在資源分配過程中采用注水（water filling）算法[5]，該算法的運行時間復雜度是關于輸入長度的偽多項式函數，操作性和用戶資源需求與資源公平分配適應性比較差，從而導致比較低的資源分配效率。

針對上述問題，本文對動態情形下，用戶的資源需求以及用戶動態進入系統時所共享資源量的差異性帶來的公平性和資源利用率問題做進一步綜合考慮，面向云共享系統，提出基于共享資源量的動態多資源公平分配策略（DMFA-SRQ, dynamic multi-resources fair allocation based on shared resource quantity）。該策略基于用戶資源需求和共享資源量，重新定義動態情形下占優資源份額，給出一個線性規劃模型，在滿足用戶資源需求同時，盡可能實現占優資源的最大公平性分配，并且證明該模型滿足公平分配的4個重要屬性：動態帕累托最優（DPO, dynamic Pareto optimality）、激勵共享（SI,sharing incentive）、動態無嫉妒性（DEF, dynamic envy freeness）和防止策略性操作（SP, strategy proofness）；提出改進的動態多資源公平分配算法使算法運行時間復雜度減小到Ο ( n2logn)（n為系統中用戶數）。理論和實驗表明，本文提出的方法解決了動態情形下基于不同共享資源量的多資源公平分配問題，且有效提高了算法的運行效率。

2 相關工作

近年來，研究者們提出了各種各樣有關公平性的資源分配算法。在單一資源類型的公平分配研究中，文獻[6～9]研究 CPU時間、鏈路帶寬資源的公平分配策略，利用“max-min fairness”思想，最大化每個用戶分配到的最小資源，保證多數用戶的資源需求得到滿足，實現公平性分配。文獻[10,11]研究在2個用戶利益之間尋求資源分配平衡機制，提出“proportional fairness”方法；Zukerman等[12]提出針對單一資源在公平和效率之間進行折中的效用評估算法；Lan等[13]基于公平分配理論屬性，提出一種資源分配機制，并為公平性的度量提供了準則。

在多資源公平分配研究中，Ghodsi等[2]最早系統地研究云計算系統中多資源公平分配問題，基于用戶相同共享資源量的假設，提出一種DRF機制。該機制顯示出諸多令人滿意的公平屬性，吸引了大量研究者的關注，并得到了廣泛推廣。Dolev等[14]提出基于瓶頸資源的公平分配（BBF, bottleneck based fairness）算法，并證明BBF滿足激勵共享和無嫉妒性2種公平屬性；Gutman等[15]考慮DRF在多個效用模型下的通用性，并且能夠在多項式時間內解決BBF公平分配問題；Bhattacharya[16]重新定義 DRF以此來支持多層次資源分配；Wang等[17]提出改進 DRF機制，使其能夠適用于異構云計算環境；Joe-Wong等[18]推廣 DRF，量化并使其成為一個一體化的框架，以權衡分配公平和分配效率；Psomans等[19]研究在多個計算節點上對離散任務的多資源公平分配方法；Parks等[20]用多種方法擴展DRF機制，適用于某些資源的零需求、不可劃分任務和不同權重等情形。

以上工作都是基于系統中所有用戶資源需求的靜態分配，與目前云共享系統中用戶隨時進入和退出的動態性有本質的不同，而且資源分配過程中并沒有考慮到歷史分配信息。在動態情形下，Zeldes等[21]提出基于資源瓶頸和全局屬性的在線公平分配機制；文獻[22,23]分別在靜態和動態情形下研究基于用戶有限任務請求數量的多資源公平分配機制，但未解決在用戶動態進入云共享系統時用戶資源請求和共享資源量的差異性對多資源公平分配的影響。Kash等[5]雖提出基于用戶相同共享資源量的多資源公平分配策略DDRF，但這種策略并沒有考慮用戶共享資源量的差異性所帶來的實際資源分配的公平性和效率問題。

綜上，雖然目前很多工作在多資源公平分配問題上取得了一定進展，但對用戶動態性以及資源需求和共享資源量差異性帶來的分配公平性和資源利用率問題缺乏進一步考慮，因此，本文引入一種基于共享資源量的動態多資源公平分配策略DMFA-SRQ，給出一個線性規劃分配模型，并提出一種改進的動態多資源公平分配算法。

3 問題描述及相關定義

在云共享系統中，用戶請求是由具有不同資源配置的虛擬機進行響應，為方便以下討論，這里做個假定：用戶任務的資源請求可認為是虛擬機資源請求，用戶任務的資源分配過程即虛擬機資源部署過程。

假定云共享系統中資源池包含m種硬件資源，如CPU、內存、磁盤、網絡帶寬等。令 R = {1,2,…,m}表示資源種類集合， U= {1,2,…, n}表示用戶集合。用戶i的資源需求向量為 Di=(Di1,… , Dim)，其中，Dij表示用戶i的任務對資源j的需求量占整個資源池中資源j總量的比例，且 Dij> 0。對Di做歸一化

令 wi表示用戶i對資源池中每種資源的共享資源量，且當系統中有k個用戶時，k ∈ {1,… ,n}，令 xik表示用戶i分配得到的占優資源份額數，即可執行的任務數。定義用戶i的占優資源份額（dominant share）為

根據占優資源定義，上式可簡化為

在動態情形下，假定用戶在不同時刻順序到達，即用戶k在用戶k?1之后到達，且用戶（i>k）的資源需求di>k未知。用戶進入系統后不會離開，并且每個用戶任務所需資源量不會隨時間發生改變。當系統中有k個用戶時，得到一個動態多資源公平分配方案Ak=(Ak,… ,,… ,)， 其 中 ，= (,…,

在資源j上分配得到的資源數量，滿足以下公式

并且對任意用戶i， i≤k? 1，k≥2，其分配結果是一個不可逆過程，即≥。對所有用戶i， 給定一個分配 Ak，則在虛擬機上被調度執行的最大

ij任務數按如下公式計算

i + ij對任意資源 j， j∈R，若存在這樣一個y，使=d y成立，則稱 Ak為無浪費分配方案。ij ij

本文設計一種動態情形下無浪費資源分配方案：基于共享資源量的動態多資源公平分配策略（DMFA-SRQ），目標是當系統中存在k個用戶時，最大化占優資源份額kM ，從而得到最大化的占優資源份額數，并且盡可能保證資源分配的公平性。因此，DMFA-SRQ策略可形式化為

該線性規劃模型中第一個約束條件是盡可能保證占優資源的公平分配，同時，共享資源量越多的用戶分配得到的占優資源份額數就越多。另外，還給出在多資源分配過程中其他2個約束條件，即當系統中有k個用戶時，對任意用戶分配得到的占優資源份額數不小于系統中有k?1個用戶時的分配情況，滿足分配的不可逆性；當系統中有k個用戶時，系統可以分配的資源量最多為

圖1舉例說明DMFA-SRQ策略的資源分配情況。假設系統中共有3個用戶，分別順序進入系統。每個用戶的資源需求向量和共享資源量分別為當系統中只有用戶1時，分配得到的占優資源份額；當系統中

在靜態分配情形下，根據文獻[15,21]以及式(4)的線性規劃方程組，可通過式(5)求得靜態最優解

接下來提出一種快速算法 DMFA-SRQ以解決動態分配情形下kM 最大化問題。

4 DMFA-SRQ策略的公平性分析

無論是在云共享系統[2,19]，還是在經濟學[24,25]中，資源分配的效率和公平性被廣泛認為是最重要的屬性，也是衡量一個公平分配機制優劣的判斷標準。文獻[5]引入在動態情形下多資源公平分配機制所滿足的4個重要屬性：動態帕累托最優、激勵共享、動態無嫉妒性、防止策略性操作。本文在此基礎上，針對動態情形下用戶資源需求以及用戶共享資源量的差異所提出的公平分配機制應滿足的4個重要屬性做進一步討論。

1) 動態帕累托最優

對于所有用戶的可行分配方案 Ak，其中任意一個用戶i的資源分配方案，有() >()成立， 那么將存在一個用戶h，使 N () <()成立。

h

2) 激勵共享

如果一種動態公平分配機制系統中有k個用戶時，對任意用戶i，i∈U ，i≤k，有 N (Ak)≥ N( w )

i i i i成立，則認為該機制滿足SI屬性。

3) 動態無嫉妒性

在動態公平分配機制中，如果用戶i嫉妒用戶h，i, h∈U，說明用戶h是在用戶i之前進入系統，并且自用戶i進入系統之后用戶h未再被分配資源，則該機制滿足DEF屬性。即當系統中有k個用戶時，如果成立，則有h

4) 防止策略性操作

用戶不能通過謊報資源需求來提高自己的占優資源份額，此屬性滿足需求不可欺騙性。令為用戶i謊報虛假資源di，而其他用戶都提交真實資源需求情況下得到的分配方案，則有i≤k成立。

圖1 DMFA-SRQ策略的資源分配結果

DPO屬性表明當用戶資源分配已經達到飽和時，它可能在影響其他用戶分配的前提下，增加自己的占優資源份額數。SI屬性確保用戶最終分配得到的占優資源份額數不少于用戶帶來的共享資源量，并且用戶帶來的共享資源量越多，分配到的資源就越多。DEF屬性說明如果一種動態分配機制是有嫉妒性的，則用戶會嫉妒比其早進入系統且分配到較多占優資源份額的用戶。SP屬性規定用戶不能通過謊報自己的需求來獲得更多額外資源。

引理1 當系統中有k個用戶時，k ∈{1,…, n}，對用戶i，i∈U ，i≤k，=max{Mkw, xk?1}。

i i

證明 考慮系統中有k個用戶時，根據式(4)中前 2個 約束 條 件≥Mkw， xk≥ xk?1，得 到i i i

證明 利用數學歸納法證明。當i>k，h>k時，== 0。假設當系統中有k?1個用戶存在時， k ∈ {h, … , n}，不等式成立。當系統中存在k個用戶時，根據引理1及得出即證畢。

h則有根據h

從引理1可以看出，對系統中每個用戶而言，不同資源需求的用戶根據 DMFA-SRQ策略分配得到的占優資源份額隨著更多用戶在不同時刻進入系統后呈現單調非遞減性。引理2表明用戶得到的占優資源份額隨著用戶進入系統的先后順序呈現單調非遞增性。引理3則表示當系統中有k個用戶時，如果用戶h的占優資源份額大于用戶i，說明用戶h比用戶i更早進入系統，且自用戶i進入系統后，用戶h未被再分配資源，因此，用戶i會嫉妒用戶h，這與動態無嫉妒屬性（DEF）所描述的含義相同。下面根據以上的引理，驗證 DMFA-SRQ策略滿足4個重要屬性：動態帕累托最優、激勵共享、動態無嫉妒性、防止策略性操作。

定理1 當系統中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足DPO屬性。

證明 當系統中有k個用戶時，至少存在一種資源 j(j∈R)和一個最優解 Mk，使式(4)中第3個約束條件成立。否則，如果存在一個不滿足分配方案的用戶i，在不影響其他用戶分配情況下，提高自己分配到的占優資源份額數，即增加一個很小的量+ε，ε>0，使 Mk值也相應增加，與 Mk是問題最優解相矛盾，因此，DMFA-SRQ滿足DPO屬性。

定理2 當系統中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足SI屬性。

證明 考慮系統中只有一個用戶時，根據式(4)中第1個約束條件，有=w1，M1=1，則可以得到≥ M1w ≥ w。接下來，利用數學歸納法證明

1 1當系統中有k個用戶時， k ∈ {2,…, n}，對任意用戶i，i∈U ，i≤k，則有)≥wi)，即≥wi。

定理3 當系統中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足DEF屬性。

證明 當系統中有k個用戶時，如果對任意用戶i, h≤k，用戶i嫉妒用戶h，即根據引理 3，則有由上述不等式可以推出否則，得出以下不等式

其中，j*為用戶i的占優資源，由式(6)可知用戶i得到比用戶h更多的占優資源份額，與條件矛盾。因此，由及引理3可以推出DMFA- SRQ滿足DEF屬性。證畢。

接下來，證明DMFA-SRQ策略滿足SP屬性，首先，給出引理 4。當系統中有k個用戶時，k ∈ {1,… , n}，假設用戶i，i∈U，謊報不真實的資源需求向量，則至少存在一個用戶t，t∈ {i, … ,k}，自加入系統之后使用戶i獲得比較多的優勢份額數量。此時，對任意其他真實需求用戶h，在不真實資源需求環境下分配得到的占優資源份額數表示為，h≤k，同時， M?k為求解線性規劃方程式(4)得到的最優解。

證明 考慮以下2種情況。

定理4 當系統中有k個用戶時，k ∈{1,… ,n}，DMFA-SRQ策略滿足SP屬性。

證明 利用反證法證明。當系統中有k個用戶時，用戶i謊報不真實資源需求，當第t個用戶進入系統時，用戶i分配得到較多的優勢份額數，則存在一種資源j，j∈R，使分配滿足動態帕累托最優性質，并根據引理4可以推出以下不等式

不等式(7)與式(4)中第3個約束條件相矛盾，因此，DMFA-SRQ滿足SP屬性。證畢。

5 DMFA-SRQ算法

Water filling算法[5]是一種在動態情形下實現資源最大最小化公平分配的經典算法，但代價是算法運行時間過長。本文基于第3節中提出的線性規劃模型，設計了一個更為快速的Ο ( n2logn)多項式時間復雜度算法，即用基于共享資源量的動態多資源公平分配算法改進求解最優分配方案的算法運行效率問題。

該算法基于本文定義的最大化 Mk以及約束條件，尋找一個用戶τ對應的vτ，使如果> vτ成立, 則否則從而確定，并最終得到該算法主要思想如下。

1) 當系統中有k個用戶時，對k?1個 xik?1值進行非遞增排序（i

3) 根據式(4)線性規劃方程組中前2個約束條件以及引理 1，當系統中有k個用戶時，每個用戶i被分配執行的任務數為，即從而最終得到用戶i在資源 j上的分配方案。DMFA-SRQ算法的操作過程如算法1所示。

算法1 DMFA-SRQ算法

1) 輸入：Demanddi,1≤i≤k

4)k←2;

7)

8) else, do

10)

12)

14) goto 10);

15) else, do

17) goto 10);

18) end if;

19) end while;

21)

24)k ←k+1;

25) end while

當系統中有k個用戶時，本文提出的DMFA-SRQ 算法利用二分法思想確定vτ，并得到和最終分配方案(,… ,xk)，算法的運行時間取k決于求解vτ值的迭代次數，因此，該算法的時間復雜度為Ο ( klogk)。當系統中共有n個用戶時，整體算法運行時間為

6 實驗評估

實驗將采用Google 集群中真實計算任務負載數據集[26]中500個任務類型文件中的143 601 184個任務運行所需的CPU和Memory資源作為本文實驗中用戶資源請求。實驗從該數據集中隨機選取20、100、500個用戶，對每個用戶的資源需求向量＜CPU,Memory>進行歸一化處理，并隨機設置每個用戶的共享資源量wi，使其滿足其中，100、500個用戶的資源需求分布如圖 2所示。本文對所提DMFA-SRQ算法與加權DRF算法進行仿真模擬，實現2種算法的資源分配，并基于最小占優資源份額、占優資源份額數和、資源利用率3個最大化目標分別在不同用戶數下各執行1 000次取均值得到2種算法的實驗結果，以此來評估 DMFA- SRQ算法性能。

圖2 用戶資源需求分布

圖3和圖4分別給出了在100個、500個用戶下，用戶共享資源量對用戶資源分配的影響。實驗設置用戶隨機動態進入系統并隨機設置其共享資源量 wi，滿足

采樣點均勻選取其中 20個用戶分配得到的占優資源份額數，并對wi進行升序排列。從圖3和圖4中可以看出，用戶共享資源量與占優資源份額數呈現單調非遞減性，即用戶共享資源量 wi越多，其分配得到的占優資源份額數就越多。該實驗結果表明，DMFA-SRQ算法保證資源分配的公平性，并且共享資源量越多的用戶，分配得到的資源也越多。

圖3 100個用戶下占優資源份額數基于wi的變化

圖4 500個用戶下占優資源份額數基于wi的變化

DMFA-SRQ算法目標是在盡可能保持公平分配情況下，最大化占優資源份額，因此，為進一步驗證所提出的 DMFA-SRQ算法能夠保證資源分配的公平性和分配效率，本文基于最小占優資源份額、占優資源份額數和、資源利用率3個最大化目標與靜態情形下加權 DRF算法進行對比分析。

1) 最小占優資源份額最大化

i驗分配結果如圖5所示。

圖5 最小占優資源份額

從圖5中可以看出，動態情形下DMFA-SRQ算法得到的占優資源份額低于靜態情形下加權DRF算法得到的結果，這主要是因為動態情形下用戶資源需求未知，分配過程中無法比較所有用戶的最小占優資源份額，而且動態分配需要滿足分配的不可逆性條件。通過實驗結果也可以看出，基于不同共享資源量的 DMFA-SRQ分配算法在不違背公平性原則的情況下，實現動態情形下最小占優資源份額最大化分配目標，也進一步驗證了該算法滿足SI屬性。

2) 占優資源份額數和最大化

在經濟學中，占優資源份額數和是衡量策略效率的一個重要指標[5]。當系統中有k個用戶時，給出占優資源份額數和的定義為圖 6 給出DMFA-SRQ算法與加權DRF算法的占優資源份額數和的對比。

圖6 占優資源份額數和

從圖6中可以看出，動態情形下的DMFA-SRQ算法分配得到的占優資源份額數和與靜態加權DRF算法結果相接近，說明 DMFA-SRQ算法在滿足式(4)線性規劃方程組中的約束條件下，能夠實現動態情形下所有用戶占優資源份額最大化分配目標。

3) 資源利用率最大化

在云共享系統中，資源利用率是衡量分配策略效率的重要標準之一[14]。因此，本文測試DMFA-SRQ算法下的CPU和Memory資源利用率，并與加權DRF算法進行比較。圖7和圖8分別給出了2種算法的CPU和Memory資源利用率結果。

從圖7和圖8中2種算法資源利用率的對比可以看出，DMFA-SRQ算法下的資源利用率值與靜態情形下的加權 DRF算法結果相接近，且用戶數越多，2種算法的資源利用率越接近。實驗結果驗證本文所提算法的資源利用率并沒有因為動態情形下用戶資源需求未知以及資源共享總量的差異而有所降低，說明該策略既保證資源分配的公平性，又兼顧到分配效率。

圖7 CPU資源利用率

圖8 Memory資源利用率

7 結束語

本文針對云計算共享系統中虛擬化資源分配的公平性問題，基于用戶資源需求和共享資源量，提出基于共享資源量的動態多資源公平分配策略。該策略建立一個線性規劃模型來實現對占優資源的盡可能公平分配，并證明該模型滿足公平分配的4個重要屬性：動態帕累托最優、激勵共享、動態無嫉妒性、防止策略性操作，此外，本文還提出基于共享資源量的動態多資源公平分配算法來改進算法運行效率。而且，本文所提出的策略和算法不僅可以應用于云共享系統資源的動態分配，也適用于WLAN和WSN等領域的網絡帶寬分配。最后，實驗基于最小占優資源份額、占優資源份額數和、資源利用率最大化目標與加權 DRF算法進行比較，進一步表明本文所提DMFA-SRQ策略能夠有效地保證動態情形下多用戶多資源分配的公平性和資源利用率。但由于云計算環境的異構性以及資源分布在多服務器等復雜情況，還可能面臨更為復雜的多資源分配問題，因此，對異構環境下的動態多用戶多資源公平分配問題將是下一步的研究工作。

[1] Max-min fairness[EB/OL]. http：//en.wikipedia.org/wiki/Max-min_fairness.

[2] GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant resource fairness： fair allocation of multiple resource types[C]//The 8th USENIX Conference on Networked Systems Design and Implementation. c2011： 24.

[3] Hadoop[EB/OL]. http：//hadoop.apache.org/.

[4] Mesos[EB/OL]. http：//mesos.apache.org/.

[5] KASH I, PROCACCIA A D, SHAH N. No agent left behind： dynamic fair division of multiple resources[J]. Journal of Artificial Intelligence Research, 2013(1)： 351-358.

[6] JAIN R, CHARNY A, CLARK D. Congestion control with explicit rate indication[C]// 1995 IEEE International Conference on Communications.c1995： 1954-1963.

[7] GOYAL P, VIN H M, CHEN H. Start-time fair queueing： a scheduling algorithm for integrated services packet switching networks[C]//ACM Sigcomm Computer Communication Review. c1996： 157-168.

[8] STOICA I, SHENKER S, ZHANG H. Core-stateless fair queueing：achieving approximately fair bandwidth allocations in high speed networks[C]//The ACM Sigcom. c1998： 118-130.

[9] CAPRITA B, CHAN W C, NIEH J, et al. Group ratio round-robin： O(1)proportional share scheduling for uniprocessor and multiprocessor systems[C]//Usenix Technical Conference. c2005： 337-352.

[10] KELLY F. Charging and rate control for elastic traffic[J]. European Transactions on Telecommunications, 1997, 8(1)：33-37.

[11] MASSOULIE L, ROBERTS J. Bandwidth sharing： objectives and algorithms[C]//18th Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '99). New York. c1999： 1395-1403.

[12] ZUKERMAN M, TAN L, WANG H, et al. Efficiency-fairness tradeoff in telecommunications networks [J]. IEEE Communications Letters,2005, 9(7)：643 - 645.

[13] LAN B T, KAO D, CHIANG M, et al. An axiomatic theory of fairness in network resource allocation[C]//IEEE Infocom. c2010： 1-9.

[14] DOLEV D, FEITELSON D G, HALPERN J Y, et al. No justified complaints： on fair sharing of multiple resources[C]//The 3rd Innovations in Theoretical Computer Science Conference. c2012： 68-75.

[15] GUTMAN A, NISAN A. Fair allocation without trade[C]//The 11th International Conference on Autonomous Agents and Multiagent Systems. c2012： 719-728.

[16] BHATTACHARYA A A, CULLER D, FRIEDMAN E, et al. Hierarchical scheduling for diverse datacenter workloads[C]//The 4th Symposium on Cloud Computing (SOCC’13). c2013：1-15.

[17] WANG W, LIANG B, LI B. Multi-resource fair allocation in heterogeneous cloud computing systems[J]. Parallel and Distributed Systems,2015, 26(10)： 2822-2835.

[18] JOE-WONG C, SEN S, LAN T, et al. Multiresource allocation： fairness-efficiency tradeoffs in a unifying framework[J]. IEEE/ACM Transactions on Networking, 2013, 21(6)： 1785-1798.

[19] PSOMAS C A, SCHWARTZ J. Beyond beyond dominant resource fairness： Indivisible resource allocation in clusters[R]. Technology Report, Berkeley, 2013.

[20] PARKES D C, PROCACCIA A D, SHAH N. Beyond dominant resource fairness： extensions, limitations, and indivisibilities[J]. ACM Transactions on Economics and Computation, 2015, 3(1).

[21] ZELDES Y, G.FEITELSON D. On-line fair allocations based on bottlenecks and global priorities[C]//The 4th ACM/SPEC International Conference on Performance Engineering. c2013： 229-240.

[22] LI W D, LIU X, ZHANG X L, et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems[J]. Eprint Arxiv, 2014.

[23] LI W, LIU X, ZHANG X, et al. Dynamic fair allocation of multiple resources with bounded number of tasks in cloud computing systems[J]. Multiagent and Grid Systems, 2016, 11(4)： 245-257.

[24] BARBANEL J B, BRAMS S J. Two-person cake-cutting： the optimal number of cuts[J]. Mathematical Inteuigencer, 2011, 36(3)： 23-35.

[25] LI J, XUE J. Egalitarian division under leontief preferences [J]. Economic Theory, 2013, 54(3)： 597-622.

[26] WILES J, REISS C. Google cluster data 2011_2[EB/OL]. https：//code.google.com/p/googleclusterdata/.

Dynamic fair allocation of multi-resources based on shared resource quantity

ZHANG Xiao-lu, LIU Xi, LI Wei-dong, ZHANG Xue-jie
(School of Information Science and Engineering, Yunnan University, Kunming 650091, China)

A dynamic fair allocation of multi-resources was proposed based on shared resource quantity for multi-resoures allocation problem in cloud shared computing system. Firstly, a linear programming model was given based on resource requirements and quantity of shared resource and this model was further proved which satisfies four fairness properties such as DPO, SI, DEF and SP. Secondly, an improved dynamic multi-resources fair allocation algorithm was introduced for the allocation efficiency. Finally, theoretical analysis and experiments demonstrate that this strategy can satisfy the demands as well as maximize the dominant share on the base of approaching fairness and the improved algorithm increases the allocation efficiency in the dynamic system.

cloud computing, multi-resources fairness allocation, dominant share, shared resource quantity

s: The National Natural Science Foundation of China (No.61170222, No.11301466), Scientific Research Foundation of Yunnan Provincial Department of Education (No.2015J007), Natural Science Foundation of Yunnan Province (No.2013FB010)

TP301

A

10.11959/j.issn.1000-436x.2016144

2015-11-19；

2016-04-20

國家自然科學基金資助項目（No.61170222, No.11301466）；云南省教育廳科學研究基金資助項目（No.2015J007）；云南省科技廳應用基礎研究面上基金資助項目（No.2013FB010）

張瀟璐（1983-），女，山東淄博人，云南大學博士生，主要研究方向為資源分配調度、云計算能耗、大數據處理。

劉曦（1987-），男，云南昆明人，云南大學博士生，主要研究方向為智能算法、資源分配調度、大數據處理。

李偉東（1981-），男，河南鄭州人，博士，云南大學副教授，主要研究方向為組合優化算法、復雜性分析、分布式計算。

張學杰（1965-），男，云南昆明人，云南大學教授、博士生導師，主要研究方向為高性能計算、云計算、大數據、分布式計算。