一种基于网络编码的云存储系统

doi:10.11896／j.issn.1002-137X.2018.12.047

摘要/Abstract

摘要： 存储空间、修复带宽和更新带宽是云存储系统的3个重要指标,系统设计往往需要在这些性能度量之间取折衷。为了降低存储空间、修复带宽、更新带宽以及系统复杂度,文中提出了一种基于网络编码的云存储系统。该系统结构为m*n数据阵列的形式,n列表示n个存储节点,其中k个节点用于存储原始数据,称为系统部分;另外(n－k)个节点用于存储校验字符,称为非系统部分。数据阵列的m行对应m个系统形式的(n,k)最大距离可分(MDS)码,每个源数据符号只参与它所在行的编码,不参与其他行的编码,这种系统结构大幅降低了编译码的复杂度。该系统可以承受最多(n－k)个节点的失效,此外,当单节点失效时,由于使用了系统形式的MDS码,可以使用干扰对齐技术进一步缩减修复带宽。与现有的某些云存储系统相比,该系统明显降低了存储空间、修复带宽和更新带宽等资源消耗,性能得到大幅提升。

关键词: 干扰对齐, 网络编码, 云存储, 最大距离可分码

Abstract: Storage,repair bandwidth and update bandwidth are three performance metrics for a cloud storage system.System design needs to make trade-off among them.To decrease the consumption on storage,repair bandwidth update bandwidth and system complexity,this paper proposed a network coding based cloud storage system.This system is in the form of an m*n data array.The n columns stand for n storage nodes,which are comprised of two parts,one is systematic part which stores source symbols,and the other is nonsystematic part which stores parity symbols.The m rows of the data array stand for the number of m(n,k) systematic Maximum Distance Separable (MDS) code.Any source symbol is only involved into encoding within the unique row in which it locates and is not used by other rows.Such a structure significantly decreases the complexity of encoding and decoding.The functionality of the system is still available even in front of the failures of less than (n－k) nodes.Moreover,by using interference alignment,systematic MDS code is beneficial to further reduce repair bandwidth in case of single node failures.Compared to some existing cloud storage schemes,the system greatly reduces the resource consumption on storage space,update bandwidth and repair bandwidth,so its performance is improved significantly.

Key words: Cloud storage, Interference alignment, MDS code, Network coding

中图分类号:

TP393

刘宴涛, 刘珩. 一种基于网络编码的云存储系统[J]. 计算机科学, 2018, 45(12): 293-298. https://doi.org/10.11896／j.issn.1002-137X.2018.12.047

LIU Yan-tao, LIU Heng. Cloud Storage System Based on Network Coding[J]. Computer Science, 2018, 45(12): 293-298. https://doi.org/10.11896／j.issn.1002-137X.2018.12.047

参考文献

