無結(jié)構(gòu)對等中網(wǎng)絡(luò)資源發(fā)現(xiàn)方法研究的最新進展

(浙江工商大學 計算機與信息工程學院， 杭州 310018)



摘要：為了提高無結(jié)構(gòu)對等網(wǎng)絡(luò)的資源查找效率，消除冗余網(wǎng)絡(luò)流量，出現(xiàn)了許多查詢算法。在分析這些算法特點的基礎(chǔ)上，將它們大致分成四類：基于前向傳遞的方法、基于緩存的方法、基于查詢和數(shù)據(jù)雙重復(fù)制的方法、基于拓撲優(yōu)化的方法。進一步深入分析其優(yōu)缺點之后，指出任何一類查詢算法都只優(yōu)化了某一方面的性能，如果能將某幾類方法有機集成，使它們相互補充，定能取得更好的效果。最后給出了一些重要的結(jié)論。

關(guān)鍵詞：無結(jié)構(gòu)對等網(wǎng)絡(luò)； 拓撲失配； 覆蓋網(wǎng)； 搜索效率

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2008)11-3214-04



Survey on resource discover methods in unstructured P2P network



XIE Man-de， WEI Gui-yi， LING Yun



(College of Computer Science Information Engineering， Zhejiang Gongshang University， Hangzhou 310018， China)



Abstract:Many search methods have been presented to avoid the large volume of unnecessary traffic incurred by the flooding-based search in unstructured P2P systems. According to the features of presented search methods， roughly divided into four categories: forwarding-base methods; cache-based methods; methods based on replication of both query and data; methods based on topology optimization. After analyzed the merits and shortcomings of all kinds of methods， the paper pointed out that any kind of search methods could only optimize a certain aspect of performance. If integrated several kinds of search algorithms smoothly， the optimization performance will be better. At last， gave some important conclusions.

Key words：unstructured peer-to-peer; topology mismatch; overlay; search efficiency



近年來，對等網(wǎng)絡(luò)（P2P）日益成為一個熱門的話題。通過將分布在Internet邊緣的眾多節(jié)點聯(lián)系起來，集合它們的計算能力以及存儲空間等資源，對等網(wǎng)絡(luò)能以極低的代價形成巨大的服務(wù)能力。在這種對等網(wǎng)絡(luò)中，所有節(jié)點處于對等地位，每個節(jié)點都可以既是服務(wù)提供者，同時也可以是服務(wù)請求者，而整個對等網(wǎng)絡(luò)的服務(wù)能力則由網(wǎng)絡(luò)中的節(jié)點所提供的共享資源來決定。根據(jù)對等網(wǎng)絡(luò)中節(jié)點對共享資源的索引方式不同，可以將目前的對等網(wǎng)絡(luò)大致分成中心式對等網(wǎng)絡(luò)和非中心結(jié)構(gòu)式對等網(wǎng)絡(luò)、非中心無結(jié)構(gòu)式對等網(wǎng)絡(luò)三類。無結(jié)構(gòu)對等網(wǎng)絡(luò)對其中的節(jié)點沒有任何束縛，且具有查詢方式靈活、可適應(yīng)高度動態(tài)的Internet環(huán)境等優(yōu)點，所以如Gnutella^[1]、KaZaA^[2]等類型的無結(jié)構(gòu)對等網(wǎng)絡(luò)成為了主流P2P網(wǎng)絡(luò)，其資源發(fā)現(xiàn)方法也受到了研究人員的高度關(guān)注。

無結(jié)構(gòu)P2P網(wǎng)絡(luò)中通常采用泛洪搜索的資源發(fā)現(xiàn)方法。這種搜索方法簡單、靈活，能提供匿名性，但是也會產(chǎn)生巨大的網(wǎng)絡(luò)負載。文獻[3，4]指出民流行P2P系統(tǒng)所產(chǎn)生的流量已經(jīng)成為一股最大的網(wǎng)絡(luò)流量。文獻[5]進一步指出在一個只有50 000個節(jié)點、任意兩節(jié)點之間95％的物理跳數(shù)不超過7、TTL=7的Gnutella系統(tǒng)中，泛洪搜索每月產(chǎn)生的網(wǎng)絡(luò)流量達到了330 TB。泛洪搜索帶來的巨大網(wǎng)絡(luò)流量嚴重限制了P2P網(wǎng)絡(luò)的擴展性。為了減少泛洪搜索中的冗余網(wǎng)絡(luò)流量，提高搜索性能，大量算法已經(jīng)被提出來。

1基于前向傳遞的方法

基于前向傳遞方法的基本思想是通過優(yōu)化或改變傳遞查詢請求消息的策略來減少網(wǎng)絡(luò)流量。

針對泛洪搜索的缺點，文獻[6]提出了迭代泛洪搜索方法。該方法進行多次泛洪搜索，每次搜索深度遞增，當查詢的結(jié)果滿足要求或者已經(jīng)到達最大的深度限制時過程結(jié)束。在泛洪中，隨著深度的增加，節(jié)點個數(shù)指數(shù)增長。因此，如果能夠在小于D（D為最大深度限制）的深度內(nèi)找到滿意的結(jié)果，與直接以深度為D進行泛洪搜索相比，很多節(jié)點就不必查詢，節(jié)省了大量的資源。但是在不理想的情況下，迭代泛洪可能要進行到最后一次迭代。這時，迭代泛洪就比直接泛洪更糟糕，因為多次迭代在網(wǎng)絡(luò)上發(fā)送了大量的resend消息，占用了網(wǎng)絡(luò)帶寬，也給節(jié)點增加了處理負擔。文獻[7]提出了廣度優(yōu)先的搜索策略。該方法以源節(jié)點為根，建立網(wǎng)絡(luò)圖的廣度優(yōu)先生成樹，源節(jié)點根據(jù)廣度優(yōu)先生成樹將查詢消息發(fā)送到每個節(jié)點。這樣可以保證每個節(jié)點都收到查詢消息，而且每個節(jié)點只收到一次查詢消息，避免了普通泛洪搜索中的節(jié)點多次遍歷問題。但是進行廣度優(yōu)先搜索需要知道關(guān)于所有節(jié)點的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。在P2P網(wǎng)絡(luò)中，雖然可以通過節(jié)點之間相互交換信息來獲得所有節(jié)點的網(wǎng)絡(luò)拓撲，但是這需要大量的信息交換，會給網(wǎng)絡(luò)帶來很大的負載。而且，由于P2P網(wǎng)絡(luò)的動態(tài)特性，節(jié)點頻繁地加入或退出，這樣獲得的網(wǎng)絡(luò)結(jié)構(gòu)圖是不準確的，生成的廣度優(yōu)先生成樹也是不可靠的。隨機行走(RW)算法^[8]則是一種深度優(yōu)先的搜索算法。它在泛洪的過程中隨機選取一個鄰居節(jié)點轉(zhuǎn)發(fā)信息，而不是像普通泛洪算法那樣向所有的鄰居節(jié)點轉(zhuǎn)發(fā)信息。很顯然，RW算法的通信負荷減少了一個數(shù)量級，但是RW的搜索效率很低，用戶可能需要為一條查詢而忍受長時間的延遲。為了減少延遲，提高搜索效率，文獻[9]提出了k-walker搜索算法。這種方法顯然能降低延時，但是消息數(shù)量相應(yīng)增加。文獻[10]則提出了一種介于廣度優(yōu)先搜索與深度優(yōu)先搜索之間的方法——有向?qū)挾葍?yōu)先搜索算法。這種方法不將搜索請求發(fā)送到所有的鄰居節(jié)點，而是根據(jù)節(jié)點所記錄的關(guān)于各個鄰居節(jié)點的一些歷史信息，只將搜索請求發(fā)送給一部分能夠返回較多結(jié)果的鄰居節(jié)點，從而可以在較短的時間得到所需數(shù)量的結(jié)果，并且可以減少所需的消息量。文獻[11]提出了一個混合周期泛洪搜索算法。該算法通過多種因素來選擇消息前向傳遞的節(jié)點，并且為了在搜索費用與響應(yīng)時間之間取得平衡，引入了部分覆蓋問題。文獻[12]則提出了最大聚集度優(yōu)先的搜索算法。該算法的基本思想是，節(jié)點在轉(zhuǎn)發(fā)查詢搜索信息包時，根據(jù)其鄰居節(jié)點的聚集度來進行，即優(yōu)先將查詢搜索信息包向相鄰節(jié)點中聚集度最高的節(jié)點轉(zhuǎn)發(fā)。若聚集度最高的節(jié)點已訪問過，則向聚集度次高的節(jié)點轉(zhuǎn)發(fā)，依此類推。這種方法對于滿足冪規(guī)律的隨機網(wǎng)絡(luò)來講效果不錯，但是對于規(guī)則網(wǎng)絡(luò)或普通隨機網(wǎng)絡(luò)來說效果不理想。

2基于緩存的方法

基于緩存方法的基本思想是，在搜索成功后，采用某種策略將查找到的資源緩存到網(wǎng)絡(luò)中的其他節(jié)點上，從而減少再次查找該資源需要的時間和網(wǎng)絡(luò)流量，提高查詢效率。針對緩存的對象不同，進一步可細分為數(shù)據(jù)索引緩存和內(nèi)容緩存。

