Coordinate-Based Routing for Overlay Networks

Traditionally overlay networks perform routing in a way that minimzes the underlying IP routing protocols. In this paper we propose a new approach to overlay routing that is based on network coordinates. The core idea is that routing is peformed entirely within the coordinate space of a network coordinate system. The main benefits of this approach are that it 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 path delay and error resilience. Furthermore, coordinate based routing allows the realization of many different overlay routing schemes and this flexibility makes it suitable for the implementation of a large variety of overlay networks over a single infrastructure.