謝紀(jì)東，武繼剛

廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

1 引言

數(shù)據(jù)網(wǎng)格已經(jīng)廣泛應(yīng)用在科學(xué)研究中，其目的是將許多分布遙遠(yuǎn)的存儲(chǔ)資源連接起來，以方便網(wǎng)格用戶分享數(shù)據(jù)[1]，這種數(shù)據(jù)一般需要消耗大量存儲(chǔ)以至于無法集中存儲(chǔ)在一個(gè)節(jié)點(diǎn)中[2]。

一般而言，計(jì)算密集型的應(yīng)用需要用到大量數(shù)據(jù)，尤其在科學(xué)計(jì)算型應(yīng)用[3-4]，比如高能物理[5]、天氣模擬以及衛(wèi)星圖像處理等[6-7]。而且隨著最近一段時(shí)間數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的發(fā)展，越來越多的數(shù)據(jù)需要進(jìn)行復(fù)雜的實(shí)驗(yàn)和分析。

然而，由于硬件成本的限制，在本地存儲(chǔ)和維護(hù)大量數(shù)據(jù)的代價(jià)有時(shí)是難以接受的，而如果將數(shù)據(jù)全部放置在遠(yuǎn)程服務(wù)器中，比如云端[8-9]，由于網(wǎng)絡(luò)帶寬的限制，取回?cái)?shù)據(jù)的時(shí)間代價(jià)又太大，因此副本放置技術(shù)應(yīng)運(yùn)而生，副本技術(shù)利用用戶對(duì)文件請(qǐng)求的歷史數(shù)據(jù)，利用有限的本地存儲(chǔ)資源只存儲(chǔ)用戶最需要文件的副本，而所有文件的原本存儲(chǔ)在云端，這樣不僅能有效利用本地存儲(chǔ)資源，也能充分利用云端的資源，同時(shí)方便共享數(shù)據(jù)資源。

本文通過改進(jìn)文獻(xiàn)[10]中對(duì)文件熱度的定義，利用間隔執(zhí)行機(jī)制以及異步策略來設(shè)計(jì)算法，算法由兩部分組成，一部分是全局算法，負(fù)責(zé)收集各個(gè)集群的用戶文件請(qǐng)求計(jì)算候選副本，另一部分為局部（本地）算法，由集群中心控制，局部算法負(fù)責(zé)放置副本到合適位置以適應(yīng)集群網(wǎng)絡(luò)環(huán)境。本文主要有3點(diǎn)貢獻(xiàn)：

（1）通過邊際分析方法改進(jìn)了文獻(xiàn)[10]中對(duì)文件流行度的定義從而能選擇更合適的候選副本。

（2）通過異步機(jī)制，分而治之的思想重構(gòu)文獻(xiàn)[10]中的算法。

（3）通過高斯分布、冪律分布來模擬用戶行為進(jìn)行模擬實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文提出的策略有效改善了網(wǎng)絡(luò)傳輸環(huán)境。

2 相關(guān)工作

副本技術(shù)的兩個(gè)主要挑戰(zhàn)：副本的選擇和副本放置。副本選擇主要負(fù)責(zé)選擇用戶最需要的副本，而一般用流行度表示用戶需要的迫切程度。副本放置主要負(fù)責(zé)將副本放置到網(wǎng)絡(luò)中最合適的節(jié)點(diǎn)以使用戶在請(qǐng)求文件時(shí)能擁有較小的網(wǎng)絡(luò)延遲和帶寬消耗[11]。

文件流行度的概念主要用來描述文件被需要的程度，大部分方法[1,10,12-19]都利用文件的請(qǐng)求頻率來定義文件流行度。

