A Unified Network Coordinate System for Bandwidth and Latency - Malkhi, Dahlia; Abraham, Ittai; Balakrishnan, Mahesh; Ramasubramanian, Rama (2008)
Network coordinate systems, such as GNP and Vivaldi, provide virtual positions for networked hosts, which enable the hosts to connect to nearby peers, find the closest server, or organize themselves in a topologically-aware manner. Current network coordinate systems, however, only use latency to compute the positions, leaving out an important network metric—namely bandwidth. In this paper, we present a unified approach that provides virtual positions based on both bandwidth and latency. The key intuition is that network latency and bandwidth are approximate tree metrics, that is, a set of distances that can be embedded in a tree. We first argue based on intuition and analysis of three real-world datasets why bandwidth and latency can be represented as tree metrics. Then, we present Sequoia, an accurate and light-weight system that provides virtual network positions by embedding bandwidth or latency on trees; the network positions computed by Sequoia are as easy to use as a set of coordinates. Finally, we present an evaluation based on the three datasets showing that: 1) Sequoia represents latency as accurately as Vivaldi in addition to being the first ”coordinate” system for bandwidth; 2) it enables selection of the closest and the most-provisioned (highest bandwidth) server with low error and overhead; and 3) it computes topologically-aware trees, which can be used to organize a networked system efficiently.