基于带宽估计的友邻选择算法

唐 红，朱辉云，胡 容，申海岑

(重庆邮电大学网络与计算研究中心，重庆 400065)

0 引言

近年来，基于P2P的各种网络应用越来越广泛，其中影响最大的应用是文件共享系统，以BitT－orrent，Gnutella，eDonkey，iMesh 等为代表。根据德国互联网调查机构ipoque发布的2008/2009互联网流量报告(internet traffic report)，BitTorrent(BT)仍然是最流行的文件传输协议，其流量大约占P2P流量的45～78%，占整个互联网流量的27～55%［1］。因此有效地提高BT协议的文件传输效率，对于提高网络服务性能、降低网络负载具有重要的现实意义。

目前，已经有很多研究关注于如何提高BT的性能，其中Peers的邻居选择策略是重要的研究问题之一。在现有的邻居选择策略的研究中，多数的研究认为非随机的邻居选择策略比随机的邻居选择策略要有效。前者要根据某一种优先策略来选择邻居进行连接和文件的传输，后者则是随机地从邻居表中选择邻居进行连接和文件的传输。在非随机选择邻居的研究中，文献［2－3］分别基于自治域(autonomous system，AS)信息和网络坐标对BT参与节点的邻居进行了有偏选择。文献［4－5］分别采用了基于内容分组和能力匹配的思想进行邻居选择。而文献［6］则将两者结合起来，将节点按内容分组，由节点上报的上传、下载的字节数计算出带宽能力，让能力匹配的节点成为邻居。虽然这些算法对BT的下载性能有不同程度的提高，但都需要一个中心节点或者是Tracker服务器的介入才能完成，对于目前越来越流行的无Tracker方式显得就不那么适用。

在BT系统中，由于一报还一报(tit for tat，TFT)机制的存在，将能力匹配的用户连到一起能够提高共享文件下载的效率。默认情况下，一个节点每隔一定的周期会选择4个提供最高下载速率的用户上传数据，并随机地选择1个用户作为优化非阻塞连接来测试其是否能提供更好的下载速率。当一个低带宽的用户连接到高带宽用户之后，这个用户很可能只能够在被其他用户作为优化非阻塞连接时才能够获得一定的文件片，但由于不能够提供相匹配的文件交换速率，该用户将很快又被阻塞。如果将各用户按照相似的能力进行分组，他们就能够彼此连续地交换数据。反之，很多情况下只能够等待被其他用户随机地选中为优化非阻塞连接。因此，将带宽匹配的用户优先连接能够提高BT系统的下载速度［5］。

选择带宽匹配的邻居节点的基础是要知道邻居节点的上传带宽。常用的带宽估计算法主要有可变包大小(variable packet size，VPS)，包对/包列分散法(packet pair/train dispersion，PPTD)，自行载入周期流(self－loading periodic streams，sLoPs)和包对序列法(trains of packet pairs，ToPP)等 4 类［7］;VPS［8－9］算法主要是用于估计在一条路径上所有节点的处理能力。VPS算法通过收到的Internet控制消息协议(internet controlmessage protocol，ICMP)包中的信息得出源节点到路径中的每一跳的往返时延(round trip time，RTT)，以此估计每个中间节点的处理能力，由于它必须利用ICMP包的信息，在节点为交换机等二层处理设备的时候就会出现不正确的估计数据。PPTD［10－12］算法主要是用于估计一条路径上面端到端的带宽。PPTP算法通过发送分组对或分组串，并测试接收后的分组间隔来估计路径的带宽。由于背景流量的存在，使得估计的带宽可能偏小。sLoPs算法和ToPP算法都是基于自拥塞理论，并且两者都用于端到端可用带宽的估计。在sLoPs［13］算法中，发送方以一定的速度周期性地发送一定数目的等长的数据包给接收方，通过在接收方监测探测数据包的单向延迟来获取发送方到接收方的网络可用带宽。ToPP［14－15］算法通过在源主机和目的主机之间发送一系列的分组，并在接收端监测到达分组的速率来估计端到端的可用带宽。这些算法都能够较有效地对网络的带宽做出估计，但共同的一个问题就是需要向网络注入探测数据包，这必然会增加网络的流量。还有一些专门针对BT用户带宽估计的算法，如基于内容分组与能力匹配的邻居选择算法(neighbor－selection algorithm based on grouping by content and capacity similarities，GCCS)，则需要Tracker服务器的介入或由用户上报带宽数据［6］。

