一種改進的非結構化P2P網絡洪泛搜索機制

?

一種改進的非結構化P2P網絡洪泛搜索機制

盧葦，周韜，邢薇薇

(北京交通大學軟件學院，北京100044)

摘要:非結構化P2P網絡使用基于洪泛的查詢算法來進行資源搜索。然而，這種搜索機制隨著網絡節點的增多，網絡規模的增大，將產生大量的冗余查詢消息，會導致網絡流量急劇增加，引起網絡擁塞。提出了一種基于轉發區間的洪泛搜索機制FIFSM(forwarding interval based flooding search mechanism)，通過為消息分配不相交的轉發區間，使其沿著一棵生成樹的結構傳播，消除了消息環路，從而避免冗余消息的產生。FIFSM機制采用高效的網絡維護策略，能夠在動態環境下以較低的開銷保證網絡的穩定性。實驗結果表明，FIFSM機制能夠降低洪泛開銷，保證資源搜索的高成功率和低延遲，是一種有效的非結構化P2P網絡資源搜索機制。

關鍵詞:算法;計算機系統;資源優化;故障檢測;容錯性;網絡管理;網絡性能;丟包率;對等網絡;可靠性分析;穩定性;時延;拓撲結構;非結構化P2P網絡;洪泛搜索;轉發區間;生成樹

P2P網絡是一種應用層的分布式網絡，網絡中各節點地位是對等的。按照資源組織與定位方法，可以將其分為結構化P2P網絡［1-3］和非結構化P2P網絡［4］。其中，由于非結構化P2P網絡的簡單性和高魯棒性使其得到了深入的研究和廣泛的應用。

以Gnutella為代表的非結構化P2P網絡，是一種沒有特定拓撲結構的覆蓋網，通常建立在隨機圖上，使用基于洪泛的查詢算法進行資源搜索。節點通常把資源存儲在本地，也可將其備份到其他節點，以提高資源搜索的效率［5-6］。由于沒有拓撲結構上的約束，在節點頻繁加入和撤離的動態環境中，非結構化P2P網絡表現出良好的性能，并且僅需較少的維護開銷。由于每一次查詢都是在本地進行評估，所以它支持任意復雜類型的查詢，如語義查詢等。非結構化P2P網絡采用基于洪泛的查詢機制進行資源搜索。在洪泛的過程中，節點在有限的TTL內，不斷地向所有的鄰居節點轉發消息，直至查詢到所需的結果或TTL變為0。洪泛的優點是響應時間短、覆蓋范圍廣以及可靠性高，但洪泛會在網絡中產生大量的冗余消息，不僅增加了節點處理負擔，還會占用大量的網絡帶寬［7］。因此，如何在有效進行資源搜索的同時，降低冗余消息量，提高系統的可擴展性和穩定性，是非結構化P2P網絡的一個核心問題。

針對上述問題，許多研究工作者嘗試通過改進洪泛算法［8-11］，以提高非結構化P2P網絡的可擴展性。這些方法不再盲目地向所有鄰居節點轉發消息，而是有策略地選擇部分鄰居節點轉發消息。例如，隨機漫步算法［12］每次隨機選擇k個鄰居節點轉發消息，其搜索過程持續至查詢到所需的結果或TTL變為0。這樣就減少了洪泛搜索產生的網絡流量，但另一方面往往會產生較大的搜索延遲，并且搜索過程有可能丟失節點。另外一種優化策略是通過改變P2P網絡結構，以達到提高搜索效率的目的，其典型如樹形結構的P2P網絡［13-15］。在這樣的系統中，由于網絡結構為樹形，洪泛時消息到達任意節點僅一次，從而避免了冗余消息的產生。如果樹的拓撲結構是穩定的，且消息丟失率較低，則樹形結構的P2P網絡具有良好的性能。然而，在節點頻繁加入和撤離的動態環境中，樹的結構經常會被分割，造成大量消息的丟失。因此，為了獲得良好的可靠性，樹形結構P2P網絡需要探測消息丟失并從中恢復，這會導致恢復信息的延遲。尤其當故障頻繁發生時，還會引起相當大的開銷，這些都會限制系統的可擴展性。樹形結構P2P網絡的另一問題是負載不均衡，樹的內部節點承載了幾乎所有的轉發負載，而葉子節點卻不分擔負載。文獻［16］提出，將非結構化P2P網絡建立在結構化P2P網絡之上，利用其結構提高洪泛的性能。文獻［17］提出了一種基于生成樹的洪泛算法，該算法保證遍歷N個節點的系統只需要N－1個消息。但由于該算法基于chord［3］，很大程度上受其協議的限制，生成樹的度數較低，消息傳播延遲較大。由于chord鄰居表中每一個表項僅維護1個節點，故當節點失效時，洪泛會導致大范圍的節點丟失。動態環境中，其性能和可靠性高度依靠底層chord協議的維護能力。因此，由于協議的語義規定了覆蓋網節點應如何連接，在結構化P2P網絡上建立非結構化P2P網絡的思想并不適合高度結構化的DHT協議。

