Ｄ－Ｆｌｏｏｄｉｎｇ：非結構化Ｐ２Ｐ網絡中高效搜索策略

摘 要：為了能夠在保持高覆蓋范圍的前提下大大減少冗余消息的數量，提出了一種新的基于連接度的搜索機制D-Flooding。D-Flooding在搜索的不同階段，依據連接度大小來選擇消息的轉發對象。分析和實驗結果表明，D-Flooding能夠提供較低負載的查詢，高效地應用于P2P搜索。與標準洪泛機制相比，在跳數不變的情況下，冗余消息的數量可減少84.5%以上，而消息的覆蓋范圍基本不變。

關鍵詞：對等網絡；洪泛；連接度

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2499-03

D-Flooding: efficient search algorithm in unstructured P2P networks

DONG Xi-guang，ZHUANG Lei，CHANG Yu-cun

(School of Information Engineering， Zhengzhou University， Zhengzhou450052，China)

Abstract:This paper proposed D-Flooding， an efficient degree-based flooding scheme， with the objective of minimizing the number of redundant messages and retaining the same message propagating scope as that of standard flooding. At the different searching steps， D-Flooding chose nodes to forward massages according to their degrees. Analysis and simulation results show that the D-Flooding scheme provides a low overhead broadcasting facility that can be effectively used in P2P searching. Compared with standard flooding used in Gnutella， it shows that the D-Flooding scheme with the same TTL can reduce up to more than 84.5% of flooding messages， and retain almost the same flooding scope.

Key words:peer-to-peer network; flooding; degree

0 引言

P2P（peer-to-peer）是構建于Internet 結構之上的一層覆蓋網^[1]，它可以給用戶提供各種各樣的服務，如文件共享、即時通信、對等計算、協同工作等。P2P的應用和普及改變了互聯網的格局，使網絡由中心化向邊緣化過渡。文件共享服務系統作為目前P2P網絡中最重要的應用之一，越來越引起人們的關注，它允許互聯網上的用戶直接訪問對方而無須中間實體。

早期的P2P文件共享系統，如Naptster^[2]使用一個中央服務器來存儲參與節點的索引，但這種中心化的設計仍然存在性能瓶頸和單點失效問題。經過不斷完善和發展，Gnutella^[3]應運而生，它是一個純分布式的文件共享系統，沒有中央索引服務器，所有的資源和服務分散在網絡中的所有節點上，從本質上解決了性能瓶頸和單點失效問題。由于網絡中沒有嚴格的拓撲和精確的文件定位信息，在文件定位和查詢中，保持一個足夠大的查詢覆蓋率顯得非常重要。而基于洪泛的搜索機制天生就有這個優點。

洪泛是當前搜索策略中最重要的搜索機制之一。在標準洪泛中，節點將接收到的查詢消息轉發給所有的鄰居節點（發送給該節點消息的鄰居節點除外），每個節點均擁有一個惟一的消息號ID；消息在到達已經收到過該消息的節點后，節點將該消息作為冗余消息丟棄；整個搜索的范圍由TTL（time to live）約束。消息產生時，被賦予一個初始TTL值（Gnutella默認為7）；查詢過程中，消息每向前一跳，TTL值減1；當消息變為冗余消息或TTL值為0時，該消息被丟棄。

洪泛機制具有很多優點，主要如下：a）高覆蓋范圍，文獻[1]指出在Gnutella網絡中采用標準洪泛搜索策略可以在7跳內到達整個系統中大約95%的節點；b）高可靠性，網絡中的節點可以自由地加入和離開網絡，當某些節點或服務失效時，由于在搜索過程中，所有可能路由的節點都被同時利用起來了，少量節點或服務失效對網絡的整體性能影響較小；c）低延時，在搜索過程中，越來越多的節點加入進來，它們以并行方式轉發消息，使得消息到達節點的數量幾乎以指數級的形式增長，直到網絡中絕大多數節點都被訪問過為止，從而可以快速地發現節點，縮短查詢和響應周期。正是由于這些原因，洪泛機制廣泛應用于非結構化P2P網絡中。然而，隨著P2P系統的流行和網絡規模的不斷擴大，查詢過程中產生的大量冗余消息嚴重吞噬了有限的網絡帶寬和CPU計算資源，制約了網絡的進一步發展^[4]。

