董西廣，張治國(guó)，張文欣

(1.河南工程學(xué)院 數(shù)理科學(xué)系,河南 鄭州 451191; 2.河南工程學(xué)院 計(jì)算機(jī)科學(xué)與工程系,河南 鄭州 451191;3.鄭州大學(xué) 信息工程學(xué)院，河南 鄭州 450001)

對(duì)等網(wǎng)絡(luò)(P2P)是構(gòu)建于因特網(wǎng)結(jié)構(gòu)之上的一層覆蓋網(wǎng)[1]，所謂對(duì)等是相對(duì)于傳統(tǒng)的客戶/服務(wù)器(C/S)模式而言的，它是指網(wǎng)絡(luò)中所有的主機(jī)處于同等地位.在C/S模式網(wǎng)絡(luò)中,客戶機(jī)和服務(wù)器處于不同的地位，實(shí)現(xiàn)不同的功能.中央服務(wù)器是整個(gè)系統(tǒng)的核心，它完成網(wǎng)絡(luò)中的大部分工作.客戶機(jī)需要服務(wù)時(shí)可直接向服務(wù)器發(fā)出請(qǐng)求信息，服務(wù)器完成相應(yīng)的功能后，把響應(yīng)結(jié)果返回給請(qǐng)求客戶機(jī).C/S模式對(duì)服務(wù)器的過(guò)分依賴，使得網(wǎng)絡(luò)容易產(chǎn)生瓶頸和單點(diǎn)失效的問(wèn)題，這限制了網(wǎng)絡(luò)的可擴(kuò)展性，嚴(yán)重地影響了網(wǎng)絡(luò)的整體性能.同時(shí)，處于邊緣節(jié)點(diǎn)的客戶機(jī)，其潛力常常被忽視而得不到充分發(fā)揮，造成了網(wǎng)絡(luò)資源的浪費(fèi).P2P技術(shù)的出現(xiàn),為解決上述問(wèn)題提供了新的思路.

早期流行的P2P系統(tǒng)，如Naptster，它借助中央服務(wù)器來(lái)存儲(chǔ)節(jié)點(diǎn)間的索引，節(jié)點(diǎn)與節(jié)點(diǎn)之間處于同等地位，發(fā)揮了邊緣節(jié)點(diǎn)的服務(wù)能力，提高了系統(tǒng)的可擴(kuò)展性，但這種中心化的設(shè)計(jì)仍然無(wú)法徹底解決單點(diǎn)失效和性能瓶頸的問(wèn)題.經(jīng)過(guò)不斷的改進(jìn)和完善，Gnutella網(wǎng)絡(luò)應(yīng)運(yùn)而生，它是一個(gè)純分布式的文件共享系統(tǒng)，沒(méi)有中央服務(wù)器，所有的資源和服務(wù)都分散在網(wǎng)絡(luò)中的不同節(jié)點(diǎn)上，從本質(zhì)上避免了單點(diǎn)失效和性能瓶頸問(wèn)題.但是,節(jié)點(diǎn)間完全對(duì)等的模式也使得網(wǎng)絡(luò)中由于沒(méi)有嚴(yán)格的拓?fù)浠蚓_的文件定位信息而對(duì)傳統(tǒng)C/S模式中很容易實(shí)現(xiàn)的資源搜索技術(shù)造成了很大的困難，在查詢過(guò)程中保持一個(gè)足夠大的查詢覆蓋范圍就顯得尤為重要,而洪泛的搜索機(jī)制天生就有這個(gè)優(yōu)點(diǎn).

洪泛機(jī)制是當(dāng)前搜索算法中最重要的策略之一.在標(biāo)準(zhǔn)洪泛中，每個(gè)節(jié)點(diǎn)都擁有唯一的消息ID，節(jié)點(diǎn)通過(guò)把查詢消息發(fā)送給所有的鄰居節(jié)點(diǎn)(發(fā)送該消息給該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)除外)來(lái)完成本次消息的轉(zhuǎn)發(fā).節(jié)點(diǎn)在收到重復(fù)到達(dá)的相同消息后，就把該消息作為冗余消息直接丟棄，搜索過(guò)程的深度受消息生存期TTL的約束.消息產(chǎn)生時(shí)，被賦予一個(gè)初始的TTL值，在查詢過(guò)程中，消息每向前一跳，TTL就減1，當(dāng)消息變成冗余消息或TTL為0時(shí)，該消息被丟棄.

