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

22/22CoolStreaming/DONet:實(shí)時(shí)流媒體傳輸?shù)臄?shù)據(jù)重疊網(wǎng)絡(luò)作者:XinyanZhang,JiangchuanLiu,BoLi,Tak-ShingPeterYum翻譯:默難().DriftingLeaves()原文參見(jiàn):本文其他局部參見(jiàn):/monnand/category/261378.aspx摘要

(本節(jié)翻譯:DriftingLeaves)本文描述了DONet---一種用于流媒體的數(shù)據(jù)驅(qū)動(dòng)網(wǎng)絡(luò).DONet的核心操作非常簡(jiǎn)單:每一個(gè)結(jié)點(diǎn)與一組伙伴周期性地交換數(shù)據(jù)可用性信息,從一個(gè)或多個(gè)伙伴那里接收自己所沒(méi)有的數(shù)據(jù),并把自己所擁有的數(shù)據(jù)提供應(yīng)需要的伙伴.我們將著重分析這種數(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)系管理算法,以及一個(gè)能完成實(shí)時(shí)且連續(xù)播放流內(nèi)容的智能調(diào)度算法.通過(guò)Planetlab已經(jīng)在大范圍內(nèi)評(píng)估了DONet的性能.這些實(shí)驗(yàn)幾乎包括了Planetlab的所有有效結(jié)點(diǎn).實(shí)驗(yàn)結(jié)果說(shuō)明DONet甚至能夠在復(fù)雜的網(wǎng)絡(luò)條件下到達(dá)很好的流質(zhì)量.此外,控制所帶來(lái)的額外開(kāi)銷(xiāo)和傳輸延遲都可以保持在很低的水平上.在2004年5月30日,一個(gè)基于Internet的DONet的實(shí)現(xiàn)---CoolStreamingv.0.9發(fā)布了.它已經(jīng)吸引了超過(guò)30000的用戶并且在一些頂峰時(shí)間創(chuàng)下了4000人同時(shí)在線的記錄.這篇論文將會(huì)討論關(guān)于CoolStreaming設(shè)計(jì)的關(guān)鍵問(wèn)題,并且描述一些這次大范圍測(cè)試中的有趣現(xiàn)象.具體來(lái)說(shuō),網(wǎng)絡(luò)范圍越大,被傳送的流的質(zhì)量將會(huì)越好.I.概述

(本節(jié)翻譯:DriftingLeaves)隨著寬帶接入的普及化,多媒體效勞對(duì)用戶來(lái)說(shuō)變得日益重要,并且已經(jīng)成為今天Internet流量的重要組成局部.許多諸如網(wǎng)絡(luò)電視,新聞播送的多媒體應(yīng)用都涉及到把流媒體從源頭傳送給大量用戶的過(guò)程.對(duì)這些應(yīng)用來(lái)說(shuō),IP多播也許是最有效的途徑;然而它的擴(kuò)展卻因?yàn)樵S多現(xiàn)實(shí)上的和政治上的因素而受到限制,例如缺乏動(dòng)力去安裝具有多播能力的路由來(lái)承當(dāng)多播流量.因此研究者們開(kāi)始關(guān)注應(yīng)用層上的解決方案---通過(guò)參與者的合作來(lái)建立一個(gè)在單播通道之外的重疊網(wǎng)絡(luò),這些參與者也被稱(chēng)作重疊網(wǎng)絡(luò)結(jié)點(diǎn)(OverlayNode),那么在此基礎(chǔ)上,就可以通過(guò)結(jié)點(diǎn)之間的數(shù)據(jù)依賴(lài)關(guān)系,實(shí)現(xiàn)所謂的多播.作為IP多播的替代方案,開(kāi)始時(shí)許多網(wǎng)絡(luò)構(gòu)建算法大多使用樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)數(shù)據(jù)傳遞.雖然這種方案能夠像IP多播一樣,與專(zhuān)用基礎(chǔ)路由(DedicatedInfrastructureRouters)很好的搭配,但是卻經(jīng)常會(huì)與帶有動(dòng)態(tài)結(jié)點(diǎn)的應(yīng)用層網(wǎng)絡(luò)搭配錯(cuò)誤.而且自主網(wǎng)絡(luò)結(jié)點(diǎn)會(huì)輕易地崩潰或離開(kāi),因此樹(shù)結(jié)構(gòu)是高度易損的.而這一問(wèn)題在對(duì)帶寬和連續(xù)性都有很高要求的流傳輸中,顯得更加嚴(yán)重.同時(shí)雖然像網(wǎng)孔和森林這樣的復(fù)雜結(jié)構(gòu)能局部地解決問(wèn)題,但其本身的實(shí)現(xiàn)卻過(guò)于復(fù)雜,而且經(jīng)常缺乏可擴(kuò)展性.從另一個(gè)角度講,把多播功能移植到應(yīng)用層同樣會(huì)導(dǎo)致更大的彈性;具體來(lái)說(shuō),所有的結(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ù),而它們之間沒(méi)有諸如父子關(guān)系,內(nèi)部外部關(guān)系和上行流下行流關(guān)系.換句話說(shuō),是數(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ò).尤其是考慮到一個(gè)半靜態(tài)的結(jié)構(gòu),無(wú)論多么有效,總是會(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ò),而其中的核心操作非常簡(jiǎn)單:每一個(gè)結(jié)點(diǎn)與一組伙伴周期性地交換數(shù)據(jù)可用性信息,從一個(gè)或多個(gè)伙伴那里接收自己所沒(méi)有的數(shù)據(jù),并把自己所擁有的數(shù)據(jù)提供應(yīng)需要的伙伴.我們將著重分析這種數(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)換.此外,關(guān)于結(jié)果的分析顯示出了網(wǎng)絡(luò)半徑與網(wǎng)絡(luò)大小的邏輯關(guān)系,這也說(shuō)明了DONet能夠在有限延遲的情況下進(jìn)行擴(kuò)展.為了實(shí)現(xiàn)傳輸實(shí)時(shí)流媒體的數(shù)據(jù)驅(qū)動(dòng)網(wǎng)絡(luò),大量的實(shí)際問(wèn)題需要考慮.在本文中,將要討論DONet中的若干關(guān)鍵問(wèn)題.包括伙伴關(guān)系的建立,數(shù)據(jù)可用性信息的編碼和交換,以及視頻數(shù)據(jù)是如何在伙伴間被提供和獲得的.這里將要提出一套可擴(kuò)展的成員關(guān)系和伙伴關(guān)系的管理算法和一個(gè)智能調(diào)度算法,這些方案將會(huì)在使用較低控制開(kāi)銷(xiāo)的情況下,為中高帶寬用戶提供高效連續(xù)的流傳輸,同時(shí)平穩(wěn)地將傳輸負(fù)載分配到正在參與的結(jié)點(diǎn)中,并使結(jié)點(diǎn)與異構(gòu)網(wǎng)絡(luò)相適應(yīng).通過(guò)Planetlab已經(jīng)在大范圍內(nèi)評(píng)估了DONet的性能.這些實(shí)驗(yàn)幾乎動(dòng)用了Planetlab跨越五大洲的所有可用結(jié)點(diǎn).實(shí)驗(yàn)結(jié)果說(shuō)明DONet在流速率和播放連續(xù)性上能到達(dá)很高的要求.此外,控制所帶來(lái)的額外開(kāi)銷(xiāo)和傳輸延遲都可以保持在很低的水平上.根據(jù)當(dāng)前掌握的材料,全球范圍的實(shí)驗(yàn)很少在文獻(xiàn)中提及.為此文章中列出了在實(shí)驗(yàn)當(dāng)中遇到的幾個(gè)典型問(wèn)題.并討論了影響實(shí)驗(yàn)結(jié)果和可能在將來(lái)影響PlanetLab開(kāi)展的因素.最后,在2004年5月30日,一個(gè)公開(kāi)的,基于Internet的DONet實(shí)現(xiàn)---CoolStreamingv.0.9發(fā)布了,它已經(jīng)能夠播放由一個(gè)免費(fèi)視頻效勞器所提供的實(shí)時(shí)體育節(jié)目,這個(gè)軟件最初只吸引了20個(gè)用戶,但是截至本文發(fā)布,超過(guò)30000的用戶(從獨(dú)立IP的統(tǒng)計(jì)上看)已經(jīng)使用過(guò)這個(gè)流媒體軟件,在一些頂峰時(shí)間甚至到達(dá)4000多用戶同時(shí)在線.先前的統(tǒng)計(jì)結(jié)果和用戶的反應(yīng)是十分鼓舞人心的,這也說(shuō)明了兩個(gè)有趣的事實(shí):第一,現(xiàn)在的Internet已經(jīng)有足夠的帶寬來(lái)支持電視質(zhì)量的數(shù)據(jù)流(450Kbps);第二,數(shù)據(jù)驅(qū)動(dòng)網(wǎng)絡(luò)越大,所傳送的數(shù)據(jù)流質(zhì)量將會(huì)越好.這兩點(diǎn)都再一次說(shuō)明了本文所提出的數(shù)據(jù)驅(qū)動(dòng)重疊網(wǎng)絡(luò)是用來(lái)解決多播視頻分配的可靠方案.II.相關(guān)工作

