NDLI: Hyperbolic embedding of internet graph for distance estimation and overlay construction

Please wait, while we are loading the content...

IEEE/ACM Transactions on Networking (TON) : Volume 24

IEEE/ACM Transactions on Networking (TON) : Volume 23

IEEE/ACM Transactions on Networking (TON) : Volume 22

IEEE/ACM Transactions on Networking (TON) : Volume 21

IEEE/ACM Transactions on Networking (TON) : Volume 20

IEEE/ACM Transactions on Networking (TON) : Volume 19

IEEE/ACM Transactions on Networking (TON) : Volume 18

IEEE/ACM Transactions on Networking (TON) : Volume 17

IEEE/ACM Transactions on Networking (TON) : Volume 16

Issue 6, December 2008

Issue 5, October 2008

Issue 4, August 2008

Issue 3, June 2008

Issue 2, April 2008

Issue 1, February 2008

Race conditions in coexisting overlay networks

Probabilistic packet marking for large-scale IP traceback

Hyperbolic embedding of internet graph for distance estimation and overlay construction

Trajectory sampling with unreliable reporting

An algorithmic approach to geographic routing in ad hoc and sensor networks

Efficient routing in intermittently connected mobile networks: the single-copy case

Efficient routing in intermittently connected mobile networks: the multiple-copy case

On the performance benefits of multihoming route control

Two techniques for fast computation of constrained shortest paths

BRA: a bidirectional routing abstraction for asymmetric mobile ad hoc networks

A stochastic foundation of available bandwidth estimation: multi-hop analysis

Improved quasi-path restoration in mesh networks

Dual-link failure resiliency through backup link mutual exclusion

Rate and delay guarantees provided by Clos packet switches with load balancing

Performance of a speculative transmission scheme for scheduling-latency reduction

A service-curve framework for packet scheduling with switch configuration delays

Matching from the first iteration: an iterative switching algorithm for an input queued switch

Simple summaries for hashing with choices

Measurement and analysis of LDAP performance

Comments on "Dynamic routing of restorable bandwidth-guaranteed tunnels using aggregated network resource usage information"

IEEE/ACM Transactions on Networking (TON) : Volume 15

IEEE/ACM Transactions on Networking (TON) : Volume 14

IEEE/ACM Transactions on Networking (TON) : Volume 13

IEEE/ACM Transactions on Networking (TON) : Volume 12

IEEE/ACM Transactions on Networking (TON) : Volume 11

IEEE/ACM Transactions on Networking (TON) : Volume 10

IEEE/ACM Transactions on Networking (TON) : Volume 9

IEEE/ACM Transactions on Networking (TON) : Volume 8

IEEE/ACM Transactions on Networking (TON) : Volume 7

IEEE/ACM Transactions on Networking (TON) : Volume 6

IEEE/ACM Transactions on Networking (TON) : Volume 5

IEEE/ACM Transactions on Networking (TON) : Volume 4

IEEE/ACM Transactions on Networking (TON) : Volume 3

IEEE/ACM Transactions on Networking (TON) : Volume 2

IEEE/ACM Transactions on Networking (TON) : Volume 1

Hyperbolic embedding of internet graph for distance estimation and overlay construction

Content Provider	ACM Digital Library
Author	Shavitt, Yuval Tankel, Tomer
Abstract	Estimating distances in the Internet has been studied in the recent years due to its ability to improve the performance of many applications, e.g., in the peer-to-peer realm. One scalable approach to estimate distances between nodes is to embed the nodes in some $\textit{d}$ dimensional geometric space and to use the pair distances in this space as the estimate for the real distances. Several algorithms were suggested in the past to do this in low dimensional Euclidean spaces. It was noted in recent years that the Internet structure has a highly connected core and long stretched tendrils, and that most of the routing paths between nodes in the tendrils pass through the core. Therefore, we suggest in this work, to embed the Internet distance metric in a hyperbolic space where routes are bent toward the center. We found that if the curvature, that defines the extend of the bending, is selected in the adequate range, the accuracy of Internet distance embedding can be improved. We demonstrate the strength of our hyperbolic embedding with two applications: selecting the closest server and building an application level multicast tree. For the latter, we present a distributed algorithm for building geometric multicast trees that achieve good trade-offs between delay (stretch) and load (stress). We also present a new efficient centralized embedding algorithm that enables the accurate embedding of short distances, something that have never been done before.
Starting Page	25
Ending Page	36
Page Count	12
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2007.899021
Volume Number	16
Issue Number	1
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-02-01
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in