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

1、.：.；CoolStreaming/DONet: 實(shí)時(shí)流媒體傳輸?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ū)動(dòng)網(wǎng)絡(luò). DONet 的中心操作非常

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

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

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

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

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

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

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

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

10、目, 這個(gè)軟件最初只吸引了20個(gè)用戶, 但是截至本文發(fā)布, 超越30000的用戶 ( 從獨(dú)立IP的統(tǒng)計(jì)上看 ) 曾經(jīng)運(yùn)用過這個(gè)流媒體軟件, 在一些頂峰時(shí)間甚至到達(dá)4000多用戶同時(shí)在線. 先前的統(tǒng)計(jì)結(jié)果和用戶的反響是非常鼓舞人心的, 這也闡明了兩個(gè)有趣的現(xiàn)實(shí) : 第一, 如今的 Internet 曾經(jīng)有足夠的帶寬來支持電視質(zhì)量的數(shù)據(jù)流 ( 450 Kbps ); 第二, 數(shù)據(jù)驅(qū)動(dòng)網(wǎng)絡(luò)越大, 所傳送的數(shù)據(jù)流質(zhì)量將會(huì)越好. 這兩點(diǎn)都再一次闡明了本文所提出的數(shù)據(jù)驅(qū)動(dòng)重疊網(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)意義上, 通常事先安排一整套效力或運(yùn)用層上的代理, 然后在這些錨點(diǎn) ( Anchor Node ) 的協(xié)助下建立起一個(gè)高質(zhì)量的網(wǎng)絡(luò)1,2,24,26,28. DONets屬于第二類, 它不依賴于公用結(jié)點(diǎn) ( Dedicated node ) , 但是能在自組織的自動(dòng)結(jié)點(diǎn) ( Autonomous Nodes ) 的根底之上建立起一個(gè)網(wǎng)絡(luò). 在這一部

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

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

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

15、 能使系統(tǒng)加強(qiáng)對隨機(jī)發(fā)生的不測退出的彈性, 并且可以進(jìn)展非中心式的操作. 與 16 類似, DONet 的成員管理中運(yùn)用了閑談協(xié)議. DONet 中的數(shù)據(jù)傳輸方法也部分遭到閑談概念的影響. 但無論如何, 不能將閑談機(jī)制直接用于流傳輸, 由于隨機(jī)的傳送數(shù)據(jù)會(huì)帶來大量的冗余, 而這對于有高帶寬需求的流運(yùn)用來說更加嚴(yán)重. DONet 中, 運(yùn)用了一個(gè)有力同伴的選擇算法, 和一個(gè)低開銷的調(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é)點(diǎn)在有異步需求的結(jié)點(diǎn)中傳播. 同時(shí), 一個(gè)或多個(gè)結(jié)點(diǎn), 可以一同為一個(gè)新結(jié)點(diǎn)提供緩沖數(shù)據(jù), 并能隨著提供者的增多, 加強(qiáng)系統(tǒng)的才干. DONet 的目的是經(jīng)過半同步的結(jié)點(diǎn), 到達(dá)實(shí)時(shí)流媒體傳輸, 這就需求不同的處理方法. 然而, 在實(shí)踐的Internet 實(shí)現(xiàn)中, DONet 的才干有很大的加強(qiáng), 這也證明了那些在 P2P 懇求式流傳輸研討中的論證.III. DONet的設(shè)計(jì)與優(yōu)化 ( 本節(jié)翻譯: 默難 ) Fig-1 一個(gè)DONet結(jié)點(diǎn)的系統(tǒng)架構(gòu)圖Fig-1 是一個(gè) DONet 結(jié)點(diǎn)中的系統(tǒng)架構(gòu)圖. 其中有三個(gè)重要模塊: (1) 成員管理模塊 ( Memb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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