(本節(jié)翻譯:DriftingLeaves)在過(guò)去的十年里,出現(xiàn)過(guò)一些基于IP多播視頻的重要研究,可以參考[18].最近,又提出了許多有關(guān)網(wǎng)絡(luò)多播(OverlayMultiplySystem)的系統(tǒng),它們大體上分為兩類(lèi):基于代理協(xié)助(Proxy-assisted)的和基于P2P的.在傳統(tǒng)意義上,通常事先安排一整套效勞或應(yīng)用層上的代理,然后在這些錨點(diǎn)(AnchorNode)的協(xié)助下建立起一個(gè)高質(zhì)量的網(wǎng)絡(luò)[1],[2],[24],[26],[28].DONets屬于第二類(lèi),它不依賴(lài)于專(zhuān)用結(jié)點(diǎn)(Dedicatednode),但是能在自組織的自動(dòng)結(jié)點(diǎn)(AutonomousNodes)的基礎(chǔ)之上建立起一個(gè)網(wǎng)絡(luò).在這一局部中,我們將對(duì)現(xiàn)行的幾種網(wǎng)絡(luò)流協(xié)議作簡(jiǎn)略介紹,重點(diǎn)將放在那些完全遵循p2p模式的協(xié)議上.A.基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)及其擴(kuò)展像前面所提到的,許多網(wǎng)絡(luò)流協(xié)議采用基于IP多播的樹(shù)狀結(jié)構(gòu).在網(wǎng)絡(luò)結(jié)點(diǎn)之間構(gòu)建并維護(hù)一個(gè)高效的分布式樹(shù)結(jié)構(gòu),是這類(lèi)系統(tǒng)的關(guān)鍵.在CoopNet中,視頻源作為樹(shù)結(jié)構(gòu)的根,收集所有結(jié)點(diǎn)的信息,用于樹(shù)的構(gòu)造及維護(hù).因此集中式的算法將會(huì)非常有效.但這樣的作法必須依賴(lài)于一個(gè)功能強(qiáng)大的專(zhuān)用根結(jié)點(diǎn).同時(shí),像SpreadIt[10],NICE[12]和ZIGZAG[11],使用分布式算法通過(guò)一系列結(jié)點(diǎn),實(shí)現(xiàn)構(gòu)建和路由功能.在大規(guī)模網(wǎng)絡(luò)中,這些算法采用層次聚類(lèi)(HierarchicalClustering)的方式來(lái)到達(dá)最小的延遲(從樹(shù)的高度上講)或邊界結(jié)點(diǎn)的工作量(從扇出度(FanoutDegree)上講).但是,一個(gè)樹(shù)結(jié)構(gòu)中的內(nèi)部結(jié)點(diǎn)會(huì)有較大的負(fù)載,因此它的離開(kāi)或崩潰,將會(huì)在很大范圍內(nèi)導(dǎo)致后代結(jié)點(diǎn)的緩沖區(qū)缺乏.雖然已經(jīng)設(shè)計(jì)出了一些樹(shù)結(jié)構(gòu)的修復(fù)算法來(lái)適應(yīng)結(jié)點(diǎn)的動(dòng)態(tài)變化[12],[11],[23];但是樹(shù)的結(jié)構(gòu)仍會(huì)在高動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境中遭到頻繁破壞.還存在許多用來(lái)解決樹(shù)結(jié)構(gòu)負(fù)載不均衡或易損性的其他方案.例如建立以網(wǎng)孔為基礎(chǔ)的樹(shù)結(jié)構(gòu)(Narada及它的擴(kuò)展[14],Bullet[20]),維護(hù)一個(gè)多分布式樹(shù)結(jié)構(gòu)(SplitStream[19]),或者在分層編碼(PALS[29])和多重描述編碼(CoopNet[3])之間權(quán)衡.DONet通過(guò)引入一種簡(jiǎn)單明了的數(shù)據(jù)驅(qū)動(dòng)方案,來(lái)彌補(bǔ)這些缺陷.它并不需要維護(hù)一個(gè)更復(fù)雜的結(jié)構(gòu),或者依賴(lài)于先進(jìn)的編碼技術(shù),雖說(shuō)后一點(diǎn)也會(huì)在這個(gè)方案中起到一定作用.B.以閑談(Gossip)為基礎(chǔ)的協(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)都收到信息.閑談對(duì)象的隨機(jī)選擇,能使系統(tǒng)加強(qiáng)對(duì)隨機(jī)發(fā)生的意外退出的彈性,并且能夠進(jìn)行非中心式的操作.與[16]相似,DONet的成員管理中使用了閑談協(xié)議.DONet中的數(shù)據(jù)傳輸方法也局部受到閑談概念的影響.但無(wú)論如何,不能將閑談機(jī)制直接用于流傳輸,因?yàn)殡S機(jī)的傳送數(shù)據(jù)會(huì)帶來(lái)大量的冗余,而這對(duì)于有高帶寬需求的流應(yīng)用來(lái)說(shuō)更加嚴(yán)重.DONet中,使用了一個(gè)有力伙伴的選擇算法,和一個(gè)低開(kāi)銷(xiāo)的調(diào)度算法,以便于在大量減少冗余的情況下,智能地從眾多伙伴中接收數(shù)據(jù).先前進(jìn)行的一些有關(guān)P2P的請(qǐng)求式流傳輸(例如,[4],[5],[6],[7],[8],[9])的工作與閑談機(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)是通過(guò)半同步的結(jié)點(diǎn),到達(dá)實(shí)時(shí)流媒體傳輸,這就需要不同的解決方法.然而,在實(shí)際的Internet實(shí)現(xiàn)中,DONet的能力有很大的增強(qiáng),這也證明了那些在P2P請(qǐng)求式流傳輸研究中的論證.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)成員管理模塊(MembershipManager).負(fù)責(zé)維護(hù)網(wǎng)絡(luò)中一局部結(jié)點(diǎn)的相關(guān)信息;(2)伙伴管理模塊(PartnershipManager).負(fù)責(zé)與網(wǎng)絡(luò)中的其他結(jié)點(diǎn)建立并維護(hù)伙伴關(guān)系(譯者注:原文中的``Member''一詞此處被翻譯為``成員'';``Partner''被譯為``伙伴''.二者區(qū)別為:網(wǎng)絡(luò)中的一個(gè)結(jié)點(diǎn)被稱(chēng)為這個(gè)網(wǎng)絡(luò)中的成員;網(wǎng)絡(luò)中兩個(gè)直接相連的結(jié)點(diǎn)互為伙伴.);(3)調(diào)度器(Scheduler).負(fù)責(zé)視頻數(shù)據(jù)傳輸過(guò)程的調(diào)度工作.一個(gè)DONet結(jié)點(diǎn)的角色相對(duì)于視頻流中的每一個(gè)分段(Segment),既可以是分段的接收者(Receiver),也可以是提供者(Supplier),或二者皆是.結(jié)點(diǎn)角色確實(shí)定會(huì)根據(jù)分段的可用性信息(Segment'sAvailabilityInformation),動(dòng)態(tài)地調(diào)整.分段的可用性信息會(huì)在結(jié)點(diǎn)及其伙伴之間周期性地傳遞.(譯者注:原文中使用的是``periodicallyexchangedbetweenthenodeanditspartners''.翻譯為``周期性地在結(jié)點(diǎn)及其伙伴間傳遞''.但是譯者認(rèn)為,這種傳遞并非是嚴(yán)格地周期性動(dòng)作,即,兩次信息交換之間的時(shí)間間隔不一定是個(gè)常數(shù).因此,此處翻譯為``周期性地''似乎欠妥)但是最初提供資源的結(jié)點(diǎn)(SourceNode)是個(gè)例外它的角色永遠(yuǎn)是分段的提供者.在此,這種結(jié)點(diǎn)被稱(chēng)為``源結(jié)點(diǎn)''(OriginNode).它可以是一個(gè)專(zhuān)用于提供視頻效勞的效勞器,也可以是網(wǎng)絡(luò)中一個(gè)運(yùn)行了視頻效勞程序的計(jì)算機(jī).本節(jié)中,將討論模塊間的交互以及設(shè)計(jì)問(wèn)題.并給出了當(dāng)前的一些解決方案.它們分別被應(yīng)用于基于PlanetLab的和基于因特網(wǎng)的實(shí)現(xiàn)中.A.結(jié)點(diǎn)的參加和成員的管理每個(gè)DONet結(jié)點(diǎn)都有自己的一個(gè)唯一標(biāo)識(shí)符(UniqueIdentifier)比方可以是它的IP地址并且維護(hù)著一個(gè)緩存,用來(lái)存儲(chǔ)DONet網(wǎng)絡(luò)中一局部活潑成員的標(biāo)識(shí)符(以下稱(chēng)該緩存為mCache).在一個(gè)簡(jiǎn)單的結(jié)點(diǎn)添加算法中,一個(gè)新參加的結(jié)點(diǎn)首先去和源結(jié)點(diǎn)聯(lián)系.源結(jié)點(diǎn)會(huì)隨機(jī)地從自己的mCache中挑選出一個(gè)代理結(jié)點(diǎn)(DeputyNode),并將新參加的結(jié)點(diǎn)連接重定向到這個(gè)代理結(jié)點(diǎn)上.新結(jié)點(diǎn)會(huì)從代理結(jié)點(diǎn)上獲得一個(gè)成員的列表,把其中的成員視為候選伙伴.之后,與這些候選伙伴建立連接,由此確定了自己在網(wǎng)絡(luò)中的伙伴關(guān)系.總體來(lái)說(shuō),這一添加過(guò)程是可行的.因?yàn)樵唇Y(jié)點(diǎn)會(huì)在整個(gè)流的傳輸過(guò)程中始終存在,并且它的標(biāo)識(shí)符/地址是眾所周知的.重定向的過(guò)程使得新結(jié)點(diǎn)可以更加均勻地選擇伙伴(譯者注:此處原文為``Theredirectionenablesmoreuniformpartnerselectionsfornewlyjoinednodes''.該句的翻譯有些過(guò)分生硬.需再斟酌),同時(shí)很大程度上減少了源結(jié)點(diǎn)的負(fù)載.本節(jié)的最后,會(huì)對(duì)這個(gè)添加算法的改良進(jìn)行一些深入探討.實(shí)踐中,此處遇到的一個(gè)關(guān)鍵問(wèn)題是:如何建立并更新mCache.為了適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)變化,每個(gè)結(jié)點(diǎn)周期性地產(chǎn)生一個(gè)成員信息(MembershipMessage)用以聲明自己的存在;每個(gè)信息包含四項(xiàng):<seq_num,id,num_partner,time_to_live>.其中,seq_num表示該信息的序號(hào);id表示結(jié)點(diǎn)的標(biāo)識(shí)符;num_partner表示結(jié)點(diǎn)當(dāng)前擁有的伙伴數(shù)量;time_to_live表示本條信息剩余的生存時(shí)間.DONet網(wǎng)絡(luò)中,成員信息的傳遞使用了ScalableGossipMembership協(xié)議,即SCAM.關(guān)于這個(gè)協(xié)議的具體細(xì)節(jié),參考[21].此處,僅強(qiáng)調(diào)它所具有的三條重要性質(zhì):可擴(kuò)展(Scalable),輕量級(jí)(Light-weight)并且每個(gè)結(jié)點(diǎn)僅掌握局部信息(UniformPartialViewatEachNode).當(dāng)結(jié)點(diǎn)收到一個(gè)新的成員信息時(shí),它會(huì)在mCache中找到對(duì)應(yīng)id的成員信息記錄,如果seq_num大于記錄中的seq_num,則更新此條記錄.如果沒(méi)有找到對(duì)應(yīng)id的記錄,則在mCache中添加一條記錄存儲(chǔ)該成員信息.mCache中,每條成員信息記錄包含五項(xiàng):<seq_num,id,num_partner,time_to_live,last_update_time>.前四項(xiàng)與成員信息中對(duì)應(yīng)項(xiàng)的意義相同,是從收到的成員信息中拷貝來(lái)的.第五項(xiàng)記錄了最后一次更新該記錄的本地時(shí)間.以下兩種事件同樣可能引起mCache中記錄的更新:(1)在會(huì)話(gossip)過(guò)程中,某條記錄即將被傳遞給其他結(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.如果計(jì)算結(jié)果小于等于零,則該條記錄會(huì)被刪除,并且不會(huì)被傳遞,也不會(huì)被參加到伙伴列表.否則,對(duì)于第二種情況,代理結(jié)點(diǎn)會(huì)把該條記錄中的num_partner項(xiàng)加一.B.緩存映像的表示和交換Fig-2DONet中的伙伴關(guān)系實(shí)例(A為源結(jié)點(diǎn))Fig-2是DONet中伙伴關(guān)系的一個(gè)例子.如前所述,在DONet網(wǎng)絡(luò)中,伙伴關(guān)系和數(shù)據(jù)傳輸方向都不是固定的.一個(gè)視頻流被分解為多個(gè)定長(zhǎng)的分段.結(jié)點(diǎn)緩存中各個(gè)分段的可用性信息被表示為一個(gè)緩存映像(BufferMap,BM).每個(gè)結(jié)點(diǎn)會(huì)和它的伙伴不斷地交換各自的BM.之后,通過(guò)調(diào)度算法,確定從哪個(gè)伙伴處接收哪個(gè)分段.對(duì)于實(shí)時(shí)的多媒體流來(lái)說(shuō),DONet結(jié)點(diǎn)中的媒體播放過(guò)程是一個(gè)半同步(semi-synchronized)的過(guò)程(譯者注:``半同步''一詞似乎有些前后矛盾.從字面上看,翻譯為``半步''更佳.但是為了便于理解,這種``矮高粱''似的詞匯還是保存了下來(lái)).分析的結(jié)果說(shuō)明,DONet中分段傳輸?shù)钠骄訒r(shí)被限制在了一定范圍之內(nèi).實(shí)驗(yàn)的結(jié)果更近一步指出了,結(jié)點(diǎn)之間的遲延很少高于一分鐘.假設(shè)每個(gè)分段包含了一秒鐘的視頻信息,一個(gè)具有120個(gè)分段長(zhǎng)度的滑動(dòng)窗口便可以有效地構(gòu)成一個(gè)緩存,而滑動(dòng)窗口以外的分組則不在結(jié)點(diǎn)的考慮范圍之內(nèi).如此,在實(shí)現(xiàn)中,便可以使用120比特來(lái)表示一個(gè)BM.如果其中的某位被置一,則說(shuō)明該比特對(duì)應(yīng)的分段有效,即,該分段已經(jīng)被存儲(chǔ)在了緩存中;反之,若某比特被置零,則說(shuō)明該比特對(duì)應(yīng)的分段無(wú)效.滑動(dòng)窗口中第一個(gè)分段的序號(hào)(seq_num)存儲(chǔ)在額外的兩個(gè)字節(jié)中.對(duì)于一個(gè)非常長(zhǎng)的視頻節(jié)目來(lái)說(shuō),這個(gè)序號(hào)可能會(huì)由于溢出而被歸零(這樣的視頻節(jié)目至少應(yīng)該大于24小時(shí)).C.調(diào)度算法給定了一個(gè)結(jié)點(diǎn)和它伙伴的BM信息,調(diào)度算法則可以用來(lái)確定從哪個(gè)伙伴處獲得所需的分段.對(duì)于一個(gè)同構(gòu)(Homogenous),靜態(tài)(Static)的網(wǎng)絡(luò),循環(huán)魯棒(Round-robin)式的調(diào)度便足以.但是對(duì)于一個(gè)動(dòng)態(tài)(Dynamically)并且異構(gòu)(Heterogeneous)的網(wǎng)絡(luò)來(lái)說(shuō),更加智能的算法就顯得尤為重要了.一個(gè)調(diào)度的結(jié)果會(huì)受到兩個(gè)約束條件的影響:每個(gè)分段的截止時(shí)間(Deadline),以及與各個(gè)伙伴間的傳輸帶寬.第一個(gè)約束條件說(shuō)明,超過(guò)截止時(shí)間到達(dá)的分段數(shù)量應(yīng)該控制在最小.這個(gè)問(wèn)題實(shí)際上是``并行計(jì)算機(jī)調(diào)度問(wèn)題''(ParallelMachineScheduling)的一個(gè)變種,屬于NP類(lèi)問(wèn)題[25].因此很難找到一個(gè)最優(yōu)解.從實(shí)際角度出發(fā),調(diào)度算法必須能夠快速地適應(yīng)高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境.因此,我們采取了一種簡(jiǎn)單且能夠快速響應(yīng)的啟發(fā)式(Heuristic)算法.這個(gè)啟發(fā)式算法中,首先計(jì)算出資源的潛在提供者(PotentialSupplier)的數(shù)量(即,擁有所需分段的伙伴的數(shù)量).因?yàn)橐粋€(gè)分段如果對(duì)應(yīng)著較少的潛在提供者,那么將意味著這個(gè)分段會(huì)很難在截止時(shí)間之前到達(dá).算法會(huì)從僅有一個(gè)潛在提供者的分組開(kāi)始確定某一分組的提供者.之后是對(duì)應(yīng)有兩個(gè)潛在提供者的分組,以此類(lèi)推.如果一個(gè)分組對(duì)應(yīng)著多個(gè)潛在提供者,那么具有最高帶寬并且具有更長(zhǎng)可用時(shí)間的提供者會(huì)被選中.Fig-3列出了這個(gè)算法的偽碼.對(duì)于每個(gè)結(jié)點(diǎn),都將會(huì)執(zhí)行該算法.它的時(shí)間復(fù)雜度為O(W*B*M).在具體的實(shí)現(xiàn)中,每次執(zhí)行僅需15ms.計(jì)算的額外開(kāi)銷(xiāo)并不高.因此,它可以比較頻繁地運(yùn)行,從而更新調(diào)度策略.Fig-3每個(gè)DONet結(jié)點(diǎn)調(diào)度算法的偽碼(譯者注:個(gè)人認(rèn)為,該偽碼包含局部打印錯(cuò)誤:自Scheduling:一行起,向下四行,有:T[j,i].個(gè)人認(rèn)為應(yīng)該改為:t[j,i]第一個(gè)if語(yǔ)句中的for循環(huán),包含一個(gè)循環(huán)控制條件,原文為:j>k.個(gè)人認(rèn)為應(yīng)該改為j>i再向下五行,原文為supplier[n].個(gè)人認(rèn)為應(yīng)該改為supplier[i]最后一個(gè)for循環(huán),包含一個(gè)循環(huán)控制條件,原文為:j>k.個(gè)人認(rèn)為應(yīng)該改為j>i以上純屬個(gè)人臆斷,一切仍以原文為準(zhǔn))結(jié)點(diǎn)通過(guò)調(diào)度算法的計(jì)算獲得調(diào)度策略,把需要從同一個(gè)伙伴處獲得哪些分段的信息存儲(chǔ)在一個(gè)類(lèi)似BM的位序列中.之后,將這個(gè)位序列發(fā)送給相應(yīng)的伙伴.該伙伴會(huì)把位序列中所對(duì)應(yīng)的分段通過(guò)一個(gè)實(shí)時(shí)的傳輸協(xié)議發(fā)送給結(jié)點(diǎn).DONet并不依賴(lài)于某個(gè)特定的協(xié)議.和其他系統(tǒng)一樣,目前所采用的是TFRC(TCP-FriendlyRateControl)協(xié)議[31].BM信息和調(diào)度策略信息可以隨數(shù)據(jù)一并傳輸.這樣可以快速更新并且減少額外開(kāi)銷(xiāo).源結(jié)點(diǎn)在此始終作為資源提供者.并且所有的分段都存儲(chǔ)在它的緩存中.為了防止源結(jié)點(diǎn)過(guò)載,這里給出了一個(gè)適應(yīng)度較高的調(diào)度算法.如果需要,它還可以通過(guò)對(duì)外公布保存的緩存映射來(lái)控制負(fù)載.例如,一個(gè)源結(jié)點(diǎn)擁有M個(gè)伙伴,那么它可以把傳遞給第k個(gè)伙伴的BM設(shè)置為:這就是說(shuō),只有第(imodM)個(gè)伙伴才會(huì)從源結(jié)點(diǎn)處獲得第i個(gè)分段.其他的分段則來(lái)自別的伙伴.D.錯(cuò)誤的恢復(fù)和伙伴的篩選在DONet網(wǎng)絡(luò)中,一個(gè)結(jié)點(diǎn)可以在事先聲明后退出,或由于崩潰而意外退出.這兩種情況都可以在TFRC空轉(zhuǎn)一段時(shí)間或者BM信息傳遞過(guò)程中被檢測(cè)出來(lái).結(jié)點(diǎn)同時(shí)離開(kāi)的概率很小,受到離開(kāi)結(jié)點(diǎn)影響的結(jié)點(diǎn)會(huì)立即做出反應(yīng)根據(jù)剩下伙伴的BM信息重構(gòu)調(diào)度策略.除了這個(gè)恢復(fù)機(jī)制以外,下面提出的操作也同樣用于增強(qiáng)系統(tǒng)的恢復(fù)能力.聲明后退出:即將退出的結(jié)點(diǎn)會(huì)提交一個(gè)退出消息.這個(gè)信息的格式與成員信息一樣,只是num_partner這一項(xiàng)被設(shè)為-1.意外退出:一個(gè)結(jié)點(diǎn)的意外退出會(huì)被它的伙伴檢測(cè)到.這個(gè)伙伴會(huì)代替退出的結(jié)點(diǎn)來(lái)發(fā)布退出消息.退出消息的傳遞方式與成員信息的傳遞方式一樣.如果結(jié)點(diǎn)是意外退出的,冗余的退出消息也許會(huì)被退出結(jié)點(diǎn)的多個(gè)伙伴發(fā)布.但是只有第一個(gè)收到的退出消息會(huì)被允許繼續(xù)在網(wǎng)絡(luò)上傳播,其他的相同信息傳播則會(huì)被抑制.每個(gè)收到消息的結(jié)點(diǎn)會(huì)刪除各自mCache中對(duì)應(yīng)于退出結(jié)點(diǎn)的記錄.最后,每個(gè)結(jié)點(diǎn)會(huì)定期地從它的mCache中隨機(jī)選擇出結(jié)點(diǎn)并與之建立伙伴關(guān)系.這一操作的目的有兩個(gè):第一,它使得每個(gè)結(jié)點(diǎn)可以在一些伙伴退出的情況下,維護(hù)一定數(shù)量的伙伴;第二,它使得結(jié)點(diǎn)可以尋找到更高質(zhì)量的伙伴.在實(shí)現(xiàn)中,一個(gè)結(jié)點(diǎn)i評(píng)估它的伙伴結(jié)點(diǎn)j,使用函數(shù)max{si,j,sj,i}.其中,si,j表示單位時(shí)間內(nèi),結(jié)點(diǎn)i收到來(lái)自結(jié)點(diǎn)j的分段的平均數(shù)量.直覺(jué)上看,一個(gè)具有更大上傳帶寬和更多可用分段的伙伴會(huì)獲得更高的評(píng)估分?jǐn)?shù).由于一個(gè)結(jié)點(diǎn)既可以是資源提供者,也可以是接收者,因此需要計(jì)算兩個(gè)方向上的最大值.在尋找到新的伙伴后,為了保持伙伴數(shù)量的穩(wěn)定,伙伴列表中具有最低分?jǐn)?shù)的伙伴將會(huì)被拋棄.伙伴的數(shù)量,M,是一個(gè)很重要的設(shè)計(jì)參數(shù).它的影響將會(huì)在之后的理論分析和實(shí)驗(yàn)中做具體介紹.IV.網(wǎng)絡(luò)半徑的分析

(本節(jié)翻譯:默難)本節(jié)將會(huì)對(duì)DONet網(wǎng)絡(luò)的半徑進(jìn)行分析.所謂網(wǎng)絡(luò)半徑,指的是一個(gè)分段在傳遞過(guò)程中,從源結(jié)點(diǎn)到所有的目的結(jié)點(diǎn)的平均距離.和大多數(shù)文獻(xiàn)[11],[12],[27]相同,距離的單位是經(jīng)過(guò)網(wǎng)絡(luò)中結(jié)點(diǎn)的跳數(shù).這在一定程度上反應(yīng)了端到端的傳輸延遲.這里用到的分析模型是經(jīng)過(guò)簡(jiǎn)化的,結(jié)果顯示網(wǎng)絡(luò)半徑與網(wǎng)絡(luò)大小之間成對(duì)數(shù)關(guān)系.這說(shuō)明,DONet網(wǎng)絡(luò)中的端到端延遲是較小的,足以用來(lái)傳輸實(shí)時(shí)的流媒體.在DONet網(wǎng)絡(luò)中,分段可用性信息的傳遞路徑,可以用一棵廣度優(yōu)先搜索(BFS,Breadth-FirstSearch)的樹(shù)結(jié)構(gòu)來(lái)表示.源結(jié)點(diǎn)是樹(shù)的根結(jié)點(diǎn),處于第0層.第k層的結(jié)點(diǎn)與源結(jié)點(diǎn)之間相隔k跳.DONet的結(jié)點(diǎn)不會(huì)維護(hù)一個(gè)明確的結(jié)構(gòu),因此,每個(gè)結(jié)點(diǎn)可以在這個(gè)BFS樹(shù)中出現(xiàn)屢次.為了描述方便,把BFS樹(shù)中的結(jié)點(diǎn)稱(chēng)為s-結(jié)點(diǎn)(s-node).根據(jù)廣度優(yōu)先搜索的規(guī)則,s-結(jié)點(diǎn)按照在搜索時(shí)被訪問(wèn)的順序進(jìn)行編號(hào).這樣,根結(jié)點(diǎn)的編號(hào)為1.對(duì)于編號(hào)為t的s-結(jié)點(diǎn),它所對(duì)應(yīng)的DONet結(jié)點(diǎn)被表示為pt(譯者注:根據(jù)下面(t)函數(shù)的定義,此處應(yīng)為).假設(shè)伙伴之間的帶寬大約相等,并且一個(gè)分段到達(dá)一個(gè)結(jié)點(diǎn)的過(guò)程,是自根結(jié)點(diǎn)出發(fā),按照廣度優(yōu)先的算法搜索樹(shù)結(jié)構(gòu),直到該結(jié)點(diǎn)第一次出現(xiàn).Fig-4顯示了Fig-2的DONet網(wǎng)絡(luò)的BFS樹(shù)結(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):

也就是說(shuō),只有在s-結(jié)點(diǎn)t第一次在樹(shù)結(jié)構(gòu)中出現(xiàn)時(shí),函數(shù)值才為1.由于成員關(guān)系和伙伴關(guān)系協(xié)議是采用隨機(jī)的伙伴選擇方式,用N表示網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)量,因此則有:這里,f(t)表示編號(hào)為1至t的s-結(jié)點(diǎn)中,包含的DONet結(jié)點(diǎn)的數(shù)量.由此則有:f(t)-f(t-1)=(t).對(duì)(1)式兩遍同時(shí)求期望,則有:由此推導(dǎo)出:因?yàn)閒(1)=1,根據(jù)等式(3)可以推導(dǎo)出:這一關(guān)系給出了DONet結(jié)點(diǎn)數(shù)目關(guān)于s-結(jié)點(diǎn)編號(hào)的函數(shù).令tk表示第k層中最后一個(gè)s-結(jié)點(diǎn)的編號(hào),那么DONet網(wǎng)絡(luò)中其他結(jié)點(diǎn)與源結(jié)點(diǎn)之間的平均距離,即網(wǎng)絡(luò)半徑,則為:注意到,當(dāng)k趨近于無(wú)窮時(shí),有:.對(duì)于一個(gè)連通的網(wǎng)絡(luò)來(lái)說(shuō),可得:考慮一種穩(wěn)定的狀態(tài):每個(gè)DONet結(jié)點(diǎn)均擁有M個(gè)伙伴.那么對(duì)應(yīng)的BFS樹(shù)中,除了根結(jié)點(diǎn)擁有M棵子樹(shù)外,每個(gè)非葉子結(jié)點(diǎn)都擁有M-1棵子樹(shù).那么可以導(dǎo)出:將(6)式中的連加分解為兩局部:一局部是從k=0到k=logM-1N;另一局部是從k=1+logM-1N到正無(wú)窮.那么有:

