一種基于對等網(wǎng)絡(luò)的高效查詢機制

摘 要：如何實現(xiàn)有效查詢是對等應(yīng)用的關(guān)鍵，在分析幾種常見的查詢算法的基礎(chǔ)上，介紹雙重指針分布式索引算法的實現(xiàn)過程。通過計算對等網(wǎng)絡(luò)中文檔的流行度和網(wǎng)絡(luò)的連通狀態(tài)，確定節(jié)點的有用性，進一步?jīng)Q定查詢的路由。通過仿真實驗，將該算法與幾種常用算法在查詢耗時、查詢請求數(shù)量、更新信息數(shù)量上進行比較。

關(guān)鍵詞：對等網(wǎng)絡(luò);查詢;DDI算法;有用性

中圖法分類號：TP393.02文獻標(biāo)識碼：A

文章編號：1001—3695(2007)02—0318—03

隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，對等網(wǎng)絡(luò)（Peer-to-Peer，P2P）技術(shù)的研究已逐漸成熟，在不同的領(lǐng)域有著廣泛的應(yīng)用，一些大型的P2P計算項目也進入實施階段。目前，比較流行的軟件系統(tǒng)如Gnutella，F(xiàn)reenet，Napster等都是基于P2P技術(shù)實現(xiàn)的。關(guān)于如何在P2P網(wǎng)絡(luò)中實現(xiàn)有效的信息查詢也逐漸成為P2P研究方面的熱點。

1 相關(guān)技術(shù)

P2P網(wǎng)絡(luò)中分布的主機之間有著高度的自治性，并且扮演相同的角色，在需要時進行信息交換。對等的主機在查

找、發(fā)現(xiàn)信息時，必須采用一定的查找發(fā)現(xiàn)協(xié)議來確定信息提供者的地理位置，獲得目標(biāo)主機物理地址的一個鏈接或者是在某個公共的命名服務(wù)器中唯一的標(biāo)識符，然后對等的主機之間按照事先約定好的規(guī)則進行數(shù)據(jù)通信。目前，對等網(wǎng)絡(luò)采用的查詢算法大約有以下三種：

(1)集中式查詢（CS）。一般在有中心節(jié)點或?qū)嶓w服務(wù)器的網(wǎng)絡(luò)中采用。對等主機進行查詢時，先向中心服務(wù)器發(fā)送查詢請求，由中心服務(wù)器負責(zé)處理請求并作出應(yīng)答，查詢主機根據(jù)應(yīng)答的內(nèi)容來進行下一步的操作。Hybrid P2P采用的就是集中式查詢，其實Hybrid P2P是一種混合型的網(wǎng)絡(luò)，兼有C/S網(wǎng)絡(luò)和對等網(wǎng)絡(luò)的優(yōu)點。CS查詢的缺點是如果有大量的對等節(jié)點同時需要在中心節(jié)點進行信息查詢，則會給中心節(jié)點帶來很大的網(wǎng)絡(luò)負載和管理費用，并且中心節(jié)點的可靠性也是這種類型網(wǎng)絡(luò)的致命弱點，如果中心節(jié)點癱瘓或停止服務(wù)，則整個網(wǎng)絡(luò)無法實現(xiàn)連通。

(2)分布式查詢（DS）。網(wǎng)絡(luò)中并不存在特殊的節(jié)點提供查詢服務(wù)，而是每一個對等節(jié)點向其他節(jié)點直接進行查詢請求，每一個節(jié)點均維護一個列表在自己的緩存中，并且不定期地進行更新。如果在本地網(wǎng)絡(luò)中不存在目標(biāo)節(jié)點，則由網(wǎng)絡(luò)中負責(zé)路由的節(jié)點將請求轉(zhuǎn)發(fā)到其他網(wǎng)絡(luò)。Gnutella，F(xiàn)reenet和Sun公司開發(fā)的對等計算平臺——JXTA采用的就是DS查詢，DS查詢性能明顯要優(yōu)于CS。但是在較大規(guī)模的對等網(wǎng)絡(luò)中（1 000個節(jié)點以上），若采用DS算法，由于每一個對等節(jié)點需要向其他所有節(jié)點發(fā)送查詢請求，導(dǎo)致網(wǎng)絡(luò)通信量呈指數(shù)級增長，網(wǎng)絡(luò)帶寬被大量占用，網(wǎng)絡(luò)性能急劇下降。并且主機節(jié)點的緩存經(jīng)常處于缺頁狀態(tài)，可通過增加緩存更新的頻率，將已經(jīng)失效的節(jié)點信息從緩存中清除出去，但是頻繁的緩存調(diào)度也會影響系統(tǒng)的性能。