文獻[13~15]提出了一個DHT方法。該方法通過預(yù)定義的hash函數(shù)在所有的參與節(jié)點上建立分布式索引，以減少泛洪查詢流量，但是索引維護代價太高。所以DHT方法不適合于高度動態(tài)的P2P網(wǎng)絡(luò)。

Sripanidkulchai^[16]考察了Gnutella網(wǎng)絡(luò)查詢的流行分布，發(fā)現(xiàn)Gnutella網(wǎng)絡(luò)查詢的流行分布具有明顯的兩相性：最流行的對象具有近似相等的流行性；而次流行的對象的流行性則呈現(xiàn)出Zipf-like的性質(zhì)。利用這一性質(zhì)，Sripanidkulchai提出了一個基于TTL的UIC緩存方法：Gnutella節(jié)點監(jiān)視經(jīng)過其上的查詢匹配串及查詢結(jié)果，并且將相應(yīng)的查詢結(jié)果緩存下來，每個緩存的條目只保存一定時間(緩存生命期TTL)，超過這個時間，緩存的條目將作廢而不再使用；節(jié)點收到查詢后，根據(jù)查詢是否命中有效緩存來決定查詢消息是否轉(zhuǎn)發(fā)。Markatos^[17]進一步考察了Gnutella的流量性質(zhì)，發(fā)現(xiàn)Gnutella流量在不同尺度上都表現(xiàn)出較明顯的突發(fā)性質(zhì)，并且有較明顯的局部性。基于這個特性，Markatos提出了一個改進的UIC緩存方案。該方案針對查詢消息的生命期作了如下處理：在緩存每個經(jīng)過節(jié)點的查詢結(jié)果時，節(jié)點同時記錄該查詢消息剩余的TTL，節(jié)點在比較緩存的索引信息的相關(guān)TTL與該查詢消息的剩余TTL后，再決定是否轉(zhuǎn)發(fā)該查詢消息。Wang等人^[18]在KaZaA網(wǎng)絡(luò)中的一些節(jié)點上應(yīng)用了UIC方法，并考察了兩個相鄰緩存節(jié)點的緩存內(nèi)容，發(fā)現(xiàn)在兩個相鄰的緩存節(jié)點中，有超過30%的緩存命中是相互交疊的，因此Wang等人提出了一個分層方法DiCAS以解決緩存交疊的問題。其方法是：P2P網(wǎng)絡(luò)中的節(jié)點被分成多個組，每個組有一個惟一的組ID，每個節(jié)點都與鄰居交換自己的組ID與鄰居節(jié)點度。通過這個方法，節(jié)點可以了解所有鄰居的組ID及其鄰居節(jié)點度。節(jié)點收到一個查詢消息后，對該查詢消息進行hash和求模計算。如果某個鄰居節(jié)點的組ID與計算得到的值相匹配，則將該查詢消息轉(zhuǎn)發(fā)給該鄰居節(jié)點；如果沒有相匹配的鄰居，則轉(zhuǎn)發(fā)給節(jié)點度最大的鄰居。通過這種方法，DiCAS算法實現(xiàn)了按層的泛洪路由。查詢結(jié)果沿著逆向路徑返回，沿途節(jié)點并不是所有節(jié)點都將查詢結(jié)果緩存下來，而是像前面只有匹配的鄰居節(jié)點才轉(zhuǎn)發(fā)查詢消息一樣，只有匹配的沿途節(jié)點才將查詢結(jié)果緩存下來。DiCAS方法通過在P2P網(wǎng)絡(luò)上再人為地構(gòu)造層次，并實現(xiàn)了按層路由與按層緩存，極大地緩解了緩存命中交疊的問題。

文獻[3]提出了一個基于內(nèi)容的緩存方法，建立了一個理想的基于KaZaA P2P網(wǎng)絡(luò)的緩存模擬器。實驗證明，基于內(nèi)容的緩存方法能較大地減少大規(guī)模P2P網(wǎng)絡(luò)的帶寬需求，但是與基于索引緩存的方法相比，這種方法浪費存儲空間，實現(xiàn)代價較大。

文獻[19]思路比較特殊，它不是通過緩存策略，而是通過冗余響應(yīng)傳遞（RRD）、自適應(yīng)響應(yīng)傳遞（ARD）和擴展的自適應(yīng)響應(yīng)傳遞（e-ARD）三種技術(shù)來提高查詢響應(yīng)傳遞質(zhì)量，以減少響應(yīng)消息丟失率，提高網(wǎng)絡(luò)資源利用率，這也能有效減少查詢產(chǎn)生的網(wǎng)絡(luò)流量。

