劉 勇，秦志光

(電子科技大學計算機科學與工程學院 成都 610054)

對等(P2P)架構(gòu)能夠有效聚集網(wǎng)絡(luò)邊界資源，如網(wǎng)絡(luò)帶寬、CPU計算能力和存儲空間等，具有大規(guī)模、可擴展、健壯、低成本等優(yōu)勢，適宜構(gòu)建大規(guī)模資源共享系統(tǒng)，如基于對等網(wǎng)絡(luò)的公平交換[1]、流媒體[2]等。當前，多種流行的大規(guī)?；ヂ?lián)網(wǎng)應(yīng)用均基于對等架構(gòu)，如Skype[3]，PPLive[4]，BitTorrent[5]等，大部分互聯(lián)網(wǎng)流量是由該類P2P應(yīng)用所產(chǎn)生。2008～2009年的互聯(lián)網(wǎng)統(tǒng)計結(jié)果表明，P2P流量所占比例為42.51%～69.95%，其中BitTorrent所占的比例為30.02%～80.83%[6]。由此可見，BitTorrent協(xié)議的運行行為對整個互聯(lián)網(wǎng)的性能具有相當大的影響，研究BitTorrent流量優(yōu)化問題能夠提高網(wǎng)絡(luò)運行的效率，具有重要的現(xiàn)實意義。

BitTorrent協(xié)議不考慮下層網(wǎng)絡(luò)的連接結(jié)構(gòu)，而且傳輸?shù)膬?nèi)容來自于動態(tài)的用戶節(jié)點，因此對互聯(lián)網(wǎng)流量工程帶來嚴峻的挑戰(zhàn)。BitTorrent是一個應(yīng)用層協(xié)議，采用隨機分配的方式從Tracker獲取鄰居節(jié)點，節(jié)點之間建立直接的邏輯連接，而不考慮下層對應(yīng)的物理連接是否跨越了多個互聯(lián)網(wǎng)服務(wù)提供商(ISP)。BitTorrent的聯(lián)網(wǎng)方式帶來大量的跨ISP流量，這些流量既降低了網(wǎng)絡(luò)的性能，又增加了ISP的運營成本。ISP通常采用流量控制設(shè)備來應(yīng)對該問題，對P2P流量進行限流、封堵等，但這些措施既不利于ISP盈利(客戶流失)，也不便于用戶使用，無法從根本上解決上述流量問題。

解決上述問題的有效方法是帶偏鄰居分配，即將一個節(jié)點的大部分鄰居約束在當前ISP內(nèi)，而允許小部分鄰居跨ISP。帶偏鄰居分配機制能夠在不增加下載時間的條件下降低跨ISP流量，同時滿足了ISP和客戶的需求。帶偏鄰居分配在鄰居分配中考慮ISP的因素，因而可稱為ISP感知的鄰居分配。然而，由于互聯(lián)網(wǎng)本身是一個松散的分布式系統(tǒng)，無集中的中央節(jié)點協(xié)調(diào)系統(tǒng)的運行，節(jié)點無法有效獲取所需的全局信息，因此有效實現(xiàn)ISP感知的鄰居分配仍然是一個挑戰(zhàn)性難題。

為了解決BitTorrent流量優(yōu)化問題，本文提出并實現(xiàn)了ISP感知的鄰居分配方案STracker。首先設(shè)計了基于Tracker代理的STracker架構(gòu)，利用該架構(gòu)實現(xiàn)ISP感知的鄰居分配；然后設(shè)計了Tracker代理的節(jié)點管理算法。本文通過模擬的方法驗證STracker的有效性，模擬結(jié)果表明STracker能在不增加下載時間的條件下，大幅降低跨ISP流量。本文的主要貢獻包括：

1) 基于Tracker代理的BitTorrent流量優(yōu)化架構(gòu)STracker；

2) Tracker代理的節(jié)點維護算法。

1 相關(guān)工作

