P2P模式下的資源定位技術(shù)探究

李瑞興

（福州教育學(xué)院 計算機系，福建 福州 350108）

P2P模式下的資源定位技術(shù)探究

李瑞興

（福州教育學(xué)院 計算機系，福建 福州 350108）

在P2P模式的網(wǎng)絡(luò)環(huán)境中，如何迅速的對節(jié)點資源進行定位和建立連接，是網(wǎng)絡(luò)技術(shù)研究的重點之一.針對P2P混合型模式的資源定位和搜索算法中存在冗余消息等問題，通過算法分析，提出兩種改進思路和方法：一是減少查詢的冗余消息；二是查詢到的信息直接發(fā)送給起始的查詢節(jié)點.通過仿真實驗，表明改進后的算法，減少了查詢消息冗余和提高了搜索速度.

P2P；搜索算法；RVP；Peer定位

隨著社會信息化的深入，網(wǎng)絡(luò)規(guī)模的迅速擴大，在網(wǎng)的主機數(shù)目越來越多，這就使得網(wǎng)內(nèi)的總資源更加豐富.C／S架構(gòu)是一種重要的互聯(lián)網(wǎng)模式，在該模式下提供信息的角色主要由網(wǎng)內(nèi)的諸多Web服務(wù)器擔(dān)任，這樣的模式有一個弊端就是整個Internet網(wǎng)絡(luò)都主要靠僅有的服務(wù)器節(jié)點來提供服務(wù)，造成了許多個人主機中的重要資源不能共享，利用率不高.網(wǎng)絡(luò)中的各個主機節(jié)點在P2P模式中，扮演著服務(wù)器和被服務(wù)者的雙重角色，所有的節(jié)點權(quán)利和其所處地位都是一樣的，這樣使得每個節(jié)點上的信息資源利用率大大提高［1］.

P2P這種網(wǎng)絡(luò)模型中的各個節(jié)點是對等的關(guān)系［2］，具有一樣的處理數(shù)據(jù)和提供服務(wù)能力的網(wǎng)絡(luò)節(jié)點會相互協(xié)同，一起承擔(dān)網(wǎng)絡(luò)中的任務(wù).在該模式下完成任務(wù)是由分布的主機提供資源和技術(shù)，主要任務(wù)涉及：數(shù)據(jù)信息的共享、分布處理和計算、平臺信息服務(wù)、節(jié)點間相互協(xié)作和通信等［3］.如何迅速的對節(jié)點資源進行定位，同時能夠確定快捷合理的路徑以建立連接是實現(xiàn)P2P網(wǎng)絡(luò)技術(shù)的關(guān)鍵所在.由于在分布式的網(wǎng)絡(luò)中節(jié)點間關(guān)系無論在邏輯上還是能力上都是對等的，所以就削減甚至取消了服務(wù)器的作用.

1 P2P網(wǎng)絡(luò)的基本結(jié)構(gòu)

當(dāng)前主要有三種P2P網(wǎng)絡(luò)結(jié)構(gòu)：分布式的P2P結(jié)構(gòu)、集中式的P2P結(jié)構(gòu)和混合式的P2P結(jié)構(gòu)［4］.

1.1 分布式

該模式下的網(wǎng)絡(luò)中僅僅存在對等的網(wǎng)絡(luò)節(jié)點，中央服務(wù)器不再被采用，所有網(wǎng)路節(jié)點接入網(wǎng)絡(luò)的方式是自行接入，然后再與相鄰的網(wǎng)絡(luò)節(jié)點進行連接.在這種分布式的P2P模式下，節(jié)點間進行資源共享和信息查詢是采用廣播的方式，這就造成了較大的網(wǎng)絡(luò)數(shù)據(jù)流量，導(dǎo)致進行節(jié)點信息定位和資源搜索的速度很慢，響應(yīng)時間也大大加長.

1.2 集中式

集中式的結(jié)構(gòu)采用的算法是快速搜索，該算法的主要特性是性能高、彈性高、排隊響應(yīng)所用的時間較短；該模式靈活性差，過于依靠中央控制點.如果它出現(xiàn)了故障，服務(wù)便會被迫中斷.在這種模式中，為網(wǎng)絡(luò)中對等節(jié)點提供主要目錄服務(wù)的是與節(jié)點互相連接的中央目錄服務(wù)器.該模式的工作流程為，首先在目錄服務(wù)器上對等節(jié)點進行自身信息的注冊，要想對其他的節(jié)點進行定位或者進行相關(guān)信息的查詢，可以訪問目錄服務(wù)器獲得消息.

