結(jié)構(gòu)化P2P網(wǎng)絡(luò)訪問(wèn)熱點(diǎn)預(yù)測(cè)與負(fù)載均衡機(jī)制研究

杜 超，徐 蕾

(沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽(yáng) 110136)

基于DHT(Distributed Hash Table)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)具有自組織、擴(kuò)展性好等優(yōu)勢(shì)，進(jìn)而得到了廣泛的應(yīng)用。但在此環(huán)境下，由于節(jié)點(diǎn)的處理能力及用戶資源使用的不均衡，使P2P環(huán)境中的負(fù)載均衡成為一個(gè)突出、急需解決的問(wèn)題。

P2P環(huán)境中節(jié)點(diǎn)的工作負(fù)載是動(dòng)態(tài)變化的，負(fù)載均衡需要解決P2P環(huán)境中節(jié)點(diǎn)負(fù)載信息的采集，及節(jié)點(diǎn)出現(xiàn)過(guò)載時(shí)系統(tǒng)如何分擔(dān)過(guò)載節(jié)點(diǎn)的工作進(jìn)而實(shí)現(xiàn)P2P環(huán)境的負(fù)載均衡。現(xiàn)有的負(fù)載均衡策略，大都依賴P2P網(wǎng)絡(luò)中某些固定位置的節(jié)點(diǎn)收集負(fù)載信息并進(jìn)行熱點(diǎn)轉(zhuǎn)移，這種策略對(duì)負(fù)責(zé)收集負(fù)載信息的節(jié)點(diǎn)依賴性強(qiáng)，容易出現(xiàn)“單點(diǎn)失效”問(wèn)題；而過(guò)載節(jié)點(diǎn)的熱點(diǎn)轉(zhuǎn)移通常采用復(fù)制副本的方法，復(fù)制的副本數(shù)與副本的存放位置是這種策略需要解決的問(wèn)題。

文獻(xiàn)[1-2]提出利用多個(gè)哈希函數(shù)重定位指定系統(tǒng)中的副本資源數(shù)和存放位置，這種方法可以實(shí)現(xiàn)部分熱點(diǎn)資源的分布，但是承載熱點(diǎn)資源的節(jié)點(diǎn)負(fù)載仍然遠(yuǎn)大于一般節(jié)點(diǎn)；文獻(xiàn)[3-5]提出利用虛擬服務(wù)器局部信息調(diào)整負(fù)載的方法，但該方法是在結(jié)點(diǎn)超載時(shí)再執(zhí)行負(fù)載均衡算法，此時(shí)，負(fù)載均衡算法的開銷有可能加劇超載結(jié)點(diǎn)的過(guò)載程度，使算法響應(yīng)速度變慢，是一種被動(dòng)的負(fù)載均衡方法。文獻(xiàn)[6]提出在鄰居節(jié)點(diǎn)間進(jìn)行副本緩存，部分資源的查詢請(qǐng)求將轉(zhuǎn)由存有副本的鄰居節(jié)點(diǎn)來(lái)處理，進(jìn)而在一定程度上平衡負(fù)載；文獻(xiàn)[7]提出了P2P網(wǎng)絡(luò)性能及流量監(jiān)測(cè)模型,提出了適應(yīng)高速 P2P 網(wǎng)絡(luò)環(huán)境、擴(kuò)展性較好的P2P 網(wǎng)絡(luò)監(jiān)測(cè)模型；文獻(xiàn)[8]提出一種自適應(yīng)的負(fù)載均衡算法，能夠部分調(diào)整系統(tǒng)中節(jié)點(diǎn)的負(fù)載差異。