由于BitTorrent協(xié)議的高效性，從其出現(xiàn)開始，迅速成為網(wǎng)絡(luò)用戶首選的共享大文件的工具。然而，由于BitTorrent協(xié)議是一個應(yīng)用層協(xié)議，其初始設(shè)計未考慮下層網(wǎng)絡(luò)的連接結(jié)構(gòu)，因此造成大量的跨ISP流量，而且這些流量的冗余度相當大。為了降低BitTorrent應(yīng)用所造成的負面影響，學術(shù)界提出了多種解決方案優(yōu)化BitTorrent流量。

由于BitTorrent協(xié)議的高效性，大部分大文件共享均采用BitTorrent協(xié)議進行分發(fā)，如視頻文件、Linux操作系統(tǒng)的發(fā)行版等，因而大量的互聯(lián)網(wǎng)流量屬于BitTorrent協(xié)議。BitTorrent協(xié)議的隨機節(jié)點連接方式導致了大量的跨ISP流量，這些流量既降低網(wǎng)絡(luò)的效率又增加ISP的成本，因此成為ISP重點控制的對象。最初，ISP采用比較直接的方法限制、封堵BitTorrent流量，然而，這些措施無法從根本上解決BitTorrent所帶來的流量問題。BitTorrent協(xié)議設(shè)計者采用加密等方法混淆BitTorrent流量，使得上述控制策略失效。帶偏鄰居選擇[7]是一種有效的優(yōu)化BitTorrent流量的策略，節(jié)點在選擇鄰居節(jié)點時，大部分鄰居節(jié)點為當前ISP內(nèi)的節(jié)點，而小部分節(jié)點為當前ISP外的節(jié)點。模擬實驗表明，帶偏鄰居選擇策略能在不增加資源下載時間的條件下，降低跨ISP流量。然而，由于互聯(lián)網(wǎng)是一個松散的分布式系統(tǒng)，在缺少全局狀態(tài)信息的條件下，如何實現(xiàn)帶偏鄰居分配仍然是一個難題。

P4P[8]是最近提出的一種優(yōu)化P2P流量的架構(gòu)，其中包括iTracker、AppTracker和peer節(jié)點3個主要的組成部分。ISP部署iTracker提供當前ISP的網(wǎng)絡(luò)拓撲等信息，peer節(jié)點通過與iTracker通信獲得當前網(wǎng)絡(luò)的相關(guān)信息。AppTracker是與具體應(yīng)用相關(guān)的Tracker節(jié)點，通過與iTracker通信獲得相關(guān)ISP的網(wǎng)絡(luò)拓撲信息。peer節(jié)點通過AppTracker的協(xié)調(diào)，能夠獲得優(yōu)化的鄰居，構(gòu)建流量優(yōu)化的BitTorrent網(wǎng)絡(luò)。在理想條件下，即iTracker、AppTracker和peer節(jié)點完全合作的條件下，P4P能夠獲得優(yōu)化的性能。然而，iTracker和AppTracker之間如何建立信任關(guān)系是一個難題。一方面，iTracker由ISP提供，代表ISP的利益；而AppTracker只是提供鄰居分配任務(wù)，無任何激勵使得AppTracker相信并完全利用iTracker提供的信息。另一方面，由于P4P中采用非隨機的鄰居分配策略，所構(gòu)建的P2P網(wǎng)絡(luò)的健壯性受到破壞。因此，P4P并非一個完善的P2P流量優(yōu)化方案。需要進一步指出的是P4P并非代替P2P網(wǎng)絡(luò)，只是提供了一種機制允許ISP參與到P2P網(wǎng)絡(luò)連接建立中，為P2P節(jié)點提供額外的關(guān)于網(wǎng)絡(luò)拓撲方面的信息，以期構(gòu)建一個優(yōu)化的P2P網(wǎng)絡(luò)，獲得優(yōu)化的流量。