为了避免以上问题的出现，本文提出一种新的基于上传量和时间间隔的BT节点带宽估计方法，该方法很好地利用节点之间的协作关系，能在几乎不增加网络流量、不需要Tracker服务器介入和不依赖用户如实上报带宽数据的条件下，对邻居节点的上传带宽做出较为准确的估计。在此基础上，依据带宽匹配的原则将邻居划为友邻(即带宽匹配的邻居)和非友邻，再根据友邻优先的原则进行邻居选择，达到在不依赖中心节点或Tracker服务器的情况下选择带宽匹配的邻居进行连接和上传的目的，从而提高系统的下载性能。

1 算法介绍

算法由带宽估计和友邻选择2部分组成，带宽估计算法估计出邻居节点当前的上传带宽，友邻选择算法则以带宽估计结果为依据进行友邻选择。

1.1 带宽估计算法

1.1.1 算法思路

某一个节点对其他节点的带宽估计按照以下规则计算:在和其他节点发生了文件片上传后定期修正其估计值;算法每隔一定的周期向邻居请求交换带宽估计信息，依据邻居返回的信息更新自身的带宽估计表。

在每个节点中建一个带宽估计表bandList。设更新时间因子为 αk= βk·(1 － e(－(t－tlastj)/γ))，其中βk(k=1，2)为影响因子，且0.8 ＜ βk＜ 1;t表示当前时刻;tlastj表示上次对节点j更新带宽估计数据的时刻;t－tlastj表示更新的时间间隔;γ则控制曲线的衰减速度，9.5＜γ＜10.5。这样一个取值范围的设定能够保证在更新时间间隔较长的情况下，最新数据能对结果产生重大影响，而历史数据也能够保留一定的影响。设EBj(j=1，2，…，n)表示对节点j的估计带宽，max(bandj)=max(band1j，band2j，…，bandnj)，其中任意 bandij(i，j=1，2，…，n)为邻居i对节点j的带宽估计。

1.1.2 算法描述

带宽评估数据的更新发生在以下2种情况时。1)向邻居发送带宽评估请求，根据返回的带宽估计表，有以下2种可能。

①表中没有某个邻居的带宽数据，该邻居的带宽数据不更新;

②表中含有某个邻居j的带宽数据。

如果bandList中存在该邻居的带宽，EBj=当前数据·(1－α1)+max(bandj)·α1;

如果bandList中没有该邻居的带宽数据，EBj=max(bandj);

修改更新时间，tlastj=t;

2 )如果有邻居给自己上传了数据。

如果bandList中存在该邻居j的带宽数据，EBj=当前数据·(1－α2)+连续k个时间的上传量/k·α2;

如果bandList中没有该邻居的带宽数据，EBj=连续k个时间的上传量/k;

修改更新时间，tlastj=t。

1.2 友邻选择算法

首先给出带宽匹配的界定:如果邻居节点的上传带宽在本节点上传带宽10%的误差范围内，则认为两者的带宽是匹配的。

友邻选择算法包括友邻选择策略，非阻塞算法和优化非阻塞算法3部分组成，邻居选择策略是由非阻塞算法和优化非阻塞算法来实现。

1.2.1 友邻选择策略

友邻选择策略如图1所示，其中Uadd为待增连接节点集合，Udel为待断开连接节点集合。

图1 友邻选择策略Fig.1 Strategy of neighbor selection

1.2.2 友邻选择策略的实现

友邻选择策略是由非阻塞算法和优化非阻塞算法来实现的，因此，需要对BT系统的非阻塞算法和优化非阻塞算法进行修改。

1 )对BT系统的非阻塞算法中的排序算法进行修改。

①如果邻居a的上传量＞邻居b的上传量，则a排前面;

②如果邻居a的上传量等于邻居b的上传量，则如果a，b都是友邻或都不是友邻，次序不变。否则，a，b中唯一的一个友邻的排前面。

2 )对优化非阻塞算法的修改。

①创建一个新的友邻表;

②遍历自身的邻居表:如果为友邻，加入友邻表;

③如果友邻表非空，从友邻表中随机选取一个作为优化非阻塞的邻居。否则，从邻居表中随机选取一个作为优化非阻塞的邻居;