為了解決這些問題，研究者們對Gnutella協議進行了改進，在原有Gnutella基礎上逐步形成了現代Gnutella網絡^[5]。它的主要特點是：a）半結構化。網絡中的節點分為超級節點和葉子節點，核心層由超級節點組成。b）動態查詢。與擴展環或迭代加深策略^[6]相似。現代Gnutella中，半結構化的拓撲結構可以大大減少轉發給葉子節點的消息，動態查詢也可以減少冗余消息的轉發。但網絡的核心層仍然是無結構的隨機網絡；消息的轉發又主要集中在核心層上；動態查詢在搜索流行的文件時有優勢，但在搜索不流行的文件時效率很低，這使得網絡搜索性能極不穩定。

正是由于P2P網絡的重要性和目前P2P網絡搜索中存在的一系列缺陷，很多研究人員在該領域中做了大量工作，在標準洪泛機制的基礎上出現了一些改進算法，如文獻[6]中提到的Modified-BFS、Rumor Mongering、Gnutella with Shortcuts、Iterative Deepening 和文獻[7]中提出的PartialMinFlood等。這些改進后的算法在某些特定條件下確實提高了搜索效率，進而提高了網絡的整體性能。然而，這些改進算法中要么因為要實現某些方面的改進而不得不在其他方面付出了昂貴的代價；要么改進后的算法過于復雜，難以實現；要么改進后的算法限制條件太多，實際網絡中難以滿足要求；要么對算法的改進非常有限。這些算法在目前P2P應用中均沒有得到普及。

本文在對標準洪泛機制進行研究的基礎上，針對洪泛搜索過程中在不同階段產生的不同結果^[8]提出了一種新的基于連接度的搜索算法（D-Flooding）。它將整個搜索過程分為兩個階段，在前幾跳中，優先選擇連接度大的節點轉發消息；在后幾跳中，優先選擇連接度小的節點轉發消息。這是因為，在前幾跳中，消息到達的節點數量還比較少，絕大部分節點還沒有被訪問過，選擇連接度大的節點，既有利于搜索范圍的迅速擴大，又有利于快速發現目標節點^[9]；在后幾跳中，網絡中大部分節點都已經接收過消息，由于網絡具有小群體^[10]特性，且密集程度比較高，連接度大的節點接收過消息的概率就比較大，后幾跳將消息發送給連接度大的節點產生冗余消息的概率也比較大，而到達新節點的概率就比較小。這種基于連接度的查詢策略，能有效地將兩個階段的優點結合在一起。

1 相關工作

為了解決在非結構化P2P中由于洪泛機制所引起的問題，研究人員提出了多種解決方法，包括以下三種：

a）Iterative Deepening^[11]。文獻[12]描述了兩種相似的算法，它們在增加深度的同時連續使用BFS搜索。在搜索終止條件與用戶定義的采樣數相關時這些算法的結果最好，很有可能一個小范圍洪泛就可以滿足查詢。這種算法與標準洪泛算法不同，它并不是一開始就給定一個確定不變的TTL值，而是在搜索過程中更多地考慮了動態因素，爭取在保證查詢覆蓋范圍的前提下盡量減少冗余消息。Iterative Deepening中，一開始給定一個較小的TTL值，在這個范圍內按照BFS機制向前推進，如果滿足查詢，則終止；否則，增大TTL值，在變化后的TTL范圍內再次按照BFS查詢，循環執行，直到查詢源節點收到足夠多的響應消息。這種算法在搜索網絡中的流行信息時效率較高，但在搜索一些不流行的信息時效率很低。

