P2P技術(shù)資源發(fā)現(xiàn)與定位論文

導(dǎo)語(yǔ)：P2P技術(shù)資源發(fā)現(xiàn)與定位論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀(guān)點(diǎn)，若需要原創(chuàng)文章可咨詢(xún)客服老師，歡迎參考。

摘要p2p主要指計(jì)算機(jī)之間以對(duì)等方式形成的網(wǎng)絡(luò)連接，弱化或完全取消了服務(wù)器的作用。文章從分析P2P的基本概念、需求和發(fā)展入手,討論了P2P與網(wǎng)格和C/S的聯(lián)系和區(qū)別，并列舉了現(xiàn)今P2P的主要應(yīng)用，最后，對(duì)目前P2P中存在的資源發(fā)現(xiàn)與定位問(wèn)題做了分析和論述。

關(guān)鍵字P2P、資源管理、Gnutella、哈希查找

1P2P技術(shù)簡(jiǎn)介

1.1概念及特征

P2P是peertopeer的縮寫(xiě)，是指：通過(guò)使用分布資源，借助于分布計(jì)算技術(shù)來(lái)完成關(guān)鍵任務(wù)的系統(tǒng)和應(yīng)用的總稱(chēng)。這里的分布式資源包括計(jì)算能力、數(shù)據(jù)（包括存儲(chǔ)介質(zhì)和內(nèi)容）、網(wǎng)絡(luò)帶寬和其它資源（如計(jì)算機(jī)、人力資源等）；分布計(jì)算包括算法、數(shù)據(jù)、元數(shù)據(jù)等，或者是三者總體；關(guān)鍵任務(wù)包括分布計(jì)算、數(shù)據(jù)（或內(nèi)容）共享、通信與協(xié)作，或者是平臺(tái)服務(wù)等。

P2P技術(shù)的主要特征是弱化服務(wù)器作用，甚至取消服務(wù)器，使分布式系統(tǒng)中的各個(gè)節(jié)點(diǎn)邏輯對(duì)等，這種技術(shù)出現(xiàn)的目的就是希望能夠充分利用網(wǎng)絡(luò)中所蘊(yùn)含的潛在資源。與C/S模型不同，P2P模型中每個(gè)節(jié)點(diǎn)既可以是服務(wù)（或者資源）的提供者，也可以是使用者，充其量就是提供的服務(wù)（或資源）的類(lèi)型不同。

1.2需求與背景

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，接入網(wǎng)絡(luò)的主機(jī)增加，可用資源豐富，然而目前的互聯(lián)網(wǎng)仍然是以C/S模式為主，尤其是Web技術(shù)的發(fā)展使得許多Web服務(wù)器成為信息的主要提供源，整個(gè)Internet系統(tǒng)依附于這些少量的服務(wù)器節(jié)點(diǎn)，而大量的個(gè)人主機(jī)中的資源卻成了網(wǎng)絡(luò)中的信息孤島，無(wú)法得到充分利用，能否發(fā)揮這些閑散資源的使用效率（或者作用）構(gòu)成了人們關(guān)注P2P的理由。

1.3P2P與網(wǎng)格的聯(lián)系與區(qū)別

網(wǎng)格與P2P在技術(shù)上沒(méi)有本質(zhì)區(qū)別，都是在廣域網(wǎng)條件下實(shí)現(xiàn)資源共享和分布計(jì)算。正因如此，全球網(wǎng)格論壇（GGF）與對(duì)等網(wǎng)絡(luò)研究小組（P2PWG）已宣布合并。但二者也有一定的區(qū)別。網(wǎng)格類(lèi)似于電力系統(tǒng)，格點(diǎn)（或者節(jié)點(diǎn)）類(lèi)似發(fā)電站，通過(guò)整個(gè)網(wǎng)絡(luò)輸送給用戶(hù)，相對(duì)于P2P，更象是將一些大型資源組織起來(lái)，供社會(huì)共享，我國(guó)目前正在實(shí)施的生物研究網(wǎng)格和網(wǎng)絡(luò)教育服務(wù)網(wǎng)格都可作為其輔證；P2P則泛指閑散資源的組織。

