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

1、50/50CoolStreaming/DONet: 實(shí)時(shí)流媒體傳輸?shù)臄?shù)據(jù)重疊網(wǎng)絡(luò)作者: Xinyan Zhang, Jiangchuan Liu, Bo Li, Tak-Shing Peter Yum翻譯: 默難 ( monnand ). DriftingLeaves ( driftingleaves )原文參見: /zhang05coolstreamingdonet.html本文其他部分參見: /monnand/category/261378.aspx摘要 ( 本節(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ù)提供給需要的伙伴. 我們將著重分析這種數(shù)據(jù)驅(qū)動(dòng)設(shè)計(jì)的三種突出特性:(1) 易于實(shí)現(xiàn), 它不需要構(gòu)建或維護(hù)一個(gè)復(fù)雜的全局結(jié)構(gòu); (2) 高效,數(shù)據(jù)的傳遞方向是依照數(shù)據(jù)的可用性信息而動(dòng)態(tài)改變的, 而不是被限制在特定的方向上; (3) 健壯, 同意結(jié)點(diǎn)的伙伴關(guān)系在眾多提供者中作出適應(yīng)變化的快速轉(zhuǎn)換. 這篇文章將會(huì)通篇分析 DONet 在有限延遲下的可擴(kuò)展性, 而且也會(huì)考慮到實(shí)現(xiàn) DONet 時(shí)所面臨的一些實(shí)際挑戰(zhàn), 并在此基礎(chǔ)上提出一個(gè)有效的成員關(guān)系和伙伴關(guān)系治理算法,

3、以及一個(gè)能完成實(shí)時(shí)且連續(xù)播放流內(nèi)容的智能調(diào)度算法.通過 Planetlab 差不多在大范圍內(nèi)評估了 DONet 的性能. 這些實(shí)驗(yàn)幾乎包括了 Planetlab 的所有有效結(jié)點(diǎn). 實(shí)驗(yàn)結(jié)果表明 DONet 甚至能夠在復(fù)雜的網(wǎng)絡(luò)條件下達(dá)到專門好的流質(zhì)量. 此外, 操縱所帶來的額外開銷和傳輸延遲都能夠保持在專門低的水平上. 在2004年5月30日, 一個(gè)基于Internet 的 DONet 的實(shí)現(xiàn) - - - CoolStreaming v.0.9公布了. 它差不多吸引了超過30000的用戶同時(shí)在一些高峰時(shí)刻創(chuàng)下了4000人同時(shí)在線的記錄. 這篇論文將會(huì)討論關(guān)于 CoolStreaming 設(shè)計(jì)的

4、關(guān)鍵問題, 同時(shí)描述一些這次大范圍測試中的有味現(xiàn)象. 具體來講, 網(wǎng)絡(luò)范圍越大, 被傳送的流的質(zhì)量將會(huì)越好.I. 概述 ( 本節(jié)翻譯: DriftingLeaves )隨著寬帶接入的普及化, 多媒體服務(wù)對用戶來講變得日益重要, 同時(shí)差不多成為今天 Internet 流量的重要組成部分. 許多諸如網(wǎng)絡(luò)電視, 新聞廣播的多媒體應(yīng)用都涉及到把流媒體從源頭傳送給大量用戶的過程. 對這些應(yīng)用來講, IP 多播也許是最有效的途徑; 然而它的擴(kuò)展卻因?yàn)樵S多現(xiàn)實(shí)上的和政治上的因素而受到限制, 例如缺乏動(dòng)力去安裝具有多播能力的路由來承擔(dān)多播流量. 因此研究者們開始關(guān)注應(yīng)用層上的解決方案 - - - 通過參與者的

