distances in Euclidean space

for embedding network

Big-BangSimulationforembeddingnetwork

distancesinEuclideanspace

YuvalShavitt

TomerTankel

Dept.ofElectricalEngineering,Tel-AvivUniversity,Israel

Email:{shavitt,tankel}@eng.tau.ac.il

Abstract—EmbeddingofagraphmetricinEuclideanspaceef cientlyandaccuratelyisanimportantproblemingeneralwithapplicationsintopologyaggregation,closestmirrorselection,andapplicationlevelrouting.WeproposeanewgraphembeddingschemecalledBig-BangSimulation(BBS),whichsimulatesanexplosionofparticlesunderforce eldderivedfromembeddingerror.BBSisshowntobesigni cantlymoreaccurate,comparedtoallotherembeddingmethodsincludingGNP.WereportanextensivesimulationstudyofBBScomparedwithseveralknownembeddingschemeandshowitsadvantagefordistanceestimation(asintheIDMapsproject),mirrorselectionandtopologyaggregation.

I.INTRODUCTION

Knowledgeofthedistancesbetweenallpairsofagroupofnodescanimprovetheperformanceofmanypracticalnetworkingproblems,suchasroutingthroughasubnetworkandselectingtheclosestmirrorserver.However,measuringandtoagreaterextenddisseminationofthisinformationbecomesimpracticalevenforafewtensofnodes,sincethenumberofnodepairsisquadraticinthenumberofnodes.Thus,researcherssoughtwaystoreducetheallpairdistancerepresentationwhilepreserv-ingthedistanceinthereducedrepresentationascloseaspossibletotheoriginalones.Nextweshortlydescribetwoexamplenetworkingproblems,whereallpairdistanceinformationisrequired.

Routingthroughasubnetwork.WhenroutingthroughanATMsub-network,thedistancesbetweenallpairsofbordernodes,i.e.,nodesthatareconnectingthesub-networktoothersub-network,areusedtocomputetheshortest(orcheapest)paththroughthecloud[1].Forthisend,eachnetworkadvertisesitsdistancematrixinacompressedmanner,anditisrecommendedthatthematrixrepresentationissmallerthan3b,wherebisthenumberofbordernodes[1].Thebestcompressiontechniquethatwassuggestedinthepast[2]willbepresentedlater.

1This

researchwassupportedbyagrantfromtheUnitedStates-IsraelBinationalScienceFoundation(BSF),Jerusalem,Israel.

Selectingtheclosestmirror.Recently,therewasalargeinterestinusingdistancemapsoftheInternettoaidintaskssuchasclosestmirrorselectionandapplicationlayermulticast[3],[4],[5],[6].IntheIDMapsprojectitwasidenti edthatthenumberofpossiblenodeswhichrepresentthedistancemapgranularityisinthethousandswhichmakesaccuratedistancedisseminationimpractical.Duetothepracticalityofthemeasurementprocessandtoreducetherepresentation,IDMapssuggeststouseasmallernumberofmeasurementpoints,Tracers,thatmeasuredistancesamongthemselvesandthenusethemasareferencedistancemaptotheothernetworkregions.ArelativelynewapproachtorepresentanetworkdistancematrixistomapnetworknodesintopointsinarealEuclideanspace.SuchamappingisdesignedtopreservethedistancebetweenanypairofnetworknodesclosetotheEuclideandistancebetweentheirgeometricimages.Suchamappingiscalledanembeddingandideallygraphedgelengthsareexactlyembeddedinthegeometricedges.However,itcanbeeasilyshownthatanexactembeddingisnotalwayspossible,e.g.,incaseofatree,andin-fact,inmostcasesembeddingintroducessomedistortion.Ina’good’embedding,theaverageandmaximumdistancedistortionoverallpairsofnodesarerelativelylow.Thedistancedistortionisde nedforeachpairasthemaximumoftheratiobetweentheoriginalandEuclideandistanceanditsinverse.

Outsidethenetworkingcommunityembeddinghasbeenusedforquitealongtimeinmanydiverseresearchareas.MultiDimensionalScaling(MDS)iswidelyusedinareasofstatisticsandvision.ThesimplicityandlowcomplexityofclassicalmetricMDS[7]makesitappeal-ingintheseareas.Recentlycomputergraphicsresearches[8]suggestedtouseMDSformapping attexturesovercurvedsurfaceswithminimumdistortion.Embeddingisusedextensivelyinbio-informatics,andspeci callyforclassi cationofproteinsequencesintosimilarityfamilies[9].

TheoreticalboundsonthemaximalpairdistortionandthedimensionofthetargetspacewerederivedbyLinial

Word文档免费下载Word文档免费下载:distances in Euclidean space (共11页,当前第1页)

distances in Euclidean space相关文档

最新文档

返回顶部