P2P网络中自适应节点选择策略

王 城，陈兴蜀，杨邓奇，刘莉伟

（四川大学 计算机学院网络与可信计算研究所，四川 成都610065）

0 引 言

P2P系统中节点选择是影响系统服务性能的关键因素之一，实施一个好的节点选择策略对整个系统性能的提高尤为重要。之前的研究工作已使得系统的性能在很大程度上提高，节约了大量的网络带宽资源。文献 ［1］中X.Yang等人通过建立数学模型分析系统的服务性能，但是却忽略系统中文件分布的特性。文献 ［2－5］中提出了一种基于tracker端的邻居节点选择算法，考虑了节点地理位置的分布。文献 ［6］提出了基于速率的节点选择策略（TFT策略），采用阻塞算法（choking）中融入乐观不阻塞算法（optimistic－unchoking，OU）的策略，以10s为阻塞算法周期，选择4个上传速度较快的节点作为自己上传的对象，以30s为OU算法周期，随机的选择节点进行上传，这样能保证新加入节点获取文件块的机会，并且能更好的发现资源交互对象。但是这种节点选择策略存在两方面的不足：①虽然在tracker端实施邻居节点选择算法，但并未从本质上解决非tracker来源的节点，造成大量的跨网段、跨地域的带宽流量，浪费带宽资源。②传统的节点选择策略中，并不能根据具体网络状况，自调节节点选择策略，以灵活的节点选择策略充分适应网络环境，保障各节点高效的分发性能。

针对以上问题，本文设计并实现P2P系统中自适应的节点选择策略，该策略通过以邻近节点优先连接与基于上传带宽利用率的节点选择算法相结合，以实现P2P网络高效、自适应的节点选择。

1 自适应节点选择机制

本文是在基于以C＋＋为开发语言，开发的SecBT平台上进行的开发研究工作，以下简称自适应机制。

1.1 总体设计

自适应机制主要分为三大模块（如图1所示）：节点预处理模块、节点选择模块和自适应更新与维护模块。

图1 自适应节点选择机制框架

（1）节点预处理模块主要是处理收到的来自于Tracker、DHT、PEX的节点列表信息，包括节点过滤和邻近优先两个子模块。

节点过滤：在节点池1中查询节点列表，过滤IP、Port异常或者已建立连接的节点。

邻近优先：根据邻近优先算法，计算出各个节点与本节点的距离，并且优先连接距离本节点较近的节点。将建立连接的节点存放到节点池2。

（2）节点选择模块是负责从已经建立连接的节点中选择一部分节点与之进行数据交互，包括服务性节点选择模块、公平性节点选择模块、空闲带宽节点选择模块。

服务性节点选择：选择周期为10s，每个选择周期统计各节点为本节点提供的上传数据量，在上一个选择周期提供较多上传的节点，就是为本节点提供较多服务的节点，此类节点会被选作为上传对象（系统默认为4个节点）。

公平性节点选择：选择周期为30s，本节点从已建立连接的各节点中随机的选择一个节点为其提供上传，这样既保证了新加入网络没有任何数据的节点被选择的机会，也有利于了本节点发现更好的节点资源（系统默认为1个节点）。

空闲带宽节点选择：选择周期为10s，根据自适应更新阶段系统分配的上传连接数以及统计的空闲带宽队列，在本节点上传带宽利用率较低的情况下，选择具有较大空闲带宽的节点为其提供上传。

（3）自适应更新与维护。统计本节点上传带宽利用率，分配系统上传连接数，统计各节点空闲带宽。

1.2 邻近优先机制

为了选择较近的节点进行连接，首先需要探测本节点与各节点之间的邻近性，在P2P网络中，可以通过RTT（round－trip－time）值和路由跳数值反映两个节点的距离，但由于RTT值会根据当前网络拥塞程度而频繁的变化，在该机制中主要以路由跳数作为邻近节点选择标准。在搜索候选连接节点时采迭代加深搜索的思想：在迭代搜索中，每次迭代深度限制递增。当查询的节点数目满足要求或者已经达到最大的深度限制，迭代过程结束。在迭代过程中，随着深度的增加，节点个数迅速增长。因此，在最大深度限制的深度找到满意的结果和直接以最大深度进行搜索比较起来，节约大量资源消耗。邻近节点优先策略如图2所示。