為避免結(jié)構(gòu)化P2P網(wǎng)絡(luò)中承載熱點(diǎn)資源的節(jié)點(diǎn)過(guò)載時(shí)再進(jìn)行系統(tǒng)的負(fù)載平衡，本文將查詢請(qǐng)求分析機(jī)制與緩存策略相結(jié)合，提出了一種負(fù)載均衡方案。方案利用資源的歷史訪問(wèn)信息對(duì)資源未來(lái)的訪問(wèn)量進(jìn)行預(yù)測(cè)，若可能成為熱點(diǎn)資源則提前進(jìn)行資源復(fù)制，并在資源的查詢路徑中存儲(chǔ)資源副本，進(jìn)而降低承載熱點(diǎn)資源節(jié)點(diǎn)的訪問(wèn)負(fù)載。實(shí)驗(yàn)結(jié)果表明，當(dāng)系統(tǒng)中文件查詢請(qǐng)求極不平衡的情況下，預(yù)測(cè)模型可以有效識(shí)別網(wǎng)絡(luò)中的文件訪問(wèn)熱點(diǎn)，結(jié)合網(wǎng)絡(luò)中的文件緩存策略，提高了P2P系統(tǒng)中文件訪問(wèn)的成功率，降低了文件訪問(wèn)響應(yīng)時(shí)間。

1 基于查詢請(qǐng)求分析的熱點(diǎn)預(yù)測(cè)模型

已有研究[10]表明，用戶資源查詢?cè)诮Y(jié)構(gòu)化P2P網(wǎng)絡(luò)中具有重復(fù)性，節(jié)點(diǎn)中文件的近期訪問(wèn)量對(duì)未來(lái)的訪問(wèn)趨勢(shì)具有較高的參考價(jià)值。因此根據(jù)節(jié)點(diǎn)中文件的近期訪問(wèn)量，選擇一個(gè)合適的預(yù)測(cè)模型對(duì)訪問(wèn)熱點(diǎn)進(jìn)行預(yù)測(cè)，可以更好地預(yù)防超載情況的發(fā)生。本文對(duì)比了三種預(yù)測(cè)模型對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)訪問(wèn)熱點(diǎn)的預(yù)測(cè)效果。

1.1 基于ARMA模型的預(yù)測(cè)

ARMA (p,q)模型是自回歸模型(AR模型)和滑動(dòng)平均模型(MA模型)的一般形式，ARMA(p,q)模型可表示為：

其中{yt}是平穩(wěn)的時(shí)間序列，φ1,…,φp是自回歸系數(shù)，θ1,…,θq是滑動(dòng)平均系數(shù)，εt,εt-1,…,ε1是誤差項(xiàng)；根據(jù)時(shí)間序列理論，通?？梢赃x擇模型ARMA(2n,2n-1)(n是正整數(shù))，為了減少計(jì)算量，本文采用模型ARMA(2,1)，模型可表示為yt=φ1yt-1+φ2yt-2+εt-θ1εt-1。

圖1 網(wǎng)絡(luò)節(jié)點(diǎn)中文件訪問(wèn)請(qǐng)求次數(shù)時(shí)間序列及平穩(wěn)化結(jié)果對(duì)比

ARMA是有限參數(shù)線性模型，采用矩估計(jì)方法估計(jì)ARMA(2,1)模型的參數(shù)。設(shè)利用有限時(shí)間序列{xi}(i=1,2，…,n)的樣本數(shù)據(jù)對(duì)ARMA(2,1)模型進(jìn)行數(shù)據(jù)擬合，樣本的自協(xié)方差函數(shù)為

樣本的自相關(guān)系數(shù)定義為得

Xt=1.274 2Xt-1-0.436 1Xt-2+εt-0.248 7εt-1

令ε0=0，利用遞推的方法逐步向前得出下一項(xiàng)誤差項(xiàng)。

1.2 基于BP網(wǎng)絡(luò)和一次指數(shù)平滑的預(yù)測(cè)

1)利用BP 網(wǎng)絡(luò)預(yù)測(cè)