b）Gnutella with Shortcuts^[13]。這種算法主要是給類Gnutella圖加入捷徑（如到最近證明有用的節點的直接鏈接）。最開始的時候，捷徑表為空，仍然采用原始的洪泛機制定位文件，有節點響應時，響應的節點被請求者加入索引，認為它們可以為更多的請求提供服務。當再次發送查詢時，節點首先把查詢消息發送給其捷徑表中的節點（通常按照一定的策略對捷徑表中的節點進行排序），當所有捷徑均失敗時，再用洪泛算法定位文件。這種方法與DRLP^[14]相似，只是存儲的指針不止一個，而且保留它們的統計表。對于語義相關查詢，它能快速識別相關節點且大部分情況是可以用捷徑來定位目標的。此外，由于回溯采用洪泛機制，可想而知，它會有一個較高的查詢成功率。但另一方面，如果節點發出許多不相關的查詢或不存儲相關內容，或目標節點離開或目標文件被刪除時，捷徑就會失效，這樣，系統所花費的代價比標準洪泛還要多。

c）Morpheus^[14]。這種算法中，利用超級節點來提供部分中心定位服務的功能。超級節點就是網絡中表現為某些客戶機的中心服務器的那些節點。這些超級節點維護客戶機的索引并且引導相應的查詢和定位，超級節點又彼此相互連接組成了一個純Gnutella類型的網絡。顯然，在超級節點組成的類Gnutella網絡中采用洪泛搜索策略勢必要花費很大的代價。

以上三種算法是現行基于洪泛機制改進算法的典型代表。它們在某些方面，在某些特定的環境中確實能提高查詢效率，但它們始終存在很大的缺陷，因此很難在P2P系統中得到大規模的應用。本文提出的基于連接度的搜索算法（D-Floo-ding）必將憑借其簡單性、有效性成為非結構化P2P網絡中提高整體搜索效率的一項重要技術。

2 基于連接度的搜索策略

標準洪泛機制是根據消息的TTL值逐跳展開的，隨著跳數的增加，消息到達新節點的數量越來越多，產生的轉發消息數量也越來越多，但大部分都是冗余消息。為了觀察在標準洪泛中隨著跳數的增加，消息到達新節點的數量以及產生的冗余消息數量的變化情況，根據現代Gnutella網絡的特點，結合文獻[5]中指出的有關節點連接度分布情況和文獻[10]中指出的節點分布規律，構造了一個由70 000個節點構成的網絡N1，網絡中節點的分布符合小世界規律^[10]，平均連接度為25.313，在查詢過程中設定TTL=7（Gnutella默認值）。實驗結果如圖1、2所示。圖中分別列出了標準洪泛機制中每一跳時消息到達新節點數量百分比和產生冗余消息數量百分比?？梢钥闯?，查詢的覆蓋范圍和產生的冗余消息的數量存在明顯的階段性。

在前4跳時，每跳中消息到達新節點的數量持續上升。其中，第3、4跳時分別占總數的22.91%和69.55%，但從第5跳開始，消息到達新節點的數量迅速下降，在第5跳時僅占6.4%，第6、7跳時更低；而與之相對應的，在前4跳時，每跳中產生的冗余消息數量緩慢增加，尤其是前3跳中，產生的冗余消息數量之和不足總量的1%，但在第5跳時，冗余消息數量迅速增加，達到72.24%。

基于此，提出了一種新的基于連接度的搜索策略D-Flooding。它將整個搜索過程分為兩個階段，在每一階段依據連接度信息按照不同的策略轉發查詢消息。在前4跳時，優先把查詢消息轉發給連接度較大的鄰居節點，在保證有一個必需的查詢覆蓋范圍的同時，增加找到待查信息的可能性，因為在非結構P2P網絡中，連接度大的節點找到待查信息的可能性比較大^[9]；后3跳時，優先將查詢消息轉發給連接度較小的鄰居節點，盡量減少產生的冗余消息量，因為連接度大的節點在前幾跳中已經被訪問過的概率比連接度小的節點大。