當(dāng)M大于等于3時(shí),有(M-1)k>=(M-1)k.則eM-1^k<=e-(M-1)k.由此導(dǎo)出:由此,源結(jié)點(diǎn)到網(wǎng)絡(luò)中任意結(jié)點(diǎn)的平均距離則為O(logN).從式(4)和式(8)可以看出,從源結(jié)點(diǎn)出發(fā),在k跳之內(nèi)可以到達(dá)的結(jié)點(diǎn)的比例為.也就是說(shuō),對(duì)于包含500個(gè)結(jié)點(diǎn)的DONet網(wǎng)絡(luò),設(shè)M=4,那么,大約95%的結(jié)點(diǎn)可以在6跳之內(nèi)到達(dá).V.

基于全球范圍的性能評(píng)估

(本節(jié)翻譯:A-C由DriftingLeaves翻譯;D和E由默難翻譯)

關(guān)于DONet的原型,已經(jīng)進(jìn)行過(guò)多方面實(shí)驗(yàn).這一局部中,將會(huì)首先說(shuō)明在PlanetLab[30]環(huán)境下,實(shí)驗(yàn)系統(tǒng)是如何設(shè)計(jì).其次會(huì)列出一些典型的結(jié)果.最后,本文會(huì)指出在實(shí)驗(yàn)中所遇到的一些典型問(wèn)題,并討論它們對(duì)實(shí)驗(yàn)結(jié)果的影響.

Fig-5結(jié)點(diǎn)地理分布的快照

A.

實(shí)驗(yàn)系統(tǒng)的設(shè)計(jì)

這些實(shí)驗(yàn)幾乎動(dòng)用了PlanetLab的所有可用結(jié)點(diǎn),

而結(jié)點(diǎn)的總量在實(shí)驗(yàn)期間(2004年5月到2004年6月),到達(dá)了200個(gè)到300個(gè).每一個(gè)結(jié)點(diǎn)都運(yùn)行一個(gè)程序原型,扮演DONet結(jié)點(diǎn)的角色.源結(jié)點(diǎn)被設(shè)置在美國(guó)(,IP:2),而借助遠(yuǎn)程登錄,通過(guò)在香港(.hk,IP:8)的結(jié)點(diǎn)控制整個(gè)系統(tǒng),它也就是所謂的監(jiān)控結(jié)點(diǎn)(MonitoringNode).實(shí)際上這也是亞洲第一個(gè)接入PlanetLab的結(jié)點(diǎn)(從2003年1月開(kāi)始).Fig-5展示了一個(gè)在5月進(jìn)行的實(shí)驗(yàn)所動(dòng)用結(jié)點(diǎn)的地理分布快照.

對(duì)于這樣一個(gè)大范圍分布的實(shí)驗(yàn)臺(tái),如何有效地控制結(jié)點(diǎn)和收集報(bào)告,將會(huì)是一個(gè)挑戰(zhàn),因?yàn)闊o(wú)論是啟動(dòng)或升級(jí)程序,還是收集實(shí)驗(yàn)結(jié)果,所有的結(jié)點(diǎn)都將會(huì)集中地完成登錄,上傳或下載操作.所以設(shè)計(jì)一個(gè)自動(dòng)控制系統(tǒng)是很必要的.而同時(shí)實(shí)驗(yàn)系統(tǒng)應(yīng)該具有高度的可擴(kuò)展性,以便參加新的結(jié)點(diǎn)和性質(zhì).有趣的是,借助PlanetLab所提供的工具,以上目的也可以通過(guò)使用重疊網(wǎng)絡(luò)來(lái)到達(dá).

