面向任務(wù)服務(wù)質(zhì)量的網(wǎng)絡(luò)資源需求預(yù)測(cè)算法*

劉林 張東

（91202部隊(duì) 葫蘆島 125004）

1 引言

云計(jì)算是一個(gè)用時(shí)付費(fèi)的模型，用戶根據(jù)這個(gè)模型按需獲取各種可配置，可共享的虛擬資源。其中資源映射是云計(jì)算中相對(duì)復(fù)雜且重要的關(guān)鍵技術(shù)。當(dāng)用戶提出任務(wù)時(shí)，并不知道自己的任務(wù)需求需要什么以及多少虛擬資源。一般情況下，用戶都盡可能地選擇更多更好的資源，遠(yuǎn)遠(yuǎn)超過他們的需求，因此產(chǎn)生了過度供應(yīng)問題。此外，用戶選擇的資源不足的話，也會(huì)導(dǎo)致任務(wù)失敗，其Qos指標(biāo)沒法保障。資源映射的目的是為了實(shí)現(xiàn)用戶需求到虛擬資源的映射，以此來保證用戶所需要的服務(wù)質(zhì)量。如果云平臺(tái)能自動(dòng)預(yù)測(cè)用戶任務(wù)的網(wǎng)絡(luò)資源需求，在滿足任務(wù)的服務(wù)質(zhì)量情況下，并利用網(wǎng)絡(luò)資源匹配技術(shù)選擇最合適的網(wǎng)絡(luò)資源來完成任務(wù)，為用戶提供性價(jià)比高的服務(wù)，也提高了網(wǎng)絡(luò)資源利用率，這是一個(gè)很有意義的研究問題。

目前，也有很多基于Qos的任務(wù)網(wǎng)絡(luò)資源需求預(yù)測(cè)的解決方案。田啟華［1］等提出了利用層次分析法（AHP）來構(gòu)造資源分配矩陣，從而確定資源分配權(quán)重系數(shù)。但利用層次分析法最后得到的結(jié)果是每個(gè)任務(wù)對(duì)總資源需求的占比，不能準(zhǔn)確地預(yù)測(cè)任務(wù)需求的資源。

吳世山［2］利用神經(jīng)網(wǎng)絡(luò)對(duì)程序資源消耗預(yù)測(cè)，以影響程序運(yùn)行所需要的各項(xiàng)因素作為神經(jīng)網(wǎng)絡(luò)的輸入，以程序運(yùn)行所消耗的資源作為網(wǎng)絡(luò)輸出。預(yù)測(cè)器不斷收集程序運(yùn)行的歷史數(shù)據(jù)作為神經(jīng)網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)，從而實(shí)現(xiàn)對(duì)新應(yīng)用進(jìn)行預(yù)測(cè)。但該方法前提是歷史任務(wù)已經(jīng)分門別類地存儲(chǔ)在預(yù)測(cè)系統(tǒng)里，并且已經(jīng)知道新任務(wù)的類別。這在云計(jì)算上是十分困難的，因?yàn)樵朴?jì)算任務(wù)類型是繁多復(fù)雜的，需要在任務(wù)預(yù)測(cè)之前用相應(yīng)的算法對(duì)任務(wù)進(jìn)行分類。

Sarka等［3］采用了混合克隆檢測(cè)技術(shù)預(yù)測(cè)云計(jì)算中的任務(wù)資源需求，將歷史任務(wù)執(zhí)行過程中的資源消耗存儲(chǔ)在數(shù)據(jù)庫里。利用克隆技術(shù)尋找與新任務(wù)資源消耗模式相似的歷史任務(wù)。找到相似的歷史任務(wù)后，根據(jù)實(shí)際情況選用回歸的方法預(yù)測(cè)新任務(wù)的資源需求。但克隆技術(shù)多基于源碼分析，是不利于在公有云環(huán)境上推廣應(yīng)用的。

