| Conference |
| Type of Publication |
| Shortcuts in a virtual World |
| Title |
|
Ernst W. Biersack
|
| Authors |
| Proceedings of CoNext 2006, Lisbon, Portugal, December 2006 |
| Published in |
| 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(N^{1/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. |
| Abstract |
|
p2p
overlay network
small world
|
| Keywords |
| [PDF]
[BIB] [XML] |
| Downloads & Bib-Entries |