1.3 混合式

這種結(jié)構(gòu)是以上兩種結(jié)構(gòu)的綜合，兼具了查找快速和中心弱化的特點.在進行資源定位搜索的時候是分層次進行查找的，這樣使得資源的分布情況和它的存儲位置能夠迅速地被鎖定，任務(wù)進行排隊時間縮短，搜索性能得到了很大的改進.響應(yīng)時間也大大減小，網(wǎng)絡(luò)自身的性能和彈性得到提高，主要是歸功于超級節(jié)點的存在.

該模式下中央服務(wù)器被分布在網(wǎng)絡(luò)中的超級節(jié)點代替，根據(jù)連接帶寬大小、計算處理能力強弱、網(wǎng)絡(luò)等待時間長短的差異等［5］，將節(jié)點劃分為不同的類型.普通節(jié)點是其中一種類型，它和另一種超級節(jié)點共同組成一個自治的簇，簇中的節(jié)點分布結(jié)構(gòu)是普通網(wǎng)絡(luò)節(jié)點以超級節(jié)點為中心進行圍繞.超級節(jié)點間相連接的方式是分布式P2P網(wǎng)絡(luò)結(jié)構(gòu)，簇內(nèi)采用集中式進行連接.

2 P2P資源定位技術(shù)

P2P技術(shù)應(yīng)用領(lǐng)域廣泛，包括了信息搜索，文件交換，信息資源共享，分布式數(shù)據(jù)處理和計算，實時通信，協(xié)同工作，網(wǎng)絡(luò)游戲開發(fā)等［6］.要想實現(xiàn)以上功能，就要處理好資源定位問題，找到合理的搜索定位算法.

信息資源快速定位的常用方法主要是“地址查詢”.網(wǎng)絡(luò)中每個資源的定位主要依賴于標識符，其次還要考慮到包含該資源位置的地址指針，二者共同起到了尋位作用.資源信息標識符如表1所示：

表1 標識符說明

系統(tǒng)會將＜OID，P＞定位信息保存，當(dāng)網(wǎng)絡(luò)用戶要對資源進行訪問的時候，根據(jù)保存的位置信息，以O(shè)ID為依據(jù)來對P進行查詢，進而達到了資源的定位.

2.1 集中目錄定位方式

在該定位方式中，資源位置的索引信息集中進行記錄，這些信息會由一個與服務(wù)器很相似的節(jié)點提供.

1）個人主機中資源要與網(wǎng)絡(luò)中其他節(jié)點共享時，要先對自己的資源進行注冊，由索引服務(wù)器記錄好注冊信息，資源位置信息＜OID，P＞.許多的定位信息保存在索引服務(wù)器中，包括了資源的地址指針列表和位置標識符.

2）網(wǎng)絡(luò)用戶要對自己所需的資源進行查找時，首先進行索引服務(wù)器的查詢，查詢依據(jù)是資源標識符，然后服務(wù)器會將該資源的地址指針返回，用戶通過返回的信息對資源定位.

3）資源的所在位置定位后，開始在節(jié)點間進行網(wǎng)絡(luò)資源的查詢和下載等，此時索引服務(wù)器是不參與該通信過程的.如圖1所示，其中雙向箭頭表示資源的下載，單項箭頭表示資源的定位查找.

該種定位方式自身有優(yōu)點，但也存在弊端.較為明顯的缺點是：該方式與C／S模式很相似［7］，過于依賴僅有的一些索引服務(wù)器，單點故障造成的影響很大，可擴展性較差.該方式的主要優(yōu)點是：實現(xiàn)容易，方法簡單.

2.2 泛洪請求的資源定位方式