(3)帶指針的分布式查詢（Distributed Searching with Indices，DSI）。節(jié)點通過保存在緩存中的指針進行查詢，可以將DSI看作是在DS基礎(chǔ)上的優(yōu)化。采用DSI可以很好地解決CS和DS的弊端，在純粹的P2P（PP2P）網(wǎng)絡(luò)中可以實現(xiàn)有效的查詢。在這種類型的網(wǎng)絡(luò)中，每個節(jié)點都知道其鄰節(jié)點的存在，所有的查詢都通過向鄰節(jié)點轉(zhuǎn)發(fā)進行深度優(yōu)先搜索，并且在緩存中保存指針，指向其他節(jié)點，查詢是根據(jù)指針的指向進行的。

目前，在P2P網(wǎng)絡(luò)中采用的算法大多是DSI算法或改進后的DSI算法，如一些學(xué)者設(shè)計了基于分布式哈希表的查詢技術(shù)（DHTs）、路由索引（RIs）查詢算法等。Taizo Yamada，Kenro Aihara等人提出一種直接索引算法DI[1]，主要思想就是將網(wǎng)絡(luò)節(jié)點分為三類，即連接節(jié)點、查詢節(jié)點和傳輸節(jié)點，每個節(jié)點有不同的功能。節(jié)點在緩存中保存其他節(jié)點的有用性，查詢進行時以節(jié)點的有用性作為依據(jù)。與DSI算法相比，DI算法，在查詢的請求數(shù)量、查詢消耗的時間以及更新指針帶來的開銷大大減小。但是DI算法存在以下幾個問題：

(1)單純討論節(jié)點之間的相對有用性，沒有考慮網(wǎng)絡(luò)連通狀態(tài)。節(jié)點的連通性只有在更新指針信息時才能反映出來。

(2)可能由于某個節(jié)點的文檔流行度過高而導(dǎo)致該節(jié)點的有用性較高。對于結(jié)構(gòu)不對稱的網(wǎng)絡(luò)，該算法的客觀性比較差。在如圖1所示的網(wǎng)絡(luò)中，節(jié)點C的本身的有效性過高，但是對于G，I等節(jié)點來說，它們之間只有一條非直接連接的鏈路，并且經(jīng)過幾次轉(zhuǎn)發(fā)，因此有用性并不高。

(3)節(jié)點的有用性沒有累積效應(yīng)。在某幾個更新周期內(nèi)，節(jié)點的有用性的累積應(yīng)該比較明顯。

本文在DI查詢算法的基礎(chǔ)上，針對上述問題，對節(jié)點的指針結(jié)構(gòu)和查詢算法作出一些改進，提出一個在對等網(wǎng)絡(luò)環(huán)境下進行信息查詢的算法DDI（Distributed-searching with Double Indices，雙重指針分布式索引)，介紹該算法的詳細步驟，并討論算法的性能，最后通過仿真實驗將該算法和傳統(tǒng)的算法進行比較。

2 雙重指針分布式索引——DDI

2.1 節(jié)點有用性

在P2P網(wǎng)絡(luò)中，查詢的效率與查詢所采用的算法以及具體的網(wǎng)絡(luò)環(huán)境有關(guān)。在采用指針查詢算法中，指針結(jié)構(gòu)是優(yōu)化算法的關(guān)鍵環(huán)節(jié)，因為查詢過程的進行就是通過指針的移動來實現(xiàn)的。另外，指針內(nèi)容的更新頻率也影響查詢的效率。指針?biāo)赶虻氖枪?jié)點的描述信息，除了有目標(biāo)節(jié)點的一般信息，如文檔、源路由等，還應(yīng)該加入節(jié)點的有用性（Availability）信息，并且在具體的查詢過程中將有用性作為衡量節(jié)點完成查詢的能力。節(jié)點的有用性主要是由節(jié)點的訪問頻率、節(jié)點最近訪問的時間、節(jié)點之間通信開銷以及節(jié)點所保存的文檔流行度等因素來決定的。將節(jié)點的有用性作為查詢的一種依據(jù)，能有效避免查詢信息在網(wǎng)絡(luò)上大規(guī)模的發(fā)送，在實踐中降低了發(fā)生廣播風(fēng)暴的幾率，降低了網(wǎng)絡(luò)帶寬的占用，在一定程度上提高了查詢機制的性能。

其中，Tc是當(dāng)前時間，亦即指針更新時的時間，Tl是文檔最后被訪問的時間，Q是用戶給定的某一參數(shù)，反映累加效應(yīng)的權(quán)重，且有0

節(jié)點的有用性等于節(jié)點中所有共享文檔流行度的平均值，節(jié)點p的有用性（也稱本地有用性）計算如下：

