云計算下保障公平性的多資源分配算法

盧 笛，馬建峰，王一川，習(xí) 寧，張留美，孟憲佳

（西安電子科技大學(xué) 計 算機學(xué)院，陜西 西 安 710071）

云計算平臺通過對多種計算資源在云端進行整合，實現(xiàn)了對資源的統(tǒng)一管理和調(diào)度.為了向外部提供服務(wù)，云平臺依賴虛擬機節(jié)點執(zhí)行計算任務(wù).因此，云平臺的調(diào)度系統(tǒng)需要根據(jù)當(dāng)前各個虛擬機節(jié)點的資源需求，對資源進行合理的分配.其中，分配的公平性保證了在有限的資源條件下，各節(jié)點的利益最大，且不對其他節(jié)點造成損害，使得所有節(jié)點能夠有足夠的資源完成計算任務(wù).另外，針對不同的計算任務(wù)，節(jié)點資源需求也呈現(xiàn)出變化的特點，資源調(diào)度系統(tǒng)需要根據(jù)不同任務(wù)階段節(jié)點的需求進行資源分配.因此，云平臺調(diào)度系統(tǒng)需要解決多種資源情況下，面向動態(tài)資源需求的公平分配問題.

為得到更多的資源，節(jié)點可能通過需求欺騙、長期占用等手段非法使用資源，對資源分配公平性造成破壞.此外，在非可信網(wǎng)絡(luò)環(huán)境下，節(jié)點可能被攻陷而成為惡意節(jié)點，這些惡意節(jié)點通過上述手段攫取和蠶食系統(tǒng)資源，在破壞資源公平性的同時，使得平臺內(nèi)其他節(jié)點因資源需求無法滿足而無法正常作業(yè).因此，資源調(diào)度還需要保護分配公平性，對破壞公平性行為進行干預(yù)，遏制非法的資源使用.

目前，多數(shù)工作集中在如何解決資源分配的公平性問題，包括兩個方面：單資源和多資源分配的公平性問題.在單資源分配公平性方面，文獻[1－3]尋求最小資源需求的最大化，保證多數(shù)用戶的資源需求得到滿足；文獻[4]提出了一種在公平和效率之間進行折中的效用評估方法；文獻[5－6]在兩個沖突利益之間尋求資源分配的平衡；文獻[14]提出了基于5條基本公理的資源分配策略，為公平性的度量提供了準(zhǔn)則.

在多資源分配公平性方面，已有工作主要考慮存在同一資源的多個實例情況下的分配公平性問題，例如，文獻[7－9]針對多 CPU 實例；而文獻[10－12]針對帶寬；文獻[13]提出了一種基于“優(yōu)勢份額（Dominant Share，DShr）”分配算法，解決了在多種不同資源并存情況下如何保證分配公平性的問題；文獻[15]在文獻[13－14]的基礎(chǔ)上，提出了多種資源情況下資源分配和效率的折中模型；文獻[13，15]在多資源分配公平性問題上給出了較為合理的解決方法，但并未考慮上述兩個重要的問題：首先是用戶資源請求在不同階段是動態(tài)變化的；其次是有效遏制節(jié)點非法使用資源，保證公平性不被破壞.

綜上，目前工作雖在多種資源分配公平性上取得一定的進展，而對于資源需求動態(tài)性、防止惡意或非法資源使用等方面缺乏進一步的考慮.因此，有必要對云計算平臺下，面向動態(tài)資源需求的公平性保障方面進行進一步的研究.筆者將從資源需求動態(tài)變化的背景出發(fā)，提出基于動態(tài)資源需求的公平性分配模型，進一步給出基于信用量的公平性保障模型cbDRF.

1 cbDRF分配算法

1.1 多資源公平性算法

文獻[13]提出了一種基于“優(yōu)勢份額”的多資源環(huán)境下公平分配方案.該方法的核心思想是根據(jù)每個參與者的資源需求和系統(tǒng)資源總量，計算出各個參與者的DShr.通過均衡各參與者的DShr，確定每個參與者的子任務(wù)數(shù)量，最終得到參與者能夠分配到的其他資源的配額.該算法過程可描述如下：