為了有效解決BitTorrent流量優(yōu)化問題，本文提出了STracker方案，STracker由不同ISP中的Tracker代理通過對等聯(lián)網(wǎng)構(gòu)成，Tracker代理完成節(jié)點維護和鄰居分配。與P4P相對比，本文提出的STracker更加簡單、健壯，可擴展性更好。

2 BitTorrent流量優(yōu)化問題

最初的BitTorrent協(xié)議采用隨機分配的策略為請求節(jié)點分配鄰居，該分配策略忽略了下層網(wǎng)絡(luò)的連接結(jié)構(gòu)，帶來大量的跨ISP流量，因此是一種低效的鄰居分配策略。BitTorrent流量優(yōu)化則是在不影響現(xiàn)有共享性能的條件下，降低跨ISP流量，提高網(wǎng)絡(luò)的效率，降低運營成本。因此，BitTorrent流量優(yōu)化的根本問題是有效的鄰居分配策略。本文首先說明隨機鄰居分配中存在的問題，然后對帶偏鄰居分配進行討論，從數(shù)學上證明帶偏鄰居分配可以優(yōu)化BitTorrent流量。

圖1 ISP連接結(jié)構(gòu)

BitTorrent協(xié)議中，Torrent文件給出了Tracker節(jié)點的URL，節(jié)點訪問該URL而獲得鄰居，鄰居之間的連接構(gòu)成一個隨機網(wǎng)絡(luò)。本文定義根據(jù)同一Torrent文件連接起來的網(wǎng)絡(luò)為一個Torrent網(wǎng)絡(luò)。設(shè)一個Torrent網(wǎng)絡(luò)中的節(jié)點數(shù)量為N，其中，位于ISP1中的節(jié)點數(shù)量為I，非ISP1中的節(jié)點數(shù)量為E，即N=I+E，如圖1所示。ISP1中的節(jié)點A如果需要下載一個數(shù)據(jù)塊，則選中該Torrent網(wǎng)絡(luò)中任一節(jié)點的概率為1/N，該節(jié)點位于ISP1的概率為I/N，位于ISP1外部的概率為E/N。因此，對ISP1來說，造成跨ISP流量的概率為E/N，即與該Torrent文件相關(guān)的跨ISP流量所占的比例為E/N。通常N遠大于I，則(N?I)/N趨近于1，從而跨ISP流量所占的比例相當大。