采用三層結(jié)構(gòu)的BP(Back Propagation)神經(jīng)網(wǎng)絡(luò)對(duì)結(jié)構(gòu)化P2P網(wǎng)絡(luò)訪問(wèn)熱點(diǎn)進(jìn)行預(yù)測(cè)。設(shè)BP網(wǎng)絡(luò)的輸入層節(jié)點(diǎn)數(shù)是n，輸出層節(jié)點(diǎn)數(shù)是1(記為節(jié)點(diǎn)z)，隱層是一層結(jié)構(gòu)且節(jié)點(diǎn)數(shù)是m；BP的輸入層節(jié)點(diǎn)表示P2P網(wǎng)絡(luò)節(jié)點(diǎn)中某個(gè)文件n個(gè)T時(shí)間間隔的訪問(wèn)請(qǐng)求量，輸出層節(jié)點(diǎn)表示該文件下個(gè)時(shí)間單位訪問(wèn)請(qǐng)求量的預(yù)測(cè)值。以P2P網(wǎng)絡(luò)節(jié)點(diǎn)中文件訪問(wèn)請(qǐng)求量的時(shí)間序列{xi}作為BP網(wǎng)絡(luò)的學(xué)習(xí)數(shù)據(jù)。

BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法分為向前計(jì)算和向后的參數(shù)調(diào)整兩部分：

向后的參數(shù)調(diào)整主要是根據(jù)輸出層節(jié)點(diǎn)輸出值與輸出期望值之間的誤差調(diào)整網(wǎng)絡(luò)中邊的權(quán)值系數(shù)。設(shè)t表示輸出層節(jié)點(diǎn)z的輸出期望值，BP網(wǎng)絡(luò)的邊權(quán)值wij(前一層的第i個(gè)節(jié)點(diǎn)連接到下一層的第j個(gè)節(jié)點(diǎn)的邊上的權(quán)值)的調(diào)整公式為：wij(n+1)=wij(n)+η(n)oiδj

其中(n+1)和(n)表示迭代次數(shù)，oi是上層第i節(jié)點(diǎn)的輸出(若第i層是輸入層，則輸出值即為輸入值)，η是學(xué)習(xí)因子，計(jì)算方法為η(n)=η(n-1)+α(e(n)-e(n-1))/e(n)，其中e(n)=t-oz(n)是第n次迭代時(shí)期望輸出t與實(shí)際輸出oz(n)的誤差，用系數(shù)α調(diào)整誤差變化在η(n)調(diào)整中的影響；若j是輸出層節(jié)點(diǎn)z，δz=oz(1-oz)(t-oz)，若j是隱層節(jié)點(diǎn)δj=oj(1-oj)δzwjz。

利用文件訪問(wèn)請(qǐng)求的時(shí)間序列作為BP網(wǎng)絡(luò)的學(xué)習(xí)數(shù)據(jù)，并對(duì)BP網(wǎng)絡(luò)輸入層及隱層的不同節(jié)點(diǎn)數(shù)進(jìn)行誤差分析，本文選定誤差較小的5-15-1作為文件訪問(wèn)量預(yù)測(cè)的三層BP網(wǎng)絡(luò)結(jié)構(gòu)。

2)利用一次指數(shù)平滑模型預(yù)測(cè)以P2P網(wǎng)絡(luò)節(jié)點(diǎn)中文件在T時(shí)間間隔內(nèi)的訪問(wèn)請(qǐng)求量為基本單位，利用一次指數(shù)平滑預(yù)測(cè)模型對(duì)節(jié)點(diǎn)中第(t+1)時(shí)間單位內(nèi)的文件訪問(wèn)量yt+1進(jìn)行預(yù)測(cè)，可表示為：

2 熱點(diǎn)文件副本復(fù)制算法

根據(jù)第2節(jié)預(yù)測(cè)出P2P網(wǎng)絡(luò)節(jié)點(diǎn)中文件的訪問(wèn)量，若訪問(wèn)量的預(yù)測(cè)值達(dá)到或者超過(guò)警戒值，就認(rèn)為該文件是熱點(diǎn)訪問(wèn)文件。對(duì)預(yù)測(cè)到的熱點(diǎn)文件按照一定的策略創(chuàng)建和復(fù)制副本文件。

文件的訪問(wèn)量預(yù)測(cè)是根據(jù)文件的已知訪問(wèn)量完成的，節(jié)點(diǎn)中需要保存每個(gè)文件的訪問(wèn)信息，在節(jié)點(diǎn)中保存一組文件的訪問(wèn)數(shù)據(jù)，如表1所示。