趙春燕［4］提出了一種分配性正義的伯格模型，用一般期待來約束資源選擇。根據(jù)任務(wù)的Qos指標(biāo)提供給任務(wù)特定的一般期待資源向量去尋找合適的虛擬機(jī)資源來完成任務(wù)。任務(wù)完成后利用公平評(píng)判函數(shù)來修正期待資源向量。這種算法實(shí)現(xiàn)簡單，利于推廣。該算法的核心是如何根據(jù)任務(wù)得到合適的一般期待資源向量，期待資源向量的好壞影響著整個(gè)預(yù)測(cè)調(diào)度系統(tǒng)的性能，但文獻(xiàn)中沒有提到怎么獲取準(zhǔn)確的一般期待資源向量。

目前的研究大都實(shí)現(xiàn)了任務(wù)服務(wù)質(zhì)量指標(biāo)到虛擬資源的映射。輸入給定任務(wù)的關(guān)鍵描述和任務(wù)的服務(wù)質(zhì)量需求，通過機(jī)器學(xué)習(xí)等技術(shù)預(yù)測(cè)任務(wù)的網(wǎng)絡(luò)資源需求，但目的只是預(yù)測(cè)網(wǎng)絡(luò)資源需求的多少，網(wǎng)絡(luò)資源利用率提升有限。網(wǎng)絡(luò)資源需求預(yù)測(cè)算法性能的好壞取決于找到相似歷史任務(wù)的網(wǎng)絡(luò)資源消耗的精確程度和調(diào)度框架提供的反饋機(jī)制。因此，任務(wù)完成后，需要一種反饋機(jī)制去判定網(wǎng)絡(luò)資源分配是否公平合理，從而提高網(wǎng)絡(luò)資源需求預(yù)測(cè)的準(zhǔn)確程度，提高網(wǎng)絡(luò)資源的使用率，實(shí)現(xiàn)一個(gè)最優(yōu)的面向任務(wù)的網(wǎng)絡(luò)資源調(diào)度過程。

綜上所述，本文提出了一種面向任務(wù)網(wǎng)絡(luò)資源需求預(yù)測(cè)的網(wǎng)絡(luò)資源映射框架。為了解決云計(jì)算任務(wù)類型眾多異構(gòu)等問題，首先對(duì)歷史執(zhí)行和待完成任務(wù)服務(wù)質(zhì)量識(shí)別后，從歷史任務(wù)集合中搜索相同類別的任務(wù)建模利用強(qiáng)化學(xué)習(xí)進(jìn)行預(yù)測(cè)。在任務(wù)完成后，設(shè)計(jì)了兩種反饋信息來提高預(yù)測(cè)的精確度，更接近實(shí)際的任務(wù)需求。一種是隱式反饋來表示任務(wù)是否完成，另一種是顯式反饋來表示任務(wù)完成實(shí)際用了多少網(wǎng)絡(luò)資源。若分配的網(wǎng)絡(luò)資源大于實(shí)際所用的網(wǎng)絡(luò)資源，則更新歷史任務(wù)消耗網(wǎng)絡(luò)資源數(shù)據(jù)庫。

2 基于強(qiáng)化學(xué)習(xí)的網(wǎng)絡(luò)資源需求預(yù)測(cè)

2.1 總體方案

我們所提的方案是基于強(qiáng)化學(xué)習(xí)自動(dòng)預(yù)測(cè)任務(wù)所需求的網(wǎng)絡(luò)資源。圖1為整個(gè)方案的流程。首先，我們根據(jù)Qos指標(biāo)對(duì)進(jìn)行任務(wù)分類，本文參考了完成時(shí)間，帶寬，可靠性，費(fèi)用四個(gè)Qos參數(shù)。

圖1 預(yù)測(cè)任務(wù)網(wǎng)絡(luò)資源需求的調(diào)度過程