[1]DIMAKIS A G,GODFREY P B,WU Y,et al.Network Coding for Distributed Storage Systems [J].IEEE Transactions on Information Theory,2010,56(9):4539-4551.
[2]DIMAKIS A G,RAMCHANDRAN K,WU Y,et al.A Survey on Network Codes for Distributed Storage [J].Proceedings of the IEEE,2011,99(3):476-489.
[3]ACEDANSKI S,DEB S,MEDARD M,et al.How Good Is Random Linear Coding Based Distributed Networked Storage [C]∥The 1st Workshop on Network Coding,Theory and Applications.Riva del Garda:IEEE Press,2005:1-6.
[4]ZAKERINASAB M R,WANG M.An Update Model for Network Coding in Cloud Storage Systems [C]∥The 50th Annual Allerton Conference on Communication,Control,and Computing.Monticello:IEEE Press,2012:1158-1165.
[5]ZAKERINASAB M R,WANG M.DeltaNC:Efficient File Updates for Network-Coding-Based Cloud Storage Systems [C]∥IEEE 21st International Symposium on Modelling,Analysis and Simulation of Computer and Telecommunication Systems.San Francisco:IEEE Press,2013:360-364.
[6]WANG L J,CHEN Y,YAN X C,et al.Differential Data Update Scheme on Network-Coding-Based Cloud Storage System [J].Journal on Communications,2017,38(3):154-164.(in Chinese)
王龙江,陈越,严新成,等.网络编码云存储系统差分数据更新方案[J].通信学报,2017,38(3):154-164.
[7]WU H,LAI C Z,FAN J L,et al.Data Update Algorithm Based on Secure Network Coding in Cloud Environment [J].Journal on Communications,2017,35(5):121-127.(in Chinese)
吴昊,赖成喆,范九伦,等.云环境下基于安全网络编码的数据更新方法[J].通信学报,2017,35(5):121-127.
[8]WU Y,DIMAKIS A G.Reducing Repair Traffic for ErasureCoding-Based Storage via Interference Alignment [C]∥2009 IEEE International Symposium on Information Theory.Seoul:IEEE Press,2009:2276-2280.
[9]CADAMBE V R,JAFAR S A.Interference Alignment and the Degrees of Freedom for the K User Interference Channel [J].IEEE Transactions on Information Theory,2008,54(8):3425-3441.
[10]HUANG Q.Efficient Repair Schemes in Cloud Storage Based on Interference Alignment [D].Chongqing:Chongqing University of Posts and Telecommunications,2014.(in Chinese)
黄倩.基于干扰对齐的高效云存储修复方法研究[D].重庆:重庆邮电大学,2014.
[11]CHEN H C H,HU Y,LEE P P C,et al.NCCLoud:A Network-Coding-Based Storage System in a Cloud-of-Clouds [J].IEEE Transactions on Computers,2014,63(1):31-44.
[12]ZHANG J F.Cloud Storage Schemes Based on Network Coding[D].Changsha:Central South University,2014.(in Chinese)
张俊峰.基于网络编码云存储方案研究 [D].长沙:中南大学,2014.
[13]XIE C Y,JIA Z T,QING S H,et al.Semi-Random Linear Network Coding for Cloud Storage Redundancy [J].Journal of Beijing University of Posts and Telecommunications,2013,36(3):30-34.(in Chinese)
谢垂益,贾忠田,卿斯汉,等.适用于云存储冗余的半随机线性网络编码[J].北京邮电大学学报,2013,36(3):30-34.
[14]XU Y,HE Q,LUO Y.Optimal Repair for Distributed Storage Codes in Vehicular Networks [C]∥2016 IEEE 83^rd Vehicular Technology Conference.Nanjing:IEEE Press,2016:1-5.
[15]SIPOS M,GAHM J,VENKAT N,et al.Erasure Coded Storage on A Changing Network:the Untold Story [C]∥2016 IEEE Global Communications Conference (GLOBECOM).Washington DC:IEEE Press,2016:1-6.
[16]ELYASI M,MOHAJER S.Determinant Coding:A NovelFramework for Exact-Repair Regenerating Codes [J].IEEE Transactions on Information Theory,2016,62(12):6683-6697.
[17]WANG Z,TAMO I,BRUCK J.Explicit Minimum Storage Regenerating Codes [J].IEEE Transactions on Information Theory,2016,62(8):4466-4479.
[18]PAPAILIOPOULOS D S,LUO J,DIMAKIS A G,et al.Simple Regenerating Codes:Network Coding for Cloud Storage [OL].http://arXiv.org/pdf/1109.0264.pdf.
[19]PRAKASH N,KRISHNAN M N.The Storage-Repair-Band-width Trade off of Exact Repair Linear Regenerating Codes for the Case d=k=n－1 [C]∥IEEE International Symposium on Information Theory (ISIT).Hong Kong:IEEE Press,2015:859-863.
[20]LI J,TANG X,XIANG W.A New Construction of (k+2,k)Minimal Storage Regenerating Code over F₃ with Optimal Access Property for All Nodes [J].IEEE Communications Letters,2016,20(7):1289-1292.
[21]WANG Z,TAMO I,BRUCK J.Optimal Rebuilding of Multiple Erasures in MDS Codes [J].IEEE Transactions on Information Theory,2017,63(2):1084-1101.
[22]LI R,LIN J,LEE P P C.Enabling Concurrent Failure Recovery for Regenerating-Coding-Based Storage Systems:from Theory to Practice [J].IEEE Transactions on Computers,2015,64(7):1898-1911.
[23]ZHANG H,LI H,SHUM K W,et al.Concurrent Regenerating Codes [J].IET Communications,2017,11(3):362-369.
[24]KUMAR S,ROSNES E,AMAT A G I.Secure RepairableFountain Codes [J].IEEE Communications Letters,2016,20(8):1491-1494.
[25]AGARWAL A,MAZUMDAR A.Security in Locally RepairableStorage [J].IEEE Transactions on Information Theory,2016,62(11):6204-6217.
[26]CHEN Y,WANG L,LIAO C.Eavesdropping Prevention forNetwork Coding Encrypted Cloud Storage Systems [J].IEEE Transactions on Parallel and Distributed Systems,2016,27(8):2261-2273.

相关文章 15