表1給出的文件訪問(wèn)數(shù)據(jù)主要是為文件的訪問(wèn)量預(yù)測(cè)服務(wù)的；其中文件F的反向節(jié)點(diǎn)定義為：設(shè)P2P網(wǎng)絡(luò)中文件F的存放節(jié)點(diǎn)是a，某個(gè)節(jié)點(diǎn)b在請(qǐng)求查找文件F時(shí)，按照結(jié)構(gòu)化P2P查找規(guī)則找到節(jié)點(diǎn)a的查找路徑中最后經(jīng)過(guò)節(jié)點(diǎn)是c，則c是a的反向節(jié)點(diǎn)；文件的反向節(jié)點(diǎn)數(shù)據(jù)包括反向節(jié)點(diǎn)的IP地址和查找文件經(jīng)過(guò)的次數(shù)n。熱點(diǎn)文件的副本主要存放在該文件的反向節(jié)點(diǎn)中。在節(jié)點(diǎn)中可以設(shè)置專門的副本存放位置(稱為副本復(fù)制區(qū))，可便于副本的撤銷。

表1 P2P網(wǎng)絡(luò)節(jié)點(diǎn)保存的文件訪問(wèn)節(jié)點(diǎn)數(shù)據(jù)

為保持在節(jié)點(diǎn)加入或離開動(dòng)態(tài)變化后結(jié)構(gòu)化P2P網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性，網(wǎng)絡(luò)中節(jié)點(diǎn)要定期執(zhí)行結(jié)構(gòu)的穩(wěn)定性算法，這樣，熱點(diǎn)文件的預(yù)測(cè)和副本復(fù)制也可以是節(jié)點(diǎn)周期性執(zhí)行的算法。描述如下：

1)node.Cache() {//節(jié)點(diǎn)Node中運(yùn)行的文件副本復(fù)制算法；

2)初始化線性表L；

3)for( node中每個(gè)存儲(chǔ)的文件Fi)

4)if(Fi.numi> File_access_max) add(L,Fi);//文件Fi訪問(wèn)次數(shù)大于文件訪問(wèn)閾值，

文件Fi的標(biāo)識(shí)加入線性表L

5)for(線性表中每個(gè)存儲(chǔ)的文件Fi) {

6)Fi_pred=access_pred(Fi，Method)；//利用Method模型對(duì)文件Fi下一時(shí)間

區(qū)間的訪問(wèn)量進(jìn)行預(yù)測(cè)；

7)if(Fi_pred>hot_limit) { //預(yù)測(cè)的文件訪問(wèn)量超過(guò)熱點(diǎn)閾值

8)copy_num=(N*Numi/Total)>M? M:(N*Numi/Total);//按文件Fi訪問(wèn)量與

//與節(jié)點(diǎn)文件的總訪問(wèn)量比計(jì)算副本的數(shù)量，副本數(shù)不能超過(guò)反向節(jié)點(diǎn)數(shù)。

9)for(j=1;j<=copy_num;j++) copy( Fi,(IPj,nj))；//向反向節(jié)點(diǎn)j副本復(fù)制區(qū)復(fù)制Fi

10)}

11)}

12)}

算法中的文件訪問(wèn)量預(yù)測(cè)模型Method可以是前面介紹的三種模型之一。

具有副本復(fù)制策略的結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)請(qǐng)求查找文件F時(shí)，在查找路徑節(jié)點(diǎn)的副本復(fù)制區(qū)首先查找F，若存在，查找終止；否則沿路徑查找直到找到存放文件F的節(jié)點(diǎn)v，此時(shí)需更新節(jié)點(diǎn)v上F文件訪問(wèn)計(jì)數(shù)、節(jié)點(diǎn)Total計(jì)數(shù)及文件F的反向節(jié)點(diǎn)數(shù)據(jù)。

熱點(diǎn)文件具有階段性特征，一段時(shí)間后可能變成非熱點(diǎn)文件。P2P網(wǎng)絡(luò)中節(jié)點(diǎn)可以在一定時(shí)間間隔內(nèi)定期執(zhí)行熱點(diǎn)文件副本刪除算法，算法主要檢查節(jié)點(diǎn)中的副本復(fù)制區(qū)，采用“最近最少使用算法(LRU)”刪除很少使用的副本。