洪泛機(jī)制最大的優(yōu)點(diǎn)是能夠保持較高的查詢覆蓋范圍，文獻(xiàn)[1]指出，Gnutella網(wǎng)絡(luò)中采用標(biāo)準(zhǔn)洪泛搜索策略消息可以在7跳內(nèi)到達(dá)整個(gè)系統(tǒng)中95%以上的節(jié)點(diǎn)，這對(duì)于查詢的完整性和有效性來(lái)說(shuō)至關(guān)重要.在查詢中，節(jié)點(diǎn)以并行方式轉(zhuǎn)發(fā)消息的形式也有助于消息快速到達(dá)目標(biāo)節(jié)點(diǎn)，從而縮短查詢和響應(yīng)的時(shí)間.正是由于這些原因，洪泛算法被廣泛應(yīng)用于非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)中.然而，隨著P2P系統(tǒng)的流行和網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，洪泛查詢中產(chǎn)生的大量冗余消息也嚴(yán)重吞噬了有限的網(wǎng)絡(luò)帶寬和CPU計(jì)算資源，制約了網(wǎng)絡(luò)的更進(jìn)一步發(fā)展[2].

針對(duì)洪泛機(jī)制產(chǎn)生大量冗余消息的問(wèn)題，根據(jù)搜索在不同階段產(chǎn)生的不同結(jié)果，提出了一種新的基于消息跳數(shù)的分段搜索策略hpsearch.hpsearch策略的主要思想如下：根據(jù)標(biāo)準(zhǔn)洪泛機(jī)制中消息在處于不同跳數(shù)時(shí)所表現(xiàn)出的不同性能，對(duì)整個(gè)搜索過(guò)程進(jìn)行分段處理，低跳時(shí)仍然采用標(biāo)準(zhǔn)洪泛機(jī)制，為查詢覆蓋范圍積累必要的廣度，同時(shí)有助于查詢消息快速接近目標(biāo)節(jié)點(diǎn)；高跳時(shí)不再向所有的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢消息，僅僅隨機(jī)選擇其中的部分節(jié)點(diǎn)作為轉(zhuǎn)發(fā)對(duì)象，盡量降低冗余消息的數(shù)量.

1 相關(guān)搜索算法

在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，針對(duì)資源搜索問(wèn)題提出了很多影響廣泛的改進(jìn)算法，如文獻(xiàn)[3]提到的Rumor Mongering協(xié)議、文獻(xiàn)[4]提到的Iterative Deepening協(xié)議、文獻(xiàn)[5]提到的Gnutella with Shortcuts算法、文獻(xiàn)[6]提到的Intelligent Search算法和文獻(xiàn)[7]提到的Local Indices方法等.在Rumor Mongering算法中,消息在每一跳時(shí)僅隨機(jī)選擇部分節(jié)點(diǎn)而不是全部鄰居節(jié)點(diǎn)來(lái)作為消息的轉(zhuǎn)發(fā)對(duì)象，減少了冗余消息的數(shù)量，但屢次轉(zhuǎn)發(fā)時(shí)節(jié)點(diǎn)選擇的部分性和隨機(jī)性降低了消息查詢的完整性和可靠性.Iterative Deepening算法在增加深度的同時(shí)連續(xù)使用BFS搜索，初始時(shí)給定一個(gè)TTL值，在該范圍內(nèi)如果有滿足查詢的結(jié)果響應(yīng)，則查詢結(jié)束，否則增大TTL值，繼續(xù)按照BFS策略進(jìn)行查詢.該算法查找熱點(diǎn)信息較快，但對(duì)于一般信息的查找則可能與標(biāo)準(zhǔn)洪泛機(jī)制的開銷相當(dāng).Gnutella with Shortcuts算法在系統(tǒng)中引入捷徑表，查詢時(shí)優(yōu)先選擇捷徑表中的節(jié)點(diǎn)，當(dāng)所有捷徑都無(wú)效時(shí)再用洪泛算法.該算法在捷徑有效時(shí)能夠快速發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)，但當(dāng)原始捷徑表中的目標(biāo)文件被刪除或目標(biāo)節(jié)點(diǎn)離開時(shí)，系統(tǒng)的開銷甚至?xí)群榉簷C(jī)制還要高.Intelligent Search算法對(duì)鄰居節(jié)點(diǎn)進(jìn)行了簡(jiǎn)單的跟蹤統(tǒng)計(jì)，如返回查詢結(jié)果數(shù)量和網(wǎng)絡(luò)延遲等信息，根據(jù)相應(yīng)的標(biāo)準(zhǔn)選擇最好的鄰居轉(zhuǎn)發(fā)查詢，該算法雖然有助于快速接近目標(biāo)節(jié)點(diǎn)、降低冗余消息數(shù)量，但對(duì)鄰居節(jié)點(diǎn)的跟蹤統(tǒng)計(jì)也要引入不小的開銷.Local Indices算法是以索引為基礎(chǔ)、系統(tǒng)中每個(gè)節(jié)點(diǎn)都保存與它距離為k內(nèi)的所有節(jié)點(diǎn)上數(shù)據(jù)的索引，索引信息的有效性和維護(hù)索引的復(fù)雜度是影響該算法性能的重要因素.

以上改進(jìn)算法確實(shí)在某些方面提高了效率、改善了網(wǎng)絡(luò)的整體性能，但這些算法要么以系統(tǒng)搜索的完整性和可靠性為代價(jià)，要么僅僅適用于某些特定環(huán)境，要么以增加額外的開銷為代價(jià)，難以在P2P網(wǎng)絡(luò)中獲得大規(guī)模的應(yīng)用，無(wú)法在對(duì)等網(wǎng)絡(luò)應(yīng)用中得到普及.

2 基于消息跳數(shù)的分段搜索策略

洪泛機(jī)制依據(jù)消息的生存期逐跳展開，消息每向前一跳到達(dá)一個(gè)新的節(jié)點(diǎn)，該節(jié)點(diǎn)都會(huì)把該消息向自己所有的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，隨著消息的不斷向前推進(jìn)，節(jié)點(diǎn)轉(zhuǎn)發(fā)所產(chǎn)生的消息數(shù)量以指數(shù)級(jí)速率迅速增長(zhǎng)，消息訪問(wèn)過(guò)的節(jié)點(diǎn)數(shù)量會(huì)越來(lái)越多，但每一跳時(shí)消息所到達(dá)的新節(jié)點(diǎn)的數(shù)量和產(chǎn)生的冗余消息數(shù)量是有所變化的.在初始階段，消息到達(dá)的新節(jié)點(diǎn)的數(shù)量還比較少，尤其是在前3跳中，網(wǎng)絡(luò)中的絕大部分節(jié)點(diǎn)都還沒(méi)有被訪問(wèn)過(guò)，消息到達(dá)的節(jié)點(diǎn)基本上都是第一次收到該消息，消息到達(dá)新節(jié)點(diǎn)的數(shù)量與產(chǎn)生的轉(zhuǎn)發(fā)消息的數(shù)量基本成正比，該階段中查詢消息快速覆蓋網(wǎng)絡(luò)且產(chǎn)生的冗余消息數(shù)量相對(duì)較少；而在后幾跳中，網(wǎng)絡(luò)中的不少節(jié)點(diǎn)都已經(jīng)被訪問(wèn)過(guò)，消息到達(dá)新節(jié)點(diǎn)的概率就比較小，消息訪問(wèn)新節(jié)點(diǎn)的數(shù)量與轉(zhuǎn)發(fā)消息的數(shù)量嚴(yán)重不匹配，轉(zhuǎn)發(fā)所產(chǎn)生的消息大部分都屬于冗余消息.

為了觀察標(biāo)準(zhǔn)洪泛中消息的覆蓋范圍與冗余消息數(shù)量的變化情況，根據(jù)文獻(xiàn)[8]指出的“冪規(guī)律”特性和文獻(xiàn)[9]指出的“小世界”特性，構(gòu)造網(wǎng)絡(luò)N1，網(wǎng)絡(luò)規(guī)模包括70 000個(gè)節(jié)點(diǎn)，平均連接度為25.3，查詢過(guò)程中設(shè)定TTL=7.實(shí)驗(yàn)結(jié)果如圖1與圖2所示，圖中分別給出了標(biāo)準(zhǔn)洪泛機(jī)制中每一跳時(shí)消息到達(dá)新節(jié)點(diǎn)的數(shù)量百分比和產(chǎn)生冗余消息的數(shù)量百分比.

圖1 不同跳數(shù)時(shí)消息覆蓋百分比Fig.1 Percentage of message coverage with different hop

圖2 不同跳數(shù)時(shí)冗余消息百分比Fig.2 Percentage of redundant message with different hop

