ML-Chord中基于動(dòng)態(tài)查詢(xún)的查詢(xún)策略

孫娟娟，禹繼國(guó)

（曲阜師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，山東 日照 276826）

0 引言

無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)一般采用洪泛法進(jìn)行資源定位。該方法在查詢(xún)受歡迎文件時(shí)非常有效，但在查詢(xún)稀有文件時(shí)效率不高；結(jié)構(gòu)化P2P網(wǎng)絡(luò)一般利用分布式哈希表來(lái)定位資源。該方法在查詢(xún)稀有文件時(shí)比較有效，但在進(jìn)行多關(guān)鍵字查詢(xún)或者區(qū)間查詢(xún)時(shí)效率比較低。鑒于它們的優(yōu)缺點(diǎn)，P2P網(wǎng)絡(luò)中的混合查詢(xún)機(jī)制引起了越來(lái)越多研究者的關(guān)注。

文獻(xiàn)[1]將現(xiàn)有P2P混合查詢(xún)策略分成兩類(lèi)：第一類(lèi)是基于檢測(cè)的簡(jiǎn)單混合策略。該策略首先執(zhí)行洪泛，如果在一個(gè)預(yù)定的時(shí)間內(nèi)沒(méi)有返回足夠多的查詢(xún)結(jié)果，就將其作為一個(gè)DHT再次發(fā)起查詢(xún)過(guò)程，直到查詢(xún)內(nèi)容最終被定位到；第二類(lèi)是采用閑聊方式利用收集到的聚集信息來(lái)估算文件的受歡迎程度，并且通過(guò)在相關(guān)文件數(shù)目上設(shè)定閾值以確定是采用洪泛還是采用DHT。

1 相關(guān)工作

動(dòng)態(tài)查詢(xún)是無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)中采用的查詢(xún)技術(shù)，該方法使用較少的節(jié)點(diǎn)就能夠到達(dá)目標(biāo)節(jié)點(diǎn)。查詢(xún)發(fā)起者在一個(gè)小的TTL值內(nèi)通過(guò)“刺探”過(guò)程將查詢(xún)信息發(fā)送給網(wǎng)絡(luò)中的一些節(jié)點(diǎn)并由此開(kāi)始查詢(xún)過(guò)程。“刺探”查詢(xún)的目標(biāo)是對(duì)定位到的資源評(píng)估其受歡迎程度[2]。

文獻(xiàn)[3]中，Lu等在Chord[4]的基礎(chǔ)上，提出了多層次P2P資源共享模型 ML-Chord。該模型中的所有資源基于一個(gè)選擇的本體被分成不同的類(lèi)別，每一個(gè)類(lèi)別對(duì)應(yīng)一個(gè)覆蓋層；同時(shí)選出能力強(qiáng)的節(jié)點(diǎn)作為橋節(jié)點(diǎn)連接到所有Chord環(huán)上，所有橋節(jié)點(diǎn)組成一個(gè)Chord環(huán)。

動(dòng)態(tài)查詢(xún)是在無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)中采用的查詢(xún)技術(shù)，采用這種查詢(xún)方法可以使用較少的節(jié)點(diǎn)就可以達(dá)目標(biāo)節(jié)點(diǎn)。查詢(xún)發(fā)起者在一個(gè)小的 TTL內(nèi)通過(guò)把查詢(xún)信息發(fā)送給網(wǎng)絡(luò)中的一些節(jié)點(diǎn)開(kāi)始搜索過(guò)程。這個(gè)“刺探”查詢(xún)的目標(biāo)是對(duì)定位到的資源。這個(gè)“刺探”查詢(xún)的目標(biāo)是對(duì)定位到的資源評(píng)估其受歡迎程度。一種結(jié)合動(dòng)態(tài)查詢(xún)的搜索算法應(yīng)用在了無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)中[5],將動(dòng)態(tài)查詢(xún)應(yīng)用到無(wú)結(jié)構(gòu)的洪泛[6]比文獻(xiàn)[5]中的查詢(xún)方法取得了更好的搜索效率。

文獻(xiàn)[5]中，Talia等在Chord上將動(dòng)態(tài)查詢(xún)技巧與文獻(xiàn)[7]提出的有效廣播算法結(jié)合。查找過(guò)程是首先進(jìn)行一個(gè)刺探階段，如果在刺探階段已得到足夠多的查詢(xún)結(jié)構(gòu)，則終止查詢(xún)。否則，根據(jù)刺探階段得到的數(shù)據(jù)估算文件的受歡迎程度作為調(diào)整洪泛范圍的依據(jù)。

2 ML-Chord中動(dòng)態(tài)查詢(xún)的執(zhí)行

2.1 ML-Chord的結(jié)構(gòu)

圖1 ML-Chord的結(jié)構(gòu)示意

若系統(tǒng)中有C個(gè)類(lèi)別覆蓋層，則整個(gè)邏輯覆蓋網(wǎng)中有T=C+1個(gè)邏輯覆蓋層。圖1中所示的節(jié)點(diǎn)和雖然標(biāo)識(shí)符不同，但它們是同一個(gè)節(jié)點(diǎn)，即相同的節(jié)點(diǎn)位于兩個(gè)覆蓋層上，這也意味著該節(jié)點(diǎn)需要維護(hù)兩套路由表。

2.2 動(dòng)態(tài)查詢(xún)過(guò)程