5、合作來建立一個(gè)在單播通道之外的重疊網(wǎng)絡(luò), 這些參與者也被稱作重疊網(wǎng)絡(luò)結(jié)點(diǎn) ( Overlay Node ), 那么在此基礎(chǔ)上, 就能夠通過結(jié)點(diǎn)之間的數(shù)據(jù)依靠關(guān)系, 實(shí)現(xiàn)所謂的多播.作為 IP 多播的替代方案, 開始時(shí)許多網(wǎng)絡(luò)構(gòu)建算法大多使用樹結(jié)構(gòu)來實(shí)現(xiàn)數(shù)據(jù)傳遞. 盡管這種方案能夠像 IP 多播一樣, 與專用基礎(chǔ)路由 ( Dedicated Infrastructure Routers ) 專門好的搭配, 然而卻經(jīng)常會(huì)與帶有動(dòng)態(tài)結(jié)點(diǎn)的應(yīng)用層網(wǎng)絡(luò)搭配錯(cuò)誤. 而且自主網(wǎng)絡(luò)結(jié)點(diǎn)會(huì)輕易地崩潰或離開, 因此樹結(jié)構(gòu)是高度易損的. 而這一問題在對帶寬和連續(xù)性都有專門高要求的流傳輸中, 顯得更加嚴(yán)峻. 同時(shí)盡管

6、像網(wǎng)孔和森林如此的復(fù)雜結(jié)構(gòu)能部分地解決問題, 但其本身的實(shí)現(xiàn)卻過于復(fù)雜, 而且經(jīng)常缺乏可擴(kuò)展性.從另一個(gè)角度講, 把多播功能移植到應(yīng)用層同樣會(huì)導(dǎo)致更大的彈性; 具體來講, 所有的結(jié)點(diǎn)都有專門強(qiáng)的緩沖能力同時(shí)能夠靈活, 智能地決定數(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ò)結(jié)構(gòu)約束了數(shù)據(jù)的流向.這種數(shù)據(jù)中心的設(shè)計(jì)將會(huì)更加適應(yīng)具有高動(dòng)態(tài)的結(jié)點(diǎn)的網(wǎng)絡(luò). 尤其是考

7、慮到一個(gè)半靜態(tài)的結(jié)構(gòu), 不管多么有效, 總是會(huì)因?yàn)榻Y(jié)點(diǎn)的動(dòng)態(tài)而處于次優(yōu)的狀態(tài).基于如此的目標(biāo), 本文描述了DONet - - - 一個(gè)數(shù)據(jù)驅(qū)動(dòng)的重疊網(wǎng)絡(luò), 而其中的核心操作特不簡單: 每一個(gè)結(jié)點(diǎn)與一組伙伴周期性地交換數(shù)據(jù)可用性信息, 從一個(gè)或多個(gè)伙伴那兒接收自己所沒有的數(shù)據(jù), 并把自己所擁有的數(shù)據(jù)提供給需要的伙伴. 我們將著重分析這種數(shù)據(jù)驅(qū)動(dòng)設(shè)計(jì)的三種突出特性:(1) 易于實(shí)現(xiàn), 它不需要構(gòu)建并維護(hù)一個(gè)復(fù)雜的全局結(jié)構(gòu); (2) 高效,數(shù)據(jù)的傳遞方向是依照數(shù)據(jù)的可用性信息而動(dòng)態(tài)改變的, 而不是被限制在特定的方向上; (3) 健壯的, 有彈性的, 同意結(jié)點(diǎn)的伙伴關(guān)系在眾多提供者中作出適應(yīng)變化的快速

