一種可控P2P文件下載算法*

龐 濤，黃 海，龍 斌，武 娟

（中國電信股份有限公司廣東研究院 廣州 510630）

一種可控P2P文件下載算法*

龐 濤，黃 海，龍 斌，武 娟

（中國電信股份有限公司廣東研究院 廣州 510630）

以BitTorrent為代表的對等網(wǎng)絡(luò)文件下載時存在帶寬吞噬的難題，如何實現(xiàn)可控傳輸是這類應(yīng)用可持續(xù)發(fā)展的必要條件。本文基于電信新業(yè)務(wù)平臺——媒體電信網(wǎng)對可控傳輸?shù)男枨螅岢鲆环N可控性對等網(wǎng)絡(luò)文件下載算法，采用集中式目錄服務(wù)器傳輸調(diào)度有效限制骨干網(wǎng)負載流量；同時利用基于對等技術(shù)的分布式傳輸，采用空閑終端和補償服務(wù)器相結(jié)合的策略進行補償傳輸，以保持不低于BitTorrent的下載速率?；赑DNS的數(shù)據(jù)包級大規(guī)模網(wǎng)絡(luò)并行仿真結(jié)果證明了所提出算法的有效性，其綜合性能優(yōu)于BitTorrent算法。

可控對等網(wǎng)；P2P文件下載；BitTorrent協(xié)議；對等節(jié)點

*國家發(fā)改委CNGI示范工程2006年產(chǎn)業(yè)化及應(yīng)用試驗資助項目

1 引言

以BitTorrent[1]（BT）為典型代表的P2P文件下載算法帶給了用戶高速下載的體驗，但其存在的不可控性造成“帶寬吞噬”問題，其造成的擁塞極大降低其他未使用P2P業(yè)務(wù)的上網(wǎng)速度。同時，由于BT基于應(yīng)用層，缺少對物理拓撲的意識，容易造成骨干網(wǎng)上大量重復(fù)流量，對資源的利用率造成極大的浪費，對網(wǎng)絡(luò)運營商而言極大降低產(chǎn)出投入比。

為解決BT的不可控性，急需提出具有“可控性”的P2P文件下載新算法?？煽匦缘暮x主要包括：（1）流量可控，指對P2P流量實施合理調(diào)度，尤其是減少骨干網(wǎng)中不必要的重復(fù)流量；（2）下載速率可控，即新算法的性能不能低于BT，否則用戶不會選擇；（3）版權(quán)可控；（4）計費可控。后二者是P2P能否大規(guī)模商業(yè)化應(yīng)用的關(guān)鍵。

本文以CNGI實際項目為背景，基于電信新業(yè)務(wù)平臺的網(wǎng)絡(luò)架構(gòu)——媒體電信網(wǎng) （media telecom network，MTN）[2]，提出一種基于MTN具有可控性的P2P文件下載新算法（簡稱MTN算法）。MTN分層框架如圖1所示，主要包括運營支撐層、業(yè)務(wù)應(yīng)用層、業(yè)務(wù)控制層和網(wǎng)絡(luò)承載層。業(yè)務(wù)應(yīng)用層中包括數(shù)字版權(quán)管理系統(tǒng)，負責(zé)解決困擾P2P商業(yè)化應(yīng)用的版權(quán)問題，同時支持可控P2P下載、可控P2P直播和可控P2P點播算法；業(yè)務(wù)控制層負責(zé)資源的調(diào)度和管理，比如在本算法中要用到的服務(wù)器的管理；運營支撐層負責(zé)統(tǒng)計、計費等管理；網(wǎng)絡(luò)承載層則負責(zé)網(wǎng)絡(luò)接入。MTN框架中已充分考慮版權(quán)和計費可控問題，本文算法重點解決可控性前兩個方面的問題。