3基于查詢和數(shù)據(jù)雙重復(fù)制的方法

基于查詢和數(shù)據(jù)雙重復(fù)制的方法不是簡單地將查詢請求同時分發(fā)給多個節(jié)點，資源發(fā)現(xiàn)后再將數(shù)據(jù)采用某種策略備份到多個節(jié)點，而是在查詢時，通過查詢數(shù)據(jù)包和目標數(shù)據(jù)同時復(fù)制的方法來提高查詢效率和成功率。

Sarshar等人^[20]針對Gnutella拓撲結(jié)構(gòu)，提出了一個近似線性復(fù)雜度的窮舉搜索算法。該算法在分兩階段的搜索方案中，采用了隨機行走的數(shù)據(jù)復(fù)制策略。查詢首先通過隨機行走的方法被安裝在各個節(jié)點，然后通過基于數(shù)據(jù)和查詢相互滲透的概率算法進行泛洪。然而這種方法只能適合于具有冪規(guī)律的圖模型，同時由于引入了度為｜V｜的節(jié)點，系統(tǒng)的查詢復(fù)雜度達到了O(｜V｜ log2 ｜V｜)，同時查詢延時較大。文獻[21]也基于概率的思想提出了一種搜索算法。由于該算法采用隨機步行的方式來對節(jié)點進行采樣，使算法不能考慮節(jié)點容量的異構(gòu)性，查詢延時較大，同時也不能控制采樣節(jié)點的精確規(guī)模。

針對上述算法的缺點，文獻[22，23]中提出了一種叫做BubbleStorm的搜索方法。該方法采用了一個可擴展、自適應(yīng)、魯棒的獨立于具體的分布式查詢語言的網(wǎng)絡(luò)層搜索策略。BubbleStorm也采用概率思想，其基本原理是：假設(shè)讓紅色的球表示查詢復(fù)制操作，讓綠色的球表示文檔元數(shù)據(jù)的復(fù)制操作，對于一個規(guī)模為n個節(jié)點的網(wǎng)絡(luò)，將r個紅色球和g個綠色球隨機均勻地分布到n個節(jié)點中，同時有紅色球和綠色球的節(jié)點不存在的概率將小于e-rg/n，如果網(wǎng)絡(luò)規(guī)模n是確定的，則概率只與rg的乘積有關(guān)，增加r減小g或增加g減小r都可以保持概率不變。假設(shè)rg=4n，則查詢只存在一個數(shù)據(jù)副本的操作，成功的概率將大于1-e-4≈0.981 7。當將指定數(shù)目的數(shù)據(jù)或查詢包拷貝到隨機節(jié)點中時，顯然h跳內(nèi)的所有節(jié)點延時比較小，但是由于各個節(jié)點的具體度數(shù)不同，很難通過h控制精確的節(jié)點數(shù)量，由此引入了一個新的稱為bubblecast的映射操作來完成。每個查詢包在查詢bubble中復(fù)制。每個數(shù)據(jù)包在數(shù)據(jù)bubble中復(fù)制，當有一個節(jié)點同時接收到數(shù)據(jù)包和查詢包，就產(chǎn)生了匯集點，查詢成功。圖1給出了這個過程的解釋。BubbleStorm算法的主要步驟如下：

a）產(chǎn)生隨機多圖的覆蓋網(wǎng)。初始節(jié)點只有一條自循環(huán)的邊，當有新的節(jié)點加入時，為了保持已有節(jié)點度不變，從已有節(jié)點中隨機選擇一條邊，將新節(jié)點插入；相似地，當有節(jié)點離開時進行相反的操作，以保持形成的P2P覆蓋網(wǎng)的隨機多圖特性。

b）檢測網(wǎng)絡(luò)的全局狀態(tài)，以計算需要復(fù)制的查詢和數(shù)據(jù)份數(shù)。假設(shè)Di=∑v∈Vdeg (v)i，c:=-ln(1-r)。其中：V為節(jié)點集合；r為用戶給定的可靠性要求，則通過改進Kempe等人^[24]的算法可以確定查詢復(fù)制份數(shù)q和數(shù)據(jù)份數(shù)d：

q:=｜cTRd/Rq｜，d:=｜cTRq/Rd｜

其中：T=D21/（D2-2D1）；Rd、Rq分別表示數(shù)據(jù)和查詢注入系統(tǒng)的速率。