（1）應(yīng)用面

網(wǎng)格較側(cè)重于重大科學(xué)計(jì)算和大型專(zhuān)業(yè)性的協(xié)同，其一個(gè)或多個(gè)主要節(jié)點(diǎn)仍有較重的服務(wù)器色彩；P2P提供普通的信息、計(jì)算服務(wù)，每個(gè)參與者明顯地兼有客戶(hù)、服務(wù)器雙重身份。

（2）訪(fǎng)問(wèn)對(duì)象

網(wǎng)格訪(fǎng)問(wèn)計(jì)算資源、數(shù)據(jù)資源、軟件資源，相對(duì)來(lái)說(shuō)，有較固定的目標(biāo)；P2P完全是隨機(jī)訪(fǎng)問(wèn)，隨機(jī)使用。

（3）安全性

網(wǎng)格中每個(gè)節(jié)點(diǎn)都有身份鑒定、授權(quán)、防火墻保護(hù)的能力；P2P每個(gè)參與者不保證這些能力，甚至是匿名的。

（4）控制

網(wǎng)格在資源監(jiān)視/分配和作業(yè)調(diào)度上仍有較多的集中控制；P2P僅有很少的或沒(méi)有集中控制，主要靠自行組織。

（5）服務(wù)質(zhì)量

網(wǎng)格確保可靠的服務(wù)質(zhì)量；P2P只有部分的保證，某些參與者甚至是不可信的。以上這些區(qū)別是相對(duì)而言，隨著不斷發(fā)展和改進(jìn)，這些區(qū)別會(huì)逐步縮小。

1.4P2P與C/S的聯(lián)系

從某種程度上說(shuō)，也許不應(yīng)該將P2P和C/S模式完全的對(duì)立起來(lái)，就某項(xiàng)特定的應(yīng)用，以及特定的時(shí)間，P2P網(wǎng)絡(luò)也許是以C/S方式進(jìn)行工作的。例如：如果每個(gè)用戶(hù)都有一些軟件資源（例如文字處理程序）或者硬件設(shè)施（例如：打印機(jī)），自然，可以采用P2P的方式進(jìn)行可控共享，此時(shí)，提供打印機(jī)的客戶(hù)（本地的某個(gè)進(jìn)程）就臨時(shí)充當(dāng)了服務(wù)器的角色。再分析一下目前的Web工作方式，我們更多的應(yīng)用是文件（或者資料）的查找，Web頁(yè)面成為文件資源的目錄，存儲(chǔ)對(duì)應(yīng)文件的主機(jī)成為提供者，原理上，該主機(jī)可以獨(dú)立于Web服務(wù)器，這也可認(rèn)為是P2P的一種形式。

2P2P資源發(fā)現(xiàn)與定位

目前P2P技術(shù)已在文件交換，分布式計(jì)算，搜索，信息共享，協(xié)同工作，即時(shí)通信，網(wǎng)絡(luò)游戲等等方面得到了廣泛的應(yīng)用，還有一些公司在開(kāi)發(fā)基于P2P的平臺(tái)。但是，無(wú)論是通信、P2P協(xié)作、分布式搜索引擎還是共享計(jì)算和交互式游戲等功能的實(shí)現(xiàn)，都只能以很好解決網(wǎng)內(nèi)資源的迅速準(zhǔn)確定位問(wèn)題為前提。所以，P2P網(wǎng)絡(luò)中資源發(fā)現(xiàn)是及其重要的。

目前，資源的定位一般采用的是“地址查詢(xún)”的方法，即：每個(gè)資源有一個(gè)全局唯一標(biāo)識(shí)符OID和一個(gè)包含其所在地址的指針P，系統(tǒng)將<OID,P>保存起來(lái)，當(dāng)用戶(hù)需要訪(fǎng)問(wèn)該資源時(shí)，根據(jù)OID來(lái)查詢(xún)P，從而進(jìn)行定位。定位機(jī)制有不同的實(shí)現(xiàn)方法。按照實(shí)現(xiàn)系統(tǒng)的體系結(jié)構(gòu)，主要可以分為兩類(lèi)：集中目錄式、泛洪請(qǐng)求式

