BT的基本運作原理

原貼 http://mmdays.wordpress.com/2007/04/06/bt1/

由於原貼已經連不進了,其它地方又參差不齊,還好數年前有備份,於2014年5月25日,轉貼至此。

透視BT(一)­­── BT的基本運作原理

Posted by Mr. Friday

談到BT,相信大家都不陌生。沒錯,今天要來談的就是這幾年在網路上非常重要,已經快要變成全民運動的──BT程式。筆者有鑒於BT已經變成非常火紅的應用程式,但是了解這個程式的基本運作原理與影響的人卻寥寥無幾,於是決定撰寫這個主題;本篇會先介紹BT的源起與運作原理,接下來的幾篇則會根據這一兩年學術上對BT的觀察,介紹BT在各種使用情境下對網路行為的影響(當中包含一些相當出人意表的發現)。

BitTorrent,簡稱BT,由Bram Cohen於2002年獨立完成其核心程式碼的撰寫。從Bram Cohen簡陋而陽春的個人網頁上看來,他於1993年進入紐約州立大學就讀,輟學之後陸續做過研究員、網路程式設計師,就履歷上看來並不是非常特出,2002年間他發表的BT一開始也沒有獲得很大的關注。隔年五月他把BT的理論基礎寫成一篇簡短五頁的學術文章發表在「Workshop on Economics of Peer-to-Peer Systems, 2003」上,文章本身沒有知名教授的背書、用字遣辭顯然也不夠精練,然而這篇文章至今卻已累積了474篇的reference數。2004年六月時,據CNN報導,BT已經佔據了網路上所有P2P流量的53%。至今,BT程式檔的下載量已經超過一億三千五百萬人次,而這些數字還不包含網路上經其他使用者修改過的版本,如BitComet、BitSpirit…等等。



Bram Cohen照片,在他blog裡還有各種用電腦變形過後的照片,例如變身成美少女戰士的樣子。

就Mr. Friday自己的觀察,BT程式已經成為眾多網路鄉民平日不可或缺的「資料來源」之一,就算沒有使用過,或多或少也會在生活中聽到相關的用語,比如說torrent檔、種子、斷種等等術語。更有甚者,許多網路應用也開始使用BT的模式,比如說某些Linux的ISO檔、魔獸世界WOW的更新檔就是透過BT方式在網路上散佈,也有一些網路電視程式是從BT處得到靈感來源,例如現在相當火紅的PPStream。

BT最讓人驚奇的地方在於下載的速度極快。使用過的人都曉得,BT下載往往比傳統的FTP、網頁下載來得快很多。這當中的原理可以從下圖解釋:



左圖是FTP與HTTP下載的基本原理,道理很簡單,擁有檔案的人負責將檔案傳送給所有想下載檔案的人。假設今天的同時下載這個檔案的人有三個(A、B、C),則每個人的下載速度就是檔案擁有者上傳速度的1/3。

BT的原理就比較複雜一點。擁有檔案(例如File.txt)的人(稱為種子)會將檔案切很多很多的小塊(例如File1.txt、File2.txt、…、File100.txt),每當有人(假設也叫A)想下載檔案時,種子(或者其他的下載者)就把一部份的小塊檔案寄給這個A,A就拿著這些檔案片段去跟另外一個也在下載的人B、C說:「Hey!我有一部分的小檔案,你也有一部分的小檔案,我們來互相交換彼此沒有的部分吧!」。對於A來說,他就可以同時從種子與B、C處抓取檔案片段,因此下載的速度就會變快,而不僅限於種子頻寬的1/3。如果今天網路上的下載者不只2個,而是成千上萬,那麼理論上A的速度就可以一飛千里。透過這個「下載者互通有無」的想法,讓下載的速度來得比以往的FTP、HTTP還快。

