CoolStreaming-DONet：實時流媒體傳輸?shù)臄?shù)據(jù)重疊網(wǎng)絡(luò)

1、.：.；CoolStreaming/DONet: 實時流媒體傳輸?shù)臄?shù)據(jù)重疊網(wǎng)絡(luò)作者: Xinyan Zhang, Jiangchuan Liu, Bo Li, Tak-Shing Peter Yum翻譯: 默難 ( monnandgmail ). DriftingLeaves ( driftingleavesyahoo )原文參見: /zhang05coolstreamingdonet.html本文其他部分參見: ( 本節(jié)翻譯: DriftingLeaves )本文描畫了 DONet - - - 一種用于流媒體的數(shù)據(jù)驅(qū)動網(wǎng)絡(luò). DONet 的中心操作非常

2、簡單 : 每一個結(jié)點與一組同伴周期性地交換數(shù)據(jù)可用性信息, 從一個或多個同伴那里接納本人所沒有的數(shù)據(jù), 并把本人所擁有的數(shù)據(jù)提供應(yīng)需求的同伴. 我們將著重分析這種數(shù)據(jù)驅(qū)動設(shè)計的三種突出特性:(1) 易于實現(xiàn), 它不需求構(gòu)建或維護(hù)一個復(fù)雜的全局構(gòu)造; (2) 高效,數(shù)據(jù)的傳送方向是按照數(shù)據(jù)的可用性信息而動態(tài)改動的, 而不是被限制在特定的方向上; (3) 強(qiáng)壯, 允許結(jié)點的同伴關(guān)系在眾多提供者中作出順應(yīng)變化的快速轉(zhuǎn)換. 這篇文章將會通篇分析 DONet 在有限延遲下的可擴(kuò)展性, 而且也會思索到實現(xiàn) DONet 時所面臨的一些實踐挑戰(zhàn), 并在此根底上提出一個有效的成員關(guān)系和同伴關(guān)系管理算法, 以及一

3、個能完成實時且延續(xù)播放流內(nèi)容的智能調(diào)度算法.經(jīng)過 Planetlab 曾經(jīng)在大范圍內(nèi)評價了 DONet 的性能. 這些實驗幾乎包括了 Planetlab 的一切有效結(jié)點. 實驗結(jié)果闡明 DONet 甚至可以在復(fù)雜的網(wǎng)絡(luò)條件下到達(dá)很好的流質(zhì)量. 此外, 控制所帶來的額外開銷和傳輸延遲都可以堅持在很低的程度上. 在2004年5月30日, 一個基于Internet 的 DONet 的實現(xiàn) - - - CoolStreaming v.0.9發(fā)布了. 它曾經(jīng)吸引了超越30000的用戶并且在一些頂峰時間創(chuàng)下了4000人同時在線的記錄. 這篇論文將會討論關(guān)于 CoolStreaming 設(shè)計的關(guān)鍵問題, 并

4、且描畫一些這次大范圍測試中的有趣景象. 詳細(xì)來說, 網(wǎng)絡(luò)范圍越大, 被傳送的流的質(zhì)量將會越好.I. 概述 ( 本節(jié)翻譯: DriftingLeaves )隨著寬帶接入的普及化, 多媒體效力對用戶來說變得日益重要, 并且曾經(jīng)成為今天 Internet 流量的重要組成部分. 許多諸如網(wǎng)絡(luò)電視, 新聞廣播的多媒體運用都涉及到把流媒體從源頭傳送給大量用戶的過程. 對這些運用來說, IP 多播也許是最有效的途徑; 然而它的擴(kuò)展卻由于許多現(xiàn)實上的和政治上的要素而遭到限制, 例如缺乏動力去安裝具有多播才干的路由來承當(dāng)多播流量. 因此研討者們開場關(guān)注運用層上的處理方案 - - - 經(jīng)過參與者的協(xié)作來建立一個在

5、單播通道之外的重疊網(wǎng)絡(luò), 這些參與者也被稱作重疊網(wǎng)絡(luò)結(jié)點 ( Overlay Node ), 那么在此根底上, 就可以經(jīng)過結(jié)點之間的數(shù)據(jù)依賴關(guān)系, 實現(xiàn)所謂的多播.作為 IP 多播的替代方案, 開場時許多網(wǎng)絡(luò)構(gòu)建算法大多運用樹構(gòu)造來實現(xiàn)數(shù)據(jù)傳送. 雖然這種方案可以像 IP 多播一樣, 與公用根底路由 ( Dedicated Infrastructure Routers ) 很好的搭配, 但是卻經(jīng)常會與帶有動態(tài)結(jié)點的運用層網(wǎng)絡(luò)搭配錯誤. 而且自主網(wǎng)絡(luò)結(jié)點會隨便地解體或分開, 因此樹構(gòu)造是高度易損的. 而這一問題在對帶寬和延續(xù)性都有很高要求的流傳輸中, 顯得更加嚴(yán)重. 同時雖然像網(wǎng)孔和森林這樣的復(fù)