文獻(xiàn)[12]提出了最近請(qǐng)求文件最大權(quán)重算法（latest access largest weight，LALW）。該算法對(duì)不同的文件請(qǐng)求計(jì)算不同的權(quán)重，時(shí)間越近的請(qǐng)求擁有越大的權(quán)重，這樣能使用戶最近的偏好得以凸顯。文獻(xiàn)[15]提出了基于主動(dòng)刪除技術(shù)的最近請(qǐng)求最大權(quán)算法（closest access greatest weight with proactive deletion，CAGWPD），該算法基于歷史請(qǐng)求記錄以及主動(dòng)刪除技術(shù)，通過設(shè)置閾值來控制副本數(shù)量，選擇文件流行度大于平均流行度的文件作為副本。這種方式能更加有效地利用資源節(jié)點(diǎn)的存儲(chǔ)容量。文獻(xiàn)[18]提出了公平分享算法（fair-share replication，F(xiàn)SR），該方法通過平衡資源節(jié)點(diǎn)的工作量和存儲(chǔ)容量來更有效地放置副本到合適的節(jié)點(diǎn)。這幾種方法都沒有考慮到用戶的行為變化對(duì)系統(tǒng)的影響，在定義文件熱度時(shí)，其偏向于將小文件作為副本進(jìn)行放置，而忽略了大文件的傳輸能顯著影響網(wǎng)絡(luò)傳輸條件的事實(shí)。

流行文件優(yōu)先復(fù)制算法（popular file replicate first，PFRF）由文獻(xiàn)[1]提出，該算法基于星型拓?fù)渚W(wǎng)絡(luò)，在節(jié)點(diǎn)存儲(chǔ)資源有限的情況下通過歷史文件請(qǐng)求判斷文件熱度并進(jìn)行副本放置，其采用間隔執(zhí)行的算法運(yùn)行機(jī)制充分考慮了用戶行為變化，并進(jìn)行了復(fù)雜的實(shí)驗(yàn)來評(píng)測(cè)PFRF算法。但是其文件熱度定義和之前的工作一樣，偏向于選擇小文件，同樣忽略了大文件請(qǐng)求對(duì)網(wǎng)絡(luò)造成的影響。

改進(jìn)的流行文件優(yōu)先復(fù)制算法（improved popular file replicate first，IPFRF）由文獻(xiàn)[10]提出，該算法同樣基于間隔執(zhí)行的運(yùn)行機(jī)制，所謂間隔執(zhí)行，即將時(shí)間劃分為等間隔時(shí)間段，算法會(huì)在一個(gè)時(shí)間段結(jié)束時(shí)運(yùn)行。這種機(jī)制有利于動(dòng)態(tài)調(diào)整副本選擇和放置。IPFRF改進(jìn)了PFRF中沒有考慮節(jié)點(diǎn)地理位置而進(jìn)行副本放置的缺點(diǎn)。IPFRF通過調(diào)節(jié)文件請(qǐng)求權(quán)重，對(duì)集群進(jìn)行個(gè)性化推薦，增加副本刪除機(jī)制更加有效利用了本地存儲(chǔ)資源，提高了副本命中率，有效減少了網(wǎng)絡(luò)平均延遲和消耗帶寬。但是由于IPFRF的算法需要等待收集所有集群的信息才能進(jìn)行計(jì)算，一旦有集群離線，系統(tǒng)會(huì)發(fā)生不可預(yù)知錯(cuò)誤，缺乏健壯性，同樣由于和PFRF采用了相似的文件熱度定義，對(duì)大文件的請(qǐng)求不敏感。

基于以上缺點(diǎn)，本文提出了一種改進(jìn)流行度的基于間隔執(zhí)行機(jī)制的異步文件副本放置策略。本文從三方面對(duì)IPFRF進(jìn)行了改進(jìn)。第一，通過對(duì)文件請(qǐng)求產(chǎn)生的邊際延遲分析，大文件在一定條件下需要進(jìn)行優(yōu)先放置，而不是一味地用文件請(qǐng)求密度來進(jìn)行定義造成在選擇副本時(shí)偏好小文件的問題。第二，通過異步機(jī)制打破同步算法所帶來的低容錯(cuò)缺點(diǎn)。第三，本文引入高斯分布來模擬用戶對(duì)文件請(qǐng)求的行為變化。

3 系統(tǒng)模型

3.1 拓?fù)浣Y(jié)構(gòu)

