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

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

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