8、轉(zhuǎn)換. 此外, 關(guān)于結(jié)果的分析顯示出了網(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 中的若干關(guān)鍵問題. 包括伙伴關(guān)系的建立, 數(shù)據(jù)可用性信息的編碼和交換, 以及視頻數(shù)據(jù)是如何在伙伴間被提供和獲得的. 那個(gè)地點(diǎn)將要提出一套可擴(kuò)展的成員關(guān)系和伙伴關(guān)系的治理算法和一個(gè)智能調(diào)度算法, 這些方案將會(huì)在使用較低操縱開銷的情況下, 為中高帶寬用戶提供高效連續(xù)的流傳輸, 同時(shí)平穩(wěn)地將傳輸負(fù)載分配到正在參與的結(jié)點(diǎn)中, 并使結(jié)點(diǎn)與異構(gòu)網(wǎng)絡(luò)相適應(yīng). 通過 Planetlab

9、 差不多在大范圍內(nèi)評估了 DONet 的性能. 這些實(shí)驗(yàn)幾乎動(dòng)用了 Planetlab 跨越五大洲的所有可用結(jié)點(diǎn). 實(shí)驗(yàn)結(jié)果表明 DONet 在流速率和播放連續(xù)性上能達(dá)到專門高的要求. 此外, 操縱所帶來的額外開銷和傳輸延遲都能夠保持在專門低的水平上. 依照當(dāng)前掌握的材料, 全球范圍的實(shí)驗(yàn)專門少在文獻(xiàn)中提及. 為此文章中列出了在實(shí)驗(yàn)當(dāng)中遇到的幾個(gè)典型問題. 并討論了阻礙實(shí)驗(yàn)結(jié)果和可能在今后阻礙 PlanetLab 進(jìn)展的因素.最后,在2004年5月30日, 一個(gè)公開的, 基于Internet 的 DONet 實(shí)現(xiàn) - - - CoolStreaming v.0.9公布了, 它差不多能夠播放由一

10、個(gè)免費(fèi)視頻服務(wù)器所提供的實(shí)時(shí)體育節(jié)目, 那個(gè)軟件最初只吸引了20個(gè)用戶, 然而截至本文公布, 超過30000的用戶 ( 從獨(dú)立IP的統(tǒng)計(jì)上看 ) 差不多使用過那個(gè)流媒體軟件, 在一些高峰時(shí)刻甚至達(dá)到4000多用戶同時(shí)在線. 先前的統(tǒng)計(jì)結(jié)果和用戶的反饋是十分鼓舞人心的, 這也講明了兩個(gè)有味的事實(shí) : 第一, 現(xiàn)在的 Internet 差不多有足夠的帶寬來支持電視質(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)工作 ( 本節(jié)翻譯: DriftingLea

11、ves )在過去的十年里, 出現(xiàn)過一些基于IP多播視頻的重要研究, 能夠參考 18. 最近,又提出了許多有關(guān)網(wǎng)絡(luò)多播 ( Overlay Multiply System ) 的系統(tǒng), 它們大體上分為兩類: 基于代理協(xié)助 ( Proxy-assisted ) 的和基于 P2P 的. 在傳統(tǒng)意義上, 通常事先安排一整套服務(wù)或應(yīng)用層上的代理, 然后在這些錨點(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 )

12、 的基礎(chǔ)之上建立起一個(gè)網(wǎng)絡(luò). 在這一部分中, 我們將對現(xiàn)行的幾種網(wǎng)絡(luò)流協(xié)議作簡略介紹, 重點(diǎn)將放在那些完全遵循 p2p 模式的協(xié)議上.A. 基于樹結(jié)構(gòu)的網(wǎng)絡(luò)及其擴(kuò)展像前面所提到的, 許多網(wǎng)絡(luò)流協(xié)議采納基于IP多播的樹狀結(jié)構(gòu). 在網(wǎng)絡(luò)結(jié)點(diǎn)之間構(gòu)建并維護(hù)一個(gè)高效的分布式樹結(jié)構(gòu), 是這類系統(tǒng)的關(guān)鍵. 在CoopNet 中, 視頻源作為樹結(jié)構(gòu)的根, 收集所有結(jié)點(diǎn)的信息, 用于樹的構(gòu)造及維護(hù). 因此集中式的算法將會(huì)特不有效. 但如此的作法必須依靠于一個(gè)功能強(qiáng)大的專用根結(jié)點(diǎn). 同時(shí), 像 SpreadIt10, NICE12和ZIGZAG11, 使用分布式算法通過一系列結(jié)點(diǎn), 實(shí)現(xiàn)構(gòu)建和路由功能. 在大規(guī)

13、模網(wǎng)絡(luò)中, 這些算法采納層次聚類 ( Hierarchical Clustering ) 的方式來達(dá)到最小的延遲 (從樹的高度上講 ) 或邊界結(jié)點(diǎn)的工作量 (從扇出度 ( Fanout Degree ) 上講 ) . 然而, 一個(gè)樹結(jié)構(gòu)中的內(nèi)部結(jié)點(diǎn)會(huì)有較大的負(fù)載, 因此它的離開或崩潰, 將會(huì)在專門大范圍內(nèi)導(dǎo)致后代結(jié)點(diǎn)的緩沖區(qū)不足. 盡管差不多設(shè)計(jì)出了一些樹結(jié)構(gòu)的修復(fù)算法來適應(yīng)結(jié)點(diǎn)的動(dòng)態(tài)變化 12,11,23; 然而樹的結(jié)構(gòu)仍會(huì)在高動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境中遭到頻繁破壞.還存在許多用來解決樹結(jié)構(gòu)負(fù)載不均衡或易損性的其他方案. 例如建立以網(wǎng)孔為基礎(chǔ)的樹結(jié)構(gòu) ( Narada 及它的擴(kuò)展 14, Bullet

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

15、到所有結(jié)點(diǎn)都收到信息. 閑談對象的隨機(jī)選擇, 能使系統(tǒng)加強(qiáng)對隨機(jī)發(fā)生的意外退出的彈性, 同時(shí)能夠進(jìn)行非中心式的操作. 與 16 相似, DONet 的成員治理中使用了閑談協(xié)議. DONet 中的數(shù)據(jù)傳輸方法也部分受到閑談概念的阻礙. 但不管如何, 不能將閑談機(jī)制直接用于流傳輸, 因?yàn)殡S機(jī)的傳送數(shù)據(jù)會(huì)帶來大量的冗余, 而這關(guān)于有高帶寬需求的流應(yīng)用來講更加嚴(yán)峻. DONet 中, 使用了一個(gè)有力伙伴的選擇算法, 和一個(gè)低開銷的調(diào)度算法, 以便于在大量減少冗余的情況下, 智能地從眾多伙伴中接收數(shù)據(jù).先前進(jìn)行的一些有關(guān) P2P 的請求式流傳輸 ( 例如, 4, 5, 6, 7, 8, 9) 的工作與閑

16、談機(jī)制緊密相關(guān), DONet 也是如此. 在如此的機(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 的目標(biāo)是通過半同步的結(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è)

17、重要模塊: (1) 成員治理模塊 ( Membership Manager ). 負(fù)責(zé)維護(hù)網(wǎng)絡(luò)中一部分結(jié)點(diǎn)的相關(guān)信息; (2) 伙伴治理模塊 ( Partnership Manager ). 負(fù)責(zé)與網(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 ). 負(fù)責(zé)視頻數(shù)據(jù)傳輸過程的調(diào)度工作. 一個(gè) DONet 結(jié)點(diǎn)的角色相關(guān)于視頻流中的每一個(gè)分段 ( Segment ), 既能夠是分段的接收者

18、 ( Receiver ), 也能夠是提供者 ( Supplier ), 或二者皆是. 結(jié)點(diǎn)角色的確定會(huì)依照分段的可用性信息 ( Segments Availability Information ), 動(dòng)態(tài)地調(diào)整. 分段的可用性信息會(huì)在結(jié)點(diǎn)及其伙伴之間周期性地傳遞. ( 譯者注: 原文中使用的是 periodically exchanged between the node and its partners. 翻譯為周期性地在結(jié)點(diǎn)及其伙伴間傳遞. 然而譯者認(rèn)為, 這種傳遞并非是嚴(yán)格地周期性動(dòng)作, 即, 兩次信息交換之間的時(shí)刻間隔不一定是個(gè)常數(shù). 因此, 此處翻譯為周期性地 大概欠妥 ) 然而

19、最初提供資源的結(jié)點(diǎn) ( Source Node ) 是個(gè)例外 它的角色永久是分段的提供者. 在此, 這種結(jié)點(diǎn)被稱為源結(jié)點(diǎn) ( Origin Node ). 它能夠是一個(gè)專用于提供視頻服務(wù)的服務(wù)器, 也能夠是網(wǎng)絡(luò)中一個(gè)運(yùn)行了視頻服務(wù)程序的計(jì)算機(jī).本節(jié)中, 將討論模塊間的交互以及設(shè)計(jì)問題. 并給出了當(dāng)前的一些解決方案. 它們分不被應(yīng)用于基于PlanetLab的和基于因特網(wǎng)的實(shí)現(xiàn)中. A. 結(jié)點(diǎn)的加入和成員的治理每個(gè) DONet 結(jié)點(diǎn)都有自己的一個(gè)唯一標(biāo)識符 ( Unique Identifier ) 比如能夠是它的IP地址 同時(shí)維護(hù)著一個(gè)緩存, 用來存儲(chǔ) DONet 網(wǎng)絡(luò)中一部分活躍成員的標(biāo)識符

20、( 以下稱該緩存為mCache ). 在一個(gè)簡單的結(jié)點(diǎn)添加算法中, 一個(gè)新加入的結(jié)點(diǎn)首先去和源結(jié)點(diǎn)聯(lián)系. 源結(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)系. 總體來講, 這一添加過程是可行的. 因?yàn)樵唇Y(jié)點(diǎn)會(huì)在整個(gè)流的傳輸過程中始終存在, 同時(shí)它的標(biāo)識符/地址是眾所周知的. 重定向的過程使得新結(jié)點(diǎn)能夠更加均勻地選擇伙伴 ( 譯者注: 此處原文為 The redirecti

21、on enables more uniform partner selections for newly joined nodes. 該句的翻譯有些過分生硬. 需再斟酌 ), 同時(shí)專門大程度上減少了源結(jié)點(diǎn)的負(fù)載. 本節(jié)的最后, 會(huì)對那個(gè)添加算法的改進(jìn)進(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)前擁

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

23、記錄. 假如沒有找到對應(yīng) id 的記錄, 則在 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 .

24、假如計(jì)算結(jié)果小于等于零, 則該條記錄會(huì)被刪除, 同時(shí)可不能被傳遞, 也可不能被加入到伙伴列表. 否則, 關(guān)于第二種情況, 代理結(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. 之后, 通過調(diào)度算法, 確定從哪個(gè)伙伴

25、處接收哪個(gè)分段.關(guān)于實(shí)時(shí)的多媒體流來講, 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)中, 便能夠使用1

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

27、以. 然而關(guān)于一個(gè)動(dòng)態(tài) ( Dynamically ) 同時(shí)異構(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í)際角度動(dòng)身, 調(diào)度算法必須能夠快速地適應(yīng)高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境. 因此, 我們采取了一種簡單且能

28、夠快速響應(yīng)的啟發(fā)式 ( Heuristic ) 算法.那個(gè)啟發(fā)式算法中, 首先計(jì)算出資源的潛在提供者 ( Potential Supplier ) 的數(shù)量 ( 即, 擁有所需分段的伙伴的數(shù)量 ). 因?yàn)橐粋€(gè)分段假如對應(yīng)著較少的潛在提供者, 那么將意味著那個(gè)分段會(huì)專門難在截止時(shí)刻之前到達(dá). 算法會(huì)從僅有一個(gè)潛在提供者的分組開始確定某一分組的提供者. 之后是對應(yīng)有兩個(gè)潛在提供者的分組, 以此類推. 假如一個(gè)分組對應(yīng)著多個(gè)潛在提供者, 那么具有最高帶寬同時(shí)具有更長可用時(shí)刻的提供者會(huì)被選中. Fig-3 列出了那個(gè)算法的偽碼. 關(guān)于每個(gè)結(jié)點(diǎn), 都將會(huì)執(zhí)行該算法. 它的時(shí)刻復(fù)雜度為 O( W * B *

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

30、一切仍以原文為準(zhǔn) )結(jié)點(diǎn)通過調(diào)度算法的計(jì)算獲得調(diào)度策略, 把需要從同一個(gè)伙伴處獲得哪些分段的信息存儲(chǔ)在一個(gè)類似 BM 的位序列中. 之后, 將那個(gè)位序列發(fā)送給相應(yīng)的伙伴. 該伙伴會(huì)把位序列中所對應(yīng)的分段通過一個(gè)實(shí)時(shí)的傳輸協(xié)議發(fā)送給結(jié)點(diǎn). DONet 并不依靠于某個(gè)特定的協(xié)議. 和其他系統(tǒng)一樣, 目前所采納的是 TFRC ( TCP-Friendly Rate Control ) 協(xié)議 31. BM 信息和調(diào)度策略信息能夠隨數(shù)據(jù)一并傳輸. 如此能夠快速更新同時(shí)減少額外開銷.源結(jié)點(diǎn)在此始終作為資源提供者. 同時(shí)所有的分段都存儲(chǔ)在它的緩存中. 為了防止源結(jié)點(diǎn)過載, 那個(gè)地點(diǎn)給出了一個(gè)適應(yīng)度較高的調(diào)度