下面將簡(jiǎn)要描述實(shí)驗(yàn)系統(tǒng)的模塊,Fig-6描述了這一模塊的構(gòu)成.

Fig-6實(shí)驗(yàn)系統(tǒng)的模塊結(jié)構(gòu)圖

DONet模塊:DONet是使用Python---也就是Planet的編程語(yǔ)言,來(lái)實(shí)現(xiàn)的.在這一模塊中,對(duì)于并行事件的處理是采用具有非阻塞模式套接字的事件隊(duì)列來(lái)完成的,而不是多線程.正因?yàn)槌绦蚴菃尉€程的,可以防止許多在多線程編程下的復(fù)雜問(wèn)題,因此程序的調(diào)試和實(shí)現(xiàn)會(huì)更加簡(jiǎn)單,這也會(huì)使得原型的設(shè)計(jì)變得快捷.

控制臺(tái)和自動(dòng)機(jī)模塊:控制臺(tái)通過(guò)交互命令來(lái)便控制整個(gè)系統(tǒng).這些命令會(huì)是諸如參加,離開(kāi)DONet或改變參數(shù).而Python的突出性質(zhì)是能夠動(dòng)態(tài)地執(zhí)行指令.那么,新的特性和功能就能夠在防止重寫(xiě)和重新裝入整個(gè)程序的情況下參加.在控制臺(tái)中,同時(shí)設(shè)計(jì)了自動(dòng)機(jī)的模塊,它能夠自動(dòng)地開(kāi)始實(shí)驗(yàn)并執(zhí)行一系列在隊(duì)列中事先定義好的指令.這樣不僅能完成精確的時(shí)間控制,還能夠減輕長(zhǎng)時(shí)間實(shí)驗(yàn)(許多實(shí)驗(yàn)經(jīng)常會(huì)持續(xù)5個(gè)小時(shí))的監(jiān)控工作.

指令分發(fā)和報(bào)告收集模塊:由監(jiān)控結(jié)點(diǎn)直接連接到每一個(gè)結(jié)點(diǎn)來(lái)分發(fā)指令和收集報(bào)告,這樣的設(shè)計(jì)是不具有可擴(kuò)展性的.而使用另一個(gè)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)命令的分發(fā)將會(huì)很好地緩和這個(gè)問(wèn)題.在實(shí)際中,每一個(gè)指令都有唯一的序號(hào);一個(gè)結(jié)點(diǎn)接收到命令后,會(huì)把它轉(zhuǎn)發(fā)給一列自己的結(jié)點(diǎn),而這列結(jié)點(diǎn)就是先前在DONet模塊的mCache中獲取的那一列.由于指令在數(shù)量上是有限的,并且對(duì)于延遲敏感,采用泛洪式的方式來(lái)播送指令是一個(gè)合理的選擇.這樣的作法同時(shí)會(huì)有助于建立一個(gè),用于收集報(bào)告的逆向樹(shù)結(jié)構(gòu).在這個(gè)結(jié)構(gòu)中,有關(guān)喪失和路徑長(zhǎng)度等信息能在一些交叉結(jié)點(diǎn)(JuncionNode)處分類(lèi)合并,然后再傳回監(jiān)控結(jié)點(diǎn).綜上所述,就能在不讓監(jiān)控結(jié)點(diǎn)過(guò)重負(fù)載的情況下完成在線統(tǒng)計(jì).

在能自動(dòng)控制系統(tǒng)的情況下,創(chuàng)造一個(gè)穩(wěn)定的(使用持續(xù)結(jié)點(diǎn))或動(dòng)態(tài)的(使用動(dòng)態(tài)參加,離開(kāi)或異常退出的結(jié)點(diǎn))環(huán)境并不困難.下面將通過(guò)列舉一組有代表性的結(jié)果來(lái)說(shuō)明DONet在這兩種環(huán)境中的性能,并且指出一些關(guān)鍵的影響因素.

B.

穩(wěn)定環(huán)境下的性能

在第一組實(shí)驗(yàn)當(dāng)中,所有的結(jié)點(diǎn)都將會(huì)在一段初始化時(shí)段(1分鐘左右)內(nèi)參加,并在某個(gè)流的播放時(shí)間內(nèi)(120分鐘,一部電影的典型長(zhǎng)度)保持可用.默認(rèn)的流速率是500Kbps,每個(gè)分段都包含長(zhǎng)度為一秒鐘的流.每個(gè)結(jié)點(diǎn)會(huì)維持一個(gè)含有60個(gè)分段的劃動(dòng)窗口,或者說(shuō)是長(zhǎng)度為60秒的數(shù)據(jù)流,并會(huì)在接受到第一個(gè)分段10秒鐘后開(kāi)始播放.

控制開(kāi)銷(xiāo):成員關(guān)系管理使用了輕量級(jí)的gossip協(xié)議,DONet中的大多數(shù)控制信息是用來(lái)交換數(shù)據(jù)可用性信息的.因此伙伴數(shù)量成為決定控制開(kāi)銷(xiāo)的關(guān)鍵因素.Fig-7將控制流量描述為平均伙伴數(shù)量的函數(shù).開(kāi)銷(xiāo)自然會(huì)隨著伙伴數(shù)量的增長(zhǎng)而變大,但是相比于視頻流量,

甚至在伙伴超過(guò)5,6個(gè)情況下(控制流量少于總流量的2%),控制流量也是次要的.這個(gè)結(jié)果也給人一種直觀的印象---每個(gè)分段的可用性信息僅由1比特表示.

Fig-7在不同網(wǎng)絡(luò)規(guī)模下控制負(fù)載關(guān)于伙伴數(shù)量的函數(shù).(控制負(fù)載=每個(gè)結(jié)點(diǎn)控制流量/每個(gè)結(jié)點(diǎn)視頻流量).

Fig-8連續(xù)性信息關(guān)于伙伴數(shù)量的函數(shù).

播放連續(xù)性:維持播放的連續(xù)性是流應(yīng)用的首要目標(biāo).為了評(píng)估連續(xù)性,這里定義了連續(xù)性指標(biāo),它表示能在播放的截止時(shí)間前到達(dá)的分段數(shù)量與分段總量的比值.Fig-8將連續(xù)性指標(biāo)表示為伙伴數(shù)量M的函數(shù).連續(xù)性會(huì)隨著M的增長(zhǎng)而加大,因?yàn)槊總€(gè)結(jié)點(diǎn)都會(huì)有更多的資源提供者以供選擇.但是在伙伴超過(guò)4個(gè)之后,這種增長(zhǎng)將變得不再明顯.在Fig-9中將連續(xù)性指標(biāo)表示為流速率的函數(shù),可以看到,即使在高速率下,伙伴數(shù)量為4時(shí)仍然會(huì)到達(dá)很好的效果.考慮到控制開(kāi)銷(xiāo)會(huì)隨著伙伴數(shù)量的增長(zhǎng)而加大,M=4在實(shí)際中將會(huì)是一個(gè)很好的選擇,這一點(diǎn)在下面的實(shí)驗(yàn)中也同樣適用.

Fig-9連續(xù)性信息關(guān)于流速率的函數(shù).網(wǎng)絡(luò)規(guī)模=200結(jié)點(diǎn).

可擴(kuò)展性:從Fig-7中可以看出每個(gè)結(jié)點(diǎn)的控制開(kāi)銷(xiāo)幾乎與網(wǎng)絡(luò)規(guī)模無(wú)關(guān),這是因?yàn)閿?shù)據(jù)的可用性信息(BM)只在本地交換.同樣,相比于較小的網(wǎng)絡(luò),連續(xù)性指標(biāo)在大規(guī)模網(wǎng)絡(luò)中也沒(méi)有太大的變化.實(shí)際上,后文將會(huì)說(shuō)明,隨著網(wǎng)絡(luò)規(guī)模的增大,合作的程度將會(huì)增加,這往往會(huì)導(dǎo)致更好的播放連續(xù)性.一句話,DONet無(wú)論在網(wǎng)絡(luò)規(guī)模上還是流速率上都具有可擴(kuò)展性.

C.

動(dòng)態(tài)環(huán)境下的性能

下面將要檢測(cè)DONet在有結(jié)點(diǎn)動(dòng)態(tài)參加,離開(kāi)或意外退出時(shí)的性能.大多數(shù)的參數(shù)設(shè)置與前一組實(shí)驗(yàn)相同,只是在這里,每個(gè)結(jié)點(diǎn)會(huì)按照ON/OFF模型來(lái)改變它的狀態(tài):在ON時(shí)段,結(jié)點(diǎn)會(huì)在網(wǎng)絡(luò)中保持活潑,而在OFF時(shí)段,結(jié)點(diǎn)會(huì)離開(kāi)(或意外退出).ON和OFF都在平均為T(mén)的時(shí)間內(nèi)呈指數(shù)分部.

Fgi-10在不同網(wǎng)絡(luò)規(guī)模下控制流量關(guān)于ON/OFF平均周期的函數(shù)

Fig-10將不同網(wǎng)絡(luò)規(guī)模下的控制流量表示為ON/OFF周期的函數(shù).可以看到,控制流量會(huì)隨著ON/OFF周期的縮短(例如,動(dòng)態(tài)結(jié)點(diǎn)執(zhí)行更多動(dòng)作)而有輕微的增長(zhǎng).這些附加的控制流量主要是由離開(kāi)或意外退出的聲明引起的,但是像前面所提到的,相對(duì)于總體流量,這只是次要局部.

Fig-11在不同網(wǎng)絡(luò)規(guī)模下連續(xù)性指標(biāo)關(guān)于ON/OFF平均周期的函數(shù)

Fig-11描述了連續(xù)性指標(biāo)在不同ON/OFF周期下的變化.更短的ON/OFF周期肯定會(huì)導(dǎo)致更低的連續(xù)性指標(biāo),但是下降不是很明顯.在使用DONet內(nèi)部一些恢復(fù)機(jī)制的情況下,即使在高動(dòng)態(tài)的網(wǎng)絡(luò),DONet的連續(xù)性指標(biāo)仍然是可以接受的(在1分鐘之內(nèi)找到新的資源結(jié)點(diǎn)).

D.

與基于樹(shù)結(jié)構(gòu)網(wǎng)絡(luò)的比較

本節(jié)將把DONet與傳統(tǒng)的樹(shù)結(jié)構(gòu)網(wǎng)絡(luò)進(jìn)行一個(gè)比較.公平起見(jiàn),樹(shù)中的每個(gè)結(jié)點(diǎn)的度被限制在三個(gè)以?xún)?nèi).這就是說(shuō),除了源結(jié)點(diǎn)可以擁有四棵子樹(shù)以外,其他非葉子結(jié)點(diǎn)最多只能擁有三棵子樹(shù)(加上一個(gè)父結(jié)點(diǎn),則總度數(shù)為4.這與DONet中每個(gè)結(jié)點(diǎn)的度數(shù)相同).

然而,考慮到異構(gòu)能力和帶寬的約束,讓每個(gè)結(jié)點(diǎn)都支持三個(gè)子樹(shù)似乎并不現(xiàn)實(shí).在這種情況下,一些子樹(shù)將被移到更底的層次,直到約束條件解除.同時(shí),會(huì)使用一種樹(shù)修復(fù)算法,使得在結(jié)點(diǎn)異常退出的時(shí)候,把一些下游結(jié)點(diǎn)移到上游.

首先比較的是端到端的延遲(end-to-enddelay).由于PlanetLab中結(jié)點(diǎn)的時(shí)鐘并非完全同步,所以準(zhǔn)確地計(jì)算出每個(gè)分段的端到端延遲并非是件易事.因此,使用了一種更簡(jiǎn)單的方法來(lái)衡量延遲計(jì)算跳數(shù)(hop-count)的方法.利用這種方法的衡量結(jié)果被顯示在Fig-13中.盡管樹(shù)結(jié)構(gòu)經(jīng)常被認(rèn)為可以實(shí)現(xiàn)最短的延遲,但測(cè)試結(jié)果顯示,無(wú)論是在穩(wěn)定的還是動(dòng)態(tài)的網(wǎng)絡(luò)中,基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)都表現(xiàn)的不那么盡如人意.如前所述,這是由于上傳帶寬的限制可以在很大程度上增加樹(shù)的高度.Fig-12顯示了本次實(shí)驗(yàn)中的樹(shù)結(jié)構(gòu).結(jié)點(diǎn)總數(shù)是231,但是樹(shù)的高度卻是19而一顆231個(gè)結(jié)點(diǎn)的滿平衡三叉樹(shù)的高度卻只有五層.

Fig-12一個(gè)包含231個(gè)結(jié)點(diǎn)的基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)

Fig-13DONet和基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)中的平均跳數(shù)延遲.

Fig-14在連續(xù)性指標(biāo)方面,DONet網(wǎng)絡(luò)和基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)的比較.(Y軸:連續(xù)性指標(biāo);X軸:ON/OFF周期;網(wǎng)絡(luò)大小分別為50和200個(gè)結(jié)點(diǎn))

Fig-15在一段時(shí)間內(nèi),DONet和基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)中的連續(xù)性指標(biāo)的采樣(采樣自從第10分鐘起至第20分鐘)

如Fig-14所示,在連續(xù)性指標(biāo)方面,采用樹(shù)的拓?fù)浣Y(jié)構(gòu)遠(yuǎn)不如DONet網(wǎng)絡(luò).特別是在較大的動(dòng)態(tài)網(wǎng)絡(luò)中.這是因?yàn)闃?shù)結(jié)構(gòu)的網(wǎng)絡(luò)對(duì)于非葉子結(jié)點(diǎn)的異常退出非常敏感.從Fig-12中可以看到,有些非葉子結(jié)點(diǎn)在樹(shù)結(jié)構(gòu)中起到了至關(guān)重要的作用.比方根結(jié)點(diǎn)的最右邊那個(gè)子結(jié)點(diǎn),它僅僅擁有一顆子樹(shù)它或者它的子結(jié)點(diǎn)的異常退出,都可以導(dǎo)致下游結(jié)點(diǎn)的緩沖區(qū)缺乏,而這就意味著網(wǎng)絡(luò)中會(huì)有大約3/4的結(jié)點(diǎn)受到影響.為了更進(jìn)一步指出樹(shù)結(jié)構(gòu)的易損性,Fig-15顯示了在一段時(shí)間內(nèi),200個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中的連續(xù)性指標(biāo).顯然,在連續(xù)性指標(biāo)方面,樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)不僅比DONet網(wǎng)絡(luò)的低,而且還表現(xiàn)出了很大的波動(dòng)性.比方,在800至900秒?yún)^(qū)間,連續(xù)性指標(biāo)嚴(yán)重下跌,甚至低于了0.4.根據(jù)當(dāng)時(shí)的記錄顯示,這是根結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)離開(kāi)所導(dǎo)致的.而這種情況在DONet中則很少見(jiàn).因?yàn)榻Y(jié)點(diǎn)的負(fù)載被平等地分擔(dān)開(kāi),并且傳輸?shù)穆窂绞歉鶕?jù)數(shù)據(jù)的可用性動(dòng)態(tài)確定的.

值得注意的是,哪怕樹(shù)結(jié)構(gòu)是滿且平衡的,它在動(dòng)態(tài)網(wǎng)絡(luò)中依然比DONet網(wǎng)絡(luò)更加易損.為此,對(duì)于由結(jié)點(diǎn)離開(kāi)或崩潰而導(dǎo)致的播放間斷,作一個(gè)簡(jiǎn)單的分析,為了方便描述,將結(jié)點(diǎn)的離開(kāi)或崩潰統(tǒng)稱(chēng)為結(jié)點(diǎn)失效(Nodefailure).假設(shè)失效的概率為Pf.引入另一個(gè)變量P0,表示一個(gè)相關(guān)結(jié)點(diǎn)(在樹(shù)結(jié)構(gòu)中指失效節(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn),在DONet中指它的一個(gè)伙伴)在t時(shí)間內(nèi)無(wú)法找到新的資源提供者的概率.Ps表示一個(gè)結(jié)點(diǎn)可以在它的相關(guān)結(jié)點(diǎn)提出請(qǐng)求后便馬上提供上傳的概率.P0和Ps的值都依賴(lài)于網(wǎng)絡(luò)維護(hù)的算法,和網(wǎng)絡(luò)/結(jié)點(diǎn)的性能.比方修復(fù)算法,緩沖區(qū)大小,上傳帶寬等.在實(shí)際中,假設(shè)樹(shù)結(jié)構(gòu)中的絕大局部非葉子結(jié)點(diǎn)都給M-1個(gè)子結(jié)點(diǎn)提供效勞,那么Ps可以適當(dāng)高一些,比方等于0.5.

在DONet網(wǎng)絡(luò)中,每個(gè)結(jié)點(diǎn)擁有M個(gè)伙伴.假設(shè)只能有一個(gè)結(jié)點(diǎn)可能替換失效節(jié)點(diǎn)成為資源提供者,那么一個(gè)非失效節(jié)點(diǎn)在delta_t時(shí)間內(nèi)找不到新的資源提供者的概率為:

那么,出現(xiàn)流間斷的結(jié)點(diǎn)數(shù)量的期望是:

上述的結(jié)果顯然是低估了.因?yàn)槲覀兒雎粤艘粋€(gè)事實(shí):活潑的伙伴結(jié)點(diǎn)可以協(xié)同工作為一個(gè)結(jié)點(diǎn)提供資源.這已經(jīng)在之前的調(diào)度算法中提及了.同樣,在樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)中,出現(xiàn)流間斷的結(jié)點(diǎn)數(shù)量的期望是(推導(dǎo)的細(xì)節(jié)參見(jiàn)附錄):

這里,h表示一顆滿且平衡的樹(shù)的高度.

Fig-16在t

時(shí)間內(nèi),出現(xiàn)流間斷結(jié)點(diǎn)的比例的期望

Fig-16在數(shù)值上顯示了兩個(gè)網(wǎng)絡(luò)的性能.這顯示了,哪怕樹(shù)是滿且平衡的,DONet網(wǎng)絡(luò)依然可以在播放的連續(xù)性上表現(xiàn)得更好些.在大規(guī)模,并且結(jié)點(diǎn)失效概率較高的網(wǎng)絡(luò)中,差距則更為明顯.值得注意的是,由于在網(wǎng)絡(luò)層次上DONet與基于樹(shù)結(jié)構(gòu)的結(jié)點(diǎn)沒(méi)有差異,因此,基于DONet算法的結(jié)點(diǎn)可以與基于樹(shù)結(jié)構(gòu)算法的結(jié)點(diǎn)協(xié)同工作,而運(yùn)算的復(fù)雜度方面,DONet顯然更加簡(jiǎn)便.

E.

總結(jié)及展望

總體說(shuō)來(lái),DONet的性能足以用于實(shí)時(shí)的流媒體傳輸.它在控制上的額外開(kāi)銷(xiāo)非常低,大約僅相當(dāng)于視頻流量的1%,并且這一比值不會(huì)隨著網(wǎng)絡(luò)的擴(kuò)大而增長(zhǎng).和基于樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)相比,DONet的播放連續(xù)性更佳,特別是在一種高度動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境中.并且端到端延遲也比樹(shù)結(jié)構(gòu)的網(wǎng)絡(luò)要小.

實(shí)踐中也說(shuō)明,實(shí)現(xiàn)一個(gè)DONet的原型并不難.這即是由于它本身的簡(jiǎn)單性,也因?yàn)镻lanetLab提供的出色支持.畢竟,PlanetLab方案依然在開(kāi)展中并且還未成熟.在此討論一些有代表性的觀點(diǎn)以及由此得到的啟示.

可擴(kuò)展性(Scalability):命令分發(fā)和報(bào)告收集系統(tǒng)的實(shí)現(xiàn),使得DONet可以運(yùn)行于更多的結(jié)點(diǎn)之上.如今限制它規(guī)模的僅僅是PlanetLab中的結(jié)點(diǎn)數(shù)量.而且,如Fig-7所示,大多數(shù)的PlanetLab結(jié)點(diǎn)都分布于北美和歐洲.這僅僅能反映出當(dāng)今局部因特網(wǎng)的情況.為了創(chuàng)造一個(gè)更接近于因特網(wǎng)的網(wǎng)絡(luò)環(huán)境,我們期待著有更多其他國(guó)家結(jié)點(diǎn)的參加.

可再現(xiàn)性(Reproducibility):與前人在這種非完全控制(not-fully-controlled)的環(huán)境下所遇到的問(wèn)題相同,基于PlanetLab的實(shí)驗(yàn)同樣面臨著可再現(xiàn)性的問(wèn)題.但是不管怎么樣,PlanetLab網(wǎng)絡(luò)在幾個(gè)小時(shí)之內(nèi)是可以保持相對(duì)穩(wěn)定的.所以這個(gè)問(wèn)題并沒(méi)有那么嚴(yán)重,并且連續(xù)的幾次實(shí)驗(yàn)在總體上是具有可比性的.

可描述性(Representability):PlanetLab的穩(wěn)定性在一定程度上是由于網(wǎng)絡(luò)中的應(yīng)用較少,因此額外的流量較少.實(shí)驗(yàn)盡量模擬了當(dāng)前因特網(wǎng)的環(huán)境,因此有意地參加了一些額外流量,并且抑制了注入速率以防超出了規(guī)定帶寬.另一點(diǎn)需要考慮的就是源結(jié)點(diǎn)的為止.在本次實(shí)驗(yàn)中,選擇的源結(jié)點(diǎn)幾本都在美國(guó),因?yàn)榇蠖鄶?shù)PlanetLab結(jié)點(diǎn)都在那里.同時(shí)也使用了香港的結(jié)點(diǎn),盡管與其他結(jié)點(diǎn)相隔較遠(yuǎn),但由于香港與美國(guó)/歐洲之間的連接較通暢,因此得到的結(jié)果也類(lèi)似.現(xiàn)在正在聯(lián)系更多的位于其他大洲的結(jié)點(diǎn),以它們?yōu)樵唇Y(jié)點(diǎn),用于更深入的實(shí)驗(yàn).VI.CoolStreaming:DONet的實(shí)現(xiàn)和它的擴(kuò)展

(本節(jié)翻譯:DriftingLeaves)在DONet的基礎(chǔ)上,一個(gè)基于Internet的實(shí)現(xiàn)---CoolStreaming在2004年5月30日發(fā)布了第一個(gè)公開(kāi)版(v.0.9).CoolStreamingv.0.9包含了2000行Python源代碼,這個(gè)版根源于以PlanetLab為基礎(chǔ)的實(shí)驗(yàn)原型,并且在實(shí)驗(yàn)完成的兩星期之內(nèi)就發(fā)布了.這也再一次說(shuō)明了DONet的簡(jiǎn)單.它目前支持RealVideo和WindowsMedia格式,不過(guò)只要用戶安裝了支持其他視頻格式的播放器,就可以實(shí)現(xiàn)其他格式視頻的播放.此外,它的實(shí)現(xiàn)與平臺(tái)無(wú)關(guān).無(wú)論是Unix,Windows,或者其他的操作系統(tǒng),只要是支持Python和所播放的視頻格式,均可以使用它.像其他的Internet應(yīng)用一樣,CoolStreaming能否成功依賴(lài)于它所傳送的內(nèi)容.然而,又不像傳統(tǒng)的用戶/效勞器模型,重疊網(wǎng)絡(luò)沒(méi)有一個(gè)擁有豐富資源,并由其所有者完成升級(jí)的專(zhuān)用結(jié)點(diǎn).此外,它還會(huì)涉及到許多諸如版權(quán)問(wèn)題,以及關(guān)于它們的深入研究,但這些超出了本文所研究的范圍.更重要的是,我們沒(méi)有意圖,也沒(méi)有能力成為內(nèi)容提供者.那么,有一個(gè)實(shí)際且快速的解決方案:使DONet(CoolStreaming)成為內(nèi)容提供者和用戶之間的能力放大器(CapacityAmplifier).換句話說(shuō),它會(huì)最終成為網(wǎng)絡(luò)基礎(chǔ)設(shè)施的一局部.到現(xiàn)在為止,CoolStreaming已經(jīng)用來(lái)播放實(shí)時(shí)體育節(jié)目(450Kbps–755KbpsRealVideo/Windowsmedia格式),資源是由一個(gè)免費(fèi)的視頻效勞器提供的.這個(gè)效勞器接受匿名訪問(wèn),但是它的能力有限.結(jié)果,許多遲來(lái)的用戶在頂峰時(shí)段不能直接與效勞器建立連接,這也給用戶和效勞器操作人員帶來(lái)了許多不愉快的經(jīng)歷.而現(xiàn)在,通過(guò)安裝CoolStreaming和重定向Realplay