基于Ｈｙｐｅｒｃｕｂｅ模型的Ｐ２Ｐ路由算法的改进

汤景云　张永平

摘要：基于Hypercube模型的P2P资源搜索策略和路由策略，是以单纯广播方式进行的，搜索和路由效率比较低.因此提出了“一跳复制”技术以及改进算法RA1，提高了搜索和路由的效率，同时增强了P2P网络的效率和健壮性。

关键词：一跳复制； RA1算法；路由表

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)18-2pppp-0c

Improvement of P2P Routing Algorithm Based on Hypercube Model

TANG Jing-yun,ZHANG Yong-ping

(Department of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221008,China)

Abstract:The P2P resource searching and routing strategy based on Hypercube Model depend the pure broadcast way,and are very inefficient.So, an "one-hop replication " technology and RA1 algorithmare adopt in this thesis which would enhance the efficiency of searching and routing, and also increase the efficiency and haleness of P2P-based network.

Key words:one-hop replication;RA1 algorithm;Table of routing

1 引言

对等网络（P2P）技术是最近研究的热点技术之一，它是分布式系统和计算机网络相结合的产物。与传统的基于C/S 方式的Internet相比，P2P采用一种既不排斥，也不固有的依赖中心控制节点的、基于网络的计算方式，它最大的特点是网络资源不再集中存放于服务器，而是分布于边缘计算机中，具有较好的扩展性、容错性、自主性。

在P2P网络中，其基本问题就是网络路由问题。现有的P2P路由算法假设网络中所有的节点的带宽、存储能力以及处理能力等属性都是相等的。而实际的网络中情况并非如此,P2P网络存在着极大的节点异构性，用户之间在带宽、处理能力、存储容量、NAT访问方式等方面存在着很大的差异性。一部分节点拥有较强的处理能力和较大的带宽，而部分节点的能力却很有限。

首先对P2P网络中的重要概念进行定义：

P2P系统中的一台主机称为一个节点。如果两个节点互知对方的IP地址，则称在这两个节点之间存在一个连接。延迟是指，一次通信过程中，消息从源节点到目标节点所经过的连接数，用跳数(hop)来描述。为了实现P2P网络，每个节点上需要保存一个与其有连接关系的节点的IP地址列表，称为邻居列表。同时，为了支持通信，每个节点还需要保存一个建立在IP地址列表基础上的消息转发目标表，称为路由表。

一个好的P2P路由算法必须具备如下几个特点：

(1)高可扩展性：每个节点的邻居节点IP列表要小。

(2)高效：消息传递平均延迟要小。

(3)高可用性：每两个节点之间的不同通讯路径要多。

接下来介绍基于Hypercube 超立方体模型的路由算法以及改进算法。

2 基于Hypercube 超立方体模型的路由算法描述

基于Hypercube协议的P2P网络将节点组织成确定、对称的图形拓扑结构。该协议根据筛选算法和域分组策略把加入网络中的节点分成两类：超级节点（SuperNode，SN）和普通节点(OrdianryNode,ON)；一个SN管理若干个ON。ON与SN通过星型拓扑连接起来。SN间则形成HyperCube超立方体结构。下面是一个维数d=3时的结构，如图1所示。

图1 d=3 的超立方体

该协议构造出的模型使每个SN都可以看成由所有SN组成的生成树的根节点。由这个节点出发可以遍历整个树。考虑到模型中SN的拓扑结构比较简单，广播方式可以高效率地完成查询工作，所以Hypercube 模型的消息路由策略是利用单纯广播方式进行的。如节点0 要搜索资源，利用广播的形式，把搜索请求发给它的所有邻居节点（NeighborNode,NN）1、2、4。这些节点收到请求后首先查看本节点上否是有目标资源，如果有则发布回应；如果没有则检查TTL（Time To Live，生存时间），如果不超时，则继续将请求发给自己的NN。

3 算法的改进

3.1 利用“一跳复制”策略提高消息路由效率

现有模型是通过广播方式完成搜索的。当多个节点同时发送查询请求和要求消息路由时，会导致传输效率变低，甚至使网络不可用。要解决的问题是：搜索和路由时要尽可能减少消息的传递次数，平均消息延迟要小，即跳数要小。

3.1.1“一跳复制”策略描述

