文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Scalable On-Demand Streaming of Non-Linear Media
侵权投诉

Scalable On-Demand Streaming of Non-Linear Media

Abstract--- A conventional video file contains a single temporally-ordered sequence of video frames. Clients requesting on-demand streaming of such a file receive (all or intervals of) the same content. For popular files that receive many requests during a

widthrequiredforvariousclassesofprotocols.Someoftheprotocolclassesconsideredmakeuseofadvanceknowledgeofwhichbranchaclientwilllikelyfollowateachbranchpoint.Weconsiderboththeuseofmeasured(overallclients)branchchoicefrequencies,andclient-speci cinformation,asmightresultfrompre-declarationofintendedclientpathsorfromclientclassi cation.

Ourresultsshowthatfairlypreciseaprioriinformationregardingclientpathselectioncandramaticallyreduceserverbandwidthrequirementsaswellastheclientdataoverheadofreceivingdatathatisneverused.Intheabsenceofsuchinformation,strategiesthatrestrictwhatdataclientswillreceiveinadvanceofknowingwhetherornotitwillbeneeded,basedonhowfaraheadthatdataisinthevideo leratherthanmoreapproximateclientpathpredictions,cangreatlyreducetheclientdataoverheadatrelativelysmallbandwidthcost.Finally,usinginsightsderivedfromtheboundswedesignnewimmediateserviceandperiodicbroadcastprotocolsfornon-linearvideo,andevaluatethebandwidthsavingsthattheyprovide.Withineachclassofprotocols,variantsaredevelopedthatassumetheextremesofeithernoaprioripathknowledge,orfullknowledge.Ingeneral,aswithourlowerbounds,preciseaprioriinformationregardingclientpathselectioncansubstantivelyreducetheserverbandwidthrequirements.

Theremainderofthepaperisorganizedasfollows.SectionIIdescribesmodelsfornon-linearmedia.Tightlowerboundsontheserverbandwidthrequiredforagiven lerequestrateandclientstart-updelay,andthecorrespondingclientdataoverheadifnoaprioriclientpathselectioninformationisavailable,arederivedinSectionIII.SectionIVderivestheserverbandwidthboundsandassociatedclientdataoverheadsforvariouspoliciesthatrestrictthedatathatclientsreceiveaheadofwhenitisneeded.SectionVpresentsnewstreammergingandperiodicbroadcastprotocols,andcomparativeperformanceresults.ConclusionsaregiveninSectionVI.

II.NON-LINEARMEDIAMODELS

A.Non-LinearMediaStructures

Thesimplestinterestingstructurefornon-linearvideoisthatofaheightonetreewithrootnodecorrespondingtoacommoninitialportion,andchildnodescorrespondingtomultiplepossibleendingportions.Ina“completepath”playbackofthevideo,theclientplaysthecommonportionplusoneoftheendingportions.Ifthedesiredvariantoftheendingportionischosensuf cientlyaheadoftheendofthecommoninitialportion(thebranchpoint),thecompletepathcanbeplayedwithoutjitter.Inthefollowing,exceptwhenstatedotherwise,itisassumedthatclientsmakenavigationdecisionssoonenoughtoavoidjitter,butsuf cientlyclosetotherespectivebranchpointthatthegapcanbeneglectedinouranalysis.

Amoregeneralstructureisanarbitrarytree,whereeachnodecorrespondstoaportionofthevideo,andchildnodescorrespondtovariantsubsequentportions.Acompletepathplaybackwouldconsistofthecommonrootportion,plusallotherportionsonapathuptoandincludingaleafnode.Thisstructurecanbefurthergeneralizedtoadirectedacyclic

graph(i.e.,pathscanconvergeatsharedportions),orageneralgraphstructure.Inthelattercase,thenotionofa“completepath”playbackmayhavenomeaning;clientssimplystartplaybackatsomeclient-selectedvideoportionandthegraphlinksdeterminethepossiblesubsequentportions.

TheboundsinSectionsIIIandIVaredevelopedfortreestructures,althoughtheanalysiscanbegeneralized.TheimmediateserviceprotocolsdevelopedinSectionV.Aareapplicabletonon-linearmediahavingageneralgraphstructure,whileourperiodicbroadcastprotocolsinSectionV.Bareapplicabletodirectedacyclicgraphsinwhichthepathlengthstoanyvideoportionwithmultipleparentsareidentical,andtogeneraltreestructures.Forclarity,however,wepresentnumericalresultsonlyforbalancedbinarytreesinwhichallvideoportionshaveidenticalplaybacktime,andassumingthateachclientrequestisforacompletepathplayback.

Weassumeconstantbitratevideo.Generalizationsforvari-ablebitratevideocanbedevelopedusingsimilarapproachesasforlinearmedia[13],[14],[18].B.ClientBranchSelections

Akeyissueconcernstherelativefrequencieswithwhichclientsselectamongalternativeportionsofthevideoatbranchpoints.Inthecontextofbalancedbinarytreestructures,wehaveexploredseveralalternativepopularitymodels.ThemodelforwhichnumericalresultswillbepresentedassignsselectionprobabilitiestoleavesaccordingtoaZipfdistribu-tion,asfollows.First,theleafthatwillbethemostpopularischosenrandomly,andassignedthecorrespondingprobability.Then,outoftheremainingleaves,asecondmostpopularischosenrandomly,andsoon.Oncealloftheleaveshavebeengivenselectionprobabilities,selectionprobabilitiesforallinteriorvideoportionscanbecomputedbyworkingupfromtheleaves.

OthermodelsthatwereconsideredincludeamodelinwhichtheleavesareassignedZipf-distributedselectionprobabilitiesinorder,withtheleftmostleafthemostpopularandtherightmosttheleastpopular,andamodelinwhichtheselectionprobabilitiesateachbranchpointareZipf-distributed(specif-ically,forabranchpointwithtwobranches,onebranchisselectedwithprobability2/3,andtheotherwithprobability1/3).Althoughtheseothermodelswouldappeartodiffersigni cantlyfromthechosenmodel(inparticular,theygivemoreskewedselectionprobabilitiesatthebranchpointsneartherootofthetreeandlessskewedprobabilitiesatthoseneartheleaves),theywerefoundtoyieldverysimilarresults.C.AnExample

Fig.1showsasamplenon-linearvideo lestructure.Eachportionofthevideoisdenotedbyalinesegment,withbranchpointsdenotedbysolidblackcircles.Asatreestructurewithnodesrepresentingportionsofthevideo,thestructureinFig.1correspondstoabalancedbinarytreeofheight3.Inthe gureeachvideoportionislabelledbyitsselectionprobability,ascomputedbychoosingleafselectionprobabilitiesaccordingtoaZipfdistribution,andthenworkingupthetree.Alsoshown

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email