假定存在兩種資源r1和r2，其資源總量為R1和R2；存在兩個參與者i和j，其資源需求向量分別為Di＝〈di，r1，di，r2〉 和Dj＝ 〈dj，r1，dj，r2〉.若存在以下關(guān)系：di，rR1＞di，rR2，dj，rR1＞dj，rR2，則i的“優(yōu)勢資源（DSrc）”為r1，而j的DSrc為r2.假設(shè)xi，xj分別為i和j的子任務(wù)數(shù)，則xi和xj為

由式（1）可得，i的DShr為dj，rxi，j的DShr為dj，rxj.可以看出，參與者的任務(wù)數(shù)xk是由其DSrc決定的，12而參與者在其他資源（非DSrc資源）上的份額也是由其DSrc間接確定的.在資源分配過程中，DRF算法采取 m ax－min fairness方法[1－3].

1.2 cbDRF分配算法

在云計算環(huán)境下，計算任務(wù)是階段性的.即不同時期的計算任務(wù)不同.因此，參與者（計算節(jié)點）對資源的需求在不同階段也呈現(xiàn)出變化的特點.例如，執(zhí)行數(shù)據(jù)壓縮的任務(wù)時，對CPU和內(nèi)存資源的需求量較大；而進行網(wǎng)絡(luò)數(shù)據(jù)傳輸時，對網(wǎng)絡(luò)帶寬需求量較大.因此，計算節(jié)點的DShr應(yīng)根據(jù)計算任務(wù)進行調(diào)整，確保公平性原則.另外，計算節(jié)點可能謊報資源需求，長時間占用資源不釋放，從而影響其他節(jié)點對該資源的使用.而惡意節(jié)點也可利用該方法對分配公平性進行破壞，因此，需要引入一種基于資源使用情況的機制，遏制節(jié)點的惡意行為，保護分配的公平性.針對這個問題，文中提出一種基于參與者信用的資源分配算法cbDRF.

假定資源種類數(shù)為m，參與者i的資源請求向量為Di.考慮節(jié)點計算任務(wù)的階段性特點，在時間區(qū)間〈tσ，m〉 內(nèi)，i執(zhí)行計算任務(wù)T〈tσ，m〉，其資源需求向量可表示為Di，〈tσ，m〉.其中，〈tσ，m〉 表示起始時間為tσ，持續(xù)長度為m.若i中包含的子任務(wù)數(shù)為xi，則節(jié)點i的資源配額向量Si，〈tσ，m〉可以表示為

由于不同時間區(qū)間計算任務(wù)以及節(jié)點對資源需求的不同，節(jié)點i的DShr需要重新計算.在時間區(qū)間〈tσ，m〉內(nèi)，節(jié)點i的DSrc可表示為

由此建立了基于時間區(qū)間和動態(tài)資源需求的DRF算法模型.

進一步考慮兩個相鄰時間區(qū)間τ′ ＝ 〈t ′σ，m′〉 和τ′＝ 〈t ′σ，m′〉，滿足tσ＞t′σ，tσ＝t′σ＋m′。定義τ′階段結(jié)束后節(jié)點i的理論釋放資源量為?i，τ，則?i，τ可表示為

而τ′內(nèi)為i分配的資源量Ai，τ′＝?i，τ′.在實際環(huán)境中，由于計算任務(wù)結(jié)束后，系統(tǒng)往往需要執(zhí)行一些回收操作，為下一次計算做準(zhǔn)備.因此，被占用資源不會在計算階段結(jié)束后立即完全釋放掉，有Ai，τ′≥.表示節(jié)點i在τ′之后的實際資源釋放量.

為描述節(jié)點釋放資源的情況，引入評估參數(shù)η：ηi，τ′＝Ai，τ′，0≤ηi，τ′≤1，該參數(shù)直接反映節(jié)點在階段任務(wù)完成之后釋放資源量的情況.若η→0，則節(jié)點在任務(wù)完成后仍然占用大量資源；若η→1，則節(jié)點在任務(wù)結(jié)束后及時釋放了占用的資源.為度量評估參數(shù)η，引入門限ρ，使得