3 實(shí)驗(yàn)結(jié)果與分析

設(shè)計(jì)仿真實(shí)驗(yàn)評(píng)估不同預(yù)測(cè)模型的預(yù)測(cè)效果，并驗(yàn)證副本復(fù)制算法在解決P2P網(wǎng)絡(luò)的熱點(diǎn)問(wèn)題的有效性。實(shí)驗(yàn)基于典型的結(jié)構(gòu)化P2P網(wǎng)絡(luò)結(jié)構(gòu)chord，按照chord結(jié)構(gòu)的構(gòu)成方法均勻的分布網(wǎng)絡(luò)中的資源，chord結(jié)構(gòu)中節(jié)點(diǎn)id位長(zhǎng)是16，網(wǎng)絡(luò)中的可區(qū)別的資源數(shù)(不含副本)為節(jié)點(diǎn)數(shù)的5倍以上，熱點(diǎn)資源占總資源數(shù)的1/10。在仿真實(shí)驗(yàn)中，隨機(jī)產(chǎn)生的網(wǎng)絡(luò)中節(jié)點(diǎn)文件查詢事件服從N(0,10，2)的高斯分布；實(shí)驗(yàn)主要是針對(duì)熱點(diǎn)預(yù)測(cè)與副本復(fù)制，因此選用的是穩(wěn)定的網(wǎng)絡(luò)結(jié)構(gòu)。

ARMA和BP模型需要利用實(shí)驗(yàn)數(shù)據(jù)進(jìn)行訓(xùn)練，設(shè)BP模型的初始參數(shù)η=0.2，α=0.5，一次指數(shù)平滑模型的參數(shù)a=0.7。利用仿真實(shí)驗(yàn)中前2000次訪問(wèn)對(duì)ARMA與BP模型進(jìn)行訓(xùn)練，不斷進(jìn)行擬合，ARMA模型從第1200次左右誤差趨于平穩(wěn)。BP模型從第1800次開始訓(xùn)練誤差保持了平穩(wěn)。

為測(cè)試系統(tǒng)處理資源訪問(wèn)請(qǐng)求不均勻情況的能力，實(shí)驗(yàn)中設(shè)置節(jié)點(diǎn)資源訪問(wèn)事件中，80%的資源訪問(wèn)請(qǐng)求是針對(duì)熱點(diǎn)資源的；設(shè)置的文件訪問(wèn)閾值和熱點(diǎn)閾值為File_access_max=10，hot_limit=15。

在熱點(diǎn)預(yù)測(cè)時(shí)間方面，ARMA模型預(yù)測(cè)100個(gè)實(shí)驗(yàn)數(shù)據(jù)需要1.749秒，而BP模型預(yù)測(cè)100個(gè)實(shí)驗(yàn)數(shù)據(jù)需要0.085秒，一次指數(shù)平滑模型預(yù)測(cè)100個(gè)實(shí)驗(yàn)數(shù)據(jù)只需要0.049秒。各模型性能對(duì)比如表2所示。三種預(yù)測(cè)模型下平均響應(yīng)時(shí)間對(duì)比如圖2所示，頻繁訪問(wèn)熱點(diǎn)資源時(shí)的訪問(wèn)成功率對(duì)比如圖3所示。

三種預(yù)測(cè)模型在減少文件訪問(wèn)的響應(yīng)時(shí)間和提高訪問(wèn)成功率方面效果顯著。ARMA模型的預(yù)測(cè)時(shí)間要長(zhǎng)于其他兩種模型，但其預(yù)測(cè)效果好，文件訪問(wèn)的平均響應(yīng)時(shí)間小，訪問(wèn)成功率相對(duì)較高；由圖3中可以看出，在系統(tǒng)仿真的開始階段，隨著熱點(diǎn)資源訪問(wèn)量的增加，訪問(wèn)成功率會(huì)有一個(gè)下降的過(guò)程，而后隨著系統(tǒng)對(duì)熱點(diǎn)的識(shí)別和預(yù)測(cè)，訪問(wèn)成功率不斷升高并趨于穩(wěn)定，而ARMA與BP模型由于在訓(xùn)練階段就與仿真數(shù)據(jù)基本達(dá)到擬合，訪問(wèn)成功率比較穩(wěn)定。

