资源描述：
《spanners and message distribution in networks》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SpannersandMessageDistributioninNetworksArthurM.Farley,AndrzejProskurowskiComputerandInformationScienceDepartmentandKurtWindischAdvancedNetworkTechnologyCenter,ComputingCenterUniversityofOregonEugene,OR,97403Weinvestigatetheapplicabilityofk-spannersassharedvirtualtopologiesf
2、orintradomainbroad-castandmulticastontheInternet.Alight-weightk-spannerisaspanningsubgraphofanetworkthathasbothrelativelysmalltotaledgeweightandsmallmultiplicativepenalty(atmostk)onallpoint-to-pointdistances.Wede nebroadcastingandmulticastingprotocolsbasedon
oodingofaspanner
3、,followedbypruningthedistributiontreewithinthespannerandthenjoininginthenetworktoformsender-basedtrees,ifdesired.Weevaluatek-spanners(for2k7)intermsofnumberofedges,diameter,andaveragedistanceonsetsofrandomlygeneratedgraphshavingpropertiessimilartointradomainnetworks.Wecomp
4、arevaluesofthesemetricsforspannerswiththoseforgivengraphsandsingle-sourceminimum-distancespanningtrees.Resultsshowthata3-or4-spannercouldserveasagoodvirtualtopologyformessagedistribution,havingfeweredgesthanthefullnetworkyetloweraveragedistanceanddiameterthanasingle-source,m
5、inimum-distancespanningtree.CategoriesandSubjectDescriptors:C.2.1[Computer-CommunicationNetworks]:NetworkarchitectureanddesignGeneralTerms:PerformanceAdditionalKeyWordsandPhrases:Multicastprotocol,k-spanner,distributiontree1.INTRODUCTIONIthasbecomeincreasinglyapparentthatthe
6、reisaneedforecientwaystodis-tributemessagesfromsinglesenderstomorethanonereceiverwithincommunica-tionnetworks.Sendingadi erentcopyofthemessagetoeachreceiver(i.e.,mailinglists)canworke ectivelyforapplicationsinvolvinginfrequent,shorttransmissions.However,applicationssuchasre
7、al-timevideodistributionoron-linegamingandconferencing,eachrequiringfrequentdistributionofrelativelylongmessages,haveresultedintheneedformoreecientbroadcastingandmulticastingalgorithmsandassociatedprotocols.Inthispaper,weinvestigatetheapplicabilityofgraphspannersasvirtualto
8、polo-giesforbroadcastingandmulticastingincommunicationnetworks.Firstwede ne
