基于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-),女,福建莆田人,讲师,硕士,研究方向:计算机应用技术.