對可控性第一方面的研究比較多（見§2），主要集中在P2P流量局域化方面，但未兼顧可控性的第二方面。若僅考慮P2P流量局域化，可能會降低P2P文件下載的平均速率，其原因分析如下：P2P流量局域化主要是控制對等節(jié)點（Peer）盡量從本域的鄰居對等節(jié)點獲取消息，當域內(nèi)含有文件所有分塊（Block或Piece）的時候，域內(nèi)的對等節(jié)點的下載速率顯然會比較快；但當局域內(nèi)無法提供所有分塊的時候，有一部分分塊需要從外域鄰居節(jié)點獲取，但為了流量局域化，會限制一部分本域的對等節(jié)點從外域獲得分塊。這樣從整體來看，存在對等節(jié)點可能獲取分塊的范圍比原始BT協(xié)議中的對等節(jié)點獲取分塊的范圍小，所以其帶寬利用率沒有得到充分的利用，從而局域化后的整個P2P會話的平均速率會有所降低，所以需要采取新的策略對下載速率進行有效補償。

綜上所述，本文提出的可控P2P文件下載新算法不僅考慮流量的局域化，而且利用空閑資源來進行速率補償，其中對物理拓撲的信息可以直接利用電信運營商的數(shù)據(jù)庫獲得，電信的CDN網(wǎng)絡(luò)中已經(jīng)部署很多服務(wù)器，這些服務(wù)器資源可以用于控制和調(diào)度的目錄服務(wù)器，而結(jié)合MTN的具體要求，電信運營商需要提供一個特別設(shè)計的MTN客戶端程序，當MTN終端處于空閑狀態(tài)的時候，可以被目錄服務(wù)器加以調(diào)度，從而對下載速率進行補償。同時，電信的服務(wù)器也可以用作補償服務(wù)器，即當空閑終端資源不足于調(diào)度的時候，補償服務(wù)器加入到調(diào)度補償?shù)娜蝿?wù)中。這樣也可以充分利用網(wǎng)絡(luò)的資源，減少服務(wù)器的壓力。另外，MTN網(wǎng)絡(luò)中有相應(yīng)的激勵機制（如積分機制），可以保證當某個節(jié)點作為空閑終端使用后，其積分會隨著上傳速率相應(yīng)增加，當該節(jié)點進行P2P下載時，可以獲得較大的概率（以相應(yīng)比例）被疏通。

2 相關(guān)工作

對可控性第一方面（即流量局域化）的研究，是針對網(wǎng)絡(luò)層和應(yīng)用層的拓撲不一致問題（也稱為拓撲失配問題[3～4]），可分兩類：P2P 文件下載和 P2P 流媒體，雖本文側(cè)重P2P文件下載，但流量局域化的技術(shù)是可以通用的。

P2P流媒體中流量局域化技術(shù)：Anysee和Nearcast等[5]采用地標（Landmark）的機制解決流量局域化的問題，地標是一個56位數(shù)據(jù)類型的值，由地理位置與IP的對應(yīng)關(guān)系和一定的編碼規(guī)則產(chǎn)生，作為調(diào)度路徑上的“路標”。Li[6]提出4層分層的相鄰關(guān)系，通過各自級別的目錄服務(wù)器來控制流量的局域化。

P2P文件下載中流量局域化的研究也可分為以下兩類。（1）針對有結(jié)構(gòu)化的研究，例如Plethora是針對分布式哈希表（DHT）查找的改進[7]，分2個覆蓋層：全局和局部覆蓋層，其中局部覆蓋層是相當于全局覆蓋層的一個緩存，該緩存根據(jù)地理遠近特征進行聯(lián)合調(diào)度。（2）針對無結(jié)構(gòu)化的 P2P，例如針對 BT、Gnutella 等協(xié)議的改進[8～12]。當前由運營商推出的P2P流量局域化改進是P4P[8]，利用本地iTracker和統(tǒng)一的appTracker來負責(zé)對等節(jié)點的選擇，以保證流量的局域化以及系統(tǒng)的信息傳遞。Bindal等[9]提出有偏向的對等節(jié)點選擇算法，其主要思想是：若有N個鄰居，N－k個從同一個ISP中選擇，而其余k個從外面隨機選擇。參考文獻[10]計算所有的近鄰對等節(jié)點之間的片段融合度，一旦發(fā)現(xiàn)它們可以構(gòu)成一個完整的對等節(jié)點群時，馬上停止從外網(wǎng)下載片段，從而實現(xiàn)流量局域化。參考文獻[11]提出基于鄰近節(jié)點聚類方法，并利用基于馬爾可夫鏈的流體數(shù)學(xué)模型從理論上證明了層次化結(jié)構(gòu)的BT系統(tǒng)比原BT系統(tǒng)具有更好的文件共享性能。參考文獻[12]將網(wǎng)絡(luò)編碼（network coding）新技術(shù)應(yīng)用到P2P文件下載，并且采用時延探測的流量局域化技術(shù)，仿真結(jié)果顯示優(yōu)于未采用網(wǎng)絡(luò)編碼的Narada，但局限于一類特殊的組合網(wǎng)絡(luò)（combination network）。

