無結構對等中網絡資源發現方法研究的最新進展

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



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

關鍵詞：無結構對等網絡； 拓撲失配； 覆蓋網； 搜索效率

中圖分類號：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



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

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

1基于前向傳遞的方法

基于前向傳遞方法的基本思想是通過優化或改變傳遞查詢請求消息的策略來減少網絡流量。

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

2基于緩存的方法

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

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

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

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

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

3基于查詢和數據雙重復制的方法

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

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

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

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

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

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

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

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

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

4基于拓撲優化的方法

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

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

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

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

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

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

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

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

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

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

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

c）紅色節點進行FC計算。在從鄰居節點收集到的鄰居費用表的基礎上，紅色節點為該節點和兩跳范圍內的所有節點構造MST樹。由于兩跳范圍內已經包括了白色節點，白色節點無須建立MST樹。

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

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

5結束語

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

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

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

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

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

參考文獻：

［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.