图2 邻近节点优先策略

策略实施过程如下：

（1）计算本节点与节点池1中各个节点的距离dis＝［hop＿count，RTT］。并按hop＿count由小到大存入临时备选连接列表（当节点hop－count值相等时，对相同的节点按RTT值由小到大排序），初始化阈值threshold＝0。

（2）连接hop＿count在阈值范围内的节点（threshold＝0，表示优先搜索同网段内的节点）。如果连接成功则将此节点存放入节点池2。

（3）无论连接成功或者失败，删除临时备选连接列表中的此节点信息。

（4）系统扩大阈值threshold值，由近及远进行连接。跳至过程（2）、（3）。

1.3 节点选择机制

节点选择机制是在节点自适应更新阶段基于自身上传带宽利用率和对等节点的空闲带宽的情况触发的。当本节点带宽利用率较低，并且当前连接对等节点有空闲的带宽，那么系统分配上传连接数用于提供上传。

节点选择机制有描述如下：在节点选择阶段中，N＿all为系统总的上传连接数，由服务性选择的节点数目为N＿service，由公平性节点选择的节点数目为N＿fairness，由空闲带宽节点选择的节点数目为N＿free。

上传连接数分配：N＿all＝N＿service＋N＿fairness＋N＿free，在自适应节点选择机制中，系统默认N＿service＝4，N＿fairness＝1，N＿free＝0。系统总的上传连接数N＿all由自适应更新阶段自动分配。某时刻t时，可以定义上传带宽利用率utilization＿rate，上传字节量为upload＿byte；用户（系统分配上传字节量/s）为upload＿limit则utilization＿rate＝upload＿byte/upload＿limit；

当utilization＿rate值偏小时说明本节点的上传带宽利用率较低。系统自增加上传连接数N＿free，同时从统计的节点空闲带宽列表中选择节点为其提供上传。在节点选择更新方面，每10s更新一次，这样能保证当自身带宽利用率不高的情况下，每10s检测一次带宽利用率以及统计节点的空闲带宽，并将自增的上传连接数目用于上传给拥有较大空闲带宽的节点，达到充分利用带宽的目的。

2 实验与结果分析

2.1 邻近性距离测量

为了验证自适应节点选择机制中邻近优先模块的有效性，本实验对稳定连接阶段的节点进行了测量分析。在P2P网络中，两个节点的距离可以通过往返时延RTT和路由跳数Hop－count来测量，RTT为两节点网络时延，Hopcount为两节点路由跳数。利用基于tracert的方法可以获得到达其他节点的网络时延和路由跳数。发送端通过发送一个UDP包，tracert程序可以跟踪发射包整个的路由过程和计算网络时延。小数量的包可以产生一个较好的简单的网络预测，从而得到所需要到达节点的RTT和Hop－count。在Internet中，两节点的路由跳数一般低于30。

图3是从稳定连接阶段所连接节点中选择50个节点进行的测量分析，由图统计的RTT和Hop－count值，分析可得随着RTT值增加，Hop－count值也随之增加，但是并不成线性关系。可以得出在传统机制中由于对节点的连接都是随机的选择，所连接节点的RTT值主要分布于50ms—90ms、Hop－count值主要分布于13跳—27跳。在实施自适应机制中，RTT值主要分布于30ms—70ms，并且有一部分同网段的节点被发现的，路由跳数值主要分布于6跳—14跳。图4为平均往返时间随节点数目变化图。通过对比试验说明，自适应节点选择机制下本节点优先选择距离本节点较近的节点进行连接。

作为评价邻近优先模块的一个参考标准，平均网络时延较小的节点被认为距离本节点较近，在传统机制之中，对于节点连接存在着随机性，而在改进之后由于会优先连接距离本节点较近的节点，所以平均网络时延较小，但随着连接范围的扩大，逐渐会连接那些距离本节点较远的节点，因此随着节点规模的扩大，平均网络时延逐渐变大。同样的如图5所示，邻近优先机制中总是优先连接距离本节点较近的节点（同网段中若有节点，则优先连接同网段节点）。正如路由跳数反映的情况，距离本节点较近的节点拥有较小的路由跳数，但随着连接范围扩大，连接的节点距离越来越远，路由跳数成上升趋势。