本文設(shè)計的具有可控性的P2P文件下載算法，與現(xiàn)有研究的不同之處如下。

·相關(guān)研究關(guān)于流量局域化的工作，主要闡述如何獲得局域的物理拓撲意識，僅限于可控性的第一個方面；而本文基于MTN，可直接從電信網(wǎng)絡(luò)數(shù)據(jù)庫獲得物理拓撲的相關(guān)信息，因此本文重點探討如何從域外取分塊和從域內(nèi)取分塊最優(yōu)動態(tài)調(diào)度，達到既控制骨干網(wǎng)的流量，又盡量減少因?qū)2P施控造成的速率下降。

·現(xiàn)有研究未考慮可控性的第二個方面，本文則利用帶有激勵機制的空閑終端并結(jié)合補償服務(wù)器來共同補償因?qū)2P施控造成的速率下降問題，該補償可以使得MTN算法在保證流量局域化基礎(chǔ)上，下載速率可以比BT性能更好，該算法有效支持對等節(jié)點高動態(tài)加入/離開。

·本文算法基于MTN框架，可支持版權(quán)管理和流量計費，雖然后者超出本文討論范圍，但與本文算法結(jié)合后可以實現(xiàn)較完整意義上的可控P2P文件下載。

3 算法詳述

本文算法基于MTN的分層框架，在對用戶資源管理時，采用了對等組（group）、域（area）兩級管理方式。

對等組：針對某一特定內(nèi)容源、由對等節(jié)點建立的共享團體，形成的一個傳遞特定內(nèi)容源的虛擬的交互平臺。一個有用戶使用著的內(nèi)容源通常對應(yīng)著一個對等組號。比如，當所有對等節(jié)點下載某個文件時，則這些對等節(jié)點將具有一個相同的對等組號。若某對等節(jié)點沒有任何一個對等組號，意味著這個節(jié)點暫時沒有下載任何的文件，稱為“空閑MTN終端”。

域：由于同一時間共享一個內(nèi)容的用戶數(shù)量可能很多，為了進一步減輕目錄服務(wù)器的壓力，提供用戶間共享的效率，將對等組內(nèi)對等節(jié)點根據(jù)一定規(guī)則（如地域、加入次序等）組成更小粒度的通信團體。不同范圍的域由不同級別的服務(wù)器來管理。

基于MTN的分層網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。主要的網(wǎng)絡(luò)元素包括：二層目錄服務(wù)器，包括RM（resource manager）和DR（designed RM），RM是第一級的資源管理中心，負責(zé)全局的資源管理、控制和負載均衡；DR是第二級的資源管理節(jié)點，負責(zé)局部域內(nèi)的資源管理、控制和負載均衡。補償服務(wù)器，由電信運營商廣泛部署的CDN資源構(gòu)成，可以在MTN中作為下載速率補償。MTN終端（活躍MTN終端和空閑MTN終端，前者具有某個對等組號，而后者沒有對等組號）。RM通過和DR交互獲取MTN所有范圍內(nèi)的內(nèi)容信息，而DR通過與MTN終端交互獲得局部的內(nèi)容信息。下載內(nèi)容是分布式存儲在中心服務(wù)器和邊緣服務(wù)器以及所有MTN終端上?？臻eMTN終端在一定激勵機制下，共享一部分資源（CPU計算資源、存儲資源、帶寬等），由RM/DR統(tǒng)一調(diào)度和管理，共同實現(xiàn)高速下載的目的。

本算法的詳細設(shè)計思想包括以下三點。

（1）流量局域化和內(nèi)容均衡聯(lián)合設(shè)計的P2P傳輸可控機制

