李瑞興

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

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

李瑞興

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

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

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

隨著社會信息化的深入，網(wǎng)絡(luò)規(guī)模的迅速擴(kuò)大，在網(wǎng)的主機(jī)數(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é)點(diǎn)來提供服務(wù)，造成了許多個人主機(jī)中的重要資源不能共享，利用率不高.網(wǎng)絡(luò)中的各個主機(jī)節(jié)點(diǎn)在P2P模式中，扮演著服務(wù)器和被服務(wù)者的雙重角色，所有的節(jié)點(diǎn)權(quán)利和其所處地位都是一樣的，這樣使得每個節(jié)點(diǎn)上的信息資源利用率大大提高［1］.

P2P這種網(wǎng)絡(luò)模型中的各個節(jié)點(diǎn)是對等的關(guān)系［2］，具有一樣的處理數(shù)據(jù)和提供服務(wù)能力的網(wǎng)絡(luò)節(jié)點(diǎn)會相互協(xié)同，一起承擔(dān)網(wǎng)絡(luò)中的任務(wù).在該模式下完成任務(wù)是由分布的主機(jī)提供資源和技術(shù)，主要任務(wù)涉及：數(shù)據(jù)信息的共享、分布處理和計(jì)算、平臺信息服務(wù)、節(jié)點(diǎn)間相互協(xié)作和通信等［3］.如何迅速的對節(jié)點(diǎn)資源進(jìn)行定位，同時能夠確定快捷合理的路徑以建立連接是實(shí)現(xiàn)P2P網(wǎng)絡(luò)技術(shù)的關(guān)鍵所在.由于在分布式的網(wǎng)絡(luò)中節(jié)點(diǎn)間關(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é)點(diǎn)，中央服務(wù)器不再被采用，所有網(wǎng)路節(jié)點(diǎn)接入網(wǎng)絡(luò)的方式是自行接入，然后再與相鄰的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行連接.在這種分布式的P2P模式下，節(jié)點(diǎn)間進(jìn)行資源共享和信息查詢是采用廣播的方式，這就造成了較大的網(wǎng)絡(luò)數(shù)據(jù)流量，導(dǎo)致進(jìn)行節(jié)點(diǎn)信息定位和資源搜索的速度很慢，響應(yīng)時間也大大加長.

1.2 集中式

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

1.3 混合式

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

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

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

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

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

表1 標(biāo)識符說明

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

2.1 集中目錄定位方式

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

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

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

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

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

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

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

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

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

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

1）路徑標(biāo)識符

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

2）UID消息標(biāo)識符

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

3）消息生存周期

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

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

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

3 資源定位搜索算法與改進(jìn)

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

3.1 搜索定位算法

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

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

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

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

3.1.2 全連接方式

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

3.2 算法改進(jìn)策略

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

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

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

3.3 算法改進(jìn)描述

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

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

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

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

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

表2 消息表概況

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

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

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

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

4 實(shí)驗(yàn)仿真分析

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

實(shí)驗(yàn)過程：

1）對NS2進(jìn)行安裝，從而進(jìn)行模擬，利用GT－ITM對拓?fù)浣Y(jié)構(gòu)進(jìn)行建立.

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

［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ìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008（7）：1 694-1 697

［6］ 周功業(yè)，黎書生.新一代網(wǎng)絡(luò)計(jì)算模型——P2P及其JXTA體系結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)［J］.計(jì)算機(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)中資源管理機(jī)制的研究［D］.北京：中國科學(xué)技術(shù)大學(xué)，2007：15-41

［10］ 殷 煒，蔣卓明，陳 剛，許榕生.基于一簇多超級結(jié)點(diǎn)的混合P2P網(wǎng)絡(luò)模型［J］.計(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é)院高級講師，從事計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)研究.