c）Bubblecast映射。該映射操作的輸入為需要復(fù)制的數(shù)據(jù)項、復(fù)制份數(shù)和分割因子s，處理時當前節(jié)點首先將權(quán)重減1（也就是復(fù)制份數(shù)減1），然后進行數(shù)據(jù)存儲或查詢操作。如果權(quán)重不為1，則從前向鄰居節(jié)點中隨機選取s個節(jié)點（不包括轉(zhuǎn)發(fā)該消息的鄰居），并將剩下的權(quán)重分配給它們。圖2演示了一個bubblecast映射過程。顯然這種方法具有較好的并行性，同時能精確地控制復(fù)制份數(shù)。

BubbleStorm采用bubblecast方式實現(xiàn)窮舉搜索，這個效果非常令人震驚。傳統(tǒng)算法往往都是通過TTL值來控制搜索規(guī)模，常用的TTL=7。這樣在節(jié)點規(guī)模巨大的網(wǎng)絡(luò)中，搜索覆蓋率非常小，即使是TTL=7。由于查詢產(chǎn)生的網(wǎng)絡(luò)流量已經(jīng)占用了Internet流量的大部分，如果再進一步增大TTL值，網(wǎng)絡(luò)流量將難以接受，而BubbleStorm從概率的角度能保證非常高（接近1）的查詢成功率，而網(wǎng)絡(luò)流量基本不會增加。同時它也克服了采用隨機步行方法帶來的大延時和不能精確控制采用節(jié)點規(guī)模的缺點。但是BubbleStorm沒有給出bubblecast映射過程隨機性的證明，不能保證采用這種映射后，資源和查詢復(fù)制的隨機性。

4基于拓撲優(yōu)化的方法

P2P網(wǎng)絡(luò)是一種建立在物理網(wǎng)絡(luò)之上的抽象的、邏輯網(wǎng)絡(luò)。任何想加入P2P網(wǎng)絡(luò)的節(jié)點，隨機地選擇一個節(jié)點作為邏輯鄰居，而對底層網(wǎng)絡(luò)的物理拓撲不關(guān)心。這種機制很容易導(dǎo)致P2P邏輯覆蓋網(wǎng)與底層物理網(wǎng)路之間的拓撲失配，從而產(chǎn)生許多冗余消息。文獻[25]用實驗的方法已經(jīng)證明在提交的1 000 000查詢中，有超過70%的路徑遭遇了拓撲失配問題。基于拓撲優(yōu)化的方法，就是盡量優(yōu)化邏輯網(wǎng)絡(luò)拓撲，使其更好地與物理拓撲相匹配，從根本上消除冗余消息。

文獻[26]提出了一個Narada的終端多播系統(tǒng)。但是這種方法將引入很大的負載，其負載正比于系統(tǒng)規(guī)模，而且這種構(gòu)造最小生成樹的思想沒有考慮節(jié)點的動態(tài)加入和離開，所以這種方法在大規(guī)模、高度動態(tài)的P2P系統(tǒng)中很不合適。文獻[27，28]提出了基于IP地址的集群方法。但是這種方法不能保證映射的準確性，同時也縮小了搜索范圍。文獻[29]提出了一個基于距離構(gòu)造P2P拓撲的方法。該方法首先測量每個節(jié)點到多個相對穩(wěn)定的稱之為landmarks的Internet服務(wù)器之間的延時，籍此確定節(jié)點之間的距離。這種方法的缺點是測量需要在全局的P2P范圍內(nèi)進行，而且需要額外的landmarks支持；另外該方法也會縮小搜索的范圍。文獻[30]提出了一個動態(tài)拓撲自適應(yīng)算法Gia，以保證高容量的節(jié)點確實有高的度數(shù)，低容量的節(jié)點位于高容量節(jié)點的周邊，實現(xiàn)高容量的節(jié)點接收并處理多數(shù)查詢消息的思想。這種方法關(guān)注的是一種容量失配、能很好地處理異構(gòu)帶寬的情況，但它沒有闡述和解決物理拓撲及邏輯拓撲失配的問題。Apocrypha^[31]通過交換多對節(jié)點來優(yōu)化覆蓋網(wǎng)的拓撲結(jié)構(gòu)。

Liu等人^[32]提出了一個LTM算法。該算法在Gnutella 0.6的P2P協(xié)議中引入了一個TTL2-detectord的新消息類型，每個節(jié)點周期性地向兩跳范圍內(nèi)的節(jié)點提交一個TTL2-detectord類型的偵測消息，收到偵測消息的節(jié)點記錄相對延時信息，并計算與源節(jié)點的路徑費用。基于路徑費用，收到偵測消息多次的接收者（也就是只有入度大于2的節(jié)點才有可能優(yōu)化）可以偵測并消除許多低效、冗余的邏輯連接，添加物理上更近的節(jié)點作為其直接鄰居。LTM的主要缺點是：a）每次優(yōu)化操作只能處理兩條邊，這樣優(yōu)化算法需要頻繁運行，收斂速度較慢；b）為了偵測延時信息，需要同步所有節(jié)點的時鐘，需要網(wǎng)絡(luò)時鐘協(xié)議NTP^[25]的支持，而且同步性能對整個算法影響非常大。

