p2p網(wǎng)絡(luò)中基于動(dòng)態(tài)our算法的負(fù)載均衡技術(shù)

p2p網(wǎng)絡(luò)中基于動(dòng)態(tài)our算法的負(fù)載均衡技術(shù)

1結(jié)構(gòu)與非結(jié)構(gòu)化p2p系統(tǒng)p2p系統(tǒng)越來(lái)越多地用于數(shù)據(jù)處理、資源交換、信息管理、共享等領(lǐng)域。然而，隨著問(wèn)題的普及，這種負(fù)荷補(bǔ)償也出現(xiàn)了。節(jié)點(diǎn)之間如何均勻組織負(fù)載？系統(tǒng)性能的質(zhì)量取決于問(wèn)題的答案。由于不平衡，p2p系統(tǒng)帶來(lái)了許多性能問(wèn)題，如此期間的延誤。因此，負(fù)荷補(bǔ)償已成為p2p系統(tǒng)研究的一個(gè)重要問(wèn)題。一些p2p系統(tǒng)，如燒香、幻燈片和胡同，通過(guò)提供一組有序的噪聲補(bǔ)償機(jī)制來(lái)平衡噪聲，并且在理想的環(huán)境中提供了相同的性能。所有文件都具有相同的訪問(wèn)頻率，因此生成的節(jié)點(diǎn)是統(tǒng)一的。然而，現(xiàn)實(shí)系統(tǒng)是不同的。事實(shí)上，由于節(jié)點(diǎn)性能的不同結(jié)構(gòu)和熱點(diǎn)文件的存在，負(fù)荷仍然存在。對(duì)于一些非結(jié)構(gòu)的p2p系統(tǒng)，如gilla，節(jié)點(diǎn)沒(méi)有顯示身份的唯一標(biāo)識(shí)，并且沒(méi)有與其他節(jié)點(diǎn)相關(guān)的信息。它只能通過(guò)網(wǎng)絡(luò)上的洪水信息來(lái)定位資源，這大大增加了網(wǎng)絡(luò)負(fù)荷。為了解決這些問(wèn)題，許多文獻(xiàn)在非結(jié)構(gòu)pm系統(tǒng)的基礎(chǔ)上引入了超級(jí)節(jié)點(diǎn)。超級(jí)節(jié)點(diǎn)是能力強(qiáng)的節(jié)點(diǎn)，每個(gè)超節(jié)點(diǎn)管理著一些普通節(jié)點(diǎn)。這些普通節(jié)點(diǎn)和管理的普通節(jié)點(diǎn)構(gòu)成一個(gè)群體（或組）。每個(gè)普通節(jié)點(diǎn)都是唯一的身份標(biāo)識(shí)符，并且每個(gè)普通節(jié)點(diǎn)都管理著一些普通節(jié)點(diǎn)。超級(jí)節(jié)點(diǎn)和他們管理的普通節(jié)點(diǎn)構(gòu)成一個(gè)群體（或組）。每個(gè)普通節(jié)點(diǎn)都有一個(gè)唯一的身份標(biāo)識(shí)符，并且希望向組織中的超節(jié)點(diǎn)提供信息。通過(guò)定期溝通，超節(jié)點(diǎn)之間交換彼此的信息。本文提出了兩種通過(guò)副本策略處理負(fù)載平衡的技術(shù):周期性的副本策略(PeriodicReplicationPolicy,簡(jiǎn)稱PRP)和基于需求的副本策略(Demand-basedReplicationPolicy,簡(jiǎn)稱DRP).在PRP中,超節(jié)點(diǎn)周期性地傳遞那些全局被訪問(wèn)頻率高的文件副本到遠(yuǎn)程的超節(jié)點(diǎn),從而降低了搜索文件的跳數(shù).當(dāng)一個(gè)超節(jié)點(diǎn)收到一個(gè)文件副本時(shí),它會(huì)在一定范圍內(nèi)通知它的鄰居超節(jié)點(diǎn).與PRP不同,DRP是基于當(dāng)?shù)氐脑L問(wèn)頻率的,而不是像PRP那樣從全局來(lái)考慮的.如果一個(gè)超節(jié)點(diǎn)所在組對(duì)某個(gè)文件的訪問(wèn)頻率超過(guò)了一定的值,那么這個(gè)超節(jié)點(diǎn)將會(huì)保留這個(gè)文件副本在本組內(nèi).2理想的副本策略近來(lái)已經(jīng)有很多文獻(xiàn)提出了P2P環(huán)境下的副本策略,如文獻(xiàn).它們主要討論的副本策略如下:·統(tǒng)一分配策略:在P2P網(wǎng)絡(luò)中,所有的文件的副本數(shù)目都是相同的.·正比策略:每個(gè)文件的副本數(shù)目與它被查詢的概率成正比關(guān)系.·平方根策略:每個(gè)文件的副本數(shù)目與它被查詢的概率的平方根成正比關(guān)系.統(tǒng)一分配策略沒(méi)有考慮文件流行程度,對(duì)于熱門文件來(lái)說(shuō),系統(tǒng)中存儲(chǔ)的副本數(shù)可能并不能滿足查詢的需求,容易造成瓶頸問(wèn)題.而對(duì)于訪問(wèn)量比較少的文件來(lái)說(shuō),它們副本的利用率很低,浪費(fèi)了存儲(chǔ)空間.正比策略和平方根策略考慮了文件流行度的差別,使得副本的利用率得到了提高,但是為了存儲(chǔ)流行度的相關(guān)信息,每個(gè)節(jié)點(diǎn)的負(fù)擔(dān)大大加重了.在P2P網(wǎng)絡(luò)中,負(fù)載平衡是衡量其性能的一個(gè)重要因素,越來(lái)越多的文獻(xiàn),如針對(duì)這個(gè)方面進(jìn)行了研究.提出了一種通過(guò)副本策略來(lái)達(dá)到負(fù)載平衡的策略.它通過(guò)文件的流行程度來(lái)確定副本數(shù)目,并且通過(guò)定義多個(gè)哈希函數(shù)來(lái)使得每個(gè)副本被訪問(wèn)的頻率盡量接近,從而達(dá)到負(fù)載平衡.但是因?yàn)樗肓硕鄠€(gè)哈希函數(shù),在選擇副本的時(shí)候就要付出更多的代價(jià).3副策略本節(jié)主要來(lái)討論副本策略的兩種算法的實(shí)現(xiàn)策略—周期性的副本策略和基于需求的副本策略.3.1周期流特征在文件副本策略下的展現(xiàn)在周期性的副本策略里,每個(gè)超節(jié)點(diǎn)都保存著該組里所有文件被訪問(wèn)頻率的信息.如果一個(gè)文件被訪問(wèn)的頻率超過(guò)了某一個(gè)預(yù)先定義的值,那么該文件的一個(gè)副本就會(huì)被拷貝到一個(gè)訪問(wèn)此文件頻率最高的超節(jié)點(diǎn)所在的組內(nèi).當(dāng)這個(gè)超節(jié)點(diǎn)接收到文件副本后,它將根據(jù)當(dāng)前組內(nèi)節(jié)點(diǎn)的空間剩余情況,選擇一個(gè)剩余存儲(chǔ)空間最大的普通節(jié)點(diǎn)來(lái)存儲(chǔ)該文件副本,然后通知它的鄰居節(jié)點(diǎn)這個(gè)文件副本所在地的信息.為了減輕網(wǎng)絡(luò)的負(fù)擔(dān),它只通知一定范圍內(nèi)的鄰居超節(jié)點(diǎn).在這種副本策略里,超節(jié)點(diǎn)之間需要周期性地更新彼此的信息,如圖1所示.圖1顯示了周期性副本策略的操作過(guò)程.超節(jié)點(diǎn)SP1,SP5等請(qǐng)求某個(gè)文件i,假定該文件在超節(jié)點(diǎn)SP6所在組內(nèi)命中,SP6將檢查該文件i的訪問(wèn)頻率是否超過(guò)了預(yù)先定義的閾值,如果檢測(cè)到文件i的訪問(wèn)頻率高于這個(gè)閾值,那么SP6將拷貝一個(gè)副本發(fā)送給訪問(wèn)文件i頻率最高的超節(jié)點(diǎn)(這里我們假定SP1訪問(wèn)文件i的頻率最高).SP1收到這個(gè)文件副本后,將把該文件副本保存在本組內(nèi)剩余空間最多的普通節(jié)點(diǎn)Pi上,并在一定范圍內(nèi)通知其鄰居超節(jié)點(diǎn).3.2基于需求副本策略在基于需求的副本策略里,每個(gè)超節(jié)點(diǎn)都記錄著本組內(nèi)所有普通節(jié)點(diǎn)對(duì)每個(gè)文件的訪問(wèn)頻率信息.當(dāng)一個(gè)普通節(jié)點(diǎn)發(fā)送對(duì)某個(gè)文件F的請(qǐng)求到它所在組內(nèi)的超節(jié)點(diǎn)SPi時(shí),SPi首先檢查一下本組內(nèi)對(duì)該文件的請(qǐng)求頻率是否已經(jīng)超過(guò)了一個(gè)預(yù)先定義的值,如果超過(guò)了,SPi將發(fā)送一個(gè)副本請(qǐng)求到該文件所在組內(nèi)的超節(jié)點(diǎn)SPj.SPj接收到請(qǐng)求后就會(huì)把文件副本發(fā)給SPi,SPi收到文件副本后,將把該副本保存在本組內(nèi)剩余空間最多的普通節(jié)點(diǎn)上,并通知自己的鄰居節(jié)點(diǎn).當(dāng)然,為了節(jié)省網(wǎng)絡(luò)代價(jià),它也只通知一定范圍內(nèi)的鄰居超節(jié)點(diǎn),如圖2所示.圖2顯示了基于需求的副本策略的操作過(guò)程.超節(jié)點(diǎn)SP1檢查到本組內(nèi)頻繁的發(fā)送對(duì)文件i的請(qǐng)求,并且其頻率已經(jīng)超過(guò)事先定義的閾值,假定該文件在SP6所在組內(nèi)命中,那么SP1將給SP6發(fā)送對(duì)文件i副本的請(qǐng)求.SP6收到請(qǐng)求后就會(huì)把文件i的副本發(fā)給SP1.SP1收到文件副本后,將把該文件副本保存在本組內(nèi)剩余空間最多的普通節(jié)點(diǎn)Pi上,并在一定范圍內(nèi)通知其鄰居超節(jié)點(diǎn).4獲取文件的概率在這節(jié),我們將分析上面提出的兩種副本策略的平均訪問(wèn)代價(jià)和副本負(fù)載大小.首先我們來(lái)看一下它們的平均訪問(wèn)代價(jià).在這里我們把命中分為兩種,一種是本地命中(節(jié)點(diǎn)請(qǐng)求的文件在它所在組內(nèi)命中),另一種是遠(yuǎn)程命中(節(jié)點(diǎn)請(qǐng)求的文件在其他組內(nèi)命中).每個(gè)請(qǐng)求的平均代價(jià)計(jì)算如下:AvgCost=P(local)*LocalCost+P(remote)*RemoteCost(1)其中P(local)表示請(qǐng)求被本地命中的概率,P(remote)表示請(qǐng)求被遠(yuǎn)程命中的概率,LocalCost是從組內(nèi)取得文件所需的代價(jià),RemoteCost是從其它組內(nèi)取得文件所需的代價(jià).P(local)和P(remote)之和為1,并且它們的值能通過(guò)查詢請(qǐng)求的分布被計(jì)算出來(lái).一般文件共享系統(tǒng)中,文件的請(qǐng)求服從Zipf分布,那么文件i被訪問(wèn)的概率如下式:P(i)=1∑x=1D1x*1i(DΡ(i)=1∑x=1D1x*1i(D為系統(tǒng)中不相同文件的數(shù)目)(2)P(local)=∑i=1mP(i)(mΡ(local)=∑i=1mΡ(i)(m為本地不同文件的數(shù)目)(3)P(remote)+P(local)=1(4)4.1節(jié)點(diǎn)平均網(wǎng)絡(luò)地理位置在PRP方法中,超節(jié)點(diǎn)根據(jù)組內(nèi)文件的全局訪問(wèn)頻率來(lái)決定是否發(fā)送文件副本到其他發(fā)送請(qǐng)求的超節(jié)點(diǎn).我們用λ來(lái)表示一個(gè)預(yù)先定義好的閾值,當(dāng)文件的訪問(wèn)次數(shù)超過(guò)這個(gè)值的時(shí)候,一個(gè)文件副本將會(huì)發(fā)送給某個(gè)訪問(wèn)此文件頻率最高的超節(jié)點(diǎn).一個(gè)文件i被訪問(wèn)的頻率在公式(2)中已經(jīng)定義了.我們定義每個(gè)普通節(jié)點(diǎn)發(fā)出查詢請(qǐng)求的頻率為Q,超節(jié)點(diǎn)的數(shù)目為N,每個(gè)超節(jié)點(diǎn)平均和k個(gè)普通節(jié)點(diǎn)連接,在一個(gè)周期t內(nèi),請(qǐng)求文件i被請(qǐng)求的次數(shù)可以計(jì)算為:NumberAccess(i)=t*N*k*Q*P(i)(5)P(NumberAccess(i)>λ)表示文件i被訪問(wèn)的次數(shù)高于預(yù)先定義的值λ的概率,那么在一段時(shí)間T內(nèi)產(chǎn)生的平均副本數(shù)量為:NumberReplica?PRP=Tt*∑i=1D(P(NumberAccess(i)＞λ))(6)ΝumberReplica-ΡRΡ=Τt*∑i=1D(Ρ(ΝumberAccess(i)＞λ))(6)副本的負(fù)載代價(jià)為:Overhead-PRP=NumberReplica-PRP*AverageHops*TransferCost(7)AverageHops表示副本在超節(jié)點(diǎn)間傳輸過(guò)程中平均經(jīng)過(guò)的跳數(shù),TransferCost表示每跳的傳輸所需要的代價(jià).4.2生成的副本數(shù)量及負(fù)載代價(jià)在DRP方法中,超節(jié)點(diǎn)Si根據(jù)組內(nèi)對(duì)文件i請(qǐng)求的情況來(lái)決定是否需要請(qǐng)求拷貝副本到本組內(nèi).如果組內(nèi)對(duì)文件i的請(qǐng)求超過(guò)了預(yù)先定義的閾值θ,那么Si就會(huì)發(fā)送副本請(qǐng)求到擁有該文件i的超節(jié)點(diǎn)Sj.在一段時(shí)間T內(nèi),每組對(duì)文件i發(fā)出請(qǐng)求的次數(shù)可以計(jì)算為:NumberAccess(i)=T*k*Q*P(i)(8)P(NumberAccess(i)>θ)表示文件i被訪問(wèn)的次數(shù)高于預(yù)先定義的值θ的概率,那么在時(shí)間T內(nèi)產(chǎn)生的副本數(shù)量為:NumberReplica?PRP=N*∑i=1D(P(NumberAccess(i)＞θ))(9)ΝumberReplica-ΡRΡ=Ν*∑i=1D(Ρ(ΝumberAccess(i)＞θ))(9)副本的負(fù)載代價(jià)為:Overhead-DRP=NumberReplica-DRP*AverageHops*TransferCost(10)5性能評(píng)價(jià)這節(jié)將通過(guò)模擬實(shí)驗(yàn)來(lái)驗(yàn)證我們提出的副本策略的有效性,實(shí)驗(yàn)參數(shù)如表1所示.5.1spsize對(duì)平均跳數(shù)的影響由第4節(jié)的分析,可以得知在網(wǎng)絡(luò)結(jié)構(gòu)一定的情況下,影響PRP性能的重要參數(shù)是周期t,閾值λ,超節(jié)點(diǎn)緩存大小SPSize,而評(píng)價(jià)PRP性能好壞的標(biāo)準(zhǔn)就是副本負(fù)載及獲得查詢結(jié)果需要的平均跳數(shù)AverageHops.因此在本小節(jié)我們將通過(guò)實(shí)驗(yàn)分析這些參數(shù)之間的關(guān)系.表2顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數(shù)AverageHops隨閾值λ變化而變化的情況.從表中我們可以得知,隨著λ值的增大,AverageHops并沒(méi)有太明顯的變化.這是因?yàn)楣?jié)點(diǎn)發(fā)出的請(qǐng)求服從Zipf分布,一般請(qǐng)求偏向于比較熱門的文件,而這些文件的訪問(wèn)量很快可以達(dá)到預(yù)定的λ值,所以隨著λ值的增加,AverageHops的值并沒(méi)有明顯的變化,而只是略微有點(diǎn)升高的趨勢(shì).表3顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數(shù)AverageHops隨周期t變化而變化的情況.隨著t從1增加到4分鐘時(shí),平均跳數(shù)有明顯的減少,而當(dāng)它從4增加到6時(shí),平均跳數(shù)又開(kāi)始了慢幅度的增加,這是因?yàn)槿绻鹴過(guò)小,則在一個(gè)周期內(nèi)的請(qǐng)求數(shù)也相對(duì)比較少,很多相對(duì)熱門的文件的訪問(wèn)量也沒(méi)有達(dá)到預(yù)先定義的閾值λ,因此產(chǎn)生的副本數(shù)就很少,平均跳數(shù)也就比較高了.我們可以看到,當(dāng)t=1時(shí),平均跳數(shù)接近8,這和沒(méi)有采用副本策略的情況下的跳數(shù)幾乎差不多.而當(dāng)t過(guò)大時(shí),一個(gè)周期內(nèi)產(chǎn)生的副本并不會(huì)有明顯的增加,反而在一定的時(shí)間T內(nèi)產(chǎn)生的副本數(shù)會(huì)略微下降.表4顯示了PRP方法中,在其它值固定(取表1中的值)的情況下,平均跳數(shù)AverageHops隨SPSize變化而變化的情況.隨著SPSize的增加,其存儲(chǔ)能力越強(qiáng),能夠存儲(chǔ)的副本數(shù)越多,當(dāng)然平均跳數(shù)也就會(huì)下降了.當(dāng)超節(jié)點(diǎn)的緩存大小從1MB升到2MB時(shí),平均跳數(shù)有著明顯的降低,繼續(xù)上升到3MB時(shí),上升的趨勢(shì)有所減退,繼續(xù)增加SPSize時(shí),平均跳數(shù)幾乎保持不變了.5.2drp過(guò)程中平均跳數(shù)隨超節(jié)點(diǎn)緩沖溶液的變化表5顯示了DRP方法中,平均跳數(shù)AverageHops隨閾值θ變化而變化的情況.顯然,隨著θ的增加,AverageHops的值會(huì)越來(lái)越大,當(dāng)θ達(dá)到30以上時(shí),AverageHops的值幾乎不再發(fā)生變化,并且接近沒(méi)有采用副本策略情況下的平均跳數(shù)值.當(dāng)然,如果θ的值越小,AverageHops的值就會(huì)越小,但是整個(gè)系統(tǒng)中的副本負(fù)載就會(huì)加重.表6顯示了DRP方法中,平均跳數(shù)隨著超節(jié)點(diǎn)緩存大小SPSize變化而變化的情況.從圖中,我們可以看到,隨著緩存的增加,平均跳數(shù)并沒(méi)有明顯的下降趨勢(shì).這