【文章內(nèi)容簡介】 另外Vishnumurthy[30]等人在2006年提出了一種針對無結(jié)構(gòu)化異構(gòu)P2P網(wǎng)絡(luò)的拓?fù)涔芾矸椒ǎ摲椒ǘx了一個關(guān)鍵參數(shù)：用戶的期望負(fù)載。用于調(diào)節(jié)網(wǎng)絡(luò)異構(gòu)性產(chǎn)生的負(fù)載不均衡現(xiàn)象。具體為構(gòu)造隨機(jī)圖時不是構(gòu)造常數(shù)度的隨機(jī)圖，而是節(jié)點根據(jù)自身的期望負(fù)載選擇與多少個隨機(jī)節(jié)點建立連接，能力強(qiáng)的節(jié)點可以連接較多的鄰居以形成較大的連接出度。這種非常數(shù)度的連接方式對負(fù)載起到了一種均衡的作用。但最終形成的拓?fù)涫且环N靜態(tài)的隨機(jī)拓?fù)?，不能很好的對大?guī)模P2P網(wǎng)絡(luò)的變化以及抖動做出自適應(yīng)的改變。而在2005年Ming[31]等人提出了一種無結(jié)構(gòu)P2P環(huán)境中的非均勻的隨機(jī)拓?fù)涔芾聿呗裕且环N偏好性的拓?fù)涔芾聿呗?。作者認(rèn)為在很多應(yīng)用場景中采用偏好的節(jié)點選擇使得P2P網(wǎng)絡(luò)的服務(wù)更加高效，并將提出的方法應(yīng)用于在DHT網(wǎng)絡(luò)中進(jìn)行距離偏好的節(jié)點選擇，節(jié)點選擇充分考慮了節(jié)點之間的延時，將選擇延時較小的節(jié)點作為服務(wù)節(jié)點。但是該方法沒有考慮大規(guī)模P2P網(wǎng)絡(luò)存在較強(qiáng)的擾動特性，根據(jù)Chawathe [7]的觀點，隨機(jī)游走在在擾動性較強(qiáng)的網(wǎng)絡(luò)環(huán)境中需要重新構(gòu)建游走路徑，導(dǎo)致收斂時間較長，不適合動態(tài)的網(wǎng)絡(luò)環(huán)境。 綜上所述：傳統(tǒng)的P2P網(wǎng)絡(luò)中的拓?fù)涔芾砑夹g(shù)存在盲目進(jìn)行節(jié)點選擇導(dǎo)致選擇的服務(wù)節(jié)點不能滿足上層應(yīng)用的現(xiàn)象。問題在于采用隨機(jī)方式選擇目標(biāo)gossip節(jié)點以及需要交換的鄰居節(jié)點信息，以構(gòu)建一個隨機(jī)化的拓?fù)浣Y(jié)構(gòu)來提高網(wǎng)絡(luò)的魯棒性，避免出現(xiàn)“熱點”發(fā)生。但該方法沒有沒有考慮節(jié)點的服務(wù)能力與負(fù)載承受狀況，也忽略了節(jié)點的實時負(fù)載隨時間變化的特性，在負(fù)載持續(xù)增加時導(dǎo)致20%30%的服務(wù)節(jié)點選擇不能滿足上層應(yīng)用需求，增加了重新進(jìn)行節(jié)點選擇的幾率與成本，降低了P2P網(wǎng)絡(luò)的性能。需要一種負(fù)載均衡的拓?fù)涔芾矸?wù)來為P2P網(wǎng)路的上層應(yīng)用提供合適的節(jié)點選擇，保證上層應(yīng)用的正常運(yùn)行。 負(fù)載均衡程度的評價方法判斷一個P2P網(wǎng)絡(luò)的負(fù)載均衡程度，可以幫助網(wǎng)絡(luò)管理員了解網(wǎng)絡(luò)的運(yùn)行狀態(tài)，以便在負(fù)載不均衡導(dǎo)致網(wǎng)絡(luò)性能嚴(yán)重下降的情況下介入并監(jiān)管網(wǎng)絡(luò)，使其可以穩(wěn)定運(yùn)行來保證服務(wù)質(zhì)量。Vishnumurthy[30]在2006年的INFOCOM會議中描述了負(fù)載分布的狀態(tài)圖，指出了負(fù)載的分布具有正態(tài)分布的特性，即大部分節(jié)點的負(fù)載位于一個合適的負(fù)載范圍內(nèi)，而承受極少與極多負(fù)載的節(jié)點是少數(shù)。但他沒有提出一種衡量負(fù)載均衡程度的方法來對P2P網(wǎng)絡(luò)的負(fù)載分布的均衡性做出客觀評價。2004年2007年，gossip通信領(lǐng)域的權(quán)威人士Voulgaris[23]、Jelasity[24]與Ogston[27]分別使用節(jié)點入度方差來衡量網(wǎng)絡(luò)的負(fù)載均衡程度。節(jié)點入度代表一個覆蓋網(wǎng)絡(luò)中這個節(jié)點被多少節(jié)點置入自己的鄰居表中，從而知道這個節(jié)點的存在。在進(jìn)行節(jié)點選擇時入度高的節(jié)點被選為服務(wù)節(jié)點的概率較高。所以P2P網(wǎng)絡(luò)中的節(jié)點入度方差表征了所有節(jié)點被選擇為服務(wù)節(jié)點概率的差異性。這種差異性在一定程度上反映了網(wǎng)絡(luò)節(jié)點可以承受負(fù)載的差異性。但存在以下問題：1）節(jié)點可以承受負(fù)載的能力（節(jié)點入度）不等同于節(jié)點已經(jīng)承受的負(fù)載，負(fù)載均衡程度的衡量應(yīng)該將節(jié)點實際承受的負(fù)載納入考量范圍內(nèi)；2）P2P網(wǎng)絡(luò)是一個異構(gòu)的覆蓋網(wǎng)絡(luò)，節(jié)點之間具有不同的硬件配置資源與接入帶寬，不同的節(jié)點也就具有了不同的服務(wù)能力，如果按照一個統(tǒng)一標(biāo)準(zhǔn)要求每個節(jié)點都承受相同的負(fù)載，可能導(dǎo)致對于服務(wù)能力較弱的節(jié)點來說負(fù)載過重，對于服務(wù)能力較強(qiáng)的節(jié)點負(fù)載過輕，這并不是一種真正的負(fù)載均衡。3）僅僅按照連接度來描述負(fù)載的分配是不精確的，因為當(dāng)前的P2P網(wǎng)絡(luò)多提供盡力而為的服務(wù)模式[82]。當(dāng)一個節(jié)點作為服務(wù)節(jié)點為其他多個節(jié)點提供服務(wù)時，其他節(jié)點施加的負(fù)載并不是均勻的。如果采用基于節(jié)點入度的評價，則可以認(rèn)為每個“度”給節(jié)點帶來的不一定是相同的負(fù)載，這使得基于連接個數(shù)的衡量方式不能準(zhǔn)確描述網(wǎng)絡(luò)中的負(fù)載分布。綜上所述：現(xiàn)有的P2P網(wǎng)絡(luò)負(fù)載均衡程度的評價方法存在粗略不精確的現(xiàn)象，問題在于傳統(tǒng)評價方法采用節(jié)點入度表示節(jié)點被選擇作為服務(wù)節(jié)點的機(jī)率，將所有節(jié)點的入度方差作為描述網(wǎng)絡(luò)整體負(fù)載均衡程度的指標(biāo)。該方法忽略了P2P網(wǎng)絡(luò)中節(jié)點自有的異構(gòu)特性與實際環(huán)境中節(jié)點實時負(fù)載變化的因素，欠缺合理性與精確性，故節(jié)點入度方差不適合作為P2P網(wǎng)絡(luò)負(fù)載均衡程度的評價指標(biāo)。需要一種精確客觀的負(fù)載均衡量化方法來衡量實際應(yīng)用中的網(wǎng)絡(luò)負(fù)載，以幫助網(wǎng)絡(luò)管理員對P2P網(wǎng)絡(luò)的負(fù)載分布作出客觀的評價。 基于gossip的分層P2P拓?fù)錁?gòu)造技術(shù) 在純粹平坦式（flat）的大規(guī)模無結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，由于節(jié)點地理位置分布的不均衡性和節(jié)點能力的異構(gòu)性導(dǎo)致節(jié)點之間可能存在較大的延時以及弱能力節(jié)點不能滿足應(yīng)用需求的問題，因此造成了在平坦式的無結(jié)構(gòu)化P2P網(wǎng)絡(luò)上運(yùn)行的如文件共享、流媒體傳輸、即時通訊等應(yīng)用的效率下降。為了解決該問題，國內(nèi)外學(xué)者提出了一系列構(gòu)造分層P2P拓?fù)涞募夹g(shù)來改進(jìn)平坦式拓?fù)浣Y(jié)構(gòu)的不足。：分層P2P拓?fù)錁?gòu)造技術(shù)分類圖 現(xiàn)有的分層P2P拓?fù)錁?gòu)造技術(shù)主要分為以下幾類： 2002年，[82]，在這個版本中提出Ultrapeer與leafpeer的概念，即超級節(jié)點與葉節(jié)點。協(xié)議將網(wǎng)絡(luò)分為二層結(jié)構(gòu)，上層為超級節(jié)點通過隨機(jī)方式連接構(gòu)成，下層為葉節(jié)點，葉節(jié)點只維持對少量超級節(jié)點的連接。超級節(jié)點將作為葉節(jié)點的代理服務(wù)器幫助葉節(jié)點完成諸如查詢請求轉(zhuǎn)發(fā)以及消息處理等工作。這種結(jié)構(gòu)考慮到了節(jié)點之間存在的異構(gòu)性特點，有效提高了Gnutella網(wǎng)絡(luò)的靈活性，降低了消息處理與路由過程中參與的節(jié)點個數(shù)以及節(jié)點之間傳輸數(shù)據(jù)的流量，提高了網(wǎng)絡(luò)的性能。但是該方法也存在明顯的不足，對于超級節(jié)點的選擇通過預(yù)先定義的節(jié)點帶寬閾值進(jìn)行選擇，使得超級節(jié)點的選擇缺乏靈活性，當(dāng)網(wǎng)絡(luò)帶寬存在物理升級與變化，難以控制超級節(jié)點所占比例；超級節(jié)點不能實現(xiàn)與葉節(jié)點的靈活角色互換，導(dǎo)致不能適應(yīng)動態(tài)的網(wǎng)絡(luò)環(huán)境變化。2003年，Yatin等人提出了GIA[7]，一種基于無結(jié)構(gòu)P2P模型Gnutella而改進(jìn)的分層P2P拓?fù)?。GIA用于解決并發(fā)查詢給節(jié)點帶來的負(fù)載過重的問題。在進(jìn)行超級節(jié)點的選擇時，GIA將網(wǎng)絡(luò)中節(jié)點可以處理查詢請求的速率作為超級節(jié)點選擇的指標(biāo)，認(rèn)為網(wǎng)絡(luò)中的節(jié)點按照處理查詢請求速率進(jìn)行劃分具有幾個不同級別，高于1000x速率的節(jié)點即為超級節(jié)點。這種方法源自固定閾值劃分，即將節(jié)點按照某種能力劃分為若干級別，達(dá)到一定級別的可視為超級節(jié)點，方法簡單有效。但是該方法不具有自適應(yīng)性。需要預(yù)先對級別做出定義，針對一個大規(guī)模的P2P網(wǎng)絡(luò)，在初始構(gòu)造階段難以定義一個合適的分組規(guī)則對節(jié)點的服務(wù)能力進(jìn)行有效劃分。同時隨著節(jié)點自身硬件資源或傳輸速度的升級或大量高服務(wù)能力的節(jié)點加入到P2P網(wǎng)絡(luò)中，大量節(jié)點將被劃分為超級節(jié)點，使得網(wǎng)絡(luò)拓?fù)溱呄蛴谄教故浇Y(jié)構(gòu)，無法精確控制超級節(jié)點比例，降低了分層P2P拓?fù)涞男阅堋?004年，Alberto等人提出了SG1[32]，一種基于gossip的自適應(yīng)的分層P2P拓?fù)錁?gòu)造方法。SG1在原有的覆蓋拓?fù)渲辖⒁粋€分層P2P拓?fù)?，并通過節(jié)點之間的gossip過程來判斷節(jié)點的服務(wù)能力與負(fù)載狀態(tài)做出節(jié)點角色劃分的決定：超級節(jié)點傾向于在與其他超級節(jié)點進(jìn)行g(shù)ossip交互的過程中把與自己相連的葉節(jié)點推向具有更強(qiáng)服務(wù)能力的超級節(jié)點，然后自己可以降為葉節(jié)點。SG1有效避免了固定閾值法不能適應(yīng)節(jié)點服務(wù)能力變化的特點。但SG1存在以下不足：當(dāng)一個超級節(jié)點把自身的負(fù)載轉(zhuǎn)移到另一個具有更強(qiáng)服務(wù)能力的超級節(jié)點上時，容易引起P2P網(wǎng)絡(luò)中負(fù)載不均衡的現(xiàn)象，即SG1傾向于“耗盡”服務(wù)能力強(qiáng)的超級節(jié)點的性能。對于目前采用“盡力而為”模式的Internet而言，這可能引起超級節(jié)點負(fù)載過重甚至崩潰，反而降低了分層P2P拓?fù)涞男阅堋?005年，Michael等提出了LST[33]，一種輕量級的超級節(jié)點拓?fù)洹Ｎ墨I(xiàn)只提到超級節(jié)點的選取準(zhǔn)則包括超級節(jié)點應(yīng)該具有足夠的資源為其他節(jié)點進(jìn)行服務(wù)，并且不能頻繁的加入或離開P2P網(wǎng)絡(luò)。沒有提到具體的選擇策略。同年，Li等人提出了DLM[34]，一種動態(tài)分層的P2P拓?fù)涔芾硭惴āLM認(rèn)為傳統(tǒng)的節(jié)點能力比較方法不能適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，使用了一種“可擴(kuò)展的比較方法（scaled parsion）”來進(jìn)行節(jié)點之間的比較以確定超級節(jié)點的選擇。DLM包含兩個向量參數(shù)Xcapa與Xage，用于指定服務(wù)能力與節(jié)點在線時間各自所占的權(quán)重比例。DLM最終計算的是節(jié)點的服務(wù)能力與在線時長分別在所有鄰居節(jié)點中的相對位置值，同時DLM定義了兩個閾值Zcapa與Zage，通過分別比較服務(wù)能力與在線時長與兩個閾值參數(shù)的大小決定超級節(jié)點和葉節(jié)點的轉(zhuǎn)化。該方法具有可以靈活適應(yīng)拓?fù)?，維持合適超級節(jié)點比例的特點。但該方法也存在不足：DLM最終計算的是節(jié)點在自身鄰居節(jié)點中的相對位置值，這要求節(jié)點鄰居的服務(wù)能力與在線時長必須是全局P2P網(wǎng)絡(luò)的均勻采樣值。但DLM維持的是靜態(tài)鄰居表，不能保證是全局網(wǎng)絡(luò)的均勻采樣，導(dǎo)致計算出的相對位置值相對全局P2P網(wǎng)絡(luò)可能存在較大偏差，導(dǎo)致引起不恰當(dāng)?shù)某壒?jié)點選擇。2006年，鄭倩冰等人提出了ERSN[35]，一種使用gossip機(jī)制構(gòu)造的兩層P2P網(wǎng)絡(luò)。ERSN選擇超級節(jié)點的方法類似于Yatin等人的方法，該方法直接將節(jié)點的帶寬能力分為幾類，帶寬高的節(jié)點則為超級節(jié)點。其缺陷與GIA的缺陷一樣，不能適應(yīng)P2P網(wǎng)絡(luò)帶寬的變化。2007年，Gian等人基于SG1的基礎(chǔ)提出了SG2[36]。SG2加入了虛擬坐標(biāo)服務(wù)，將節(jié)點之間的延時距離作為是否歸屬于一個超級節(jié)點的評價標(biāo)準(zhǔn)，有助于提升實際應(yīng)用中的分層P2P拓?fù)涞男阅?。?jié)點從葉節(jié)點轉(zhuǎn)化為超級節(jié)點的過程是當(dāng)一個葉節(jié)點收到CLBCAST類消息，由自身的信號強(qiáng)度與響應(yīng)極限這二個參數(shù)構(gòu)成的轉(zhuǎn)化函數(shù)決定。實驗證明這種方式容易導(dǎo)致葉節(jié)點暫時性不能找到歸屬超級節(jié)點的問題，呈現(xiàn)“孤立”現(xiàn)象。另外SG2仍然沒有改變SG1中存在的問題，即負(fù)載傾向于向服務(wù)能力更強(qiáng)的超級節(jié)點遷移，而不考慮此時超級節(jié)點承受的負(fù)載是否造成負(fù)載不均衡，最終導(dǎo)致分層P2P拓?fù)湫阅芟陆怠Ｍ?，Cao[37]等人提出了一種動態(tài)超級節(jié)點拓?fù)?。該拓?fù)涠x了三類節(jié)點，其中DSN與BN為服務(wù)能力較強(qiáng)的節(jié)點，DSN作為動態(tài)超級節(jié)點從BN中進(jìn)行動態(tài)選擇。一個DSN在完成從BN的角色轉(zhuǎn)化時，將其服務(wù)能力乘以一個因子K，即將其服務(wù)能力放大K倍以保證網(wǎng)絡(luò)演化時DSN不會輕易被替換掉。但是針對DSN與BN的選擇仍然是依賴其絕對服務(wù)能力值的大小，需要劃定選擇DSN與BN的閾值，不能根據(jù)全網(wǎng)節(jié)點的服務(wù)能力值分布進(jìn)行自適應(yīng)的選擇。2008年，Peter等人提出了一種基于網(wǎng)絡(luò)坐標(biāo)的超級節(jié)點選擇算法SPSA[38]。SPSA將節(jié)點處于網(wǎng)絡(luò)拓?fù)渲械奈恢米鳛橹饕笜?biāo)進(jìn)行超級節(jié)點的選擇。SPSA將問題量化為：超級節(jié)點到所有葉節(jié)點的總延時最小。該問題為NP難題，只能求得最優(yōu)解。最終網(wǎng)絡(luò)中的超級節(jié)點個數(shù)為（N為網(wǎng)絡(luò)規(guī)模），每個超級節(jié)點附屬的葉節(jié)點個數(shù)為。該方法從通信代價的角度考進(jìn)行超級節(jié)點的選擇，有利于減少P2P網(wǎng)絡(luò)中的消息路由延時，但SPSA的大量計算依賴于網(wǎng)絡(luò)坐標(biāo)系統(tǒng)之間的距離計算，當(dāng)前的GNP[46]，PIC[47]，Latency Filters[48]等網(wǎng)絡(luò)坐標(biāo)系統(tǒng)精度又強(qiáng)烈依賴于“燈塔”節(jié)點的選擇，誤差達(dá)到40%甚至更高，導(dǎo)致SPSA的計算精度難以保證，當(dāng)網(wǎng)絡(luò)出現(xiàn)擾動時，網(wǎng)絡(luò)坐標(biāo)系統(tǒng)需要重新計算坐標(biāo)來修正坐標(biāo)誤差。可見網(wǎng)絡(luò)坐標(biāo)系統(tǒng)只能作為輔助手段進(jìn)行超級節(jié)點選擇，不適宜作為主要指標(biāo)參數(shù)構(gòu)造分層拓?fù)洹Ｍ?，Liu等人針對SG1做了改進(jìn)，提出了ERASP[39]，在衡量節(jié)點服務(wù)能力時增加了在線時長作為權(quán)重。同時加入了連接增強(qiáng)策略，即一個葉節(jié)點盡量保持超級節(jié)點集合的個數(shù)為預(yù)定義的常數(shù)d，如果超級節(jié)點集合容量小于d，則將從葉節(jié)點集合中選擇部分服務(wù)能力最強(qiáng)的節(jié)點來補(bǔ)充超級節(jié)點集合。這樣有利于加強(qiáng)葉節(jié)點對超級節(jié)點的連接，防止葉節(jié)點成為“單點”。但ERASP在超級節(jié)點之間進(jìn)行負(fù)載遷移時仍然采用與SG1相同的策略，易引發(fā)P2P網(wǎng)絡(luò)中的負(fù)載不均衡的現(xiàn)象發(fā)生。2009年，Paul等人提出了Myconet[40]，一種利用生物群落繁殖原則進(jìn)行拓?fù)錁?gòu)造的超級節(jié)點拓?fù)洹yconet中超級節(jié)點將主動尋找葉節(jié)點并吸收其加入自身所在的簇。但Myconet存在與SG2類似的問題：當(dāng)超級節(jié)點處于immobile狀態(tài)時，將從其他狀態(tài)的的超級節(jié)點處主動遷移負(fù)載，讓自身連接的葉節(jié)點個數(shù)維持最大。這同樣易產(chǎn)生負(fù)載不均衡現(xiàn)象。同年，Luis等人提出了DANTE[41]，一種根據(jù)網(wǎng)絡(luò)負(fù)載變換網(wǎng)絡(luò)結(jié)構(gòu)的拓?fù)淠Ｐ?。DANTE根據(jù)節(jié)點當(dāng)前的負(fù)載動態(tài)調(diào)整拓?fù)?，即與其他節(jié)點重連來達(dá)到一個新狀態(tài)以適應(yīng)網(wǎng)絡(luò)環(huán)境的變化。當(dāng)網(wǎng)絡(luò)整體處于輕負(fù)載狀態(tài)，整個拓?fù)涑尸F(xiàn)中心化的連接，當(dāng)網(wǎng)絡(luò)整體處于重負(fù)載狀態(tài)，整個拓?fù)涑尸F(xiàn)隨機(jī)化的連接。這樣可以有效避免中心化負(fù)載過重與惡意節(jié)點攻擊的問題。但該方法也存在明顯不足：節(jié)點通過本地信息無法感知網(wǎng)絡(luò)的整體負(fù)載輕重，進(jìn)而無法確定合適的重連時間，文中給出的辦法是相隔一定的時間間隔即啟動重連機(jī)制對拓?fù)溥M(jìn)行重連，這樣增加了不必要的管理負(fù)載開銷。此外，近年來P2P領(lǐng)域的專家學(xué)者提出了一種分布式排序/分組算法，可以以一種分布式的方式在P2P網(wǎng)絡(luò)的全局范圍內(nèi)實現(xiàn)排序或分組，使得每個節(jié)點只需要根據(jù)自身所知道的局部拓?fù)湫畔⒏兄约涸谌种械南鄬ξ恢弥?。該類算法可以?yīng)用于分層P2P的拓?fù)錁?gòu)造以實現(xiàn)對超級節(jié)點的篩選。2006年Mark[42]等人最先提出一種在大規(guī)模覆蓋網(wǎng)絡(luò)中進(jìn)行節(jié)點排序的算法。其原理為每個節(jié)點在本地生成一個取自固定區(qū)間的均勻隨機(jī)數(shù)，然后節(jié)點通過Newscast協(xié)議[43]進(jìn)行節(jié)點特征值的比較決定是否進(jìn)行隨機(jī)數(shù)的交換，最終節(jié)點持有的隨機(jī)數(shù)按照節(jié)點特征值的大小進(jìn)行排序，使得節(jié)點通過本地隨機(jī)數(shù)大小即可感知自己在網(wǎng)絡(luò)全局范圍的相對位置值。該方法利用gossip協(xié)議實現(xiàn)，簡單可靠。但該方法也存在不足：針對一個未知規(guī)模的P2P網(wǎng)絡(luò)環(huán)境，很難建立一個合適的均勻隨機(jī)數(shù)生成模型，隨著后期的網(wǎng)絡(luò)擾動，使得網(wǎng)絡(luò)中所有節(jié)點持有的隨機(jī)數(shù)集合并非均勻分布的隨機(jī)數(shù)集合，這使得節(jié)點根據(jù)隨機(jī)數(shù)感知自己的相對位置時的誤差越來越大，導(dǎo)致排序最終無法收斂。2007年，Antonio[44]等提出了一種在動態(tài)系統(tǒng)中進(jìn)行節(jié)點分組的算法。節(jié)點通過在持續(xù)不斷的gossip過程中比較自己持有的特征值與鄰居節(jié)點的特征值來計算自己的分組索引估值