保证服务质量的P2P目标节点路由算法

陈园园 张利红

摘 要：在深入研究P2P覆盖网拓扑生成方法的基础上，结合P2P流媒体点播服务的实际情况，设计了一种基于超级节点的目标节点路由算法。该算法比一般的P2P路由算法速度更快，通常只需2至3跳路由查询即可定位到资源节点。

关键词：P2P；服务质量；路由算法

中图分类号：TP393 文献标识码：A 文章编号：2095-2163（2015）05-

Target Node Routing Algorithm in P2P based on the Quality of Service

CHEN Yuanyuan， ZHANG Lihong

（School of Physics and Electromechnical Engineering，Zhoukou Normal University， Zhoukou Henan 466001， China）

Abstract： On the basis of in-depth study of P2P overlay network topology generation method， combined with the P2P streaming media on-demand services to the actual situation， the paper presents the design of the destination node routing algorithm based on super nodes. The algorithm than the average P2P routing algorithm is faster， which usually only 2-3 hop routing queries could locate the resource nodes.

Keywords： P2P； QOS； Routing Algorithm

1 路由查询机制

P2P（Peer-to-Peer）网络中提供节点定位[1]的方式主要有两种：（1）基于服务器目录。在此定位方法中，目录存放在服务器上，用其记录着网络中所有节点的索引信息和资源分布情况，而某个节点需要搜索资源数据块时，只需查找服务器目录即可定位到资源节点。但是这种方式却通常易使服务器成为整个系统的瓶颈；（2）基于DHT。DHT全称叫分布式哈希表（Distributed Hash Table），这种定位方式是通过将网络中的节点组织到一个结构化的P2P网络中，每个节点都存储着一部分的目录信息。由此就构成了一个目录的完整性备份，当节点中目录内容变化较小的时候，基于DHT方式的路由查询是高效、完备的。

本文在上述两种节点资源定位算法的基础上设计了保证QoS的定位算法——QoSVoD，这一算法的主要思想是将P2P流媒体点播网络中的超级节点作为一个小型的临时目录服务器，超级节点将记录本簇中普通节点的数据块位图信息，同时在超级节点的帮助下，目标节点的快速准确定位也随即获得实现。

在描述本文的路由查询机制前，先给出如下3个定义。

定义1： 请求节点。是指网络中需要某个数据块，向其他节点发出资源请求的节点。

定义2：资源节点。是指网络中拥有请求节点所需数据块的节点。

定义3：目的节点。请求节点发出一个资源请求后，网络中通常会有多个资源节点满足请求节点的需求，其中最优的资源节点称为目的节点。

节点的路由查询机制主要根据当前时刻点播同一个流媒体资源的节点所形成的簇规模不同而采取如下的两种办法。

（1）如果簇中节点的数目较少（如只有几百个），小于预先设定的阈值maxSize，超级节点维护簇中所有普通节点的资源位图信息。请求节点查询某个数据块时，首先向超级节点发起查询消息，超级节点在查询自己维护的节点资源位图，并定位到资源节点后，即由资源节点为请求节点提供服务。这种查询方式在 内就可以查询到资源节点。

（2）如果簇中的节点很多（比如上万个），即有很多节点同时点播某个流媒体资源，请求节点则需使用下面描述的VoDMeridian路由算法进行资源查找。

2 网络中节点距离预测度量

节点在簇内查找资源时，如果簇中的节点数很多，需要使用特定的路由算法进行查找。在此之前，首先需要度量簇内节点间的距离。但是P2P网络的高度动态性使得精准度量节点距离较为困难，因此，本文采用节点距离预测技术[2-3]来近似度量节点间的距离。常用的节点间距离预测技术可分为：非坐标距离预测方法和网络坐标计算方法两大类。对其给出基本概述如下。

非坐标距离预测方法是通过直接测量网络中部分节点的距离，再根据相应部分测得的距离信息来直接预测所有节点之间的距离信息，并不使用任何坐标计算的形式来实现预测。但却常常需要一些特殊节点（如DNS服务器等）协助完成。

网络坐标方法是通过一定的映射算法，将整个网络中节点映射到几何空间中，网络中的节点位置即以空间坐标来提供定义，而且网络中的节点与几何空间中的节点对应为一一映射，将可通过计算几何空间中的节点距离来反映实际网络中的真实距离。

本文在估计簇中节点间的距离时，根据P2P流媒体点播的实际情况，重点关注从多个资源节点中选取邻近的节点，而并非测量出具体的距离值。因此本文设计的解决方案是：构建了适用于P2P点播网络的节点距离预测算法，并利用此算法来优化节点的路由查询，再通过查询算法寻找到目标节点或目标节点集。

3 环点播查询路由算法

3.2.1 VoDMeridian环点播查询路由算法

在P2P点播系统模型中，每个节点都维护一个Meridian同心圆环结构的邻居节点列表。当某个簇中节点很多时，就使用VoDMeridian路由查找算法查找目标节点。这里，需将原物理网络拓扑节点映射为Meridian环状网络拓扑结构。

为此，涉及到一个核心问题，即如何选取映射关系，也就是物理网络中的节点按照何种规则对应到Meridian环状网络拓扑结构中。为了解决这一问题，本文给出如下定义。

定义4：节点间的播放距离

假设当前网络规模总数为N，集合 ，表示网络中点播同一部流媒体资源的m个节点的当前点播位置，节点i和节点j的播放距离本文定义为 。

在进行流媒体点播时，节点在数据传输中的滑动窗口大小是有相应限制的，假设最多一次能交换w个数据片，这就使得只有播放距离 在w以内的节点互相交换数据才具现实意义，即对当前的节点i，本文将满足 的节点加入到节点i维护的Meridian同心圆环结构中的数据交换环（第1层）中。以此类推，加入节点i第2层Meridian环的节点应该满足 ；加入节点i第K层Meridian环的节点就应该满足 。

物理节点映射到Meridian环状网络拓扑结构后，VoDMeridian环点播查询路由算法如下：

（1）请求节点A根据自己的播放位置确定所需的数据片；

（2）请求节点根据数据片，查找目的节点T。首先请求节点从Meridian环中找到最接近T的节点。如果最近接近的节点就是T，则查找成功；否则，跳转到（3）；

（3）最接近節点查找自己的Meridian环中最接近T的节点，以此类推；

（4）返回最终查找的最接近节点。如果最接近节点为T，查找成功；否则，查找失败。

3.2 距离预测模型

本文所设计的距离预测模型以子午线[4]（Meridian）节点选择机制为基础，将P2P覆盖网中的对等节点根据其相互间的距离关系组织在一个半径以指数增长的同心圆环结构中。具体来说，该模型主要包括3部分：同心圆环结构、圆环成员管理、节点路由查找机制。此后，将具体描述每一部分的机理实现模式。

3.2.1 同心圆环结构

网络中的每个节点A都维护着一个同心圆环结构，用以保存一定数量的节点信息。这个同心圆的半径是以指数增长，第 个环的内圆半径为 ，外圆半径为 ， 是一个常数，而 是一个指数增长因子。 表示最里面的圆环，本文称为数据交换环，节点A只能与这里面的节点进行数据交换。如果被测量的节点B与节点A的距离为 ，且满足 ，则将节点B添加到节点A的第 个圆环内。为了限制圆环数目，本文定义阈值 ，如果圆环个数 达到 ，则 。

3.2.2 圆环成员管理

为了有效控制每个圆环中节点的数量，每个圆环中最多能保存L个节点。L是查找准确度和维护节点开销的权衡值。如果L值越大，节点A越容易查找到资源节点，但维护其他节点的开销也相应越大；如果L值小，表示节点A维护其他节点的开销很小，但却随之增加了查找到目标节点的路由跳数。

同心圆环中目的节点的查找过程：

（1）请求节点A从每个圆环中随机取出一个节点，向这些节点发出查询目标节点T消息；

（2）节点收到A的消息后，在自己维护的同心圆环中查询，测量自己与目标节点T的距离，并对自己维护圆环中的节点进行路由转发查询，直至找到目标节点T为止；

（3）请求节点A接受返回的目标节点T。

