鄭藝芳

(福建師范大學(xué)人民武裝學(xué)院,福建福州350007)

基于Dual-Chord模型的資源定位技術(shù)研究＊

鄭藝芳

(福建師范大學(xué)人民武裝學(xué)院,福建福州350007)

為了更高效地實(shí)現(xiàn)資源定位,提出了一種基于Dual-Chord的資源定位模型,在該模型中將網(wǎng)絡(luò)分成主網(wǎng)和子網(wǎng)兩層,主網(wǎng)采用k-高頻詞搜索路由算法,子網(wǎng)采用雙向查詢Chord算法.理論上得出使用該模型的用戶可以實(shí)現(xiàn)高效的查全率、查準(zhǔn)率,實(shí)現(xiàn)高度的資源本地化等.

P2P;Dual-Chord模型;網(wǎng)絡(luò)資源;資源定位

1 P2P簡(jiǎn)介

最近幾年來,P2P(Peer-to-Peer)成為了因特網(wǎng)上的一個(gè)熱點(diǎn).P2P是因特網(wǎng)的一種應(yīng)用模式,其意思是指網(wǎng)絡(luò)上的任何設(shè)備(包括大型機(jī)、PC機(jī)、PDA、手機(jī)、機(jī)頂盒等等)都可以平等地直接協(xié)作.相比當(dāng)前因特網(wǎng)上主流的應(yīng)用模式Client/Server或者Client/Service而言,P2P具有自己鮮明的特點(diǎn)和優(yōu)勢(shì).

P2P是一種技術(shù),但更多的是一種思想,有著改變整個(gè)互聯(lián)網(wǎng)基礎(chǔ)的潛能的思想.當(dāng)前,學(xué)術(shù)界對(duì)P2P有著許多不同的定義,各種不同的定義看起來都有一些差別,但本質(zhì)上都不矛盾.P2P中的P指的是peer,peer的意思是“(地位、能力等)同等者”、“伙伴”等意思.因此,P2P可以解釋為“伙伴對(duì)伙伴”或者“端對(duì)端”等意思,更通俗的稱法就是“對(duì)等網(wǎng)絡(luò)”.

當(dāng)今社會(huì),P2P被認(rèn)為在加強(qiáng)網(wǎng)絡(luò)上人的交流、文件交換、分布計(jì)算等方面大有前途.P2P還是point to point點(diǎn)對(duì)點(diǎn)下載的意思,它是下載術(shù)語,意思是你在下載別人計(jì)算機(jī)上信息的同時(shí),自己的計(jì)算機(jī)也在信息上傳.這種下載方式,參與的人越多下載的速度越快,但缺點(diǎn)是對(duì)你的硬盤損傷比較大(在寫的同時(shí)還要讀),還有就是對(duì)你內(nèi)存占用較多,影響整機(jī)速度.

下一代互聯(lián)網(wǎng)的關(guān)鍵技術(shù)被認(rèn)為是P2P技術(shù),與傳統(tǒng)的客戶端與服務(wù)器的構(gòu)架不同,對(duì)等網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)既是客戶端也是服務(wù)器.《財(cái)富》更將對(duì)等網(wǎng)絡(luò)認(rèn)為是影響Internet未來的四項(xiàng)科技之一.雖然目前P2P還沒有一個(gè)統(tǒng)一的定義,但各種定義雖稍有不同,卻都是有著共同點(diǎn):P2P打破了傳統(tǒng)的C/S模式,在P2P網(wǎng)絡(luò)中,每個(gè)節(jié)點(diǎn)都有著相同地位,他們既為其他節(jié)點(diǎn)提供服務(wù),又充當(dāng)服務(wù)器.C/ S模式和P2P的網(wǎng)絡(luò)結(jié)構(gòu)分別如圖1、圖2所示.對(duì)等網(wǎng)絡(luò)(Peer to Peer)是指基于非集中式模型、充分利用分布式節(jié)點(diǎn)資源的系統(tǒng)和應(yīng)用程序的集合.和傳統(tǒng)的集中式/客戶端相比,對(duì)等網(wǎng)絡(luò)中不再有任何中心節(jié)點(diǎn)或集中式服務(wù)器,而是每個(gè)節(jié)點(diǎn)之間直接的通信.節(jié)點(diǎn)同時(shí)扮演著服務(wù)器和客戶端這兩個(gè)角色,這種方式最小化了工作負(fù)荷可是最大化了網(wǎng)絡(luò)性能.

圖1 C/S模式的網(wǎng)絡(luò)結(jié)構(gòu)

圖2 P2P模式的網(wǎng)絡(luò)結(jié)構(gòu)

從圖中我們可以看到,P2P把互聯(lián)網(wǎng)中的人們直接聯(lián)系起來,使得人們?cè)诨ヂ?lián)網(wǎng)中可以直接進(jìn)行交互.從而P2P讓人們?cè)诨ヂ?lián)網(wǎng)上的溝通變得更直接、更容易,因此也就更好地做到了共享和交互,真正做到了消除中間商.P2P另一個(gè)突出的特點(diǎn)是改變傳統(tǒng)Internet中以大網(wǎng)站為中心的狀態(tài)、重返“非中心化”,并把權(quán)力交還給用戶.P2P聽起來似乎很新鮮,但正如B2C、B2B將現(xiàn)實(shí)世界中很普通的東西存儲(chǔ)到互聯(lián)網(wǎng)上一樣,P2P并不是什么新鮮東西.在實(shí)際的生活中,人們每天都是按照P2P的模式,面對(duì)面地或者通過電話來進(jìn)行交流和溝通.

2 P2P網(wǎng)絡(luò)資源定位技術(shù)

2.1 雙向查詢Chord引用[1]

在子網(wǎng)中,我們利用雙向Chord算法來實(shí)現(xiàn)資源定位.下面是對(duì)雙向Chord算法的介紹.由斯坦福大學(xué)提出的雙向查詢系統(tǒng)同時(shí)利用了節(jié)點(diǎn)的后繼節(jié)點(diǎn)和前驅(qū)節(jié)點(diǎn)列表信息,從順時(shí)針和逆時(shí)針的兩個(gè)方向進(jìn)行資源查找.它除了順時(shí)針的查詢路由表,還定義了另外一張路由表,稱之為R-finger表,這張表是Chord協(xié)議中finger表的一個(gè)反轉(zhuǎn),是一張逆時(shí)針方向的路由表.圖3是一個(gè)雙向查詢Chord中一個(gè)節(jié)點(diǎn)的全部路由表的定義.其中包括了協(xié)議中的finger路由表successor和predecessor路由項(xiàng),而R-finger路由表則是雙向協(xié)議里面才有的.

雙向查詢系統(tǒng)的主要算法思想是:Chord環(huán)上的任意兩個(gè)節(jié)點(diǎn)之間的邊可以看作是一條路由,它代表疊加層上的一個(gè)連接.假設(shè)環(huán)上存在兩個(gè)節(jié)點(diǎn),并且X和Y之間的距離是2的i次方,則X和Y之間的路由可以定義為這里是m標(biāo)識(shí)符的二進(jìn)制表示位,并且0≤i

圖3 Chord查詢模型

2.2 k-高頻詞搜索算法[2]

在主網(wǎng)中,我們利用k-高頻詞搜索算法來實(shí)現(xiàn)資源定位.下面是對(duì)k-高頻詞搜索算法的介紹.

基于k-高頻詞主題相關(guān)性搜索路由算法(RTRkFT)的基本原理概述為:以節(jié)點(diǎn)搜索結(jié)果集的主題作為搜索請(qǐng)求的主題,計(jì)算搜索請(qǐng)求的主題與遠(yuǎn)程對(duì)等點(diǎn)表中的節(jié)點(diǎn)的主題的距離,根據(jù)距離排序,把搜索請(qǐng)求路由到具有最小距離的那些節(jié)點(diǎn)上.

基于k-高頻詞主題相關(guān)搜索路由算法具體描述如下:

①hop=1;;

②搜索請(qǐng)求發(fā)起節(jié)點(diǎn)用全文搜索方式,搜索本地資源,得到結(jié)果集RS;

③If(RS==null)

隨機(jī)從遠(yuǎn)程對(duì)等點(diǎn)表中選擇一個(gè)節(jié)點(diǎn),作為搜索請(qǐng)求轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn);

else

用HFT算法計(jì)算結(jié)果集Rs的k-高頻詞向量dsf;

Foreach(對(duì)等點(diǎn)表in遠(yuǎn)程主題)

{

計(jì)算每項(xiàng)的k-高頻詞向量與dsf之間的距離;

}

選擇以上距離中最小的hop平方個(gè)節(jié)點(diǎn)作為搜索請(qǐng)求轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn);

把搜索請(qǐng)求的TTL減1:

Hop++;

向所有下一跳節(jié)點(diǎn)轉(zhuǎn)發(fā)請(qǐng)求;

④收到搜索請(qǐng)求的節(jié)點(diǎn)用全文搜索方式搜索本地資源,得到結(jié)果集RS;

If(ttl==0)結(jié)束算法;

else

goto第③步;

⑤算法結(jié)束.

算法以本地全文搜索開始,如果本地有相關(guān)資源,則分析相關(guān)資源的主題,作為搜索請(qǐng)求發(fā)送的依據(jù),如果沒有相關(guān)資源,則隨機(jī)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn).