為此，本文提出了一種改進的非結構化P2P網絡洪泛搜索機制FIFSM (forwarding interval based flooding search mechanism)。此機制借鑒結構化網絡的策略，為每一個節點分配唯一的標識符，并建立有結構的鄰居表。此外，在洪泛查詢消息(下文簡稱查詢消息)中添加2個字段，用于限制節點的轉發范圍。FIFSM機制的實現主要包括2個部分:洪泛算法和網絡維護策略。FIFSM洪泛算法通過為消息分配不相交的轉發區間，使其沿著一棵生成樹的結構傳播，避免消息環路的產生，從而避免冗余查詢消息。鄰居表中添加了冗余節點，消息轉發過程中，如果遇到失效節點，選擇冗余節點轉發消息，降低節點失效造成消息丟失的可能，以提高洪泛算法的容錯能力。FIFSM采用高效的網絡維護策略，通過3種任務周期性地維護覆蓋網，保證了資源搜索的低延遲，提高了動態環境中資源搜索的成功率，使其維護開銷隨著節點變動率的增加而降低。

1　FIFSM搜索機制的定義

在FIFSM機制中，本文定義了標識符空間、鄰居表、以及前向和后向節點。

1．1標識符空間

FIFSM機制使用一致性哈希函數［18］為節點分配一個m位的標識符，m必須足夠大，以保證2個節點標識符是唯一的。標識符空間是以2m為模依次排列的一個標識符圓環。在標識符空間中，以任意一個點x為中心，把距離x大小為2m－1的點稱作x的界點，記作M(x)。圖1展示了以0為中心且m = 3的標識符空間。

圖1　標識符空間

1．2鄰居表

在FIFSM機制中，對任意節點x都要維護2個鄰居表，分別記錄標識符空間中順時針和逆時針方向x到M(x)區間中的鄰居節點。鄰居表有m－1個鄰居表項，其中，第i個表項包含變量start、end、interval和neighbors。start為標識符空間中與節點x相對距離為的標識符，end為標識符空間中與節點x相對距離為2i的標識符，［start，end］表示第i個表項所屬的區間。interval為起點是2i－1，終點是2i的區間，neighbors為第i個表項的鄰居節點列表，其節點數受限于節點冗余度H。鄰居表相關變量的定義如表1所示。

表1　鄰居表的變量定義

1．3前向和后向節點

在FIFSM機制中，節點x除了要維護鄰居表以外，還需要維護它的前向節點和后向節點。前向節點是節點x沿逆時針方向的第一個節點，記作predecessor(x)。后向節點是節點x沿順時針方向的第一個節點，記作successor(x)。如圖2所示，對于節點N0，它的前向節點predecessor(N0) = N7，它的后向節點successor(N0) = N1。

圖2　環狀拓撲結構

2　FIFSM搜索機制的洪泛算法

2．1算法定義

定義1轉發區間是標識符空間中的一段連續的區間，用于限制消息的轉發范圍。轉發區間定義為，其中，LL是轉發區間的左邊界，RL為轉發區間的右邊界。

定義2洪泛的消息定義為message(Info，LL，RL)，其中，LL和RL為消息中添加的2個m位的字段，表示消息的轉發區間，Info表示消息的內容。

2．2算法描述