每个SN 动态地维护其NN所拥有数据的索引（包括NN本身以及所管理的ON的数据），通过这样的索引可以提高查询速度。因为每个数据的索引被“复制”到了离自己“一跳”的邻居中，所以称为“一跳复制”策略。如图1，节点0存有节点 1、2、4 的数据索引，；同理，节点1、2、4 上也存有节点0的数据索引。

3.1.2 改进前后效率对比

改进后，通过“一跳复制”,节点0 要得到节点7 上的数据，搜索结果实际需要的查询请求是9 条，经过2 跳，同时将会得到6 条不同的搜索路径。

而改进前，不进行“一跳复制”，节点0 则要经过3 跳才能得到搜索结果，同时由于搜索是通过广播来实现的，且消息在传输过程中的不同步性，这样实际需要的查询请求就是15 条，可以得到3 条不同的搜索路径。

通过对比两组数据可以得出，利用“一跳复制”策略可以很好地减少跳数从而缩短查询时间,降低网络负载量，有效地提高了网络带宽的利用率。

3.2 建立查询路由表提高网络效率

现有很多协议为了提高资源搜索的速度，在节点上建立了基于关键字或资源描述框架的语义索引。随之而来的问题是怎样快速而且准确地在源节点和目的节点之间进行消息传输。要求是：每两个非直连节点间的可达通信路径要多，同时保证这些是最优路径。

3.2.1 改进的路由算法RA1

为了解决以上问题， 我们提出了改进的路由算法RA1。

(1)普通节点将搜索请求qid发送给自己的超级节点(源节点)，超级节点收到搜索请求，查询本节点上是否存在请求的资源。由“一跳复制”策略可知，此超级节点上会存储有本身和其邻居节点的资源索引。所以此查询可确定n＋1 个(n 是维数)超级节点上是否有请求资源。有则直接将有效路由加入路由表中。

(2)查询源节点的邻居列表，统计邻居节点(n 个)，生成n 张预备路由表。设置预备路由表的属性：邻居节点为当前节点，设置邻居节点号为子查询id 号。将预备路由表分别发送给相应的邻居节点。

(3)邻居节点收到预备路由表后，按照表中资源请求搜索本节点。搜索范围涉及到n个超级节点（本节点及n个邻居节点，除去源节点）。若有请求资源，则将有效路由保存并计算查询时间。检查TTL，决定是否继续向前搜索。

(4)得到当前节点的向前邻居节点，分别对其提出查询请求。若得到有效路由，则保存。更新预备路由表。

(5)检查搜索的深度是否已经达到了TTL 的限制。如果达到了TTL的限制则停止搜索，将得到的预备路由表中有效路由进行反相路由，复制到源节点的路由表中。否则分别将邻居节点作为当前节点，调用(4)过程，向深一层搜索。

(6)搜索完毕，删除预备路由表。

例如，在上面的搜索过程中，0号超级节点发出搜索某资源请求， 算法生成3 张预备路由表： Table(0---1) ， Table(0---2)，Table(0---4)。其上没有要求的资源，循环依次得到当前节点的邻居，修改当前节点，并不断更新预备路由表， 1---3，1---5；2---3，2---6；4---5，4---6；经过2 跳就得到了结果。得到以下关系：

r(s,d)=h (s,n) + rs(n,d)

其中：s 代表源节点，n 代表源节点的邻居，也是第一个当前节点，d 代表目标节点，h (s,n)代表直连可得，rs (n,d)表示递归得到剩余的路径信息。

如果搜索的资源就在邻居上，则通过r=h (s,n) 能够表示出这条路由是直连，否则通过得到邻居节点作为当前节点递归调用生成算法。如上搜索过程可以得到路由消息索引为： r=h ( 0,1 )+( 1,3 )+(3,7 ) ；r=h (0,4 )+( 4,5 )+(5,7)等。

3.2.2 算法说明

RA1算法说明：

(1)路径优先级确定机制

通过RA1算法生成查询路由表，一般有多于一条的路由信息。那么这几条路经的优先级如何来确定呢，本文提出了以下的优先级确定机制。

(1)每一个节点都认为它的邻居是优先级最高的；

(2)在1）的基础上再依据节点收到消息回应的速度来确定优先级。消息回应速度快的路径优先级高，反之，消息回应速度低的路径优先级低。