6、雜構(gòu)造能部分地處理問題, 但其本身的實現(xiàn)卻過于復(fù)雜, 而且經(jīng)常缺乏可擴(kuò)展性.從另一個角度講, 把多播功能移植到運用層同樣會導(dǎo)致更大的彈性; 詳細(xì)來說, 一切的結(jié)點都有很強(qiáng)的緩沖才干并且可以靈敏, 智能地決議數(shù)據(jù)的傳輸方向. 因此文章中提出了一個以數(shù)據(jù)為中心的 ( Data-centric ) 設(shè)計方案- - - 一個結(jié)點總是向那些需求數(shù)據(jù)的結(jié)點傳送數(shù)據(jù), 而它們之間沒有諸如父子關(guān)系, 內(nèi)部外部關(guān)系和上行流下行流關(guān)系. 換句話說, 是數(shù)據(jù)的可用性信息引導(dǎo)著數(shù)據(jù)的流向, 而不是一個特殊的網(wǎng)絡(luò)構(gòu)造約束了數(shù)據(jù)的流向.這種數(shù)據(jù)中心的設(shè)計將會更加順應(yīng)具有高動態(tài)的結(jié)點的網(wǎng)絡(luò). 尤其是思索到一個半靜態(tài)的構(gòu)造,

7、 無論多么有效, 總是會由于結(jié)點的動態(tài)而處于次優(yōu)的形狀.基于這樣的目的, 本文描畫了DONet - - - 一個數(shù)據(jù)驅(qū)動的重疊網(wǎng)絡(luò), 而其中的中心操作非常簡單: 每一個結(jié)點與一組同伴周期性地交換數(shù)據(jù)可用性信息, 從一個或多個同伴那里接納本人所沒有的數(shù)據(jù), 并把本人所擁有的數(shù)據(jù)提供應(yīng)需求的同伴. 我們將著重分析這種數(shù)據(jù)驅(qū)動設(shè)計的三種突出特性:(1) 易于實現(xiàn), 它不需求構(gòu)建并維護(hù)一個復(fù)雜的全局構(gòu)造; (2) 高效,數(shù)據(jù)的傳送方向是按照數(shù)據(jù)的可用性信息而動態(tài)改動的, 而不是被限制在特定的方向上; (3) 強(qiáng)壯的, 有彈性的, 允許結(jié)點的同伴關(guān)系在眾多提供者中作出順應(yīng)變化的快速轉(zhuǎn)換. 此外, 關(guān)于結(jié)

8、果的分析顯示出了網(wǎng)絡(luò)半徑與網(wǎng)絡(luò)大小的邏輯關(guān)系, 這也闡明了 DONet 可以在有限延遲的情況下進(jìn)展擴(kuò)展. 為了實現(xiàn)傳輸實時流媒體的數(shù)據(jù)驅(qū)動網(wǎng)絡(luò), 大量的實踐問題需求思索. 在本文中, 將要討論 DONet 中的假設(shè)干關(guān)鍵問題. 包括同伴關(guān)系的建立, 數(shù)據(jù)可用性信息的編碼和交換, 以及視頻數(shù)據(jù)是如何在同伴間被提供和獲得的. 這里將要提出一套可擴(kuò)展的成員關(guān)系和同伴關(guān)系的管理算法和一個智能調(diào)度算法, 這些方案將會在運用較低控制開銷的情況下, 為中高帶寬用戶提供高效延續(xù)的流傳輸, 同時平穩(wěn)地將傳輸負(fù)載分配到正在參與的結(jié)點中, 并使結(jié)點與異構(gòu)網(wǎng)絡(luò)相順應(yīng). 經(jīng)過 Planetlab 曾經(jīng)在大范圍內(nèi)評價了

9、DONet 的性能. 這些實驗幾乎動用了 Planetlab 跨越五大洲的一切可用結(jié)點. 實驗結(jié)果闡明 DONet 在流速率和播放延續(xù)性上能到達(dá)很高的要求. 此外, 控制所帶來的額外開銷和傳輸延遲都可以堅持在很低的程度上. 根據(jù)當(dāng)前掌握的資料, 全球范圍的實驗很少在文獻(xiàn)中提及. 為此文章中列出了在實驗當(dāng)中遇到的幾個典型問題. 并討論了影響實驗結(jié)果和能夠在未來影響 PlanetLab 開展的要素.最后,在2004年5月30日, 一個公開的, 基于Internet 的 DONet 實現(xiàn) - - - CoolStreaming v.0.9發(fā)布了, 它曾經(jīng)可以播放由一個免費視頻效力器所提供的實時體育節(jié)

