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

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


Posted by Mr. Friday

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

 

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



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

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

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

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


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

1流體模型(Fluid Model

還記得國中數學上的馬可夫鏈(Markov Chain)嗎?典型的題目是這樣:

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

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

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

相信大家一定都對這樣的數學模型算出來的結果很有興趣(包括我😄),算出來的結果是

windowslivewriterbtbt-13b42napster1

代表平均下載人數,代表平均種子數,θ代表中途取消下載的比例,β則是受到下載速度、平均上傳頻寬、檔案分享效率與種子離開率影響的一個變數。從排隊理論可以進一步推導出x變成y(下載者變成種子)的時間大約是:

bt_download_time

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

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

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

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

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

2賽局理論

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

bt_game_6

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

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

3Free Riding問題

Free RidingFree 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這個參數的設定,反倒變成BitCometBitSpirit、μTorrent這些軟體的兩難議題了。

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

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

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

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

 

相關連結:

Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks

~ 由 壞孩子 於 四月 7, 2007.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

 
%d 位部落客按了讚: