AN EXPLORATION OF NON-ASYMPTOTIC LOW-DENSITY, PARITY CHECK ERASURE CODES FOR WIDE-AREA STORAGE APPLICATIONS
Abstract
As peer-to-peer and widely distributed storage systems proliferate, the need to perform efficient erasure coding, instead of replication, is crucial to performance and efficiency. Low-Density Parity-Check (LDPC) codes have arisen as alternatives to standard erasure codes, such as Reed-Solomon codes, trading off vastly improved decoding performance for inefficiencies in the amount of data that must be acquired to perform decoding. The scores of papers written on LDPC codes typically analyze their collective and asymptotic behavior. Unfortunately, their practical application requires the generation and analysis of individual codes for finite systems.
This paper attempts to illuminate the practical considerations of LDPC codes for peer-to-peer and distributed storage systems. The three main types of LDPC codes are detailed, and a huge variety of codes are generated, then analyzed using simulation. This analysis focuses on the performance of individual codes for finite systems, and addresses several important heretofore unanswered questions about employing LDPC codes in real-world systems.
References
-
M. S. Allen and R. Wolski , The Livny and Plank-Beck Problems: Studies in data movement on the computational grid , SC2003 ( 2003 ) . Google Scholar -
N. Alon , J. W. Spencer and P. Erdos , The Probabilistic Method ( John Wiley & Sons , New York , 1992 ) . Google Scholar W. A. Burkhard and J. Menon , Disk array storage system reliability, 23rd International Symposium on Fault-Tolerant Computing (1993) pp. 432–441. Google ScholarJ. Byers , A digital fountain approach to reliable distribution of bulk data, ACM SIGCOMM '98 (1998) pp. 56–67. Google ScholarJ. W. Byers , M. Luby and M. Mitzenmacher , Accessing multiple mirror sites in parallel: Using tornado codes to speed up downloads, IEEE INFOCOM (1999) pp. 275–283. Google Scholar- ACM Computing Surveys 26(2), 145 (1994), DOI: 10.1145/176979.176981. Crossref, ISI, Google Scholar
-
R. L. Collins and J. S. Plank , Assessing the performance of erasure codes in the wide-area , DSN-05: International Conference on Dependable Systems and Networks ( IEEE , 2005 ) . Google Scholar - IEEE Transactions on Information Theory 48, 1570 (2002). ISI, Google Scholar
- Digital Fountain, Inc. Next generation data transfer: the meta-content revolution. A Digital Fountain White Paper, http://www.digitalfountain.com, 2002 . Google Scholar
-
R. G. Gallager , Low-Density Parity-Check Codes ( MIT Press , Cambridge, MA , 1963 ) . Crossref, Google Scholar -
H. Jin , A. Khandekar and R. McEliece , Irregular repeat-accumulate codes , 2nd International Symposium on Turbo codes and Related Topics ( 2000 ) . Google Scholar J. Kubiatowicz , Oceanstore: An architecture for global-scale persistent storage, Proceedings of ACM ASPLOS (ACM, 2000) pp. 190–201. Google ScholarW. Litwin and T. Schwarz , Lh*rs: a high-availability scalable distributed data structure using Reed Solomon codes, Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (2000) pp. 237–248. Google Scholar-
M. Luby , LT codes , IEEE Symposium on Foundations of Computer Science ( 2002 ) . Google Scholar M. Luby , M. Mitzenmacher and A. Shokrollahi , Analysis of random processes via and-or tree evaluation, 9th Annual ACM-SIAM Symposium on Discrete Algorithms (ACM, 1998) pp. 364–373. Google ScholarM. Luby , Practical loss-resilient codes, 29th Annual ACM Symposium on Theory of Computing (ACM, 1997) pp. 150–159. Google Scholar- R. J. McEliece. Achieving the Shannon Limit: A progress report. Plenary Talk, 38th Allerton Conference, October 2000 . Google Scholar
J. S. Plank , Improving the performance of coordinated checkpointers on networks of workstations using RAID techniques, 15th Symposium on Reliable Distributed Systems (1996) pp. 76–85. Google Scholar-
J. S. Plank , Small parity-check erasure codes - exploration and observations , DSN-05: International Conference on Dependable Systems and Networks ( IEEE , 2005 ) . Google Scholar - J. S. Plank and M. G. Thomason. On the practical use of LDPC crasure codes for distributed storage applications. Technical Report CS-03-510, University of Tennessee, September 2003 . Google Scholar
J. S. Plank and M. G. Thomason , A practical analysis of low-density parity-check erasure codes for wide-area storage applications, DSN-2004: The International Conference on Dependable Systems and Networks (IEEE, 2004) pp. 115–124. Google Scholar- IEEE Internet Computing 5(5), 40 (2001), DOI: 10.1109/4236.957894. Crossref, ISI, Google Scholar
- T. Richardson and R. Urbanke. Modern coding theory. Draft from http://lthcwww.epfl.ch/papers/ics.ps, August 2003 . Google Scholar
-
A. Roumy , Design methods for irregular repeat accumulate codes , IEEE International Symposium on Information Theory ( 2003 ) . Google Scholar - A. Shokrollahi. Raptor codes. Technical Report DR2003-06-001, Digital Fountain, 2003 . Google Scholar
M. A. Shokrollahi , New sequences of linear time erasure codes approaching the channel capacity, Proceedings of AAECC-13,Lecture Notes in CS 1719 (Springer-Verlag, 1999) pp. 65–76. Google Scholar-
M. A. Shokrollahi ,Lecture Notes in Computer Science 1770 ( 2000 ) . Google Scholar -
M. A. Shokrollahi and R. Storn , Design of efficient erasure codes with differential evolution , IEEE International Symposium on Information Theory ( 2000 ) . Google Scholar -
E. R. Tufte , The Visual Display of Quantitative Information ( Graphics Press , Cheshire, Connecticut , 1983 ) . Google Scholar - R. Urbanke et al. LdcpOpt - a fast and accurate degree distribution optimizer for LPDC ensembles, http://lthcwww.epfl.ch/research/ldpcopt/index.php, 2003 . Google Scholar
-
H. Weatherspoon and J. Kubiatowicz , Erasure coding vs. replication: A quantitative comparison , First International Workshop on Peer-to-Peer Systems (IPTPS) ( 2002 ) . Google Scholar -
S. B. Wicker and S. Kim , Fundamentals of Codes, Graphs, and Iterative Decoding ( Kluwer Academic Publishers , Norwell, MA , 2003 ) . Google Scholar Z. Zhang and Q. Lian , Reperasure: Replication protocol using erasure-code in peer-to-peer storage network, 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02) (2002) pp. 330–339. Google Scholar


