張麗敏

（西安外事學(xué)院現(xiàn)代教育技術(shù)中心 西安 710077）

1 引言

虛擬技術(shù)為云供應(yīng)商提供更加便捷的方法來(lái)分配計(jì)算資源。云供應(yīng)商定義不同的虛擬機(jī)（VM）組合，并以VM實(shí)例為單位出售資源。當(dāng)前，云供應(yīng)商使用定價(jià)策略分配和出售VM實(shí)例[1]，使用拍賣(mài)算法來(lái)出售定價(jià)之后仍然閑置的資源。云供應(yīng)商希望分配算法能夠支持動(dòng)態(tài)供應(yīng)，以便他們根據(jù)市場(chǎng)需求就不同類(lèi)型的VM實(shí)例數(shù)量做出決策。云供應(yīng)商也希望實(shí)現(xiàn)營(yíng)運(yùn)收入最大化。

多篇文獻(xiàn)已經(jīng)對(duì)云計(jì)算的經(jīng)濟(jì)問(wèn)題進(jìn)行了研究。參考文獻(xiàn)[2]針對(duì)目前國(guó)內(nèi)并沒(méi)有相應(yīng)的云計(jì)算計(jì)價(jià)標(biāo)準(zhǔn)，價(jià)格高低直接影響網(wǎng)絡(luò)利用率和收益的問(wèn)題，在計(jì)價(jià)時(shí)考慮價(jià)格因素對(duì)網(wǎng)絡(luò)負(fù)載的影響，提出了一種改進(jìn)的蟻群算法，解決了計(jì)算資源閑置導(dǎo)致的網(wǎng)絡(luò)利用率低下和收益減少問(wèn)題。參考文獻(xiàn)[3]提出了一種面向資源分配的第k+1個(gè)價(jià)格拍賣(mài)算法。通過(guò)理論分析與仿真得出，當(dāng)資源和用戶(hù)較多時(shí)，該算法既可以提高分配的效率，又可以增加云服務(wù)商的收入。參考文獻(xiàn)[4]設(shè)計(jì)了一種基于馬爾可夫決策過(guò)程的資源在線(xiàn)算法，給出了同一模型面對(duì)大規(guī)模問(wèn)題時(shí)的近似求解方法。參考文獻(xiàn)[5]設(shè)計(jì)了一種并行系統(tǒng)下可拓展并行作業(yè)的資源在線(xiàn)調(diào)度算法。該算法在其模型中支持作業(yè)搶占，如果作業(yè)的價(jià)值更高，那么即使提交時(shí)間晚于當(dāng)前分配的作業(yè)，也可以獲得優(yōu)先權(quán)支持。參考文獻(xiàn)[6]提出了一種云資源調(diào)度模型（cloud-resource scheduling model，CSM），該模型以實(shí)現(xiàn)效用最大為調(diào)度目標(biāo)，可以充分提高用戶(hù)的滿(mǎn)意程度。文中通過(guò)求解CSM優(yōu)化問(wèn)題得到最優(yōu)的虛擬機(jī)和物理機(jī)映射關(guān)系，實(shí)現(xiàn)了對(duì)云資源的最優(yōu)分配。

另外，參考文獻(xiàn)[7]針對(duì)云商務(wù)環(huán)境下信息服務(wù)資源分配過(guò)程中的定價(jià)問(wèn)題，分別建立了服務(wù)者、服務(wù)用戶(hù)和服務(wù)環(huán)境的模型，并提出相應(yīng)的求解方法。仿真實(shí)驗(yàn)結(jié)果表明，當(dāng)交易者的規(guī)模增加時(shí)，該方法可以在保證第三方收入的情況下，使參與交易的雙方獲取更高的服務(wù)效用。參考文獻(xiàn)[8]提出了一種基于組合拍賣(mài)的VM分配算法CA-Provision，該算法通過(guò)假設(shè)資源以數(shù)量固定但類(lèi)型不同的VM實(shí)例形式提前供應(yīng)，從而解決VM分配問(wèn)題。另外，CA-Provision算法拓展了參考文獻(xiàn)[7]中的模型，并支持VM實(shí)例的動(dòng)態(tài)供應(yīng)和分配。然而，該算法在運(yùn)行時(shí)需要收集一段時(shí)間內(nèi)所有用戶(hù)請(qǐng)求的所有信息，即這些算法是離線(xiàn)算法，需要定期運(yùn)行來(lái)為用戶(hù)分配資源。