Liu等人在文獻[33]中又提出了一個AOTO算法。Xiao等人^[34]對這一算法進行了進一步的改進和完善，并提出了一個自適應(yīng)連接建立的ACE算法。該算法首先在源節(jié)點與源節(jié)點某個直徑范圍內(nèi)的節(jié)點之間建立一個覆蓋多播樹，再進一步優(yōu)化不在多播樹上的鄰居節(jié)點。算法主要分為以下三個步驟：

a）鄰居費用表構(gòu)造和交換。每個節(jié)點采用與文獻[32]相似的方法探測與直接鄰居之間的費用，組成鄰居費用表；兩個鄰居節(jié)點相互交互它們的鄰居費用表，以了解鄰居節(jié)點集合中任何節(jié)點對之間的費用，籍此建立它到各邏輯鄰居節(jié)點間的拓撲結(jié)構(gòu)。

b）選擇泛洪。基于收集到的鄰居費用表，在源節(jié)點與其直接鄰居節(jié)點間建立MST樹，進一步將位于最小生成樹上的直接鄰居稱為泛洪鄰居，不位于最小生成樹上的直接鄰居稱為非泛洪鄰居。在轉(zhuǎn)發(fā)查詢消息時，有選擇地只轉(zhuǎn)發(fā)給它的泛洪鄰居。

c）拓撲優(yōu)化。每個節(jié)點盡量用物理相距較近的節(jié)點替換物理相距較遠的節(jié)點，非泛洪鄰居尋找合適的非泛洪鄰居的鄰居進行替換。

ACE算法的缺點是每個節(jié)點都需要進行鄰居費用表探測和優(yōu)化處理，每個節(jié)點的負載較大，而且僅僅能處理一跳范圍內(nèi)的邏輯鄰居，收斂速度也較慢。

針對ACE算法的缺點，文獻[35]提出了一個改進的SBO算法。該算法利用一個有效的策略將優(yōu)化任務(wù)分發(fā)給不同的節(jié)點。在SBO算法中，通過給節(jié)點著紅色或白色的方法來標記不同的節(jié)點，節(jié)點在進入P2P網(wǎng)絡(luò)時被分配以紅色或白色。節(jié)點將只與不同顏色的節(jié)點互連，也就是白色節(jié)點的所有直接鄰居都是紅色節(jié)點，紅色節(jié)點的所有直接鄰居都是白色節(jié)點。白色節(jié)點負責探測與鄰居節(jié)點的費用，并將費用信息發(fā)送給它的紅色鄰居節(jié)點；而紅色節(jié)點從白色節(jié)點收集到兩跳范圍內(nèi)的節(jié)點費用信息后，負責建立MST樹，進一步優(yōu)化拓撲結(jié)構(gòu)。SBO算法的主要步驟如下：

a）初始二分P2P覆蓋網(wǎng)建立。每個節(jié)點在加入P2P網(wǎng)絡(luò)時，隨機地被分配一種顏色：紅色或白色，并保證每個節(jié)點只與不同顏色的節(jié)點互連。

b）白色節(jié)點探測和報告費用。白色節(jié)點應(yīng)用與文獻[34]相似的方法，探測和建立鄰居費用表，并將費用表傳送給紅色鄰居節(jié)點。

c）紅色節(jié)點進行FC計算。在從鄰居節(jié)點收集到的鄰居費用表的基礎(chǔ)上，紅色節(jié)點為該節(jié)點和兩跳范圍內(nèi)的所有節(jié)點構(gòu)造MST樹。由于兩跳范圍內(nèi)已經(jīng)包括了白色節(jié)點，白色節(jié)點無須建立MST樹。

d）直接鄰居替換。這個優(yōu)化操作由白色節(jié)點完成。MST樹構(gòu)造好以后，一些白色節(jié)點記為E，成為了紅色節(jié)點記為P的非傳遞節(jié)點，所以白色節(jié)點E必須在紅色節(jié)點P兩跳范圍內(nèi)找到一個合適的紅色節(jié)點以替換節(jié)點P成為其直接鄰居節(jié)點。

