ISP感知的BitTorrent流量优化

刘 勇，秦志光

(电子科技大学计算机科学与工程学院 成都 610054)

对等(P2P)架构能够有效聚集网络边界资源，如网络带宽、CPU计算能力和存储空间等，具有大规模、可扩展、健壮、低成本等优势，适宜构建大规模资源共享系统，如基于对等网络的公平交换[1]、流媒体[2]等。当前，多种流行的大规模互联网应用均基于对等架构，如Skype[3]，PPLive[4]，BitTorrent[5]等，大部分互联网流量是由该类P2P应用所产生。2008～2009年的互联网统计结果表明，P2P流量所占比例为42.51%～69.95%，其中BitTorrent所占的比例为30.02%～80.83%[6]。由此可见，BitTorrent协议的运行行为对整个互联网的性能具有相当大的影响，研究BitTorrent流量优化问题能够提高网络运行的效率，具有重要的现实意义。

BitTorrent协议不考虑下层网络的连接结构，而且传输的内容来自于动态的用户节点，因此对互联网流量工程带来严峻的挑战。BitTorrent是一个应用层协议，采用随机分配的方式从Tracker获取邻居节点，节点之间建立直接的逻辑连接，而不考虑下层对应的物理连接是否跨越了多个互联网服务提供商(ISP)。BitTorrent的联网方式带来大量的跨ISP流量，这些流量既降低了网络的性能，又增加了ISP的运营成本。ISP通常采用流量控制设备来应对该问题，对P2P流量进行限流、封堵等，但这些措施既不利于ISP盈利(客户流失)，也不便于用户使用，无法从根本上解决上述流量问题。

解决上述问题的有效方法是带偏邻居分配，即将一个节点的大部分邻居约束在当前ISP内，而允许小部分邻居跨ISP。带偏邻居分配机制能够在不增加下载时间的条件下降低跨ISP流量，同时满足了ISP和客户的需求。带偏邻居分配在邻居分配中考虑ISP的因素，因而可称为ISP感知的邻居分配。然而，由于互联网本身是一个松散的分布式系统，无集中的中央节点协调系统的运行，节点无法有效获取所需的全局信息，因此有效实现ISP感知的邻居分配仍然是一个挑战性难题。

为了解决BitTorrent流量优化问题，本文提出并实现了ISP感知的邻居分配方案STracker。首先设计了基于Tracker代理的STracker架构，利用该架构实现ISP感知的邻居分配；然后设计了Tracker代理的节点管理算法。本文通过模拟的方法验证STracker的有效性，模拟结果表明STracker能在不增加下载时间的条件下，大幅降低跨ISP流量。本文的主要贡献包括：

1) 基于Tracker代理的BitTorrent流量优化架构STracker；

2) Tracker代理的节点维护算法。

1 相关工作

由于BitTorrent协议的高效性，从其出现开始，迅速成为网络用户首选的共享大文件的工具。然而，由于BitTorrent协议是一个应用层协议，其初始设计未考虑下层网络的连接结构，因此造成大量的跨ISP流量，而且这些流量的冗余度相当大。为了降低BitTorrent应用所造成的负面影响，学术界提出了多种解决方案优化BitTorrent流量。

由于BitTorrent协议的高效性，大部分大文件共享均采用BitTorrent协议进行分发，如视频文件、Linux操作系统的发行版等，因而大量的互联网流量属于BitTorrent协议。BitTorrent协议的随机节点连接方式导致了大量的跨ISP流量，这些流量既降低网络的效率又增加ISP的成本，因此成为ISP重点控制的对象。最初，ISP采用比较直接的方法限制、封堵BitTorrent流量，然而，这些措施无法从根本上解决BitTorrent所带来的流量问题。BitTorrent协议设计者采用加密等方法混淆BitTorrent流量，使得上述控制策略失效。带偏邻居选择[7]是一种有效的优化BitTorrent流量的策略，节点在选择邻居节点时，大部分邻居节点为当前ISP内的节点，而小部分节点为当前ISP外的节点。模拟实验表明，带偏邻居选择策略能在不增加资源下载时间的条件下，降低跨ISP流量。然而，由于互联网是一个松散的分布式系统，在缺少全局状态信息的条件下，如何实现带偏邻居分配仍然是一个难题。

