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

相关文档
...embedding network distances in Euclidean space_...
12, NO. 6, DECEMBER 2004 993 Big-Bang Simulation for Embedding Network Distances in Euclidean Space Yuval Shavitt, Senior Member, IEEE, and Tomer Tankel...
POPULAR DISTANCES IN 3-SPACE
POPULAR DISTANCES IN 3-SPACE Abstract. Let m(n) denote the smallest integer m with the property that any set of n points in Euclidean 3-space has...
Chains on a Grating in Euclidean Space 1
On distinct distances in... 暂无评价 15页 免费 On the minimal distance ...Next we state two propositions: CHAINS ON A GRATING IN EUCLIDEAN SPACE 6 ...
Extreme distances in multicolored point sets
Extreme distances in multicolored point sets Given a set of n colored points in some d-dimensional Euclidean space, a bichromatic closest (resp. ...
...distance between sets in Euclidean space_免费下...
On distinct distances in... 暂无评价 15页 免费 On the Smallest Minimal ...of Bia?ystok On the Minimal Distance Between Sets in Euclidean Space1 ...
测绘专业英语翻译
(距离不一定指的是直线的, 尤其是在地球曲面上的距离) this In subject we will deal with distances in Euclidean space, which we can consider a straight ...
Combining Euclidean and Mahalanobis Distances for R...
Combining Euclidean and Mahalanobis Distances for Recognition We consider recognition by Gaussian models, noise sensitivity from using sample covariances to ...
...Reconstruction in Euclidean Spaces_免费下载
暂无评价 13页 免费 distances in Euclidean s... 暂无评价 11页 免费...methods to reconstruct large classes of compact subsets of Euclidean space Rd...
3距离测量
尤其是在地球曲面上的距离) In this subject we will deal with distances in Euclidean space, which we can consider a straight line from one point or ...
测绘工程专业英语翻译第三章
Distances are not necessarily linear, especially if they occur on the spherical earth. In this subject we will deal with distances in Euclidean space, ...
相关主题
热门文档