當(dāng)對(duì)待執(zhí)行任務(wù)進(jìn)行合理的分類后，向網(wǎng)絡(luò)資源預(yù)測(cè)器輸入待執(zhí)行的任務(wù)。網(wǎng)絡(luò)資源預(yù)測(cè)器基于歷史執(zhí)行任務(wù)預(yù)測(cè)該任務(wù)所需要的虛擬網(wǎng)絡(luò)資源。然后，網(wǎng)絡(luò)資源分配器將這些任務(wù)分配給合適的可用網(wǎng)絡(luò)資源。一旦任務(wù)成功完成，預(yù)測(cè)器收集反饋信息來更新數(shù)據(jù)庫的信息。如果由于網(wǎng)絡(luò)資源容量不足而導(dǎo)致作業(yè)終止失敗，則它們將由用戶重新提交或由調(diào)度系統(tǒng)自動(dòng)執(zhí)行?？傊擃A(yù)測(cè)器的主要目標(biāo)是釋放未使用的網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)資源的利用率。

2.2 網(wǎng)絡(luò)資源需求預(yù)測(cè)算法

預(yù)測(cè)任務(wù)需求網(wǎng)絡(luò)資源取決于兩種主要因素：一是精確得到歷史相似任務(wù)需求網(wǎng)絡(luò)資源的能力；二是調(diào)度器里的反饋機(jī)制。為了做到準(zhǔn)確且自動(dòng)地預(yù)測(cè)任務(wù)網(wǎng)絡(luò)資源需求，本算法使用強(qiáng)化學(xué)習(xí)進(jìn)行預(yù)測(cè)。強(qiáng)化學(xué)習(xí)是一種通過代理探索狀態(tài)空間來學(xué)習(xí)行為策略的學(xué)習(xí)算法，此外代理通過修改其行動(dòng)政策來最大化自己的累積獎(jiǎng)勵(lì)。強(qiáng)化學(xué)習(xí)還可以很好地應(yīng)用反饋信息得到更精準(zhǔn)的平均實(shí)際網(wǎng)絡(luò)資源需求。

而當(dāng)任務(wù)完成后，需要收集任務(wù)的反饋信息。本算法中反饋信息有兩種。一種是隱式反饋信息，一種是顯式反饋信息。隱式反饋信息反映了任務(wù)是否能完成；顯式反饋包含任務(wù)終止時(shí)使用的實(shí)際網(wǎng)絡(luò)資源量。我們收集并報(bào)告此信息給預(yù)測(cè)器，當(dāng)隱式反饋認(rèn)為該任務(wù)完成，預(yù)測(cè)器就根據(jù)顯式反饋信息來改進(jìn)預(yù)測(cè)近似值并更接近實(shí)際的工作網(wǎng)絡(luò)資源需求。

此外，我們提出了分類和回歸兩種方法，通過使用非線性的感知來估計(jì)工作要求。在根據(jù)準(zhǔn)確的反饋信息下，感知機(jī)試圖估計(jì)實(shí)際網(wǎng)絡(luò)資源要求，之后決定是否使用當(dāng)前的網(wǎng)絡(luò)資源完成任務(wù)?；趶?qiáng)化學(xué)習(xí)預(yù)測(cè)算法的如下：

1）初始化感知機(jī)關(guān)于任務(wù)特征向量x的權(quán)重向量ω，p表示目前已經(jīng)成功執(zhí)行的任務(wù)率，設(shè)置其為0.5。

2）逐個(gè)分析已經(jīng)分類好待執(zhí)行的任務(wù)。預(yù)測(cè)當(dāng)前分析的任務(wù)的網(wǎng)絡(luò)資源需求量E'，如果E'小于可用的網(wǎng)絡(luò)資源能力E，則就提交任務(wù)去執(zhí)行。否則轉(zhuǎn)到步驟3）。