10、目, 這個軟件最初只吸引了20個用戶, 但是截至本文發(fā)布, 超越30000的用戶 ( 從獨立IP的統(tǒng)計上看 ) 曾經(jīng)運用過這個流媒體軟件, 在一些頂峰時間甚至到達(dá)4000多用戶同時在線. 先前的統(tǒng)計結(jié)果和用戶的反響是非常鼓舞人心的, 這也闡明了兩個有趣的現(xiàn)實 : 第一, 如今的 Internet 曾經(jīng)有足夠的帶寬來支持電視質(zhì)量的數(shù)據(jù)流 ( 450 Kbps ); 第二, 數(shù)據(jù)驅(qū)動網(wǎng)絡(luò)越大, 所傳送的數(shù)據(jù)流質(zhì)量將會越好. 這兩點都再一次闡明了本文所提出的數(shù)據(jù)驅(qū)動重疊網(wǎng)絡(luò)是用來處理多播視頻分配的可靠方案.II. 相關(guān)任務(wù) ( 本節(jié)翻譯: DriftingLeaves )在過去的十年里, 出現(xiàn)過一些

11、基于IP多播視頻的重要研討, 可以參考 18. 最近,又提出了許多有關(guān)網(wǎng)絡(luò)多播 ( Overlay Multiply System ) 的系統(tǒng), 它們大體上分為兩類: 基于代理協(xié)助 ( Proxy-assisted ) 的和基于 P2P 的. 在傳統(tǒng)意義上, 通常事先安排一整套效力或運用層上的代理, 然后在這些錨點 ( Anchor Node ) 的協(xié)助下建立起一個高質(zhì)量的網(wǎng)絡(luò)1,2,24,26,28. DONets屬于第二類, 它不依賴于公用結(jié)點 ( Dedicated node ) , 但是能在自組織的自動結(jié)點 ( Autonomous Nodes ) 的根底之上建立起一個網(wǎng)絡(luò). 在這一部

12、分中, 我們將對現(xiàn)行的幾種網(wǎng)絡(luò)流協(xié)議作簡單引見, 重點將放在那些完全遵照 p2p 方式的協(xié)議上.A. 基于樹構(gòu)造的網(wǎng)絡(luò)及其擴(kuò)展像前面所提到的, 許多網(wǎng)絡(luò)流協(xié)議采用基于IP多播的樹狀構(gòu)造. 在網(wǎng)絡(luò)結(jié)點之間構(gòu)建并維護(hù)一個高效的分布式樹構(gòu)造, 是這類系統(tǒng)的關(guān)鍵. 在CoopNet 中, 視頻源作為樹構(gòu)造的根, 搜集一切結(jié)點的信息, 用于樹的構(gòu)造及維護(hù). 因此集中式的算法將會非常有效. 但這樣的作法必需依賴于一個功能強(qiáng)大的公用根結(jié)點. 同時, 像 SpreadIt10, NICE12和ZIGZAG11, 運用分布式算法經(jīng)過一系列結(jié)點, 實現(xiàn)構(gòu)建和路由功能. 在大規(guī)模網(wǎng)絡(luò)中, 這些算法采用層次聚類 (

13、Hierarchical Clustering ) 的方式來到達(dá)最小的延遲 (從樹的高度上講 ) 或邊境結(jié)點的任務(wù)量 (從扇出度 ( Fanout Degree ) 上講 ) . 但是, 一個樹構(gòu)造中的內(nèi)部結(jié)點會有較大的負(fù)載, 因此它的分開或解體, 將會在很大范圍內(nèi)導(dǎo)致后代結(jié)點的緩沖區(qū)缺乏. 雖然曾經(jīng)設(shè)計出了一些樹構(gòu)造的修復(fù)算法來順應(yīng)結(jié)點的動態(tài)變化 12,11,23; 但是樹的構(gòu)造仍會在高動態(tài)的網(wǎng)絡(luò)環(huán)境中遭到頻繁破壞.還存在許多用來處理樹構(gòu)造負(fù)載不平衡或易損性的其他方案. 例如建立以網(wǎng)孔為根底的樹構(gòu)造 ( Narada 及它的擴(kuò)展 14, Bullet 20) , 維護(hù)一個多分布式樹構(gòu)造 (

14、SplitStream 19), 或者在分層編碼 ( PALS 29) 和多重描畫編碼 ( CoopNet 3) 之間權(quán)衡. DONet 經(jīng)過引入一種簡單明了的數(shù)據(jù)驅(qū)動方案, 來彌補(bǔ)這些缺陷. 它并不需求維護(hù)一個更復(fù)雜的構(gòu)造, 或者依賴于先進(jìn)的編碼技術(shù), 雖說后一點也會在這個方案中起到一定作用.B. 以 閑談 ( Gossip ) 為根底的協(xié)議最近, 閑談 ( 或傳染病 ) 算法曾經(jīng)成為 P2P 系統(tǒng)中信息多播傳播的流行處理方案 13, 22. 在一個典型的閑談算法中, 一個結(jié)點將新信息發(fā)給一組隨機(jī)選擇的結(jié)點; 這些結(jié)點會在下一輪中作類似的事情, 直到一切結(jié)點都收到信息. 閑談對象的隨機(jī)選擇,

15、 能使系統(tǒng)加強(qiáng)對隨機(jī)發(fā)生的不測退出的彈性, 并且可以進(jìn)展非中心式的操作. 與 16 類似, DONet 的成員管理中運用了閑談協(xié)議. DONet 中的數(shù)據(jù)傳輸方法也部分遭到閑談概念的影響. 但無論如何, 不能將閑談機(jī)制直接用于流傳輸, 由于隨機(jī)的傳送數(shù)據(jù)會帶來大量的冗余, 而這對于有高帶寬需求的流運用來說更加嚴(yán)重. DONet 中, 運用了一個有力同伴的選擇算法, 和一個低開銷的調(diào)度算法, 以便于在大量減少冗余的情況下, 智能地從眾多同伴中接納數(shù)據(jù).先前進(jìn)展的一些有關(guān) P2P 的懇求式流傳輸 ( 例如, 4, 5, 6, 7, 8, 9) 的任務(wù)與閑談機(jī)制嚴(yán)密相關(guān), DONet 也是如此. 在

16、這樣的機(jī)制中, 視頻數(shù)據(jù)由一些種子結(jié)點在有異步需求的結(jié)點中傳播. 同時, 一個或多個結(jié)點, 可以一同為一個新結(jié)點提供緩沖數(shù)據(jù), 并能隨著提供者的增多, 加強(qiáng)系統(tǒng)的才干. DONet 的目的是經(jīng)過半同步的結(jié)點, 到達(dá)實時流媒體傳輸, 這就需求不同的處理方法. 然而, 在實踐的Internet 實現(xiàn)中, DONet 的才干有很大的加強(qiáng), 這也證明了那些在 P2P 懇求式流傳輸研討中的論證.III. DONet的設(shè)計與優(yōu)化 ( 本節(jié)翻譯: 默難 ) Fig-1 一個DONet結(jié)點的系統(tǒng)架構(gòu)圖Fig-1 是一個 DONet 結(jié)點中的系統(tǒng)架構(gòu)圖. 其中有三個重要模塊: (1) 成員管理模塊 ( Memb

17、ership Manager ). 擔(dān)任維護(hù)網(wǎng)絡(luò)中一部分結(jié)點的相關(guān)信息; (2) 同伴管理模塊 ( Partnership Manager ). 擔(dān)任與網(wǎng)絡(luò)中的其他結(jié)點建立并維護(hù)同伴關(guān)系 ( 譯者注: 原文中的Member一詞此處被翻譯為成員; Partner被譯為同伴. 二者區(qū)別為: 網(wǎng)絡(luò)中的一個結(jié)點被稱為這個網(wǎng)絡(luò)中的成員; 網(wǎng)絡(luò)中兩個直接相連的結(jié)點互為同伴. ); (3) 調(diào)度器 ( Scheduler ). 擔(dān)任視頻數(shù)據(jù)傳輸過程的調(diào)度任務(wù). 一個 DONet 結(jié)點的角色相對于視頻流中的每一個分段 ( Segment ), 既可以是分段的接納者 ( Receiver ), 也可以是提供者

18、( Supplier ), 或二者皆是. 結(jié)點角色確實定會根據(jù)分段的可用性信息 ( Segments Availability Information ), 動態(tài)地調(diào)整. 分段的可用性信息會在結(jié)點及其同伴之間周期性地傳送. ( 譯者注: 原文中運用的是 periodically exchanged between the node and its partners. 翻譯為周期性地在結(jié)點及其同伴間傳送. 但是譯者以為, 這種傳送并非是嚴(yán)厲地周期性動作, 即, 兩次信息交換之間的時間間隔不一定是個常數(shù). 因此, 此處翻譯為周期性地 似乎欠妥 ) 但是最初提供資源的結(jié)點 ( Source Node

19、 ) 是個例外 - 它的角色永遠(yuǎn)是分段的提供者. 在此, 這種結(jié)點被稱為源結(jié)點 ( Origin Node ). 它可以是一個公用于提供視頻效力的效力器, 也可以是網(wǎng)絡(luò)中一個運轉(zhuǎn)了視頻效力程序的計算機(jī).本節(jié)中, 將討論模塊間的交互以及設(shè)計問題. 并給出了當(dāng)前的一些處理方案. 它們分別被運用于基于PlanetLab的和基于因特網(wǎng)的實現(xiàn)中. A. 結(jié)點的參與和成員的管理每個 DONet 結(jié)點都有本人的一個獨一標(biāo)識符 ( Unique Identifier ) - 比如可以是它的IP地址 - 并且維護(hù)著一個緩存, 用來存儲 DONet 網(wǎng)絡(luò)中一部分活潑成員的標(biāo)識符 ( 以下稱該緩存為mCache )

