Title: Internet Distance Estimation and Overlay construction 
through Embedding: From Euclidean to Hyperbolic spaces


Speaker: Tomer Tankel, Tel-Aviv University


Abstract:

Embedding of a graph metric in Geometric
space efficiently and accurately is an important problem in
general with applications in topology aggregation, closest
mirror selection, and application level routing. 
We propose a new graph embedding scheme called Big-Bang Simulation
(BBS), which simulates an explosion of particles under
force field derived from embedding error. BBS is shown
to be significantly more accurate, compared to all other
embedding methods including GNP. 

It was noted in recent years the Internet structure resembles 
a star with a highly connected core and long stretched tendrils.  
Motivated by this structure, we embed the Internet distance 
metric in a hyperbolic space. We properly select the hyperbolic
curvature, and achieveembedding accuracy better than achieved
before for the Euclidean space.  

We demonstrate the strength of our embedding with two 
applications: selecting the closest server and building 
an application level multicast tree.