3）設(shè)置一個(gè)隨機(jī)數(shù) rand ，其值范圍為［0，1］。若 rand＞ep/τ+e(1-p)/τ，則利用當(dāng)前僅有網(wǎng)絡(luò)資源執(zhí)行任務(wù)，其中τ為強(qiáng)化學(xué)習(xí)的衰減常數(shù)。否則，返回任務(wù)給用戶。

4）當(dāng)任務(wù)執(zhí)行完成后，根據(jù)式（1）收集反饋信息：

其中U為實(shí)際任務(wù)使用的網(wǎng)絡(luò)資源。

5）設(shè)置 z=E'，為更新目前任務(wù)權(quán)重向量ω作準(zhǔn)備。

6）根據(jù)式（2）計(jì)算關(guān)于ω的導(dǎo)數(shù)：

7）利用以下兩個(gè)公式更新權(quán)重向量ω的值：

8）更新任務(wù)成功完成率 p值。

雖然，即使現(xiàn)有的網(wǎng)絡(luò)資源不能滿足估計(jì)的網(wǎng)絡(luò)資源，但我們認(rèn)為任務(wù)也有一定概率能完成的。所以設(shè)置一個(gè)閾值來決定是否用僅有的網(wǎng)絡(luò)資源來執(zhí)行任務(wù)。這個(gè)閾值決定于任務(wù)完成率p。這個(gè)過程是強(qiáng)化學(xué)習(xí)的探索階段。

根據(jù)反饋信息我們可以得到任務(wù)執(zhí)行情況。如果任務(wù)成功執(zhí)行則報(bào)告所用的網(wǎng)絡(luò)資源，否則報(bào)告最大的分配網(wǎng)絡(luò)資源量。最后根據(jù)執(zhí)行結(jié)果更新感知機(jī)的權(quán)重向量和探索閾值，不斷近似最小網(wǎng)絡(luò)資源供給方案。由于云計(jì)算每天處理的任務(wù)的數(shù)量是巨大的，用這種學(xué)習(xí)方式得到基于Qos的任務(wù)需求預(yù)測(cè)是可行的。

3 實(shí)驗(yàn)與仿真

3.1 評(píng)估指標(biāo)

本文中，為了驗(yàn)證本文提出網(wǎng)絡(luò)資源需求預(yù)測(cè)模型的性能，選取自回歸模型、指數(shù)平滑算法以及本文中的考慮反饋的綜合預(yù)測(cè)模型分別進(jìn)行預(yù)測(cè)，并選取以下3種不同的評(píng)價(jià)指標(biāo)對(duì)比各模型的預(yù)測(cè)性能。

1）平均絕對(duì)百分比誤差MAPE，用于衡量預(yù)測(cè)模型對(duì)網(wǎng)絡(luò)資源需求預(yù)測(cè)誤差的情況。計(jì)算公式如下：

其中，N為測(cè)量次數(shù)，xt為真實(shí)值，x't為預(yù)測(cè)值。算法的MAPE越小，說明預(yù)測(cè)值和真實(shí)值的偏差越小。

2）均方根誤差RMSE，是預(yù)測(cè)值和真實(shí)值之差的平方和的開方與測(cè)量次數(shù)N的比值，它表示預(yù)測(cè)數(shù)據(jù)與真實(shí)數(shù)據(jù)的偏離程度。

3）節(jié)點(diǎn)負(fù)載利用率，用來衡量每個(gè)節(jié)點(diǎn)的負(fù)載情況，計(jì)算公式如下：

其中，TT為總的運(yùn)行時(shí)間。此外，我們定義任務(wù)負(fù)載率Task Load來衡量提交任務(wù)數(shù)量，其值越大，表示調(diào)度器中任務(wù)的數(shù)量越多，計(jì)算公式如下：

其中，任務(wù)到達(dá)時(shí)間為 ai（i=1，2，…，N），每一個(gè)節(jié)點(diǎn)Mi運(yùn)行時(shí)間為Ti秒；MT為運(yùn)行節(jié)點(diǎn)的總數(shù)。在開始階段，系統(tǒng)沒到達(dá)飽和時(shí)候利用率是線性增長的，當(dāng)系統(tǒng)飽和點(diǎn)處節(jié)點(diǎn)利用率越高說明算法性能越好。

3.2 仿真結(jié)果

在我們的試驗(yàn)中，我們從一個(gè)高性能計(jì)算平臺(tái)上收集數(shù)據(jù)，構(gòu)建了一個(gè)真實(shí)的任務(wù)網(wǎng)絡(luò)資源請(qǐng)求數(shù)據(jù)集合。選用了其中3/4作為訓(xùn)練集，1/4作為測(cè)試集。為了說明本算法的性能，將本算法與自回歸預(yù)測(cè)模型［5］，基于徑向量神經(jīng)網(wǎng)絡(luò)［6］預(yù)測(cè)模型作對(duì)比。

表1 三種網(wǎng)絡(luò)資源需求預(yù)測(cè)模型的MAPE和RMSE仿真參數(shù)

由表1可知，由于本文的預(yù)測(cè)算法利用反饋機(jī)制不斷近似得到實(shí)際的網(wǎng)絡(luò)資源值，使得其預(yù)測(cè)結(jié)果的誤差較小，擬合程度也很高。

為了檢驗(yàn)各個(gè)預(yù)測(cè)模型的網(wǎng)絡(luò)資源利用情況，仿真中我們通過改變?nèi)蝿?wù)負(fù)載率變化節(jié)點(diǎn)負(fù)載利用率來衡量算法使用網(wǎng)絡(luò)資源的效率。我們?cè)O(shè)置了1024個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有不同MB的物理內(nèi)存，便于簡便論證我們方案的性能，我們僅利用節(jié)點(diǎn)內(nèi)存的利用情況進(jìn)行仿真實(shí)驗(yàn)分析。

如圖2所示，各個(gè)預(yù)測(cè)模型一開始由于系統(tǒng)的網(wǎng)絡(luò)資源充足負(fù)載利用率都呈線性增長。當(dāng)任務(wù)量到達(dá)0.5時(shí)候，就慢慢接近飽和。但由于本算法考慮了預(yù)測(cè)網(wǎng)絡(luò)資源大于可用網(wǎng)絡(luò)資源也有可能完成任務(wù)的情況，因此負(fù)載利用率更高，另一方面也說明預(yù)測(cè)的精確性更高。

圖2 算法負(fù)載利用率對(duì)比

通過實(shí)驗(yàn)結(jié)果的比較和分析可知，本文提出的基于強(qiáng)化學(xué)習(xí)的預(yù)測(cè)模型在預(yù)測(cè)的準(zhǔn)確性和性能方面表現(xiàn)的更好，與真實(shí)值的擬合程度更高。與傳統(tǒng)的自回歸和神經(jīng)網(wǎng)絡(luò)算法相比，本文的算法在預(yù)測(cè)效果和預(yù)測(cè)精度方面都有所提高。

4 結(jié)語

針對(duì)難以實(shí)現(xiàn)任務(wù)Qos到虛擬網(wǎng)絡(luò)資源的映射，本文提出了一種自動(dòng)預(yù)測(cè)任務(wù)資源需求的算法。與目前大部分算法不同的是，我們通過反饋機(jī)制提供一個(gè)近似最小化的資源供給方案。盡管用戶不知道要實(shí)現(xiàn)任務(wù)需要什么虛擬資源，但可以通過本算法的學(xué)習(xí)系統(tǒng)自動(dòng)地精確預(yù)測(cè)任務(wù)需要的實(shí)際資源。仿真結(jié)果表明，我們算法有很高的預(yù)測(cè)精準(zhǔn)度，提高了資源利用率，降低了服務(wù)成本的同時(shí)還實(shí)現(xiàn)了用戶的任務(wù)需求。