Network Coordinates

Network Coordinates

Overview SBON | Hourglass | PL Service |

Stable and Accurate Network Coordinates

Authors: Jonathan Ledlie, Peter Pietzuch, and Margo Seltzer
Contact: {jonathan,prp,margo}

Synthetic network coordinates scale to estimate latencies between many physical hosts. As such, researchers are starting to include them in the set of networking tools used in real deployments. While there are several algorithms for producing coordinates, none currently accounts for the fact that, instead of perceiving a single latency for each link, nodes see a stream of distinct observations that may vary by as much as three orders-of-magnitude. With limited means to discern appropriate link latencies, coordinate systems are prone to high error and instability in live deployments. In addition, triangle violations and other dynamics can lead to coordinate oscillations, making it difficult for applications to know when their coordinates have truly changed. Because coordinate systems can provide sufficiently accurate, low cost answers to several types of common queries in simulation, solving these problems is an important step in furthering their practical use.

We introduce latency filters, that turn streams of latency observations into a single approximation, and update filters, that summarize underlying coordinate change and squelch false application updates. We show how a compact, non-linear low pass filter can ascertain a clear underlying signal from each link. These latency filters primarily improve accuracy. Then we evaluate a set of change-detection heuristics that allow coordinates to evolve at the system-level and initiate an application-level update only after a coordinate has undergone a significant change. These update filters boost coordinate stability without diminishing accuracy. Both filters combined to improve network coordinate accuracy by 54 percent and coordinate stability by 96 percent when run on a real large-scale network. 

  • Paper (currently under submission)
  • Source Code and traces available on request
  • WORLDS 2005 talkVideos of Latency and Update filters on PlanetLab.
@techreport{ ledlie05coordinates,
        author = "Jonathan Ledlie and Margo Seltzer",
        title = "Stable and Accurate Network Coordinates",
        institution = "Harvard University",
        type = "Research Report",
        year = "2005",
        month = "July"
	number = "TR-17-05"