本文模型和文獻(xiàn)[10]保持一致，如圖1，整個(gè)模型由m個(gè)集群和一個(gè)主站（master site）組成，主節(jié)點(diǎn)通過GRC（global replica controller）和各個(gè)集群交流，主站包含所有文件，即其容量足夠大總是能存儲(chǔ)所有文件。主站一般是專業(yè)的存儲(chǔ)服務(wù)提供者，比如存儲(chǔ)云等。每個(gè)集群都有本地副本控制服務(wù)器LRC（local replica controller），通過集群內(nèi)部路由和集群內(nèi)各個(gè)資源節(jié)點(diǎn)相連，資源節(jié)點(diǎn)容量有限，只能存儲(chǔ)一部分文件。

集群內(nèi)資源節(jié)點(diǎn)地理分布較為接近，而集群之間地理分布較為遙遠(yuǎn)。此模型由樹形拓?fù)浜?jiǎn)化而來，文獻(xiàn)[1]已證明其合理性。每個(gè)集群內(nèi)部的LRC負(fù)責(zé)管理存儲(chǔ)在集群中資源節(jié)點(diǎn)中的副本，并提供策略在適當(dāng)?shù)臅r(shí)間和位置存儲(chǔ)副本，由于服務(wù)器容量有限，同時(shí)也要在適當(dāng)?shù)臅r(shí)機(jī)刪除一部分不太重要的副本，為后續(xù)更重要的副本騰出空間。

用戶通過向存儲(chǔ)服務(wù)器發(fā)出副本請(qǐng)求來獲取副本，如果本地服務(wù)器中沒有對(duì)應(yīng)副本，則需要從遠(yuǎn)程服務(wù)器中請(qǐng)求對(duì)應(yīng)文件。當(dāng)副本放置策略無法有效滿足用戶需求時(shí)，遠(yuǎn)程服務(wù)器需要滿足大量用戶需求，而受限于網(wǎng)絡(luò)帶寬，用戶獲取文件的延遲有可能會(huì)變得非常大，因此，可以通過在此模型上模擬多種用戶偏好變化來檢測(cè)副本放置策略的有效性。

3.2 評(píng)價(jià)指標(biāo)

評(píng)價(jià)指標(biāo)包括三部分：平均請(qǐng)求延遲、平均消耗帶寬、副本發(fā)現(xiàn)比率。

平均請(qǐng)求延遲。請(qǐng)求延遲反映了用戶下載文件的時(shí)長(zhǎng)，延遲越大，用戶需要等待越久。平均請(qǐng)求延遲越小，證明越多的文件請(qǐng)求在本地得到滿足，副本放置算法越有效。

Fig.1 Simulation topology圖1 模擬系統(tǒng)拓?fù)浣Y(jié)構(gòu)

平均消耗帶寬。文件消耗帶寬根據(jù)文件大小和傳輸時(shí)經(jīng)過的中間節(jié)點(diǎn)數(shù)量計(jì)算，文件傳輸帶寬消耗越大，表示文件越大或者需要經(jīng)過越多的中間節(jié)點(diǎn)。平均文件消耗帶寬越小，副本放置算法越有效。

副本發(fā)現(xiàn)比率。驗(yàn)證副本放置算法是否有效的直接指標(biāo)，就是計(jì)算副本命中率。命中率越高，表示集群內(nèi)部的副本能滿足更多的請(qǐng)求。但是副本發(fā)現(xiàn)率在文獻(xiàn)[10]提出的算法下對(duì)小文件有明顯的偏心。雖然副本發(fā)現(xiàn)率能在一定程度上反映算法的有效性，但是不一定能反映網(wǎng)絡(luò)傳輸環(huán)境的改善情況。比如，當(dāng)副本服務(wù)器的容量一定時(shí)，文獻(xiàn)[10]的算法更偏向于選擇體積較小的文件作為副本，因此，副本服務(wù)器能放置更多的副本，自然能擁有更大的副本命中率。但是，網(wǎng)絡(luò)的擁塞，體積較大的文件的傳輸產(chǎn)生的影響不可忽視。同時(shí)，由于大文件的邊際延遲更大，如果只是偏向于對(duì)小文件放置副本，網(wǎng)絡(luò)中每增加一次對(duì)大文件的請(qǐng)求，網(wǎng)絡(luò)傳輸環(huán)境惡化得更嚴(yán)重，邊際延遲將在第4章詳述。

