article

An analytical study of a structured overlay in the presence of dynamic membership

Authors:

Supriya Krishnamurthy,

Sameh El-Ansary,

Seif HaridiAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 4

Pages 814 - 825

https://doi.org/10.1109/TNET.2007.905590

Published: 01 August 2008 Publication History

Abstract

In this paper, we present an analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a fluid model approach to describe steady-state or transient phenomena and apply it to the Chord system. For any rate of churn and stabilization rates and any system size, we accurately account for the functional form of the probability of network disconnection as well as the fraction of failed or incorrect successor and finger pointers. We show how we can use these quantities to predict both the performance and consistency of lookups under churn. All theoretical predictions match simulation results. The analysis includes both features that are generic to structured overlays deploying a ring as well as Chord-specific details and opens the door to a systematic comparative analysis of, at least, ring-based structured overlay systems under churn.

References

[1]

K. Aberer, A. Datta, and M. Hauswirth, "Efficient, self-contained handling of identity in peer-to-peer systems," IEEE Trans. Knowledge Data Eng., vol. 16, no. 7, pp. 858-869, Jul. 2004.

[2]

D. Anick, D. Mitra, and M. M. Sondhi, "Stochastic theory of data-handling systems with multiple sources," Bell Syst. Tech. J., vol. 61, pp. 1871-1894, 1982.

[3]

J. Aspnes, Z. Diamadi, and G. Shah, "Fault-tolerant routing in peer-to-peer systems," in Proc. 21st ACM Symp. Principles of Distributed Computing (PODC 2002), Monterey, CA, Jul. 2002, pp. 223-232.

[4]

E. Brockmeyer, H. L. Halstrom, and A. Jensen, The Life and Works of A. K. Erlang. Copenhagen, Denmark: Copenhagen Telephone Co., 1948.

[5]

M. Castro, M. Costa, and A. Rowstron, "Performance and dependability of structured peer-to-peer overlays," in Int. Conf. Dependable Systems and Networks (DSN 2004), Florence, Italy, 2004.

[6]

F. Clevenot and P. Nain, "A simple fluid model for the analysis of the Squirrel peer-to-peer caching system," in Proc. IEEE INFOCOM 2004, Hong Kong, Mar. 2004, pp. 95-104.

[7]

S. El-Ansary, E. Aurell, and S. Haridi, "A physics-inspired performace evaluation of a structured peer-to-peer overlay network," in Int. Conf. Parallel and Distributed Computing and Networks (PDCN 2005), Innsbruck, Austria, 2005.

[8]

