Towards realizing the performance and availability benefits of a global overlay network

Abstract. Prior analyses of the benefits of routing overlays are based on platforms consisting of nodes located primarily in North America, on the academic Internet, and at the edge of the network. This paper is the first global study of the benefits of overlays on the commercial Internet in terms of round trip latencies and availability, using measurements from diverse ISPs distributed across all tiers, and over 1100 locations (77 countries, 630 cities and 6 continents). Our study shows that while overlays provide some improvements in North America, their benefits are especially significant for paths with Asian endpoints. For example, overlays reduce latencies of a quarter of the paths in Asia by over 50%, while the latencies of over half the paths globally are improved by at least 10%. Furthermore, overlays increase availability in North America and Europe by up to 0.5%, whereas improvements in Asia are significantly larger at 3.25%. Our study also focuses on practical considerations in constructing overlay routes. We show that a simple algorithm that randomly chooses a small number of alternate redundant paths achieves an availability of over 99.5%. We also propose and evaluate a simple predictive scheme that achieves almost optimal latency using only 2-3 paths. Finally, we demonstrate that this is achievable with surprisingly persistent routing choices.