基于P2P技術(shù)的BT系統(tǒng)阻塞算法分析

王力群

摘要:隨著Bit Torrent系統(tǒng)的廣泛使用,Bit Torrent引起了學(xué)術(shù)界的極大關(guān)注。已有的研究工作主要集中于Bit Torrent測(cè)量、建模和算法等方面。該文通過對(duì)BT系統(tǒng)的阻塞算法的分析研究,指出存在的問題,為提高阻塞算法研究提供依據(jù)。

關(guān)鍵詞:阻塞算法;阻塞機(jī)制;P2P;Bit Torrent;文件共享

中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)35-9999-02

Based on the P2P Technology BT System Obstruction Algorithm Analysis

WANG Li-qun

(Nanjing Institute of Railway Techology, Nanjing 210015, China)

Abstract: With the wide use of Bit Torrent system, caused a Bit Torrent of academic attention. The research has focused on Bit Torrent measurement, modeling and algorithm, etc. Based on the choke algorithm of BT system analysis, points out the existing problems, in order to provide basis for improving choke algorithm.

Key words: choke algorithm; choke mechanisms; P2P; bit torrent; file sharing

對(duì)等網(wǎng)(P2P:Peer-to-Peer)因其良好的可擴(kuò)展性和健壯性成為Internet中最重要的系統(tǒng)之一。文件共享已經(jīng)作為P2P系統(tǒng)的應(yīng)用之一而廣泛應(yīng)用,從最初的Napster到Gnutella,Kazak,引領(lǐng)了P2P技術(shù)的不斷發(fā)展。Bit Torrent(簡(jiǎn)稱BT)是P2P技術(shù)在文件共享分發(fā)中的典型應(yīng)用。BT系統(tǒng)中文件被分割成一定大小(一般為256KB)的文件塊(piece),每一個(gè)Peer既可以從別的Peer獲取文件,同時(shí)也為其他的Peer提供下載服務(wù),但是作為每一個(gè)Peer來講,由于各節(jié)點(diǎn)間的鏈路情況存在差異,如何使得每一個(gè)Peer能夠獲得滿意的下載速率,同時(shí)又能夠?yàn)槠渌鸓eer提供良好的上傳服務(wù)是P2P技術(shù)中一個(gè)重要的問題。

1 阻塞機(jī)制的概念

在節(jié)點(diǎn)間建立連接后,進(jìn)行內(nèi)容分發(fā)的過程中,一個(gè)節(jié)點(diǎn)可能會(huì)同時(shí)收到來自它多個(gè)節(jié)點(diǎn)的要求下載文件分片的請(qǐng)求。如果本節(jié)點(diǎn)同時(shí)滿足所有這些請(qǐng)求,向所有這些節(jié)點(diǎn)發(fā)送文件,就可能會(huì)造成本節(jié)點(diǎn)性能下降以及網(wǎng)絡(luò)擁塞(因?yàn)楣?jié)點(diǎn)的數(shù)目可能會(huì)比較大)。為了避免這種情況,必須采取一定的方法,對(duì)部分節(jié)點(diǎn)的請(qǐng)求進(jìn)行阻塞(Choke),不予處理。

首先考慮兩個(gè)節(jié)點(diǎn)(設(shè)為A和B)間能夠進(jìn)行內(nèi)容傳輸?shù)臈l件。一般來說A向B送文件片斷,需要滿足兩個(gè)條件:

1) B對(duì)該文件片斷感興趣(Interested);

2) A同意向B發(fā)送該文件片斷,也就是說A不阻塞(Choke)B。

可以把這兩個(gè)條件看成AB連接的兩個(gè)狀態(tài)。為了表示這兩個(gè)狀態(tài),在程序中引入兩個(gè)狀態(tài)變量:

Choked:該狀態(tài)為真時(shí),表示A阻塞了B;

Interested:該狀態(tài)為真時(shí),表示B對(duì)A的文件片斷感興趣。