算法根據(jù)主題的相關(guān)性來決定轉(zhuǎn)發(fā)的節(jié)點(diǎn),因而能夠把搜索請(qǐng)求導(dǎo)航到最可能擁有相關(guān)資源的節(jié)點(diǎn)上.

3 改進(jìn)的dual-chord模型設(shè)想

3.1 基于dual-chord資源定位模型的構(gòu)建

基于Chord模型的改進(jìn)模型有許多,例如:唐輝等提出了一種混合的P2P網(wǎng)絡(luò)模型HMPN(Hybrid Model based P2P Ne twork)[3];陳東峰、彭小延等提出了一種利用拓?fù)湎嚓P(guān)路由算法和超級(jí)節(jié)點(diǎn)的Chord系統(tǒng)TaChord[4].HMPN模型分為兩層,主干網(wǎng)使用DHT結(jié)構(gòu)化模型Chord,子網(wǎng)使用Napster或著Gnutella.這種設(shè)計(jì)是利用分層混合建網(wǎng)的機(jī)制,解決了部分資源本地化的問題,但在其子網(wǎng)中還是使用Gnutella或者Napster等模型,這種P2P網(wǎng)絡(luò),仍會(huì)在子網(wǎng)中出現(xiàn)單點(diǎn)失效、泛洪(Gnutella)等問題.而TaChord同時(shí)使用了Finger Table、Routing Table、Local Node List及超級(jí)節(jié)點(diǎn)使用緩存策略,和chord相比來說,路由性能是有了較大提高,但它的路由代價(jià)卻很高,在這個(gè)系統(tǒng)中同時(shí)要維護(hù)三張不同的鄰居表,每個(gè)超級(jí)節(jié)點(diǎn)負(fù)荷太重,成為網(wǎng)絡(luò)瓶頸.

許多異構(gòu)Chord模型較Chord模型有了許多改進(jìn),但每種模型仍有些不足,我們提出了一種基于Dual-Chord資源定位模型.該模型分為兩層,主網(wǎng)層和子網(wǎng)層,主網(wǎng)層就是我們的互聯(lián)網(wǎng),由超級(jí)節(jié)點(diǎn)(SuperNode)和管理節(jié)點(diǎn)(ManagePeer)組成,采用的是k-高頻詞主題相關(guān)性搜索路由算法來進(jìn)行資源的定位和發(fā)布;而子網(wǎng)層是根據(jù)一定規(guī)則(如IP地址,興趣域等)組成的,由超級(jí)節(jié)點(diǎn)(SuperNode)、備份節(jié)點(diǎn)(BackupNode)和普通節(jié)點(diǎn)(Norma lNode)組成,使用雙向Chord查找策略進(jìn)行資源定位和發(fā)布.在Dual-Chord中,搜索資源被哈希成一個(gè)64位的關(guān)鍵值,關(guān)鍵值的低32位表示對(duì)象索引所在的節(jié)點(diǎn)的位置,高32位用來表示對(duì)象索引(存儲(chǔ)實(shí)際對(duì)象的指針)所在的子網(wǎng)位置.進(jìn)行資源搜索時(shí),子網(wǎng)節(jié)點(diǎn)采用基于Chord雙向查找策略利用后繼和前驅(qū)節(jié)點(diǎn)路由信息,并且同時(shí)從逆時(shí)針和順時(shí)針兩個(gè)方向去查詢,如果匹配請(qǐng)求,直接將匹配消息轉(zhuǎn)發(fā)到目的節(jié)點(diǎn),完成搜索;否則發(fā)送搜索請(qǐng)求給本子網(wǎng)的超級(jí)節(jié)點(diǎn),要求到外網(wǎng)去進(jìn)一步搜索.超級(jí)節(jié)點(diǎn)利用關(guān)鍵值中的高32位,把消息路由到負(fù)責(zé)該高32位鍵值的超級(jí)節(jié)點(diǎn).接著在主網(wǎng)層中,首先要在本地資源中進(jìn)行全文搜索,并計(jì)算搜索結(jié)果集的k-高頻詞向量,然后以此向量作為搜索請(qǐng)求的主題,再根據(jù)主題來確定是否要向下一節(jié)點(diǎn)發(fā)出路由請(qǐng)求.如果索引記錄匹配,立刻向原查詢節(jié)點(diǎn)返回結(jié)果,否則返回失敗消息.

這種基于Dual-Chord資源定位模型,將IP地址接近的節(jié)點(diǎn)或有某些共性的節(jié)點(diǎn)分在同一個(gè)子網(wǎng)中,資源定位時(shí)在同一個(gè)子網(wǎng)內(nèi)搜索的概率較大,這樣可以減少資源定位的時(shí)間.下面我們就將具體來介紹本文提出的基于Dual-Chord資源定位模型.