在傳統的洪泛算法中，節點收到消息后，盲目地向所有鄰居節點轉發消息，導致消息的重復到達，產生大量的冗余消息。在FIFSM的洪泛算法中，節點收到消息后，僅向轉發區間內的部分鄰居節點轉發消息，當轉發區間內不存在鄰居節點時，則停止轉發。如圖3所示，其中圖3a)為節點之間的連接關系，圖3b)展示了洪泛時消息的轉發過程，圖中的區間為節點的轉發區間。例如，當節點5發起洪泛時，它選擇鄰居節點2，4，6，0發送消息，當節點2收到消息后，它向轉發區間中的鄰居節點3轉發消息。節點3收到消息后，發現轉發區間中不存在節點，則停止轉發，其他節點與之類似。從圖中可以看出，節點之間的轉發區間是不相交的，且每次轉發后，節點不會出現在之后的轉發區間中，保證了節點上消息的不重復到達，避免了冗余信息的產生。圖3c)展示了洪泛過程中消息的傳播路徑。可以看出，消息的傳播路徑是1棵生成樹，消息到達任意節點僅1次。

圖3　洪泛生成樹的生成過程

2．3算法實現

FIFSM的洪泛算法不僅能實現全網洪泛，也可以針對特定的范圍進行洪泛，本文稱之為范圍洪泛。

2．3. 1發起洪泛

1)全網洪泛

對于當前節點x，分別從鄰居表的每一個表項中選擇一個鄰居節點，對于從表項i中選出的鄰居節點y，把表項i的start和end賦予消息m的LL和RL字段，并向節點y發送消息m。如果表項j不存在鄰居節點，即neighbors為空，則將表項j所屬的區間［start，end)并入下一個節點的轉發區間中。

2)范圍洪泛

對于當前節點x，在鄰居表中找到一個目的范圍［LL，RL)內的鄰居節點y，向它發送一個封裝了［LL，RL)的消息m，節點y收到消息m后就會在該范圍內進行洪泛。

2．3. 2轉發消息

節點y收到消息m后，對于鄰居表中屬于轉發區間［LL，RL)內的表項i，檢查其neighbors是否為空，如果不為空，則從neighbors中選出一個鄰居節點z，把表項i的start和end賦予消息m的LL和RL字段，向鄰居節點z發送消息m。如果表項i不存在鄰居節點，即neighbors為空，則將表項i所屬的區間［start，end)并入下一個節點的轉發區間中。

2．4算法分析

假設洪泛過程中消息的每一次轉發都成功，且不存在失效節點，以下從節點丟失和消息冗余兩方面進行算法可行性分析。

1)節點丟失節點x轉發消息時，存在以下4種情況，如圖4所示。在圖4a)中，x的前向和后向節點都位于轉發區間［LL，RL)中，在圖4b)和圖4c)中，x的前向或后向節點位于轉發區間［LL，RL)中，對于這3種情況，x的前向和后向節點至少有一個位于轉發區間中，所以節點x可以把消息轉發出去，不丟失節點。在圖4d)中，x的前向和后向節點都不在轉發區間［LL，RL)中，由于前向和后向節點是離x最近的節點，因此［LL，RL)內不存在其他節點，節點x停止轉發，不丟失節點。綜上，該算法能夠保證遍歷所有的節點而不會出現節點丟失的現象。

圖4　消息轉發的情況

2)消息冗余

該算法保證了節點之間具有不相交的轉發區間，且被訪問過的節點不會出現在之后的轉發區間中，從而保證了每個節點收到且僅僅收到1次相同的消息，不會產生冗余消息。

3　FIFSM搜索機制的網絡維護

P2P網絡的環境是高度動態的，需要在頻繁加入和撤離節點時保證網絡的穩定性。網絡維護主要包括兩部分:節點的加入和撤離以及鄰居表的維護。

節點n加入網絡時，需要通過外部機制聯系到一個在線的節點，由該節點在全網洪泛一個節點連接請求。如果一個節點能夠接受節點n作為鄰居節點，則該節點就會直接發送回復消息給節點n，最后它們將對方添加到各自的鄰居表中。在FIFSM搜索機制中，當節點y收到節點x的連接請求時，在如下2種條件之一發生的情況下，節點y會主動連接節點x:①鄰居表項的節點數沒有達到節點冗余度H;②節點x是節點y的前向或后向節點。

而節點n撤離網絡時，會發送“leave”消息給它的鄰居節點，當這些節點收到“leave”消息時，便將節點n從其鄰居表中刪除。

