一类新的(k+2,k) Hadamard MSR码

张司娜; 唐小虎; 李杰

doi:10.3969/j.issn.0258-2724.2016.01.026

一类新的(k+2,k) Hadamard MSR码

doi: 10.3969/j.issn.0258-2724.2016.01.026

详细信息

作者简介:
张司娜(1985-),女,博士研究生,研究方向为分布式存储编码,E-mail:nsz1221@163.com

通讯作者:
唐小虎(1971-),男,教授,博士生导师,研究方向为信息安全与编码,E-mail:xhtang_scce@home.swjtu.edu.cn

计量
- 文章访问数: 896
- HTML全文浏览量: 93
- PDF下载量: 273
- 被引次数: 26
出版历程
- 收稿日期: 2015-02-01
- 刊出日期: 2016-01-25

A New (k+2, k) Hadamard Minimum Storage Regenerating Code

摘要

摘要: 为降低分布式存储系统中节点的存储量,构造了一类新(k+2, k)Hadamard MSR码.该码的每个编码矩阵皆对应于2个值,供其对角元素选取.在编码矩阵中,这2个值循环出现,且不同的矩阵,循环出现的周期不同.基于这一特性构造了节点的修复方案,将失效节点中的个数据分成/2组,每一组重建2个数据,其他k+1个节点为每一组各提供1个数据.证明了若新码编码矩阵的对角元素可取的2个值不相等,则可最优修复系统节点;若所有编码矩阵对角元素可取的2个值的和为同一不为0的值,则可最优修复第1个校验节点;若所有编码矩阵对角元素可取的2个值的逆的和为1,则可最优修复第2个校验节点.新码的节点存储量降低到了Hadamard MSR码的理论界,可最优修复任意系统节点和1个校验节点.
- 分布式 /
- 存储 /
- 再生码 /
- MSR码 /
- 高码率 /
- 最优 /
- 修复
Abstract: To reduce the storage capacity of nodes in distributed storage systems, a new (k+2, k) Hadamard Minimum Storage Regenerating (MSR) code was constructed. Each coding matrix is related to two values, from which the diagonal elements of this coding matrix are selected. These two values appear in the coding matrix in a repeating pattern, but with different repeating cycles for different matrices. Based on the structure of the coding matrix, a repair strategy was constructed. The repair strategy divides symbols in the failed node into /2 groups with two symbols in each group, then the two symbols are recovered by downloading one symbol from each of the other k+1 nodes. If the two values related to each coding matrix are unequal, the new Hadamard MSR code can optimally repair systematic nodes. If the sum of two values related to each coding matrix is nonzero and the k values are the same, the new Hadamard MSR code can optimally repair the first parity node. If the sum of the inverse of two values related to each coding matrix is one, the new Hadamard MSR code can optimally repair the second parity node. The new code reduces the storage capacity to the bond for Hadamard MSR code. Further, it can optimally repair all systematic nodes and one parity node.
- distributed /
- storage /
- regenerating code /
- MSR code /
- high code-rate /
- optimal /
- repair

HTML全文

参考文献(16)

RHEA S, WELLS C, EATON P, et al. Maintenance-free global data storage[J]. IEEE Internet Computing, 2001, 5(5): 40-49.

BHAGWAN R, TATI K, CHENG Y C, et al. Total recall: System support for automated availability management[C]//Symposium Networked Systems Design and Implementation. San Francisco: ACM, 2004: 25-25.

DABEK F, LI Jinyang, SIT E, et al. Designing a DHT for low latency and high throughput[C]//Symposium Networked Systems Design and Implementation (NSDI). San Francisco: ACM, 2004: 85-98

HUANG Cheng, SIMITCI H, XU Yi, et al. Erasure coding in windows azure storage[C]//Usenix annual Technical Conference. Boston: ACM, 2012: 15-26.

DIMAKIS A G, GODFREY P B, WU Yunnan, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539-4551.

范文礼,刘志刚. 基于传输效率矩阵的复杂网络节点重要度排序方法[J]. 西南交通大学学报,2014,49(2): 337-342. FAN Wenli, LIU Zhigang. Ranking method for node importance based on efficiency matrix[J]. Journal of Southwest Jiaotong University, 2014, 49(2): 337-342.