[1]	徐堃, 付印金, 陈卫卫, 张亚男. 基于区块链的云存储安全研究进展 Research Progress on Blockchain-based Cloud Storage Security Mechanism 计算机科学, 2021, 48(11): 102-115. https://doi.org/10.11896/jsjkx.210600015
[2]	韩晓冬, 高飞, 张立炜. 适用于线性网络编码关键路径的实时性算法 Novel Real-time Algorithm for Critical Path of Linear Network Coding 计算机科学, 2020, 47(9): 232-237. https://doi.org/10.11896/jsjkx.190800023
[3]	李莹, 于亚新, 张宏宇, 李振国. 基于TBchain区块链的高可信云存储模型 High Trusted Cloud Storage Model Based on TBchain Blockchain 计算机科学, 2020, 47(9): 330-338. https://doi.org/10.11896/jsjkx.190800147
[4]	陈利锋, 朱路平. 一种基于云端加密的FPGA自适应动态配置方法 Encrypted Dynamic Configuration Method of FPGA Based on Cloud 计算机科学, 2020, 47(7): 278-281. https://doi.org/10.11896/jsjkx.190700110
[5]	徐光宪, 崔俊杰. 一种基于量子GHZ态的防窃听网络编码 Anti-eavesdropping Network Coding Based on Quantum GHZ State 计算机科学, 2020, 47(7): 314-321. https://doi.org/10.11896/jsjkx.190500168
[6]	张茜, 王箭. 用户身份可追踪的云共享数据完整性审计方案 Public Integrity Auditing for Shared Data in Cloud Supporting User Identity Tracking 计算机科学, 2020, 47(6): 303-309. https://doi.org/10.11896/jsjkx.190600079
[7]	李树全,刘磊,朱大勇,熊超,李锐. 一种面向云存储的数据动态验证方案 Protocol of Dynamic Provable Data Integrity for Cloud Storage 计算机科学, 2020, 47(2): 256-261. https://doi.org/10.11896/jsjkx.181202371
[8]	宋莺, 钟忺, 孙宝林, 桂超. MANET中基于滑动窗口的网络编码协作算法 Sliding Window-based Network Coding Cooperative Algorithm in MANET 计算机科学, 2020, 47(11): 322-326. https://doi.org/10.11896/jsjkx.191000181
[9]	白利芳, 祝跃飞, 芦斌. 云数据存储安全审计研究及进展 Research and Development of Data Storage Security Audit in Cloud 计算机科学, 2020, 47(10): 290-300. https://doi.org/10.11896/jsjkx.191000111
[10]	张锦辉, 邓茜, 李振宇. 网络编码与多路径传输在互联网视频直播中的应用研究 Study on Application of Network Coding and Multipath Transmission in Internet Live Video Broadcasting 计算机科学, 2019, 46(8): 171-177. https://doi.org/10.11896/j.issn.1002-137X.2019.08.028
[11]	冀保峰, 王一丹, 邢冰冰, 李玉琦, 高宏峰, 韩瑽琤. 基于分层多跳物理层网络编码的超密集网络吞吐量增强方法 Enhancement Method of Throughput in Ultra-dense Network Based on Hierarchical Multi-hop Physical Layer Network Coding 计算机科学, 2019, 46(7): 56-60. https://doi.org/10.11896/j.issn.1002-137X.2019.07.008
[12]	乔毛,秦岭. 云存储服务中一种高效属性撤销的AB-ACCS方案 AB-ACCS Scheme for Revocation of Efficient Attributes in Cloud Storage Services 计算机科学, 2019, 46(7): 96-101. https://doi.org/10.11896/j.issn.1002-137X.2019.07.015
[13]	谢四江,贾倍,王鹤,许世聪. 基于多分支路径树的云存储大数据完整性证明机制 Cloud Big Data Integrity Verification Scheme Based on Multi-branch Tree 计算机科学, 2019, 46(3): 188-196. https://doi.org/10.11896/j.issn.1002-137X.2019.03.028
[14]	陈杰, 谢显中, 黄倩, 黎佳. 无线车载网络中一种基于跨层优化的网络编码TCP协议 Network Coding TCP Protocol Based on Cross-layer Optimization in Wireless Vehicle Networks 计算机科学, 2019, 46(2): 88-94. https://doi.org/10.11896/j.issn.1002-137X.2019.02.014
[15]	顾晨阳, 付伟, 刘金龙, 孙刚. 云存储中的ORAM研究综述 Survey of ORAM Research in Cloud Storage 计算机科学, 2019, 46(11A): 341-347.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed