research-article

Shortcuts in a virtual world

Authors:

Moritz Steiner,

Ernst W. BiersackAuthors Info & Claims

CoNEXT '06: Proceedings of the 2006 ACM CoNEXT conference

Article No.: 17, Pages 1 - 9

https://doi.org/10.1145/1368436.1368460

Published: 04 December 2006 Publication History

Abstract

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.

References

[1]

K. Calvert, M. Doar, and E. W. Zegura. Modeling internet topology. IEEE Communications Magazine, 35(6):160--163, June 1997.

Digital Library

[2]

K. Calvert, J. Eagan, S. Merugu, A. Namjoshi, J. Stasko, and E. Zegura. Extending and enhancing gt-itm. In MoMeTools '03: Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, pages 23--27, 2003.

Digital Library

[3]

M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron. Topology-aware routing in structured peer-to-peer overlay networks. Technical Report MSR-TR-2002-82, Microsoft Research, One Microsoft Way, Redmond, WA 98052, 2002.

[4]

R. Cox, F. Dabek, F. Kaashoek, J. Li, and R. Morris. Vivaldi: A decentralized network coordinate system. In Proceedings ACM SIGCOMM 2004, Aug.

Digital Library

[5]

B. Delaunay. Sur la sphère vide. A la mémoire de Georges Voronoi. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk, 7:793--800, 1934.

[6]

M. Gutowski. Lévy flights as an underlying mechanism for global optimization algorithms. ArXiv Mathematical Physics e-prints, June 2001.

[7]

K. Hui, J. Lui, and D. Yau. Small world overlay p2p networks. In Quality of Service, 2004. IWQOS 2004. Twelfth IEEE International Workshop on, pages 201--210, 2004.

[8]

J. Kleinberg. The small-world phenomenon: an algorithm perspective. In STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 163--170, 2000.

Digital Library

[9]

P. Lévy. Théorie de l'Addition des Variables Aléatoires. Gauthier-Villiers, Paris, 1937.

[10]

M. Li, W.-C. Lee, and A. Sivasubramaniam. Semantic small world: An overlay network for peer-to-peer search. In Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP'04), pages 228--238, 2004.

Digital Library

[11]

J. Liebeherr, M. Nahas, and S. Weisheng. Application-layer multicasting with delaunay triangulation overlays. IEEE Journal on Selected Areas in Communications, 20(8):1472--1488, Oct. 2003.

Digital Library

[12]

Y. Liu, Z. Zhuang, L. Xiao, and L. M. Ni. A distributed approach to solving overlay mismatching problem. In Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), pages 132--139. IEEE Computer Society, 2004.

Digital Library

[13]

S. Merugu, S. Srinivasan, and E. Zegura. Adding structure to unstructured peer-to-peer networks: The role of overlay topology. In Proceedings of NGC 2003, volume 2816, pages 83--94, Sept. 2003.

[14]

S. Milgram. The small world problem. Psychology Today, 2:60--67, may 1967.

[15]

S. Ratnasamy, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM, 2001.

Digital Library

[16]

A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale Peer-to-peer systems. In R. Guerraoui, editor, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), LNCS, pages 329--350, Heidelberg, Germany, November 2001. Springer.

Digital Library

[17]

M. Steiner. Structure and algorithms for the collaboration between peers and their application in solipsis. Master's thesis, University of Mannheim and Institut Eurécom, Sophia-Antipolis, France, Mar. 2005.

[18]

M. Steiner and E. W. Biersack. A fully distributed peer to peer structure based on 3d delaunay triangulation. In Proceedings of Algotel - Septièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, pages 93--96, May 2005.

[19]

I. Stoica, R. Morris, D. Karger, M. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. ACM SIGCOMM, 2001.

Digital Library

[20]

D. Watts and S. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393(6684):409--410, 1998.

[21]

D. J. Watts. Small worlds: the dynamics of networks between order and randomness. Princeton University Press, Princeton, NJ, USA, 1999.

Digital Library

[22]

M. Yvinec and J.-D. Boissonnat. Algorithmic Geometry. Cambridge University Press, 1998.

Digital Library

[23]

B. Y. Zhao, J. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, Computer Science Division, University of California, Berkeley, Apr 2001.

Digital Library

Cited By

Ghaffari MHariri BShirmohammadi SAhmed D(2015)A Dynamic Networking Substrate for Distributed MMOGsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2014.23305203:2(289-302)Online publication date: Jun-2015
https://doi.org/10.1109/TETC.2014.2330520
Gilmore JEngelbrecht H(2012)A Survey of State Persistency in Peer-to-Peer Massively Multiplayer Online GamesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.21023:5(818-834)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.210
Hu SChen K(2011)VSOProceedings of the 2011 IEEE Fifth International Conference on Self-Adaptive and Self-Organizing Systems10.1109/SASO.2011.13(21-30)Online publication date: 3-Oct-2011
https://dl.acm.org/doi/10.1109/SASO.2011.13
Show More Cited By

Index Terms

Shortcuts in a virtual world
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks
  1. Network architectures
  2. Network properties
    1. Network structure

Recommendations

Improving peer connectivity in wide-area overlays of virtual workstations

Self-configuring virtual networks rely on structured P2P routing to provide seamless connectivity among nodes through overlay routing of virtual IP packets, support decentralized hole-punching to establish bi-directional communication links among nodes ...
Can ISPS and P2P users cooperate for improved performance?

Peer-to-peer (P2P) systems, which are realized as overlays on top of the underlying Internet routing architecture, contribute a significant portion of today's Internet traffic. While the P2P users are a good source of revenue for the Internet Service ...
The FastTrack overlay: A measurement study
Overlay distribution structures and their applications

Both in terms of number of participating users and in traffic volume, FastTrack is one of the most important applications in the Internet today. Nevertheless, because FastTrack is proprietary and uses encryption, little is understood about FastTrack's ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '06: Proceedings of the 2006 ACM CoNEXT conference

December 2006

318 pages

ISBN:1595934561

DOI:10.1145/1368436

Program Chairs:
C. Diot
Thomson, France
,
M. Ammar
Georgia Tech

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Fundacao para a Ciencia e Tecnologia
Associacao de Turismo de Lisboa
SIGCOMM: ACM Special Interest Group on Data Communication
Microsoft: Microsoft
Intel: Intel
ISCTE
Thomson
CISCO
Camara Municipal de Lisboa
E-Next

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 December 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Freance Telecom

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
113
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghaffari MHariri BShirmohammadi SAhmed D(2015)A Dynamic Networking Substrate for Distributed MMOGsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2014.23305203:2(289-302)Online publication date: Jun-2015
https://doi.org/10.1109/TETC.2014.2330520
Gilmore JEngelbrecht H(2012)A Survey of State Persistency in Peer-to-Peer Massively Multiplayer Online GamesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.21023:5(818-834)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.210
Hu SChen K(2011)VSOProceedings of the 2011 IEEE Fifth International Conference on Self-Adaptive and Self-Organizing Systems10.1109/SASO.2011.13(21-30)Online publication date: 3-Oct-2011
https://dl.acm.org/doi/10.1109/SASO.2011.13
Zhuge HSun X(2008)A Virtual Ring Method for Building Small-World Structured P2P OverlaysIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2008.10220:12(1712-1725)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1109/TKDE.2008.102

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents