網路的頻寬分享與BT的隨機過程模型

原貼 http://mmdays.wordpress.com/2007/04/07/bt2/

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

zmarkchang：
2007年的老貼看看就好，現今的BT和那時已經不同了，這篇內文還參差了，很多它的個人見解，有許多錯誤的地方，非原文翻譯，不是很好。

透視BT（二）──網路的頻寬分享與BT的隨機過程模型

前一篇文章介紹了BT的基本運作原理，這一篇文章就來看看學術界對這個機制的探討吧。

關於BT機制本身的實驗文章其實不少。2004年一群法國人發表了一篇Dissecting BitTorrent：Five Months in a Torrent＇s Life。內容是他們把Red Hat 9的原始檔（約1.77G）放在網路上供人下載，透過Tracker的紀錄機制，觀察BT的下載特性。相較於這群法國人觀察的是單一BT檔的下載過程，紐西蘭Delft大學的研究生則觀察了國外比較有名的BT分享論壇（Supernova.org、Youceff.com等）幾個月來的人潮（大約有六萬人）。從這些鄉野實驗，可以得到幾個基本的結論：

（1） BT檔案往往會有flash crowd情形：分享開始的前幾天會湧入大量人潮，然而高潮退去後人也散得快。

（2） 下載的速度呈現「多數人下載慢，極少數人下載速度超快」的情形；不過即使「多數人下載慢」，下載的平均速度仍然比ftp快上不少。根據實驗，平均下載速度是240K，90%的人速度不會超過520K。有極少數的人下載速度會達到每秒3000K以上。

（3） 檔案的存活天數難以從檔案分享十天後的狀況來預測：紐西蘭學生嘗試著去預測檔案存活天數，不過失敗了。後面我們會看到另外一篇paper是如何成功預測的。

就這樣而已嗎？這兩篇實驗雖然做了一段蠻長的時間，可是得出的結論好像跟沒做差不多；我們這些下載者不用做實驗也知道。不過學術界就是這樣：會有人先去做最基本的實驗，弄出一大堆看似無用的數據，接著就會出現根據這些數據做出的漂亮推論。2004年，著名期刊SIGCOMM石破天驚地刊出了一篇論文：「Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks」，作者是UIUC的Dongyu Qiu與R. Sirkant。該篇文章用廣泛而嚴謹的數學模型推導BitTorrent在穩定態效能、檔案分享效度、Free Rider（不提供上傳頻寬但享受下載速度的懶蟲）等問題，做了一番精闢的解析，讓所有網路學教授驚覺BT中的價值：不只是因為根據BT的數學隨機模型極有研究價值（經數學驗證，BT擁有「無人數上限」、「下載速度不受人潮影響」的特性），更讓他們驚奇的是，這些教授竟然都沒發現身邊有這麼傑出的軟體，而且還是一個無名小卒寫的XD。從該篇文章之後，有更多的學術資源投入與BT相關的研究，BT技術的影響也深入到其他應用，例如隨選視訊（VOD）、CDN等等。

既然上一篇討論過了BT的基本特性，我們就直接來看看這篇論文探討了哪些東西吧！接下來的文章可能會牽涉到一些數學，我會盡量用淺顯易懂的字眼跟大家解釋的。

（1）流體模型（Fluid Model）

還記得國中數學上的馬可夫鏈（Markov Chain）嗎？典型的題目是這樣：

某旅行家固定在A、B兩城走動，每天他會決定要前往A城或B城，如果今天他人在A城，則有80%的機率明天他會走到B城去（20%的機率留下來）；如果今天他在B城，則明天他有75%的機率跑到A城（25%的機率待在B城）。問經過無數天之後，旅行家待在A城的機率有多少？待在B城的機率有多少？？

相信大家對這類的數學問題還有一點點印象。好了，今天我們不討論如何解題，來看看Sirkant他們如何用類似的方式模擬BT：

