王力群

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

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

中圖分類號:TP393文獻(xiàn)標(biāo)識碼:A文章編號: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

對等網(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(簡稱BT)是P2P技術(shù)在文件共享分發(fā)中的典型應(yīng)用。BT系統(tǒng)中文件被分割成一定大小(一般為256KB)的文件塊(piece),每一個Peer既可以從別的Peer獲取文件,同時也為其他的Peer提供下載服務(wù),但是作為每一個Peer來講,由于各節(jié)點(diǎn)間的鏈路情況存在差異,如何使得每一個Peer能夠獲得滿意的下載速率,同時又能夠為其他Peer提供良好的上傳服務(wù)是P2P技術(shù)中一個重要的問題。

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

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

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

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

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

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

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

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

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

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

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

2.1 TFT阻塞算法

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

2.2 樂觀阻塞算法

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

2.3 種子阻塞算法

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

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