3.2 dual-chord資源定位模型結(jié)構(gòu)

3.2.1 系統(tǒng)模型結(jié)構(gòu)圖

Dual-Chord的雙層P2P資源定位系統(tǒng),如圖4所示.系統(tǒng)一共分為兩層(如3.1節(jié)所介紹),其中下層子網(wǎng)的劃分主要是依據(jù)節(jié)點(diǎn)的物理位置(IP地址),把物理地址接近的節(jié)點(diǎn)分為一組.

圖4 Dual-Chord的雙層P2P資源定位系統(tǒng)

3.2.2 dual-chord資源定位模型

為了更好地對(duì)本章前面所介紹的資源定位過程加以理解,下面舉例說明一個(gè)用戶從發(fā)出查詢到收獲結(jié)果的整個(gè)過程,如圖5所示.

圖5 Dual-Chord模型資源定位圖

第一步,當(dāng)子網(wǎng)中有用戶節(jié)點(diǎn)A發(fā)出查詢請(qǐng)求,首先利用前面介紹的雙向查詢算法在本地子網(wǎng)內(nèi)進(jìn)行雙向搜索即順時(shí)針和逆時(shí)針方向同時(shí)搜索.若查詢失敗,則將普通節(jié)點(diǎn)A所要的資源信息發(fā)送給A所在子網(wǎng)的超級(jí)節(jié)點(diǎn)SN1.

第二步,超級(jí)節(jié)點(diǎn)SN1收到請(qǐng)求后,將收到的查詢信息利用前面所介紹的k-高頻詞主題搜索算法向主網(wǎng)中的其它節(jié)點(diǎn)發(fā)出搜索請(qǐng)求.

第三步,請(qǐng)求以節(jié)點(diǎn)搜索結(jié)果集的主題作為搜索請(qǐng)求的主題,計(jì)算距離,然后再根據(jù)距離排序,把請(qǐng)求路由到最小距離的節(jié)點(diǎn)上,即到目標(biāo)超級(jí)節(jié)點(diǎn)SN2,SN2查詢自己的索引記錄列表,搜索與目標(biāo)節(jié)點(diǎn)匹配的索引記錄,發(fā)送應(yīng)答消息給源子網(wǎng)的超級(jí)節(jié)點(diǎn)SN1.

第四步,超級(jí)節(jié)點(diǎn)SN2將搜索結(jié)果返回給源查詢節(jié)點(diǎn)A,同時(shí)將k-高頻詞向量記錄到SN2所對(duì)應(yīng)的本地主題對(duì)照表中.

第五步,A節(jié)點(diǎn)根據(jù)返回的結(jié)果消息得知所要的資源所在的節(jié)點(diǎn)B上,立即和B建立連接,到B節(jié)點(diǎn)處下載資源.

4 結(jié)論

本文在Dual-Chord模型上結(jié)合雙向查詢Chord算法和k-高頻詞搜索路由算法,提出了一種基于Dual-Chord的資源定位模型.理論上得出使用該模型的用戶可以實(shí)現(xiàn)較高的資源查詢效率、實(shí)現(xiàn)子網(wǎng)資源的高度本地化等.但這種模型同時(shí)還存在著許多如前所述的不足,將是今后進(jìn)一步研究的方向.

[1]劉金山,盧顯良.基于DHT的P2P搜索引擎的研究——一種Chord改進(jìn)算法[D].北京:電子科技大學(xué),2008.

[2]徐傳運(yùn),楊丹.基于主題相關(guān)的P2P全文搜索引擎的研究[D].重慶:重慶大學(xué),2006.

[3]唐輝,張國(guó)杰,黃建華等一種混合P2P網(wǎng)絡(luò)模型研究與設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用,2005,25(3):521-521,535.

[4]Chen Dongfeng,Yang Shoubao,Peng Xiaoyan.TaChord:a Chord system using topology-aware routing and super pees [J].in Journal of Southeast University,2004,20(3):15-20.

The Study of Resource Locating Technology Based on Dual-ChordModel

ZHENG Yi-fang

(College of the People’sAr my,Fujian Nor malUniversity,Fuzhou Fujian 350007,China)

To effectively locate resources,Dual-Chordmodel has been put for ward.In themodel the ne twork is divided into the principal ne twork and subnet.The latter uses bidirectional inquiry Chord algorithm,and the former uses the k-high frequencyword search routing algorithm.Theoretcally,it is obtained that users of thismodel can realize highly effective recall,accurate ratio and high localization of resources.

P2P;Dual-Chord model;network resources;resource location

book=9,ebook=399

TP 393.02

A

1673-2103(2010)05-0039-05

2010-08-06

鄭藝芳(1978-),女,福建莆田人,講師,碩士,研究方向:計(jì)算機(jī)應(yīng)用技術(shù).