今天有A、B、C、D四個城，A城象徵沒有加入BT的人，B城象徵成為BT下載者的人，C城象徵成為BT種子的人，D城象徵下載完後離開系統的人。A城每天有λ人會進入B城，C城每天有γ的人會進入D城，而C城到D城（下載者變成種子）的速率則視當下BT中有多少人、每人平均分享頻寬而定，則經過無數天之後，B城的人有多少？C城的人有多少？從B城到C城的平均速度是多少？？

相信大家一定都對這樣的數學模型算出來的結果很有興趣（包括我XD），算出來的結果是：



代表平均下載人數， 代表平均種子數，θ代表中途取消下載的比例，β則是受到下載速度、平均上傳頻寬、檔案分享效率與種子離開率影響的一個變數。

從排隊理論可以進一步推導出x變成y（下載者變成種子）的時間大約是：



T是平均下載時間。從這些奇怪的數學蝌蚪文中，作者得到了以下結論：

Ø 平均下載時間與人潮湧進的速率無關。因此下載時間不會因為系統中人很多（或人很少）而變快（或變慢）。

Ø 檔案分享的效率越高，下載時間越短。分享的效率與「BT中一個下載者同時最多能向多少人交換檔案片段下落的資訊」成正相關。

Ø 種子離開系統的速率會影響下載時間。每分鐘若有10個種子離開BT，平均下載速率會比每分鐘5個種子離開的BT慢。

Ø 在網路上絕大多數人使用ADSL的情況下，會影響下載速度的是「每個人平均願意分享出來的頻寬」。除非今天每個下載者變成種子之後都捨不得離開BT、讓BT中充滿無限多個種子，否則這個法則不會改變。

（2）賽局理論

還記得「美麗境界」裡面John Nash對於「如何追女孩子」提出的賽局理論解說嗎？

沒錯，這篇論文也用上了賽局，用來解釋「如果你上傳頻寬比別人少的話，跟別人搶下載資源會多麼吃力」這件事。事實上根據BT的基本設定，這個結論還頗殘酷的……。 還記得上一篇提到，每個人都會上傳給「分享給我檔案且速度最快的前四個人」嗎？假設今天系統中有六個人，這六個人的上傳頻寬都不一樣，則根據這個法則，上 傳頻寬最少的使用者將屈居劣勢，因為頻寬前五名的使用者會「玩他們自己的」，互相將檔案傳給對方，而頻寬最後一名的使用者只能等待前五位偶發性的「Optimistic Unchoking」施捨一點檔案給第六名，或者說等前五位都下載完畢成為種子之後，才能得到檔案。



所以BT中達不到皆大歡喜的Nash Equilibrium（納許平衡點），總是會有人得不到檔案嘛？倒也不盡然。這篇paper另外提出一種情境，在這種情境下每個人的下載速度都不會太低：將網路上的下載者依據頻寬分為幾個大族群。上傳頻寬最大的族群會優先獲得檔案，當這個族群的下載速度已經快到不能再快的時候，多出來的上傳頻寬會分享給第二快的族群，然後依此類推…。只要每個族群的人數到達一定的數量，就會達到人人有檔抓、速度都不慢的納許平衡點。

（事實上Mr. Friday對賽局不熟，這段看了我好久啊~如果有錯還請指正）

（3）Free Riding問題

Free Riding（Free Riding是一種行為，Free Rider是指有這種行為的人）指的是不合作的使用者。在注重分享功能的BT系統中，偏偏有些人上傳開一點點或根本不開，那麼這些人的還是會享有很高的效能嘛？讓我們來想一下，Free Rider們唯一能夠獲得檔案的機會就是其他人透過Optimistic Unchoking隨機上傳檔案給他們的時候。那麼一個Free Rider接受到的機會有多少？假設系統中只有一個Free Rider，則其他人隨機選到他、上傳檔案給他的頻寬就等於

N（總人數）

乘上μ（每人平均上傳頻寬）

乘上1/N-n（選中Free Rider的機率，N為總人數，n為當下有上傳關係的人數）

乘上1/(n+1)（Optimistic Unchoking佔去的頻寬比例）

因為N往往極大（人數常常破千上萬），相較於n很小（預設同時上傳給4人），所以化簡後可得