在帶偏鄰居分配策略中，節(jié)點被選擇作為鄰居節(jié)點的概率是不等的。為了降低跨ISP流量，顯然應(yīng)該為同一ISP內(nèi)的節(jié)點賦更高的概率。設(shè)選中同一ISP內(nèi)節(jié)點的概率為p，則選中其他ISP內(nèi)節(jié)點的概率為q=1?p，當p>q時，則實現(xiàn)帶偏鄰居分配。為了實現(xiàn)帶偏鄰居分配策略，本文采用一種候選鄰居表的途徑從全局節(jié)點中抽取符合要求的候選鄰居，然后在候選鄰居中實現(xiàn)隨機分配。因此，需要解決的關(guān)鍵問題是如何構(gòu)建候選鄰居表，該表可決定每個節(jié)點被選中的概率。針對ISP1，Tracker節(jié)點維護一張候選鄰居表，其中包含I個ISP1中的節(jié)點和R(R

3 STracker的設(shè)計

本文設(shè)計STracker實現(xiàn)上述帶偏鄰居分配策略，STracker以Tracker代理的方式運行，構(gòu)建并維護合理的候選鄰居表，實現(xiàn)全局的帶偏鄰居分配。在ISP網(wǎng)絡(luò)中設(shè)置Tracker代理，該代理響應(yīng)該ISP中所有BitTorrent客戶端的鄰居分配請求。不同ISP中的Tracker代理以P2P方式連接，構(gòu)成一個Tracker代理的P2P網(wǎng)絡(luò)，如圖2所示，Tracker代理TP1，TP2，TP3和TP4連接成一個P2P網(wǎng)絡(luò)，通過該網(wǎng)絡(luò)分布式維護全局的BitTorrent節(jié)點信息。節(jié)點之間周期性進行通信，完成鄰居表的更新。BitTorrent客戶端通過配置其所在ISP的TP的地址完成將鄰居請求發(fā)送給其所屬的TP而不是Torrent文件中的Tracker地址，TP根據(jù)對應(yīng)的Torrent文件訪問原始的Tracker獲取外部的節(jié)點，構(gòu)建對應(yīng)于該Torrent文件的鄰居候選表。

圖2 STracker體系結(jié)構(gòu)

每個TP維護一個候選鄰居表，該表分為兩個部分，其一為LI，用于維護當前ISP內(nèi)的peer節(jié)點，另一為LE用于維護外部節(jié)點。TP節(jié)點之間需要周期性傳播節(jié)點信息，用于更新接收節(jié)點的鄰居表。STracker采用push-gossip的方法傳播節(jié)點信息，每個TP節(jié)點周期性地將融合后的節(jié)點信息推送給一個隨機節(jié)點；接收節(jié)點收到節(jié)點信息后，融合本地LE表，并隨機選擇其中一部分作為新的LE表。具體算法如算法1和2所示，其中t為一個全局參數(shù)，|LE|表示LE表的大小，random_select()用于從指定的表中隨機選取指定數(shù)量的節(jié)點。

在實際部署中，STracker存在“某些ISP沒有部署TP”和“如何激勵BitTorrent客戶端采用Tracker代理模式”兩個問題。但該兩問題均可以很好地被解決。圖2所示的STracker是一種理想情況，部署Tracker代理的條件下，BitTorrent客戶端直接通過各自的TP就可以獲得鄰居節(jié)點，在整個網(wǎng)絡(luò)范圍內(nèi)，均無需其他單獨的Tracker節(jié)點完成鄰居分配。當網(wǎng)絡(luò)中存在獨立的Tracker節(jié)點時，TP節(jié)點可以通過相應(yīng)的Torrent文件獲得Tracker節(jié)點的URL并訪問Tracker節(jié)點，從而獲得一定數(shù)量的節(jié)點信息，然后將這些節(jié)點加入到鄰居表的LE表中。對ISP來說，采用TP節(jié)點能夠有效降低運營成本，提高網(wǎng)絡(luò)效率，因此，ISP部署TP節(jié)點是可以得到回報的。對于BitTorrent客戶端，使用TP并不一定能帶來下載性能的提高，因此，需要設(shè)計相應(yīng)的機制激勵用戶采用TP。ISP可以采用數(shù)據(jù)包重定向策略來引導用戶采用TP，在ISP的網(wǎng)絡(luò)邊界，對所有進出的Tracker協(xié)議數(shù)據(jù)包，均重定向到TP，由TP來完成鄰居分配工作。該方案基于網(wǎng)絡(luò)協(xié)議識別技術(shù)[12-13]，可以很好地工作。

4 性能評估

根據(jù)前文的分析，STracker是一個可行的BitTorrent流量優(yōu)化方案，本文通過模擬途徑進一步對STracker的性能進行評估。模擬過程中關(guān)注的主要指標包括TP節(jié)點構(gòu)建候選鄰居表的性能、跨ISP流量和BitTorrent客戶端的內(nèi)容下載時間。

Tracker代理之間以P2P方式連接，本身構(gòu)成一個P2P網(wǎng)絡(luò)。本文模擬過程中采用Gnutella協(xié)議[14]構(gòu)建TP網(wǎng)絡(luò)，分別模擬了1 000、3 000和5 000個節(jié)點的冪律隨機圖。初始條件下，每個節(jié)點的候選鄰居表只包含一個本ISP內(nèi)部的候選鄰居。在每個循環(huán)中，當前節(jié)點隨機選擇一個鄰居節(jié)點，合并兩個節(jié)點的候選鄰居表，將合并后的表作為該鄰居節(jié)點的候選鄰居表。上述過程模擬TP節(jié)點的新候選鄰居節(jié)點如何快速混合到其他TP節(jié)點的外部鄰居表中。模擬過程中，首先觀察需要多少周期才能夠有效混合外部鄰居節(jié)點，即外部鄰居節(jié)點如何大致分布在不同的ISP的TP中。候選鄰居節(jié)點的有效混合是以每個TP節(jié)點中所緩存的不同候選鄰居的數(shù)量度量的，即觀察模擬過程中，經(jīng)過多少時間，TP節(jié)點的不同候選鄰居數(shù)量趨于收斂。模擬結(jié)果如圖3所示，根據(jù)圖示，10個周期后，鄰居表的規(guī)模迅速增長；15個周期后，基本達到收斂。因此，采用push-gossip算法能夠快速傳播候選鄰居信息，有助于實現(xiàn)外部鄰居選擇的隨機性。

圖3 TP鄰居表收斂速度

完成鄰居分配之后，資源共享的性能成為關(guān)注的另一個指標。通常，對P2P客戶端來說，共享的性能指下載一個大文件所需的時間，時間越短，用戶的體驗越好。因此，需要對比隨機鄰居分配策略和STracker的帶偏鄰居分配策略。帶偏鄰居分配的目的之一是降低跨ISP流量，因此跨ISP流量是模擬過程需要關(guān)注的指標之一。模擬過程中，共享文件的大小為10 000個分塊，初始網(wǎng)絡(luò)規(guī)模為10個節(jié)點，每個節(jié)點獲得50個隨機分塊。隨著節(jié)點的動態(tài)加入，觀察整個系統(tǒng)中的跨ISP流量和獲得全部分塊的節(jié)點數(shù)量。系統(tǒng)獲得全部分塊的節(jié)點數(shù)量與時間變化的關(guān)系即下載速度的對比如圖4所示。根據(jù)圖4所示，帶偏鄰居分配策略具有與隨機鄰居分配策略相當?shù)南螺d速度?？鏘SP流量對比如圖5所示。由圖可見，帶偏鄰居分配大大降低了跨ISP流量。