4 流行度定義和算法

IPFRF是一個(gè)基于間隔執(zhí)行機(jī)制（round-based）的副本放置策略，它將時(shí)間分成固定長(zhǎng)度的時(shí)間片段，在每個(gè)時(shí)間片段結(jié)束時(shí)，它會(huì)采取4個(gè)步驟來進(jìn)行副本放置。第一步，IPFRF從所有集群收集文件請(qǐng)求信息。第二步，IPFRF計(jì)算每個(gè)文件在對(duì)應(yīng)集群中的流行度，然后再取平均作為文件的全局流行度。第三步，將每個(gè)集群中請(qǐng)求的文件按照流行度降序排序，并且選擇排名靠前的一定數(shù)量的文件作為候選副本。第四步，IPFRF根據(jù)集群中資源節(jié)點(diǎn)的地理位置分布、容量和已有副本，將候選副本放置到最合適的資源節(jié)點(diǎn)中。本文從兩方面對(duì)IPFRF進(jìn)行了優(yōu)化：文件流行度定義和算法結(jié)構(gòu)。

4.1 文件流行度

文件流行度是一個(gè)評(píng)價(jià)文件是否應(yīng)該被復(fù)制到集群中資源節(jié)點(diǎn)的重要因素，IPFRF對(duì)文件流行度(FPi,c,n)的定義：

其中，Ri,c,n為集群c在第n個(gè)時(shí)間間隔對(duì)文件i收集的請(qǐng)求次數(shù)；TRn為第n個(gè)時(shí)間間隔內(nèi)對(duì)所有集群收集的文件請(qǐng)求總數(shù)；FSi為文件i的大?。籥是一個(gè)常量，在文獻(xiàn)[10]中并沒有顯式給出，本文根據(jù)文獻(xiàn)[1]進(jìn)行取值。IPFRF中平均流行度（APi,n）的定義如下：

其中，noc表示集群數(shù)量。IPFRF的文件熱度定義考慮了文件數(shù)量、文件大小，其權(quán)重也根據(jù)不同集群不同時(shí)期的總需求量動(dòng)態(tài)變化。但是仍然有不足之處。本文通過邊際分析方法，重新對(duì)文件熱度進(jìn)行了定義。定義邊際延遲（marginal delay，MD）如下：

其中，nor表示文件傳輸過程中經(jīng)過的路由數(shù)量；Bi,i+1表示從發(fā)送節(jié)點(diǎn)i到接收節(jié)點(diǎn)i+1的網(wǎng)絡(luò)帶寬；Di,i+1表示從發(fā)送節(jié)點(diǎn)i到接收節(jié)點(diǎn)i+1的距離；在真實(shí)環(huán)境下，k和m的取值是一定的。

所謂邊際延遲，即網(wǎng)絡(luò)中每增加一個(gè)文件請(qǐng)求所增加的傳輸和發(fā)送延遲。顯而易見的是，一個(gè)請(qǐng)求對(duì)兩個(gè)大小不一的文件所造成的延遲是不一樣的，文件越大，所造成的延遲越多，因此，網(wǎng)絡(luò)中每增加一個(gè)對(duì)于大文件的請(qǐng)求所造成的延遲，遠(yuǎn)大于網(wǎng)絡(luò)中每增加一個(gè)對(duì)小文件請(qǐng)求所造成的延遲。即大文件的邊際延遲大于小文件的邊際延遲，雖然網(wǎng)絡(luò)中對(duì)于大文件的請(qǐng)求不一定比小文件多，但是其重復(fù)傳輸所產(chǎn)生的延遲依然很大。比如：現(xiàn)有兩個(gè)文件存儲(chǔ)在主站中，文件大小如表1。

Table 1 Files'information表1 文件信息

用戶對(duì)文件的請(qǐng)求需要經(jīng)過兩次路由才能到達(dá)，假設(shè)用戶在兩個(gè)時(shí)間段內(nèi)都對(duì)兩個(gè)文件進(jìn)行了請(qǐng)求，網(wǎng)絡(luò)帶寬為100 Mb/s，傳播延遲相等，請(qǐng)求數(shù)量如表2。

