Skip to main content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Wireless Personal Communications 2/2022

12-06-2022

A Novel Repairable Fountain Codes Scheme Based on Partial Duplication Technique

Authors: Anan Zhou, Benshun Yi, Mian Xiang, Laigan Luo

Published in: Wireless Personal Communications | Issue 2/2022

Login to get access
share
SHARE

Abstract

Distributed storage system (DSS) is an emerging paradigm which provides reliable storage services for various source data. As the fault-tolerance scheme for DSS, erasure codes are required to provide redundancy service with high fault-tolerance and low cost.However, the existing coding scheme cannot provide these requirements well. Thus, it becomes an important yet challenging issue to find a code for storing various source data with high fault-tolerance and low cost. In this paper, a novel construction of repairable fountain codes with unequal locality is proposed by combining with partial duplication technique, namely the PD-ULRFC scheme. We construct a multi-tier heterogeneous storage network, where data core, processing units and storage nodes collaboratively store and transmit data. Moreover, the proposed PD-ULRFC scheme can reduce the repair and download cost by sacrificing a little extra storage occupation. Furthermore, the expressions of the repair cost and download cost are derived to analyze the performance of PD-ULRFC scheme. The simulation results demonstrate that the PD-ULRFC scheme significantly outperforms other redundant schemes in communication cost saving.
Literature
1.
go back to reference Weatherspoon, H., & Kubiatowicz, J. D. (2002). Erasure coding vs. replication: A quantitative comparison. In Proceedings of the international workshop on peer-to-peer system (pp. 328–337). Weatherspoon, H., & Kubiatowicz, J. D. (2002). Erasure coding vs. replication: A quantitative comparison. In Proceedings of the international workshop on peer-to-peer system (pp. 328–337).
2.
go back to reference Dimakis, A. G., Godfrey, P. B., Wu, Y., Wainwright, M. J., & Ramchandran, K. (2010). Network coding for distributed storage systems. IEEE Transactions on Information Theory, 56(9), 4539–4551. CrossRef Dimakis, A. G., Godfrey, P. B., Wu, Y., Wainwright, M. J., & Ramchandran, K. (2010). Network coding for distributed storage systems. IEEE Transactions on Information Theory, 56(9), 4539–4551. CrossRef
4.
go back to reference Gopalan, P., Huang, C., Simitci, H., & Yekhanin, S. (2012). On the locality of codeword symbols. IEEE Transactions on Information Theory, 58(11), 6925–6934. MathSciNetCrossRef Gopalan, P., Huang, C., Simitci, H., & Yekhanin, S. (2012). On the locality of codeword symbols. IEEE Transactions on Information Theory, 58(11), 6925–6934. MathSciNetCrossRef
5.
go back to reference Papailiopoulos, D. S., & Dimakis, A. G. (2012). Locally repairable codes. In Proceedings of the IEEE international symposium on information theory proceeding (ISIT) (pp. 2771–2775). Papailiopoulos, D. S., & Dimakis, A. G. (2012). Locally repairable codes. In Proceedings of the IEEE international symposium on information theory proceeding (ISIT) (pp. 2771–2775).
6.
go back to reference Huang, C., Simitci, H., Xu, Y. K., Ogus, A., Calder, B., Gopalan, P., Li, J., & Yekhanim, S. (2012). Erasure coding in windows azure storage. In Proceedings of the USENIX conferences annual technical conference (pp. 1–12). Huang, C., Simitci, H., Xu, Y. K., Ogus, A., Calder, B., Gopalan, P., Li, J., & Yekhanim, S. (2012). Erasure coding in windows azure storage. In Proceedings of the USENIX conferences annual technical conference (pp. 1–12).
7.
go back to reference Luby, M. (2002). LT Codes. In Proceedings of the 43rd Annual IEEE symposium on foundations computer science (pp. 271–280). Luby, M. (2002). LT Codes. In Proceedings of the 43rd Annual IEEE symposium on foundations computer science (pp. 271–280).
9.
go back to reference MacKay, D. J. C. (2005). Fountain Codes. IEE Proceeding, Part I, Communications, 152(6), 1062–1068. MacKay, D. J. C. (2005). Fountain Codes. IEE Proceeding, Part I, Communications, 152(6), 1062–1068.
10.
go back to reference Cao, N., Wang, Q., Ren, K., & Lou, W.J. (2010). Distributed storage coding for flexible and efficient data dissemination and retrieval in wireless sensor networks. In Proceedings of the IEEE international conference on communications (ICC). Cao, N., Wang, Q., Ren, K., & Lou, W.J. (2010). Distributed storage coding for flexible and efficient data dissemination and retrieval in wireless sensor networks. In Proceedings of the IEEE international conference on communications (ICC).
11.
go back to reference Lu, H.F., Foh, C. H., Wen, Y.G., & Cai, J.F. (2012). Optimizing content retrieval delay for LT-based distributed cloud storage systems. In Proceedings of the IEEE global communications conference (GLOBECOM). Lu, H.F., Foh, C. H., Wen, Y.G., & Cai, J.F. (2012). Optimizing content retrieval delay for LT-based distributed cloud storage systems. In Proceedings of the IEEE global communications conference (GLOBECOM).
12.
go back to reference Ye, X. C., Chen, W. T., & Tang, F. L. (2015). LT codes based distributed coding for efficient distributed storage in wireless sensor networks. In Proceedings of the IFIP networking conference. Ye, X. C., Chen, W. T., & Tang, F. L. (2015). LT codes based distributed coding for efficient distributed storage in wireless sensor networks. In Proceedings of the IFIP networking conference.
13.
go back to reference Janet, J., Balakrishnan, S., & Somasekhara, K. (2016). Fountain code based cloud storage mechanism for optimal file retrieval delay. In Proceedings of thw international conference on information communication and embedded systems (ICICES). Janet, J., Balakrishnan, S., & Somasekhara, K. (2016). Fountain code based cloud storage mechanism for optimal file retrieval delay. In Proceedings of thw international conference on information communication and embedded systems (ICICES).
14.
go back to reference Asteris, M., & Dimakis, A. G. (2014). Repairable fountain codes. IEEE Journal on Selected Areas in Communications, 32(5), 1037–1047. CrossRef Asteris, M., & Dimakis, A. G. (2014). Repairable fountain codes. IEEE Journal on Selected Areas in Communications, 32(5), 1037–1047. CrossRef
15.
go back to reference Gummadi, R. (2011). Coding and scheduling in networks for erasures and broadcast. Ph.D. dissertation, University of Illinois at Urbana Champaign. Gummadi, R. (2011). Coding and scheduling in networks for erasures and broadcast. Ph.D. dissertation, University of Illinois at Urbana Champaign.
16.
go back to reference Okpotse, T., & Yousefi, S. (2015). Locality-aware fountain codes for massive distributed storage systems. In Proceedings of the 2015 IEEE 14th Canadian workshop on information theory (CWIT) (pp. 18–21). Okpotse, T., & Yousefi, S. (2015). Locality-aware fountain codes for massive distributed storage systems. In Proceedings of the 2015 IEEE 14th Canadian workshop on information theory (CWIT) (pp. 18–21).
17.
go back to reference Okpotse, T., & Yousefi, S. (2019). Systematic fountain codes for massive storage using the truncated Poisson distribution. IEEE Transactions on Communications, 67(2), 943–954. CrossRef Okpotse, T., & Yousefi, S. (2019). Systematic fountain codes for massive storage using the truncated Poisson distribution. IEEE Transactions on Communications, 67(2), 943–954. CrossRef
18.
go back to reference Wang, Y., Gu, S. S., Zhao, L., Zhang, N., Xiang, W., & Zhang, Q. Y. (2020). Repairable fountain coded storage systems for multi-tier mobile edge caching networks. IEEE Transactions on Network Science and Engineering, 7(4), 2310–2322. MathSciNetCrossRef Wang, Y., Gu, S. S., Zhao, L., Zhang, N., Xiang, W., & Zhang, Q. Y. (2020). Repairable fountain coded storage systems for multi-tier mobile edge caching networks. IEEE Transactions on Network Science and Engineering, 7(4), 2310–2322. MathSciNetCrossRef
19.
go back to reference Baik, J., Suh, Y., Shin, M., Kim, S., & Kim, J. (2020). Locality-improved repairable fountain codes for distributed storage systems. In Proceedings of the IEEE international conference on communication (ICC). Baik, J., Suh, Y., Shin, M., Kim, S., & Kim, J. (2020). Locality-improved repairable fountain codes for distributed storage systems. In Proceedings of the IEEE international conference on communication (ICC).
20.
go back to reference Elishco, O., & Barg, A. (2021). Capacity of dynamical storage systems. IEEE Transactions on Information Theory, 67(1), 329–346. MathSciNetCrossRef Elishco, O., & Barg, A. (2021). Capacity of dynamical storage systems. IEEE Transactions on Information Theory, 67(1), 329–346. MathSciNetCrossRef
Metadata
Title
A Novel Repairable Fountain Codes Scheme Based on Partial Duplication Technique
Authors
Anan Zhou
Benshun Yi
Mian Xiang
Laigan Luo
Publication date
12-06-2022
Publisher
Springer US
Published in
Wireless Personal Communications / Issue 2/2022
Print ISSN: 0929-6212
Electronic ISSN: 1572-834X
DOI
https://doi.org/10.1007/s11277-022-09803-x

Other articles of this Issue 2/2022

Wireless Personal Communications 2/2022 Go to the issue