3．1鄰居表維護

在動態環境下，鄰居表中可能出現失效節點、前向和后向節點不一致以及空鄰居表項，會降低FIFSM搜索機制的性能。為此，本文提出了3種任務，分別解決相應問題。其中，fault detector負責探測失效節點并修復鄰居表，SP fixer負責維護前向和后向節點的一致性，connect task負責為節點增加新的連接。

1) fault detector

節點的故障撤離會導致鄰居表中失效節點的產生，為了探測失效節點并修復鄰居表，fault detector周期性地(60 s)向鄰居節點發送“Are you there!”的探測消息，然后等待回復，如果在幾次詢問后仍未收到某個節點的回復，便向它發送“leave”消息，并把該節點從鄰居表中移除。

2) SP fixer

節點加入網絡后，由于網絡的動態性，節點之間維護的前向和后向節點可能不一致。在圖5a)中，節點a，b，c依次排列在節點標識符空間中，節點a維護的后向節點是c，而節點c維護的前向節點是b而不是a，即節點a的后向節點和節點c的前向節點不一致。這種情況下，節點a會在范圍內發起洪泛，當節點b收到消息后，發現節點a是自己的前向節點，則主動與節點a建立連接，這樣節點a的后向節點和節點b的前向節點都實現了更新。同理，圖5b)展示了節點c的前向節點的維護過程。

3) connect task

在動態的網絡中，節點的頻繁撤離會造成節點鄰居表中空表項的產生，即該表項的鄰居節點數為0，不利于查詢消息的高效轉發，增加洪泛搜索的延遲。為了降低洪泛搜索的延遲，需要為鄰居表增加連接。connect task會定期地檢查鄰居表中的每一個表項，并根據表項的鄰居節點數進行相應處理。

圖5　前向和后向節點的維護策略

1)當鄰居節點數為0時，connect task會主動在該表項所屬的區間［start，end］內洪泛。同時，接受來自其他節點的連接請求。

2)當鄰居節點數不為0且小于H時，connect task不會主動洪泛。但它仍然接受來自其他節點的連接請求。

3)當鄰居節點數達到H時，connect task既不主動洪泛，也不接受來自其他節點的連接請求。

4　仿真實驗

為了評估FIFSM搜索機制的性能，本文在OMNET++［19］仿真平臺上，建立了FIFSM搜索機制的仿真模型(以下簡稱為FIFSM模型)，并進行了一系列的實驗。實驗中，我們采用大小為215的標識符空間。

4．1靜態評估

為了評估FIFSM洪泛算法的有效性和容錯能力，本文進行了2組實驗。實驗開始后，所有的節點依次加入網絡，并在實驗過程中保持在線狀態。

4．1. 1FIFSM洪泛算法的有效性

為了把FIFSM洪泛算法與傳統的洪泛算法進行對比，本文參考Gnutella 0．4協議，在OMNET++平臺上建立了Gnutella的仿真模型，并在相同的條件下進行實驗。實驗中，我們設置不同的網絡規模，節點數N從23到214依次增長，選擇不同的節點發起洪泛，觀察是否所有的節點都被訪問到了，并統計產生的消息數。圖6為FIFSM模型和不同度數的Gnutella模型中洪泛遍歷所有節點產生的消息數對比實驗結果，其中，度數指Gnutella中每個節點的連接數。從圖中可以看出，在相同的網絡規模下，Gnutella模型產生了比FIFSM模型更多的消息，并隨著網絡規模和度數的增大而大幅度增加，而N個節點的FIFSM模型中僅產生N－1個消息。這是由于傳統的洪泛算法會產生大量冗余消息，而FIFSM洪泛算法不產生任何冗余消息。

圖6　洪泛遍歷所有節點的消息數

4．1. 2FIFSM洪泛算法的容錯能力

在FIFSM洪泛算法中，查詢消息攜帶了接收節點的轉發區間，查詢消息的丟失會導致該轉發區間內節點的丟失。為了評估FIFSM洪泛算法在故障環境下的容錯能力，本文定義α和β，分別代表鏈路故障下的丟包率和失效節點率。實驗中，我們設置N = 1 000和4 000。

實驗中，我們設置丟包率α在0．1%～0．6%范圍內，α= 0．1%表示1 000個消息會有1個消息丟失。節點加入網絡后，我們讓每個節點都發起1次洪泛，統計節點被訪問到的次數，并計算丟失的節點數。圖7為不同α對應的節點丟失率曲線。

圖7　鏈路故障下洪泛的節點丟失率

從圖中可以看出，隨著α的增加，節點丟失率呈線性增長，而且隨著節點數的增加，節點丟失率也隨之增加。可以看出，消息的丟失對搜索的成功率有著很大的影響，實際網絡中，可以采用TCP作為傳輸層協議，保證消息傳輸的可靠性，避免鏈路故障造成的消息丟失的現象。

為了評估FIFSM洪泛算法對節點故障的容錯能力，實驗中，令節點以β的比率故障離開，造成節點失效的情況，我們統計30 s內若干次洪泛后丟失的節點數。圖8展示了N=1 000的網絡，在不同的H和β下節點的丟失率曲線。

圖8　節點故障下洪泛的節點丟失率

從圖中可以看出，當H = 1時，節點的丟失率隨著β的增大而迅速增加，但隨著H的增大，節點丟失率顯著降低。當H = 4時，節點的丟失率幾乎為0。這是因為鄰居表采用了冗余節點機制，每一個表項的鄰居節點數可以達到H。當節點轉發消息的時候，如果遇到失效節點，可以選擇其他的冗余節點轉發消息。假設節點失效概率為p，則1次轉發失效的概率為pH。因此隨著H的增大，FIFSM洪泛算法的容錯能力也隨之提高。

4．2動態評估

為了評估動態環境下FIFSM機制的搜索成功率、維護開銷以及搜索延遲，根據文獻［20］的策略，本文建立了動態的網絡環境。我們在網絡中隨機指定一部分節點為“保留節點”，它們在實驗的過程中不離開網絡，始終保持在線狀態。其他的節點則為“非保留節點”，這些節點在實驗開始后，以0．5的概率選擇是否加入網絡。這樣，網絡初始化后，非保留節點有大約一半處于在線狀態，一半處于非在線狀態。在實驗過程中，每隔一段時間，實驗中設置為60 s，“非保留節點”以概率選擇是否從在線狀態轉換到非在線狀態，反之亦然，這樣我們就建立了一個變動率為λ的動態網絡。本文針對不同的λ值進行實驗，實驗的運行時間設置為3 600 s。

4．2. 1FIFSM的搜索成功率

為了評估動態環境中FIFSM機制的搜索成功率，實驗設置SP fixer工作周期為20 s，實驗開始后，網絡中的在線節點每10 s發起1次洪泛，“保留節點”將記錄被訪問到的次數，同時，我們還將記錄所有節點的總洪泛次數，于是就可以計算出實驗過程中每個“保留節點”的命中率，即訪問次數占總洪泛次數的百分比。通過對所有“保留節點”的命中率取平均值，則近似得到在當前λ的動態環境下洪泛的節點命中率。圖9展示了N=1 000和4 000時，λ在［0，0．3］范圍內的動態環境下，洪泛時節點的命中率曲線。從圖中可以看出，隨著λ的增大，節點命中率逐漸降低，但均保持在99．9%以上，并且不隨網絡規模的增大而劇烈變化，保持了動態環境下的高度可靠性。

圖9　動態環境下節點的命中率

4．2. 2FIFSM的維護開銷

為了評估FIFSM的網絡維護開銷，實驗中，我們主要統計節點平均每分鐘收到的控制消息數，這里的控制消息主要指SP fixer和connect task產生的控制消息。

設SP fixer工作周期為20 s，connect task工作周期為60 s，節點個數，圖10為不同λ下的控制消息數曲線。從圖中可以看出，SP fixer產生的控制消息數保持在7個左右，這是因為SP fixer僅在當前節點的前向和后向節點區間之內洪泛控制消息，所以消息不會被大范圍轉發。此外，connect task產生的控制消息數則隨著λ的增加而逐漸減小，因為當節點加入網絡的時候，會在全網進行洪泛，與網絡中的節點建立連接，增加其鄰居表的飽和度。雖然節點的離開可能會導致其他節點空路由表項的產生，但由于每個表項的節點數最多可以達到節點冗余度H，降低空表項產生的可能，因此隨著λ的增大，節點的加入越多，connect task洪泛的次數也隨之減少。綜上，在動態環境中，FIFSM的維護開銷隨著節點變動率λ的增加而降低，大大減少了網絡維護開銷。

圖10　動態環境中FIFSM的維護開銷

4．2. 3FIFSM的搜索延遲

為了評估FIFSM機制在動態環境中的搜索延遲，我們分別在、0．15、0．25的動態環境中進行實驗。設connect task的工作周期為60 s，實驗開始后，在線節點在每個固定的時間間隔(10 s)后發起一次洪泛，統計查詢消息經歷的跳數，實驗結果如表2所示。表2的第一列為實驗運行的參數，包括節點變動率λ﹑節點數N和節點冗余度H。第二列至第五列為不同跳數范圍內包含的消息數占總消息數的比例。最后一列為所有消息的平均跳數。實驗結果表明，在N=1 000和4 000的不同λ的動態網絡中，消息的跳數主要集中在8跳以內，平均跳數均小于5跳。對比實驗＜0．15，1 000，1＞和＜0．15，1 000，4＞以及＜0．15，4 000，1＞和＜0．15，4 000，4＞的結果可知，在相同的N和λ下，隨著H的增大，消息的平均跳數也隨之減少。綜上，FIFSM機制在動態環境中具有較低的洪泛搜索延遲。

表2　FIFSM的洪泛搜索延遲

5　結論

本文提出了一種改進的非結構化P2P網絡洪泛搜索機制-FIFSM，其主要內容和貢獻包括: (1)提出了在非結構化P2P網絡中使用一致性哈希函數為節點分配標識符，建立結構化的鄰居表的優化策略，并在鄰居表中增加冗余節點，提高洪泛算法在節點失效時的容錯能力。(2)提出并實現了基于轉發區間的洪泛算法，避免了冗余消息的產生，降低了洪泛搜索的代價。另外，增加了范圍洪泛的功能，以降低特定范圍內搜索的開銷。(3)提出了高效的網絡維護機制，其維護開銷隨著網絡動態程度的增加而降低。實驗結果表明，FIFSM機制不僅降低了非結構化P2P網絡基于洪泛的資源搜索的開銷，提高了非結構化P2P網絡的可擴展性，并且能夠在動態環境中保持高度的穩定性和可靠性。未來的工作將考慮節點之間的實際物理距離，建立與底層物理網絡更加匹配的覆蓋網拓撲，利用節點之間的鄰近性，進一步降低FIFSM洪泛搜索的消息延遲，合理利用網絡帶寬。

參考文獻:

［1］Ratnasamy S，Francis P，Handley M，et al．A Scalable Content-Addressable Network［C］∥Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，New York: ACM Press，2001: 149-160

［2］Rowstron A I T，Druschel P．Pastry: Scalable，Decentralized Object Location，and Routing for Large-Scale Peer-to-Peer Systems［C］∥Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg，Springer-Verlag，2001

［3］Stoica I，Morris R．Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications［J］．ACM Sigcomm Computer Communication Review，2001，31(4) : 149-160

［4］Clip2com．The Gnutella Protocol Specification．http: / /rfc-gnutella．sourceforge．net/Development，2010

［5］Cohen E，Shenker S．Replication Strategies in Unstructured Peer-to-Peer Networks［J］．ACM Sigcomm Computer Communication Review，2002，32(4) : 177-190

［6］Morselli R，Bhattacharjee B．Efficient Lookup on Unstructured Topologies［J］．IEEE Journal of Communications，2007，25(1) : 62-72

［7］Ritter J．Why Gnutella Can't Scale．No，Rea-lly．http: / /www．darkridge．com/～jpr5/doc/gnutella．html，2001

［8］朱桂明，郭得科，金士堯，等．基于副本復制和Bloom Filter的P2P概率路由算法［J］．軟件學報，2011，22(4) : 773-781 Zhu Guiming，Guo Deke，Jin Shiyao，et al．P2P Probabilistic Routing Algorithm Based on Data Copying and Bloom Filter［J］．Journal of Software，2011，22(4) : 773-781 (in Chinese)

［9］Kitamura H，Fujita S．A Biased k-Random Walk to Find Useful Files in Unstructured Peer-to-Peer Networks［C］∥2009 International Conference on Parallel and Distributed Computing，Applications and Technologies，2009: 210-216

［10］葉培順．非結構化P2P網絡的一種改進搜索算法［J］．計算機與現代化，2013(12) : 44-47 Ye Peishun．Improved Search Algorithm for Unstructured P2P Network［J］．Computer and Modernization，2013(12) : 44-47 (in Chinese)

［11］馬文明，孟祥武，張玉潔．面向非結構化P2P網絡的雙向隨機漫步搜索機制［J］．軟件學報，2012，23(4) : 894-911 Ma Wenming，Meng Xiangwu，Zhang YuJie．Bidirectional Random Walk Search Mecha-Nism for Unstructured P2P Network［J］．Journal of Software，2012，23(4) : 894-911 (in Chinese)

［12］Gkantsidis C，Mihail M，Saberi A．Random Walks in Peer-to-Peer Networks［C］∥IEEE Conference on Computer Communications，2004: 120-130

［13］Jagadish H V，Ooi B C，Vu Q H．BATON: a Balanced Tree Structure for Peer-to-Peer Networks［C］∥Proceedings of the 31st International Conference on Very Large Data Bases，2005

［14］Hu Z．Improved Algorithm of Unstructured P2P Network Topology Structure［C］∥2009 International Symposium on Intelligent U-biquitous Computing and Education，2009: 358-361

［15］楊亞，宋俊德．一種適合異構P2P網絡的樹形結構覆蓋層［J］．高技術通訊，2009，19(3) : 230-236 Yang Ya，Song Junde．TSOHEN: a Tree Structure Overlay for Heterogeneous P2P Networks［J］．Chinese High Technology Letters，2009，19(3) : 230-236 (in Chinese)

［16］Castro M，Costa M，Rowstron A．Should We Build Gnutella on a Structured Overlay?［J］ACM Siggomm Computer Communication Review，2004，34(1) : 131-136

［17］Elansary S，Alima L O，et al．Efficient Broadcast in Structured P2P Networks［J］．Peer-to-Peer Systems II，2003，2735: 304-314

［18］林雅榕，侯整風．對哈希算法SHA-1的分析和改進［J］．計算機技術與發展，2006，16(3) : 124-126 Lin Yarong，Hou Zhengfeng．Analysis and Improvement to Algorithm of SHA-1［J］．Computer Technology And Development，2006，16(3) : 124-126 (in Chinese)

［19］Melamed R，Keidar I．Araneola: A Scalable Reliable Multicast System for Dynamic Environments［J］．Journal of Parallel and Distributed Computing，2008，68(12) : 1539-1560

An Improved Flooding Based Search Mechanism in Unstructured P2P Network

Lu Wei，Zhou Tao，Xing Weiwei

(School of Software Engineering，Beijing Jiaotong University，Beijing 100044，China)

Abstract:In the unstructured P2P networks，the flooding-based search algorithm is used to search resources; however，with increasing nodes and network scale，flooding-based search will produce large amount of redundant query messages，which will lead to heavy traffic and congestion of the network．We propose a Forwarding Interval based Flooding Search Mechanism (FIFSM)．By assigning a disjoint forwarding interval to each message，they spread along a spanning tree to avoid message loops，thus eliminating redundant messages．The efficient network maintenance strategy is presented in FIFSM; this ensures the stability of the network in dynamic environment at a very low cost．Experimental results and their analysis show preliminarily that FIFSM，as an efficient search mechanism in unstructured P2P network，can reduce flooding overhead and achieve high success rate of resource search and low latency．

Key words:algorithms; computer system; cost reduction; fault detection; fault tolerance; network management ; network performance; packet loss; peer to peer networks; reliability analysis; stability; time delay; topology; unstructured P2P networks; flooding search; forwarding interval; spanning tree

作者簡介:盧葦(1963—)，北京交通大學教授，主要從事軟件服務工程研究。

收稿日期:2014-09-02基金項目:國家自然科學基金(61100143、61370128、61272353)、教育部新世紀人才計劃項目(NCET-13-0659)與北京高校青年英才計劃項目(YETP0583)資助

文章編號:1000-2758(2015) 02-0342-09

文獻標志碼:A

中圖分類號:TP393