Top

Peer-to-Peer Networking and Applications

Published in:

01-12-2014

P2P storage systems: Study of different placement policies

Authors: Stéphane Caron, Frédéric Giroire, Dorian Mazauric, Julian Monteiro, Stéphane Pérennes

Published in: Peer-to-Peer Networking and Applications | Issue 4/2014

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In a P2P storage system using erasure codes, a data block is encoded in many redundancy fragments. These fragments are then sent to distinct peers of the network. In this work, we study the impact of different placement policies of these fragments on the performance of storage systems. Several practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. We compare three policies: two of them are local, in which the data are stored in logical neighbors, and the other one, global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. We then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. Additionally, we propose a new external reconstruction strategy that greatly improves the performance of local placement strategies. Finally, we give analytical methods to estimate the mean time to the occurrence of data loss for the three policies.

previous article Hybrid fluid modeling approach for performance analysis of P2P live video streaming systems

next article Tsunami: A parasitic, indestructible botnet on Kad

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

There are two groups of peers in each spike of the Buddy. A bigger one around 1500 kbit/s, that corresponds to peers doing the retrieval and sending phases of the reconstruction (i.e., \(s+r-r_0\) uploads for each block). The smaller one, with an upload bandwidth around 400 kbit/s, correspond to peers that have failed and were replaced with empty disks. As they are empty, they do not send fragments to the reconstructors (no retrieval upload), but they are in charge of some reconstructions, so we see their sending upload (i.e. \(r-r_0\) fragments for each block).

Alouf S, Dandoush A, Nain P (2007) Performance analysis of peer-to-peer storage systems. In: Lorne M, Tadeusz D, James Y (eds) Managing traffic performance in converged networks. 20th International Teletraffic Congress, ITC20 2007, Ottawa, Canada, 17–21 June, 2007. Lecture notes in computer science, vol 4516. Springer, Heidelberg, pp 642–653

Araujo J, Giroire F, Monteiro J (2011) Hybrid approaches for distributed storage systems. In: Proceedings of fourth international conference on data management in grid and P2P systems (Globe’11), Toulouse, France

Batten C, Barr K, Saraf A, Trepetin S (2002) pStore: a secure peer-to-peer backup system. Technical Memo MIT-LCS-TM-632. Massachusetts Institute of Technology Laboratory for Computer Science

Bermond J-C, Jean-Marie A, Mazauric D, Yu J (2011) Well balanced designs for data placement. Research Report 7725. INRIA

Bernard S, Le Fessant F (2009) Optimizing peer-to-peer backup using lifetime estimations. In: Proceedings of the 2009 EDBT/ICDT workshops. ACM, pp 26–33

Bhagwan R, Tati K, Cheng Yc, Savage S, Voelker GM (2004) Total recall: system support for automated availability management. In: Proceedings of the 1st USENIX symposium on networked systems design and implementation (NSDI), pp 337–350

Bolosky WJ, Douceur JR, Ely D, Theimer M (2000) Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs. ACM SIGMETRICS Perform Eval Rev 28(1):34–43CrossRef

Caron S, Giroire F, Mazauric D, Monteiro J, Pérennes S (2010) Data life time for different placement policies in p2p storage systems. In: Proceedings of the 3rd international conference on data management in grid and P2P systems (Globe). Lecture notes in computer science, vol 6265. Bilbao, pp 75–88

Chun B-G, Dabek F, Haeberlen A, Sit E, Weatherspoon H, Kaashoek MF, Kubiatowicz J, Morris R (2006) Efficient replica maintenance for distributed storage systems. In: Proceedings of USENIX symposium on networked systems design and implementation (NSDI). Berkeley, pp 45–58

10.

Colbourn CJ, Dinitz JH (2007) Handbook of combinatorial designs, vol 42. Chapman & Hall/CRC, New York

11.

Dabek F, Kaashoek MF, Karger D, Morris R, Stoica I (2001) Wide-area cooperative storage with cfs. In: Proceedings of the ACM symposium on operating systems principles (SOSP). Canada, pp 202–215

12.

Dabek F, Li J, Sit E, Robertson J, Kaashoek MF, Morris R (2004) Designing a DHT for low latency and high throughput. In: Proceedings of usenix symposium on networked systems design and implementation (NSDI). San Francisco

13.

Dalle O, Giroire F, Monteiro J, Pérennes S (2009) Analysis of failure correlation impact on peer-to-peer storage systems. In: Proceedings of the 9th IEEE international conference on peer-to-peer computing (P2P), pp 184–193

14.

De Bruijn NG (1969) A combinatorial problem. Kibern Sb Nov Ser 6:33–40

15.

Douceur JR, Wattenhofer R (2001) Competitive hill-climbing strategies for replica placement in a distributed file system. In: DISC ’01: proceedings of the 15th international conference on distributed computing. Springer-Verlag, London, pp 48–62

16.

Douceur JR, Wattenhofer RP (2001) Large-scale simulation of replica placement algorithms for a serverless distributed file system. In: 9th International workshop on modeling, analysis, and simulation of computer and telecommunication systems (MASCOTS 2001), 15–18 August 2001, Cincinnati, OH, USA. IEEE Computer Society, pp 311–322

17.

Druschel P, Rowstron A (2001) PAST: a large-scale, persistent peer-to-peer storage utility. In: Proceedings of 8th workshop on hot topics in operating systems. Schoss Elmau, Germany, pp 75–80CrossRef

18.

Ghemawat S, Gobioff H, Leung S-T (2003) The google file system. ACM SIGOPS Oper Syst Rev 37(5):29–43CrossRef

19.

Giroire F, Monteiro J, Pérennes S (2009) P2P storage systems: how much locality can they tolerate? In: Proceedings of the 34th IEEE conference on local computer networks (LCN). Zurich, pp 320-323