2.1集中目錄式

在集中目錄式（CentralIndexServer）中，有一個(gè)類(lèi)似于服務(wù)器的節(jié)點(diǎn)集中提供資源索引信息。當(dāng)用戶(hù)共享資源時(shí)，需將資源的<OID,P>向索引服務(wù)器進(jìn)行資源注冊(cè)，索引服務(wù)器中保存著系統(tǒng)中所有資源的標(biāo)識(shí)符和指針列表。當(dāng)用戶(hù)需要查找資源時(shí)，首先通過(guò)資源標(biāo)識(shí)符查詢(xún)索引服務(wù)器，服務(wù)器返回該資源的指針，用戶(hù)通過(guò)該指針定位。當(dāng)定位到資源的存儲(chǔ)位置后，資源的下載在節(jié)點(diǎn)之間直接進(jìn)行，與索引服務(wù)器沒(méi)有關(guān)系。

集中式的優(yōu)點(diǎn)是：簡(jiǎn)單、容易實(shí)現(xiàn)。大多數(shù)的分布式系統(tǒng)采用的都是這種方法，例如：三種分布式對(duì)象計(jì)算環(huán)境（CORBA,DCOM,JAVARMI）提供的分布對(duì)象名字服務(wù)、大量的通用目錄服務(wù)（如X.500、LDAP和NIS）和一些實(shí)用分布式系統(tǒng)（如Napster）的資源定位方法等。

集中式的缺點(diǎn)很明顯：類(lèi)似于C/S模式，缺乏可擴(kuò)展性和存在單點(diǎn)故障問(wèn)題。

2.2泛洪請(qǐng)求式

與集中目錄式不同，泛洪請(qǐng)求式（FloodingRequest）沒(méi)有中央目錄服務(wù)器，用戶(hù)的請(qǐng)求通過(guò)所有連接的節(jié)點(diǎn)傳遞，這些節(jié)點(diǎn)或者響應(yīng)該請(qǐng)求，或者在不能滿(mǎn)足請(qǐng)求時(shí)，將該請(qǐng)求向與自己相連的其他節(jié)點(diǎn)廣播，直到請(qǐng)求得到響應(yīng)為止（泛洪）。為了減少?gòu)V播帶來(lái)的網(wǎng)絡(luò)帶寬浪費(fèi)，一般將廣播傳遞限制在7~8跳以?xún)?nèi)，即如果請(qǐng)求在經(jīng)過(guò)有限的循環(huán)廣播之后，仍不能得到響應(yīng)，則發(fā)送請(qǐng)求的節(jié)點(diǎn)將得到一個(gè)錯(cuò)誤信息。Gnutella是泛洪的經(jīng)典之作，Gnutella協(xié)議設(shè)置了三種機(jī)制來(lái)控制消息數(shù)量的指數(shù)增長(zhǎng)。

機(jī)制一:消息生存時(shí)間(Time-to-Live簡(jiǎn)稱(chēng)TTL)

消息生存時(shí)間主要是控制消息在網(wǎng)絡(luò)中傳播時(shí)能夠生存的時(shí)間，是消息頭中的一個(gè)字段，在消息生成時(shí)被賦予一個(gè)初始值。當(dāng)消息被發(fā)送出去，其它主機(jī)結(jié)點(diǎn)接收到該消息時(shí)，首先將該消息的TTL值減1，如果為零，則將該消息丟棄掉。否則，發(fā)給它的鄰居結(jié)點(diǎn)。TTL值越大，消息能傳播的距離就越遠(yuǎn)，反之，就越近。機(jī)制二:消息的唯一標(biāo)識(shí)符(UniqueMessageIdentification簡(jiǎn)稱(chēng)UID).