图5 平均路由跳数随节点数目变化

2.2 上传带宽利用率

在以C＋＋实现的SecBT进行实验中，下载文件大小为588MB的文件，经过多次实验，传统机制中平均下载完成总耗时2006.1秒。自适应机制中平均下载完成总耗1871.3s。如图6所示，文件在整个下载过程上传带宽利用率曲线图。

图6 上传宽利用率随时间变化

传统节点选择机制中，上传带宽利用受网络中节点的加入和退出或者是对等节点被阻塞而导致上传带宽使用情况波动较大，并且平均带宽利用率仅为86.4%，文件平均完成总耗时2006.1s。

在自适应机制中，平均上传带宽利用率为93.7%，与传统节点选择机制相比提高了8.45%，完成文件下载平均总耗时为1871.3s，在下载总耗时方面较传统机制缩短了6.7%，当文件越大改进的效果越明显，这是因为由自适应机制选择的节点会弥补节点因退出、被阻塞情况而出现减少服务对象，从而保证在上传带宽的正常合理使用，同时自适应机制根据网络中节点的空闲下载带宽大小，选择节点提供服务，这样在提高自身上传带宽利用的同时能充分的利用网络中空闲的下载带宽，从整体上提高网络的下载性能以及文件分发的能力。

2.3 文件第一块下载影响

对于新加入的网络节点，由于自身没有数据块，不能为其他节点提供上传。因此新加入节点往往需要等待一定的时间，直到自己被其他节点选择作为上传对象。因此对新加入节点第一个文件分片下载有很大影响，在自适应机制中由于新加入节点具有较大的上传和下载带宽，因此自适应机制大大增加了新节点被选中的概率，使新节点较快的拥有数据块快速的进入稳定下载阶段，缩短了新加入网络的节点下载第一个文件分片的时间，也促进了整个系统的运行。第一块平均下载完成时间随机节点数目变化如图7所示。

图7 第一块平均下载完成时间随节点数目变化

2.4 BT系统文件分发效力

BT文件分发效力是衡量改进后节点选择机制对整个系统性能提高情况的主要标准。可以用某时间段内节点下载文件的完成度或者节点下载完成所需用时来评价。设t时刻网络中需要下载某共享文件M的节点为N个，标记为N1，N2…Ni，需要分发的文件大小一共有m个数据分片，每一个节点在下载过程中拥有的数据分片标记为X1，X2…Xi。则t时刻节点Ni的M 文件下载完成度可以表示为

系统的文件分发效力E可由整个系统的关于M 文件完成度即为来表示，得

图8对100个节点规模的下载情况进行了分析，分析其中t＝30mins时刻的情况，在下载进行30分钟时，传统机制中完成下载的节点数目是36个，由于36个节点已经拥有所有的分片即完成度D＝1，假设剩余的64个节点获得的数据分片数目为1—m－1片，即完成度在0到100%随机分布，则文件的分发效力，在自适应机制下，完成下载的节点数目为47个，文件分发效力，容易证明E2＞E1。

图8 节点完成数目随时间变化

图9 不同节点规模下节点平均下载完成时间

由图9可见，就下载完成时间而言，自适应机制较传统节点选择机制平均提高36.6%。平均缩短下载时间13.6分钟。

实验表明，自适应节点选择机制的实施对于文件在系统的分发有较好的促进作用，其文件分发效力明显优于传统机制。

2.5 系统公平性

在自适应节点选择机制中，由于系统在上传带宽利用率不高的情况下自增上传连接数选择并未向本节点提供上传的节点作为自己的上传对象，这对系统的公平性会产生一定影响。

对于公平性的评价，通过对该节点的分享率f所对应的随机变量ξ的标准差σ（ξ）进行分析 ，在有n个下载节点的系统中节点i的上传文件分片数，下载文件分片数，其分享率定义如下：同时有：σ（ξ）＝为系统的平均分享率。其中节点i作为单独的离散点存在，则p（fi）＝1/n，在整个系统中有总的上传分片书等于总的下载分片数，因此E（ξ）＝1，由此可得：代入统计数据可得传统机制中σ（ξ）＝0.57113，自适应机制中σ（ξ）＝0.570752，由此可见，自适应机制对系统公平性有较小的影响。这是由于在自适应机制被触发之后，在较短时间会恢复到稳定的 “4＋1”状态，对系统中的公平性影响比较小。