④将随机选择的邻居加入优化非阻塞表;

⑤友邻表清空。

2 仿真实验与结果分析

2.1 仿真器和仿真条件

为了获得更高的仿真效率和支持更多的节点参与，本文采用C++构建了一个BT协议的离散时间仿真器，仿真了节点的加入、自动离开与块交换等节点活动，也实现了TFT节点选择、最少片优先、反停滞等重要的BT算法，还能根据当前的连接情况动态分配带宽。仿真器时间以时步划分，仿真器使用的参数如表1所示。每个节点的最大连接数为40，节点的加入服从到达率为λ的泊松过程，节点完成下载后在系统中停留的时步数服从期望值为t的负指数分布。

表1 仿真器使用的参数Tab.1 Parameters used in the simulator

为了更真实地仿真实际BT网络中节点不对称的接入带宽，参考了Cameron Dale［16］使用的节点带宽类别，如表2所示。

表2 实验使用的节点特征Tab.2 Characteristics of peer used in the experiments

2.2 仿真实验

首先将新的基于带宽估计的友邻选择算法加入到仿真器中。实验开始的时候，只有一个种子节点，其类型设置为5，设定该种子节点始终不离开。当所有的用户均完成下载时，实验结束。在实验中，分别对200和300个节点在不同的文件片数条件下的下载过程做了仿真。

2.3 仿真结果与分析

为了验证算法的效果，分别在不同的节点数和不同的文件分片数条件下做了实验。同时为了验证作为整个算法基础的带宽估计算法的有效性，在程序中专门设置了全局数据结构BandList_All用于保存所有的用户的带宽数据。每一个节点都可以来访问这一个数据结构，从而直接获取邻居的带宽。在这种方式下，每个节点都能知道与它相连接的所有邻居的准确带宽数据。我们把这时候的友邻选择算法称之为基于已知带宽的友邻选择算法。实验结果见图2—7，图4—7对应的数据部分见表2。实验结果中的平均下载完成时间以时步为单位进行计算。

图2 种子节点对所有的200个节点的最大上传带宽估计图Fig.2 Maximum upload bandwidth of all 200 nodes estimated by the seed

图2为200个节点情况下，种子节点对所有的节点的带宽估计结果，图3为300个节点的情况下，180号节点对所有的节点的带宽估计结果。图2和图3的结果显示，节点带宽的估计值(估计带宽)与系统设定值(本文称为已知带宽)在绝大多数情况下差距不大。通过计算两者的相关系数，得出在图2和图3的条件下分别为0.912 7和0.849，表明两者的一致程度较高，说明带宽估计算法较准确地估计出了邻居节点的最大上传带宽。将基于已知带宽的友邻选择算法和基于带宽估计的友邻算法对BT性能的改进效果做比较(见图4—7)，发现两者区别不大，进一步说明了带宽估计算法的有效性。图4—7的结果显示，算法大幅度提高了中高带宽节点的下载速度，缩短了其平均下载完成时间，对于低带宽的节点也保持了较好的改进效果。在图4中，第5类节点的平均下载完成时间从144.44时步降低到83.11时步，减少了42.46%。第4类节点的平均下载完成时间则从149.33时步降低到86.38时步，减少的幅度达42.15%。而第3类节点的平均下载完成时间则从166.07时步降低到100.76时步，减少的幅度达到了39.33%。300个节点2 560个文件片的情况下，这几类节点的平均下载完成时间的减少幅度与此类似。通过对比图4和图5，图6和图7的实验数据，发现节点数对节点平均下载时间影响不大;对比图4和图6，则发现图6第2类和第3类节点的平均下载时间的减少幅度不如图 4;对比图5和图7，能发现同样的问题。通过输出实验后半程的拓扑图，发现在下载较大文件时，由于高带宽节点比低带宽节点完成的时间绝对差大幅度增加，而这些高带宽节点又在下载完成之后很快离开了系统，导致低带宽节点平均下载时间的改进效果不如下载较小文件时。通过增加高带宽节点下载后在系统中的停留时间能有效地提高整个系统的性能，降低节点的平均下载时间。

表3 图4－7对应的实验结果数据Tab.3 Corresponding result data of experiments according to Fig.4－7

3 结论