那么,在節(jié)點(diǎn)A收到B的文件片斷請(qǐng)求報(bào)文時(shí),就可以通過檢查這兩個(gè)狀態(tài),來決定是否向B傳送文件了。

2 BT系統(tǒng)的阻塞算法

BT系統(tǒng)中,每?jī)蓚€(gè)建立連接的節(jié)點(diǎn)之間,一個(gè)節(jié)點(diǎn)對(duì)另一個(gè)節(jié)點(diǎn)都設(shè)置有一個(gè)狀態(tài):阻塞?！白枞北硎静辉敢饨o對(duì)方傳送數(shù)據(jù),即使對(duì)方向該節(jié)點(diǎn)請(qǐng)求下載,該節(jié)點(diǎn)也不會(huì)回應(yīng);“服務(wù)”(即“取消阻塞”)表示對(duì)方可以從該節(jié)點(diǎn)獲得下載。具體的阻塞算法有三種:

2.1 TFT阻塞算法

節(jié)點(diǎn)以回報(bào)的方式,選擇當(dāng)前向自己上傳文件速度最快的一定數(shù)量(默認(rèn)為4個(gè))的節(jié)點(diǎn)作為自己的服務(wù)對(duì)象。這樣可以有效防止“搭便車者”(只下載而不愿上傳的節(jié)點(diǎn)),并且有效的激勵(lì)節(jié)點(diǎn)參與上傳服務(wù),因?yàn)橹挥羞@樣才能夠最大可能的獲得其余節(jié)點(diǎn)對(duì)自己的上傳,從而最大化自己的下載帶寬。這個(gè)決策結(jié)果以一定時(shí)間(10秒)為周期進(jìn)行更新。

2.2 樂觀阻塞算法

從所有向自己發(fā)出申請(qǐng)的節(jié)點(diǎn)里面隨機(jī)選擇一個(gè)為其提供上傳服務(wù),而不管對(duì)方當(dāng)前是否為自己服務(wù)。周期為TFT阻塞算法的三倍(30秒),采用長(zhǎng)周期目的是保證為新節(jié)點(diǎn)提供完整的一塊文件塊,以使其能夠?yàn)槠渌?jié)點(diǎn)服務(wù)。采用這種算法的目的,一是為了發(fā)現(xiàn)是否具有更適合的交換對(duì)象;二是為了向新加入節(jié)點(diǎn)提供最初文件塊的下載,因?yàn)樗鼈儧]有任何文件塊,根據(jù)TFT阻塞算法不會(huì)獲取到別人的上傳。

2.3 種子阻塞算法

由于種子節(jié)點(diǎn)(已經(jīng)下載完成的節(jié)點(diǎn))不再需要下載,所以不能夠以下載速度作為節(jié)點(diǎn)選擇的依據(jù)。這時(shí)決定因素是連接節(jié)點(diǎn)從它這里獲得的下載速度,即它只為下載速度最快的那些(默認(rèn)為5個(gè))節(jié)點(diǎn)服務(wù),以便最大化上傳帶寬,加快文件的分發(fā)。

3 BT系統(tǒng)阻塞算法中存在的問題分析

依據(jù)TFT阻塞算法,連接雙方都是在對(duì)方為自己提供服務(wù)的前提下才會(huì)為對(duì)方提供服務(wù)。這種“先取后予”的方法必然導(dǎo)致以下問題。

問題一:BT系統(tǒng)中“第一塊”問題,即節(jié)點(diǎn)需要很長(zhǎng)時(shí)間才能夠獲取到最初幾塊文件塊(一般為最初5%的文件塊)。由于新加入節(jié)點(diǎn)沒有任何資源可與別人交換,依據(jù)TFT算法是沒有可能獲得下載的,所以只能依靠種子或是其它節(jié)點(diǎn)樂觀阻塞算法才有機(jī)會(huì)獲得服務(wù)。而種子和樂觀算法數(shù)量很少,所以數(shù)據(jù)來源很少。