相對于ACE^[34]，SBO算法有兩個突出的優(yōu)點：a）不像ACE讓每個節(jié)點都參與鄰居費用的探測和MST樹的構(gòu)造，SBO將所有節(jié)點分成紅白兩個節(jié)點群：白色節(jié)點群負責探測鄰居費用表；紅色節(jié)點群負責構(gòu)造MST樹。這樣顯然能減少每個節(jié)點的平均負載。b）由于SBO覆蓋網(wǎng)的拓撲具有二叉屬性，SBO無須增加任何負載，就可以構(gòu)造兩跳范圍內(nèi)的MST樹。但是SBO與算法LTM一樣也需要時鐘同步，需要網(wǎng)絡(luò)時鐘協(xié)議NTP的支持。

5結(jié)束語

在對近幾年提出的大量方法深入分析的基礎(chǔ)上，本文總結(jié)出一些重要結(jié)論，并進行了一些探討：

a）任何一類查詢方法的改進，都只注重和優(yōu)化了某一方面的性能，提高的效果非常有效。如果能將某幾類方法有機地集成，例如在基于拓撲優(yōu)化的方法中，集成基于緩存的方法、基于前向傳遞的方法，使它們相互補充，定能取得更好的效果。

b）現(xiàn)已提出的查詢方法中，多數(shù)主要是通過改變查詢消息轉(zhuǎn)發(fā)策略和優(yōu)化資源備份策略。但是基于拓撲優(yōu)化的查詢方法從本質(zhì)上對查詢效率進行了改進，不但減少了冗余流量，而且也改善了查詢響應(yīng)時間，具有較好的效果，將是一個不錯的優(yōu)化方向。

c）應(yīng)該盡量采用分布式技術(shù)，這樣在進行優(yōu)化操作時不需要知道全局信息，只需要收集優(yōu)化節(jié)點的局部信息，既增加了操作的可行性，又降低了操作負載；盡量采用基于測量的技術(shù)，在保證不縮小搜索范圍的情況下，能準確、動態(tài)地偵測并消除多數(shù)失配的連接，優(yōu)化拓撲結(jié)構(gòu)。

d）絕大多數(shù)查詢算法的查詢覆蓋率都受TTL值的影響，受制于網(wǎng)絡(luò)流量。TTL值不能設(shè)置得太大，所以查詢覆蓋率都比較小。基于概率的窮舉查詢方法提出了一個查詢和資源互相尋找對方的新思想，提供了一個全新的優(yōu)化思路，而且無須太大的負載就能實現(xiàn)窮盡的查詢，這應(yīng)該是未來資源發(fā)現(xiàn)算法的一個發(fā)展方向。

參考文獻：

［1］Gnutella[EB/OL].(2003). http://gnutella.wego.com.

[2]KaZaA[EB/OL].(2003). http://www.kazaa.com.

[3]SAROIU S， GUMMADI K P， DUNN R J， et al. An analysis of Internet content delivery systems[C]//Proc of the 5th Symp Operating Systems Design and Implementation. 2002.

[4]SEN S， WANG Jia. Analyzing peer-to-peer traffic across large networks[C]//Proc of ACM SIGCOMM Internet Measurement Workshop. 2002.

[5]RIPEANU M， LAMNITCHI A， FOSTER I. Mapping the Gnutella network[J].IEEE Internet Computing， 2002，6(1):50-57.

[6]YANG B， CARCIA-MOLINA H. Improving search in peer-to-peer networks[R].[S.l.]: Stanford University， 2002.

[7]ROUSSOPOULOS M， BAKER M. Practical load balancing for content requests in peer-to-peer networks[R].[S.l.]:Harvard University， 2003:34-45.

[8]SUEL T， MATHUR C，WU J W，et al.ODISSEA:a peer-to-peer architecture for scalable Websearch and informationretrieval[C]//Proc ofthe 6th International Workshop on the Web and Databases. 2003:67-72.

[9]LV Qin， CAO Pei， COHEN E， et al. Search and replication in unstructured peer-to-peer networks[C]//Proc of the 16th ACM Int’l Conf on Supercomputing. 2002:84-95.

[10]YANG B， GARCIA-MOLINA H. Efficient search in peer-to-peer networks[C]//Proc of the 22nd Int’l Conf on Distributed Computing Systems. 2002.

[11]ZHUANG Zhen-yun， LIU Yun-hao， XIAO Li，et al.Hybridperiodical flooding in unstructured peer-to-peer networks[C]//Procof Parallel Processing. 2003. 

[12]ROWSTRON A， DRUSCHEL P. Pastry:scalable distributed object location and routing for large-scale peer-to-peer systems[C]//Proc of IFIP/ACM International Conference on Distributed Systems Platforms (Middleware). 2001:329-350.