例如：节点0发出一个查询请求，如果在节点2 和节点3上都有它所请求的资源，因为节点2是节点0的邻居，所以路由r=h( 0 , 2)的优先级就比r=h (0,2 )+h( 2,3) 高，前一条路经应该被优先选择。如果是节点3和5上的资源，则依据消息查询回应的速度来决定。

根据以上的路径优先级机制，搜索得到的有效路由就可以按照优先级的顺序排列在查询路由表中。

(2)搜索深度限制（TTL）

经过一次搜索能够得到的有效路由的条数与搜索深度有关。RA1算法规定在搜索时，给定一个参数，由用户来选择搜索深度，模型中用TTL 进行度量。搜索深度越大，得到路由的数量也越大，但是需要更长的搜索时间。我们将指定一个默认值以满足不同用户的需要。

(3)路由环路的问题

该模型可能存在路由环路的问题。如7-3-2-6-7 就是一个路由回路，形成回路的原因是超级节点2只知道查询请求是3 发出来的，并不知道6 是否已经接收过查询请求，所以会将查询请求发送给它，同样6 也只知道是2 委托它查询，同样会将请求发送给7，这就形成了回路。

解决的方法：当每一个查询请求开始，分配一个唯一的查询qid,每个节点检查自己的预备路由表，是否已经接收过此请求。接收请求的超级节点会自动检查以前是否接收过此查询qid，若接收过则拒绝请求。

(4)查询率统计策略

每个节点的存储空间有限。随着时间的推移，节点维护的查询路由表将会很大。在查询时对重复查询率进行统计，将那些经常用的查询结果放在查询路由表的开头，这样能够提高查询速度。同时限制查询路由表的大小M，超过M时，自动从表最后一条记录开始删除。

3.2.3 改进后算法分析

(1)通过改进的RA1算法，节点在进行资源查找的同时保存了路由信息，在确定资源所在位置的同时也确定了消息传输的最优路径。而前者部分工作是路由器来承担的，但是，基于HyperCube 模型的相对简单的拓扑结构使人们可以将这部分工作放到每个节点上完成。这将大大提高网络的效率，基本上可以节省消息路由的时间。

(2) 通过RA1 算法生成的路由表建立了源节点与目标节点间的快速通道，同时保证两个节点间有多条可达路径，并且按照优先级排列，当一条或几条路径不可达时，仍然可以保证消息传输的可靠性。同时这几条路由都是最优化的路由方式。相反的，如果没有路由信息引导，则靠硬路由器，将带来许多的重复工作，也不可能在短时间内保证有多条路径供选择。

4 结束语

本文探讨了基于HyperCube 模型的P2P路由算法，对原有的搜索和路由机制进行了一些改进和完善。这种设计的最大优点在于提高了网络的效率，利用“一跳复制”机制来解决网络工作时大量消息传输对网络带宽的占用，同时在此基础上的RA1算法增强了网络的安全性和健壮性。

参考文献：

[1]Schlosser M,Sintek M,Decker S.HyperCuP —— Hypercubes,Ontologies and Efficient Search on P2P Networks[Z].Computer Science Department,Stanford University,2002-07.

[2]Wolpers M, Siberski W, Schmitz C.Super-peer-based Routing Strategies for RDF-based Peer-to-peer Networks[Z].Germany Computation and Information Structures Institute,Technical University Berlin,Germany,2003.

[3]庄明,董健全.基于P2P的路由选择技术的研究[Z].计算机工程,2006,03.

[4]杨斌,孟波.P2P经典路由算法的改进[Z].计算机工程与设计,2004,02.

[5]孙珊珊.P2P网络路由算法的研究及Chord协议算法的改进[D].工学硕士,吉林大学,2007.

[6]McIlraith S,Son T C,Zeng H.Semantic Web Services[J].IEEE Intelligent Systems,2002,16(2 (Special Issue on the Semantic Web)):46-53.

收稿日期：2008-03-11

作者简介：汤景云（1984-），女，江西高安人，中国矿业大学计算机科学与技术学院硕士研究生，研究方向：计算机网络，信息安全；张永平（1958-），男，辽宁东沟人，中国矿业大学计算机科学与技术学院硕士生导师，副教授，研究方向：计算机网络，信息安全。