Table 2 The first interval表2 第一次間隔

按照IPFRF的計(jì)算方式，文件A和文件B的流行度如表3所示（因?yàn)閭鞑パ舆t相等，所以只計(jì)算發(fā)送延遲，每個(gè)文件的初始流行度都為0.5，a=0.5）。

Table 3 Result after the first interval表3 第一次間隔后結(jié)果

如表3由于文件A的流行度遠(yuǎn)大于文件B，因此IPFRF選擇將文件A作為候選副本，但是由邊際分析可知，文件B的額外請(qǐng)求會(huì)造成更多延遲，雖然文件B比文件A需要更多存儲(chǔ)空間，但是在一定條件下，需要優(yōu)先放置文件B。按照IPFRF的方法將文件A作為副本放置后，第二個(gè)時(shí)間間隔假設(shè)用戶對(duì)文件A和文件B的請(qǐng)求數(shù)量和第一個(gè)時(shí)間間隔一樣，第二個(gè)時(shí)間間隔產(chǎn)生的延遲如表4。

Table 4 Delay caused by files using IPFRF in the 2nd interval表4 IPFRF第二個(gè)間隔產(chǎn)生延遲

如果第一輪不放置文件A為副本，而選擇B為副本時(shí)，第二個(gè)時(shí)間間隔產(chǎn)生延遲如表5。

Table 5 If replicate file B表5 假設(shè)為文件B創(chuàng)建副本

由此可見，IPFRF在流行度定義上仍有不足，通過邊際延遲考慮文件大小對(duì)延遲的影響，本文定義改進(jìn)的流行度如下：

其中，GFPi,n表示全局流行度；Ri,n表示第n個(gè)時(shí)間間隔文件i在所有集群中的請(qǐng)求次數(shù)；Rn表示所有文件在所有集群中的總請(qǐng)求次數(shù)；LFPi,c,n表示集群c中文件i在第n個(gè)時(shí)間間隔的本地流行度；MDi表示文件i的邊際延遲；0≤a≤1。如果采用本文流行度定義，則上文舉例中第一個(gè)間隔結(jié)束后結(jié)果如表6。

Table 6 Result by refined definition表6 按本文熱度定義結(jié)果

4.2 算法

IPFRF算法僅由主站完成副本選擇和放置任務(wù)，這種集中式的算法不利于負(fù)載均衡且容錯(cuò)性較低，因此本文重新設(shè)計(jì)了算法框架，將副本選擇和放置任務(wù)交給LRC執(zhí)行，而GRC負(fù)責(zé)收集全局信息并記錄維護(hù)全局流行度表。算法中符號(hào)意義如表7。

Table 7 Symbol table表7 符號(hào)表

GRC算法（算法1）由兩部分組成，第一部分從各個(gè)集群中收集文件請(qǐng)求。第二部分利用歷史文件流行度表以及新的文件請(qǐng)求更新文件流行度表，然后排降序。

貪心算法（算法2）負(fù)責(zé)根據(jù)文件大小、文件流行度貪心選擇出候選副本。然后再將候選副本交由LRC算法，根據(jù)對(duì)應(yīng)節(jié)點(diǎn)剩余容量、已有副本、文件流行度來放置副本，如果節(jié)點(diǎn)剩余容量充足，就直接將副本傳輸?shù)綄?duì)應(yīng)節(jié)點(diǎn)，如果節(jié)點(diǎn)剩余存儲(chǔ)容量不足，就根據(jù)文件大小和文件流行度的比較看是否值得替換已有文件副本。

LRC算法（算法3）為各個(gè)集群分別運(yùn)行的算法，主要負(fù)責(zé)本集群的文件請(qǐng)求信息收集以及候選副本的選擇和放置。經(jīng)過式（4）計(jì)算文件流行度后排降序。

算法1收集文件請(qǐng)求，維護(hù)全局流行度

算法3副本選擇和放置

4.3 存取模式

