skip to main content
research-article

A Diophantine model of routes in structured P2P overlays

Published: 01 March 2008 Publication History

Abstract

An important problem in any structured Peer-to-Peer (P2P) overlay is what routes are available between peers. Understanding the structure of routes helps to solve challenging problems related to routing performance, security, and scalability. In this paper, we propose a theoretical approach for describing routes. It is based on a recent result in the linear Diophantine analysis and introduces a novel Diophantine model of P2P routes. Such a route aggregates several P2P paths that packets follow. A commutative context-free grammar describes the forwarding behavior of P2P nodes. Derivations in the grammar correspond to P2P routes. Initial and final strings of a derivation define packet sources and destinations, respectively. Based on that we construct a linear Diophantine equation system, where any solution counts forwarding actions in a route representing certain integral properties. Therefore, P2P paths and their composition into routes are described by a linear Diophantine systems; its solutions (basis) define a structure of P2P paths.

References

[1]
S. Androutsellis-Theotokis and D. Spinellis. A survey of peer-to-peer content distribution technologies. ACM Computing Surveys, 36(4):335--371, Dec. 2004.
[2]
M. S. Artigas, P. G. Lopez, and A. F. G. Skarmeta. A novel methodology for constructing secure multipath overlays. IEEE Internet Computing, 9(6):50--57, 2005.
[3]
D. P. Bertsekas. Network Optimization: Continuous and Discrete Models. Athena Scientific, 1998.
[4]
Y. A. Bogoyavlenskiy and D. G. Korzun. On solutions of a system of linear Diophantine equations associated with a context-free grammar. Transactions of Petrozavodsk State University on Applied Mathematics and Computer Science, 6:79--94, 1998. (in Russian).
[5]
M. Castro, M. Costa, and A. Rowstron. Performance and dependability of structured peer-to-peer overlays. Technical Report MSR-TR-2003-94, Microsoft Research, Dec. 2003.
[6]
R. Cox, A. Muthitacharoen, and R. T. Morris. Serving dns using a peer-to-peer lookup service. In Proc. of the 1st International Workshop on Peer-to-Peer Systems (IPTPS '02). Springer-Verlag, Mar. 2002.
[7]
J. Esparza. Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae, 30:23--41, 1997.
[8]
K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of DHT routing geometry on resilience and proximity. In Proc. of ACM SIGCOMM'03, pages 381--394, New York, NY, USA, Aug. 2003. ACM Press.
[9]
A. Gurtov, D. Korzun, and P. Nikander. Hi3: An efficient and secure networking architecture for mobile hosts. Technical Report TR-2005-2, HIIT, June 2005.
[10]
J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Technical Report TR 99-1776, Cornell Computer Science, 1999.
[11]
D. G. Korzun. On an interrelation of formal grammars and systems of linear Diophantine equations. Bulletin of young scientists, 3:50--56, 2000. (in Russian).
[12]
D. G. Korzun. Grammar-based algorithms for solving certain classes of nonnegative linear Diophantine systems. In Proc. of the annual Finnish Data Processing Week at Petrozavodsk State University. (FDPW 2000) on Advances in Methods of Modern Information Technology, volume 3, pages 52--67. Petrozavodsk State University, 2001.
[13]
D. G. Korzun. Syntactic methods in solving linear Diophantine equations. In Proc. of the annual Finnish Data Processing Week at Petrozavodsk State University (FDPW 2004) on Advances in Methods of Modern Information Technology, volume 6, pages 151--156. Petrozavodsk State University, 2005.
[14]
S. F. Lam and K. H. Chan. Computer Capacity Planning. Academic Press Inc., 1987.
[15]
D. Loguinov, A. Kumar, V. Rai, and S. Ganesh. Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience. IEEE/ACM Trans. on Networking, 13(5):1107--1120, 2005.
[16]
D. Malkhi, M. Naor, and D. Ratajczak. Viceroy: a scalable and dynamic emulation of the butterfly. In PODC '02: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pages 183--192, New York, NY, USA, 2002. ACM Press.
[17]
C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. In Proc. of the 9th Annual Symposium on Parallel Algorithms and Architectures (SPAA '97), pages 311--320, June 1997.
[18]
S. Ratnasamy, P. F. M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. of ACM SIGCOMM'01, pages 161--172, San Diego, CA, USA, Aug. 2001.
[19]
A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.
[20]
I. Stoica, D. Adkins, S. Zhuang, S. Shenker, and S. Surana. Internet indirection infrastructure. In Proc. of ACM SIGCOMM'02, pages 73--88, Pittsburgh, PA, USA, Aug. 2002.
[21]
I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for Internet applications. IEEE/ACM Trans, on Networking, 11(1):17--32, 2003.
[22]
J. Xu, A. Kumar, and X. Yu. On the fundamental tradeoffs between routing table size and network diameter in peer-to-peer networks. IEEE Journal on Selected Areas in Communications, 22:151--163, Jan. 2004.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review
ACM SIGMETRICS Performance Evaluation Review  Volume 35, Issue 4
March 2008
70 pages
ISSN:0163-5999
DOI:10.1145/1364644
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2008
Published in SIGMETRICS Volume 35, Issue 4

Check for updates

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)LDEPTH: A low diameter hierarchical P2P network architecture2016 IEEE 14th International Conference on Industrial Informatics (INDIN)10.1109/INDIN.2016.7819275(832-837)Online publication date: Jul-2016
  • (2012)Diophantine RoutingStructured Peer-to-Peer Systems10.1007/978-1-4614-5483-0_9(245-266)Online publication date: 10-Oct-2012
  • (2012)Hierarchical Neighbor MaintenanceStructured Peer-to-Peer Systems10.1007/978-1-4614-5483-0_3(47-86)Online publication date: 10-Oct-2012
  • (2010)Survey on hierarchical routing schemes in “flat” distributed hash tablesPeer-to-Peer Networking and Applications10.1007/s12083-010-0093-z4:4(346-375)Online publication date: 5-Oct-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media