P4P[8]是最近提出的一种优化P2P流量的架构，其中包括iTracker、AppTracker和peer节点3个主要的组成部分。ISP部署iTracker提供当前ISP的网络拓扑等信息，peer节点通过与iTracker通信获得当前网络的相关信息。AppTracker是与具体应用相关的Tracker节点，通过与iTracker通信获得相关ISP的网络拓扑信息。peer节点通过AppTracker的协调，能够获得优化的邻居，构建流量优化的BitTorrent网络。在理想条件下，即iTracker、AppTracker和peer节点完全合作的条件下，P4P能够获得优化的性能。然而，iTracker和AppTracker之间如何建立信任关系是一个难题。一方面，iTracker由ISP提供，代表ISP的利益；而AppTracker只是提供邻居分配任务，无任何激励使得AppTracker相信并完全利用iTracker提供的信息。另一方面，由于P4P中采用非随机的邻居分配策略，所构建的P2P网络的健壮性受到破坏。因此，P4P并非一个完善的P2P流量优化方案。需要进一步指出的是P4P并非代替P2P网络，只是提供了一种机制允许ISP参与到P2P网络连接建立中，为P2P节点提供额外的关于网络拓扑方面的信息，以期构建一个优化的P2P网络，获得优化的流量。

为了有效解决BitTorrent流量优化问题，本文提出了STracker方案，STracker由不同ISP中的Tracker代理通过对等联网构成，Tracker代理完成节点维护和邻居分配。与P4P相对比，本文提出的STracker更加简单、健壮，可扩展性更好。

2 BitTorrent流量优化问题

最初的BitTorrent协议采用随机分配的策略为请求节点分配邻居，该分配策略忽略了下层网络的连接结构，带来大量的跨ISP流量，因此是一种低效的邻居分配策略。BitTorrent流量优化则是在不影响现有共享性能的条件下，降低跨ISP流量，提高网络的效率，降低运营成本。因此，BitTorrent流量优化的根本问题是有效的邻居分配策略。本文首先说明随机邻居分配中存在的问题，然后对带偏邻居分配进行讨论，从数学上证明带偏邻居分配可以优化BitTorrent流量。

图1 ISP连接结构

BitTorrent协议中，Torrent文件给出了Tracker节点的URL，节点访问该URL而获得邻居，邻居之间的连接构成一个随机网络。本文定义根据同一Torrent文件连接起来的网络为一个Torrent网络。设一个Torrent网络中的节点数量为N，其中，位于ISP1中的节点数量为I，非ISP1中的节点数量为E，即N=I+E，如图1所示。ISP1中的节点A如果需要下载一个数据块，则选中该Torrent网络中任一节点的概率为1/N，该节点位于ISP1的概率为I/N，位于ISP1外部的概率为E/N。因此，对ISP1来说，造成跨ISP流量的概率为E/N，即与该Torrent文件相关的跨ISP流量所占的比例为E/N。通常N远大于I，则(N−I)/N趋近于1，从而跨ISP流量所占的比例相当大。