本文提出的基于带宽估计的友邻选择算法，在较准确地估计出邻居上传带宽的基础上，依据带宽匹配的原则进行邻居选择，算法大幅度提高了中、高带宽节点的下载速度，缩短了所有用户的平均下载时间，且不需要Tracker服务器的介入。

［1］SCHULZE Hendrik，MOCHALSKI Klaus.Internet Study 2008/2009［EB/OL］.(2009－10－15)［2011－03－02］.http://www.ipoque.com/userfiles/file/ipoque－Internet－Study－08－09.pdf，2009.

［2］BINDAL R，CAO P，CHANW.Improving traffic locality in BitTorrent via biased neighbor selection［C/OL］//IEEE ICDCS'.06.26th International Conference.Lisboa，July 4，2006:Distributed Computing Systems［2011－02－24］.http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=＆arnumber=1648853.

［3］张增斌，陈阳，邓北星，等.基于邻近原则的BitTorrent实验研究［J］.厦门大学学报:自然科学版，2007，46(02):213－215.

ZHANG Zeng－bin，CHEN Yang，DENG Bei－xing，et al.Experimental Study on Network Coordinate Based Locality－aware BitTorrent［J］.Journal of Xiamen University:Natural Science Edition，2007，46(A02):213－215.

［4］CHEN Hai－tao，GONG Zheng－hu，HUANG Zun－guo.Parallel downloading algorithm for large－volume file distribution［C/OL］//PDCAT'2005，Dalian，Dec 5，2005:Sixth International Conference on Parallel and Distributed Computing Applications and Technologies［2011－03－02］.http://www.computer.org/portal/web/csdl/doi/10.1109/PDCAT.2005.184.

［5］SUNG L G A，LIH H Y.Neighbour selectian strategies for P2P systerns using tit－for－tatexchange algorithm［D］.Waterloo:University ofWaterloo，2004.

［6］方阳，郑烇，李俊，等.基于内容分组与能力匹配的邻居选择算法［J］.计算机仿真，2009(4):158－161.

FANG Yang，ZHENG Quan，LIJun，et al.A Neighbor－Selection Algorithm Based on Grouping by Content and Capacity Similarities［J］.Computer Simulation，2009(4):158－161.

［7］PRASAD R，DOVROLISC，MURRAY M，et al.Bandwidth estimation:metrics，measurement，techniques，and tools［J］.IEEE Network，2003，17(6):27－35.

［8］BELLOVIN Steven M.A best－case network performance model［R］.［s.l.］:ATTResearch，1992.

［9］JACOBSON V.Pathchar:a tool to infer characteristics of Internet paths［EB/OL］.(1997－06－09)［2011－03－02］.ftp://ftp.ee.lbl.gov/pathchar/，1997.

［10］JACOBSON V.Congestion avoidance and control［J］.ACM SIGCOMM Computer Communi－cation Review，1988，18(4):314－329.

［11］KESHAV S.A control－theoretic approach to flow control［J］.ACM SIGCOMM Computer Communication Review，1991，21(4):3－15.

［12］BOLOT J C.Characterizing end－to－end packet delay and loss in the Internet［J］.Journal of High Speed Networks，1993，2(3):305－323.

［13］JAIN M DOVROLISC.End－to－end available bandwidth:measurement methodology，dynamics，and relation with TCP throughput［J］.IEEE/ACM Transactions on Networking，2003，11(4):537－549.

［14］MELANDER B，BJORKMAN M，GUNNINGBERG P.A new end－to－end probing and analysis method for estimating bandwidth bottlenecks［C/OL］//IEEE GLOBECOM'00.Nov 27，2000:Global Telecommunications Conference［2002－08－06］.http://ieeexplore.ieee.org/stamp/stamp.jsp?tp= ＆－arnumber=892039.

［15］MELANDER B，BJORKMAN M，GUNNINGBERG P.Regression－based available bandwidth measurements［C］//Proceedings of International Symposium on Performance Evaluation of Computer and Telecommunications Systems.San Diego:［s.n.］，2002:27－35.

［16］DALE C，LIU J，PETERS J，et al.Evolution andenhancement of BitTorrent network topologies［C/OL］//IEEE IWQoS'08 16th International Conference，Netherlands.Jun 2，2008:InternationalWorkshop on Quality of Service ［2008－06－10］.http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=＆arnumber=4539662.

(编辑:王敏琦)