DIMAKIS A G, RAMCHANDRAN K, WU Yunnan, et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE, 2011, 99(3): 476-489.

郝杰,逯彦博,刘鑫吉,等. 分布式存储中的再生码综述[J]. 重庆邮电大学学报:自然科学版,2013,25(1): 30-38. HAO Jie, LU Yanbo, LIU Xinji, et al. Survey for regenerating codes for distributed storage[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2013, 25(1): 30-38.

PAPAILIOPOULOS D S, DIMAKIS A G, CADAMBE V R. Repair optimal erasure codes through hadamard designs[J]. IEEE Transactions on Information Theory, 2013, 59(5): 3021-3037.

TAMO I, WANG Zhiying, BRUCK J. Zigzag codes: MDS array codes with optimal rebuilding[J]. IEEE Transactions on Information Theory, 2013, 59(3): 1597-1616.

WANG Zhiying, TAMO I, BRUCK J. Long MDS codes for optimal repair bandwidth[C]//Proceedings of IEEE International Symposium on Information Theory. Cambridge: IEEE, 2012: 1182-1186.

TAMO I, WANG Zhiying, BRUCK J. MDS array codes with optimal rebuilding[C]//Proceedings of IEEE International Symposium on Information Theory. St. Petersburg: IEEE, 2011: 1240-1244.

CADAMBE V R, JAFAR S A, MALEKI H, et al. Asymptotic interference alignment for optimal repair of MDS codes in distributed storage[J]. IEEE Transactions on Information Theory, 2013, 59(5): 2974-2987.

CADAMBE V R, HUANG Cheng, LI Jin, et al. Polynomial length MDS codes with optimal repair in distributed storage[C]//The 45th Asilomar Conference on Signals, Systems and Computers (ASILOMAR).Pacific Grove: IEEE, 2011: 1850-1854.

CADAMBE V R, HUANG Cheng, LI Jin. Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems[C]//Proceedings of IEEE International Symposium on Information Theory Proceedings (ISIT).St. Petersburg: IEEE, 2011: 1225-1229.

TAMO I, WANG Zhiying, BRUCK J. Access versus bandwidth in codes for storage[J]. IEEE Transactions on Information Theory, 2014, 60(4): 2028-2037.

施引文献

期刊类型引用(11)

1.	周福林，李琦琦，杨瑞轩，熊进飞，李群湛. V/v接线牵引变压器高次谐波横向传递特性. 中国电机工程学报. 2020(01): 290-299+395 . 百度学术
2.	陈民武，田航，宋雅琳，陈玲. 基于变频控制策略的同相供电装置可靠性优化方法. 西南交通大学学报. 2020(01): 9-17 . 本站查看
3.	骆冰祥，解绍锋，李群湛，苏鹏. 牵引网谐振特性与治理方案. 电网技术. 2020(05): 1957-1963 . 百度学术
4.	王广慧，张利军. 车网系统谐波模型及谐振特性仿真研究. 控制与信息技术. 2020(06): 42-49 . 百度学术
5.	赵文胜，罗杰，崔召华，黄军. 高速铁路AT供电系统谐波谐振频率研究. 铁道标准设计. 2019(08): 145-150 . 百度学术
6.	杨颢，陈民武，盛望群，刘巍，解绍锋. 新型贯通同相供电系统建模与运行特性分析. 铁道科学与工程学报. 2018(08): 2131-2139 . 百度学术
7.	谭智杰. 浅谈供电系统信息通信综合网控室的建立策略. 通讯世界. 2017(04): 74-75 . 百度学术
8.	袁琳. 高速铁路牵引变电所电源故障后的应急供电对策. 中小企业管理与科技(下旬刊). 2017(02): 173-174 . 百度学术
9.	乔沈楠. 高校供电系统的分析与节能的措施. 科学家. 2016(04): 79+81 . 百度学术
10.	赵元哲，李群湛，周福林. 基于阻波高通滤波器的高速铁路谐振抑制方案. 电力自动化设备. 2015(04): 139-144 . 百度学术
11.	赵元哲，李群湛，周福林，朱鹏. 牵引网高次谐波对高低压三相系统的渗透特性. 西南交通大学学报. 2015(05): 961-969 . 本站查看