20、. 在一個簡單的結(jié)點添加算法中, 一個新參與的結(jié)點首先去和源結(jié)點聯(lián)絡(luò). 源結(jié)點會隨機(jī)地從本人的 mCache 中挑選出一個代理結(jié)點 ( Deputy Node ), 并將新參與的結(jié)點銜接重定向到這個代理結(jié)點上. 新結(jié)點會從代理結(jié)點上獲得一個成員的列表, 把其中的成員視為候選同伴. 之后, 與這些候選同伴建立銜接, 由此確定了本人在網(wǎng)絡(luò)中的同伴關(guān)系. 總體來說, 這一添加過程是可行的. 由于源結(jié)點會在整個流的傳輸過程中一直存在, 并且它的標(biāo)識符/地址是眾所周知的. 重定向的過程使得新結(jié)點可以更加均勻地選擇同伴 ( 譯者注: 此處原文為 The redirection enables more u

21、niform partner selections for newly joined nodes. 該句的翻譯有些過分生硬. 需再斟酌 ), 同時很大程度上減少了源結(jié)點的負(fù)載. 本節(jié)的最后, 會對這個添加算法的改良進(jìn)展一些深化討論. 實際中, 此處遇到的一個關(guān)鍵問題是: 如何建立并更新 mCache. 為了順應(yīng)網(wǎng)絡(luò)的動態(tài)變化, 每個結(jié)點周期性地產(chǎn)生一個成員信息 ( Membership Message ) 用以聲明本人的存在; 每個信息包含四項: . 其中, seq_num 表示該信息的序號; id 表示結(jié)點的標(biāo)識符; num_partner 表示結(jié)點當(dāng)前擁有的同伴數(shù)量; time_to_li

22、ve 表示本條信息剩余的生存時間. DONet網(wǎng)絡(luò)中, 成員信息的傳送運用了 Scalable Gossip Membership 協(xié)議, 即SCAM. 關(guān)于這個協(xié)議的詳細(xì)細(xì)節(jié), 參考 21. 此處, 僅強(qiáng)調(diào)它所具有的三條重要性質(zhì): 可擴(kuò)展 ( Scalable ), 輕量級 ( Light-weight )并且每個結(jié)點僅掌握部分信息 ( Uniform Partial View at Each Node ). 當(dāng)結(jié)點收到一個新的成員信息時, 它會在 mCache 中找到對應(yīng) id 的成員信息記錄, 假設(shè)seq_num大于記錄中的seq_num, 那么更新此條記錄. 假設(shè)沒有找到對應(yīng) id 的

23、記錄, 那么在 mCache 中添加一條記錄存儲該成員信息. mCache 中, 每條成員信息記錄包含五項: . 前四項與成員信息中對應(yīng)項的意義一樣, 是從收到的成員信息中拷貝來的. 第五項記錄了最后一次更新該記錄的本地時間.以下兩種事件同樣能夠引起 mCache 中記錄的更新: (1) 在會話 ( gossip ) 過程中, 某條記錄即將被傳送給其他結(jié)點; (2) 一個代理結(jié)點即將把某條記錄傳送給新參與的結(jié)點. 在這兩種情況下, 結(jié)點會把相應(yīng)記錄的 time_to_live 減去 current_local_time - last_update_time . 假設(shè)計算結(jié)果小于等于零, 那么該

24、條記錄會被刪除, 并且不會被傳送, 也不會被參與到同伴列表. 否那么, 對于第二種情況, 代理結(jié)點會把該條記錄中的num_partner項加一.B. 緩存映像的表示和交換Fig-2 DONet 中的同伴關(guān)系實例 ( A為源結(jié)點 )Fig-2 是 DONet 中同伴關(guān)系的一個例子. 如前所述, 在 DONet 網(wǎng)絡(luò)中, 同伴關(guān)系和數(shù)據(jù)傳輸方向都不是固定的. 一個視頻流被分解為多個定長的分段. 結(jié)點緩存中各個分段的可用性信息被表示為一個緩存映像 ( Buffer Map, BM ). 每個結(jié)點會和它的同伴不斷地交換各自的BM. 之后, 經(jīng)過調(diào)度算法, 確定從哪個同伴處接納哪個分段.對于實時的多媒體