S. Krishnamurthy, S. El-Ansary, E. Aurell, and S. Haridi, "A statistical theory of chord under churn," in Proc. 4th Int. Workshop on Peer-to-Peer Systems (IPTPS'05), Ithaca, NY, Feb. 2005, pp. 93-103.

[9]

S. Krishnamurthy, S. El-Ansary, E. Aurell, and S. Haridi, "Comparing maintenance strategies for overlays," in PDP 2008, Toulouse, France, Feb. 2008.

[10]

J. Li, J. Stribling, R. Morris, M. Frans Kaashoek, and T. M. Gil, "A performance versus cost framework for evaluating DHT design tradeoffs under churn," in Proc. 24th IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 225-235.

[11]

D. Liben-Nowell, H. Balakrishnan, and D. Karger, "Analysis of the evolution of peer-to-peer systems," in Proc. 21st ACM Conf. Principles of Distributed Computing (PODC 2002), Monterey, CA, Jul. 2002, pp. 233-242.

[12]

N. G. van Kampen, Stochastic Processes in Physics and Chemistry. Amsterdam, The Netherlands: North-Holland, 1981.

[13]

D. Qui and R. Srikant, "Modeling and performance analysis of BitTorrent-like peer-to-peer networks," in Proc. ACM SIGCOMM 2004, Portland, OR, Aug. 2004, pp. 367-377.

[14]

S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, "Handling churn in a DHT," in Proc. 2004 USENIX Annu. Technical Conf. (USENIX '04), Boston, MA, Jun. 2004, pp. 127-140.

[15]

I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. Frans Kaashoek, F. Dabek, and H. Balakrishnan, "Chord: A scalable peer-to-peer lookup service for Internet applications," IEEE Trans. Netw., vol. 11, no. 1, pp. 17-32, Feb. 2003.

[16]

S. Wang, D. Xuan, and W. Zhao, "On resilience of structured peer-to-peer systems," in Proc. GLOBECOM, Dec. 2003, pp. 3851-3856.

Cited By

Singh SKumar CNath P(2022)Resource-Cardinality Based Scheme to Reduce Resource Lookup Cost in Structured P2P NetworksWireless Personal Communications: An International Journal10.1007/s11277-022-09714-x125:4(3351-3377)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11277-022-09714-x
Singh SKumar CNath P(2021)Analysis and modelling the effects of mobility, Churn rate, node’s life span, intermittent bandwidth and stabilization cost of finger table in structured mobile P2P networksWireless Networks10.1007/s11276-020-02493-y27:2(1049-1062)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11276-020-02493-y
Singh MKumar CNath P(2020)Finger Forwarding Scheme to Reduce Lookup Cost in Structured P2P NetworksWireless Personal Communications: An International Journal10.1007/s11277-020-07475-z114:3(2263-2281)Online publication date: 17-May-2020
https://dl.acm.org/doi/10.1007/s11277-020-07475-z
Show More Cited By

Index Terms

An analytical study of a structured overlay in the presence of dynamic membership

Recommendations

Locality in structured peer-to-peer networks

Distributed hash tables (DHTs), used in a number of structured peer-to-peer (P2P) systems, provide efficient mechanisms for resource placement and location. A key distinguishing feature of current DHT systems, such as Chord, Pastry, CAN and Tapestry, is ...
A location-aware peer-to-peer overlay network: Research Articles

This work describes a novel location-aware, self-organizing, fault-tolerant peer-to-peer (P2P) overlay network, referred to as Laptop. Network locality-aware considerations are a very important metric for designing a P2P overlay network. Several network ...
Resilience of structured P2P systems under churn: The reachable component method

Users in a peer-to-peer (P2P) system join and leave the network in a continuous manner. Understanding the resilience properties of P2P systems under high rate of node churn becomes important. In this work, we first find that a lifetime-based dynamic ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 4

August 2008

249 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 August 2008

Revised: 04 February 2007

Received: 07 October 2005

Published in TON Volume 16, Issue 4

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
250
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Singh SKumar CNath P(2022)Resource-Cardinality Based Scheme to Reduce Resource Lookup Cost in Structured P2P NetworksWireless Personal Communications: An International Journal10.1007/s11277-022-09714-x125:4(3351-3377)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11277-022-09714-x
Singh SKumar CNath P(2021)Analysis and modelling the effects of mobility, Churn rate, node’s life span, intermittent bandwidth and stabilization cost of finger table in structured mobile P2P networksWireless Networks10.1007/s11276-020-02493-y27:2(1049-1062)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11276-020-02493-y
Singh MKumar CNath P(2020)Finger Forwarding Scheme to Reduce Lookup Cost in Structured P2P NetworksWireless Personal Communications: An International Journal10.1007/s11277-020-07475-z114:3(2263-2281)Online publication date: 17-May-2020
https://dl.acm.org/doi/10.1007/s11277-020-07475-z
Sànchez-Artigas MFérnandez-Casado E(2011)Evaluation of p2p systems under different churn modelsProceedings of the 17th international conference on Parallel processing - Volume Part I10.5555/2033345.2033402(541-553)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.5555/2033345.2033402
Ardelius JMejías B(2011)Modeling the performance of ring based DHTs in the presence of network address translatorsProceedings of the 11th IFIP WG 6.1 international conference on Distributed applications and interoperable systems10.5555/2022090.2022092(15-28)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.5555/2022090.2022092

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents