一種改進的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)洪泛搜索機制

?

一種改進的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)洪泛搜索機制

盧葦，周韜，邢薇薇

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

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

關(guān)鍵詞:算法;計算機系統(tǒng);資源優(yōu)化;故障檢測;容錯性;網(wǎng)絡(luò)管理;網(wǎng)絡(luò)性能;丟包率;對等網(wǎng)絡(luò);可靠性分析;穩(wěn)定性;時延;拓撲結(jié)構(gòu);非結(jié)構(gòu)化P2P網(wǎng)絡(luò);洪泛搜索;轉(zhuǎn)發(fā)區(qū)間;生成樹

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

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

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

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

1　FIFSM搜索機制的定義

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

1．1標(biāo)識符空間

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

圖1　標(biāo)識符空間

1．2鄰居表

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

表1　鄰居表的變量定義

1．3前向和后向節(jié)點

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

圖2　環(huán)狀拓撲結(jié)構(gòu)

2　FIFSM搜索機制的洪泛算法

2．1算法定義

定義1轉(zhuǎn)發(fā)區(qū)間是標(biāo)識符空間中的一段連續(xù)的區(qū)間，用于限制消息的轉(zhuǎn)發(fā)范圍。轉(zhuǎn)發(fā)區(qū)間定義為，其中，LL是轉(zhuǎn)發(fā)區(qū)間的左邊界，RL為轉(zhuǎn)發(fā)區(qū)間的右邊界。

定義2洪泛的消息定義為message(Info，LL，RL)，其中，LL和RL為消息中添加的2個m位的字段，表示消息的轉(zhuǎn)發(fā)區(qū)間，Info表示消息的內(nèi)容。

2．2算法描述

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

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

2．3算法實現(xiàn)

FIFSM的洪泛算法不僅能實現(xiàn)全網(wǎng)洪泛，也可以針對特定的范圍進行洪泛，本文稱之為范圍洪泛。

2．3. 1發(fā)起洪泛

1)全網(wǎng)洪泛

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

2)范圍洪泛

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

2．3. 2轉(zhuǎn)發(fā)消息

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

2．4算法分析

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

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

圖4　消息轉(zhuǎn)發(fā)的情況

2)消息冗余

該算法保證了節(jié)點之間具有不相交的轉(zhuǎn)發(fā)區(qū)間，且被訪問過的節(jié)點不會出現(xiàn)在之后的轉(zhuǎn)發(fā)區(qū)間中，從而保證了每個節(jié)點收到且僅僅收到1次相同的消息，不會產(chǎn)生冗余消息。

3　FIFSM搜索機制的網(wǎng)絡(luò)維護

P2P網(wǎng)絡(luò)的環(huán)境是高度動態(tài)的，需要在頻繁加入和撤離節(jié)點時保證網(wǎng)絡(luò)的穩(wěn)定性。網(wǎng)絡(luò)維護主要包括兩部分:節(jié)點的加入和撤離以及鄰居表的維護。

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

而節(jié)點n撤離網(wǎng)絡(luò)時，會發(fā)送“l(fā)eave”消息給它的鄰居節(jié)點，當(dāng)這些節(jié)點收到“l(fā)eave”消息時，便將節(jié)點n從其鄰居表中刪除。

3．1鄰居表維護

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

1) fault detector

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

2) SP fixer

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

3) connect task

在動態(tài)的網(wǎng)絡(luò)中，節(jié)點的頻繁撤離會造成節(jié)點鄰居表中空表項的產(chǎn)生，即該表項的鄰居節(jié)點數(shù)為0，不利于查詢消息的高效轉(zhuǎn)發(fā)，增加洪泛搜索的延遲。為了降低洪泛搜索的延遲，需要為鄰居表增加連接。connect task會定期地檢查鄰居表中的每一個表項，并根據(jù)表項的鄰居節(jié)點數(shù)進行相應(yīng)處理。

圖5　前向和后向節(jié)點的維護策略

1)當(dāng)鄰居節(jié)點數(shù)為0時，connect task會主動在該表項所屬的區(qū)間［start，end］內(nèi)洪泛。同時，接受來自其他節(jié)點的連接請求。

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

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

4　仿真實驗

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

4．1靜態(tài)評估

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

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

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

圖6　洪泛遍歷所有節(jié)點的消息數(shù)

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

在FIFSM洪泛算法中，查詢消息攜帶了接收節(jié)點的轉(zhuǎn)發(fā)區(qū)間，查詢消息的丟失會導(dǎo)致該轉(zhuǎn)發(fā)區(qū)間內(nèi)節(jié)點的丟失。為了評估FIFSM洪泛算法在故障環(huán)境下的容錯能力，本文定義α和β，分別代表鏈路故障下的丟包率和失效節(jié)點率。實驗中，我們設(shè)置N = 1 000和4 000。

實驗中，我們設(shè)置丟包率α在0．1%～0．6%范圍內(nèi)，α= 0．1%表示1 000個消息會有1個消息丟失。節(jié)點加入網(wǎng)絡(luò)后，我們讓每個節(jié)點都發(fā)起1次洪泛，統(tǒng)計節(jié)點被訪問到的次數(shù)，并計算丟失的節(jié)點數(shù)。圖7為不同α對應(yīng)的節(jié)點丟失率曲線。

圖7　鏈路故障下洪泛的節(jié)點丟失率

從圖中可以看出，隨著α的增加，節(jié)點丟失率呈線性增長，而且隨著節(jié)點數(shù)的增加，節(jié)點丟失率也隨之增加?？梢钥闯?，消息的丟失對搜索的成功率有著很大的影響，實際網(wǎng)絡(luò)中，可以采用TCP作為傳輸層協(xié)議，保證消息傳輸?shù)目煽啃裕苊怄溌饭收显斐傻南G失的現(xiàn)象。

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

圖8　節(jié)點故障下洪泛的節(jié)點丟失率

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

4．2動態(tài)評估

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

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

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

圖9　動態(tài)環(huán)境下節(jié)點的命中率

4．2. 2FIFSM的維護開銷

為了評估FIFSM的網(wǎng)絡(luò)維護開銷，實驗中，我們主要統(tǒng)計節(jié)點平均每分鐘收到的控制消息數(shù)，這里的控制消息主要指SP fixer和connect task產(chǎn)生的控制消息。

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

圖10　動態(tài)環(huán)境中FIFSM的維護開銷

4．2. 3FIFSM的搜索延遲

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

表2　FIFSM的洪泛搜索延遲

5　結(jié)論

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

參考文獻:

［1］Ratnasamy S，F(xiàn)rancis 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］朱桂明，郭得科，金士堯，等．基于副本復(fù)制和Bloom Filter的P2P概率路由算法［J］．軟件學(xué)報，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，F(xiàn)ujita 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］葉培順．非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的一種改進搜索算法［J］．計算機與現(xiàn)代化，2013(12) : 44-47 Ye Peishun．Improved Search Algorithm for Unstructured P2P Network［J］．Computer and Modernization，2013(12) : 44-47 (in Chinese)

［11］馬文明，孟祥武，張玉潔．面向非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的雙向隨機漫步搜索機制［J］．軟件學(xué)報，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］楊亞，宋俊德．一種適合異構(gòu)P2P網(wǎng)絡(luò)的樹形結(jié)構(gòu)覆蓋層［J］．高技術(shù)通訊，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］林雅榕，侯整風(fēng)．對哈希算法SHA-1的分析和改進［J］．計算機技術(shù)與發(fā)展，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—)，北京交通大學(xué)教授，主要從事軟件服務(wù)工程研究。

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

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

文獻標(biāo)志碼:A

中圖分類號:TP393