龐 濤，黃 海，龍 斌，武 娟

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

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

龐 濤，黃 海，龍 斌，武 娟

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

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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3 算法詳述

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

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

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

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

本算法的詳細(xì)設(shè)計(jì)思想包括以下三點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 MTN客戶端算法

每個(gè)對(duì)等節(jié)點(diǎn)的下載算法細(xì)節(jié)（如圖3所示）如下。

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

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

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

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

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

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

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

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

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

仿真的網(wǎng)絡(luò)場(chǎng)景包括：均勻加入和突發(fā)加入，節(jié)點(diǎn)下載完畢后在0～600 s中隨機(jī)離開(kāi)，6種不同節(jié)點(diǎn)規(guī)模。仿真拓?fù)洳捎矛F(xiàn)網(wǎng)拓?fù)浜碗S機(jī)拓?fù)洹７抡嫦螺d文件大小為25 MB，共采用8臺(tái)仿真服務(wù)器，最大為4 800個(gè)對(duì)等節(jié)點(diǎn)。

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

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

4.1 平均下載時(shí)間

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

本文針對(duì)媒體電信網(wǎng)（MTN）框架和需求，提出具有骨干流量可控、下載速率可控的可控P2P下載新算法，基于PDNS的大規(guī)模仿真結(jié)果證實(shí)了算法的有效性。與MTN框架中的版權(quán)管理和流量計(jì)費(fèi)相結(jié)合后可以實(shí)現(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 歐陽(yáng)榮，苗卉，雷振明.一種減少網(wǎng)間P2P流量的對(duì)等節(jié)點(diǎn)選擇算法.計(jì)算機(jī)工程，2008，34（8）：108～110

11 薛廣濤，俞嘉地，尤晉元.基于臨近結(jié)點(diǎn)聚類構(gòu)建層次化BitTorrent文件共享系統(tǒng).電子學(xué)報(bào)，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）