The Journal of Korean Institute of Communications and Information Sciences (한국통신학회논문지)

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지
DOI QR코드

DOI QR Code

Average Repair Read Cost of Linear Repairable Code Ensembles

선형 재생 부호 앙상블의 평균 복구 접속 비용

  • Park, Jin Soo (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Kim, Jung-Hyun (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Park, Ki-Hyeon (School of Electrical and Electronic Engineering, Yonsei University) ;
  • Song, Hong-Yeop (School of Electrical and Electronic Engineering, Yonsei University)
  • Received : 2014.08.30
  • Accepted : 2014.11.06
  • Published : 2014.11.28
Download PDF
⟨ Previous Next ⟩

Abstract

In this paper, we derive the average repair bandwidth and/or read cost for arbitrary repairable linear code ensembles. The repair bandwidth and read cost are the required amount of data and access number of nodes to restore a failed node, respectively. Here, the repairable linear code ensemble is given by such parameters as the number k of data symbols, the number m of parity symbols, and their degree distributions. We further assume that the code is systematic, and no other constraint is assumed, except possibly that the exact repair could be done by the parity check-sum relation with fully connected n=k+m storages. This enables one to apply the result of this paper directly to any randomly constructed codes with the above parameters, such as linear fountain codes. The final expression of the average repair read cost shows that it is highly dependent on the degree distribution of parity symbols, and also the values n and k.

본 논문에서는 임의의 선형 재생 부호 앙상블에 대하여 복구 대역폭(Repair bandwidth)과 접속 비용(Repair read cost)의 평균을 유도한다. 한 데이터가 여러 노드에 부호화 되어 분산 저장된 상황에서 하나의 노드가 소실될 경우, 이를 복구하기 위해 필요한 데이터 량을 복구 대역폭, 접속해야 하는 노드 수를 복구 접속 비용이라 한다. 이 때, 선형 재생 부호 앙상블은 데이터 심볼의 수 k와 패리티 심볼의 수 m, 그리고 그들의 차수 분포로 주어진다. 우리는 이러한 부호들이 시스터메틱(Systematic)이며 정확한 복구(Exact repair)를 수행하고 n=k+m개의 모든 저장소(Storages)들이 전부 연결되어 있는 상황을 가정한다. 본 논문의 결과는 파운틴 부호 등과 같이 위와 같은 파라미터들로 랜덤하게 만들어진 부호들에 바로 적용 가능하다. 최종 결과식은 평균 복구 접속 비용이 차수 분포와 n, k에 따라 결정됨을 보여준다.

Keywords

References

  1. T.-H. Kim, J. Kim, and Y. I. Eom, "A scheme on high-performance caching and high capacity file transmission for cloud storage optimization," J. KICS, vol. 37C, no. 8, Aug. 2012. https://doi.org/10.7840/kics.2012.37C.8.670
  2. I. Y. Jung, I. Jo, and Y. Yu, "Trust Assurance of Data in Cloud Computing Environment," J. KICS, vol. 36B, no. 9, Sept., 2011. https://doi.org/10.7840/KICS.2011.36B.9.1066
  3. J.-H. Kim, J. S. Park, K.-H. Park, M. Y. Nam, and H.-Y. Song , "Trends of regenerating codes for next-generation cloud storage systems," Inf. Commun. Mag., vol. 31, no. 2, pp. 125-131, Feb. 2014.
  4. A. G. Dimakis, P. B. Godfrey, Y. Wu, M. J. Wainwright, and K. Ramchandran, "Network coding for distributed storage systems," IEEE Trans. Inf. Theory, vol. 56, no. 9, Sept. 2010.
  5. A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, "A survey on network codes for distributed storage," in Proc. IEEE, vol. 99, no. 3, Mar. 2011.
  6. J. Li and B. Li, "Erasure coding for cloud storage systems: a survey," Tsinghua Sci. Technol., vol. 18, no. 3, Jun. 2013.
  7. F. Oggier and A. Datta, Coding Techniques for Repairablity in Networked Distributed Storage Systems, Foundations and Trends in Communications and Information Theory, MA: Now Publishers Inc., 2013.
  8. H. T. Lim, M. J. Park, S. G. Kang, and E. K. Joo, "Performance analysis of RS, turbo and LDPC code in the binary symmetric erasure channel," J. KICS, vol. 35, no. 2, Feb. 2010.
  9. N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, "Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage-bandwidth tradeoff," IEEE Trans. Inf. Theory, vol. 58, no. 3, Mar. 2012.
  10. K. V. Rashmi, N. B. Shah, and P. V. Kumar, "Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction," IEEE Trans. Inf. Theory, vol. 57, no. 8, Aug. 2011.
  11. M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur, "XORing elephants: Novel erasure codes for big data," in Proc. 39th Int. Conf. Very Large Data Bases, vol. 6, no. 5, pp. 325-336, Mar. 2013.
  12. C. Huang, H. Simitci, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, "Erasure coding in windows azure storage," in Proc. 2012 USENIX Annu. Tech. Conf. (ATC '12), Boston, MA, Jun. 2012.
  13. P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, "On the locality of codeword symbols," IEEE Trans. Inf. Theory, vol. 58, no. 11, Nov. 2012.
  14. A. Mazumdar, V. Chandar, and G. W. Wornell, "Local recovery properties of capacity achieving codes," in Proc. Inf. Theory Appl. Workshop (ITA), pp. 1-3, San Diego, CA, Feb. 2013.
  15. C. Huang, M. Chen, and J. Li, "Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems," ACM Trans. Storage, vol. 9, no. 1, Article 3, Mar. 2013.
  16. M. Asteris and A. G. Dimakis, "Repairable fountain codes," in Proc. IEEE Int. Symp. Inf. Theory (ISIT '12), vol. 32, no. 5, pp. 1037- 1047, May 2014.
  17. Y. Wu and A. G. Dimakis, "Reducing repair traffic for erasure coding-based storage via interference alignment," in Proc. 2009 IEEE Int. Symp. Info. Theory (ISIT '09), pp. 2276- 2280, Seoul, Jun.-Jul. 2009.
  18. V. R. Cadambe, S. A. Jafar, H. Maleki, K. Ramchandran, and C. Suh, "Asymptotic interference alignment for optimal repair of MDS codes in distributed storage," IEEE Trans. Inf. Theory, vol. 59, no. 5, May 2013.
  19. M. Luby, "LT-codes," in Proc. 43rd Annu. IEEE Symp. Foundations of Comput. Sci. (FOCS), Vancouber, BC, Canada, Nov. 2002.