消息的唯一標(biāo)識(shí)符是為了避免一個(gè)消息在同一個(gè)主機(jī)節(jié)點(diǎn)重復(fù)傳播而設(shè)計(jì)的。UID也被包含在消息頭中，每個(gè)消息的標(biāo)識(shí)符都是不一樣的。當(dāng)消息被發(fā)送出去，其它主機(jī)結(jié)點(diǎn)接收到該消息時(shí)，取出它的消息頭中的UID字段，同本地記錄的UID列表相比較，如果該消息的UID己經(jīng)在列表中，說(shuō)明該主機(jī)結(jié)點(diǎn)己經(jīng)看過(guò)這條消息，它將直接把這條消息丟棄掉。否則，如果該消息的UID不在本地列表中，該主機(jī)結(jié)點(diǎn)將儲(chǔ)存這條消息的UID到本地UID列表，然后將該消息傳播出去。

機(jī)制三:路徑標(biāo)識(shí)符(PathIdentification)。

路徑標(biāo)識(shí)符是為了防止消息循環(huán)的出現(xiàn)及指導(dǎo)返回消息按原路返回而設(shè)置的。路徑標(biāo)識(shí)符其實(shí)是一個(gè)地址列表，記錄了該消息所經(jīng)過(guò)的結(jié)點(diǎn)的地址。當(dāng)一個(gè)主機(jī)結(jié)點(diǎn)接收到一條消息后，該主機(jī)結(jié)點(diǎn)會(huì)檢查自己的主機(jī)地址是否在消息所經(jīng)過(guò)的地址列表中，若在，說(shuō)明該條消息已經(jīng)到過(guò)該主機(jī)結(jié)點(diǎn)，則該主機(jī)結(jié)點(diǎn)會(huì)將這條消息直接丟棄。否則，該主機(jī)將自己的地址加入消息的地址列表中，然后發(fā)送出去。

以上三個(gè)控制機(jī)制保證了消息在網(wǎng)絡(luò)中不會(huì)被無(wú)限制的擴(kuò)散，從而確保Gnutella網(wǎng)絡(luò)可以正常的運(yùn)行。但是，這三種控制機(jī)制也不是盡善盡美，也會(huì)導(dǎo)致很多問(wèn)題，其中之一便是短路效應(yīng)。

泛洪請(qǐng)求式由于通過(guò)廣播方式進(jìn)行查找和定位，因此一般擴(kuò)展性差，但在小范圍內(nèi)效率高，可靠性好。此外如果在系統(tǒng)中存在一些所謂的超級(jí)節(jié)點(diǎn)（即該節(jié)點(diǎn)擁有大量的資源信息），則可以顯著減少帶寬的浪費(fèi)。

目前第二代泛洪請(qǐng)求式的資源定位主要采用分布式Hash表算法：賦予系統(tǒng)中每個(gè)節(jié)點(diǎn)一個(gè)全局唯一標(biāo)識(shí)符NID，通過(guò)一個(gè)哈希函數(shù)建立起資源唯一標(biāo)識(shí)符OID和NID之間的對(duì)應(yīng)關(guān)系：NID＝HASH(OID)，NID與OID是一對(duì)多的關(guān)系。將資源的定位信息<OID,P>保存到節(jié)點(diǎn)標(biāo)識(shí)符為HASH（OID）的節(jié)點(diǎn)上。當(dāng)用戶(hù)需要查找對(duì)象時(shí)，首先通過(guò)OID和哈希函數(shù)計(jì)算出該資源定位信息所在節(jié)點(diǎn)的標(biāo)識(shí)符HASH(OID)，然后將該請(qǐng)求發(fā)送到該節(jié)點(diǎn)上，即可找到該對(duì)象。由于P2P中，任意兩個(gè)節(jié)點(diǎn)可以通訊，并且各個(gè)節(jié)點(diǎn)上的哈希函數(shù)都相同，因此，只要知道對(duì)象的OID，用戶(hù)可以從任何一個(gè)節(jié)點(diǎn)出發(fā)找到該對(duì)象。

根據(jù)節(jié)點(diǎn)的NID與OID之間的映射關(guān)系不同，分布式Hash表算法有許多不同的實(shí)現(xiàn)形式，如Chord、CAN、Pastry、Tapestry等。目前的最好效率是發(fā)現(xiàn)資源需要的路由表長(zhǎng)度為logN（N為P2P網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)），查詢(xún)資源需要的通信量為logN。

2.3現(xiàn)有的問(wèn)題與改進(jìn)