為此，本文設(shè)計(jì)了一種云條件下VM實(shí)例的在線(xiàn)供應(yīng)和分配算法。首先，設(shè)計(jì)了一種申請(qǐng)協(xié)議，當(dāng)用戶(hù)申請(qǐng)一批VM時(shí)，表明用戶(hù)只對(duì)整批VM感興趣，而不是其中的一部分。在接收到這些申請(qǐng)后，本文算法在線(xiàn)計(jì)算分配策略和花費(fèi)。同時(shí)，分配不得被搶占，如果用戶(hù)在時(shí)間t接收到分配策略，則在用戶(hù)所請(qǐng)求的該段時(shí)間內(nèi)始終占有資源。最后，通過(guò)理論分析和仿真實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。

2 VM實(shí)例分配問(wèn)題

假設(shè)云服務(wù)提供商提供的計(jì)算資源共有m種不同的VM實(shí)例類(lèi)型，本文將這些實(shí)例類(lèi)型表示為VM1,…,VMm。對(duì)每種類(lèi)型的實(shí)例 VMi關(guān)聯(lián)一個(gè) “權(quán)重”ωi∈，ωi表示VMi相對(duì)云供應(yīng)商提供的最強(qiáng)大VM實(shí)例 （即類(lèi)型為VM1的實(shí)例）的計(jì)算能力。不失一般性，本文認(rèn)為ω1=1且ω1≤…≤ωm。將可以用于分配的可用計(jì)算資源的總計(jì)算能力表示為M，定義為類(lèi)型VM1的M個(gè)實(shí)例的等價(jià)計(jì)算能力。假設(shè)云供應(yīng)商提供3種類(lèi)型的VM實(shí)例：小型（VM1）、中型（VM2）、大型（VM3）。這些 VM 的配置如下：VM1為 1 個(gè)2 GHz處理器、8 GB內(nèi)存、2 TB硬盤(pán)；VM2為 2個(gè) 2 GHz處理器、8 GB內(nèi)存、2 TB硬盤(pán)；VM3為2個(gè)2 GHz處理器、16 GB內(nèi)存、4 TB硬盤(pán)。對(duì)于該配置來(lái)說(shuō)，VM的權(quán)重為：ω1=1、ω2=2、ω3=4。假設(shè)云提供商有足夠的資源來(lái)提供100 000個(gè)VM1實(shí)例，則M=100 000。云提供商的目的是將其可用資源動(dòng)態(tài)供應(yīng)為VM實(shí)例，在將其高效提供給用戶(hù)的同時(shí)實(shí)現(xiàn)收益最大化。

滿(mǎn)足的約束條件為：

式（1）表示問(wèn)題的目標(biāo)，即云供應(yīng)商使成功申請(qǐng)資源的用戶(hù)價(jià)值之和最大化。式（ 2 ） 表示在已知時(shí)間t分配的資源不得超過(guò)最大可用資源數(shù)量M。其中，，該集合表示在時(shí)間t及t之前分配到資源，并且在時(shí)間t所分配到的時(shí)間間隙還沒(méi)有結(jié)束的用戶(hù)集合。

上述問(wèn)題的一種直接求解方法就是選擇價(jià)值最大的用戶(hù)，然后向這些用戶(hù)收取各自的費(fèi)用。然而，用戶(hù)是理性用戶(hù)，他們可能為了自身利益而誤報(bào)自己的類(lèi)型。例如，用戶(hù)可能少報(bào)價(jià)值以便減少支付額度，或者多報(bào)價(jià)值以增加被分配概率。如果云提供商偏好截止日期較早的作業(yè)而忽略?xún)r(jià)值，則用戶(hù)可能會(huì)早報(bào)他們的截止日期。因?yàn)檫@一信息是隱私信息，所以提供商需要使用一種算法來(lái)根據(jù)用戶(hù)報(bào)告的價(jià)值計(jì)算分配策略及相關(guān)費(fèi)用，以便提供商設(shè)定的全系統(tǒng)目標(biāo)能夠?qū)崿F(xiàn)。