其中，D(p)表示節(jié)點p的所有共享文檔的集合。通過節(jié)點文檔的流行度來確定節(jié)點的有用性E(p)，并且E(p)∈[0，1]，數(shù)值越大，表示節(jié)點越有用，對其他節(jié)點的參考價值越顯著。

這樣分析節(jié)點之間相對有用性有兩個優(yōu)點:①將網(wǎng)絡(luò)的連通狀態(tài)考慮進去，將節(jié)點之間的最佳路由和有用性最大值一一對應(yīng);②對某一節(jié)點而言，具有相同的本地有用性的鄰節(jié)點和非鄰節(jié)點，計算出來的相對有用性是有差異的，鄰節(jié)點的相對有用性應(yīng)該要大一些，之間的差異通過參數(shù)μ來調(diào)節(jié)。

2.2 DDI查詢算法描述

采用DI查詢時，如果目標(biāo)節(jié)點并非鄰節(jié)點，而且要經(jīng)過很多的步跳才能到達，則查詢效率會有所下降。因為DI查詢是通過向鄰節(jié)點發(fā)送查詢請求，并轉(zhuǎn)發(fā)。如果目標(biāo)節(jié)點經(jīng)過很多次轉(zhuǎn)發(fā)才能到達，這樣中間節(jié)點就會向其鄰節(jié)點發(fā)送很多的查詢請求，直到確定查詢前進方向為止。在這種情況下，查詢請求信息量會急劇上升。

2.2.1 DDI索引表的結(jié)構(gòu)

DDI所使用的索引表實際上就是一個指針列表，分別指向不同的網(wǎng)絡(luò)節(jié)點，列表中的每一項存放的是對應(yīng)節(jié)點的重要信息，如節(jié)點的ID信息、位置信息（物理地址或IP）、節(jié)點的相對有用性和路由信息等。其中，節(jié)點的物理地址由網(wǎng)絡(luò)中專門的系統(tǒng)（名字系統(tǒng)）來進行分配和認證的，路由信息是當(dāng)前節(jié)點到目標(biāo)節(jié)點的最佳路徑，通過路由指針指向一個最佳路由表，并且，按照路由信息計算出來的節(jié)點之間的相對有用性一定為最大值。圖2是某網(wǎng)絡(luò)中節(jié)點p1索引表和路由表的例子。

2.2.2 查詢過程

在本地網(wǎng)絡(luò)初始化時，每一個節(jié)點都計算與其他節(jié)點的相對有用性，并且將自己的地理位置和相對有用性發(fā)送給目標(biāo)節(jié)點，目標(biāo)節(jié)點將所有接收到的節(jié)點的相關(guān)信息維護在索引表中，以供查詢時使用。索引表間隔一定的時間進行更新。

查詢時，節(jié)點搜索本地索引表，從中選擇有用性較高的目標(biāo)節(jié)點，并且按照路由順序依次通過中間節(jié)點進行轉(zhuǎn)發(fā)。由于DDI算法事先已經(jīng)確定雙方的路由信息，所以就可以直接進行查詢，而DI查詢事先沒有確定路由，是由轉(zhuǎn)發(fā)節(jié)點自主選擇路由，必然要消耗一定的時間來進行路由信息的確認，因此在查詢信息傳播消耗的時間要遠遠小于DI查詢。從目標(biāo)節(jié)點搜索到足夠的文檔后，查詢結(jié)束。如果沒有達到預(yù)定的文檔數(shù)量，則選擇次優(yōu)有用性的節(jié)點繼續(xù)進行查詢。

在目標(biāo)節(jié)點查詢到滿足條件的文檔時，雙方建立通信鏈路后即可進行文檔的傳輸，文檔也通過中間節(jié)點進行轉(zhuǎn)發(fā)。如果預(yù)定的文檔分布在多個節(jié)點上，則需要同時與多個節(jié)點進行連接，實現(xiàn)文檔的并行傳輸。

2.2.3 索引表的維護

DDI索引表主要的維護有增加節(jié)點、刪除節(jié)點和節(jié)點信息更新。當(dāng)網(wǎng)絡(luò)中有新的節(jié)點加入時，該節(jié)點首先向網(wǎng)絡(luò)中所有節(jié)點發(fā)送廣播包，其他節(jié)點接收到廣播包后發(fā)送應(yīng)答消息到新加入節(jié)點，節(jié)點根據(jù)應(yīng)答消息中的路由信息計算與各節(jié)點之間的相對有用性，并將信息添加到索引表中，其他節(jié)點也根據(jù)接收到的廣播信息計算各自與新加入節(jié)點的相對有用性和路由信息。圖3是一個新節(jié)點的加入過程。