以查询到目标节点T 为例，普通节点向某个圆环中的节点A 发起查询请求。节点A首先判断自己到T的距离d，然后探测其在 范围的环成员节点，并将该查询转发至这些环成员节点中距离T最近的节点B。节点B 重复这一查询过程，直至转发到某个节点后无法再找到更近节点为止。最后查找到的节点即为目标节点T。此处 。由于Meridian覆盖网络圆环半径以指数增长，因此，这种迭代查询算法即会以指数速度 接近目标节点。

4 实验仿真及结果分析

为了验证路由查找算法的性能，本文将QoSVoD模型与经典的Kad模型[5]进行仿真比较。Kad是一种已经应用到实际网络中的高效路由查找算法，可通过对网络节点ID值的异或计算来度量节点间的距离。仿真实验室中，QoSVoD模型与Kad模型比较如下性能指标数据：

（1）查找成功率。节点发出查询，最后成功收到正确回复的统计数据。

（2）平均路由跳数。请求节点查询到目标节点中间经过的路由转发次数。

（3）平均时延。节点发出查询消息直至接收到回复消息之间的时间间隔。

图1、2、3反映了QoSVoD模型与Kad模型在查找成功率，平均路由跳数，节点间的查找时延等方面的性能比较结果。在此，可做如下分析。

（1） 节点查找成功率

查找成功率是统计节点发出查询后成功收到正确的回复的统计数据，查找成功率越高，说明模型越有效。从图1可以观察出，虽然节点的扰动现象使两种模型的查找成功率均发生上下波动，但QoSVoD模型的查找成功率却一直比Kad算法呈现更高态势。这主要是因为当QoSVoD模型中的节点通过路由算法查找不到目的节点时，流媒体服务器可向其提供流媒体服务，从而保证了请求稀有资源的节点的服务质量。

图1 节点的查找成功率

Fig.1 Lookup success rate of node

（2）平均路由查找跳数

图2反映了当网络规模变化时，Kad和QoSVoD路由查询算法的平均查找跳数的变化情况。路由查找跳数是反映节点查找效率的统计数据，平均查找跳数越少，说明模型查找效率越高。从图2可以观察出，QoSVoD模型中路由查询算法的查找效率比Kad要明显偏高，Kad网络中节点的平均路由查询跳数随网络规模的增加而增加，而QoSVoD模型中节点的查询跳数相对稳定。这是因为QoSVoD模型中存在超级节点，当点播某资源的节点簇中成员较少时，超级节点能直接为其他普通节点提供查询定位服务。当簇中节点较多的时候，请求节点可在簇内使用VoDMeridian算法进行定位查询，查询效率也可达到 。

图2 平均查找路由跳数

Fig.2 Find average routing hops

（3） 查找延迟

图3反映了Kad和QoSVoD模型路由查找算法的查询时间延迟的对比情况。查询时延主要统计节点发出查询消息到接收到回复之间的时间间隔。从图3可以观察到，QoSVoD网络中节点的查询时延稳定在200ms左右，总体上比Kad小，这是因为通过节点所维护的环状路由表，节点搜索当前点播位置的临近资源时速度更快，从而减小了查询时延。

图3 查询的时间延迟

Fig.3 Query time delay

5 结束语

通过对影响P2P流媒体点播QoS因素的分析，设计了保证服务质量的P2P模型中目标节点路由算法，与Kad模型在查找成功率，平均路由跳数，节点间的查找时延等方面的性能比较之后，可以看出该算法在保证服务质量的前提下有很好的定位效果。

参考文献：

[1] 刑长友，陈鸣.网络距离预测技术[J].软件学报，2009，20（6）：2470-2482.

[2] LEE S，ZHANG Z，SAHU S， et al. Fundamental effects of clustering on the euclidean embedding of Internet hosts[A]. Proc. of the IFIP Networking [C]. Berlin： Springer-Verlag， 2007. 890?901.

[3] 朱培栋，卢锡城，等.一种网络自组织演化的数学模型[J].软件学报，2007，18（12）：3071-3079.

[4] WU D， LIANG C， LIU Y， et al. View-upload decoupling： A redesign of multi-channel P2P Video Systems [A]. IEEE INFOCOM[C]. Rio de Janeiro： IEEE， 2009：2007-2018.

[5] 李杰.对等网络搭便车行为研究与激励机制的优化[D].苏州：苏州大学，2009：28-37.