3 结束语

本文以P2P的主流应用BitTorrent为协议背景，结合节点选择的3个阶段：节点获取阶段、节点选择阶段、节点维护阶段的特点，考虑了除Tracker以外的DHT、PEX节点获取情况以及网络中各节点空闲带宽情况，从减少跨网段带宽资源浪费、提高节点带宽资源利用率出发。设计并实现了基于带宽利用的自适应节点选择机制，通过与传统节点选择机制的对比实验，验证了自适应机制的有效性和优越性。对于减少网络中不必要的流量浪费，使各节点带宽利用率有较大的改善，从而在整体使得P2P交互性能得以提高。

［1］YANG Xiangying，Gustavo de Veciana.Service capacity of peer to peer networks［C］.INFOCOM Twenty－third AnnualJoint Conference of the IEEE Computer and Communications Societies，2004.

［2］TANG Hong，ZHANG Yunlong.Scheme of BitTorrent traffic control ［J］.Journal of Computer Applications，2011，31（2）：304－307（in Chinese）. ［唐红，张云龙.Bittorrent流量控制方案 ［J］.计算机应用，2011，31（2）：304－307.］

［3］LIU Weidong.Enhancing tit－for－tat for incentive in BitTorrent networks ［J］.Peer－to－Peer Networks，2010，3（1）：27－35.

［4］CHEN Xingshu，LIN Dayun，WANG Wenxian.Research and implementation of intelligent selection mechanism in P2P ［J］.Journal of Computer Applications，2011，31（2）：293－297（in Chinese）.［陈兴蜀，林大云，王文贤.P2P节点智能选择机制的研究与实现 ［J］.计算机应用，2011，31（2）：293－297.］

［5］QiAO Zhiwei，XU Tingrong.Design and implementation of simulation platform for neighbor selection algorithm in BT system ［J］.Computer Engineering and Design，2010，31（12）：2914－2917（in Chinese）.［乔志伟，徐汀荣.BT邻居结点算法验证平台的设计与实现 ［J］.计算机工程与设计，2010，31（12）：2914－2917.］

［6］Ruchir B，CAN P，William C.Improving traffic locality in Bit－Torrent via biased neighbor selection ［C］.Lisboa，Portugal：26th IEEE International Conference on Distributed Computing Systems，2006：66－76.

［7］David Erman，Daniel Saavedra.Validating.BitTorrent models［J］.Telecommunication Systems，2008；39（2）：103－116.

［8］Thanasis G，Papaioannou，George D，et al.A mechanism that provides incentives for truthful feedback in peer－to－peer systems ［J］.Electronic Commerce Research，2010，10（3）：331－337.

［9］YU Jiadi.Research on key technique of BitTorrent－like peer－topeer file sharing system ［D］.Shanghai：Shanghai Jiaotong U－niversity，2007：82－85（in Chinese）.［俞嘉地.BitTorrent对等网文件共享系统关键技术研究 ［D］.上海：上海交通大学，2007：82－85.］

［10］LI Jin.On peer－to－peer（P2P）content delivery ［J］.Peer－to－Peer Networking and Applications，2008，1（1）：45－63.

［11］CHEN Zhide，ZHENG Jinhua，XU Li.Network service incentive mechanism based on competitive game ［J］.Communica－tions in Computer and Information Science，2009，60（1）：46－53.

［12］QIU Dongyu，SANG Weiqian，MA Zuhui.On the efficiency of peer－to－peer file sharing ［J］.Journal of Signal Processing Systems，2010，59（3）：347－353.

［13］QIU D，Srikant S.Modeling and performance analysis of BitTorrent－like peer－to－peer networks ［C］.Barcelona，Spain：Proc of IEEE INFOCOM，2006：524－529.

［14］TIAN Y，WU D，NG K W.Modeling analysis and improvement for BitTorrent－like file sharing networks ［C］.Barcelona，Spain：Proc of IEEE INFOCOM，2006：641－647.

［15］CHAN Ho－Leung，LAM Tak－Wah，Prudence W H Wong.Efficiency of data distribution in BitTorrent－like systems ［J］.Computer Science，2007，45（2）：378－388.