其一，流量局域化是通過充分利用電信所擁有的IP數(shù)據(jù)庫信息得到的，與BT不同的是本算法中目錄服務(wù)器需要增加位圖（BitField，位圖中的每個比特用于標記分塊的擁有情況）來掌握域內(nèi)的分塊內(nèi)容的擁有情況，從而有效地進行調(diào)度。仿真實驗證明對RM/DR的壓力是在合理范圍內(nèi)。其二，單獨保證流量局域化可能會降低下載速度，而單獨考慮基于稀有優(yōu)先（即采用純BT機制）的內(nèi)容均衡又會導(dǎo)致流量在骨干網(wǎng)上的對沖，針對此矛盾，將二者結(jié)合起來考慮，在目錄服務(wù)器中采用自適應(yīng)多階段的推送機制，可分為非穩(wěn)定階段和穩(wěn)定階段，在穩(wěn)定階段采用流量局域化原則，而在非穩(wěn)定階段則可以采用快取原則，即不一定遵循流量局域化的原則，只要能夠盡快獲取內(nèi)容即可。這兩個階段由中心服務(wù)器控制自適應(yīng)地切換。中心目錄服務(wù)器管理網(wǎng)絡(luò)中所有對等節(jié)點獲取其他對等節(jié)點信息來控制MTN骨干網(wǎng)流量；管理和調(diào)度網(wǎng)絡(luò)中的空閑資源，實施相應(yīng)的積分激勵機制，并利用空閑資源和補償服務(wù)器結(jié)合來補償下載速率的下降。目錄管理服務(wù)器一般采用分級分層結(jié)構(gòu)。

（2）基于空閑終端和補償服務(wù)器的補償加速技術(shù)

通過目錄服務(wù)器發(fā)現(xiàn)、更新和管理空閑資源，并調(diào)度空閑終端和補償服務(wù)器來補償和加速MTN的下載速度，具體調(diào)度原則是盡量利用空閑資源來補償下載速率，當空閑資源不足時才調(diào)用電信部門部署的補償服務(wù)器的資源，以盡量減少補償服務(wù)器的壓力，有效改善資源投入產(chǎn)出比。

（3）基于積分激勵機制的阻塞和疏通技術(shù)

采用積分機制來激勵對等用戶提供出盡可能多的空閑資源，而且將積分機制設(shè)計到MTN下載算法的阻塞和疏通算法中。其中積分機制是由目錄服務(wù)器實現(xiàn)。

3.1 目錄服務(wù)器端算法

首先介紹目錄服務(wù)器中的算法細節(jié)。

為便于查找和推送，在目錄服務(wù)器中的對等節(jié)點清單（Peerlist，某個對等節(jié)點的所有鄰居對等節(jié)點IP列表）的結(jié)構(gòu)為：對等組號→種子IP→非種子節(jié)點IP→空閑節(jié)點IP。其中種子節(jié)點定義為含有所有的文件分塊，其位圖中比特均為1。目錄服務(wù)器中設(shè)置“域位圖”，用于監(jiān)控本域分塊的分步情況。

目錄服務(wù)器中的流程如下。

①對首次加入的節(jié)點，分配目錄服務(wù)器DR。

②將對等節(jié)點的位圖與目錄服務(wù)器的位圖進行 “或”操作，并將收到的注冊IP分類加入對等節(jié)點清單。

③對客戶端的請求，根據(jù)最優(yōu)原則（該子網(wǎng)對等節(jié)點清單中種子和非種子IP清單中隨機選?。┻x10個回復(fù)給客戶端。當域位圖非全1階段（意味著本域沒有所有的分塊，需要從外域請求一部分分塊），分二個階段，啟動階段先隨機推送對等節(jié)點清單，然后按域位圖中1的比例推送；穩(wěn)定階段，當域位圖全1后采用本地優(yōu)先。其中，當域位圖出現(xiàn)空缺（如有節(jié)點離開）則利用空閑終端和補償服務(wù)器結(jié)合的機制來補償。

④對離開網(wǎng)絡(luò)的客戶端離開消息，將客戶端IP從對等節(jié)點清單中刪除；若此時該客戶端的子網(wǎng)對等節(jié)點清單中不存在種子，則將該子網(wǎng)中的位圖相應(yīng)離開的分塊位置上清零。

⑤若定時（30 s）重連目錄服務(wù)器時間到，執(zhí)行②。