3 在線(xiàn)算法的設(shè)計(jì)

每個(gè)用戶(hù)j可將價(jià)值函數(shù)Vj定義如下：

如果用戶(hù)申請(qǐng)成功，則用戶(hù)接收到的價(jià)值為υj；否則，接收到的價(jià)值為0。本文用效用函數(shù)來(lái)定量描述用戶(hù)j的效益，該效用函數(shù)定義為用戶(hù)從算法接收到的價(jià)值與用戶(hù)需要支付的費(fèi)用之差，即：

如果在線(xiàn)算法拒絕為其分配資源，則用戶(hù)接收到的價(jià)值為0。此時(shí)，如果算法不向其收取任何費(fèi)用，用戶(hù)的效用也將為0。

定義 1 （激勵(lì)作用）如果對(duì)任意用戶(hù)j有∈Θj、-j∈Θ-j、并滿(mǎn)足式（5），則算法E具有激勵(lì)作用[9]。

用戶(hù)如果不管其他用戶(hù)的申請(qǐng)如何，而把自己的真實(shí)類(lèi)型匯報(bào)給算法，則可以實(shí)現(xiàn)自身效用最大化。這是非常重要的算法，因?yàn)槿绻麧M(mǎn)足這一屬性，參與算法的用戶(hù)就不會(huì)向算法匯報(bào)虛假類(lèi)型，即匯報(bào)真實(shí)屬性是用戶(hù)的最優(yōu)策略。

不管其他用戶(hù)的申請(qǐng)如何，用戶(hù)只要參與在線(xiàn)算法并匯報(bào)了自己的真實(shí)類(lèi)型，自己的效用一定不會(huì)為負(fù)。這也是在線(xiàn)算法的重要屬性，因?yàn)榭梢怨膭?lì)用戶(hù)積極參與在線(xiàn)算法。為了使算法具有激勵(lì)作用，分配函數(shù)A必須單調(diào)且費(fèi)用函數(shù)P必須實(shí)現(xiàn)臨界值支付[10]。

如果用戶(hù)j通過(guò)匯報(bào)類(lèi)型而申請(qǐng)成功，則該用戶(hù)匯報(bào)也會(huì)申請(qǐng)成功 ，其 中′比更 受 偏 好 。

定義4 （臨界值支付）用戶(hù)j的臨界值 定義為

臨界值是指用戶(hù)為了申請(qǐng)成功而必須向算法匯報(bào)的最小值。費(fèi)用函數(shù)應(yīng)該向用戶(hù)收取臨界值費(fèi)用，以便使算法具有激勵(lì)功能。本文設(shè)計(jì)了一種解決OVMPA問(wèn)題的在線(xiàn)算法。

4 在線(xiàn)VM分配算法

本節(jié)給出了解決OVMPA問(wèn)題的在線(xiàn)VM分配和供應(yīng)算法。

4.1 ODAA-VM

ODAA-VM采取事件處理程序架構(gòu)，當(dāng)新的申請(qǐng)到達(dá)或者用戶(hù)分配到的批量資源到期，并且將VM實(shí)例返回給供應(yīng)商時(shí)，調(diào)用事件處理程序。假設(shè)通過(guò)某種標(biāo)準(zhǔn)化協(xié)議，用戶(hù)和資源的信息對(duì)算法是已知的。ODAA-VM利用這一信息來(lái)確定用戶(hù)集合及當(dāng)前時(shí)間可用資源，并可調(diào)用分配函數(shù)和費(fèi)用函數(shù)。ODAA-VM流程如下。

ODAA-VM以事件、當(dāng)前分配集合及費(fèi)用集合為輸入。事件類(lèi)型包括資源的釋放或到達(dá)的用戶(hù)申請(qǐng)。假設(shè)系統(tǒng)存儲(chǔ)這兩個(gè)集合，并且當(dāng)ODAA-VM被調(diào)用時(shí)將其傳輸給ODAA-VM。ODAA-VM更新集合，然后返回給系統(tǒng)。在第1～4行，ODAA-VM設(shè)置當(dāng)前時(shí)間為t，且3個(gè)變量的初始化如下：N(t)為迄今還沒(méi)有申請(qǐng)成功的用戶(hù)申請(qǐng)集合；(t)為已經(jīng)成功申請(qǐng)但是分配的資源還沒(méi)有到期的用戶(hù)申請(qǐng)集合；M(t)為在時(shí)間t可用于分配的資源總權(quán)重。只有當(dāng)資源和用戶(hù)可用時(shí)，算法才會(huì)運(yùn)行。算法會(huì)調(diào)用以未獲得成功的用戶(hù)申請(qǐng)和時(shí)間可用資源為參數(shù)的函數(shù)ODAA-VM-Allocate。ODAA-VM-Allocate函數(shù)（見(jiàn)第4.2節(jié)）返回在時(shí)間t申請(qǐng)成功的用戶(hù)集合A(t)。

然后，ODAA-VM將整個(gè)分配集合A更新為A(t)。A(t)中的申請(qǐng)也被插入費(fèi)用集合，且 為初始費(fèi)用。然而，通過(guò)調(diào)用ODAA-VM-Payment函數(shù)（見(jiàn)第4.3節(jié)）可以更新該費(fèi)用（第11行）。實(shí)際上，用戶(hù)j的費(fèi)用會(huì)被更新多次，直到t=δj（即用戶(hù)接收到所要求的批量實(shí)例）為止。因此，ODAA-VM-Payment函數(shù)計(jì)算這些用戶(hù)的費(fèi)用并更新費(fèi)用集合P。ODAA-VM算法的下一個(gè)步驟是確定當(dāng)前時(shí)間已經(jīng)超過(guò)δj的用戶(hù)j的申請(qǐng)集合NP（第12行）。然而，這一集合只包括t′之后已經(jīng)度過(guò)δi時(shí)間的用戶(hù)，其中t′表示上次調(diào)用ODAA-VM的時(shí)間（第12行）。如果用戶(hù)j已經(jīng)分配到了批量資源，則該用戶(hù)的費(fèi)用不會(huì)再改變，當(dāng)前時(shí)刻的費(fèi)用即最終費(fèi)用。如果用戶(hù)j直到時(shí)間t還沒(méi)有申請(qǐng)成功且t>δj，則用戶(hù)不會(huì)申請(qǐng)到完成他的作業(yè)所需要的資源。此時(shí)，用戶(hù)j將支付的費(fèi)用為pj=0（第14～19行）。

4.2 ODAA-VM-Allocate函數(shù)

函數(shù)ODAA-VM-Allocate的具體過(guò)程如下。

首先，ODAA-VM-Allocate函數(shù)按照ρj的非升次序?qū)λ猩暾?qǐng)排序。按照如下次序打破關(guān)聯(lián)：偏愛(ài)更早的δj、更小的以及更小的。然后，當(dāng)資源允許時(shí)，算法將為這些用戶(hù)分配各自請(qǐng)求的資源。最后，算法返回在時(shí)間t被選擇分配資源的用戶(hù)集合A(t)。

ODAA-VM-Allocate函數(shù)的目的是實(shí)現(xiàn)申請(qǐng)成功的用戶(hù)價(jià)值之和最大化。當(dāng)存在關(guān)聯(lián)情況時(shí)，通過(guò)向δj較小的用戶(hù)賦予優(yōu)先級(jí)（即沒(méi)有申請(qǐng)成功而將較早離開(kāi)系統(tǒng)的用戶(hù)），也可以保證受到服務(wù)的用戶(hù)數(shù)量最大化?；谕瑯釉颍瑢?duì)于δj關(guān)聯(lián)情況，資源使用時(shí)間較短的用戶(hù)也將受到優(yōu)先對(duì)待。

4.3 ODAA-VM-Payment函數(shù)

ODAA-VM-Payment函數(shù)如下。