如上所述，Gnutella中存在著短路效應(yīng)。如圖4所示，假設(shè)Gnutella網(wǎng)絡(luò)上有A,B,C三臺(tái)主機(jī)，當(dāng)有消息M(TTL=t)由主機(jī)A發(fā)出，假設(shè)有兩條路徑可以到達(dá)主機(jī)B，一條路徑是沿Ll(x1,x2,…,xp),路徑長(zhǎng)度為p；一條是L2(y1,y2,…,yq)，路徑長(zhǎng)度為q。另有一條由主機(jī)B到主機(jī)C的路徑L3(z1,…,zr)，路徑長(zhǎng)度為r，其中有p+r>t且q+r<t。設(shè)從路徑Ll傳遞的消息稱(chēng)為M1，把從路徑L2傳遞的消息稱(chēng)為M2。按照Gnutella的傳輸協(xié)議及以上介紹的三種控制機(jī)制，從主機(jī)A發(fā)出的消息，應(yīng)該能夠到達(dá)所有的符合以下條件的主機(jī)：這些主機(jī)距離主機(jī)A的跳數(shù)小于初始TTL值(從一個(gè)主機(jī)到另外一個(gè)與它直接相連的主機(jī)的距離稱(chēng)之為一跳)。按照這條規(guī)則，從主機(jī)A發(fā)出的消息M也應(yīng)該能夠到達(dá)主機(jī)C，因?yàn)榇嬖谶@樣一條路徑（y1，…，yq,z1,…，zr)，該路徑長(zhǎng)度(q+r)小于消息的初始TTL值t。但是，由于網(wǎng)絡(luò)異構(gòu)延遲的影響，消息M卻可能無(wú)法到達(dá)主機(jī)C。原因在于從主機(jī)A到主機(jī)B的傳輸過(guò)程中，假設(shè)從路徑Ll傳遞的消息M1先于從路徑L2傳遞的消息M2到達(dá)主機(jī)B，主機(jī)B在收到M1后，檢查它的UID及TTL，發(fā)現(xiàn)此UID并不在本地的消息列表中，它的TTL值t-p也大于0，所以它會(huì)先記錄M1的UID到本地的消息列表，然后將TTL值減去1，最后將M1發(fā)送給它的所有的鄰居。但是M1肯定無(wú)法到達(dá)主機(jī)C，因?yàn)閺闹鳈C(jī)A到主機(jī)C的跳數(shù)p+r大于消息的初始TTL值。在主機(jī)B處理過(guò)消息M1后，沿路徑L2的消息M2也將到達(dá)該主機(jī)。因?yàn)镸2和M1都是同一條消息的兩個(gè)副本，它們的UID也必然相同，因而當(dāng)主機(jī)B檢查消息M2的UID時(shí)，會(huì)發(fā)現(xiàn)該UID己經(jīng)存在于本地的UID列表中，按照控制機(jī)制二，主機(jī)B會(huì)丟棄消息M2。如此一來(lái)，便沒(méi)有可以到達(dá)主機(jī)C的消息。這就是短路效應(yīng)。需要說(shuō)明的是，當(dāng)網(wǎng)絡(luò)規(guī)模大到一定的程度時(shí)，由于網(wǎng)絡(luò)結(jié)構(gòu)、帶寬等的差異，異構(gòu)延遲現(xiàn)象的存在是很正常并且是很普遍的。實(shí)驗(yàn)表明，在現(xiàn)在的Gnutella網(wǎng)絡(luò)中，在異構(gòu)延遲的影響下，消息的可達(dá)率一般在55%左右，即一條消息發(fā)出后，在應(yīng)該收到該消息的主機(jī)中，約有一半數(shù)量的主機(jī)實(shí)際上收不到這條消息。這就大大降低了整個(gè)Gnutella網(wǎng)絡(luò)的查詢(xún)效率。

