MIT > LCS > PDOS Home > 

Publications > 

Abstracts > Vivaldi

Projects
People
Software

By subject
By date

Vivaldi: A Decentralized Network Coordinate System

Frank Dabek, Russ Cox, Frans Kaahoek, Robert Morris

Abstract

Large-scale Internet applications can benefit from an ability to predict round-trip times to other hosts without having to contact them first. Explicit measurements are often unattractive because the cost of measurement can outweigh the benefits of exploiting proximity information. Vivaldi is a simple, light-weight algorithm that assigns synthetic coordinates to hosts such that the distance between the coordinates of two hosts accurately predicts the communication latency between the hosts. Vivaldi is fully distributed, requiring no fixed network infrastructure and no distinguished hosts. It is also efficient: a new host can compute good coordinates for itself after collecting latency information from only a few other hosts. Because it requires little communication, Vivaldi can piggy-back on the communication patterns of the application using it and scale to a large number of hosts. An evaluation of Vivaldi using a simulated network whose latencies are based on measurements among 1740 Internet hosts shows that a 2-dimensional Euclidean model with height vectors embeds these hosts with low error (the median relative error in round-trip time prediction is 11 percent).

This paper is posted as corrected on August 28, 2004. The original version of the paper incorrectly described how often nodes measure the RTT to another node. Nodes keep one RTT probe RPC outstanding (instead of sending one probe per second)

In the Proceedings of SIGCOMM 2004, Portland, OR, Aug, 2004 (BibTeX entry)

Paper text: PDF, PS, gzipped PS