問題二:當(dāng)兩個(gè)新連接節(jié)點(diǎn)彼此向?qū)Ψ桨l(fā)出申請(qǐng)后,需要長(zhǎng)時(shí)間的等待才能夠開始之間的文件下載。新連接的節(jié)點(diǎn)雙方向?qū)Ψ桨l(fā)出申請(qǐng)后,都在等待獲取對(duì)方的服務(wù),都在等待對(duì)方的樂觀阻塞算法選中自己,而不愿首先提供服務(wù),進(jìn)而出現(xiàn)了彼此等待的“僵局”。因樂觀阻塞算法執(zhí)行周期長(zhǎng)且服務(wù)數(shù)量?jī)H有一個(gè),所以需要長(zhǎng)時(shí)間的等待。而且由于BT系統(tǒng)極強(qiáng)的動(dòng)態(tài)性,連接節(jié)點(diǎn)的退出導(dǎo)致連接過少或是中途退出一段時(shí)間后返回系統(tǒng),節(jié)點(diǎn)都會(huì)增加新的連接,所以中途連接節(jié)點(diǎn)很平常;而此時(shí)文件塊的互補(bǔ)性很強(qiáng),進(jìn)而彼此會(huì)向?qū)Ψ缴暾?qǐng)文件塊,所以新連接節(jié)點(diǎn)彼此向?qū)Ψ缴暾?qǐng)文件塊的情況也并不顯見。

問題三:節(jié)點(diǎn)在“最后塊”時(shí)期的上傳連接過少。BT系統(tǒng)中,一直存在著“最后塊”的問題,即節(jié)點(diǎn)往往要花很長(zhǎng)的時(shí)間來下載最后幾塊文件塊,因?yàn)橛嘞碌膸讐K文件塊往往是只被個(gè)別節(jié)點(diǎn)擁有的“稀罕資源”或是被帶寬很低的節(jié)點(diǎn)擁有,所以需要長(zhǎng)時(shí)間的資源尋找和下載。在這段很長(zhǎng)的時(shí)間里,節(jié)點(diǎn)雖然有著絕大部分資源,但由于自己當(dāng)前只從極個(gè)別節(jié)點(diǎn)下載,所以依據(jù)TFT算法只可能為這些極個(gè)別的節(jié)點(diǎn)服務(wù),從而導(dǎo)致上傳連接數(shù)量很少,以至沒有平均快速的分發(fā)資源。大量文章想通過創(chuàng)建一種鼓勵(lì)機(jī)制,延長(zhǎng)節(jié)點(diǎn)下載完成后的停留時(shí)間,以使其盡可能多的分發(fā)文件,但卻忽略了節(jié)點(diǎn)在成為種子的前一段時(shí)間,雖擁有與種子差不多的資源,但卻不能充分提供上傳服務(wù)。

4 結(jié)束語

該文首先介紹了基于P2P技術(shù)的BT系統(tǒng)中阻塞算法的原理和作用,然后對(duì)阻塞算法中存在的幾個(gè)問題進(jìn)行了詳細(xì)描述,為針對(duì)問題提出新的阻塞算法提供理論依據(jù)。

參考文獻(xiàn):

[1] 汪燕,柳斌.Bit Torrent協(xié)議分析及控制策略[J].實(shí)驗(yàn)技術(shù)與管理,2006,1(23):54-56.

[2] 王坯.Bit Torrent下載技術(shù)研究[J].科技廣場(chǎng),2005,2(2):26-27.

[3] 孔彬,徐良賢.Bit Torrent原理分析及改進(jìn).計(jì)算機(jī)工程,2004,1(30):257-259.

[4] 王冠英.Bit Torrent系統(tǒng)中可擴(kuò)展性的研究[D].杭州:浙江大學(xué),2005.

[5] 周文莉.Bit Torrent文件共享系統(tǒng)的流量模型與文件評(píng)估方法[J].計(jì)算機(jī)工程,2006,32(13):15-17.