在带偏邻居分配策略中，节点被选择作为邻居节点的概率是不等的。为了降低跨ISP流量，显然应该为同一ISP内的节点赋更高的概率。设选中同一ISP内节点的概率为p，则选中其他ISP内节点的概率为q=1−p，当p>q时，则实现带偏邻居分配。为了实现带偏邻居分配策略，本文采用一种候选邻居表的途径从全局节点中抽取符合要求的候选邻居，然后在候选邻居中实现随机分配。因此，需要解决的关键问题是如何构建候选邻居表，该表可决定每个节点被选中的概率。针对ISP1，Tracker节点维护一张候选邻居表，其中包含I个ISP1中的节点和R(R

3 STracker的设计

本文设计STracker实现上述带偏邻居分配策略，STracker以Tracker代理的方式运行，构建并维护合理的候选邻居表，实现全局的带偏邻居分配。在ISP网络中设置Tracker代理，该代理响应该ISP中所有BitTorrent客户端的邻居分配请求。不同ISP中的Tracker代理以P2P方式连接，构成一个Tracker代理的P2P网络，如图2所示，Tracker代理TP1，TP2，TP3和TP4连接成一个P2P网络，通过该网络分布式维护全局的BitTorrent节点信息。节点之间周期性进行通信，完成邻居表的更新。BitTorrent客户端通过配置其所在ISP的TP的地址完成将邻居请求发送给其所属的TP而不是Torrent文件中的Tracker地址，TP根据对应的Torrent文件访问原始的Tracker获取外部的节点，构建对应于该Torrent文件的邻居候选表。

图2 STracker体系结构

每个TP维护一个候选邻居表，该表分为两个部分，其一为LI，用于维护当前ISP内的peer节点，另一为LE用于维护外部节点。TP节点之间需要周期性传播节点信息，用于更新接收节点的邻居表。STracker采用push-gossip的方法传播节点信息，每个TP节点周期性地将融合后的节点信息推送给一个随机节点；接收节点收到节点信息后，融合本地LE表，并随机选择其中一部分作为新的LE表。具体算法如算法1和2所示，其中t为一个全局参数，|LE|表示LE表的大小，random_select()用于从指定的表中随机选取指定数量的节点。

在实际部署中，STracker存在“某些ISP没有部署TP”和“如何激励BitTorrent客户端采用Tracker代理模式”两个问题。但该两问题均可以很好地被解决。图2所示的STracker是一种理想情况，部署Tracker代理的条件下，BitTorrent客户端直接通过各自的TP就可以获得邻居节点，在整个网络范围内，均无需其他单独的Tracker节点完成邻居分配。当网络中存在独立的Tracker节点时，TP节点可以通过相应的Torrent文件获得Tracker节点的URL并访问Tracker节点，从而获得一定数量的节点信息，然后将这些节点加入到邻居表的LE表中。对ISP来说，采用TP节点能够有效降低运营成本，提高网络效率，因此，ISP部署TP节点是可以得到回报的。对于BitTorrent客户端，使用TP并不一定能带来下载性能的提高，因此，需要设计相应的机制激励用户采用TP。ISP可以采用数据包重定向策略来引导用户采用TP，在ISP的网络边界，对所有进出的Tracker协议数据包，均重定向到TP，由TP来完成邻居分配工作。该方案基于网络协议识别技术[12-13]，可以很好地工作。

4 性能评估

根据前文的分析，STracker是一个可行的BitTorrent流量优化方案，本文通过模拟途径进一步对STracker的性能进行评估。模拟过程中关注的主要指标包括TP节点构建候选邻居表的性能、跨ISP流量和BitTorrent客户端的内容下载时间。

Tracker代理之间以P2P方式连接，本身构成一个P2P网络。本文模拟过程中采用Gnutella协议[14]构建TP网络，分别模拟了1 000、3 000和5 000个节点的幂律随机图。初始条件下，每个节点的候选邻居表只包含一个本ISP内部的候选邻居。在每个循环中，当前节点随机选择一个邻居节点，合并两个节点的候选邻居表，将合并后的表作为该邻居节点的候选邻居表。上述过程模拟TP节点的新候选邻居节点如何快速混合到其他TP节点的外部邻居表中。模拟过程中，首先观察需要多少周期才能够有效混合外部邻居节点，即外部邻居节点如何大致分布在不同的ISP的TP中。候选邻居节点的有效混合是以每个TP节点中所缓存的不同候选邻居的数量度量的，即观察模拟过程中，经过多少时间，TP节点的不同候选邻居数量趋于收敛。模拟结果如图3所示，根据图示，10个周期后，邻居表的规模迅速增长；15个周期后，基本达到收敛。因此，采用push-gossip算法能够快速传播候选邻居信息，有助于实现外部邻居选择的随机性。

图3 TP邻居表收敛速度

完成邻居分配之后，资源共享的性能成为关注的另一个指标。通常，对P2P客户端来说，共享的性能指下载一个大文件所需的时间，时间越短，用户的体验越好。因此，需要对比随机邻居分配策略和STracker的带偏邻居分配策略。带偏邻居分配的目的之一是降低跨ISP流量，因此跨ISP流量是模拟过程需要关注的指标之一。模拟过程中，共享文件的大小为10 000个分块，初始网络规模为10个节点，每个节点获得50个随机分块。随着节点的动态加入，观察整个系统中的跨ISP流量和获得全部分块的节点数量。系统获得全部分块的节点数量与时间变化的关系即下载速度的对比如图4所示。根据图4所示，带偏邻居分配策略具有与随机邻居分配策略相当的下载速度。跨ISP流量对比如图5所示。由图可见，带偏邻居分配大大降低了跨ISP流量。

根据上述模拟结果可以发现，STracker能够有效降低跨ISP流量且不增加资源下载的时间，因此能够有效提高网络的效率和降低ISP的运营成本。

图4 下载速度对比

图5 跨ISP流量对比

5 结 束 语

BitTorrent流量是互联网流量的主要组成部分，对网络的性能和效率具有重要的影响。BitTorrent协议中，随机邻居分配策略导致大量的跨ISP冗余流量，而带偏邻居分配是解决跨ISP流量的有效策略。在分析带偏邻居分配策略的基础上，本文提出了ISP感知的BitTorrent流量优化方案STracker。STracker由位于不同ISP的Tracker代理构成，Tracker代理之间以P2P方式连接，通过push-gossip协议实现候选邻居节点维护。Tracker代理的邻居分配算法决定了节点的大部分邻居位于当前ISP之内，而小部分节点位于当前ISP之外，从而实现带偏邻居分配功能。模拟结果表明，STracker能够有效维护候选邻居，从而降低跨ISP流量。STracker的另一个优点是只需对当前BitTorrent客户端做较小的修改甚至无需修改就能够很好地运行。STracker的提出有效解决了当前BitTorrent流量优化所面临的难题。

[1] 秦志光, 罗绪成. P2P共享系统中无需专用ttp的公平交换协议[J]. 电子科技大学学报, 2006, 35(4): 698-701.QIN Zhi-guang, LUO Xu-cheng. Fair exchange protocol in Peer-to-Peer sharing system without dedicated TTP[J].Journal of University of Electronic Science and Technology of China, 2006, 35(4):698-701.

[2] 杨戈, 廖建新, 朱晓民, 等. 面向对等网络的流媒体接纳控制[J]. 北京邮电大学学报, 2008, 31(1): 48-51.YANG Ge，LIAO Jian-xin, ZHU Xiao-min, et al.Peer-to-peer oriented admission control for streaming media[J]. Journal of Beijing University of Posts and telecommunications, 2008, 31(1): 48-51

[3] BONFIGLIO D, MELLIA M, MEO M, et al. Revealing skype traffic: When randomness plays with you[J].SIGCOMM Computer Communication Review, 2007, 37(4):37-48.

[4] HUANG YAN, FU TOM Z. J., CHIU DAH-MING, et al.Challenges, design and analysis of a large-scale p2p-vod system[J]. SIGCOMM Computer Communication Review,2008, 38(4): 375-388.

[5] COHEN B. BitTorrent protocol[EB/OL]. [2009-09-01]http://www.bittorrent.org/beps/bep_0003.html.

[6] HENDRIK S, KLAUS M. Internet study 2008/2009[EB/OL]. [2009-09-01] http://www.ipoque.com/resources.

[7] RUCHIR B, CAO PEI, CHAN WILLIAM, et al. Improving traffic locality in bittorrent via biased neighbor selection[C]//Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006). Washington, DC, USA: IEEE, 2006: 66.

[8] XIE H Y, YANG Y R, ARVIND K, et al. P4p: Provider portal for applications[J]. Sigcomm Computer Communication Review, 2008, 38(4): 351-362.

[9] DAVID R C, BUSTAMANTE F E. Taming the torrent: a practical approach to reducing cross-isp traffic in peer-to-peer systems[J]. SIGCOMM Computer Communication Review, 2008, 38(4): 363-374.

[10] SU Ao-jan, CHOFFNES D R, ALEKSANDAR K, et al.Drafting behind akamai (travelocity-based detouring)[J].SIGCOMM Computer Communication Review, 2006,36(4): 435-446.

[11] SALTON G, MICHAEL J. MCGILL. Introduction to modern information retrieval[M]. New York, USA:McGraw-Hill Inc, 1986.

[12] NGUYEN T T T, ARMITAGE G. A survey of techniques for internet traffic classification using machine learning[J].IEEE Communications Surveys and Tutorials, 2008, 10(4):56-76.

[13] ANDREW W. MOORE, DENIS ZUEV. Internet traffic classification using bayesian analysis techniques[C]//Proceedings of the 2005 ACM International Conference on Measurement and Modeling of Computer Systems(SIGMETRICS 2005). New York, NY, USA: ACM, 2005:50-60.

[14] YATIN C, SYLVIA R, LEE B, et al. Making gnutella-like p2p systems scalable[C]//Proceedings of the 2003 ACM SIGCOMM Conference on Applications, Technologies,Architectures, and Protocols for Computer Communications (SIGCOMM 2003). New York, USA:ACM, 2003: 407-418.