在前4跳中，每跳時(shí)消息到達(dá)新節(jié)點(diǎn)的數(shù)量直線上升，其中第3、4跳時(shí)分別占總數(shù)的22.91%和69.55%，而冗余消息的數(shù)量增長(zhǎng)緩慢，尤其在前3跳中產(chǎn)生的冗余消息數(shù)量之和不足總量的1%.但從第5跳開始，消息到達(dá)新節(jié)點(diǎn)的數(shù)量迅速下降，在第5跳時(shí)僅占6.4%，第6、7跳時(shí)更低，而冗余消息的數(shù)量卻快速增長(zhǎng)，尤其是第5跳時(shí)，冗余消息的數(shù)量達(dá)72.24%，第6、7跳時(shí)冗余消息的數(shù)量又有所下降，這是因?yàn)榍耙惶鴷r(shí)產(chǎn)生的大量轉(zhuǎn)發(fā)消息中的大部分都將被視為冗余消息而丟棄，并沒(méi)有參與后續(xù)的轉(zhuǎn)發(fā)過(guò)程.

前4跳時(shí)，消息覆蓋的范圍持續(xù)擴(kuò)大，冗余消息的數(shù)量相對(duì)較少，這個(gè)階段中標(biāo)準(zhǔn)洪泛機(jī)制表現(xiàn)出很強(qiáng)的優(yōu)越性；后3跳時(shí)，消息覆蓋的范圍迅速縮小，冗余消息的數(shù)量卻明顯增多，洪泛機(jī)制的性能嚴(yán)重下降，查詢的覆蓋范圍和冗余消息的數(shù)量在整個(gè)消息生存期中表現(xiàn)出了明顯的階段性.因此,很有必要依據(jù)消息的跳數(shù)對(duì)搜索過(guò)程進(jìn)行分段處理，可以把前4跳作為搜索過(guò)程的第一階段，后3跳作為搜索過(guò)程的第二階段.第一階段時(shí)，仍采用原始洪泛搜索策略，節(jié)點(diǎn)在收到新的查詢消息后把消息向所有的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)，在保證消息高查詢覆蓋范圍的同時(shí)，快速接近目標(biāo)節(jié)點(diǎn)；第二階段時(shí)，節(jié)點(diǎn)僅隨機(jī)選擇部分鄰居作為消息轉(zhuǎn)發(fā)的對(duì)象，盡量減少冗余消息量，提高網(wǎng)絡(luò)的可擴(kuò)展性.現(xiàn)有的搜索技術(shù)，在整個(gè)查詢過(guò)程中，選擇消息轉(zhuǎn)發(fā)的目標(biāo)節(jié)點(diǎn)的策略往往并不隨著消息跳數(shù)的不同而變化，這在一定程度上造成了通信爆炸問(wèn)題，嚴(yán)重影響了查詢的效率.

改進(jìn)后的基于消息跳數(shù)的分段搜索策略hpsearch，能有效地把標(biāo)準(zhǔn)洪泛選擇和隨機(jī)部分選擇2個(gè)階段的優(yōu)勢(shì)結(jié)合起來(lái)，能夠在保持高覆蓋范圍的前提下盡量減少冗余消息的數(shù)量，有助于提高搜索效率，改善網(wǎng)絡(luò)的整體性能.

hpsearch的主要過(guò)程可以描述如下：

根據(jù)TTL把搜索過(guò)程分為2個(gè)階段，前h跳時(shí)，節(jié)點(diǎn)p通過(guò)將消息m發(fā)送給所有鄰居來(lái)完成本次消息的傳播；h跳以后，節(jié)點(diǎn)p通過(guò)將消息m發(fā)送給k個(gè)隨機(jī)選擇的鄰居來(lái)完成本次消息的傳播.

First divide the searching into two stages according to theTTL

When (node p receives a message m)

If(p has received m no more than one time and the hop is less than h)

p sends m to all neighbors that p has.

Else if(p has received m no more than one time and the hop is more than or equal to h)

p sends m to k neighbors which selected randomly that p has.

Else p drops the message.

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)以網(wǎng)絡(luò)N1為基礎(chǔ)，設(shè)定TTL=7，前4跳時(shí)按標(biāo)準(zhǔn)洪泛策略轉(zhuǎn)發(fā)查詢消息，后3跳時(shí)通過(guò)隨機(jī)選擇E(或EV比例)個(gè)鄰居來(lái)完成消息的轉(zhuǎn)發(fā)，從查詢覆蓋率和冗余消息率兩方面來(lái)考察算法hpsearch的有效性.

以E=1…7為例，圖3與圖4給出了在不同參數(shù)下消息覆蓋率和冗余消息率的變化情況.

由圖3和圖4可以看出，hpsearch的消息覆蓋率相當(dāng)于Flooding的96.8%以上，而冗余消息率最低卻相當(dāng)于Flooding的28.6%.文獻(xiàn)[10]指出了LightFlood若要達(dá)到同樣的覆蓋范圍，則需要額外增加2～3跳.不難看出，hpsearch要優(yōu)于Flooding和LightFlood，它可以在搜索范圍基本不變的情況下，減少70%以上的冗余消息.

圖3 不同參數(shù)下的消息覆蓋率Fig.3 Message coverage rate with different parameters

圖4 不同參數(shù)下的冗余消息率Fig.4 Redundant message rate with different parameters

在實(shí)驗(yàn)過(guò)程中，通過(guò)不斷改變后3跳中隨機(jī)選擇的轉(zhuǎn)發(fā)消息數(shù)量的多少來(lái)觀察hpsearch的性能，部分實(shí)驗(yàn)結(jié)果如表1所示.可以看到,hpsearch隨著選擇轉(zhuǎn)發(fā)的消息個(gè)數(shù)(或比例)的增加，消息的覆蓋范圍隨之增大，冗余消息的數(shù)量也會(huì)增加；當(dāng)選擇轉(zhuǎn)發(fā)消息的數(shù)量達(dá)到一定比例后，再增加消息的轉(zhuǎn)發(fā)數(shù)量，消息的覆蓋范圍就增長(zhǎng)緩慢，而冗余消息的數(shù)量卻增長(zhǎng)較快.

表1 不同參數(shù)情況下的消息覆蓋率和冗余消息百分比Tab.1 Rate of message coverage and redundancy with different parameters

4 結(jié)束語(yǔ)

洪泛是非結(jié)構(gòu)化P2P系統(tǒng)中的重要搜索機(jī)制，它在查詢過(guò)程中產(chǎn)生了大量冗余消息，嚴(yán)重浪費(fèi)了網(wǎng)絡(luò)資源，降低了網(wǎng)絡(luò)的可擴(kuò)展性.基于消息跳數(shù)的分段搜索策略hpsearch能夠在保持高覆蓋范圍的同時(shí)，盡量降低冗余消息的數(shù)量，從而有效提高了查詢的效率.對(duì)于不同稠密程度的P2P網(wǎng)絡(luò)，如何更加合理地分段、定量隨機(jī)選擇轉(zhuǎn)發(fā)消息的數(shù)量以及改進(jìn)不同階段的搜索策略是下一個(gè)階段的研究重點(diǎn).

參考文獻(xiàn)：

[1] Ripeanu M, Foster I, Iamnitchi A. Mapping the gnutella network: properties of large-scale peer-to-peer systems and implications for system design [J]. IEEE Internet Computing, 2002(1/2): 50-57.

[2] Chawathe Y, Ratnasamy S, Breslau L, et al. Making Gnutella-like P2P Systems Scalable [C]. Proceedings of ACM SIGCOMM, 2003.

[3] Marius P, Aruna S. Cost-effective broadcast for fully decentralized peer-to-peer networks[J]. Computer Communications,2003,26(11):1159-1167.

[4] Yang B, Garcia H M. Improving search in peer-to-peer systems[A]. Proceedings of the 22nd International Conference on Distributed Computing Systems[C]. Washington:IEEE Computer Society,2002:5-14.

[5] Scipanidkulchai K,Maggs B, Zhang H. Efficient content location using interest-based locality in peer-to-peer systems[A]. Proceedings of IEEE INFOCOM 2003[C]. San Francisco: IEEE Computer Society,2003:2166-2176.

[6] Kalogeraki V, Gunopulos D, Zeinalipouryazti D. A local search mechanism for peer-to-peer networks[A].Proceedings of the 11th ACM Conf on Information and Knowledge Management[C]. New York:ACM,2002.

[7] Yang B，Garcia Molina H. Improving search in peer-to-peer networks[C]. Proceedings of the 22nd IEEE Int Conf on Distributed Computing(IEEE ICDCS’02),Picataway,2002.

[8] Watts D J, Strogatz S H. Collective dynamics of small world networks[J]. Nature, 1998,393(6):440-442.

[9] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999,286(10):509-512.

[10] Jiang Song, Guo Lei, Zhang Xiaodong. LightFlood:an efficient flooding scheme for file search in unstructured peer-to-peer system[C]. Proceedings of the 2003 International on Parallel Processing, 2003.