25、流來說, DONet 結(jié)點中的媒體播放過程是一個半同步 ( semi-synchronized) 的過程 ( 譯者注: 半同步 一詞似乎有些前后矛盾. 從字面上看, 翻譯為半步 更佳. 但是為了便于了解, 這種矮高粱 似的詞匯還是保管了下來). 分析的結(jié)果闡明, DONet 中分段傳輸?shù)钠骄訒r被限制在了一定范圍之內(nèi). 實驗的結(jié)果更近一步指出了, 結(jié)點之間的遲延很少高于一分鐘. 假設(shè)每個分段包含了一秒鐘的視頻信息, 一個具有 120 個分段長度的滑動窗口便可以有效地構(gòu)成一個緩存, 而滑動窗口以外的分組那么不在結(jié)點的思索范圍之內(nèi). 如此, 在實現(xiàn)中, 便可以運用120比特來表示一個BM. 假設(shè)其

26、中的某位被置一, 那么闡明該比特對應(yīng)的分段有效, 即, 該分段曾經(jīng)被存儲在了緩存中; 反之, 假設(shè)某比特被置零, 那么闡明該比特對應(yīng)的分段無效. 滑動窗口中第一個分段的序號 ( seq_num ) 存儲在額外的兩個字節(jié)中. 對于一個非常長的視頻節(jié)目來說, 這個序號能夠會由于溢出而被歸零 ( 這樣的視頻節(jié)目至少應(yīng)該大于24小時 ).C. 調(diào)度算法 給定了一個結(jié)點和它同伴的BM信息, 調(diào)度算法那么可以用來確定從哪個同伴處獲得所需的分段. 對于一個同構(gòu) ( Homogenous ), 靜態(tài) ( Static )的網(wǎng)絡(luò), 循環(huán)魯棒 ( Round-robin ) 式的調(diào)度便足以. 但是對于一個動態(tài) (

27、 Dynamically ) 并且異構(gòu) ( Heterogeneous ) 的網(wǎng)絡(luò)來說, 更加智能的算法就顯得尤為重要了. 一個調(diào)度的結(jié)果會遭到兩個約束條件的影響: 每個分段的截止時間 ( Deadline ), 以及與各個同伴間的傳輸帶寬. 第一個約束條件闡明, 超越截止時間到達(dá)的分段數(shù)量應(yīng)該控制在最小. 這個問題實踐上是 并行計算機(jī)調(diào)度問題 ( Parallel Machine Scheduling ) 的一個變種, 屬于NP類問題 25. 因此很難找到一個最優(yōu)解. 從實踐角度出發(fā), 調(diào)度算法必需可以快速地順應(yīng)高度動態(tài)的網(wǎng)絡(luò)環(huán)境. 因此, 我們采取了一種簡單且可以快速呼應(yīng)的啟發(fā)式 ( He

28、uristic ) 算法.這個啟發(fā)式算法中, 首先計算出資源的潛在提供者 ( Potential Supplier ) 的數(shù)量 ( 即, 擁有所需分段的同伴的數(shù)量 ). 由于一個分段假設(shè)對應(yīng)著較少的潛在提供者, 那么將意味著這個分段會很難在截止時間之前到達(dá). 算法會從僅有一個潛在提供者的分組開場確定某一分組的提供者. 之后是對應(yīng)有兩個潛在提供者的分組, 以此類推. 假設(shè)一個分組對應(yīng)著多個潛在提供者, 那么具有最高帶寬并且具有更長可用時間的提供者會被選中. Fig-3 列出了這個算法的偽碼. 對于每個結(jié)點, 都將會執(zhí)行該算法. 它的時間復(fù)雜度為 O( W * B * M ). 在詳細(xì)的實現(xiàn)中,

29、每次執(zhí)行僅需15ms. 計算的額外開銷并不高. 因此, 它可以比較頻繁地運轉(zhuǎn), 從而更新調(diào)度戰(zhàn)略. Fig-3 每個DONet結(jié)點調(diào)度算法的偽碼( 譯者注: 個人以為, 該偽碼包含部分打印錯誤:自Scheduling: 一行起, 向下四行, 有: Tj,i. 個人以為應(yīng)該改為: tj,i第一個if語句中的for循環(huán), 包含一個循環(huán)控制條件, 原文為: jk. 個人以為應(yīng)該改為 ji再向下五行, 原文為 suppliern. 個人以為應(yīng)該改為 supplieri最后一個for循環(huán), 包含一個循環(huán)控制條件, 原文為: jk. 個人以為應(yīng)該改為 ji以上純屬個人臆斷, 一切仍以原文為準(zhǔn) )結(jié)點經(jīng)過調(diào)

