一種p2p播電網(wǎng)dpvod系統(tǒng)

一種p2p播電網(wǎng)dpvod系統(tǒng)

視頻點(diǎn)播（vod）是互聯(lián)網(wǎng)上最迷人的服務(wù)之一。傳統(tǒng)的vod系統(tǒng)采用c.s或擴(kuò)展的c.s結(jié)構(gòu)，如松散的多服務(wù)器系統(tǒng)、高性能的服務(wù)器、集群、純分布規(guī)律和基于代理的端點(diǎn)系統(tǒng)。上述系統(tǒng)的視頻源被存儲(chǔ)在一組服務(wù)器上。所有用戶都直接從服務(wù)器請(qǐng)求數(shù)據(jù)。每個(gè)用戶都單獨(dú)占用視頻流。由于服務(wù)系統(tǒng)的傳輸帶寬和服務(wù)器數(shù)量有限，它無法滿足大量服務(wù)。組播為VoD大規(guī)模應(yīng)用提供了可能,組播技術(shù)可分為IP網(wǎng)絡(luò)層組播和應(yīng)用層組播.基于IP組播的VoD系統(tǒng)在網(wǎng)絡(luò)層建立組播樹,以多路復(fù)用的方式共享媒體流,能大量節(jié)約帶寬和減輕服務(wù)器負(fù)載,如Patching.但由于路由器支持不足、擁塞控制、可靠性管理等問題,基于IP組播的VoD服務(wù)難以在短期內(nèi)廣泛實(shí)用.基于P2P的組播為當(dāng)前網(wǎng)絡(luò)環(huán)境下VoD的實(shí)際應(yīng)用提供了新的思路,基本方法是用戶通過存儲(chǔ)部分流數(shù)據(jù),并利用之為其他用戶提供服務(wù),從而實(shí)現(xiàn)多用戶共享同一條媒體流,能有效地減少服務(wù)器資源占用,提高系統(tǒng)的可擴(kuò)展性.研究者主要從以下方面提高P2P組播的性能:接近性策略、采用超級(jí)節(jié)點(diǎn)、結(jié)合流媒體編碼技術(shù),構(gòu)建不同類型的組播結(jié)構(gòu),如樹、森林或網(wǎng)絡(luò)等.P2P組播在廣播應(yīng)用研究中已取得較大進(jìn)展,但由于實(shí)時(shí)點(diǎn)播的特殊要求,P2P點(diǎn)播應(yīng)用進(jìn)展仍較緩慢,還存在急需解決的問題:可擴(kuò)展性,在服務(wù)器并發(fā)流通道數(shù)一定的情況下,盡量滿足大量用戶的點(diǎn)播請(qǐng)求;可靠性,由于P2P節(jié)點(diǎn)行為的不可預(yù)測(cè),節(jié)點(diǎn)頻繁隨意地退出系統(tǒng),用戶服務(wù)隨時(shí)可能被中斷,因此要盡量保證用戶的點(diǎn)播服務(wù)質(zhì)量.針對(duì)上述問題,提出DPVoD點(diǎn)播系統(tǒng)結(jié)構(gòu),系統(tǒng)設(shè)計(jì)了高效低開銷的節(jié)點(diǎn)狀態(tài)控制協(xié)議和組播樹鄰居組織管理機(jī)制,在此基礎(chǔ)上通過有效的節(jié)點(diǎn)加入和失效恢復(fù)等策略提高系統(tǒng)性能.對(duì)系統(tǒng)基本性能進(jìn)行理論分析和仿真實(shí)驗(yàn),結(jié)果表明,系統(tǒng)具有較高的可擴(kuò)展性和可靠性.1dpvad:基于平臺(tái)的調(diào)度優(yōu)化設(shè)計(jì)在已有的P2P點(diǎn)播研究中,Narada系統(tǒng)中引入了應(yīng)用層多播概念,給出協(xié)議設(shè)計(jì)原則并設(shè)計(jì)了全分布式的多播協(xié)議.Hefeeda等人提出的混合P2P點(diǎn)播結(jié)構(gòu)根據(jù)物理接近性原則組織多播組,以多源方式接收流數(shù)據(jù),利用性能強(qiáng)的節(jié)點(diǎn)充當(dāng)超級(jí)節(jié)點(diǎn),協(xié)助系統(tǒng)進(jìn)行查詢和數(shù)據(jù)分發(fā).P2Cast是Patching的P2P應(yīng)用,用戶的Patching流可從服務(wù)器或其他用戶獲取.Zigzag是一種分層的多播流媒體系統(tǒng),用戶節(jié)點(diǎn)度被限制在一定范圍內(nèi),以避免網(wǎng)絡(luò)瓶頸和減小端到端延遲.Promise利用底層網(wǎng)絡(luò)信息來協(xié)助父節(jié)點(diǎn)選擇,通過監(jiān)視節(jié)點(diǎn)狀態(tài)來幫助節(jié)點(diǎn)失效恢復(fù),動(dòng)態(tài)切換當(dāng)前和備用父節(jié)點(diǎn).VTN流媒體模型采用介于C?S和P2P之間的混合結(jié)構(gòu)來分發(fā)視頻流,在基于媒體數(shù)據(jù)分段的基礎(chǔ)上,設(shè)計(jì)了VirtualTheaterNetwork來組織用戶和服務(wù)器的視頻流分發(fā)和接收.在Chi等人提出的點(diǎn)播協(xié)作節(jié)點(diǎn)輔助緩存搜索BAS策略中,通過減小協(xié)作節(jié)點(diǎn)集合的索引大小來提高協(xié)作節(jié)點(diǎn)搜索效率,并基于Deadline敏感的網(wǎng)絡(luò)編碼,提出增加協(xié)作節(jié)點(diǎn)間的調(diào)度時(shí)效的算法.Chunkyspread是基于非結(jié)構(gòu)化P2P的一種層次結(jié)構(gòu)的多組播樹流媒體結(jié)構(gòu),采用基于權(quán)重的隨機(jī)游走方式來尋找鄰居.MeshCast是基于網(wǎng)狀結(jié)構(gòu)的應(yīng)用層流媒體多播協(xié)議,結(jié)合流言機(jī)制來實(shí)現(xiàn)用戶間的通信,通過運(yùn)用基于mesh肢解法來適應(yīng)用戶間的連接關(guān)系的變化.GridVOD是基于P2P網(wǎng)格的點(diǎn)播系統(tǒng),其基于興趣劃分自治組的松散管理機(jī)制的容錯(cuò)性和可靠性不高,管理過于復(fù)雜.P2VoD節(jié)點(diǎn)采用變長(zhǎng)隊(duì)列緩存視頻流數(shù)據(jù),把緩存有相同最低序號(hào)數(shù)據(jù)塊的節(jié)點(diǎn)組合為一代,下一代的節(jié)點(diǎn)可以從上一代的任意節(jié)點(diǎn)請(qǐng)求視頻流數(shù)據(jù).這種緩存機(jī)制造成某些節(jié)點(diǎn)只能緩存相當(dāng)少的視頻流數(shù)據(jù),而浪費(fèi)有緩存能力的節(jié)點(diǎn)的緩存空間PeerVoD是對(duì)P2VoD的改進(jìn),它采用定長(zhǎng)緩存以期望用戶能得到較多的候選父節(jié)點(diǎn),固定長(zhǎng)度的緩存策略不能適應(yīng)異構(gòu)的網(wǎng)絡(luò)用戶環(huán)境.上述工作從結(jié)構(gòu)、編碼、容錯(cuò)機(jī)制等方面提升點(diǎn)播系統(tǒng)性能,但仍未能很好地解決可擴(kuò)展和可靠性問題.提出的DPVoD系統(tǒng)從充分利用組播組和用戶資源出發(fā),對(duì)點(diǎn)播的多個(gè)環(huán)節(jié)進(jìn)行優(yōu)化,以提高系統(tǒng)性能.DPVoD在以下方面區(qū)別于已有研究工作:1)建立簡(jiǎn)單有效的組鄰居關(guān)系,組之間建立協(xié)同工作機(jī)制,如子樹遷移、容錯(cuò)恢復(fù);2)高效低開銷的節(jié)點(diǎn)關(guān)系和狀態(tài)管理機(jī)制;3)可定制的用戶緩存滿足用戶的異構(gòu)性和充分利用用戶資源;4)最小剩余時(shí)間優(yōu)先的父節(jié)點(diǎn)選擇原則,可提高系統(tǒng)容量和用戶加入成功率;5)首次提出可能會(huì)引起服務(wù)性能嚴(yán)重下降的結(jié)尾雪崩問題及解決方案;6)對(duì)類似結(jié)構(gòu)的系統(tǒng)的基本性能給出了理論分析結(jié)果.2dpvod系統(tǒng)結(jié)構(gòu)2.1用戶視頻流的響應(yīng)面DPVoD系統(tǒng)由服務(wù)器和用戶節(jié)點(diǎn)組成,節(jié)點(diǎn)總數(shù)為N.視頻源以FEC(forwarderrorcorrection)方式編碼,按播放時(shí)長(zhǎng)分為連續(xù)的T個(gè)時(shí)間單元,每個(gè)單元對(duì)應(yīng)一段視頻數(shù)據(jù).所有用戶都定制一定大小的緩存來存儲(chǔ)最近收到的部分視頻數(shù)據(jù),并用此來向后到達(dá)的節(jié)點(diǎn)提供服務(wù).直接從服務(wù)器請(qǐng)求并接收流數(shù)據(jù)的節(jié)點(diǎn)稱為組長(zhǎng)節(jié)點(diǎn),共享同一并發(fā)流的所有用戶形成一棵應(yīng)用組播樹.多個(gè)并發(fā)流則形成相對(duì)獨(dú)立的多棵組播樹,組之間可在錯(cuò)誤恢復(fù)等方面進(jìn)行協(xié)作.定義1.同一棵組播樹中的用戶集合稱為一個(gè)用戶組,以Group(i)表示,對(duì)應(yīng)第i條并發(fā)流.在不引起混淆之處,并發(fā)流、組播樹、組播組和用戶組表示的意義相同.定義2.如用戶Ci從Cj接收視頻流數(shù)據(jù),則Cj稱為Ci的父節(jié)點(diǎn),Ci稱為Cj的子節(jié)點(diǎn).Ci的子節(jié)點(diǎn)集合表示為son(i).對(duì)節(jié)點(diǎn)Ci,t(i)為其加入系統(tǒng)的時(shí)刻,min(i)和max(i)分別表示Ci緩存的數(shù)據(jù)塊的最小、最大序號(hào),next(i)表示Ci將要接收的下一個(gè)數(shù)據(jù)塊的序號(hào),next(i)=max(i)+1.定義3.對(duì)系統(tǒng)中的任意節(jié)點(diǎn)Ci和Cj,如果在當(dāng)前時(shí)刻滿足min(j)≤next(i)≤max(j),且Cj不為Ci的父節(jié)點(diǎn),則Cj可能成為Ci候選父節(jié)點(diǎn),如果Cj被Ci記錄并維護(hù),則稱Cj為Ci的候選父節(jié)點(diǎn),Ci的候選父節(jié)點(diǎn)集合表示為father(i).定義4.如系統(tǒng)中某節(jié)點(diǎn)緩存有視頻源的第1個(gè)數(shù)據(jù)塊,則稱該節(jié)點(diǎn)為開放節(jié)點(diǎn);而對(duì)于系統(tǒng)中的任意用戶組,如果包含開放節(jié)點(diǎn),則稱之為開放組,否則為閉合組.定義5.組播樹中,如果以某節(jié)點(diǎn)為根的子樹中存在開放節(jié)點(diǎn),則稱該子樹為開放子樹.假設(shè):1)任意時(shí)刻,每個(gè)用戶都只從一個(gè)節(jié)點(diǎn)接收視頻流數(shù)據(jù);2)節(jié)點(diǎn)加入系統(tǒng)的時(shí)間序列服從強(qiáng)度為λ的泊松分布,用戶定制緩存長(zhǎng)度L介于[τ1,τ2]之間,且服從均勻分布,均值E(L)為τ;3)節(jié)點(diǎn)加入時(shí)均從視頻流的第1個(gè)數(shù)據(jù)塊開始請(qǐng)求;4)一個(gè)用戶組的最大用戶數(shù)量上限為MaxVol.2.2狀態(tài)控制和群體管理2.2.1選擇可靠的選取數(shù)據(jù)對(duì)于動(dòng)態(tài)變化的P2P點(diǎn)播系統(tǒng),與文件共享系統(tǒng)相比,節(jié)點(diǎn)間的關(guān)系更加緊密,實(shí)時(shí)性要求更高,因此需要高效可靠的協(xié)議來管理節(jié)點(diǎn)和交換信息.為此設(shè)計(jì)分布式控制協(xié)議DDCP(DPVoDdistributedcontrolprotocol)進(jìn)行系統(tǒng)狀態(tài)的控制和管理,內(nèi)容包括節(jié)點(diǎn)之間關(guān)系建立和消息交換的規(guī)則.處于組播樹中不同位置的節(jié)點(diǎn)的角色不同,下面按服務(wù)器、組長(zhǎng)和普通節(jié)點(diǎn)對(duì)DDCP分別描述.1)服務(wù)器.僅維護(hù)少量必要信息,以最大限度減小服務(wù)器負(fù)載,包括:組ID及數(shù)量、組狀態(tài)、組長(zhǎng)緩存大小及當(dāng)前請(qǐng)求數(shù)據(jù)塊序號(hào)等.與類似系統(tǒng)不同,DPVoD的服務(wù)器不維護(hù)用戶組緩存的最小數(shù)據(jù)塊范圍,以減輕服務(wù)器負(fù)擔(dān),因?yàn)樵摂?shù)據(jù)時(shí)刻變化,維護(hù)該信息的開銷較大,而該信息對(duì)斷點(diǎn)恢復(fù)卻沒有明顯的作用.2)組長(zhǎng).與服務(wù)器交換組狀態(tài)信息、請(qǐng)求流數(shù)據(jù);維護(hù)組節(jié)點(diǎn)數(shù)、開放狀態(tài);組擁有的流數(shù)據(jù)塊范圍,最大塊號(hào)為其自身的請(qǐng)求的數(shù)據(jù)塊,最小塊號(hào)定時(shí)從最新加入本組的節(jié)點(diǎn)處獲得并校正更新;與其他組建立組之間的鄰居關(guān)系,以進(jìn)行快速的節(jié)點(diǎn)查找和定位.3)普通用戶節(jié)點(diǎn).普通用戶在加入系統(tǒng)時(shí)確定父節(jié)點(diǎn),從父節(jié)點(diǎn)請(qǐng)求數(shù)據(jù);記錄子節(jié)點(diǎn)IP地址、緩存大小和當(dāng)前請(qǐng)求數(shù)據(jù)塊號(hào),并將數(shù)據(jù)分發(fā)給各子節(jié)點(diǎn);記錄組長(zhǎng)節(jié)點(diǎn)IP和狀態(tài),如用戶為本組的最新節(jié)點(diǎn),則還定時(shí)將當(dāng)前請(qǐng)求的數(shù)據(jù)塊號(hào)發(fā)送給服務(wù)器;維護(hù)候選父節(jié)點(diǎn)IP和狀態(tài),以在父節(jié)點(diǎn)出錯(cuò)時(shí)快速恢復(fù).在P2P流媒體中,候選父節(jié)點(diǎn)是重要的容錯(cuò)途徑,但過多的候選父節(jié)點(diǎn)會(huì)帶來較多的維護(hù)開銷.因此,對(duì)候選父節(jié)點(diǎn)按穩(wěn)定性和回應(yīng)速度排序,將候選父節(jié)點(diǎn)分為兩部分:對(duì)于排位靠前的部分候選父節(jié)點(diǎn)做全面維護(hù),稱為可信候選父節(jié)點(diǎn);而對(duì)于其他的候選父節(jié)點(diǎn),則標(biāo)記刪除,不再維護(hù)其信息,但仍然被保存,稱為不可信候選父節(jié)點(diǎn).當(dāng)可信候選父節(jié)點(diǎn)數(shù)量不足時(shí),則通過不可信父節(jié)點(diǎn)或組長(zhǎng)進(jìn)行補(bǔ)充.DDCP的候選父節(jié)點(diǎn)管理機(jī)制有效地減少了維護(hù)開銷,同時(shí)保證了在需要時(shí)能快速找到合適的父節(jié)點(diǎn).2.2.2含組間的組合如果組之間能協(xié)同工作,將有助于增加系統(tǒng)容量,提高負(fù)載平衡、容錯(cuò)和快速失效恢復(fù)能力,為此建立組鄰居關(guān)系.設(shè)視頻塊序號(hào)空間為Ω,其元素從1～N,組i擁有的視頻塊序號(hào)為Ω的子集Ω(i),由各組視頻塊集合之間的空間關(guān)系,將組之間的幾何關(guān)系定義為相離、相交和包含.如圖1所示,組1和其他組相離,組2和組3組4相交,組3與組4為包含.組關(guān)系初始化在組形成時(shí)進(jìn)行.新組建立時(shí),如系統(tǒng)中存在開放組,則新組與開放組為包含,與已閉合組則為相離.相交則是在組工作過程中由包含關(guān)系發(fā)展而形成的.根據(jù)組之間的幾何關(guān)系建立組鄰居關(guān)系.強(qiáng)鄰居關(guān)系:相交或包含關(guān)系的組之間可進(jìn)行子樹遷移、斷點(diǎn)恢復(fù)等操作,因此這些組之間建立強(qiáng)鄰居關(guān)系,定時(shí)交換組信息.弱鄰居關(guān)系:相離組之間無共有數(shù)據(jù)塊序號(hào),不能進(jìn)行如斷點(diǎn)恢復(fù)的協(xié)作,但如其中一個(gè)組為開放組,則仍可以在新節(jié)點(diǎn)加入時(shí)提供快速的父節(jié)點(diǎn)查找.因此相離的兩個(gè)組中如存在開放組,則在這兩個(gè)組之間建立弱鄰居關(guān)系,僅維護(hù)組狀態(tài),當(dāng)其中的開放組變?yōu)殚]合狀態(tài)時(shí),該鄰居關(guān)系解除.組鄰居關(guān)系由組長(zhǎng)建立和維護(hù).如在點(diǎn)播過程中,由于節(jié)點(diǎn)退出、傳輸延遲等原因而導(dǎo)致組幾何關(guān)系發(fā)生變化,則組鄰居關(guān)系相應(yīng)變化.2.2.3基于sm算法的子樹遷移節(jié)點(diǎn)緩存大小和到達(dá)系統(tǒng)的分布規(guī)律,決定了系統(tǒng)中開放節(jié)點(diǎn)的數(shù)量.但在實(shí)際系統(tǒng)中,為減輕容錯(cuò)壓力和增大可靠性,對(duì)組規(guī)模(包括節(jié)點(diǎn)數(shù)和樹高)有限制,超過限制的組將不能接收新節(jié)點(diǎn),即使存在開放節(jié)點(diǎn);而另一些組可能規(guī)模較小,但無開放節(jié)點(diǎn).從而導(dǎo)致可用開放節(jié)點(diǎn)數(shù)小于實(shí)際存在的數(shù)量,造成新節(jié)點(diǎn)加入拒絕率增加或服務(wù)器負(fù)載增大.因此通過組之間的優(yōu)化操作來提高系統(tǒng)性能.本文提出子樹遷移(subtreemigration,SM)算法,將部分規(guī)模較大的組的子樹遷移到規(guī)模較小的組,以實(shí)現(xiàn)組之間的平衡,減小節(jié)點(diǎn)失效的影響和錯(cuò)誤恢復(fù)的難度.如遷移的子樹包含開放節(jié)點(diǎn),則還可使已閉合組重新開放,使即將閉合組的閉合時(shí)間推遲,從而提高開放節(jié)點(diǎn)利用率,以較小的代價(jià)換取系統(tǒng)整體性能的提升.SM算法描述如下:1)設(shè)Group(i)的組長(zhǎng)Ci發(fā)現(xiàn)需引進(jìn)子樹,則向鄰居組發(fā)送子樹遷入請(qǐng)求,請(qǐng)求中包含本組的數(shù)據(jù)塊范圍和對(duì)遷入子樹的要求.2)收到請(qǐng)求后,鄰居組長(zhǎng)根據(jù)規(guī)則判斷,選擇一個(gè)合適的子樹,將子樹根節(jié)點(diǎn)信息發(fā)送給Ci.3)設(shè)Ci收集到的待遷入子樹根節(jié)點(diǎn)集為Φ,Ci根據(jù)需要從中選擇一個(gè),假設(shè)為Cj,向Cj發(fā)送請(qǐng)求遷移消息.4)Cj收到消息后,如果同意,則改變父節(jié)點(diǎn),離開原來組,加入到Group(i),如果拒絕,則返回拒絕消息.如組滿足以下條件,則需遷入子樹:對(duì)開放組,組的開放節(jié)點(diǎn)數(shù)小于閾值或所有開放節(jié)點(diǎn)的最大開放時(shí)間小于閾值,且組樹高小于規(guī)定值;對(duì)閉合組,組節(jié)點(diǎn)數(shù)和樹高小于閾值.圖2為子樹遷移圖例.系統(tǒng)中有2個(gè)組,各對(duì)應(yīng)一個(gè)并發(fā)流,圖2(a)為遷移前的系統(tǒng)結(jié)構(gòu)和狀態(tài),Group(1)有2個(gè)開放節(jié)點(diǎn),節(jié)點(diǎn)數(shù)為7,Group(2)無開放節(jié)點(diǎn),節(jié)點(diǎn)數(shù)為3.假設(shè)Group(1)滿足遷入條件,Group(2)滿足遷出條件,且遷移成功,圖2(b)表示遷移后的情況.可看到,遷移后,由于引進(jìn)了開放節(jié)點(diǎn),Group(2)重新成為開放組,可以接納新節(jié)點(diǎn),Group(1)由于遷出了部分節(jié)點(diǎn),節(jié)點(diǎn)數(shù)減小到5.如前所述,各組相對(duì)均衡的節(jié)點(diǎn)數(shù)和開放節(jié)點(diǎn)數(shù)將從多方面提高系統(tǒng)性能.2.3開放系統(tǒng),把是否可加入開放節(jié)點(diǎn)為容錯(cuò)和優(yōu)選需要,新節(jié)點(diǎn)在加入前需獲得多個(gè)待選父節(jié)點(diǎn),為此,充分利用用戶節(jié)點(diǎn)掌握的信息,新節(jié)點(diǎn)可向系統(tǒng)中任意節(jié)點(diǎn)請(qǐng)求加入,從而降低服務(wù)器負(fù)擔(dān)和實(shí)現(xiàn)新節(jié)點(diǎn)的快速加入.設(shè)系統(tǒng)中節(jié)點(diǎn)Cold收到新節(jié)點(diǎn)Cnew的加入請(qǐng)求消息,Cold可為普通節(jié)點(diǎn)、組長(zhǎng)或服務(wù)器,處理機(jī)制如下:1)Cold為普通節(jié)點(diǎn).如自身已閉合,則回復(fù)拒絕消息.若自身為開放,且請(qǐng)求為組長(zhǎng)轉(zhuǎn)發(fā)而來,則向Cnew發(fā)送同意加入消息.若請(qǐng)求從非組長(zhǎng)節(jié)點(diǎn)轉(zhuǎn)發(fā)而來,且自身為開放,則詢問組長(zhǎng)是否可加入新節(jié)點(diǎn),如組長(zhǎng)回復(fù)可加入,則向Cnew發(fā)送同意加入消息,否則回復(fù)拒絕.2)Cold為組長(zhǎng).若本組為開放組,且滿足組播樹節(jié)點(diǎn)數(shù)量和高度等要求,則將請(qǐng)求轉(zhuǎn)發(fā)給開放節(jié)點(diǎn);若本組已閉合,則將請(qǐng)求轉(zhuǎn)發(fā)給鄰居組中的開放組組長(zhǎng).如本組和鄰居組均閉合,則將請(qǐng)求轉(zhuǎn)發(fā)給服務(wù)器.3)Cold為服務(wù)器.將請(qǐng)求轉(zhuǎn)發(fā)給開放組,如沒有開放組,如服務(wù)器有空閑并發(fā)流,則創(chuàng)建新組,并以該用戶為組長(zhǎng),否則用戶加入失敗.得到多個(gè)待選父節(jié)點(diǎn)后,Cnew從中選擇父節(jié)點(diǎn),并將其他待選父節(jié)點(diǎn)加入到候選父節(jié)點(diǎn)集合中.DPVoD的父節(jié)點(diǎn)選擇機(jī)制綜合考慮了帶寬、時(shí)延和剩余開放時(shí)間(remainopentime,ROT)因素.帶寬指Cold的剩余服務(wù)帶寬.ROT是Cold剩下的可接納新節(jié)點(diǎn)的時(shí)間,如選擇ROT較小的節(jié)點(diǎn)作為父節(jié)點(diǎn),則能充分利用將要關(guān)閉的開放節(jié)點(diǎn),從整體上增加系統(tǒng)的容量,減少新節(jié)點(diǎn)加入時(shí)被拒絕的概率.DPVoDD的父節(jié)點(diǎn)選擇機(jī)制在滿足帶寬和時(shí)延條件的基本要求之上,采用MinROT(minimalROT)規(guī)則,優(yōu)先選擇ROT小的節(jié)點(diǎn),使新節(jié)點(diǎn)加入到很快就要從開放狀態(tài)進(jìn)入閉合狀態(tài)的節(jié)點(diǎn).下面分析按MinROT和MaxROT(選擇ROT值最大的節(jié)點(diǎn)為父節(jié)點(diǎn))規(guī)則選擇父節(jié)點(diǎn)對(duì)系統(tǒng)性能的影響.設(shè)節(jié)點(diǎn)到達(dá)平均間隔為1λ=1,λτ=3,即加入系統(tǒng)的時(shí)間到當(dāng)前時(shí)刻小于等于3的節(jié)點(diǎn)為開放狀態(tài),系統(tǒng)有2個(gè)組Group(1)和Group(2),MaxVol為5.表1為節(jié)點(diǎn)到達(dá)時(shí)間及加入的一種情況.Time為5時(shí),已有4個(gè)節(jié)點(diǎn)加入系統(tǒng),其中C2,C3,C4為開放節(jié)點(diǎn),現(xiàn)在以不同規(guī)則加入Cnew.1根據(jù)minrot規(guī)則Cnew加入到Group(1),以C2為父節(jié)點(diǎn).在時(shí)刻6,兩個(gè)組均為開放狀態(tài),系統(tǒng)剩余容量最大為5.2節(jié)點(diǎn)容量的影響Cnew加入到Group(2),以C4為父節(jié)點(diǎn),在時(shí)刻6,Group(1)關(guān)閉,新節(jié)點(diǎn)只能加入到Group(2),系統(tǒng)剩余的最大容量為2.因此與采用MinROT相比,系統(tǒng)容量被大幅減小.表1中Time為5表示按MaxROT加入的情況.可見,采用MinROT規(guī)則加入新節(jié)點(diǎn)可增大系統(tǒng)容量、提高并發(fā)流利用率,平衡各組播樹的大小和高度.2.4節(jié)點(diǎn)失效恢復(fù)性在松散的P2P環(huán)境中,用戶可能隨時(shí)失效,而由于組播樹中節(jié)點(diǎn)之間的關(guān)聯(lián)性和流數(shù)據(jù)傳遞的依賴性,節(jié)點(diǎn)失效將影響到關(guān)聯(lián)節(jié)點(diǎn)的點(diǎn)播服務(wù),因此需要設(shè)計(jì)相應(yīng)的失效恢復(fù)機(jī)制.將節(jié)點(diǎn)失效分為點(diǎn)播中失效和點(diǎn)播完失效來處理.2.4.1fail的子節(jié)點(diǎn)點(diǎn)播中失效指用戶在點(diǎn)播過程中,由于網(wǎng)絡(luò)中斷或主動(dòng)退出等原因而發(fā)生失效.點(diǎn)播中失效是不可預(yù)知的,失效節(jié)點(diǎn)處于組播樹越上游,子孫節(jié)點(diǎn)越多,可能造成的損失就越大.點(diǎn)播中失效發(fā)生后,利用候選父節(jié)點(diǎn)、組長(zhǎng)、鄰居組和服務(wù)器來恢復(fù).設(shè)失效節(jié)點(diǎn)為Cfail,處理機(jī)制如下:1)如Cfail為組播樹的葉節(jié)點(diǎn),則其父節(jié)點(diǎn)停止向其發(fā)送數(shù)據(jù),并終止父子關(guān)系,組長(zhǎng)將Cfail刪除并更新組信息,如組狀態(tài)因此而變?yōu)殚]合,則還需更新組鄰居信息.2)如Cfail為非葉節(jié)點(diǎn),則其父節(jié)點(diǎn)不再向其提供服務(wù),而其子節(jié)點(diǎn)需要恢復(fù)服務(wù).Cfail的子節(jié)點(diǎn)首先利用候選父節(jié)點(diǎn)來恢復(fù)服務(wù);如失敗,則向組長(zhǎng)請(qǐng)求恢復(fù)服務(wù),組長(zhǎng)優(yōu)先在本組內(nèi)查詢是否有合適的節(jié)點(diǎn);如恢復(fù)失敗,則組長(zhǎng)將請(qǐng)求提交給具強(qiáng)鄰居關(guān)系的鄰居組長(zhǎng);如仍然失敗,則組長(zhǎng)將恢復(fù)請(qǐng)求和已請(qǐng)求恢復(fù)但失敗的組編號(hào)轉(zhuǎn)發(fā)給服務(wù)器,服務(wù)器則通過向其他組查詢或創(chuàng)建新并發(fā)流來恢復(fù).3)如Cfail為組長(zhǎng),則其子節(jié)點(diǎn)通過候選父節(jié)點(diǎn)恢復(fù),若失敗,則向服務(wù)器請(qǐng)求恢復(fù).由于利用標(biāo)記刪除方法管理選父節(jié)點(diǎn),對(duì)候選父節(jié)點(diǎn)進(jìn)行優(yōu)化控制和維護(hù),因此候選父節(jié)點(diǎn)的質(zhì)量有保證,失效恢復(fù)的成功率和效率相應(yīng)提高.利用動(dòng)態(tài)的組鄰居關(guān)系增加了失效恢復(fù)的成功率,同時(shí)減少了向服務(wù)器請(qǐng)求恢復(fù)的概率.2.4.2抗辯結(jié)合同圖像組播的分析在無約束的Internet對(duì)等環(huán)境中,節(jié)點(diǎn)點(diǎn)播完成后,大多會(huì)立即退出,而不會(huì)等待子節(jié)點(diǎn)的數(shù)據(jù)接收完畢.由于組播樹從上至下的流分發(fā)方式,總是組長(zhǎng)首先點(diǎn)播完而退出,其子節(jié)點(diǎn)必須尋找新的父節(jié)點(diǎn),但這些子節(jié)點(diǎn)也將在時(shí)間1λ(平均)內(nèi)完成點(diǎn)播而退出.以此類推,一旦最初的組長(zhǎng)點(diǎn)播完退出,將引發(fā)類似多米諾骨牌效應(yīng)的連續(xù)點(diǎn)播完失效,造成連續(xù)和頻繁的節(jié)點(diǎn)服務(wù)重定位或服務(wù)被中斷,甚至大量節(jié)點(diǎn)被迫退出系統(tǒng)的情況發(fā)生.上述點(diǎn)播完失效引起的現(xiàn)象和問題稱為結(jié)尾雪崩(tailsnowslide,TS),已有系統(tǒng)對(duì)此問題均未提及.本文提出平滑過渡算法(gracefullytransitingalogrithm,GTA)來處理TS問題.點(diǎn)播完失效行為不可避免,但卻有規(guī)律,服務(wù)器和組長(zhǎng)都可根據(jù)節(jié)目時(shí)長(zhǎng)和當(dāng)前組長(zhǎng)請(qǐng)求的數(shù)據(jù)塊號(hào)而預(yù)測(cè)到組長(zhǎng)的點(diǎn)播結(jié)束時(shí)間,而提前進(jìn)行處理.系統(tǒng)中可能存在其他組組長(zhǎng)已緩存了結(jié)尾視頻,但由于其緩存較大而還將繼續(xù)點(diǎn)播一段時(shí)間,可充分利用這些節(jié)點(diǎn)來完成最后視頻段的點(diǎn)播,以減少并發(fā)流的占用.因此當(dāng)組長(zhǎng)退出后,其子節(jié)點(diǎn)可向服務(wù)器或其他滿足條件的組長(zhǎng)請(qǐng)求繼續(xù)服務(wù).GTA算法如下:1)設(shè)組長(zhǎng)Ci發(fā)現(xiàn)其剩余停留時(shí)間T-next(i)達(dá)到預(yù)先規(guī)定的閾值,則選取Cj作為繼任,Cj的屬性滿足next(j)=max(next(k)|Ck∈son(i)),并向Cj發(fā)送請(qǐng)求繼任消息,Cj收到消息后,如同意,則向Ci回復(fù)確認(rèn)消息,否則返回拒絕消息.如Ci不能確定繼任,則轉(zhuǎn)到6).2)如Ci確定了繼任Cj,Ci向服務(wù)器或強(qiáng)鄰居關(guān)系組組長(zhǎng)告知Cj將成為繼任,并附上next(j);收到消息后,服務(wù)器或其他組長(zhǎng)如找到合適的節(jié)點(diǎn)Cp可作為Cj的父節(jié)點(diǎn),則將此信息返回給Cj.3)Ci向{Ck|Ck∈son(i),Ck≠Cj}發(fā)消息,告知Ck將作為自己的繼任.4)經(jīng)過查詢,如Cj尚有滿足要求的候選父節(jié)點(diǎn),則將以之作為新的父節(jié)點(diǎn);否則Cj與Cp聯(lián)系,若Cp能滿足Cj加入的條件,則Cj將以Cp為父節(jié)點(diǎn).這里選擇父節(jié)點(diǎn)的要求包括滿足父子關(guān)系以及組播樹屬性等條件.5)Ci將組相關(guān)信息交給Cj,Ci點(diǎn)播完成后退出.如Cj已經(jīng)找到新的非服務(wù)器的父節(jié)點(diǎn),則Cj直接從新父節(jié)點(diǎn)處請(qǐng)求數(shù)據(jù);否則將直接從服務(wù)器請(qǐng)求數(shù)據(jù),并接替Ci成為組長(zhǎng);如服務(wù)器在限定時(shí)間內(nèi)沒有收到Cj的消息,則認(rèn)為該組點(diǎn)播已經(jīng)全部完成,關(guān)閉并刪除相應(yīng)并發(fā)流.6)Ci向子節(jié)點(diǎn)發(fā)送將退出消息,點(diǎn)播完成后退出.子節(jié)點(diǎn)收到消息后重新尋找父節(jié)點(diǎn),處理過程與普通節(jié)點(diǎn)中途退出的情況相同.待Ci退出后,服務(wù)器刪除Ci和對(duì)應(yīng)組.下面理論分析采用GTA算法而減少的服務(wù)重定位或中斷的次數(shù).假設(shè)所有節(jié)點(diǎn)均正常完成點(diǎn)播,點(diǎn)播完后立即退出,其子節(jié)點(diǎn)均重定位服務(wù)或服務(wù)被中斷,除最初的組長(zhǎng)之外,每個(gè)節(jié)點(diǎn)至少要進(jìn)行一次服務(wù)重定位或點(diǎn)播中斷處理,任意組播組的平均節(jié)點(diǎn)數(shù)E(Z)(見定理1)等于eλτ,因此如不采用GTA算法,由點(diǎn)播完失效而引起服務(wù)重定位和中斷的次數(shù)大于eλτ-1,對(duì)整個(gè)系統(tǒng),則次數(shù)平均為(eλτ-1)乘以組的數(shù)量.由上分析可見,在用戶量較大和服務(wù)峰值時(shí),GTA能極大地減少服務(wù)重定位和中斷次數(shù),以一定的消息量換取了點(diǎn)播服務(wù)的平穩(wěn)進(jìn)行.而在類似系統(tǒng)中,上述情況不可避免地會(huì)毫無準(zhǔn)備的發(fā)生,從而導(dǎo)致系統(tǒng)的服務(wù)質(zhì)量急劇下降.3不超過國家網(wǎng)絡(luò)帶寬限制情況下的開放時(shí)間設(shè)視頻源時(shí)長(zhǎng)為T,不考慮用戶退出和子樹遷移的情況,從理論上分析系統(tǒng)基本性能,證明過程中用到隨機(jī)過程和概率論的相關(guān)知識(shí).限于篇幅,具體的證明過程在此被省略.定理1.單組播組擁有最大用戶數(shù)Z的均值為E(Z)=eλτ.E(Z)與λ和τ正相關(guān),即在不超過網(wǎng)絡(luò)帶寬限制的情況下,用戶到達(dá)越密集,用戶定制的緩存越大,系統(tǒng)容量越大.推論1.單一組的開放時(shí)間Topen的均值為(eλτ-1)λ.定義6.對(duì)于某組,從首個(gè)節(jié)點(diǎn)加入起,到所有節(jié)點(diǎn)離開為止,該組存在的時(shí)間,定義為組的生命周期TGroup.推論2.單并發(fā)流情況下,TGroup=T?τ+eλτ?1λ.ΤGroup=Τ-τ+eλτ-1λ.定理2.用戶到來不被拒絕,觀看時(shí)長(zhǎng)為T的影片所需最小并發(fā)流數(shù)MinStream=λT?2λτeλτ+λτ?1+1.ΜinStream=λΤ-2λτeλτ+λτ-1+1.說明用戶到達(dá)越頻繁,用戶緩存越大,服務(wù)器的負(fù)載越輕,當(dāng)服務(wù)器提供的并發(fā)流數(shù)大于MinStream時(shí),用戶以強(qiáng)度λ到達(dá)均能成功加入系統(tǒng)(按平均概率).4動(dòng)態(tài)環(huán)境下dpvad性能分析采用GT-ITM工具生成底層AS網(wǎng)絡(luò),包括有4個(gè)transit節(jié)點(diǎn),12個(gè)stub域和96～144個(gè)stub節(jié)點(diǎn),每個(gè)stub節(jié)點(diǎn)連接一個(gè)局域網(wǎng).設(shè)視頻流傳輸所需帶寬一定,系統(tǒng)可用帶寬定義為:transit節(jié)點(diǎn)之間、transit和stub節(jié)點(diǎn)之間帶寬為25條并發(fā)流,其他類型節(jié)點(diǎn)之間帶寬為7條并發(fā)流,每個(gè)用戶最大子節(jié)點(diǎn)數(shù)為7,消息通信不占用帶寬.節(jié)點(diǎn)之間按最短路徑轉(zhuǎn)發(fā)數(shù)據(jù).服務(wù)器置于transit節(jié)點(diǎn),用戶按參數(shù)為λ的泊松流規(guī)律到達(dá),隨機(jī)分布到各局域網(wǎng),用戶緩存在(min)上均勻分布.視頻時(shí)長(zhǎng)T為100min,根據(jù)需要,實(shí)驗(yàn)時(shí)間為100或200min.分別進(jìn)行了靜態(tài)和動(dòng)態(tài)環(huán)境(有節(jié)點(diǎn)退出)下的實(shí)驗(yàn).以UNICAST,PeerVoD和P2VoD為對(duì)比系統(tǒng).圖3為限制MaxVol=20時(shí),已閉合并發(fā)流的平均用戶數(shù)隨λ變化.在λ<1時(shí),用戶到達(dá)較稀疏,新節(jié)點(diǎn)可選的候選父節(jié)點(diǎn)很少,父節(jié)點(diǎn)選擇算法起的作用小,各系統(tǒng)閉合并發(fā)流的平均用戶數(shù)相差不大.隨著λ的增加,候選父節(jié)點(diǎn)數(shù)增加,DPVoD的父節(jié)點(diǎn)選擇策略從整體上提高了系統(tǒng)容量,因此能接納更多的用戶,并發(fā)流的利用率得到提高.圖4為λ變化時(shí),系統(tǒng)占用并發(fā)流數(shù)的變化對(duì)比.當(dāng)