ISP感知的BitTorrent流量优化

第40卷第4期电子科技大学学报VoL.40 No.42011年7月Joumal of University of Electronic Science and Technology ofChinaJul. 2011ISP感知的BitTorrent流量优化刘勇，秦志光(电子科技大学计算机科学与工程学院成都610054)[摘要]跨互联网服务提供商(ISP)的Biforrent流量严重降低互联网的运行效率。结合BitTorrent协议和不同ISP之间的连接结构，提出了ISP感知的BitTorrent流r优化方案STracker. STracker由 不同ISP中的Tracker代理构成，Trackr代理之间以对等联网方式连接,通过Tracker代理完成节点雏护和ISP感知的邻居分配,从而降低冗余的跨ISP流量.分析和模拟结果表明，STracker能够在不增加内容下载时间的条件下，大量降低跨ISP流量. STracker能够有效降低ISP的运营成本,提高互联网的效率.关键词Bitorrent; 互联网服务提供商; 对等网络; 流量控制;流量优化中图分类号1P393文献标识码Ado:i10.3969/j.is,10010548.2011.03.022ISP-Aware BitTorrent Traffic OptimizationLIU Yong and QIN Zhi-guang(School ofComputer Scicnce md Enginccring, University of Elcronic Science and Tchnology ofChina Chengdu 610054)Abstract BitTorrent-based applications incur massive cross-ISP traffic which heavily decreases Internetefficiency. Taking into account BitTorrent protocol specifications and connection structure among different ISPs,this paper proposes an ISP- aware BitTorrent traffic optimization scheme which is called STracker. STracker iscomposed of tracker proxies in different ISPs. Tracker proxies are connected with a P2P protocol. Tracker proxiesperform node management and biased neighbor allocation. Therefore, the cross-ISP traffic is reduced. Analysis andsimulations show that STracker can efficiently reduce the CrOss-ISP traffic while the download time is not increased. .STracker can reduce the operation cost of ISPs and improve the efficiency of Intermet efficiently.Key words BitTorrent; internet service providers; P2P networks; traffic control; traffic optimization对等(P2P)架构能够有效聚集网络边界资源，如点,节点之间建立直接的逻辑连接，而不考虑下层网络带宽、CPU计算能力和存储空间等，具有大规对应的物理连接是否跨越了多个互联网服务提供商模、可扩展、健壮、低成本等优势，适宜构建大规(SP)。BitTorrent的联网方 式带来大量的跨ISP流量,模资源共享系统，如基于对等网络的公平交换"、这些流 量既降低了网络的性能，又增加了ISP的运营流媒体2等。当前，多种流行的大规模互联网应用成本。ISP通常采用流量控制设备来应对该问题，对均基于对等架构，如Skype'), PPLivel4, BiTorrnt']P2P流量进行限流、封堵等,但这些措施既不利于ISP等，大部分互联网流量是由该类P2P应用所产生。盈利(客户流失),也不便于用户使用，无法从根本上2008~ 2009年的互 联网统计结果表明, P2P流量所占解决上述流量问题。比例为42.51%~69.95%,其中BitTorrent所占 的比例解决上述问题的有效方法是带偏邻居分配，即为30.02%~80.83%6。由此可见，BitTorrent协议的将一个节点的大部分邻居约束在当前ISP内，而允许运行行为对整个互联网的性能具有相当大的影响,小部分邻居跨ISP.带偏邻居分配机制能够在不增加研究BifTorrent流量优化问题能够提高网络运行的效下载时间的条件下降低跨ISP流量，同时满足了ISP率，具有重要的现实意义.和客户的需求。带偏邻居分配在邻居分配中考虑ISPBitTorrent协议不考虑下层网络的连接结构，而的因素，因而可称为ISP感知的邻居分配。然而，由且传输的内容来自于动态的用户节点，因此对互联于互联网本身是-一个松散的分布 式系统，无集中的网流量工程带来严峻的挑战。Bitorrent是 -一个应用中央节点协调系统的运行，节点无法有效获取所需层协议,采用随机分配的方式从Tracker获取邻居节的全局信息中国煤化工内邻居分配仍然YHCNMHG收稿日期: 2009-08-11; 修回日期。 2010-08-24基金项目:国家自然科学基金(60873075)作者简介:刘勇(1958-)勇, 博士生,主要从事网络安全对等计算方面的研究第4期.刘勇，等: ISP感知的BitTorrent流 量优化583是一个挑战性难题。Tracker节点，通过与iTracker通信获得相关ISP的网为了解决BitTorrent流量优化问题，本文提出络 拓扑信息. peer节点通过AppTracker的协调，能够并实现了ISP感知的邻居分配方案STracker.首先获得优化的邻居， 构建流量优化的BitTorrent网络.设计了基于Tracker代理的STracker架构,利用该架在理想条件下，即iTracker、 AppTracker和peer节点构实现ISP感知的邻居分配;然后设计了Tracker代完全合作的条件下, P4P能够获得优化的性能。然而，理的节点管理算法。本文通过模拟的方法验证iTracker和AppTracker之间如何建 立信任关系是一个STracker的有效性，模拟结果表明STracker能在不难题. -方面, iTracker由ISP提供,代表ISP的利益;增加下载时间的条件下，大幅降低跨ISP流量.本而AppTracker只是提 供邻居分配任务，无任何激励文的主要贡献包括:使得AppTracker相信并完全利用iTracker提供的信1)基于Tracker代理的Bitorrent流量优化架构息.另一方面，由于P4P中采用非随机的邻居分配策STracker;略,所构建的P2P网络的健壮性受到破坏。因此, P4P2) Tracker代理的节点维护算法。并非-一个完善的P2P流量优化方案。需要进一步指出1相关工作的是P4P并非代替P2P网络，只是提供了- -种机制允许ISP参与到P2P网络连接建立中,为P2P节点提供额由于BitTorrent协议的高效性，从其出现开始，外的关于网络拓扑方面的信息，以期构建-一个优化迅速成为网络用户首选的共享大文件的工具。然而，的P2P网络，获得优化的流量。由于BitTorrent协议是一一个应用层协议，其初始设计Ono9是BitTorrent协议实现Vuze的一一个插件, 用未考虑下层网络的连接结构，因此造成大量的跨ISP于提供邻居选择所需的决策信息，Ono利用内容分流量，而且这些流量的冗余度相当大.为了降低发网络(CDN),如Akamail等的探测信息实现节点Bitorrent应用所造成的负面影响，学术界提出了多之间相关性度量，从而实现更有效的邻居选择。基种解决方案优化BitTorrent流量。于CDN网络对互联网的测量，节点对CDN的探测在由于BitTorrent协议的高效性，大部分大文件共不同的时间点被重定向到不同的副本服务器。在享均采用BitTorent协议进行分发，如视频文件、个时间窗口里， 节点对CDN中不同副本服务器的访Linux操作系统的发行版等,因而大量的互联网流量问率构成-一个向量， 对节点p,这种访问率向量可属于BitTorrent协议。BitTorrent协议 的随机节点连接以表示为(fg,f&...f. >,其中，f。 为对副本服务方式导致了大量的跨ISP流量,这些流量既降低网络器r的访问率。如果两个节点具有相似的副本服务器的效率又增加ISP的成本，因此成为ISP重点控制的访问率向量，则该两节点距离较近，如间隔很少数对象。最初，ISP采用比较直接的方法限制、封堵量的网络甚至存在于同- -网络中。对于两个不同的BitTorrent流量，然而，这些措施无法从根本上解决节点，计算其访问率向量的余弦相似度凹,如果该BitTorrent所带来的流量问题。BitTorrent协议设计者相似度大于给定的阈值(如0.15),则认为该两节点可采用加密等方法混淆BitTorrent流量,使得上述控制以互为邻居节点，可优化BitTorrent的性能。与P4P策略失效。带偏邻居选择1是一种有效的优化.不一样，Ono不需要ISP和P2P应用之间的相互信任BitTorrent流量的策略，节点在选择邻居节点时，大和协作。然而, Ono对网络的测量信息来自于对CDN部分邻居节点为当前ISP内的节点,而小部分节点为网络的探测，需要P2P应用与CDN网络在某种程度当前ISP外的节点。模拟实验表明，带偏邻居选择策上的协作与信任。当前的CDN网络和P2P内容分发略能在不增加资源下载时间的条件下，降低跨ISP流网络是竞争关系，如何保证CDN网络会持续接受这量。然而，由于互联网是一个松散的分布式系统，种网络探测是- -个难题。当CDN网络采用某种方式在缺少全局状态信息的条件下，如何实现带偏邻居拒绝peer节点的探测或者给出错误信息时, Ono的流分配仍然是-一个难题。量优化功能则失效。P4Pl8是最近提出的一种优化P2P流量的架构，为了有效严计中国煤化工句题，本文提其中包括iTracker、AppTracker和peer节 点3个主要的出了STracker组成部分。ISP部署iTracker提供 当前ISP的网络拓扑MHCNM H代理通过对等联网构成，1raCKCTi任完成节 点维护等信息，peer节点通过与iTracker通信获得当前网络和邻居分配。与P4P相对比，本文提出的STracker更的相关信息。AppTracker是与具 体应用相关的加简单、健壮，可扩展性更好。.电子科技大学学报。第40卷2 BitTorrent流 量优化问题率为I(I+R),选中外部节点的概率为R(I+R),从而最初的BitTorrent协议采用随机分配的策略为请跨ISP流量所占比例为R(I+R)，当R较小时，该比例求节点分配邻居，该分配策略忽略了下层网络的连很小。Bitorent流量优化的目的是降低跨ISP的冗余接结构,带来大量的跨ISP流量,因此是-种低效的流量，降低相同的流量多次跨ISP进行传输。由于内邻居分配策略。BitTorrent流 量优化则是在不影响现容不一-定全部分布在当前ISP中，因此完全消除跨有共享性能的条件下，降低跨ISP流量,提高网络的ISP流量是不合理的，而且在跨ISP流量过小的情况效率，降低运营成本。因此，BitTorrent流量优化的下，会降低下载的性能，因此需要为R/I确定- -个合根本问题是有效的邻居分配策略。本文首先说明随理的值，主要通过对网络状况的评估来确定。机邻居分配中存在的问题，然后对带偏邻居分配进3 STracker的设计行讨论，从数学.上证明带偏邻居分配可以优化本文设计STracker实现上述带偏邻居分配策略，BitTorrent流量。STracker以Tracker代理的方式运行,构建并维护合理的候选邻居表，实现全局的带偏邻居分配。在ISP网ISP,{ ISP络中设置Tracker代理，该代理响应该ISP中所有BitTorrent客户端的邻居分配请求。不同ISP中的Tracker代理以P2P方式连接，构成- -个Tracker代理81 ISP连接结构的P2P网络，如图2所示，Tracker代理TP, TP2, TP3BitTorrent协议中，Torrent文件给 出了Tracker节和TP4连接成- -个P2P网络，通过该网络分布式维护点的URL,节点访问该URL而获得邻居，邻居之间全局的BitTorrent节点信息。节点之间周期性进行通的连接构成一个随机网络。本文定义根据同一信，完成邻居表的更新。BitTorrent客 户端通过配置Torrent文件连接起来的网络为一个Torrent网络。设其所在ISP的TP的地址完成将邻居请求发送给其所- -个Torrent网络中的节点数量为N,其中,位于ISP:属的TP而不是Torrent文件中的Tracker地址, TP根据中的节点数量为I,非ISP1中的节点数量为E，即对应的Torrent文件访问原始的Tracker获取外部的节N=I+E,如图1所示。ISP1中的节点A如果需要下载一点，构建对应于该Torrent文件的邻居候选表.个数据块，则选中该Torrent网络中任一节点的概率为1/N,该节点位于ISP1的概率为IN,位于ISP1外部r ISP2品ISP3的概率为E/N.因此，对ISP1来说，造成跨ISP流量的概率为E/N,即与该Torrent文件相关的跨ISP流量骨千ISP所占的比例为E/N.通常N远大于I,则(N-D/N趋近于1，从而跨ISP流量所占的比例相当大。在带偏邻居分配策略中，节点被选择作为邻居Qr.ISP{ IsP2了节点的概率是不等的。为了降低跨ISP流量，显然应司该为同一ISP内的节点赋更高的概率。设选中同一ISP内节点的概率为p,则选中其他ISP内节点的概率图2 STracker体系结构为q=1-p,当p>q时，则实现带偏邻居分配。为了实每个TP维护-一个候选邻居表，该表分为两个部现带偏邻居分配策略，本文采用一种候选邻居表的分，其一为L,用于维护当前ISP内的peer节点，5途径从全局节点中抽取符合要求的候选邻居，然后一为LE用于维护外部节点。TP节点之间需要周期性在候选邻居中实现随机分配。因此，需要解决的关传播节点信息，用于更新接收节点的邻居表。键问题是如何构建候选邻居表,该表可决定每个节STracker采用push-gossip的方法传播节点信息，每个点被选中的概率。针对ISPI, Tracker节 点维护-张TP节点周期性地将肿合后的节占信息推送给-个随中国煤化工候选邻居表，其中包含I个ISP1中 的节点和R(R<)个机节点;接YH融合本地Lg表,从E中随机选择的节点.依据该邻居表,同样采用随并随机选择. CNMHGR.具体算法如机分配策略,则可以实现全局带偏邻居分配的效果。算 法1和2所示，其中为- -个全局参数，Ll表示Lp当节点4需要下载- -个数据块,选中ISP中节点的概表的大小, random. sclect0用 于从指定的表中随机选586电子科技大学学报第40卷1 200of China, 2006, 35(4):698-701.随机邻居分配i 1000[ 一: --带偏邻居分配[2]杨戈,廖建新,朱晓民,等.面向对等网络的流媒体接纳控制[D北京邮电大学学报, 2008, 31(1);: 48-51.电800YANG Ge，LIAO Jian-xin, ZHU Xiao-min, et alPeer-to-peer oriented admission control for streaming media仍Jourmal of Beijing University of Posts andtelecommunications, 2008, 31(1): 48-51[3] BONFIGLI0 D, MELLIA M, MEO M, et al. Revealing忠200skype traffic: When randomness plays with you[J.o200 608010SIGCOMM Computer Communication Review, 2007, 37(4):周期/个37-48.图4下载速度对比[4] HUANG YAN, FU TOM Z. J, CHIU DAH-MING, et al.x10°Challenges, design and analysis of a large-scale p2p-vodsystem[]. SIGCOMM Computer Communication Review,.0叶带偏邻居分配]2008, 38(4): 375-388., st[5] COHEN B. BitTorrent protocol[EB/OL]. [2009- 09-01]htp://witorrent.orgbepsbep_ 0003.html.[6] HENDRIK s, KLAUS M. Internet study 2008/2009[EB/OL]. [2009- 09 -01] htp://www.ipoquc.com/resourcs.负2.0[7] RUCHIR B, CAO PEI, CHAN WILLIAM, et al. Improvingraffic locality in bitorrent ，via biased neighbor.0selection[CV/Proceedings of the 26th IEEE Intemational.s5Conference on Distributed Computing Systms (ICDCS2006). Washington, DC, USA: IEEE, 2006: 66.40 60800[8] XIE H Y, YANG Y R, ARVIND K, et al. P4p: Provider周期个portal for applications[J. Sigcomm Computer图5跨ISP流量对比Communication Review, 2008, 38(4): 351-362.5结束语[9] DAVID R C, BUSTAMANTE F E. Taming the torrent: apractical approach to reducing cross-isp traffic inBitorrent流量是互联网流量的主要组成部分，peer-to-peer systerms[]. SIGCOMM ComputerCommunication Review, 2008, 38(4): 363-374.对网络的性能和效率具有重要的影响。BitTorrent协{10] sU Ao-jan, CHOFFNES D R, ALEKSANDAR K, et al.议中，随机邻居分配策略导致大量的跨ISP冗余流Drating bchind akamai (travelocity-based detouring)[J]量，而带偏邻居分配是解决跨ISP流量的有效策略。SIGCOMM Computer Communication Review, 2006,36(4): 435-446.在分析带偏邻居分配策略的基础上,本文提出了ISP[11] SALTON G, MICHAEL J. MCGILL. Introduction to感知的BitTorrent流量优化方案STracker. STrackermodern information retrieval[M. New York, USA:由位于不同ISP的Tracker代理构成，Tracker代理之间McGraw-Hill Inc, 1986.以P2P方式连接,通过push-gossip协议实现候选邻居[12] NGUYEN T T T, ARMITAGE G. A survey of techniquesfor internet traffice classification using machine learning0.节点维护。Tracker代理的邻居分配算法决定了节点IEEE Communications Surveys and Tutorials, 2008, 10(4):的大部分邻居位于当前ISP之内,而小部分节点位于56-76.当前ISP之外，从而实现带偏邻居分配功能。模拟结[13] ANDREW W. MOORE, DENIS ZUEV. Intemnet taffcclassification using bayesian analysis techniques[CV果表明，STracker能够有效维护候选邻居，从而降低Proceedings of the 2005 ACM International Conference on跨ISP流量。STracker的另- 一个优点是只需对当前Measuremeat and Modeling of Computer SystemsBitTorrent客户端做较小的修改甚至无需修改就能够(SIGMETRICS 2005). New York, NY, USA: ACM, 2005:50~60.很好地运行。STracker的 提出有效解决了当前[14] YATIN C, SYLVIA R, LEE B, et al. Making gulelalikeBitTorrent流量优化所面临的难题。p2p systems scalable[C/Procedings of the 2003 ACMSIGCOMM Confcrence on Applications, Technologies,参考文献Architecture中国煤化工+ Comp.CommunicatYork, USA:[1]秦志光，罗绪成. P2P共享系统中无需专用切的公平交ACM, 2003:YHCNMH G换协议D.电子科技大学学报, 2006, 35(4): 698-701.QIN Zhi-guang, LU0 Xu. cbeng. Fair exchange protocol in编辑黄莘Peerto-Peer sharing system without dedicated TIP(].Joumal of University of Electronic Science and Technology