第40卷第4期電子科技大學學報VoL.40 No.42011年7月Joumal of University of Electronic Science and Technology ofChinaJul. 2011ISP感知的BitTorrent流量優(yōu)化劉勇，秦志光(電子科技大學計算機科學與工程學院成都610054)[摘要]跨互聯(lián)網(wǎng)服務提供商(ISP)的Biforrent流量嚴重降低互聯(lián)網(wǎng)的運行效率。結合BitTorrent協(xié)議和不同ISP之間的連接結構，提出了ISP感知的BitTorrent流r優(yōu)化方案STracker. STracker由 不同ISP中的Tracker代理構成，Trackr代理之間以對等聯(lián)網(wǎng)方式連接,通過Tracker代理完成節(jié)點雛護和ISP感知的鄰居分配,從而降低冗余的跨ISP流量.分析和模擬結果表明，STracker能夠在不增加內(nèi)容下載時間的條件下，大量降低跨ISP流量. STracker能夠有效降低ISP的運營成本,提高互聯(lián)網(wǎng)的效率.關鍵詞Bitorrent; 互聯(lián)網(wǎng)服務提供商; 對等網(wǎng)絡; 流量控制;流量優(yōu)化中圖分類號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)架構能夠有效聚集網(wǎng)絡邊界資源，如點,節(jié)點之間建立直接的邏輯連接，而不考慮下層網(wǎng)絡帶寬、CPU計算能力和存儲空間等，具有大規(guī)對應的物理連接是否跨越了多個互聯(lián)網(wǎng)服務提供商模、可擴展、健壯、低成本等優(yōu)勢，適宜構建大規(guī)(SP)。BitTorrent的聯(lián)網(wǎng)方 式帶來大量的跨ISP流量,模資源共享系統(tǒng)，如基于對等網(wǎng)絡的公平交換"、這些流 量既降低了網(wǎng)絡的性能，又增加了ISP的運營流媒體2等。當前，多種流行的大規(guī)?；ヂ?lián)網(wǎng)應用成本。ISP通常采用流量控制設備來應對該問題，對均基于對等架構，如Skype'), PPLivel4, BiTorrnt']P2P流量進行限流、封堵等,但這些措施既不利于ISP等，大部分互聯(lián)網(wǎng)流量是由該類P2P應用所產(chǎn)生。盈利(客戶流失),也不便于用戶使用，無法從根本上2008~ 2009年的互 聯(lián)網(wǎng)統(tǒng)計結果表明, P2P流量所占解決上述流量問題。比例為42.51%~69.95%,其中BitTorrent所占 的比例解決上述問題的有效方法是帶偏鄰居分配，即為30.02%~80.83%6。由此可見，BitTorrent協(xié)議的將一個節(jié)點的大部分鄰居約束在當前ISP內(nèi)，而允許運行行為對整個互聯(lián)網(wǎng)的性能具有相當大的影響,小部分鄰居跨ISP.帶偏鄰居分配機制能夠在不增加研究BifTorrent流量優(yōu)化問題能夠提高網(wǎng)絡運行的效下載時間的條件下降低跨ISP流量，同時滿足了ISP率，具有重要的現(xiàn)實意義.和客戶的需求。帶偏鄰居分配在鄰居分配中考慮ISPBitTorrent協(xié)議不考慮下層網(wǎng)絡的連接結構，而的因素，因而可稱為ISP感知的鄰居分配。然而，由且傳輸?shù)膬?nèi)容來自于動態(tài)的用戶節(jié)點，因此對互聯(lián)于互聯(lián)網(wǎng)本身是-一個松散的分布 式系統(tǒng)，無集中的網(wǎng)流量工程帶來嚴峻的挑戰(zhàn)。Bitorrent是 -一個應用中央節(jié)點協(xié)調系統(tǒng)的運行，節(jié)點無法有效獲取所需層協(xié)議,采用隨機分配的方式從Tracker獲取鄰居節(jié)的全局信息中國煤化工內(nèi)鄰居分配仍然YHCNMHG收稿日期: 2009-08-11; 修回日期。 2010-08-24基金項目:國家自然科學基金(60873075)作者簡介:劉勇(1958-)勇, 博士生,主要從事網(wǎng)絡安全對等計算方面的研究第4期.劉勇，等: ISP感知的BitTorrent流 量優(yōu)化583是一個挑戰(zhàn)性難題。Tracker節(jié)點，通過與iTracker通信獲得相關ISP的網(wǎng)為了解決BitTorrent流量優(yōu)化問題，本文提出絡 拓撲信息. peer節(jié)點通過AppTracker的協(xié)調，能夠并實現(xiàn)了ISP感知的鄰居分配方案STracker.首先獲得優(yōu)化的鄰居， 構建流量優(yōu)化的BitTorrent網(wǎng)絡.設計了基于Tracker代理的STracker架構,利用該架在理想條件下，即iTracker、 AppTracker和peer節(jié)點構實現(xiàn)ISP感知的鄰居分配;然后設計了Tracker代完全合作的條件下, P4P能夠獲得優(yōu)化的性能。然而，理的節(jié)點管理算法。本文通過模擬的方法驗證iTracker和AppTracker之間如何建 立信任關系是一個STracker的有效性，模擬結果表明STracker能在不難題. -方面, iTracker由ISP提供,代表ISP的利益;增加下載時間的條件下，大幅降低跨ISP流量.本而AppTracker只是提 供鄰居分配任務，無任何激勵文的主要貢獻包括:使得AppTracker相信并完全利用iTracker提供的信1)基于Tracker代理的Bitorrent流量優(yōu)化架構息.另一方面，由于P4P中采用非隨機的鄰居分配策STracker;略,所構建的P2P網(wǎng)絡的健壯性受到破壞。因此, P4P2) Tracker代理的節(jié)點維護算法。并非-一個完善的P2P流量優(yōu)化方案。需要進一步指出1相關工作的是P4P并非代替P2P網(wǎng)絡，只是提供了- -種機制允許ISP參與到P2P網(wǎng)絡連接建立中,為P2P節(jié)點提供額由于BitTorrent協(xié)議的高效性，從其出現(xiàn)開始，外的關于網(wǎng)絡拓撲方面的信息，以期構建-一個優(yōu)化迅速成為網(wǎng)絡用戶首選的共享大文件的工具。然而，的P2P網(wǎng)絡，獲得優(yōu)化的流量。由于BitTorrent協(xié)議是一一個應用層協(xié)議，其初始設計Ono9是BitTorrent協(xié)議實現(xiàn)Vuze的一一個插件, 用未考慮下層網(wǎng)絡的連接結構，因此造成大量的跨ISP于提供鄰居選擇所需的決策信息，Ono利用內(nèi)容分流量，而且這些流量的冗余度相當大.為了降低發(fā)網(wǎng)絡(CDN),如Akamail等的探測信息實現(xiàn)節(jié)點Bitorrent應用所造成的負面影響，學術界提出了多之間相關性度量，從而實現(xiàn)更有效的鄰居選擇。基種解決方案優(yōu)化BitTorrent流量。于CDN網(wǎng)絡對互聯(lián)網(wǎng)的測量，節(jié)點對CDN的探測在由于BitTorrent協(xié)議的高效性，大部分大文件共不同的時間點被重定向到不同的副本服務器。在享均采用BitTorent協(xié)議進行分發(fā)，如視頻文件、個時間窗口里， 節(jié)點對CDN中不同副本服務器的訪Linux操作系統(tǒng)的發(fā)行版等,因而大量的互聯(lián)網(wǎng)流量問率構成-一個向量， 對節(jié)點p,這種訪問率向量可屬于BitTorrent協(xié)議。BitTorrent協(xié)議 的隨機節(jié)點連接以表示為(fg,f&...f. >,其中，f。 為對副本服務方式導致了大量的跨ISP流量,這些流量既降低網(wǎng)絡器r的訪問率。如果兩個節(jié)點具有相似的副本服務器的效率又增加ISP的成本，因此成為ISP重點控制的訪問率向量，則該兩節(jié)點距離較近，如間隔很少數(shù)對象。最初，ISP采用比較直接的方法限制、封堵量的網(wǎng)絡甚至存在于同- -網(wǎng)絡中。對于兩個不同的BitTorrent流量，然而，這些措施無法從根本上解決節(jié)點，計算其訪問率向量的余弦相似度凹,如果該BitTorrent所帶來的流量問題。BitTorrent協(xié)議設計者相似度大于給定的閾值(如0.15),則認為該兩節(jié)點可采用加密等方法混淆BitTorrent流量,使得上述控制以互為鄰居節(jié)點，可優(yōu)化BitTorrent的性能。與P4P策略失效。帶偏鄰居選擇1是一種有效的優(yōu)化.不一樣，Ono不需要ISP和P2P應用之間的相互信任BitTorrent流量的策略，節(jié)點在選擇鄰居節(jié)點時，大和協(xié)作。然而, Ono對網(wǎng)絡的測量信息來自于對CDN部分鄰居節(jié)點為當前ISP內(nèi)的節(jié)點,而小部分節(jié)點為網(wǎng)絡的探測，需要P2P應用與CDN網(wǎng)絡在某種程度當前ISP外的節(jié)點。模擬實驗表明，帶偏鄰居選擇策上的協(xié)作與信任。當前的CDN網(wǎng)絡和P2P內(nèi)容分發(fā)略能在不增加資源下載時間的條件下，降低跨ISP流網(wǎng)絡是競爭關系，如何保證CDN網(wǎng)絡會持續(xù)接受這量。然而，由于互聯(lián)網(wǎng)是一個松散的分布式系統(tǒng)，種網(wǎng)絡探測是- -個難題。當CDN網(wǎng)絡采用某種方式在缺少全局狀態(tài)信息的條件下，如何實現(xiàn)帶偏鄰居拒絕peer節(jié)點的探測或者給出錯誤信息時, Ono的流分配仍然是-一個難題。量優(yōu)化功能則失效。P4Pl8是最近提出的一種優(yōu)化P2P流量的架構，為了有效嚴計中國煤化工句題，本文提其中包括iTracker、AppTracker和peer節(jié) 點3個主要的出了STracker組成部分。ISP部署iTracker提供 當前ISP的網(wǎng)絡拓撲MHCNM H代理通過對等聯(lián)網(wǎng)構成，1raCKCTi任完成節(jié) 點維護等信息，peer節(jié)點通過與iTracker通信獲得當前網(wǎng)絡和鄰居分配。與P4P相對比，本文提出的STracker更的相關信息。AppTracker是與具 體應用相關的加簡單、健壯，可擴展性更好。.電子科技大學學報。第40卷2 BitTorrent流 量優(yōu)化問題率為I(I+R),選中外部節(jié)點的概率為R(I+R),從而最初的BitTorrent協(xié)議采用隨機分配的策略為請跨ISP流量所占比例為R(I+R)，當R較小時，該比例求節(jié)點分配鄰居，該分配策略忽略了下層網(wǎng)絡的連很小。Bitorent流量優(yōu)化的目的是降低跨ISP的冗余接結構,帶來大量的跨ISP流量,因此是-種低效的流量，降低相同的流量多次跨ISP進行傳輸。由于內(nèi)鄰居分配策略。BitTorrent流 量優(yōu)化則是在不影響現(xiàn)容不一-定全部分布在當前ISP中，因此完全消除跨有共享性能的條件下，降低跨ISP流量,提高網(wǎng)絡的ISP流量是不合理的，而且在跨ISP流量過小的情況效率，降低運營成本。因此，BitTorrent流量優(yōu)化的下，會降低下載的性能，因此需要為R/I確定- -個合根本問題是有效的鄰居分配策略。本文首先說明隨理的值，主要通過對網(wǎng)絡狀況的評估來確定。機鄰居分配中存在的問題，然后對帶偏鄰居分配進3 STracker的設計行討論，從數(shù)學.上證明帶偏鄰居分配可以優(yōu)化本文設計STracker實現(xiàn)上述帶偏鄰居分配策略，BitTorrent流量。STracker以Tracker代理的方式運行,構建并維護合理的候選鄰居表，實現(xiàn)全局的帶偏鄰居分配。在ISP網(wǎng)ISP,{ ISP絡中設置Tracker代理，該代理響應該ISP中所有BitTorrent客戶端的鄰居分配請求。不同ISP中的Tracker代理以P2P方式連接，構成- -個Tracker代理81 ISP連接結構的P2P網(wǎng)絡，如圖2所示，Tracker代理TP, TP2, TP3BitTorrent協(xié)議中，Torrent文件給 出了Tracker節(jié)和TP4連接成- -個P2P網(wǎng)絡，通過該網(wǎng)絡分布式維護點的URL,節(jié)點訪問該URL而獲得鄰居，鄰居之間全局的BitTorrent節(jié)點信息。節(jié)點之間周期性進行通的連接構成一個隨機網(wǎng)絡。本文定義根據(jù)同一信，完成鄰居表的更新。BitTorrent客 戶端通過配置Torrent文件連接起來的網(wǎng)絡為一個Torrent網(wǎng)絡。設其所在ISP的TP的地址完成將鄰居請求發(fā)送給其所- -個Torrent網(wǎng)絡中的節(jié)點數(shù)量為N,其中,位于ISP:屬的TP而不是Torrent文件中的Tracker地址, TP根據(jù)中的節(jié)點數(shù)量為I,非ISP1中的節(jié)點數(shù)量為E，即對應的Torrent文件訪問原始的Tracker獲取外部的節(jié)N=I+E,如圖1所示。ISP1中的節(jié)點A如果需要下載一點，構建對應于該Torrent文件的鄰居候選表.個數(shù)據(jù)塊，則選中該Torrent網(wǎng)絡中任一節(jié)點的概率為1/N,該節(jié)點位于ISP1的概率為IN,位于ISP1外部r ISP2品ISP3的概率為E/N.因此，對ISP1來說，造成跨ISP流量的概率為E/N,即與該Torrent文件相關的跨ISP流量骨千ISP所占的比例為E/N.通常N遠大于I,則(N-D/N趨近于1，從而跨ISP流量所占的比例相當大。在帶偏鄰居分配策略中，節(jié)點被選擇作為鄰居Qr.ISP{ IsP2了節(jié)點的概率是不等的。為了降低跨ISP流量，顯然應司該為同一ISP內(nèi)的節(jié)點賦更高的概率。設選中同一ISP內(nèi)節(jié)點的概率為p,則選中其他ISP內(nèi)節(jié)點的概率圖2 STracker體系結構為q=1-p,當p>q時，則實現(xiàn)帶偏鄰居分配。為了實每個TP維護-一個候選鄰居表，該表分為兩個部現(xiàn)帶偏鄰居分配策略，本文采用一種候選鄰居表的分，其一為L,用于維護當前ISP內(nèi)的peer節(jié)點，5途徑從全局節(jié)點中抽取符合要求的候選鄰居，然后一為LE用于維護外部節(jié)點。TP節(jié)點之間需要周期性在候選鄰居中實現(xiàn)隨機分配。因此，需要解決的關傳播節(jié)點信息，用于更新接收節(jié)點的鄰居表。鍵問題是如何構建候選鄰居表,該表可決定每個節(jié)STracker采用push-gossip的方法傳播節(jié)點信息，每個點被選中的概率。針對ISPI, Tracker節(jié) 點維護-張TP節(jié)點周期性地將腫合后的節(jié)占信息推送給-個隨中國煤化工候選鄰居表，其中包含I個ISP1中 的節(jié)點和R(R<)個機節(jié)點;接YH融合本地Lg表,從E中隨機選擇的節(jié)點.依據(jù)該鄰居表,同樣采用隨并隨機選擇. CNMHGR.具體算法如機分配策略,則可以實現(xiàn)全局帶偏鄰居分配的效果。算 法1和2所示，其中為- -個全局參數(shù)，Ll表示Lp當節(jié)點4需要下載- -個數(shù)據(jù)塊,選中ISP中節(jié)點的概表的大小, random. sclect0用 于從指定的表中隨機選586電子科技大學學報第40卷1 200of China, 2006, 35(4):698-701.隨機鄰居分配i 1000[ 一: --帶偏鄰居分配[2]楊戈,廖建新,朱曉民,等.面向對等網(wǎng)絡的流媒體接納控制[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流量是互聯(lián)網(wǎng)流量的主要組成部分，peer-to-peer systerms[]. SIGCOMM ComputerCommunication Review, 2008, 38(4): 363-374.對網(wǎng)絡的性能和效率具有重要的影響。BitTorrent協(xié){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流量優(yōu)化方案STracker. STrackermodern information retrieval[M. New York, USA:由位于不同ISP的Tracker代理構成，Tracker代理之間McGraw-Hill Inc, 1986.以P2P方式連接,通過push-gossip協(xié)議實現(xiàn)候選鄰居[12] NGUYEN T T T, ARMITAGE G. A survey of techniquesfor internet traffice classification using machine learning0.節(jié)點維護。Tracker代理的鄰居分配算法決定了節(jié)點IEEE Communications Surveys and Tutorials, 2008, 10(4):的大部分鄰居位于當前ISP之內(nèi),而小部分節(jié)點位于56-76.當前ISP之外，從而實現(xiàn)帶偏鄰居分配功能。模擬結[13] ANDREW W. MOORE, DENIS ZUEV. Intemnet taffcclassification using bayesian analysis techniques[CV果表明，STracker能夠有效維護候選鄰居，從而降低Proceedings of the 2005 ACM International Conference on跨ISP流量。STracker的另- 一個優(yōu)點是只需對當前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流量優(yōu)化所面臨的難題。p2p systems scalable[C/Procedings of the 2003 ACMSIGCOMM Confcrence on Applications, Technologies,參考文獻Architecture中國煤化工+ Comp.CommunicatYork, USA:[1]秦志光，羅緒成. P2P共享系統(tǒng)中無需專用切的公平交ACM, 2003:YHCNMH G換協(xié)議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