Meridian: A Lightweight Network Location Service without Virtual Coordinates

We introduce a lightweight, scalable and accurate framework for performing node selection based on network location. The framework, called Meridian, consists of an overlay network structured around multi-resolution rings, gossip protocols for ring maintenance, and query routing with direct measurements to satisfy user specified latency constraints. We show how this framework can be used to address three commonly encountered problems, namely, closest node discovery, central leader election, and locating nodes that satisfy target latency constraints in large-scale distributed systems without having to compute absolute coordinates. We also present the Meridian Query Language, a domain specific language for users to construct custom node selection queries based on their specific network location requirements. To facilitate adoption of Meridian, we have deployed a service called ClosestNode.com that provides a DNS to Meridian gateway for oblivious clients to initiate Meridian lookups. We show analytically that the framework is scalable with logarithmic convergence when Internet latencies are modeled as a growth-constrained metric, a low-dimensional Euclidean metric, or a metric of low doubling dimension. Large scale simulations, based on latency measurements from 6.25 million node-pairs as well as an implementation deployed on PlanetLab show that the framework is accurate and effective.