式（6）中引入節(jié)點信譽參數(shù)Ci.依據(jù)評估參數(shù)ρ，若節(jié)點在任務(wù)結(jié)束后及時釋放占用資源，則Ci增加ε（ε＞0）；反之，若節(jié)點長期占用資源，則Ci值下降ε′.因此，當(dāng)節(jié)點執(zhí)行多次計算任務(wù)之后，若長期占據(jù)資源且不釋放，其信譽參數(shù)Ci將不斷降低，影響其后續(xù)任務(wù)的執(zhí)行.ε和ε′控制信譽參數(shù)增長或減少的速度.

系統(tǒng)初始時刻定義節(jié)點默認信譽值C0，引入基于信譽參數(shù)的因子ψi，τ＝CiC0，（Ci＜ C0），對節(jié)點的實際分配任務(wù)數(shù)進行約束，則分配模型式（1）可以重新構(gòu)建為

模型式（7）為基于節(jié)點信譽的 DRF模型（cbDRF）.式（7）中，信譽因子ψi，τ′表示節(jié)點i前一任務(wù)結(jié)束后，基于釋放量的評估值.圖1給出cbDRF中相鄰計算階段的關(guān)系.可以看出，cbDRF是一種反饋控制模型.其中，第τ階段的資源分配由上一階段的信譽因子ψi，τ′確定，即滿足式（7）的關(guān)系.因此，節(jié)點在上一階段的資源使用情況將對下一階段產(chǎn)生影響.若節(jié)點在任務(wù)結(jié)束后，及時釋放足夠量的資源，則下一階段的資源份額將不受影響；否則，惡意侵占或蠶食資源的行為將降低其信譽參數(shù)，導(dǎo)致節(jié)點未來階段的資源1份額逐漸減少，達到激勵節(jié)點釋放資源、遏制非法占用資源的目的.

圖1 cbDRF節(jié)點任務(wù)時序關(guān)系模型

2 cbDRF分析

cbDRF對一個計算階段后節(jié)點實際分配資源及釋放節(jié)點情況進行評估，通過信譽因子對節(jié)點下一階段任務(wù)數(shù)進行約束，防止節(jié)點長期占用資源，導(dǎo)致系統(tǒng)資源慢性損耗，從而提高資源利用率，保證公平性的持久性.

2.1 cbDRF特性分析

定理1 若cbDRF中節(jié)點其他資源份額為si，k，DSrc需求量為di，r，資源種類數(shù)為k，則si，k由di，r確定，表示為si，k～di，r.其中k＝1，2，…，n，k≠r.

證明 由DRF的定義可知，節(jié)點i的份額向量可以表示為：Si＝Dixi，而di，rxiRr＝dj，pxjRp，i≠j.其中r，p分別為i，j的DSrc.得出，xi由其DSrc需求量di，r確定.因此，Si由di，r間接確定，所以有si，k～di，r.證畢.

定理2 cbDRF中，信譽因子ψ在多個計算階段中具有累積效應(yīng).

證明 假設(shè)節(jié)點i執(zhí)行圖1所示的計算任務(wù)鏈，其中存在階段任務(wù) Ti，τ1，Ti，τ2，Ti，τ3，…，Ti，τn.假設(shè)在Ti，τk到Ti，τk＋λ內(nèi)，節(jié)點每執(zhí)行完階段任務(wù)就繼續(xù)占用多數(shù)資源，且每次釋放量都小于評估參數(shù)ρ，則其信譽值Ci會不斷降低.由于信譽因子ψ依賴于Ci的值，而隨著Ci的值不斷減小，存在如下關(guān)系：

式（8）說明在節(jié)點長期不釋放適量資源的情況下，其信譽因子會逐步降低.同理，若節(jié)點在每個階段任務(wù)及時釋放其占用資源，則信譽因子滿足如下關(guān)系：因此，ψ的值在計算階段鏈中呈現(xiàn)累積的特征.證畢.

推論1 cbDRF能夠激勵節(jié)點在階段任務(wù)完成后及時釋放資源.

證明 當(dāng)節(jié)點i在階段任務(wù)鏈的執(zhí)行過程中，每個階段任務(wù)結(jié)束時及時釋放資源，由定理2可知，i的信譽因子會遞增，保證了i的子任務(wù)數(shù)量在下一階段計算任務(wù)中不被縮減.因此，節(jié)點只有通過及時釋放占用資源才能保證其子任務(wù)數(shù)量不受影響，進而保證分配的資源量不受影響，因為節(jié)點資源分配量由子任務(wù)數(shù)和