根據(jù)上述模擬結(jié)果可以發(fā)現(xiàn)，STracker能夠有效降低跨ISP流量且不增加資源下載的時間，因此能夠有效提高網(wǎng)絡(luò)的效率和降低ISP的運營成本。

圖4 下載速度對比

圖5 跨ISP流量對比

5 結(jié) 束 語

BitTorrent流量是互聯(lián)網(wǎng)流量的主要組成部分，對網(wǎng)絡(luò)的性能和效率具有重要的影響。BitTorrent協(xié)議中，隨機鄰居分配策略導致大量的跨ISP冗余流量，而帶偏鄰居分配是解決跨ISP流量的有效策略。在分析帶偏鄰居分配策略的基礎(chǔ)上，本文提出了ISP感知的BitTorrent流量優(yōu)化方案STracker。STracker由位于不同ISP的Tracker代理構(gòu)成，Tracker代理之間以P2P方式連接，通過push-gossip協(xié)議實現(xiàn)候選鄰居節(jié)點維護。Tracker代理的鄰居分配算法決定了節(jié)點的大部分鄰居位于當前ISP之內(nèi)，而小部分節(jié)點位于當前ISP之外，從而實現(xiàn)帶偏鄰居分配功能。模擬結(jié)果表明，STracker能夠有效維護候選鄰居，從而降低跨ISP流量。STracker的另一個優(yōu)點是只需對當前BitTorrent客戶端做較小的修改甚至無需修改就能夠很好地運行。STracker的提出有效解決了當前BitTorrent流量優(yōu)化所面臨的難題。

[1] 秦志光, 羅緒成. P2P共享系統(tǒng)中無需專用ttp的公平交換協(xié)議[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] 楊戈, 廖建新, 朱曉民, 等. 面向?qū)Φ染W(wǎng)絡(luò)的流媒體接納控制[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.