ODAA-VM-Payment函數(shù)的輸入包括當(dāng)前時(shí)間t、費(fèi)用集合P、調(diào)用分配函數(shù)M(t)之前的可用資源、分配函數(shù)N(t)考慮的用戶(hù)集合以及當(dāng)前時(shí)間t占據(jù)資源的用戶(hù)集合(t)。在時(shí)間t申請(qǐng)成功的用戶(hù)也屬于集合N(t)。

ODAA-VM-Payment函數(shù)的主要思路是將用戶(hù)的到達(dá)時(shí)間看成t，然后計(jì)算δj≤t的用戶(hù)j的臨界費(fèi)用。通過(guò)每個(gè)事件重復(fù)調(diào)用這一函數(shù)，ODAA-VM可以保證和 δj之間每次出現(xiàn)事件時(shí)，均會(huì)計(jì)算用戶(hù)j的臨界費(fèi)用。ODAA-VM-Payment函數(shù)對(duì) δj≥t的所有用戶(hù)j計(jì)算時(shí)間t時(shí)的臨界值為：

以該臨界值為基礎(chǔ)，ODAA-VM將臨界值計(jì)算為：

ODAA-VM-Payment函數(shù)考慮費(fèi)用集合中 δj≤t的用戶(hù)。對(duì)于每個(gè)用戶(hù)j，將其類(lèi)型的到達(dá)時(shí)間元素設(shè)為t，價(jià)值設(shè)為每個(gè)用戶(hù)的價(jià)值，以便確定用戶(hù)j為了申請(qǐng)成功而需匯報(bào)的最小值（第2～16行）。如果未找到最小值，則將支付費(fèi)用設(shè)為0（第17～21行），也可以將該數(shù)值設(shè)為預(yù)先確定的底價(jià)。最后，將更新過(guò)的集合P返回給在線(xiàn)算法。在線(xiàn)算法通過(guò)調(diào)用ODAA-VM-Payment函數(shù)以持續(xù)更新P，并在時(shí)間t向的δj

5 算法性能

定理1ODAA-VM具有激勵(lì)作用。

定理2ODAA-VM的時(shí)間復(fù)雜度為O(nlogn)。

ODAA-VM主要包括ODAA-VM-Allocate函數(shù)和ODAA-VM-Payment函數(shù)。其中，ODAA-VM-Allocate函數(shù)成本最大的操作是第2行的用戶(hù)排序，這一操作的復(fù)雜度為O(nlogn)。ODAA-VM-Payment函數(shù)看上去非常復(fù)雜，因?yàn)樗貜?fù)調(diào)用ODAA-VM-Allocate函數(shù)。但是，在實(shí)際部署中，當(dāng)確定臨界值時(shí)并不需要調(diào)用ODAA-VM-Allocate函數(shù)。對(duì)申請(qǐng)成功的用戶(hù)j，需要以他們的非升次序考慮在時(shí)間t沒(méi)有申請(qǐng)成功的用戶(hù)j′，并且弄清如果j沒(méi)有參與，用戶(hù)j′能否申請(qǐng)成功。只需比較j占據(jù)的資源和j′請(qǐng)求的資源，就可以弄清這一點(diǎn)。當(dāng)首次發(fā)現(xiàn)這一用戶(hù)j′時(shí)，用戶(hù)j的費(fèi)用為′。需要在算法開(kāi)始時(shí)對(duì)失敗的申請(qǐng)進(jìn)行一次排序，這一過(guò)程的復(fù)雜度仍然為O(nlogn)。因此，ODAA-VM的時(shí)間復(fù)雜度為O(nlogn)。

定理3 ODAA-VM的競(jìng)爭(zhēng)比為η。

設(shè)有兩個(gè)申請(qǐng) θ1和 θ2，且s1=1，s2=M,(a1,l1,d1,υ1)=(0,l,l,υ)，(a2,l2,d2,υ2)=(1,l,l+1,Mv+ε),l>1。一方面，ODAA-VM 將為用戶(hù)1分配其在時(shí)間l>1要釋放的資源。因?yàn)閷?duì)于θ2，有a2+l2=1+l=d2，所以用戶(hù)2必須在時(shí)間a2=1申請(qǐng)成功，否則用戶(hù)2需要收回申請(qǐng)。由于其無(wú)法在截止日期前完成作業(yè)，因此ODAA-VM只會(huì)為用戶(hù)1分配VM實(shí)例，并獲得價(jià)值υ（式（1））。另一方面，最優(yōu)離線(xiàn)算法將為用戶(hù)2分配資源，獲得價(jià)值Mυ+ε>M×υ。因此，ODAA-VM 算法的競(jìng)爭(zhēng)比為 η。