在原來(lái)的機(jī)制二中，主機(jī)結(jié)點(diǎn)在檢查完消息的UID后，如果發(fā)現(xiàn)該UID已經(jīng)在本地的消息列表中，則直接就將它丟棄了。從以上的分析知道，這是不合理的，因?yàn)樵撓⒂锌赡艿竭_(dá)比己經(jīng)存在的那條消息更遠(yuǎn)的距離。因此，可以首先保存每一條消息的TTL值，當(dāng)一個(gè)主機(jī)結(jié)點(diǎn)檢查一條消息的UID，發(fā)現(xiàn)該UID已經(jīng)存在時(shí)，再檢查該消息的TTL值，如果新的消息的TTL值比原來(lái)保存的TTL值要大，則將用較大的TTL值替換較小的TTL值，并將該消息繼續(xù)前傳播。這里用較大的TTL值替換較小的TTL值，是考慮到如果后面還有另一個(gè)網(wǎng)絡(luò)延遲更厲害但TTL值更大的副本到達(dá)時(shí)，主機(jī)不會(huì)把它丟棄掉。但是，這樣改進(jìn)之后還會(huì)引發(fā)另外一個(gè)返回結(jié)果的問(wèn)題。如圖4，當(dāng)M1到達(dá)主機(jī)B后，如果它有主機(jī)A要查詢(xún)的數(shù)據(jù)，則主機(jī)B會(huì)產(chǎn)生一條回應(yīng)消息，沿著M1來(lái)時(shí)的路徑傳送到主機(jī)A。那么當(dāng)消息M2到達(dá)時(shí)，主機(jī)B還會(huì)產(chǎn)生一條回應(yīng)消息，沿著M2的路徑傳送到主機(jī)A。但是M2的回應(yīng)消息己經(jīng)沒(méi)有必要，因?yàn)橐皇荕2的路徑延遲要比M1厲害，二是多發(fā)送的那條消息是重復(fù)的，白白占用了網(wǎng)絡(luò)的帶寬。因此做一個(gè)規(guī)定，當(dāng)一個(gè)主機(jī)先后接收到相同UID的消息后，如果需要回應(yīng)，只回應(yīng)第一條消息，其它的在做完TTL及UID檢查后，或丟棄，或只簡(jiǎn)單的傳給它的鄰居結(jié)點(diǎn)。

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

雖然P2P的概念出現(xiàn)由來(lái)已久，但是隨著Internet的迅猛發(fā)展近年來(lái)對(duì)其的研究和應(yīng)用日益成為熱點(diǎn)。目前Intel，SUN等多家國(guó)際IT企業(yè)都在投入相當(dāng)大的力量研究適用的P2P計(jì)算模型及其實(shí)現(xiàn)。由于P2P技術(shù)在對(duì)等計(jì)算、協(xié)同工作方面的強(qiáng)大優(yōu)勢(shì)，今后肯定會(huì)在這兩個(gè)方面迅猛發(fā)展；將P2P技術(shù)和C/S模式的互聯(lián)網(wǎng)結(jié)合起來(lái)，在搜索引擎、文件共享方面國(guó)內(nèi)外已經(jīng)有不少商業(yè)化產(chǎn)品投入使用，但由于P2P技術(shù)本身存在不易管理、安全性差等缺陷，造成P2P技術(shù)自出現(xiàn)以來(lái)，并沒(méi)有大規(guī)模應(yīng)用，而且這兩個(gè)問(wèn)題如果得不到有效解決，將會(huì)成為P2P技術(shù)在這兩個(gè)方面發(fā)展的主要瓶頸。

參考文獻(xiàn)

1.L.TassiulasandA.Ephremides,Stabilitypropertiesofconstrainedqueueingsystemsandschedulingpoliciesformaximumthroughputinmultihopradionetworks.IEEETransactionsonAutomaticControl，Vol37,No12,Dec.1992,pp:1936~1948

2.DanaMoore,JohnHebeler著.對(duì)等網(wǎng).清華大學(xué)出版社，2003

3.AndyOram編.Harnessingthebenefitsfoadisruptivetechnolody.清華大學(xué)出版社，2003

4.Peer-to-PeerComputing[EB/OL].

www.sics.se/perbrand/,2001211203

5.KarlA,MagdalenaP.ImprovingDataAccessinP2PSystems[J].IEEEInternetComputing,2002,6(1):58-67..

6.呂向辰.P2P技術(shù)與應(yīng)用./01/0128/d/0128d06-1.asp