推論2 cbDRF是共享激勵模型.

證明 由推論1可知節(jié)點在階段任務(wù)執(zhí)行結(jié)束后，為保證自己下一階段的資源配額，會積極釋放不需要的資源，保證了其他節(jié)點的資源配額（Resource Share）.證畢.

2.2 cbDRF公平性分析

定理3 cbDRF能夠?qū)﹂L期占用無用資源的惡意行為進行懲罰性分配（Punitive Allocation）.

定理4 cbDRF是“無嫉妒（Envy－Free）”模型.

證明 假設(shè)節(jié)點i“嫉妒”節(jié)點j的資源配額，則說明節(jié)點j的資源配額大于i，且這些資源也是i所需要的.假設(shè)這些資源為k＝1，2，3，…，λ，這里需要考慮兩種情況：

（1）k是i和j的 D Src.此時，k只能是一種資源.根據(jù)假設(shè)，有di，k＞dj，k，根據(jù)式（1）有：di，kxiRk＝dj，kxjRk，則xi＞xj，即通過為i分配多個子任務(wù)來平衡其DShr，因此不會影響i的資源配額.

（2）k不是i的DSrc，但對于i較為重要，且j占有了較多的配額.假設(shè)i，j的DSrc分別為r，p，得

考慮兩種情況：

定理5 cbDRF是防止策略性操縱的（Strategy－Proofness）.即節(jié)點不能通過謊報資源需求量來提高自己的份額，滿足資源需求的不可欺騙性.

證明 假設(shè)節(jié)點i為獲得更多份額，將其需求向量從Di提升為，假設(shè)i的DSrc為r，有＞di，r.假設(shè)j的DSrc為p，則有

又因為dj，pxjRp不變，所 以

定理6 cbDRF滿足Pareto Efficiency.

證明 由Pareto Efficiency的定義，假設(shè)節(jié)點能夠提高自己的配額，并且不會使其他節(jié)點的配額受影響.根據(jù)假設(shè)，對于節(jié)點i，存在Pareto Improvement使得在不影響其余節(jié)點份額的前提下，提高i的資源份額.

由文獻[13]引理（8）可知，使用DRF的各節(jié)點至少有一個已經(jīng)飽和的資源.假設(shè)節(jié)點i在資源r上的份額從si，r提升為si，r.由定理5可知，i不能通過提高di，r來增加si，r，因此，i通過提高xi來增加資源r的份額.由引理（8）可得i至少有一個飽和資源w，因此，提高xi不可能再使w的份額增長，因而，與假設(shè)矛盾，這樣的Pareto Improvement不存在，證畢.

cbDRF滿足Pareto Efficiency實質(zhì)上是對節(jié)點占用資源的約束，即資源分配已達到飽和，節(jié)點不可能再增加自己的份額，除非占用其他節(jié)點的資源，而這種行為將被系統(tǒng)禁止.

文獻[13]指出了分配算法需要滿足的4條重要的性質(zhì)，即：激勵共享（Sharing Incentive）、無嫉妒性（Envy－Freeness）、防 止 策 略 性 操 縱 （Strategy－Proofness）、帕累托最優(yōu)（Pareto Efficiency），以此保證

分配的公平性不被破壞.表1對比了cbDRF和DRF模型.可以看出，cbDRF在滿足4條基本性質(zhì)之外，cbDRF通過信譽因子評估，實現(xiàn)了針對計算節(jié)點惡意占用資源行為的懲罰性分配，使節(jié)點在任務(wù)完成后主動及時釋放占用資源，保證了平臺資源調(diào)度的公平性不被破壞.

3 仿真評估

表1 DRF與cbDRF對比

針對cbDRF算法，對單一節(jié)點和多節(jié)點的情況進行了仿真實驗并對結(jié)果進行了比較分析.實驗選取了節(jié)點任務(wù)鏈中10個連續(xù)的階段任務(wù)，定義采用cbDRF的資源分配量為Aact，采用DRF之后的分配量為Ai，參數(shù)ξ＝AactAi對cbDRF中信譽因子ψ進行評估.

3.1 單節(jié)點分配情況評估

圖2給出了當(dāng)節(jié)點信譽因子ψ持續(xù)衰減的情況下對CPU和內(nèi)存（MEM）資源分配造成的影響.實驗設(shè)置系統(tǒng)的資源總量為〈CPU為500，Memory為50 000〉，設(shè)節(jié)點對資源的請求為隨機變量，且CPU的需求dCPU∈[20，100]；對內(nèi)存的需求dMem∈[300，1 000].節(jié)點在每個階段任務(wù)完成后釋放資源的η值小于門限ρ（ρ＝0.75），依據(jù)cbDRF算法，節(jié)點信譽因子ψ下降，導(dǎo)致子任務(wù)數(shù)減少和資源分配量的逐步減?。ǘɡ?）.從圖中可以看出，節(jié)點資源實際分配量與理想值比例參數(shù)從100%下降至10%.這是由于節(jié)點在每一階段任務(wù)完成后沒有及時釋放足夠資源，導(dǎo)致其后任務(wù)中資源分配量逐次下降，即實際分配量與理論分配量的差值越來越大.由于實驗將AactAi作為評估指標(biāo)，因此，CPU和內(nèi)存變化率相同.

圖3給出信譽因子ψ的變化對節(jié)點資源分配量的影響，實驗設(shè)置同圖2.可以看出，節(jié)點在前5個計算階段由于釋放資源不足，信譽因子ψ下降，導(dǎo)致資源分配量下降（同圖2）.從第6階段開始，節(jié)點的評估參數(shù)滿足η≥ρ，ψ增加，則子任務(wù)數(shù)遞增，因此，資源分配量逐漸增加.若ψ持續(xù)增加并趨近于1，則節(jié)點資源分配量回到正常水平，即AactAi→1.可以看出，在階段任務(wù)完成后，若節(jié)點不及時釋放足量的資源，對后續(xù)任務(wù)中的資源分配量會造成明顯的影響，并且這種影響具有累積性質(zhì)，即非法占用資源越多，節(jié)點遭受的資源懲罰就越大.

3.2 多節(jié)點分配比較

實驗對兩個節(jié)點兩種資源情況下同時采用cbDRF算法的結(jié)果進行比較（實驗設(shè)置同3.1節(jié)）.圖4顯示兩計算節(jié)點在連續(xù)10個計算階段中未釋放足量資源，導(dǎo)致其配額受到懲罰性分配的情況.從圖中明顯可以看出，兩個節(jié)點由于占用過多資源而不及時釋放，使其后續(xù)資源份額受到明顯影響.到最后一個計算階段，其單一資源的實際配額只有期望值的10%左右.

圖2 ψ持續(xù)衰減下的資源分配情況

圖3 ψ信用因子衰減后回升對資源配額的影響

圖4 持續(xù)ψ衰減下兩節(jié)點的分配情況

圖5 不同ψ情況下兩節(jié)點的分配情況比較

圖5對不同信譽因子下兩節(jié)點資源分配量進行了比較.可以看出，對于評估參數(shù)η≥ρ的節(jié)點，其資源分配量與理想的DRF分配量相等.而在階段任務(wù)結(jié)束后仍然占用過量資源的節(jié)點，經(jīng)過懲罰性分配后的資源配額呈現(xiàn)明顯下降趨勢.

通過仿真實驗可以看出，長期占用資源會導(dǎo)致節(jié)點遭受懲罰性分配，資源配額逐漸減少，并影響節(jié)點后續(xù)任務(wù)的進行.這一結(jié)果表明cbDRF是滿足懲罰性分配（Punitive Allocation）特性.若及時釋放占用資源，則節(jié)點資源配額將保持正常水平或由下降趨勢逐漸變?yōu)樯仙敝吝_到正常水平.這一特性表明，節(jié)點主動釋放占用資源能夠保證自己的份額不受影響，因此，cbDRF能夠滿足共享激勵（Sharing Incentive）和釋放激勵（Release Incentive）特性.

4 結(jié)束語