該模式中是不存在中央服務(wù)器的，用戶發(fā)出的信息和請求主要是借助相互連接的網(wǎng)絡(luò)節(jié)點進行傳遞，節(jié)點收到請求后有兩種處理方式，如果該節(jié)點滿足查詢條件和要求，就會響應(yīng)請求，如果不能夠滿足發(fā)來的請求時，就會將該請求廣播出去，主要是將信息發(fā)送給與自己互相連接的網(wǎng)絡(luò)節(jié)點，這樣的處理方式一直進行，直到發(fā)出的請求得到了某個節(jié)點的響應(yīng)為止.當(dāng)然廣播也會使帶寬遭到浪費，所以限制廣播的跳數(shù)在7～8內(nèi)，請求超過了廣播循環(huán)的有限次數(shù)之后，節(jié)點未對其響應(yīng)，將會為起始請求節(jié)點提供信息［8］.圖2為該種方式的結(jié)構(gòu)展示：

圖1 集中式結(jié)構(gòu)圖

圖2 泛洪請求模式結(jié)構(gòu)

泛洪的主要代表就是Gnutella協(xié)議，該協(xié)議為了控制傳遞的請求消息數(shù)量的快速增長制定了很多控制機制：

1）路徑標識符

為能夠指引返回的通訊消息按照原來的路線返回并防止消息在網(wǎng)絡(luò)節(jié)點間循環(huán)，設(shè)定了路徑標識符.

2）UID消息標識符

消息有時會出現(xiàn)重復(fù)的傳播，指多次到達同一個節(jié)點.為了避免該情況，設(shè)計了消息的唯一標識.

3）消息生存周期

TTL即為消息的生存周期，消息形成的起初為TTL賦予初值.TTL主要目的是為了控制消息的生命周期，從而實現(xiàn)了消息在網(wǎng)絡(luò)中傳播的實際時間，消息中也包含了UID，標識符在各個消息中是不同的.

以上控制機制的主要目的是為了確保消息在網(wǎng)絡(luò)進行傳播的時候不會失去控制，從而保證Gnutella網(wǎng)絡(luò)能夠運行正常［9］.

泛洪請求式的主要缺點是擴展性較差，但是也有很多的優(yōu)點：可靠性高，在小范圍內(nèi)執(zhí)行的效率比較高.如果較多的超級節(jié)點在系統(tǒng)中存在的話，帶寬的浪費情況可以大大改善.

3 資源定位搜索算法與改進

P2P有多種模式，分布型、集中型和混合型等，下面將分析混合型模式的網(wǎng)絡(luò)信息資源定位和搜索算法，找出存在的弊端，提出改進策略.要求改進的算法兼?zhèn)湓惴ǖ膬?yōu)點，而且自身的適應(yīng)性良好，可擴展性好，搜索效率高，冗余信息少.改進的算法中超級節(jié)點在處理查詢消息的時候，是進行單次處理，忽略掉其他冗余消息，查詢結(jié)果和反饋信息最終都會傳遞給起始的信息查詢節(jié)點.

3.1 搜索定位算法

實現(xiàn)搜索定位算法有兩種策略，分別是節(jié)點部分連接的方式和節(jié)點全連接的方式.

3.1.1 節(jié)點間采用不完全連接的方式

超級節(jié)點簡稱為RVP，當(dāng)RVP要進行消息的查詢和轉(zhuǎn)發(fā)時，只有與起始RVP相鄰的節(jié)點才會收到消息，然后在本地進行查詢，起始RVP接收查詢結(jié)果，而且結(jié)果沿著原路發(fā)送給它.

如圖3所示，中間的超級節(jié)點RVP A進行查詢轉(zhuǎn)發(fā)的時候僅僅向它的兩個相鄰RVP發(fā)送了請求信息，回饋信息被原路反向傳送給起始查詢節(jié)點.不完全連接的最大弊端就是信息搜索和查詢的速度較慢，與全連接方式相比較它的搜索范圍也相對較小.該方式削減了信息查詢次數(shù)，總體性好，網(wǎng)絡(luò)連接數(shù)也大大減少.

3.1.2 全連接方式

RVP在該種方式下查詢信息或者轉(zhuǎn)發(fā)信息時，會請求相鄰的RVP，然后它們做出響應(yīng).如圖4所示，以RVP A為中心，它是信息請求的起始節(jié)點，與其相鄰的RVP將轉(zhuǎn)發(fā)它的查詢請求信息.接收最終結(jié)果的對象是起始節(jié)點RVP A，接收請求的RVP一旦搜索到滿足條件的結(jié)果會將其發(fā)送給最初發(fā)出請求的節(jié)點.

3.2 算法改進策略