Free Rider頻寬=μ/（n+1）

如果照BT原先的預設n=4（最多同時上傳給4個人），則一個Free Rider的下載速度大概是網路平均上傳頻寬的五分之一。因為在BT機制中，每個人的下載都來自其他人的上傳，所以每人平均上傳頻寬也就等於每人平均下載速度。因此該式子代表「一個不分享上傳頻寬的傢伙，下載速率大約是其他人的五分之一」。如果是BitComet之類的軟體，將n調到10，則free rider的下載速率大概是別人的十一分之一。

大家應該都不太喜歡網路上有Free Rider的出現，那麼我們直接把n這個數字提高到無限大好不好？但n太高會引起反效果，因為開啟太多的連線數會直接導致網路擁擠，錯誤率提高，整體上傳率反而下跌，進而導致群體下載速度變更慢。n這個參數的設定，反倒變成BitComet、BitSpirit、μTorrent這些軟體的兩難議題了。

從上面精采的推導，給了我們幾個觀察BT的重點。首先是BT在檔案分享效率上已經超乎許多學者原本的預期，下載的速率不會隨著同時下載人數的多寡而變，而能一直維持在「每人平均上傳速率」－這是一個相當重要的特性，因為它打破一般以為「想要禁得起多人同時下載，就得付出龐大的伺服器架設費用」的迷思。模仿BT機制而運作良好的PPStream就是一個很好的例子。以往大家都認為Video On Demand（隨選視訊）至少還要經過個十幾年，等到有人付得起龐大的網路串流伺服器架設費用再說。現在呢？你看PPStream運作得多快！

第二個重點是BT軟體本身可設定的參數對於整個BT系統下載的影響。如前面所述，網路上有很多以BT為核心、但是經過略加修改的軟體，如BitComet、BitSpirit、μTorrent等等。可別以為這些軟體都差不多，事實上這些軟體所動到的一些參數，如同時可傳輸的人數上限、同時交換檔案片段訊息的人數上限，甚至是預設的上傳頻寬上限等等，會徹底的影響整個BT的運作效能。不過我談論的是整體：如果一群人都用BitComet，與另一群都用BitSpirit下載，兩組群體的整體效能會不相同，但是以現在網路的情形，大概有20%用BitComet、30%用BitSpirit、5%用奇奇怪怪的軟體……。如果你把慣用的BT軟體從BitComet轉換成BitSpirit，你的下載的速度應該不會有特別的影響。只有在整體的情況下─有10000人共同把軟體從BitComet換成BitSpirit─ 才會有影響。所以別輕易的被「我們這套軟體用了特殊加速的方法」之類的廣告辭迷惑。那或許是真的，不過要非常多人都使用那套軟體才會有效。而且「加快下 載」這類的技術往往都不是很光明正大，裡面不知道藏了什麼奇怪的設定（像是死道友也死貧道的foxy）才會讓下載速度變快……。還是乖乖用一般的正派BT軟體就好吧！

最後一個是我個人的感想。看到前面國中曾經學過的馬可夫鏈、電影中看過的賽局理論、高中時算得要死的機率…不知道大家是不是跟Mr. Friday一樣感慨呢？這些學問以前在學的時候總是覺得艱深，而且不知道到底可以用在哪裡。不過這些數學的應用其實就存在你我的身邊，甚至是大家每天開啟的BT程式中。透過這些數學的運算，甚至可以真實的預測出大眾看似不經意而隨機的下載行為模式。誰說國高中時學的數學是沒有用的呢？這裡還真要感謝我國高中的數學老師幫我打下的基礎，不然我還看不太懂這些言簡意賅的精妙數學運算式呢！

這樣就結束了嗎？還沒呢！下一篇將會介紹另一篇研究BT行為的Paper，看他們是如何準確預測BT從發佈到斷種的時間長度，上傳分享比率與下載速度之間的關係，甚至是開同時開數個Torrent檔時的影響！精采可期，可別錯過了喔！

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

20140525 update this article