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

鄭藝芳

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

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

鄭藝芳

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

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

P2P;Dual-Chord模型;網絡資源;資源定位

1 P2P簡介

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

P2P是一種技術,但更多的是一種思想,有著改變整個互聯網基礎的潛能的思想.當前,學術界對P2P有著許多不同的定義,各種不同的定義看起來都有一些差別,但本質上都不矛盾.P2P中的P指的是peer,peer的意思是“(地位、能力等)同等者”、“伙伴”等意思.因此,P2P可以解釋為“伙伴對伙伴”或者“端對端”等意思,更通俗的稱法就是“對等網絡”.

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

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

圖1 C/S模式的網絡結構

圖2 P2P模式的網絡結構

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

2 P2P網絡資源定位技術

2.1 雙向查詢Chord引用[1]

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

雙向查詢系統的主要算法思想是:Chord環上的任意兩個節點之間的邊可以看作是一條路由,它代表疊加層上的一個連接.假設環上存在兩個節點,并且X和Y之間的距離是2的i次方,則X和Y之間的路由可以定義為這里是m標識符的二進制表示位,并且0≤i

圖3 Chord查詢模型

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

在主網中,我們利用k-高頻詞搜索算法來實現資源定位.下面是對k-高頻詞搜索算法的介紹.

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

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

①hop=1;;

②搜索請求發起節點用全文搜索方式,搜索本地資源,得到結果集RS;

③If(RS==null)

隨機從遠程對等點表中選擇一個節點,作為搜索請求轉發的下一跳節點;

else

用HFT算法計算結果集Rs的k-高頻詞向量dsf;

Foreach(對等點表in遠程主題)

{

計算每項的k-高頻詞向量與dsf之間的距離;

}

選擇以上距離中最小的hop平方個節點作為搜索請求轉發的下一跳節點;

把搜索請求的TTL減1:

Hop++;

向所有下一跳節點轉發請求;

④收到搜索請求的節點用全文搜索方式搜索本地資源,得到結果集RS;

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

else

goto第③步;

⑤算法結束.

算法以本地全文搜索開始,如果本地有相關資源,則分析相關資源的主題,作為搜索請求發送的依據,如果沒有相關資源,則隨機選擇下一跳轉發節點.

算法根據主題的相關性來決定轉發的節點,因而能夠把搜索請求導航到最可能擁有相關資源的節點上.

3 改進的dual-chord模型設想

3.1 基于dual-chord資源定位模型的構建

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

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

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

3.2 dual-chord資源定位模型結構

3.2.1 系統模型結構圖

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

圖4 Dual-Chord的雙層P2P資源定位系統

3.2.2 dual-chord資源定位模型

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

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

第一步,當子網中有用戶節點A發出查詢請求,首先利用前面介紹的雙向查詢算法在本地子網內進行雙向搜索即順時針和逆時針方向同時搜索.若查詢失敗,則將普通節點A所要的資源信息發送給A所在子網的超級節點SN1.

第二步,超級節點SN1收到請求后,將收到的查詢信息利用前面所介紹的k-高頻詞主題搜索算法向主網中的其它節點發出搜索請求.

第三步,請求以節點搜索結果集的主題作為搜索請求的主題,計算距離,然后再根據距離排序,把請求路由到最小距離的節點上,即到目標超級節點SN2,SN2查詢自己的索引記錄列表,搜索與目標節點匹配的索引記錄,發送應答消息給源子網的超級節點SN1.

第四步,超級節點SN2將搜索結果返回給源查詢節點A,同時將k-高頻詞向量記錄到SN2所對應的本地主題對照表中.

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

4 結論

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

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

[2]徐傳運,楊丹.基于主題相關的P2P全文搜索引擎的研究[D].重慶:重慶大學,2006.

[3]唐輝,張國杰,黃建華等一種混合P2P網絡模型研究與設計[J].計算機應用,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-),女,福建莆田人,講師,碩士,研究方向:計算機應用技術.