31、算法. 假如需要, 它還能夠通過對外公布保留的緩存映射來操縱負(fù)載. 例如, 一個(gè)源結(jié)點(diǎn)擁有 M 個(gè)伙伴, 那么它能夠把傳遞給第 k 個(gè)伙伴的 BM 設(shè)置為:這確實(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ì)立即做出反應(yīng) 依照剩下伙伴的 BM 信息重構(gòu)調(diào)度策略. 除了那個(gè)恢復(fù)機(jī)制以外, 下面提出的操

32、作也同樣用于增強(qiáng)系統(tǒng)的恢復(fù)能力. 聲明后退出: 立即退出的結(jié)點(diǎn)會(huì)提交一個(gè)退出消息. 那個(gè)信息的格式與成員信息一樣, 只是num_partner這一項(xiàng)被設(shè)為-1.意外退出: 一個(gè)結(jié)點(diǎn)的意外退出會(huì)被它的伙伴檢測到. 那個(gè)伙伴會(huì)代替退出的結(jié)點(diǎn)來公布退出消息. 退出消息的傳遞方式與成員信息的傳遞方式一樣. 假如結(jié)點(diǎn)是意外退出的, 冗余的退出消息也許會(huì)被退出結(jié)點(diǎn)的多個(gè)伙伴公布. 然而只有第一個(gè)收到的退出消息會(huì)被同意接著在網(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)并與之建立

