Our work is inspired by prior work that treats Internet bandwidth as an approximate tree metric space. This paper presents a decentralized, accurate, and efficient system that predicts pairwise bandwidth between hosts. We describe an algorithm to construct a distributed tree that embeds bandwidth measurements. We then prove the correctness of the bandwidth prediction algorithm when driven by precise (ideal world) measurements. Finally, we describe three novel heuristics that achieve high accuracy for predicting bandwidth even with imprecise input data. Simulation experiments with a real-world dataset confirm that our approach shows high accuracy with little overhead, and balances measurement workload across all system hosts.

@inProceedings{infocom11,
	title = "Decentralized, Accurate, and Low-Cost Network Bandwidth Prediction",
	author = "Sukhyun Song and Peter J. Keleher and Bobby Bhattacharjee and Alan Sussman",
	booktitle = {The 30th IEEE International Conference on Computer Communications (IEEE INFOCOM 2011)},
	month = {April},
	year = {2011},
}