文獻(xiàn)[10]使用了兩種偏好模式來模擬用戶的存取行為，第一種為均勻分布，如圖2。第二種為Zipf，均勻分布對(duì)文件基本無偏好，如圖3。可以檢測(cè)算法在一般條件下的性能，Zipf分布能模擬用戶帶偏好的文件請(qǐng)求。所謂用戶偏好，即用戶對(duì)不同文件的喜好，比如一部分用戶更偏向于使用視頻文件，另一部分用戶偏向于使用文本文件或者音頻文件，不同類型的用戶擁有不同的偏好。

Zipf分布中，不同集群的用戶擁有不同偏好，第一個(gè)集群中的用戶對(duì)文件0～20的文件更加喜好。第二個(gè)集群中對(duì)文件50～70的文件更加喜好。每個(gè)集群在每一個(gè)時(shí)間間隔都有不同的喜好。前兩種存取模式應(yīng)用在文獻(xiàn)[10]中用來測(cè)試IPFRF算法的有效性。本文引入第三種存取模式：高斯分布來模擬用戶偏好行為，如圖4。

高斯分布的曲線沒有Zipf分布陡峭，能比較好地適應(yīng)當(dāng)用戶從無偏好狀態(tài)逐漸轉(zhuǎn)移到有偏好狀態(tài)的情況。

Fig.2 Average distribution圖2 平均分布

Fig.3 Zipf distribution圖3 Zipf分布

Fig.4 Normal distribution圖4 高斯分布

均勻分布中用戶對(duì)文件無特定偏好，用戶對(duì)文件的請(qǐng)求次數(shù)總是在固定值上下小范圍波動(dòng)。

為了確保每一個(gè)時(shí)間間隔的用戶偏好動(dòng)態(tài)變化，每一次生成用戶對(duì)文件的請(qǐng)求時(shí)進(jìn)行一定程度的平移：

其中，F(xiàn)ID為實(shí)際生成的文件ID；GID為由不同的存取模式生成的文件ID；T為文件數(shù)量。

5 實(shí)驗(yàn)

5.1 模擬實(shí)驗(yàn)

模擬實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為星型拓?fù)?，模擬參數(shù)如表8。

Table 8 Simulation parameters表8 模擬參數(shù)

每個(gè)集群內(nèi)部的LRC負(fù)責(zé)管理存儲(chǔ)在集群中資源節(jié)點(diǎn)中的副本，并提供策略在適當(dāng)?shù)臅r(shí)間和位置存儲(chǔ)副本，由于服務(wù)器容量有限，同時(shí)也要在適當(dāng)?shù)臅r(shí)機(jī)刪除一部分不太重要的副本，為后續(xù)更重要的副本騰出空間。

所有集群都和主站連接，集群之間無直接連接。為方便實(shí)驗(yàn)，假設(shè)主站容量為無限大，實(shí)際上，在現(xiàn)實(shí)生活中可以認(rèn)為其為云端。本文的網(wǎng)絡(luò)拓?fù)浜臀墨I(xiàn)[10]保持一致。模擬請(qǐng)求次數(shù)表示用戶總共發(fā)出的文件請(qǐng)求次數(shù)。模擬將會(huì)分4次進(jìn)行，每一次模擬的時(shí)間間隔100次，每一次時(shí)間間隔中產(chǎn)生的文件數(shù)量可以代表時(shí)間長(zhǎng)短，數(shù)量越多，任務(wù)時(shí)間間隔越長(zhǎng)。4次模擬文件請(qǐng)求總數(shù)分別為200 000、400 000、800 000、1 600 000次，在不同壓力下來檢測(cè)算法的有效性。集群內(nèi)的資源節(jié)點(diǎn)和LRC連接，資源節(jié)點(diǎn)之間無直接連接。常量a的取值根據(jù)文獻(xiàn)[1]，由于IPFRF中沒有對(duì)a的顯示賦值，也無常量a取值的討論，因此參考PFRF算法中對(duì)a的取值。

對(duì)集群地理位置的模擬采用以下公式在模擬時(shí)生成：

其中，region為集群偏移量；offset為集群內(nèi)資源節(jié)點(diǎn)的偏移量；(x,y)為資源節(jié)點(diǎn)的位置。

5.2 模擬實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)利用Java多線程編程實(shí)現(xiàn)。實(shí)驗(yàn)分三部分進(jìn)行：第一部分模擬用戶請(qǐng)求行為符合均勻分布時(shí)的場(chǎng)景；第二部分模擬用戶請(qǐng)求行為符合Zipf分布時(shí)的場(chǎng)景；第三部分模擬用戶請(qǐng)求符合高斯分布時(shí)的場(chǎng)景，每個(gè)場(chǎng)景進(jìn)行8次實(shí)驗(yàn)取平均為最后實(shí)驗(yàn)結(jié)果。

第一場(chǎng)景為均勻分布場(chǎng)景，各個(gè)集群的用戶不會(huì)產(chǎn)生特定偏好，由于差異較小，算法容易產(chǎn)生誤判斷導(dǎo)致最后結(jié)果較差，但是從表9和表10可以看出本文提出的算法策略較IPFRF仍有一定程度的提升。由于文件請(qǐng)求數(shù)量差異性較小，因此由本文基于邊際分析定義的流行度能選擇邊際延遲較大的文件放置副本，而IPFRF偏向選擇小文件，雖然能放置更多副本，但是在請(qǐng)求數(shù)量差異較小的情況下，體積較大的文件產(chǎn)生的延遲遠(yuǎn)大于體積較小的文件產(chǎn)生的延遲。

Table 9 Average latency表9 平均文件延遲

Table 10 Average bandwidth表10 平均帶寬消耗

第二場(chǎng)景為Zipf分布，從其分布圖中可以看出，各個(gè)集群的用戶帶有非常強(qiáng)烈的不同偏好，這種帶有非常強(qiáng)烈偏好的用戶一般為老用戶。在此情境下，只需要預(yù)測(cè)命中少量的副本即可大幅度降低文件延遲，在資源節(jié)點(diǎn)容量有限的情況下，IPFRF達(dá)到了很好的性能，但是同樣在副本命中率相似的情況下，優(yōu)先大文件的放置相比優(yōu)先小文件的放置能減少更多的延遲。

第三場(chǎng)景為高斯分布。這種情境適合新用戶到老用戶的過渡階段，帶有偏好但是對(duì)其他不同類型文件懷有好奇心，因此偏好差異沒有Zipf劇烈。在這種情況下不僅考驗(yàn)算法的副本命中率，而且需要平衡文件大小和存儲(chǔ)容量對(duì)資源節(jié)點(diǎn)的影響。

6 結(jié)束語

本文通過邊際分析方法，改進(jìn)了IPFRF利用請(qǐng)求密度(即文件請(qǐng)求數(shù)除以文件體積)來定義文件流行度的方法，IPFRF的定義偏向于選擇體積較小的文件，而實(shí)際情況大文件在同等情況下會(huì)產(chǎn)生更大的延遲。本文根據(jù)邊際延遲分析重新定義了文件流行度。同時(shí)，根據(jù)IPFRF的算法框架過于中心化的缺點(diǎn)，將副本放置算法分成兩部分分別在GRC和LRC處執(zhí)行，分散了主站的壓力并將副本選擇和放置任務(wù)交給集群自己處理，更能適應(yīng)集群偏好變化，而主站對(duì)全局流行度的把握能更好地預(yù)防經(jīng)驗(yàn)錯(cuò)誤，提高副本選擇的準(zhǔn)確性。最后本文通過傳統(tǒng)的兩種存取模型模擬用戶行為變化之外，引入了第三種分布模型：高斯分布，更能反映新老用戶交替的文件請(qǐng)求的行為變化。但是本文提出的算法仍有不足之處，比如算法所適用拓?fù)淠Ｐ捅容^局限，算法框架仍然屬于中心式，但是集群和主站的異步交互方式讓算法擁有良好的可擴(kuò)展性。算法實(shí)驗(yàn)環(huán)境也需要在真實(shí)的用戶網(wǎng)絡(luò)中進(jìn)行檢測(cè)和驗(yàn)證。隨著CDN和P2P的發(fā)展，如何在更加復(fù)雜的網(wǎng)絡(luò)上部署副本放置技術(shù)也成為本文未來的研究方向。