在算法的實現過程中，既可以選擇一定比例的，也可以選擇一定數量的滿足條件的鄰居節點作為消息的轉發對象。本文對這兩種情況均作了分析。對每一種情況，網絡中的每個節點均維護鄰居節點的連接度信息，節點在收到消息向下轉發過程中，并不是向所有鄰居節點轉發，也不是盲目地隨機轉發，而是在搜索的不同階段根據鄰居節點的連接度信息依據不同策略來選擇消息的轉發對象。這樣，一方面在前幾跳中優先選擇那些連接度大的節點來轉發消息，可以迅速擴大消息的覆蓋范圍，增加找到待查信息的可能性；另一方面，在后幾跳中優先選擇那些連接度小的節點來轉發消息，可以有效地避免消息再次發送到那些已經被訪問過的節點，從而提高網絡的搜索效率。

由于Gnutella網絡具有高度的自治性和動態性，在選擇消息的轉發對象時，應盡量參考本地信息，盡量避免增加網絡的負擔，從而降低網絡的開銷。同時也要充分利用Gnutella網絡自身所具有的一些特性，如網絡密集程度高、具有小群體特性。為此，在基于連接度的搜索策略中作出如下設定：a）網絡中每個節點都要把自己的連接度及時通知給鄰居節點；b）節點根據自己掌握的鄰居節點的連接度信息來選擇相應鄰居節點作為消息的轉發對象；c）當網絡中有節點加入或離開，或某些節點的連接度發生變化時，重新計算受到影響的節點的連接度信息；d）整個搜索策略中對于冗余消息的處理與標準洪泛機制一致。需要說明的是，上述的相關開銷，與維護超級節點的索引文件或基于興趣分類等搜索機制相比，要小得多^[8]。

3 實驗結果與分析

目前，對搜索效率的評價主要參考三個方面，即查詢覆蓋率、帶寬利用率和動態拓撲適應性。在前文構造的類Gnutella網絡N1的基礎上，著重從這三個方面來評價D-Flooding算法的性能。在實驗過程中，設定TTL=7（Gnutella的默認值）。消息轉發過程中，在1~4跳時，節點優先選擇連接度較大的鄰節點作為消息轉發對象，轉發消息的個數（或比例）為F（或Fv）。在5~7跳時，節點優先選擇連接度較小的鄰節點作為消息轉發對象，轉發消息的個數（或比例）為E（或Ev）。如果所設定的轉發消息數量超出了當前節點的連接度，則按照標準洪泛機制轉發。另外，為了便于觀察，在整個實驗過程中都以標準洪泛機制為基準。

首先以F=25（網絡中平均連接度），E=1，2，3，4，5，6，7為例，在圖3、4中分別繪出消息覆蓋率和冗余消息百分比的變化情況。圖3、4中同時給出了D-Flooding和PartialMinFlood的結果。

從圖中可以看出，D-Flooding和PartialMinFlood的消息覆蓋范圍都在96%以上，而D-Flooding的冗余消息百分比在15%~33%，PartialMinFlood冗余消息百分比在26%~46%。文獻[8]中指出LightFlood若要達到同樣的覆蓋范圍，則需要額外增加2或3跳。不難看出，D-Flooding要優于PartialMinFlood和LightFlood，與標準洪泛相比，更是大大提高了效率，可以在搜索范圍基本不變的情況下，減少冗余消息達84.5%以上。

為了進一步研究D-Flooding，在實驗過程中不斷改變F（Fv）和E（Ev）的值，在不同情況下觀察D-Flooding的性能。筆者發現，無論是在前幾跳或后幾跳中，隨著選擇轉發的消息個數（或比例）的增加，消息的覆蓋范圍都隨之增大，而冗余消息的數量也有所增加。部分實驗結果如圖5、6所示。從中可以看出：一般情況下，隨著選擇轉發消息數量的增加；消息的覆蓋范圍和產生冗余消息的數量也會持續增加，而當選擇的轉發消息數量到達一定比例之后，若繼續增加消息的轉發數量，則消息的覆蓋范圍增長緩慢，相比之下，冗余消息數量增長較快。在具體應用中，可以根據實際情況來設置F（Fv）和E（Ev）值，爭取能達到一個相對最優的結果。在這里，只給出針對一般情況的推薦值：F取網絡的平均連接度，E取網絡平均連接度的20%。