33、伙伴關(guān)系. 這一操作的目的有兩個(gè): 第一, 它使得每個(gè)結(jié)點(diǎn)能夠在一些伙伴退出的情況下, 維護(hù)一定數(shù)量的伙伴; 第二, 它使得結(jié)點(diǎn)能夠查找到更高質(zhì)量的伙伴. 在實(shí)現(xiàn)中, 一個(gè)結(jié)點(diǎn) i 評估它的伙伴結(jié)點(diǎn) j, 使用函數(shù) max si,j, sj,i. 其中, si,j 表示單位時(shí)刻內(nèi), 結(jié)點(diǎn) i 收到來自結(jié)點(diǎn) j 的分段的平均數(shù)量. 直覺上看, 一個(gè)具有更大上傳帶寬和更多可用分段的伙伴會(huì)獲得更高的評估分?jǐn)?shù). 由于一個(gè)結(jié)點(diǎn)既能夠是資源提供者, 也能夠是接收者, 因此需要計(jì)算兩個(gè)方向上的最大值. 在查找到新的伙伴后, 為了保持伙伴數(shù)量的穩(wěn)定, 伙伴列表中具有最低分?jǐn)?shù)的伙伴將會(huì)被拋棄. 伙伴的數(shù)量, M

34、 , 是一個(gè)專門重要的設(shè)計(jì)參數(shù). 它的阻礙將會(huì)在之后的理論分析和實(shí)驗(yàn)中做具體介紹. 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 相同, 距離的單位是通過網(wǎng)絡(luò)中結(jié)點(diǎn)的跳數(shù). 這在一定程度上反應(yīng)了端到端的傳輸延遲. 那個(gè)地點(diǎn)用到的分析模型是通過簡化的, 結(jié)果顯示網(wǎng)絡(luò)半徑與網(wǎng)絡(luò)大小之間成對數(shù)關(guān)系. 這講明 , DONet 網(wǎng)絡(luò)中的端到端延遲是較小的, 足以用來傳輸實(shí)時(shí)的流媒體.在 DONet 網(wǎng)絡(luò)中, 分段可用性信息的傳遞路徑,

