新多节点修复模型下的再生码
|
摘要
关于单节点修复模型,Dimakis已通过信息流图分析出节点存储与修复带宽的理论界。对于多节点的修复,Shum和Hu提出了新节点之间相互合作的模型,并给出此模型下存储与带宽的理论界;Zhang等人介绍的新节点之间不再传输数据的模型,比合作修复减少了设计和运算的复杂性,更符合系统的需要。针对这种新模型,利用割型找出其最小容量割,并用线性规划的方法给出存储—带宽的理论界,过程更为简单。最后给出一些特殊参数下的编码构造。
As for the model of single node repair problem,Dimakis clarified the tradeoff between the node storage capacity and repair bandwidth by using information flow graph. In case of multiple-node recovery,Shum and Hu proposed the model of mutual cooperation among nodes to be repaired,and characterized the storage-bandwidth tradeoff. Zhang et al. introduced the new multi-node repaired model,in which the newcomers no longer exchanged data symbols among themselves. This new model reduced the complexity of design and operation,so it was more suitable for the demands of the actual system. For this new model,it used an easier way to find out the minimum capacity of the cut-set,and analyzed the theoretical bound on the storagebandwidth by using the method of linear programming. Finally,the regeneration codes were constructed for some special cases.
As for the model of single node repair problem,Dimakis clarified the tradeoff between the node storage capacity and repair bandwidth by using information flow graph. In case of multiple-node recovery,Shum and Hu proposed the model of mutual cooperation among nodes to be repaired,and characterized the storage-bandwidth tradeoff. Zhang et al. introduced the new multi-node repaired model,in which the newcomers no longer exchanged data symbols among themselves. This new model reduced the complexity of design and operation,so it was more suitable for the demands of the actual system. For this new model,it used an easier way to find out the minimum capacity of the cut-set,and analyzed the theoretical bound on the storagebandwidth by using the method of linear programming. Finally,the regeneration codes were constructed for some special cases.
引文
[1]Dimakis A G,Godfrey P B,Wu Yunnan,et al.Network coding for distributed storage systems[J].IEEE Trans on Information Theory,2010,56(9):4539-4551.
[2]Tamo I,Wang Zhiying,Bruck J.Zigzag codes:MDS array codes with optimal rebuilding[J].IEEE Trans on Information Theory,2013,59(3):1597-1616.
[3]Shah N B.On minimizing data-read and download for storage-node recovery[J].IEEE Communications Letters,2013,17(5):964-967.
[4]Tamo I,Wang Zhiying,Bruck J.Access versus bandwidth in codes for storage[J].IEEE Trans on Information Theory,2014,60(4):2028-2037.
[5]Agarwal G K,Sasidharan B,Kumar P V.An alternate construction of an access-optimal regenerating code with optimal sub-packetization level[C]//Proc of the 21st National Conference on Communications.2015:1-6.
[6]Li Jie,Tang Xiaohu,Parampalli U.A framework of constructions of minimal storage regenerating codes with the optimal access/update property[J].IEEE Trans on Information Theory,2015,61(4):1920-1932.
[7]Sasidharan B,Agarwal G K,Kumar P V.A high-rate MSR code with polynomial sub-packetization level[C]//Proc of International Symposium on Information Theory.2015:2051-2055.
[8]Hu Yuchong,Xu Yinlong,Wang Xiaozhao,et al.Cooperative recovery of distributed storage systems from multiple losses with network coding[J].IEEE Journal on Selected Areas in Communications,2010,28(2):268-276.
[9]Shum K W,Hu Yuchong.Cooperative regenerating codes[J].IEEE Trans on Information Theory,2013,59(11):7229-7258.
[10]Wang Anyu,Zhang Zhifang.Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[C]//Proc of IEEE INFOCOM.2013:400-404.
[11]Scouarnec N L.Exact scalar minimum storage coordinated regenerating codes[C]//Proc of International Symposium on Information Theory Proceeding.2012:1197-1201.
[12]Chen Junyu,Shum K W.Repairing multiple failures in the SuhRamchandran regenerating codes[C]//Proc of International Symposium on Information Theory Proceedings.2013:1441-1445.
[13]Li Jun,Li Baochun.Cooperative repair with minimum-storage regenerating codes for distributed storage[C]//Proc of IEEE INFOCOM.2014:316-324.
[14]Rawat A S,Koyluoglu O O,Vishwanath S.Centralized repair of multiple node failures with applications to communication efficient secret sharing[EB/OL].(2016-03-15)[2016-12-29].http://lanl.arxiv.org/abs/1603.04822.
[15]Zhang Huayu,Li Hui,Hou Hanxu,et al.Concurrent regenerating codes and scalable application in network storage[EB/OL].(2016-04-22)[2016-12-29].http://lanl.arxiv.org/abs/1604.06457.
[2]Tamo I,Wang Zhiying,Bruck J.Zigzag codes:MDS array codes with optimal rebuilding[J].IEEE Trans on Information Theory,2013,59(3):1597-1616.
[3]Shah N B.On minimizing data-read and download for storage-node recovery[J].IEEE Communications Letters,2013,17(5):964-967.
[4]Tamo I,Wang Zhiying,Bruck J.Access versus bandwidth in codes for storage[J].IEEE Trans on Information Theory,2014,60(4):2028-2037.
[5]Agarwal G K,Sasidharan B,Kumar P V.An alternate construction of an access-optimal regenerating code with optimal sub-packetization level[C]//Proc of the 21st National Conference on Communications.2015:1-6.
[6]Li Jie,Tang Xiaohu,Parampalli U.A framework of constructions of minimal storage regenerating codes with the optimal access/update property[J].IEEE Trans on Information Theory,2015,61(4):1920-1932.
[7]Sasidharan B,Agarwal G K,Kumar P V.A high-rate MSR code with polynomial sub-packetization level[C]//Proc of International Symposium on Information Theory.2015:2051-2055.
[8]Hu Yuchong,Xu Yinlong,Wang Xiaozhao,et al.Cooperative recovery of distributed storage systems from multiple losses with network coding[J].IEEE Journal on Selected Areas in Communications,2010,28(2):268-276.
[9]Shum K W,Hu Yuchong.Cooperative regenerating codes[J].IEEE Trans on Information Theory,2013,59(11):7229-7258.
[10]Wang Anyu,Zhang Zhifang.Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[C]//Proc of IEEE INFOCOM.2013:400-404.
[11]Scouarnec N L.Exact scalar minimum storage coordinated regenerating codes[C]//Proc of International Symposium on Information Theory Proceeding.2012:1197-1201.
[12]Chen Junyu,Shum K W.Repairing multiple failures in the SuhRamchandran regenerating codes[C]//Proc of International Symposium on Information Theory Proceedings.2013:1441-1445.
[13]Li Jun,Li Baochun.Cooperative repair with minimum-storage regenerating codes for distributed storage[C]//Proc of IEEE INFOCOM.2014:316-324.
[14]Rawat A S,Koyluoglu O O,Vishwanath S.Centralized repair of multiple node failures with applications to communication efficient secret sharing[EB/OL].(2016-03-15)[2016-12-29].http://lanl.arxiv.org/abs/1603.04822.
[15]Zhang Huayu,Li Hui,Hou Hanxu,et al.Concurrent regenerating codes and scalable application in network storage[EB/OL].(2016-04-22)[2016-12-29].http://lanl.arxiv.org/abs/1604.06457.