目前用于云平臺多種虛擬資源調(diào)度的算法多關(guān)注于分配公平性的問題，而對于如何防止通過惡意占用資源、資源欺騙等手段破壞公平性的問題則很少關(guān)注.筆者針對確保資源分配公平性不被破壞的問題，基于DRF算法提出了基于信譽因子的cbDRF算法.算法通過對節(jié)點階段任務(wù)結(jié)束后的釋放資源進行評估，引入節(jié)點信譽因子ψ，根據(jù)ψ的值確定節(jié)點下一階段任務(wù)的資源配額.對惡意占用資源的行為根據(jù)ψ的值進行懲罰，激勵節(jié)點及時釋放已使用的資源，保證其他節(jié)點的分配量不受影響，從而保證整個平臺的資源可用性以及分配的公平性不被破壞.

由于云計算平臺中節(jié)點的計算任務(wù)復(fù)雜度不同，任務(wù)優(yōu)先級隨著計算的進行可能發(fā)生變化.如何針對不同階段任務(wù)優(yōu)先級變化的特性，確定不同任務(wù)階段的參考閾值ρ，保證不同優(yōu)先級任務(wù)下資源分配公平性，是筆者未來的工作目標(biāo).

[1] Bertsekas D，Gallager R.Data Networks[M].New Jersey：Prentice Hall，1992.

[2] Charny A，Clark D D，Jain R.Congestion Control with Explicit Rate Indication [C]//Proceedings of the IEEE International Conference on Communications：3.Piscataway：IEEE，1995：1954－1963.

[3] Tan L，Pugh A C，Yin M，Rate－based Congestion Control in ATM Switching Networks Using a Recursive Digital Filter[J].Control Engineering Practice，2003（11）：1171－1181.

[4] Zukerman M，Tan L，Wang H，et al.Efficiency－Fairness Tradeoff in Telecommunication Networks [J].IEEE Communications Letters，2005，9（7）：643－645.

[5] Kelly F.Charging and Rate Control for Elastic Traffic[J].European Transaction on Telecommunications，1997，8（1）：33－37.

[6] Massoulie L，Roberts J.Bandwidth Sharing：Objectives and Algorithms [C]//Proceedings of 18th Annual Joint Conference of the IEEE Computer and Communications Societies：3.Piscataway：IEEE，1999：1395－1403.

[7] Baruah S K，Cohen N K，Plaxton C G，et al.Proportionate Progress：a Notion of Fairness in Resource Allocation[J].Algorithmica，1996，15（6）：600－625.

[8] Baruah S K，Gehrke J，Plaxton C G.Fast Scheduling of Periodic Tasks on Multiple Resources [C]//Proceedings of Parallel Processing Symposium.Piscataway：IEEE，1995：280－288.

[9] Zhu D，Mosse D，Melhem R.Multiple－Resource Periodic Scheduling Problem：How Much Fairness is Necessary？[C]//24th IEEE International Real－Time Systems Symposium.Piscataway：IEEE，2003：142－151.

[10] Blanquer J M，ézden B.Fair Queuing for Aggregated Multiple Links[J].Computer Communication Review，2001，31（4）：189－197.

[11] Kleinberg J M，Rabani Y，Tardosé.Fairness in Routing and Load Balancing[J].Journal of Computer System Science，2001，63（1）：2－20.

[12] Liu Y H，Knightly E W.Opportunistic Fair Scheduling over Multiple Wireless Channels [C]//Proceedings of IEEE INFOCOM：2.Piscataway：IEEE，2003：1106－1115.

[13] Ghodsi A，Zaharia M，Hindman B，et al.Dominant Resource Fairness：Fair Allocation of Multiple Resource Types[C]//Proceedings of the 8th USENIX Conference on NSDI.Berbeley：USENIX Association，2011：24－37.

[14] Lan T，Kao D，Chiang M，et al.An Axiomatic Theory of Fairness in Network Resource Allocation[C]//Proceedings of IEEE INFOCOM.Piscataway：IEEE，2010：1－9.

[15] Joe－Wong C，Sen S，Lan L，et al.Multi－Resource Allocation：Fairness Efficiency Tradeoffs in a Unifying Framework[C]//Proceedings of IEEE INFOCOM.Piscataway：IEEE，2012：1206－1214.