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