⑥對稀有分塊的處理：定時（180 s）檢查域位圖，如果某個分塊為零的時間超過某個閾值（30 s），啟動到鄰域的目錄服務(wù)器中去取10個IP（可能包括種子），將該IP主動推送給空閑終端，由空閑終端負責(zé)下載該分塊（若沒有空閑終端，則推送給補償服務(wù)器加以實施）?？臻e終端在10個鄰域的對等節(jié)點清單中直接去申請所需的稀有片斷（此處就是要求目錄服務(wù)器給空閑終端發(fā)位圖）。

3.2 MTN客戶端算法

每個對等節(jié)點的下載算法細節(jié)（如圖3所示）如下。

①MTN客戶端進入網(wǎng)絡(luò)，向中心服務(wù)器注冊并發(fā)送下載請求，其中包括客戶端ID、端口號、需要下載的文件名等，中心服務(wù)器將這個新加入的節(jié)點的信息添加到對等節(jié)點列表中，然后根據(jù)最優(yōu)原則（包括本地化最優(yōu)原則、負載均衡原則等）回復(fù)MTN客戶端請求。中心服務(wù)器為該MTN客戶端提供具有最優(yōu)的對等節(jié)點清單來回復(fù)請求。

②MTN客戶端找出對等節(jié)點清單中擁有自己所需要下載文件的鄰居節(jié)點，并向它們發(fā)送下載請求。

③收到請求的對等節(jié)點向MTN客戶端發(fā)送握手信息以及它擁有的文件的位圖。MTN客戶端通過隨機優(yōu)先算法開始下載，其間它每30 s向DR發(fā)送一次信息，匯報自己的下載情況。中心服務(wù)器也即時更新其對等節(jié)點清單。在下載過程中，要用到稀有優(yōu)先算法、嚴格優(yōu)先算法、抵制怠慢算法和Tit-for-Tat激勵機制，其原則同BT算法。但阻塞算法、樂觀疏通算法有較大改進，通過利用積分機制，當空閑終端在傳輸?shù)臅r候，其積分將增加。在樂觀疏通的時候，對空閑終端的不同積分進行不同的樂觀疏通。在阻塞的時候，當上傳下載速率相同時，積分多的優(yōu)先被疏通，反之則被阻塞。

④當尚未下載的分塊數(shù)小于連接的對等節(jié)點數(shù)時，MTN客戶端進入最后模式，并繼續(xù)下載直至下載完畢。

⑤下載完畢后，MTN客戶端向中心服務(wù)器發(fā)送下載完畢信息，開始做種子。中心服務(wù)器則更新對等節(jié)點清單，將客戶端設(shè)為種子節(jié)點。當MTN客戶端將離開網(wǎng)絡(luò)，向中心服務(wù)器發(fā)送離開信息，中心服務(wù)器則將此節(jié)點信息從對等節(jié)點清單中刪除，并更新其域位圖信息。

為了保證空閑終端愿意貢獻資源，需要相應(yīng)的激勵機制，本文提出一種積分機制，通過修正阻塞算法和樂觀疏通算法來實現(xiàn)，由中心服務(wù)器負責(zé)管理：為每一個分塊的請求分配一個優(yōu)先級，空閑終端的分塊請求消息為高優(yōu)先級，其余的為低優(yōu)先級。對等節(jié)點在執(zhí)行樂觀疏通算法時，高優(yōu)先級的請求將會有兩倍于低優(yōu)先級的請求機會被響應(yīng)。

在每10 s執(zhí)行一次的阻塞算法中，在被阻塞的對等節(jié)點中找出貢獻比最大的對等節(jié)點（記為P1），其中貢獻比定義為一個對等節(jié)點的總上傳量與總下載量的比；在被疏通的4個對等節(jié)點中找出貢獻比最小的對等節(jié)點（記為P2）；比較P1和P2的貢獻，疏通貢獻比較大者，阻塞貢獻較小者。