若有節(jié)點退出網(wǎng)絡(luò)或經(jīng)過幾個時間周期仍然沒有連通消息，則網(wǎng)絡(luò)中的其他節(jié)點從索引表中將該節(jié)點刪除，同時刪除相應(yīng)的路由指針指向的路由信息表。

若節(jié)點的物理位置發(fā)生變化，與其他節(jié)點的相對有用性、節(jié)點之間的路由隨之也發(fā)生變化，必須及時更新索引表中節(jié)點的有用性、路由信息，但是索引表中有關(guān)該節(jié)點的ID信息不會發(fā)生變化。節(jié)點也是通過向網(wǎng)絡(luò)中其他節(jié)點廣播的方式來發(fā)送更新的信息。更新節(jié)點根據(jù)接收到的應(yīng)答中的路由信息重新計算相對有用性，發(fā)送至每一個節(jié)點。

DDI查詢的優(yōu)點在于：查詢耗時短，因為根據(jù)相對有用性來決定查詢的前進方向，而且查詢的路徑是節(jié)點間的最佳路由；查詢所占用的網(wǎng)絡(luò)帶寬小，采用DDI查詢不存在大規(guī)模的發(fā)送查詢請求，不可能因為查詢的節(jié)點數(shù)量的增加而引起網(wǎng)絡(luò)風(fēng)暴；其適合在大規(guī)模的對等網(wǎng)絡(luò)中應(yīng)用。

3 試驗

試驗采用OPNET 8.1模擬對等網(wǎng)絡(luò)環(huán)境，設(shè)定網(wǎng)絡(luò)中節(jié)點數(shù)為6 000個，文檔數(shù)800個，預(yù)定可接收的查詢文檔數(shù)15個。

在試驗中分別采用三種不同的查詢方式，即無指針的分布式查詢DS、直接索引DI和雙重指針的分布式索引DDI，比較不同查詢方式的結(jié)果。主要有三個參數(shù)作為查詢優(yōu)劣的衡量指標(biāo)，即查詢時發(fā)送請求信息數(shù)量、更新時指針更新數(shù)量和查詢耗時。

圖4是不同的查詢方法在進行查詢時所發(fā)送的查詢請求信息的數(shù)量。可以看出采用DS查詢，由于節(jié)點向所有的相關(guān)節(jié)點發(fā)送查詢請求，所以，信息量隨著節(jié)點數(shù)量增長的速度很快，直至網(wǎng)絡(luò)帶寬完全被占用。DI查詢在涉及較少節(jié)點時，信息量比較少，但是若查詢需要重復(fù)多次進行，則信息量會有迅速增加的趨勢。本文介紹的DDI算法，由于查詢是直接針對目標(biāo)節(jié)點進行，中間節(jié)點只是轉(zhuǎn)發(fā)功能，所以查詢的請求信息很少。

圖5是網(wǎng)絡(luò)結(jié)構(gòu)或文檔狀態(tài)有變化，節(jié)點索引表需要更新時，兩種查詢算法DI和DDI所更新的索引信息數(shù)量。可以看出采用DDI查詢在索引表更新時，信息數(shù)量要少于DI查詢。

圖6比較三種查詢所消耗的時間。由于DS查詢是一種發(fā)散式的查詢，需要向節(jié)點發(fā)送的查詢信息量較多，所以查詢耗時明顯高于其他兩種。而DDI查詢是直接向目標(biāo)節(jié)點發(fā)送查詢請求，并建立連接傳輸文件，因此耗時要比DI少。若查詢需要的文檔數(shù)量比較少，并且正好可以在鄰節(jié)點上得到所有的文檔時，DI查詢也具有一定的優(yōu)勢。因此，在圖6中當(dāng)查詢涉及的節(jié)點數(shù)量較少時，DI查詢甚至優(yōu)于DDI查詢。

4 總結(jié)

本文提出一種基于對等網(wǎng)絡(luò)的查詢算法——雙重指針的分布式查詢（DDI）。該算法構(gòu)造了一種特殊結(jié)構(gòu)的索引表作為查詢進行的依據(jù)。通過試驗來比較幾種查詢算法的性能，證明了采用DDI算法在查詢耗時、查詢發(fā)送的請求信息數(shù)量以及更新信息數(shù)量上均優(yōu)于目前比較流行的兩種查詢算法。由此可見在大規(guī)模的對等網(wǎng)絡(luò)中，采用DDI算法，在能夠?qū)崿F(xiàn)文檔的高效查詢的同時，對節(jié)省網(wǎng)絡(luò)資源也起到一定的積極作用。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。