由于P2P用戶(hù)常在本地空間上存儲(chǔ)相似文件，如圖2所示：查詢(xún)與a和b相關(guān)的文件，與a有關(guān)的文件廣泛存儲(chǔ)在系統(tǒng)中的節(jié)點(diǎn)上，而與b有關(guān)的文件之存儲(chǔ)在少量節(jié)點(diǎn)上，若按照計(jì)算得到。然而，Pa的值應(yīng)大于Pb的值，由此出現(xiàn)了文件受歡迎程度誤差偏大的情況。

圖2 系統(tǒng)中文件分布舉例

2.3 ML-Chord中的動(dòng)態(tài)查詢(xún)算法

對(duì)于給定的一棵二項(xiàng)式樹(shù)，它的性質(zhì)：①Bi中的節(jié)點(diǎn)數(shù)是2i；②Bi的深度為i；③Bi中在l層上的節(jié)點(diǎn)數(shù)目通過(guò)二項(xiàng)式系數(shù)及動(dòng)態(tài)查詢(xún)算法需要用到的參數(shù)得到。表1給出了相關(guān)的參數(shù)定義。

表1 參數(shù)定義

首先，將當(dāng)前查找到的資源數(shù)目Rc賦值為0，當(dāng)接收到一個(gè)查詢(xún)應(yīng)答時(shí)Rc的數(shù)目就會(huì)增加1，集合U初始化為節(jié)點(diǎn)中存儲(chǔ)的與資源 R屬于同一類(lèi)別的覆蓋層的路由表內(nèi)所有的獨(dú)一無(wú)二的指針數(shù)。將Hi設(shè)置為N(U), N(U)與網(wǎng)絡(luò)中可以查詢(xún)到的主機(jī)數(shù)目相一致，從集合U中選擇出第一個(gè)需要訪問(wèn)的子集V,集合U隨之做相應(yīng)更新。

3 性能分析

現(xiàn)在考慮一般情況：假設(shè)匹配的資源在節(jié)點(diǎn)間均勻分布，在刺探階段可以得到資源受歡迎程度的準(zhǔn)確估計(jì)，大多數(shù)的查詢(xún)只需要 2次迭代（其中包括刺探階段）。這種情況下，最大的查詢(xún)時(shí)間是刺探查詢(xún)時(shí)間和覆蓋最深子樹(shù)的迭代查詢(xún)時(shí)間，即TS=TH×((L+2)+(DU+2))，又Du=log2(N-1)，得到同理，若普通節(jié)點(diǎn)只加入一次覆蓋層且所有節(jié)點(diǎn)在覆蓋層上均勻分布，查詢(xún)的時(shí)間復(fù)雜度為

4 結(jié)語(yǔ)

這里將動(dòng)態(tài)查詢(xún)部署在多層次結(jié)構(gòu)化 P2P系統(tǒng)ML-Chord上，節(jié)點(diǎn)根據(jù)查詢(xún)資源的類(lèi)別選擇執(zhí)行動(dòng)態(tài)查詢(xún)，或者由能力更高的橋節(jié)點(diǎn)代為執(zhí)行。動(dòng)態(tài)查詢(xún)的優(yōu)點(diǎn)在于允許執(zhí)行任意類(lèi)型的查詢(xún)，可以根據(jù)文件的受歡迎程度調(diào)整查詢(xún)范圍，減少了網(wǎng)絡(luò)負(fù)載。更改后的文件受歡迎程度的簡(jiǎn)單估算方法提高了計(jì)算準(zhǔn)確性，有效地提高了查詢(xún)效率。

[1] CHEN Hanhua, JIN Hai, LIU Yunhao, et al.Difficulty-aware Hybrid Search in Peer-to-peer Networks[C].USA:IEEE,2009:71-82.

[2] VLADIMIR VISHNEVSKY, ALEXANDER SAFONOV, MIKHAIL YAKIMOV, et al.Alexander D.Gelman.Scalable Blind Search and Broadcasting over Distributed Hash Tables[J].Computer Communications, 2008, 31(02): 292-303.

[3] LU Juilin, HUANG Yungfa, LU Shuchiu.ML-Chord: A Multi-Layered P2P Resource Sharing Model[J].Network and Computer Applications, May 2009, 32(03):578-588.

[4] STOICA I, MORRIS R, KARGER D, et al.Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[C].[EB/OL].(2006-11-24) [2009-12-23].http://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf.

[5] FISK A.Gnutella Dynamic Query Protocol v0.1[EB/OL].(2003-05-12) [2009-12-23]. http://www9.limewire.com/developer/dynamic_query.html.

[6] JIANG H, JIN S.Exploiting Dynamic Querying Like Flooding Techniques in Unstructured Peer-to-peer Networks[C].USA:IEEE,2005:1121-1123.

[7] SAMEH EL A, LUC ONANA ALIMA, PER BRAND, et al.Efficient Broadcast in Structured P2P Networks[EB/OL].(2009-11-10)[2009-12-23].http://soda.swedish-ict.se/2811/

[8] PAOLO TRUNFIO, DOMENICO TALIA.Implementing Dynamic Querying Search in k-ary DHT-based Overlays[C].[s.l.]:Computer Science, 2008:275-286.

[9] DOMENICO TALIA, PAOLO TRUNFIO.Dynamic Querying in Structured Peer-to-Peer Networks, Submitted for Publication[EB/OL](2008-11-02)[2009-12-23].Available at:http://grid.deis.unical.it/papers/pdf/DQ-DHT.pdf.