表2 不同預(yù)測(cè)模型性能比較

圖2 不同規(guī)模下頻繁訪問(wèn)熱點(diǎn)資源的平均響應(yīng)時(shí)間

圖3 頻繁訪問(wèn)熱點(diǎn)資源時(shí)訪問(wèn)成功率對(duì)比

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

本文提出結(jié)構(gòu)化P2P網(wǎng)絡(luò)中訪問(wèn)熱點(diǎn)的預(yù)測(cè)及實(shí)現(xiàn)負(fù)載均衡的副本復(fù)制方法。實(shí)驗(yàn)對(duì)比了三種訪問(wèn)熱點(diǎn)預(yù)測(cè)模型在結(jié)構(gòu)化網(wǎng)絡(luò)chord中的仿真效果，三種模型能有效提高文件訪問(wèn)的成功率，縮短文件的響應(yīng)時(shí)間；且ARMA模型比其余兩種模型具有更好的性能。

文件的副本復(fù)制策略雖然在一定程度上增加了系統(tǒng)存儲(chǔ)量和更新開銷，但復(fù)制的文件副本從某種意義上降低了熱點(diǎn)文件的熱度及文件所在節(jié)點(diǎn)的負(fù)載。副本文件的存儲(chǔ)量是動(dòng)態(tài)變化的，當(dāng)熱點(diǎn)文件不在是訪問(wèn)熱點(diǎn)時(shí)，過(guò)期的副本會(huì)從系統(tǒng)中被刪除。

參考文獻(xiàn)(References)：

[1] Xia Ye,Chen Shigang,Korgaonkar V.Load balancing with multiple hash functions in peer-to-peer networks[C].Proc.of the 12th International Conf.on Paralleland Distributed Systems.Washington D.C.,USA:IEEE Press,2006.

[2] Byers J，Considine J，Mitzenmacher M.Simple load balancing for distributed hash tables[C].In：Kaashock MF，Stoica I，ads.LNCS.Berlin：Springer-Verlag，2003:80-87.

[3] Zhu Y.Load Balancing in Structured P2P Networks[M].Handbook of Peer-to-Peer Networking.Springer US,2010:1149-1164.

[4] XiaoHai W,YuXing P,DongSheng L.An efficient load balancing method for constant degree P2P systems[C].Computer Design and Applications (ICCDA),2010 International Conference on.IEEE,2010,5:V5-316-V5-319.

[5] Takeda A,Oide T,Takahashi A.New structured p2p network with dynamic load balancing scheme[C].Advanced Information Networking and Applications (WAINA),2011 IEEE Workshops of International Conference on.IEEE,2011:108-113.

[6] 劉柯萍,危韌勇,谷 科.一種解決P2P網(wǎng)絡(luò)路由熱點(diǎn)問(wèn)題的策略[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(6):108-111.

[7] 李江濤，雷振明.P2P網(wǎng)絡(luò)性能測(cè)度及監(jiān)測(cè)系統(tǒng)模型[J].北京郵電大學(xué)學(xué)報(bào),2006,29(3):17-21.

[8] 熊偉,謝冬青,焦炳旺,等.一種結(jié)構(gòu)化 P2P 協(xié)議中的自適應(yīng)負(fù)載均衡方法[J].軟件學(xué)報(bào),2009,20(3):660-670.

[9] 陳蓉.話務(wù)量分析和多種預(yù)測(cè)模型的比較研究 [D].北京:北京郵電大學(xué),2008.

[10] Stutzbach D,Rejaie R,Sen S.Characterizing unstructured overlay topologies in modern P2P file-sharing systems [J].Networking,IEEE/ACM Transactions on,2008,16(2):267-280.

[11] Box GEP,Jenkins GM,Reinsel GC.Time series analysis:forecasting and control [M].Wiley.com,2013.

[12] Ghosh B,Basu B,O'Mahony M.Multivariate short-term traffic flow forecasting using time-series analysis[J].Intelligent Transportation Systems,IEEE Transactions on,2009,10(2):246-254.