6 實(shí)驗(yàn)結(jié)果

通過(guò)對(duì)ODAA-VM和一種高性能離線(xiàn)算法的比較，證明ODAA-VM的優(yōu)缺點(diǎn)。

6.1 實(shí)驗(yàn)配置

[8]中的CA-Provision離線(xiàn)算法與本文的ODAA-VM進(jìn)行比較。CA-Provision算法解決了云環(huán)境下的動(dòng)態(tài)VM供應(yīng)和分配問(wèn)題。以固定時(shí)間間隔（如1 h）調(diào)用CA-Provision算法。當(dāng)調(diào)用時(shí)，該算法考慮上次間隔期間收集的所有申請(qǐng)，通過(guò)組合拍賣(mài)來(lái)確定申請(qǐng)成功的用戶(hù)、費(fèi)用及分配的VM實(shí)例數(shù)量。分配的VM實(shí)例只能使用一個(gè)時(shí)間間隔，用戶(hù)如果需要繼續(xù)訪(fǎng)問(wèn)資源，就必須繼續(xù)申請(qǐng)，直到滿(mǎn)足這些用戶(hù)的時(shí)間要求。如果需求量上升，則當(dāng)前分配給用戶(hù)的資源在以后可能被搶占。

本文使用的輸入來(lái)自于參考文獻(xiàn)[11]中的Parallel Workload Archive（并行工作負(fù)載數(shù)據(jù)庫(kù)）。表1給出了工作負(fù)載的日志信息及相關(guān)統(tǒng)計(jì)信息，前4列分別為工作負(fù)載日志的名稱(chēng)、日志的采集時(shí)間、作業(yè)數(shù)量及日志總小時(shí)數(shù)，第5列給出了生成日志的系統(tǒng)的處理器數(shù)量。假設(shè)VM實(shí)例的權(quán)重對(duì)應(yīng)于分配給該實(shí)例的處理器數(shù)量，則一個(gè)系統(tǒng)的處理器總數(shù)量表示計(jì)算資源的總權(quán)重s，將分配給工作負(fù)載ω的總體計(jì)算資源表示為Mω。表1的后4列表示相關(guān)統(tǒng)計(jì)數(shù)據(jù)：Jω表示每小時(shí)遞交給系統(tǒng)的平均作業(yè)數(shù)量；平均運(yùn)行時(shí)間Tω及單個(gè)作業(yè)的平均處理器數(shù)量Pω在計(jì)算時(shí)考慮工作負(fù)載日志的所有記錄；最后一列為負(fù)載ω的“正規(guī)化負(fù)載”ηω，其計(jì)算式為：

表1 工作負(fù)載日志

正規(guī)化負(fù)載用來(lái)衡量請(qǐng)求的平均資源量與可用的單位計(jì)算資源之間的相對(duì)關(guān)系，幫助對(duì)異構(gòu)工作負(fù)載進(jìn)行排序，并解釋部分實(shí)驗(yàn)結(jié)果。

表2 仿真參數(shù)

CA-Provision算法根據(jù)單個(gè)空閑VM實(shí)例的相關(guān)成本參數(shù)計(jì)算底價(jià)υres=cR-cI。雖然本文沒(méi)有給出帶有底價(jià)的ODAA-VM，但是通過(guò)拋棄低于底價(jià)的用戶(hù)，并對(duì)申請(qǐng)成功的用戶(hù)收取底價(jià)費(fèi)用而不是0費(fèi)用（ODAA-VM-Payment函數(shù)的第20行），即可集成底價(jià)策略。在本文實(shí)驗(yàn)中，ODAA-VM的底價(jià)與CA-Provision算法的底價(jià)相同。表2給出了所有參數(shù)值，對(duì)每個(gè)工作負(fù)載日志，基于不同的參數(shù)組合進(jìn)行18次實(shí)驗(yàn)。