BT對於分享檔案的種子也有好處。以往如果要讓所有的下載者都抓到檔案,種子就不能下線,直到所有人都抓完檔案為止。頻寬的消耗也是單方面的:只消耗種子的上傳頻寬,因此常常造成種子端的網路塞車。BT就不會這樣:只要網路上出現另外一個把整個檔案都下載成功的人,等於就是出現另外一個新種子,原來的種子就可以下線休息去了──甚至不用等到新種子出現!沿用前例,原先的種子把檔案片段1~3給了A,片段4~6給了B,片段7~10給了C,那麼就算種子下線休息去了,ABC之間仍然能夠透過互通有無的機制,把檔案下載成功。BT一方面減輕了單一種子的負擔,另一方面也延長了檔案的壽命-就算原先種子離開了,如果A、B、C當中有人志願留下來等到新下載者D出現,那麼檔案就能繼續流傳下去。

當然,要讓這套機制成功,還有幾個配套的措施:

(1) Torrent檔與Tracker:

由於BT中的種子、下載成員一直在變動,必須要有方法讓其他新成員找到他們,因此就出現了Torrent檔與Tracker。Tracker是個小程式,紀錄著目前所有下載成員的名單與網路位置。Torrent檔則是紀錄Tracker的位置與檔案片段的全部名稱。因此對於新成員來說,他首先要獲得的就是一個torrent檔,從torrent檔中他知道tracker的位置,然後再經由tracker與其他下載成員取得聯繫。

(2) Rarest First Policy

為了增進檔案分享的速度,每個成員會盡量分享網路上最少見的檔案片段。例如A擁有片段1、2、3,B擁有2、4、5,C擁有1、3、5,則網路上最罕見的是片段4,因此若有人想向B互通有無,B會優先傳給他片段4。

(3) Choking Policy

當一個檔案很流行的時候,一個BT系統可能會同時擁有成千上萬的下載者。A身為一個參與者,必定會收到非常多人希望跟他交換檔案的請求。但是A的頻寬很小,只允許同時上傳給4個人(在BT最初原始程式裡預設是4;其他軟體的設定就不一定了,我知道BitComet之前是10個),那麼A要如何決定拒絕這當中的誰呢?這叫做choking(拒絕)policy。BT的做法是:接受(unchoke)那些現在正上傳檔案給我、而且速度最快的前4個人!BT的Choking Policy至為重要,因為它傳達出一種「施比受更有福」的概念:願意付出更多上傳頻寬的人,將會收到其他人的回報-更快的下載速度。日後有許多關於BT的研究,都是針對這個特性作一番探討。

(4) Optimistic Unchoking

承續前述的理念,想要獲得更快的下載速度,就應該先將檔案分享給別人。Optimistic Unchoking是說,每個人每30秒就挑網路中任意一個人,將檔案上傳給他。這麼作的用意是發掘網路上未知的潛力檔案提供者:假如A與K之前並未有檔案的往來,但其實這兩個人住得很近,網路互傳的速度比其他人快。今天A透過Optimistic Unchoking隨機給K上傳了一些檔案片段,讓K驚覺A的上傳速度很快,進而允許A從K處下載檔案片段。如果A與K之間的連線速度很慢,那麼過30秒之後,A會停止提供檔案給K,而去別處尋找下一個候選人。

透過上述的幾種機制,Bram Cohen成功的開發出一套獨特的下載技術,也讓BT成為近幾年來最流行的話題,網路上更逐漸出現許多以BT為核心,內容卻略有不同的幾套下載軟體,如前述BitComet、BitSpirit等。這些軟體多少在技術上修改了BT,比如說改變檔案傳輸時使用的port、改變同時最多上傳人數等等,但技術的基本概念卻是不變的:透過鼓勵分享,達到更快的下載速度。

接下來的幾篇,會引述幾篇學術上研究BT機制的論文,讓我們看看BT這套機制透過長時間實驗與數學流體模型、機率模型、排隊模型、賽局理論……等等的驗證下,在各方面的效能如何?這些論文又會給我們什麼啟示?敬請大家拭目以待,下回再見。

返回主篇 → BT BitTorrent 基本 運作 原理 主篇

20140525 update this article

沒有留言:

張貼留言

由於一直被灌水, 因此您發表留言之後, 需要等待博客主的審核, 才會公開您的留言, 所以請不要重複的留言
Hello my friend, I have no money, My blog is super chill, Please do not screw me up in the replies at the bottom of the article, thanks a lot