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

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

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

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

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

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

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

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

1 cbDRF分配算法

1.1 多資源公平性算法

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

假定存在兩種資源r1和r2，其資源總量為R1和R2；存在兩個(gè)參與者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)勢(shì)資源（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分配算法

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

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

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

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

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

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

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

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

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

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

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

2 cbDRF分析

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

2.1 cbDRF特性分析

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

證明 由DRF的定義可知，節(jié)點(diǎn)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ù)因子ψ在多個(gè)計(jì)算階段中具有累積效應(yīng).

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

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

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

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

推論2 cbDRF是共享激勵(lì)模型.

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

2.2 cbDRF公平性分析

定理3 cbDRF能夠?qū)﹂L(zhǎng)期占用無(wú)用資源的惡意行為進(jìn)行懲罰性分配（Punitive Allocation）.

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

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

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

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

考慮兩種情況：

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

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

又因?yàn)閐j，pxjRp不變，所 以

定理6 cbDRF滿足Pareto Efficiency.

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

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

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

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

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

3 仿真評(píng)估

表1 DRF與cbDRF對(duì)比

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

3.1 單節(jié)點(diǎn)分配情況評(píng)估

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

由于云計(jì)算平臺(tái)中節(jié)點(diǎn)的計(jì)算任務(wù)復(fù)雜度不同，任務(wù)優(yōu)先級(jí)隨著計(jì)算的進(jìn)行可能發(fā)生變化.如何針對(duì)不同階段任務(wù)優(yōu)先級(jí)變化的特性，確定不同任務(wù)階段的參考閾值ρ，保證不同優(yōu)先級(jí)任務(wù)下資源分配公平性，是筆者未來(lái)的工作目標(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.