资源描述:
《A Comparison of Network Coding and Tree Packing网络编码的比较》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、AComparisonofNetworkCodingandTreePackingYunnanWu∗,PhilipA.Chou†,andKamalJain†∗Dept.ofElectricalEngineering,PrincetonUniversity,Princeton,NJ08544USA†MicrosoftResearch,OneMicrosoftWay,Redmond,WA98052-6399USAyunnanwu@princeton.edu,pachou@microsoft.com,kamalj@microsoft.com1IntroductionInthispape
2、r,weconsidertheproblemofinformationmulticast,namelytransmittingcommoninformationfromasenderstoasetofreceiversT,inacommunicationnet-work.Conventionally,inacommunicationnetworksuchastheInternet,thisisdonebydistributinginformationoveramulticastdistributiontree.Thenodesofsuchatreearerequiredonly
3、toreplicateandforward,i.e.,route,informationreceived.Recently,Ahlswedeetal.[1]demonstratedthatitisingeneralsuboptimaltorestrictthenetworknodestoperformonlyrouting.Theyshowthatthemulticastcapacity,whichisdefinedasthemaximumratethatasendercancommunicatecommoninformationtoasetofre-ceivers,isgive
4、nbytheminimumC=mint∈TCtofmax-flowsCt=maxflow(s,t)betweenthesenderandeachreceiver.Moreover,theyshowedthatwhilethemulticastcapacitycannotbeachievedingeneralbyrouting,itcanbeachievedbynetworkcoding.Networkcodingreferstoaschemewherecodingisdoneattheinteriornodesinthenetwork,notonlyatthesenderandre
5、ceivers.Li,Yeung,andCai[2]showedthatitissufficientfortheencodingfunctionsattheinteriornodestobelinear.KoetterandM´edard[3]gaveanalgebraiccharacterizationoflinearencodingschemesandprovedexistenceoflineartime-invariantcodesachievingthemulticastcapacity.Jaggi,Sanders,etal.[4][5][6]showedforacycli
6、cnetworkshowtofindtheencodinganddecodingcoefficientsinpolynomialtime.Chou,Wu,andJain[7][8]proposedadistributedschemeforpracticalnetworkcodinginrealpacketnetworksachievingthroughputclosetocapacitywithlowdelaythatisrobusttorandompacketlossanddelayaswellasrobusttoanychangestonetworktopologyorcapac
7、ity.Inthispaper,wecomparenetworkcodingsolutionsandroutingsolutionsfortheproblemofinformationmulticast,andweinvestigatethepotentialadvantagesofnetworkcodingoverrouting.Tomaximizetheperformanceoftheroutingsolutions,weinvestigatetheuseofmultiplemultic