ISP感知的BitTorrent流量?jì)?yōu)化

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