20.

Giroire F, Monteiro J, Pérennes S (2010) Peer-to-peer storage systems: a practical guideline to be lazy. In: Proceedings of the IEEE global communications conference (GLOBECOM). Miami, pp 1–6

21.

Goldberg AV, Yianilos PN (1998) Towards an archival intermemory. In: ADL ’98: proceedings of the advances in digital libraries conference. IEEE Computer Society, Washington, p 147

22.

Haeberlen A, Mislove A, Druschel P (2005) Glacier: highly durable, decentralized storage despite massive correlated failures. In: Proceedings of USENIX symposium on networked systems design and implementation (NSDI). Berkeley, pp 143–158

23.

Karlsson M, Mahalingam M, Karlsson M, Mahalingam M (2002) Do we need replica placement algorithms in content delivery networks. In: 7th international workshop on web content caching and distribution (WCW)

24.

Kermarrec AM, Le Merrer E, Straub G, Van Kempen A et al (2012) Availability-based methods for distributed storage systems. In: SRDS 2012, 31st international symposium on reliable distributed systems

25.

Ktari S, Zoubert M, Hecker A, Labiod H (2007) Performance evaluation of replication strategies in dhts under churn. In: MUM ’07. ACM, New York, pp 90–97CrossRef

26.

Kubiatowicz J, Bindel D, Chen Y, Czerwinski S, Eaton P, Geels D, Gummadi R, Rhea S, Weatherspoon H, Wells C, et al (2000) OceanStore: an architecture for global-scale persistent storage. ACM SIGARCH Comput Archit News 28(5):190–201CrossRef

27.

Legtchenko S, Monnet S, Sens P, Muller G (2009) Churn-resilient replication strategy for peer-to-peer distributed hash-tables. In: Proceedings of the 11th international symposium on stabilization, safety, and security of distributed systems, vol LNCS 5873. Lyon, pp 485–499

28.

Lian Q, Chen W, Zhang Z (2005) On the impact of replica placement to the reliability of distributed brick storage systems. In: International conference on distributed computing systems (ICSCS’05). IEEE Computer Society, Los Alamitos, pp 187–196CrossRef

29.

Liben-Nowell D, Balakrishnan H, Karger D (2002) Analysis of the evolution of peer-to-peer systems. In: Proceedings of the 21st annual symposium on principles of distributed computing (PODC’02), pp 233–242

30.

Luby MG, Mitzenmacher M, Shokrollahi MA, Spielman DA, Stemann V (1997) Practical loss-resilient codes. In: Proceedings of the 29th annual ACM symposium on theory of computing. ACM, New York, pp 150–159

31.

Patterson DA, Gibson G, Katz RH (1988) A case for redundant arrays of inexpensive disks (raid). In: Proceedings of ACM international conference on management of data (SIGMOD’88). New York, pp 109–116

32.

Picconi F, Baynat B, Sens P (2007) Predicting durability in dhts using markov chains. In: Proceedings of the 2nd international conference on digital information management (ICDIM), vol 2. IEEE pp 532–538

33.

Ramabhadran S, Pasquale J (2006) Analysis of long-running replicated systems. In: Proceedings of IEEE international conference on computer communications (INFOCOM). Barcelona, pp 1–9

34.

Rodrigues R, Liskov B (2005) High availability in dhts: erasure coding vs. replication. In: Workshop on peer-to-peer systems (IPTPS), peer-to-peer systems IV, LNCS, pp 226–239

35.

Ross SM (2006) Introduction to probability models, 9th edn. Academic Press, Inc., OrlandoMATH

36.

Rowstron A, Druschel P (2001) Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility. In: Proceedings of the ACM symposium on operating systems principles (SOSP). New York, pp 188–201

37.

Rzadca K, Datta A, Buchegger S (2010) Replica placement in p2p storage: complexity and game theoretic analyses. In: Distributed computing systems (ICDCS), 2010 IEEE 30th international conference on. IEEE, pp 599–609

38.

Song G, Kim S, Seo D, Jang S (2010) Replica placement algorithm based on peer availability for p2p storage systems. Int J Adv Netw Serv 3(1 and 2):237–248

39.

van Renesse R (2004) Efficient reliable internet storage. In: Workshop on dependable distributed data management. Florianopolis

40.

van Renesse R, Schneider FB (2004) Chain replication for supporting high throughput and availability. In: Proceedings of the 6th conference on symposium on opearting systems design & implementation (OSDI). Berkeley, pp 7–7

41.

Weatherspoon H, Kubiatowicz J (2002) Erasure coding vs. replication: a quantitative comparison. In: Revised papers from the 1st international workshop on peer-to-peer systems (IPTPS), vol LNCS 2429. Cambridge, pp 328–337

Title: P2P storage systems: Study of different placement policies
Authors: Stéphane Caron
Frédéric Giroire
Dorian Mazauric
Julian Monteiro
Stéphane Pérennes
Publication date: 01-12-2014
Publisher: Springer US
Published in: Peer-to-Peer Networking and Applications / Issue 4/2014
Print ISSN: 1936-6442
Electronic ISSN: 1936-6450
DOI: https://doi.org/10.1007/s12083-013-0203-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2014

Key distribution scheme for peer-to-peer communication in mobile underwater wireless sensor networks

SocialTrust: Enabling long-term social cooperation in peer-to-peer services

Group formation with neighbor similarity trust in P2P E-commerce

Security analysis of block cipher Piccolo suitable for wireless sensor networks

Algorithms for promoting anonymity of BS and for prolonging network lifetime of WSN

Distributed Denial of Service (DDoS) detection by traffic pattern analysis

Premium Partner