某個網(wǎng)絡(luò)節(jié)點在同一個路徑進行重復(fù)的轉(zhuǎn)發(fā)或?qū)ν粋€查詢請求進行反復(fù)的處理，那么這些被反復(fù)處理的消息就是冗余消息.這造成了較長的響應(yīng)時間，導(dǎo)致信息搜索和定位速度減慢，較大的網(wǎng)絡(luò)流量，起始查詢節(jié)點承擔(dān)的任務(wù)加重等問題.解決方法如下：

1）查詢消息到達了超級節(jié)點之后，如果是消息首次到達，則節(jié)點進行本地信息的搜索查詢或者消息的轉(zhuǎn)發(fā)，如果消息并非第一次到達該節(jié)點，則超級節(jié)點不會對查詢請求作出反應(yīng)，冗余的查詢消息就被很好地避免了.

2）查詢到的信息結(jié)果將不再沿原來的路線返回到起始查詢節(jié)點，而是直接發(fā)送給起始的查詢節(jié)點，使得查詢反饋的速度得到很大的提高.

3.3 算法改進描述

改進后的算法進行查詢時的信息處理過程方式如圖5所示，描述如下：

圖3 不完全連接方式消息傳遞方式

圖4 全連接方式消息傳遞方式

圖5 改進后的查詢請求與轉(zhuǎn)發(fā)方式

1）為了記錄首先到達節(jié)點的查詢消息，每個消息設(shè)置一個唯一的標識符ID，并設(shè)置了一個查詢消息的目錄表，網(wǎng)絡(luò)中的超級節(jié)點配有自己的消息記錄表.消息表如表2所示：

表2 消息表概況

2）當(dāng)某個節(jié)點接收到查詢消息后，以消息信息表為依據(jù)首先對到達的查詢信息進行判斷，看該RVP是否是首次到達，只有首次到達的信息才會在本地進行轉(zhuǎn)發(fā)和查詢.

3）在本地得到查詢結(jié)果之后，不是將結(jié)果發(fā)給進行查詢的超級節(jié)點，而是直接將結(jié)果反饋給起始進行查詢的對等點.

4）在圖5中，邊緣節(jié)點peer發(fā)出了查詢請求消息，本地RVP B接收到了該請求，進行本地查詢并作出相應(yīng)的處理.但是也可能超級節(jié)點B查詢失敗或無結(jié)果，它就會將收到的查詢請求進行轉(zhuǎn)發(fā)，只能轉(zhuǎn)給與它相鄰的對象，最后接收查詢結(jié)果的是邊緣Peer，若某一節(jié)點根據(jù)要求的條件進行查詢得到了結(jié)果，就會將查詢結(jié)果發(fā)送給邊緣Peer.

5）邊緣Peer得到反饋回來的查詢結(jié)果后，會將相關(guān)信息發(fā)送給所有的本地RVP.這樣，一樣的查詢請求就不會重復(fù)出現(xiàn)，查詢速度也有很大的提升.

4 實驗仿真分析

采用NS－2網(wǎng)絡(luò)仿真器對改進算法進行驗證，對比改進前后綜合性能的變化情況.主要的實驗數(shù)據(jù)分析對象是查詢延時和消息冗余量，這是混合P2P網(wǎng)絡(luò)模式的兩個網(wǎng)絡(luò)性能指標，對改進后的結(jié)果返回和查詢請求轉(zhuǎn)發(fā)算法進行綜合對比和分析.NS2是一種可以進行網(wǎng)絡(luò)模擬的軟件，利用gt－itm和packet－level在NS2上建立拓撲結(jié)構(gòu)［10］.

實驗過程：

1）對NS2進行安裝，從而進行模擬，利用GT－ITM對拓撲結(jié)構(gòu)進行建立.

2）數(shù)據(jù)參數(shù)的修改配置：為了轉(zhuǎn)換gt－itm的輸出形式，從而變成的NS2形式，對修改文件sgb2ns進行編譯之后，將其轉(zhuǎn)移到gt－itm／bin這個名稱的子目錄下，從而實現(xiàn)sgb2ns在目錄gt－itm下的正常運行.實驗?zāi)M設(shè)備和數(shù)據(jù)參數(shù)如表3所示：

表3 實驗?zāi)M設(shè)備及數(shù)據(jù)參數(shù)配置