在每30 s執(zhí)行一次的樂觀疏通算法中分為3步：①鄰居對等節(jié)點分類。根據(jù)分塊請求隊列將鄰居對等節(jié)點分成三類，第一類是請求隊列為空的鄰居對等節(jié)點，請求隊列為空說明本地對等節(jié)點沒有對方對等節(jié)點感興趣的數(shù)據(jù)；第二類是低優(yōu)先級的普通對等節(jié)點，這些對等節(jié)點目前可以從其他的鄰居處獲得數(shù)據(jù)，因此它們發(fā)出的請求消息是低優(yōu)先級的；第三類是空閑終端，即對應(yīng)分塊請求隊列中的消息為高優(yōu)先級。②為上述三類節(jié)點分配樂觀疏通的概率。對于第一類對等節(jié)點，直接阻塞，不參加樂觀疏通的競爭，依照規(guī)模和消息的優(yōu)先級分配第二類和第三類對等節(jié)點獲得樂觀疏通的概率，擁有高優(yōu)先級的第三類對等節(jié)點獲得樂觀疏通的平均幾率是第二類的2倍。③為每類中的對等節(jié)點分配樂觀疏通的概率。第二類對等節(jié)點中優(yōu)先級相同，因此等概率地分配第二類中的每一個對等節(jié)點；在第三類對等節(jié)點中引入積分機制，按照第三類中每一個對等節(jié)點的貢獻在所有第三類對等節(jié)點的貢獻中所占的比例，分配每一個對等節(jié)點獲得樂觀疏通的概率。

4 網(wǎng)絡(luò)仿真結(jié)果及分析

仿真的網(wǎng)絡(luò)場景包括：均勻加入和突發(fā)加入，節(jié)點下載完畢后在0～600 s中隨機離開，6種不同節(jié)點規(guī)模。仿真拓撲采用現(xiàn)網(wǎng)拓撲和隨機拓撲。仿真下載文件大小為25 MB，共采用8臺仿真服務(wù)器，最大為4 800個對等節(jié)點。

現(xiàn)網(wǎng)拓撲是為了仿真基于MTN網(wǎng)絡(luò)的分層拓撲結(jié)構(gòu)。第一層：模擬MTN網(wǎng)絡(luò)的核心層，帶寬10 Gbit/s，8個路由節(jié)點，采用全連接（full-mesh）結(jié)構(gòu)相連；第二層：模擬MTN網(wǎng)絡(luò)的匯接層，與第一層路由節(jié)點之間相連的鏈路帶寬為2.5 Gbit/s，每個第一層路由節(jié)點連接4～6個第二層路由節(jié)點，第二層路由節(jié)點以第一層路由節(jié)點為核心采用星型拓撲相連；第三層：與第二層節(jié)點相連的鏈路為10 Mbit/s的 Ethernet或者 ADSL 鏈路（1 Mbit/s/512 kbit/s），每個第二層路由節(jié)點連接100個第三層主機節(jié)點，ADSL鏈路的比例為70%。特殊節(jié)點包括：目錄服務(wù)器（Tracker）（以1 Gbit/s的帶寬與第二層路由節(jié)點之間相連）；種子節(jié)點（Seed）（從第三層的主機節(jié)點中隨機選擇一個）。隨機拓撲則是由8臺仿真服務(wù)器采用GT-ITM或BRITE隨機生成，每臺服務(wù)器仿真的子網(wǎng)之間采用全連接方式。

具體的性能參數(shù)包括：平均下載時間、骨干鏈路吞吐量和目錄服務(wù)器的壓力。平均下載時間的定義為：∑Peer下載時間/對等節(jié)點總數(shù)；骨干鏈路吞吐量定義為骨干網(wǎng)上所有匯聚節(jié)點的流出流量之和；目錄服務(wù)器壓力是采用目錄服務(wù)器的流量來定義的。

4.1 平均下載時間

由圖4可以看出MTN下載算法在對等節(jié)點均勻加入的情況下，完成下載的平均時間在310 s到330 s之間，隨著總節(jié)點數(shù)從2 800到4 800呈現(xiàn)略有下降的趨勢，反映P2P下載在一定規(guī)模下，節(jié)點越多下載越快的特性；而BT算法完成下載的平均下載時間在340 s到430 s之間，其下載時間在2 800到3 600、4 000到4 400節(jié)點期間是下降趨勢，反映在一定規(guī)模下BT下載節(jié)點越多下載越快的特性，其呈現(xiàn)上升的情況是因為到一定節(jié)點數(shù)目，會有一定的擁塞情況，下載時間會有一定上升。對比MTN算法和BT算法，MTN下載的完成時間比BT算法少了近15%。

圖5是MTN下載算法和BT算法在隨機拓撲網(wǎng)絡(luò)（突發(fā)加入）場景中的對等節(jié)點完成下載的平均時間隨總節(jié)點數(shù)變化的曲線。從圖5可以看出在隨機網(wǎng)絡(luò)中，MTN的平均下載時間與BT的相比要快20%左右，其原因是：在隨機網(wǎng)絡(luò)中，從源對等節(jié)點傳送的數(shù)據(jù)包需要經(jīng)過多個路由節(jié)點才能到達目的對等節(jié)點，傳輸路徑中經(jīng)過的路由節(jié)點越多，傳輸?shù)臅r延也就越大，這樣一來MTN下載算法的本地流量優(yōu)先策略將會極大增強文件下載的速度，由于本地網(wǎng)絡(luò)中的對等節(jié)點一般只通過1個或者少數(shù)幾個路由節(jié)點相連接，所以只要本地網(wǎng)絡(luò)內(nèi)存在一份完整的文件拷貝，本地網(wǎng)絡(luò)的所有對等節(jié)點可以在很短的時間內(nèi)得到文件的所有片斷。可見，在隨機拓撲中本地化的優(yōu)勢更明顯一些。在現(xiàn)網(wǎng)拓撲中，MTN和BT的跳數(shù)比較接近，所以本地化的優(yōu)勢沒有隨機拓撲中明顯。

4.2 骨干網(wǎng)鏈路吞吐量

圖6是BT和MTN 在有隨機離開的場景中骨干網(wǎng)吞吐量與節(jié)點規(guī)模的變化關(guān)系。比較在均勻加入和突發(fā)加入兩種場景下的BT骨干網(wǎng)吞吐量，前者要遠小于后者（前者約為后者的1/10）；而對于MTN而言，兩種場景下的骨干網(wǎng)鏈路吞吐量相差不大（前者約為后者的1/2），且在均勻加入和突發(fā)加入兩種場景下，MTN骨干網(wǎng)鏈路吞吐量均小于BT骨干網(wǎng)鏈路的吞吐量，這些結(jié)果驗證了MTN下載算法與BT協(xié)議相比能夠在很大程度上減少骨干鏈路的吞吐量，尤其值得一提的是，當節(jié)點加入網(wǎng)絡(luò)的突發(fā)程度越高，MTN對骨干鏈路吞吐量的優(yōu)化效果就越好。骨干鏈路的吞吐量基本不隨網(wǎng)絡(luò)節(jié)點規(guī)模的增加而變化，吞吐量的波動均在10%以內(nèi)，這是因為當節(jié)點規(guī)模在不停增加時，單位時間內(nèi)加入節(jié)點的數(shù)目保持不變，所以骨干網(wǎng)的流量基本保持不變。

圖7是網(wǎng)絡(luò)規(guī)模為4 800個對等節(jié)點的現(xiàn)網(wǎng)拓撲下，骨干網(wǎng)鏈路流量隨時間變化的曲線。由圖7可以看出，在4 800個對等節(jié)點均勻加入隨機離開的場景中，BT算法的骨干鏈路流量最高到達25 Mbit/s，平均在20 Mbit/s；而MTN下載算法的骨干鏈路流量在10 Mbit/s以內(nèi)，且在1 000 s后維持在5 Mbit/s左右?？梢奙TN下載的本地流量化得到很顯著的效果。

圖8給出現(xiàn)網(wǎng)拓撲中BT和MTN分別在突發(fā)加入方式下的骨干網(wǎng)鏈路流量變化情況，對等節(jié)點在完成下載后0～600 s隨機離開，由圖8可以看出，在4 800個對等節(jié)點突發(fā)加入隨機離開的場景中，BT算法的骨干鏈路流量最高到達200 Mbit/s；而MTN文件共享算法的骨干鏈路流量在50 Mbit/s以內(nèi)，且在250 s后維持在30 Mbit/s左右。MTN文件共享的本地流量化得到很顯著的效果。

4.3 目錄服務(wù)器壓力