6.2 結(jié)果分析

在圖1中總結(jié)了每個(gè)工作負(fù)載的結(jié)果。水平軸表示工作負(fù)載和正規(guī)化負(fù)載，垂直軸表示成功申請(qǐng)的用戶(hù)比例、每個(gè)成功申請(qǐng)的用戶(hù)的平均收入以及每個(gè)成功申請(qǐng)的用戶(hù)的平均效用。在圖1(a)中，ODAA-VM的用戶(hù)服務(wù)比例高于CA-Provision算法。最明顯的性能增益出現(xiàn)于日志 LLNLuBGL-2006（正規(guī)化負(fù)載 7.41）和 DAS2-fs0-2003（正規(guī)化負(fù)載2.01）中，且是這里使用的工作負(fù)載的最大值。DAS2-fs0-2003負(fù)載的用戶(hù)服務(wù)比例幾乎翻倍，LPC-EGEE-2004負(fù)載的用戶(hù)服務(wù)比例增長(zhǎng)將近6倍。這是因?yàn)樵贑A-Provision算法中，即使有可用資源，用戶(hù)也必須等待下次拍賣(mài)時(shí)間。那時(shí)，可能有更多用戶(hù)到達(dá)，因此該用戶(hù)可能拍賣(mài)失敗。此外，對(duì)于部分用戶(hù)來(lái)說(shuō)，即使在部分拍賣(mài)中取得成功，但是如果他們需要長(zhǎng)期占用資源來(lái)完成任務(wù)，將可能發(fā)生資源搶占，所以他們會(huì)選擇離開(kāi)。由于上述兩種工作負(fù)載增加了申請(qǐng)密度，所以導(dǎo)致拍賣(mài)數(shù)量上升，而ODAA-VM由于其在線(xiàn)設(shè)計(jì)，可以容納更多的申請(qǐng)。

從圖1（b）可知，每個(gè)成功申請(qǐng)用戶(hù)帶來(lái)的平均收益下降。由于在線(xiàn)算法根據(jù)不完全信息確定分配策略，所以無(wú)法實(shí)現(xiàn)收入最優(yōu)。一種直觀解釋就是ODAA-VM通過(guò)盡快做出分配決策，幫助用戶(hù)避免與后續(xù)用戶(hù)競(jìng)爭(zhēng)。對(duì)于CA-Provision算法，用戶(hù)必須與相同周期內(nèi)的其他用戶(hù)展開(kāi)競(jìng)爭(zhēng)，因此價(jià)格將會(huì)上升，但是成功申請(qǐng)用戶(hù)的數(shù)量上升彌補(bǔ)了收益損失。

從圖1（c）可以看出，ODAA-VM成功申請(qǐng)用戶(hù)的平均效用與CA-Provision算法相當(dāng)。雖然本文希望通過(guò)降低用戶(hù)支出提高用戶(hù)的效用，但是前提是兩次拍賣(mài)所選擇的分配用戶(hù)集合相同。這是不可能實(shí)現(xiàn)的，原因有兩點(diǎn)：一是CA-Provision算法會(huì)搶占價(jià)值較低的用戶(hù)，將資源分配給價(jià)值高的用戶(hù)，而ODAA-VM會(huì)把VM分配給用戶(hù)，并讓用戶(hù)在其所申請(qǐng)的整個(gè)時(shí)段內(nèi)使用資源，但是如果有價(jià)值更高的用戶(hù)到達(dá)，則這可能導(dǎo)致沒(méi)有可用資源，從而丟失該用戶(hù)；二是ODAA-VM中成功申請(qǐng)的用戶(hù)數(shù)量要多于CA-Provision算法，這說(shuō)明ODAA-VM容納了低價(jià)值用戶(hù)，而這些用戶(hù)導(dǎo)致平均效用較低。