在數(shù)據(jù)源的各個端節(jié)點上，為了能夠產(chǎn)生固定速率的數(shù)據(jù)流，對網(wǎng)絡(luò)帶寬進行了相關(guān)設(shè)置，保證了數(shù)據(jù)包能夠有序并高效率地進行傳輸.

實驗?zāi)M結(jié)果如圖6和圖7所示，分別是消息冗余和結(jié)果延遲算法改進前后的關(guān)系圖對比.

圖6 跳數(shù)和冗余量的關(guān)系圖

圖7 返回的查詢結(jié)果延遲與跳數(shù)的關(guān)系圖

表4記錄了在延遲時間和消息冗余方面，算法改進前后兩種方式的在網(wǎng)絡(luò)中的最后一跳時的數(shù)據(jù)信息.

表4 算法改進前后的數(shù)據(jù)對比

實驗結(jié)果表明，改進后的查詢定位方式不但兼?zhèn)淞嗽瓉鞵2P混合模式的許多優(yōu)點，還包括了RVP對來自同一個網(wǎng)絡(luò)節(jié)點的數(shù)據(jù)查詢請求，只在首次進行處理，減少了一半左右的冗余查詢消息.

6 結(jié)論

P2P網(wǎng)絡(luò)模式應(yīng)用有良好的前景，其資源定位與搜索技術(shù)對網(wǎng)絡(luò)的性能有重要的影響.為了迅速的對節(jié)點資源進行定位和建立連接，改進搜索定位算法策略，通過有效減少查詢的冗余消息和查詢到的信息直接發(fā)送給起始的查詢節(jié)點（而不是原路返回），可以提高查詢信息反饋的速度.研究結(jié)果表明，對于混合P2P模式中存在的消息冗余等問題，有較好的改進效果.

［1］ 張春紅.P2P技術(shù)全面解析［M］.北京：人民郵電出版社，2010：10-35

［2］ Karl A，Magdalena P.Improving data access in P2P systems［J］.IEEE Internet Computing，2002，6（1）：58-67

［3］ 邢小良.P2P技術(shù)及其應(yīng)用［M］.北京：人民郵電出版社，2008：43-69

［4］ 蔡 康.P2P對等網(wǎng)絡(luò)原理與應(yīng)用［M］.北京：科學(xué)出版社，2011：2-24

［5］ 趙治國，丁琳，譚敏生.基于詢問—應(yīng)答策略的Gnutella資源搜索算法的改進［J］.計算機工程與設(shè)計，2008（7）：1 694-1 697

［6］ 周功業(yè)，黎書生.新一代網(wǎng)絡(luò)計算模型——P2P及其JXTA體系結(jié)構(gòu)的設(shè)計與實現(xiàn)［J］.計算機應(yīng)用研究，2002（9）：139-142

［7］ Beverly Yang，Hector Garcia-Molina.Improving searchinPeer-to-Peer networks［R］.Technical report，Stanford University.March 2002：152-166

［8］ 管 磊.P2P技術(shù)揭秘—P2P網(wǎng)絡(luò)技術(shù)原理與典型系統(tǒng)開發(fā)［M］.北京：清華大學(xué)出版社，2011：35-67

［9］ 王 菁.P2P系統(tǒng)中資源管理機制的研究［D］.北京：中國科學(xué)技術(shù)大學(xué)，2007：15-41

［10］ 殷 煒，蔣卓明，陳 剛，許榕生.基于一簇多超級結(jié)點的混合P2P網(wǎng)絡(luò)模型［J］.計算工程，2009（2）：112-115

The Research to Resource Positioning Technology of P2P Mode

Li Ruixing
（Department of Computer，F(xiàn)uzhou Institute of Education，F(xiàn)uzhou 350108，China）

In the P2P mode network environment，one of the key points to the study of network technology is how to positioning and connecting the node resources.For the problems of P2P hybrid model＇s resources location and the redundant messages in the search algorithm，this paper provides two kinds of improved ideas and methods.One is reduce the query redundancy messages，and the other is sent the inquired messages directly to the start of the query node.The simulated experiment proved that the improved algorithm reduced the query message redundancy，and improved the search speed.

P2P；search algorithm；RVP；Peer positioning

張麗萍】

1672-2027（2012）03-0077-05

TP393

A

2012-06-28

李瑞興（1962-），男，福建福州人，福州教育學(xué)院高級講師，從事計算機網(wǎng)絡(luò)技術(shù)研究.