Coordinate-Based Routing for Overlay Networks

Overlay networks are widely used as a way to introduce novel Internet services and to improve the reliability and performance of today´s Internet. Traditionally, overlay networks perform routing by mimicking the underlying IP routing protocols, which does not scale well with the system size. In this paper, we propose a fundamentally new approach to overlay routing that is based on network coordinates. Our evaluation shows that this approach is scalable to a large number of overlay nodes with a message complexity of O(N) while providing routing decisions that are close to optimal in terms of error resilience and path delay.