Shortcuts in a virtual world

We consider the case of a virtual world of peers that are organized in an overlay built by Delaunay Triangulation. Application layer routing is used to determine the path taken in the overlay between two peers. Application layer routing incurs a major delay penalty since it ignores the characteristics of the physical network topology. We show how to augment a Delaunay based overlay by a small and bounded number of additional links called shortcuts. A peer chooses its shortcuts among the nodes that are physically close to him in the underlay while covering at the same time uniformly the overlay space. Shortcuts improve the average hopcount and the average delay for a path between two peers from O(N1/d) to O(log(N)), where N is the total number of peers in the overlay and d the dimension of the overlay. The algorithm to manage shortcuts is fully distributed and requires only local knowledge.