35、能夠用一棵廣度優(yōu)先搜索 ( BFS, Breadth-First Search) 的樹結(jié)構(gòu)來表示. 源結(jié)點(diǎn)是樹的根結(jié)點(diǎn), 處于第 0 層. 第 k 層的結(jié)點(diǎn)與源結(jié)點(diǎn)之間相隔 k 跳. DONet 的結(jié)點(diǎn)可不能維護(hù)一個(gè)明確的結(jié)構(gòu), 因此, 每個(gè)結(jié)點(diǎn)能夠在那個(gè) BFS 樹中出現(xiàn)多次.為了描述方便, 把 BFS 樹中的結(jié)點(diǎn)稱為 s-結(jié)點(diǎn) ( s-node ). 依照廣度優(yōu)先搜索的規(guī)則, s-結(jié)點(diǎn)按照在搜索時(shí)被訪問的順序進(jìn)行編號. 如此, 根結(jié)點(diǎn)的編號為 1. 關(guān)于編號為 t 的 s-結(jié)點(diǎn), 它所對應(yīng)的 DONet 結(jié)點(diǎn)被表示為 pt ( 譯者注: 依照下面(t) 函數(shù)的定義, 此處應(yīng)為 ). 假設(shè)伙

36、伴之間的帶寬大約相等, 同時(shí)一個(gè)分段到達(dá)一個(gè)結(jié)點(diǎn)的過程, 是自根結(jié)點(diǎn)動(dòng)身, 按照廣度優(yōu)先的算法搜索樹結(jié)構(gòu), 直到該結(jié)點(diǎn)第一次出現(xiàn). Fig-4 顯示了 Fig-2 的 DONet 網(wǎng)絡(luò)的 BFS 樹結(jié)構(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): 也確實(shí)是講, 只有在 s-結(jié)點(diǎn) t 第一次在樹結(jié)構(gòu)中出現(xiàn)時(shí), 函數(shù)值才為 1. 由于成員關(guān)系和伙伴關(guān)系協(xié)議是采納隨機(jī)的伙伴選擇方式, 用 N 表示網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)量, 因此則有:那個(gè)地點(diǎn), f(t) 表示編號為 1 至

37、t 的 s-結(jié)點(diǎn)中, 包含的 DONet 結(jié)點(diǎn)的數(shù)量. 由此則有: f(t) - f(t-1) = (t). 對 (1) 式兩遍同時(shí)求期望, 則有:由此推導(dǎo)出:因?yàn)?f(1) = 1, 依照等式 (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í), 有: . 關(guān)于一個(gè)連通的網(wǎng)絡(luò)來講, 可得:考慮一種穩(wěn)定的狀態(tài): 每個(gè) DONet 結(jié)點(diǎn)均擁有 M 個(gè)伙伴. 那么對應(yīng)的 BFS 樹中, 除了根結(jié)點(diǎn)擁有 M 棵

38、子樹外, 每個(gè)非葉子結(jié)點(diǎn)都擁有 M-1 棵子樹. 那么能夠?qū)С?將 (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 )事實(shí)上, 超過80%的 CoolStreaming 用戶表示 ( 通過 e-mail 或在線統(tǒng)計(jì) ) 能夠在總體上穩(wěn)定地播放視頻. 這也證明了一個(gè)推測: 是視頻服務(wù)器有限的處理能力和上傳帶寬限制了 Internet 上流服務(wù)的進(jìn)展, 而不一定是主干網(wǎng)絡(luò). 像 DONet/CoolStreaming 如此以重疊網(wǎng)絡(luò)為基礎(chǔ)的流傳播方式, 將是一個(gè)可靠的解決方案. 2.數(shù)據(jù)驅(qū)動(dòng)網(wǎng)絡(luò)越大, 所傳送的數(shù)據(jù)流質(zhì)量將會(huì)越好在公布了第一個(gè)版本之后, 我們并沒有提供要緊的升級服務(wù). 而有味的是, 隨著用戶的增加, 統(tǒng)計(jì)結(jié)果和用戶反饋反而比初期的更好. 從 Fig-17 中也可看出, 隨著結(jié)點(diǎn)數(shù)量的增加, 連續(xù)性指標(biāo)在總體上會(huì)變好 - - - 在大多數(shù)時(shí)刻達(dá)到0.95以