圖9和圖10是4 800個對等節(jié)點突發(fā)加入、隨機離開時，拓撲結(jié)構(gòu)分別為現(xiàn)網(wǎng)拓撲和隨機拓撲的目錄服務(wù)器的壓力情況?？梢钥闯鲈? 800個對等節(jié)點突發(fā)加入并在0到600 s內(nèi)隨機離開的場景下，在現(xiàn)網(wǎng)和隨機拓撲中，MTN下載算法對目錄服務(wù)器的壓力比BT算法高，因為在MTN下載算法中，目錄服務(wù)器和對等節(jié)點間交互的信息更多。MTN下載算法中，目錄服務(wù)器壓力最高數(shù)量級只是2 kbit/s級別，仿真實驗的文件大小是25 MB，此處采用了一個DR服務(wù)器，按一般DVD質(zhì)量的視頻文件800 MB大小來計算，4 800節(jié)點服務(wù)器的壓力約64 kbit/s的級別，按一般一個服務(wù)器支持2 400并發(fā)節(jié)點計算，壓力為32 kbit/s，一般服務(wù)器的帶寬至少是1 Gbit/s，可以計算得每個服務(wù)器在支持2 400并發(fā)節(jié)點的下載文件數(shù)為1 Gbit/s/32 kbit/s=4 000個文件，對電信的高性能服務(wù)器來說是可以接受的范圍，符合設(shè)計的需求。

5 結(jié)束語

本文針對媒體電信網(wǎng)（MTN）框架和需求，提出具有骨干流量可控、下載速率可控的可控P2P下載新算法，基于PDNS的大規(guī)模仿真結(jié)果證實了算法的有效性。與MTN框架中的版權(quán)管理和流量計費相結(jié)合后可以實現(xiàn)較完整意義上的可控P2P文件下載。

1 Cohen B.Incentives build robustness in bittorrent.In:Workshop on Economics of Peer-to-Peer Systems,CA,USA,2003

2 肖遂，張欣，田洪亮.基于P2P技術(shù)的媒體電信網(wǎng).通信世界網(wǎng)，2008年1月

3 Liu Y,Liu X,Xiao L,et al.Location-aware topology matching in P2P systems.In:IEEE INFOCOM’04,2004

4 Liu X,Liu Y,Xiao L,et al.Location awareness in unstructured peer-to-peer systems.IEEE Trans Parallel Distrib Syst,2005,16(2):163～174

5 Tu X,Jin H,Liao X,et al.Nearcast:a locality-aware P2P live streaming approach for distance education.ACM Trans Inter Tech,2008,8(2):1～23

6 Li J.Locality aware peer assisted delivery:the way to scale internet video to the world.In:Packet Video 2007

7 Ferreira R A,Jagannathan S,Grama A.Locality in structured peer-to-peer networks.J Parallel Distrib Comput,2006,66(2):257～273

8 Xie H,Yang Y R,Krishnamurthy A,et al.P4P:provider portal for applications.In:ACM Sigcomm 2008

9 Bindal R,Cao P,Chan W,et al.Improving traffic locality in bittorrent via biased neighbor selection.In:ICDCS 2006

10 歐陽榮，苗卉，雷振明.一種減少網(wǎng)間P2P流量的對等節(jié)點選擇算法.計算機工程，2008，34（8）：108～110

11 薛廣濤，俞嘉地，尤晉元.基于臨近結(jié)點聚類構(gòu)建層次化BitTorrent文件共享系統(tǒng).電子學(xué)報，2008，36（2）：291～297

12 Yang M,Yang Y.Peer-to-peer file sharing based on network coding.In:ICDCS'08

An Algorithm for Controllable P2P File Downloading

Pang Tao,Huang Hai,Long Bin,Wu Juan
(China Telecom Guangzhou Research Institute,Guangzhou 510630,China)

Bandwidth devouring has become a significant problem with P2P file downloading applications represented by BitTorrent(BT).Implementing controllable P2P transfer is a key for sustainable deployment of this type of service.This paper proposes a novel controllable P2P file downloading algorithm based on requirements of new Telecom service platform—Media Telecom Network (MTN).This algorithm adoptes centralized directory servers to effectively decrease traffic load of backbone networks.Meanwhile,taking advantage of distributed P2P transfer,the algorithm combines idle terminals and compensation servers to improve downloading rate,which is not worse than BT.Finally,large-scale simulations at packet level based on PDNS prove the effectiveness of the proposed algorithm and show its improvement in terms of overall performance upon BT.

controllable P2P network,P2P file downloading,BitTorrent,peer

2010-05-31）