30、度算法的計算獲得調(diào)度戰(zhàn)略, 把需求從同一個同伴處獲得哪些分段的信息存儲在一個類似 BM 的位序列中. 之后, 將這個位序列發(fā)送給相應(yīng)的同伴. 該同伴會把位序列中所對應(yīng)的分段經(jīng)過一個實時的傳輸協(xié)議發(fā)送給結(jié)點. DONet 并不依賴于某個特定的協(xié)議. 和其他系一致樣, 目前所采用的是 TFRC ( TCP-Friendly Rate Control ) 協(xié)議 31. BM 信息和調(diào)度戰(zhàn)略信息可以隨數(shù)據(jù)一并傳輸. 這樣可以快速更新并且減少額外開銷.源結(jié)點在此一直作為資源提供者. 并且一切的分段都存儲在它的緩存中. 為了防止源結(jié)點過載, 這里給出了一個順應(yīng)度較高的調(diào)度算法. 假設(shè)需求, 它還可以經(jīng)過對

31、外公布保管的緩存映射來控制負(fù)載. 例如, 一個源結(jié)點擁有 M 個同伴, 那么它可以把傳送給第 k 個同伴的 BM 設(shè)置為:這就是說, 只需第 ( i mod M ) 個同伴才會從源結(jié)點處獲得第 i 個分段. 其他的分段那么別的同伴. D. 錯誤的恢復(fù)和同伴的挑選在 DONet 網(wǎng)絡(luò)中, 一個結(jié)點可以在事先聲明后退出, 或由于解體而不測退出. 這兩種情況都可以在TFRC空轉(zhuǎn)一段時間或者BM信息傳送過程中被檢測出來. 結(jié)點同時分開的概率很小, 遭到分開結(jié)點影響的結(jié)點會立刻做出反響 - 根據(jù)剩下同伴的 BM 信息重構(gòu)調(diào)度戰(zhàn)略. 除了這個恢復(fù)機(jī)制以外, 下面提出的操作也同樣用于加強(qiáng)系統(tǒng)的恢復(fù)才干. 聲

32、明后退出: 即將退出的結(jié)點會提交一個退出音訊. 這個信息的格式與成員信息一樣, 只是num_partner這一項被設(shè)為-1.不測退出: 一個結(jié)點的不測退出會被它的同伴檢測到. 這個同伴會替代退出的結(jié)點來發(fā)布退出音訊. 退出音訊的傳送方式與成員信息的傳送方式一樣. 假設(shè)結(jié)點是不測退出的, 冗余的退出音訊也許會被退出結(jié)點的多個同伴發(fā)布. 但是只需第一個收到的退出音訊會被允許繼續(xù)在網(wǎng)絡(luò)上傳播, 其他的一樣信息傳播那么會被抑制. 每個收到音訊的結(jié)點會刪除各自 mCache 中對應(yīng)于退出結(jié)點的記錄.最后, 每個結(jié)點會定期地從它的 mCache 中隨機(jī)選擇出結(jié)點并與之建立同伴關(guān)系. 這一操作的目的有兩個:

33、 第一, 它使得每個結(jié)點可以在一些同伴退出的情況下, 維護(hù)一定數(shù)量的同伴; 第二, 它使得結(jié)點可以尋覓到更高質(zhì)量的同伴. 在實現(xiàn)中, 一個結(jié)點 i 評價它的同伴結(jié)點 j, 運用函數(shù) max si,j, sj,i. 其中, si,j 表示單位時間內(nèi), 結(jié)點 i 收到結(jié)點 j 的分段的平均數(shù)量. 直覺上看, 一個具有更大上傳帶寬和更多可用分段的同伴會獲得更高的評價分?jǐn)?shù). 由于一個結(jié)點既可以是資源提供者, 也可以是接納者, 因此需求計算兩個方向上的最大值. 在尋覓到新的同伴后, 為了堅持同伴數(shù)量的穩(wěn)定, 同伴列表中具有最低分?jǐn)?shù)的同伴將會被丟棄. 同伴的數(shù)量, M , 是一個很重要的設(shè)計參數(shù). 它的影