在研究過程中筆者還發現，在消息轉發過程中，對于那些連接度大的節點，可以只選擇一定比例的鄰節點作為轉發對象。而對于連接度小的節點，若僅僅選擇部分鄰節點作為消息轉發對象則效果不好。對于這部分小連接度的節點，按照標準洪泛機制轉發消息，效果反而較好。

為了觀察D-Flooding對動態網絡的適應性，實驗中隨機移除一些節點來觀察消息覆蓋范圍的變化情況。實驗結果如圖7所示。當失效的網絡節點占總節點數的比例較小時，消息的覆蓋范圍基本不變。事實上，即使網絡中有近1/3的節點失效，消息的覆蓋范圍仍然可以達到60%以上。

4 結束語

標準洪泛機制是非結構化P2P系統中的一個重要機制，它的高覆蓋率、高動態適應性一直都是人們追求的重要指標，但它同時也產生大量的冗余消息，嚴重浪費了網絡帶寬，限制了網絡的可擴展性。本文提出的D-Flooding機制是一種簡單的機制，它可以在高覆蓋率、高動態適應性的前提下，大大減少冗余消息產生量。實驗結果表明，在覆蓋范圍保持96.46%~99.99%之間時，冗余消息減少可達84.5%以上，與現有搜索算法相比，顯示出了巨大的優越性。同時，本文比較系統地分析了D-Flooding在不同參數環境下的性能，給出了針對一般情況的推薦值。它可大幅度地提高現有機制的性能，如Iterative Deepening、Gnutella with Shortcuts、Morpheus等。因此筆者相信，憑借其簡單性有效性，D-Flooding機制將成為P2P系統中一項應用于消息高效查詢的重要技術。

參考文獻:

[1]RIPEANU M，FOSTER I，IAMNITCHI A. Mapping the Gnutella network[J].IEEE Internet Computing， 2002，60（1）：50-57.

[2]The Napster homepage[DB/OL]. http://www.napster.com/.

[3]The Gnutella website[DB/OL]. http://www.gnutella.com.

[4]CHAWATHE Y，RATNASAMY S，BRESLAU L，et al. Making Gnutella like P2P systems scalable[C]//Proc ofConference on Applications， Technologies， Architectures， and Protocols for Computer Communications.New York: ACM Press，2003:407-418.

[5]STUTZBACH D， REJAIE R. Characterizing today’s Gnutella topology， CIS-TR-04-02 [R].Oregon: Department of Computer Science， University of Oregon，2004.

[6]TSOUMAKOS D，ROUSSOPOULOS N. Analysis and comparison of P2P search methods， CS-TR-4539，UMIACS-TR-2003-107[R].[S.l.]:University of Maryland，2003.

[7]楊東峰，莊雷. 基于稠密P2P網絡搜索機制的研究[J]. 計算機工程與應用， 2006， 42(24):111-114.

[8]JIANG Song， GUO Lei， ZHANG Xiao-dong . LightFlood: an efficient flooding scheme for file search in unstructured peer-to-peer systems[C]//Proc of International Conference on Parallel Processing . 2003.

[9]黃道穎，黃建華，莊雷，等. 基于主動網絡的分布式P2P網絡模型[J]. 軟件學報， 2004， 15(7):1081-1089.

[10]黃道穎，劉剛，張堯，等. 利用Gnutella網絡的拓撲特性改進其可擴展性[J].計算機工程與應用， 2003， 39(26): 58-60.

[11]YANG B， GARCIA-MOLINA H. Improving search in peer-to-peer networks[C]//Proc of the 22nd International Conference on Distributed Computing Systems.[S.l.]：IEEE Computer Society，2002：5-14.

[12]LV C， CAO P， COHEN E，et al. Search and replication in unstructured peer-to-peer networks[C]//Proc of the 16th ACM International Conference on Supercomputing.New York:ACM Press，2002：84-95.

[13]SCIPANIDKULCHAI K，MAGGS B，ZHANG H. Efficient content location using interest-based locality in peer-to-peer systems[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies.2003.

[14]YANG B，GARCIA-MOLINA H. Designing a super-peer network[C]//Proc of the 19th International Conference on Data Engineering.[S.l.]：IEEE Computer Society，2003.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文