總體來(lái)說(shuō)，本文認(rèn)為ODAA-VM提升了用戶(hù)和云供應(yīng)商的云體驗(yàn)，云供應(yīng)商服務(wù)了更多用戶(hù)，增加了用戶(hù)滿(mǎn)意度，最終增加了總體收入。

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

本文設(shè)計(jì)了一種云環(huán)境下VM在線(xiàn)供應(yīng)和分配算法。在該算法下，每當(dāng)有足夠多的資源和合適的申請(qǐng)，就會(huì)分配VM實(shí)例。本文算法對(duì)用戶(hù)具有激勵(lì)作用，且可在多項(xiàng)式時(shí)間內(nèi)運(yùn)行；可增加被服務(wù)的用戶(hù)數(shù)量，但是降低了平均收益，然而增加的用戶(hù)數(shù)量可以彌補(bǔ)平均收益損失。在未來(lái)工作中，將針對(duì)CA-Provision算法中用戶(hù)VM被搶占的情況，設(shè)置相應(yīng)的賠償代價(jià)，并將其再次與ODAA-VM進(jìn)行比較，觀察“用戶(hù)的平均收益”是否有所改進(jìn)。

圖1 CA-Provision算法和ODAA-VM的總體結(jié)果

參考文獻(xiàn)

1 劉正偉,文中領(lǐng),張海濤.云計(jì)算和云數(shù)據(jù)管理技術(shù).計(jì)算機(jī)研究與發(fā)展,2012,49(Z1):26～31

Liu Z W,Wen Z L,Zhang H T.Cloud computing and cloud data management technology.Journal of Computer Research and Development,2012,49(Z1):26～31

2 范杰,彭艦,黎紅友.基于蟻群算法的云計(jì)算需求彈性算法.計(jì)算機(jī)應(yīng)用,2011,31(1):1～4

Fan J,Peng J,Li H Y.Demand elasticity algorithm for cloud computing based on ant colony optimization algorithm.Journal of Computer Applications,2011,31(1):1～4

3 Lin W Y,Lin G Y,Wei H Y.Dynamic auction mechanism for cloud resource allocation.Proceedings of the 10th IEEE/ACM International Conference on Cluster,Cloud and Grid Computing(CCGrid),Melbourne,Australia,2010:591～592

4 ParkesD C,Singh S.An mdp-based approach toonline mechanism design.Proceedings of the 17th Annual Conference on Neural Information Processing Systems,Sydney,Australia,2003:1421～1426

5 Carroll T E,Grosu D.Incentive-compatible online scheduling of malleable parallel jobs with individual deadlines.Proceedings of the 39th International Conference on Parallel Processing,San Diego,CA,USA,2011:418～425

6 師雪霖,徐恪.云虛擬機(jī)資源分配的效用最大化模型.計(jì)算機(jī)學(xué)報(bào),2013,36(2):252～262

Shi X L,Xu K.Utility maximization model of virtual machine scheduling in cloud environment.Chinese Journal of Computers,2013,36(2):252～262

7 羅賀,孫錦波,胡笑旋等.云商務(wù)環(huán)境下的多源信息服務(wù)資源分配模型.計(jì)算機(jī)集成制造系統(tǒng),2013,19(10):137～142

Luo H,Sun J B,Hu X X,et al.Resource allocation model for multi-sources information service in cloud business.Computer Integrated Manufacturing Systems,2013,19(10):137～142

8 Zaman S,Grosu D.Combinatorial auction-based dynamic vm provisioning and allocation in clouds.Proceedings of IEEE 3rd International Conference on Cloud Computing Technology and Science(CloudCom),Athens,Greece,2011:107～114

9 Zaman S,Grosu D.A combinatorial auction-based mechanism for dynamic VM provisioningand allocation in clouds.IEEE Transactions on Cloud Computing,2013,1(2):129～141

10 Mu’alem A,Nisan N.Truthful approximation mechanisms for restricted combinatorialauctions.Proceedings ofthe 18th National Conference on Artificial Intelligence, Edmonton,Alberta,Canada,2002:379～384

11 Lublin U, Feitelson D G. The workload on parallel supercomputers:modeling the characteristics ofrigid jobs.Journal of Parallel and Distributed Computing,2003,63(11):1105～1122