[13]RATNASAMY S， FRANCIS P， HANDLEY M，et al.A scalable content-addressable network[C]//Proc of ACM SIGCOMM. 2001.

[14]STOICA R M，KARGER D，KAASHOEK M F，et al.Chord:a scalable peer-to-peer lookup service for Internet applications[C]//Proc of ACM SIGCOMM. 2001.

[15]ZHAO B Y，KUBIATOWICZ J D， JOSEPH A D.Tapestry:an infrastructure for fault-resilient wide-area location and routing， UCB//CSD-01-1141[R].Berkeley:University of Calif， 2001.

[16]SRIPANIDKULCHAI K. The popularity of Gnutella queries and implications on scalability[EB/OL].(2001).http://www2.cs.cmu.edu/kunwadee/research/p2p/gnutella.html.

[17]MARKATOS E P. Tracing a large-scale peer-to-peer system: an hour in the life of Gnutella[C]//Proc of the 2nd IEEE/ACM Int’l Symp Cluster Computing and the Grid. 2002.

[18]WANG Chen， XIAO Li， LIU Yun-hao， et al.DiCAS:an efficient distributed caching mechanism for P2P systems[J].IEEE Trans on Parallel and Distributed Systems，2006，17(10):1097-1109.

[19]LIU Xiao-mei， LIU Yun-hao， XIAO Li. Improving query response delivery quality in peer-to-peer systems[J].IEEE Trans on Parallel and Distributed Systems，2006，17(11):1335-1347.

[20]SARSHAR N， BOYKIN P U， ROYCHOWDHURY V P. Percolation search in power law networks: making unstructured peer-to-peer networks scalable[C]//Proc of P2P’04.Washington DC:IEEE Compu-ter Society， 2004:2-9.

[21]FERREIRA A， RAXNANATHAN M K，AWARE A，et al. Search with probabilistic guarantees in unstructured peer-to-peer networks[C]//Proc of P2P’05.Washington DC:IEEE Computer Society，2005:165-172.

[22]TERPSTRA W W， KANGASHARJU J， LENG C，et al. BubbleStorm:resilient probabilistic and exhaustive peer-to-peer search[C]//Proc of SIGCOMM’07.Kyoto:[s.n.]， 2007:27-31.

[23]TERPSTRA W W， LENG C， BUCHMAXM A P. BubbleStorm: ana-lysis of probabilistic exhaustive search in a heterogeneous peer-to-peer system， TUD-CS-2007-2[R].Germany: Technische Universitat Darmstadt， 2007.

[24]KEMPE D，DOBRA A， GEHRKE J. Gossip-based computation of aggregate information[C]//Proc ofFOGS. 2003:482-491.

[25]NTP: the network time protocol[EB/OL].(2007). http://www.ntp.org/.

[26]CHU Yang-hua，RAO S C， ZHANG Hui. A case for end system multicast[C]//Proc of ACM SIGMETRICS. 2000.

[27]KRISHNAMURTHY E， WANG Jia. Topology modeling via cluster graphs[C]//Proc of SIGCOMM Internet Measurement Workshop. 2001.

[28]PADMANABHAN V N， SUBRAMANIAN L. An investigation of geographic mapping techniques for Internet hosts[C]//Proc of ACM SIGCOMM. 2001.

[29]XU Zhi-chen， TANG Chun-qiang， ZHANG Zheng. Building topology-aware overlays using global soft-state[C]//Proc of the 23rd Int’l Confon Distributed Computing Systems. 2003.

[30]CHAWATHE Y， RATNASAMY S， SHENKER L. Making Gnutella-like P2P systems scalable[C]//Proc of ACM SIGCOMM. 2003.

[31]GANESAN P，SUNQi-xiang， GARCIA-MOLINA H. Apocrypha: making P2P overlays network-aware[R].[S.l.]: Stanford University，2004.

[32]LIU Yun-hao， XIAO Li， LIU Xiao-mei，et al. Location awareness in unstructured peer-to-peer systems[J].IEEE Trans on Parallel and Distributed Systems，2005，16(2):163-174.

[33]LIU Yun-hao， ZHUANG Zhen-yun， XIAO Li，et al.AOTO:adaptive overlay topology optimization in unstructured P2P systems[C]//Proc ofIEEE GLOBECOM. 2003.

[34]XIAO Li， LIU Yun-hao， NI L M. Improving unstructured peer-to-peer systems by adaptive connection establishment[J]. IEEE Trans on Computers，2005，54(9):1091-1103.

[35]LIU Yun-hao， XIAO Li， NI L M. Building a scalable bipartite P2P overlay network[J].IEEE Trans on Parallel and Distributed Systems，2007，18(9):1296-1306.