34、響將會在之后的實際分析和實驗中做詳細(xì)引見. IV. 網(wǎng)絡(luò)半徑的分析 ( 本節(jié)翻譯: 默難 )本節(jié)將會對 DONet 網(wǎng)絡(luò)的半徑進(jìn)展分析. 所謂網(wǎng)絡(luò)半徑, 指的是一個分段在傳送過程中, 從源結(jié)點到一切的目的結(jié)點的平均間隔 . 和大多數(shù)文獻(xiàn) 11 , 12, 27 一樣, 間隔 的單位是經(jīng)過網(wǎng)絡(luò)中結(jié)點的跳數(shù). 這在一定程度上反響了端到端的傳輸延遲. 這里用到的分析模型是經(jīng)過簡化的, 結(jié)果顯示網(wǎng)絡(luò)半徑與網(wǎng)絡(luò)大小之間成對數(shù)關(guān)系. 這闡明 , DONet 網(wǎng)絡(luò)中的端到端延遲是較小的, 足以用來傳輸實時的流媒體.在 DONet 網(wǎng)絡(luò)中, 分段可用性信息的傳送途徑, 可以用一棵廣度優(yōu)先搜索 ( BFS, B

35、readth-First Search) 的樹構(gòu)造來表示. 源結(jié)點是樹的根結(jié)點, 處于第 0 層. 第 k 層的結(jié)點與源結(jié)點之間相隔 k 跳. DONet 的結(jié)點不會維護(hù)一個明確的構(gòu)造, 因此, 每個結(jié)點可以在這個 BFS 樹中出現(xiàn)多次.為了描畫方便, 把 BFS 樹中的結(jié)點稱為 s-結(jié)點 ( s-node ). 根據(jù)廣度優(yōu)先搜索的規(guī)那么, s-結(jié)點按照在搜索時被訪問的順序進(jìn)展編號. 這樣, 根結(jié)點的編號為 1. 對于編號為 t 的 s-結(jié)點, 它所對應(yīng)的 DONet 結(jié)點被表示為 pt ( 譯者注: 根據(jù)下面(t) 函數(shù)的定義, 此處應(yīng)為 ). 假設(shè)同伴之間的帶寬大約相等, 并且一個分段到達(dá)

36、一個結(jié)點的過程, 是自根結(jié)點出發(fā), 按照廣度優(yōu)先的算法搜索樹構(gòu)造, 直到該結(jié)點第一次出現(xiàn). Fig-4 顯示了 Fig-2 的 DONet 網(wǎng)絡(luò)的 BFS 樹構(gòu)造 ( 只列舉了三個層次).Fig-4 一棵廣度優(yōu)先搜索的數(shù). 黑色的結(jié)點表示(t)等于1的結(jié)點. 即第一次出現(xiàn)的結(jié)點. 白色結(jié)點表示(t)等于零的結(jié)點.定義一個輔助函數(shù) (t): 也就是說, 只需在 s-結(jié)點 t 第一次在樹構(gòu)造中出現(xiàn)時, 函數(shù)值才為 1. 由于成員關(guān)系和同伴關(guān)系協(xié)議是采用隨機(jī)的同伴選擇方式, 用 N 表示網(wǎng)絡(luò)中的結(jié)點數(shù)量, 因此那么有:這里, f(t) 表示編號為 1 至 t 的 s-結(jié)點中, 包含的 DONet 結(jié)

37、點的數(shù)量. 由此那么有: f(t) - f(t-1) = (t). 對 (1) 式兩遍同時求期望, 那么有:由此推導(dǎo)出:由于 f(1) = 1, 根據(jù)等式 (3) 可以推導(dǎo)出:這一關(guān)系給出了 DONet 結(jié)點數(shù)目關(guān)于 s-結(jié)點編號的函數(shù). 令tk表示第 k 層中最后一個 s-結(jié)點的編號, 那么 DONet 網(wǎng)絡(luò)中其他結(jié)點與源結(jié)點之間的平均間隔 , 即網(wǎng)絡(luò)半徑, 那么為:留意到, 當(dāng) k 趨近于無窮時, 有: . 對于一個連通的網(wǎng)絡(luò)來說, 可得:思索一種穩(wěn)定的形狀: 每個 DONet 結(jié)點均擁有 M 個同伴. 那么對應(yīng)的 BFS 樹中, 除了根結(jié)點擁有 M 棵子樹外, 每個非葉子結(jié)點都擁有 M-

38、1 棵子樹. 那么可以導(dǎo)出:將 (6) 式中的連加分解為兩部分: 一部分是從 k = 0 到 k = logM-1N; 另一部分是從 k = 1 + log M-1N 到正無窮. 那么有:當(dāng) M 大于等于 3 時, 有 (M-1)k = (M-1)k. 那么 eM-1k = 450 Kbps )現(xiàn)實上, 超越80%的 CoolStreaming 用戶表示 ( 經(jīng)過 或在線統(tǒng)計 ) 可以在總體上穩(wěn)定地播放視頻. 這也證明了一個推測: 是視頻效力器有限的處置才干和上傳帶寬限制了 Internet 上流效力的開展, 而不一定是主干網(wǎng)絡(luò). 像 DONet/CoolStreaming 這樣以重疊網(wǎng)絡(luò)為根底的流傳播方式, 將是一個可靠的處理方案. 2.數(shù)據(jù)驅(qū)動網(wǎng)絡(luò)越大, 所傳送的數(shù)據(jù)流質(zhì)量將會越好在發(fā)布了第一個版本之后, 我們并沒有提供主要的晉級效力. 而有趣的是, 隨著用戶的添加, 統(tǒng)計結(jié)果和用戶反響反而比初期的更好. 從 Fig-17 中也可看出, 隨著結(jié)點數(shù)量的添加, 延續(xù)性目的在總體上會變好 - - - 在大多數(shù)時間到達(dá)0.95以