RS regenerating codes for cloud storage fault-tolerant system

RS(Reed-Solomon) regenerating erasure codes was proposed for cloud storage fault-tolerant system,which not only inherited the reliability of the RS encoding,but also achieved the high efficiency of tolerance three faults.Hybrid recovery method of the single fault node based on RS regenerating erasure codes was introduced.And the theoretical lower bound of the number of accessing disks was computed.In theory,the performance evaluation of the storage overhead,decoding efficiency,and repair bandwidth of the RS regenerating erasure codes was carried out.Experiments results show that the repair performance of RS regenerating erasure codes is improved greatly than the similar erasure codes,and the total recovery time of the system is reduced by 20.8%~28.2% using hybrid recovery algorithm in the case of single fault.     

基于再生码的云存储系统——Ustor

摘 要：Ustor是一个构建在多个商业云存储服务之上的云存储系统,它旨在保证数据可靠性的同时减少单点失效时占用的修复带宽。不同于将所有数据存储在单个云中,Ustor将数据编码后分布在多个云存储系统中保证可靠性。Ustor的编码模块部署了包括Reed-Solomon码和功能性修复再生码（FRC）在内的多种纠删码,是第一个将功能性修复再生码应用于多个异构的、真实的云存储系统中的应用。与传统的冗余编码比较,FRC显著地减少了单个云存储发生数据丢失时需要从网络上传输的数据量。实验表明：与不编码比较,冗余编码给系统增加了5%~10%的响应时间开销,但可保障节点失效;FRC码编、解码和修复速度与Reed-Solomon码基本相当,256 MB大小文件编码时间差距在0.5 s以内;FRC码修复时与传统的Reed-Solomon码相比减少了25%以上需要下载的数据量。     

Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding

This paper studies the recovery from multiple node failures in distributed storage systems. We design a mutually cooperative recovery (MCR) mechanism for multiple node failures. Via a cut-based analysis of the information flow graph, we obtain a lower bound of maintenance bandwidth based on MCR. For MCR, we also propose a transmission scheme and design a linear network coding scheme based on (η, κ) strong-MDS code, which is a generalization of (η, κ) MDS code. We prove that the maintenance bandwidth based on our transmission and coding schemes matches the lower bound, so the lower bound is tight and the transmission scheme and coding scheme for MCR are optimal. We also give numerical comparisons of MCR with other redundancy recovery mechanisms in storage cost and maintenance bandwidth to show the advantage of MCR.     

Improving reliability of erasure codes‐based storage paradigm under correlated failures for wireless sensor networks

In distributed sensor networks, ensuring data availability and reliability in the presence of node failures and malicious attacks is an important requirement. Traditionally, redundant schemes such as erasure codes and network coding are used to improve storage efficiency. However, prior works do not consider the scenario that node failures might cut the network into multiple components and result in unsuccessful data reconstruction. To address this problem, we first devise a data segment distribution scheme that enables randomly connected component of remaining network to have enough data symbols to recreate the initial data. Because the optimal symbol distribution is Nondeterministic Polynomial (NP)‐complete problem, we further propose an approximation solution to solve it for arbitrary network model. Second, an efficient data recovery scheme with integrity check is proposed to reconstruct the initial data and repair the data saved on the disabled nodes in case of Byzantine failures. Compared with the previous approaches, the proposed scheme benefits from low data loss and storage overhead, which is confirmed by evaluations. Copyright © 2015 John Wiley & Sons, Ltd.     

Design of exact regenerating hierarchical code for distributed storage system

Erasure code is widely used as the redundancy scheme in distributed storage system. When a storage node fails, the repair process often requires to transfer a large amount of data. Regenerating code and hierarchical code are two classes of codes proposed to reduce the repair bandwidth cost. Regenerating codes reduce the amount of data transferred by each helping node, while hierarchical codes reduce the number of nodes participating in the repair process. In this paper, we propose a "sub-code nesting framework" to combine them together. The resulting regenerating hierarchical code has low repair degree as hierarchical code and lower repair cost than hierarchical code. Our code can achieve exact regeneration of the failed node, and has the additional property of low updating complexity.     

云灾备的数据修复技术

基于纠错码的云灾备系统的关于降低修复带宽的最新研究成果,文章讨论了云灾备系统中存储节点失效的修复问题。文章指出数据修复问题有3种模型:精确修复、功能修复和系统部分精确修复。在精确修复中,失效的模块需要修复精确的丢失编码包;在功能修复中,新产生的编码包可以包含不同于丢失节点的数据,只要修复的云灾备系统支持最大可分离距离(MDS)码属性。系统部分精确修复是精确修复和部分修复的之间的一个混合的修复模型。     

“双码”架构下的云存储多节点修复协作编码

针对云存储中现有多节点失效修复模型的不足,给出了一种可以对多个系统节点或冗余节点同时修复的多节点协作的精确修复码,证明了其存在性,并且将此修复码与具有健康节点协作的MDS双码架构模型相结合,以达到对多节点修复的同时,降低修复带宽、修复链路数和单个中间节点需要处理的数据量。通过数值仿真结果表明,本模型与修复方案在以上3个方面具有较大改进,尤其削弱了修复时中间节点的负荷,且随着云存储中节点数量的增多,本方案的优势更加明显。     

容许多个磁盘故障的RAID编码方法研究

随着磁盘阵列规模的增大,同时发生多个磁盘故障的概率将大大增加,单容错编码难以满足应用对高可靠性存储的需求.分析了主要的双容错RAID编码方法及其特点,对各种双容错编码方法的冗余性能进行了比较.给出了一种基于循环置换矩阵构建的能容许三个磁盘故障的MDS交换群阵列码,其编码和解码效率较高,是大规模RAID存储系统的应用方向.     

一种三容错数据布局

随着存储介质的增多,单容错、双容错的数据布局方案已经无法满足现有分布式存储系统对可靠性要求。该文在双容错行对角奇偶校验(Row Diagonal Parity, RDP)码的基础上,提出一种新的扩展行对角奇偶校验 (Extending Row Diagonal Parity, E-RDP)码,能够容许任何3存储节点出错,具有最大距离可分(Maximum Distance Separable, MDS)编码特性,冗余率与纠错能力达到3容错编码最优。并采用不同斜率几何直线图描述编译码过程,给出了一种快速译码算法,易于软硬件实现。与其它纠删码数据布局方案进行比较,理论分析结果表明,E-RDP码的空间利用率、编译码效率、小写性能以及平衡性的综合性能达到最优,具有实用价值。     

An information-theoretic view of network management

We present an information-theoretic framework for network management for recovery from nonergodic link failures. Building on recent work in the field of network coding, we describe the input-output relations of network nodes in terms of network codes. This very general concept of network behavior as a code provides a way to quantify essential management information as that needed to switch among different codes (behaviors) for different failure scenarios. We compare two types of recovery schemes, receiver-based and network-wide, and consider two formulations for quantifying network management. The first is a centralized formulation where network behavior is described by an overall code determining the behavior of every node, and the management requirement is taken as the logarithm of the number of such codes that the network may switch among. For this formulation, we give bounds, many of which are tight, on management requirements for various network connection problems in terms of basic parameters such as the number of source processes and the number of links in a minimum source-receiver cut. Our results include a lower bound for arbitrary connections and an upper bound for multitransmitter multicast connections, for linear receiver-based and network-wide recovery from all single link failures. The second is a node-based formulation where the management requirement is taken as the sum over all nodes of the logarithm of the number of different behaviors for each node. We show that the minimum node-based requirement for failures of links adjacent to a single receiver is achieved with receiver-based schemes.     

Very low rate trellis/Reed-Muller (TRM) codes

This paper considers a technique for very low rate channel coding. The main application for such codes is in spread-spectrum systems where significant bandwidth spreading is possible. New, very low rate binary channel codes based on a combination of a trellis code with a first-order Reed-Muller block code (trellis/Reed-Muller (TRM) codes) are presented. The construction technique for TRM codes, which is considered in this paper, is related to Kerdock (1972) codes. It is shown that these TRM codes provide a better tradeoff between rate and gain than other existing very low rate codes, such as the orthogonal or superorthogonal convolutional codes, and the IS-95 uplink code. Due to their improved performance, TRM codes can significantly increase the bandwidth efficiency of spread-spectrum multiple-access systems     

基于可分组设计的部分重复码研究

针对最小带宽再生情形下的有效修复问题,提出了一种新型部分重复(FR,fractional repetition)码设计。该设计由外部最大距离可分(MDS,maximum distance separable)码和内部重复码组成,称为GDDBFR(group divisible design based FR)码,可以达到随机访问模式下的系统存储容量,并且能够在很大范围内选择构造参数。理论分析指出,尽管GDDBFR码采用基于表格的修复方式,但通常具有大量的节点修复选择方案。此外,实验结果表明,与传统的RS(Reed-Solomon)码和再生码相比,GDDBFR码可以显著地减少失效修复时间。     

基于差集矩阵的部分重复码构造

针对最小带宽再生码的有效修复问题,该文提出一种基于差集矩阵的部分重复(FR)码的构造算法。利用差集矩阵和克罗内克(Kronecker)和来构造正交排列,根据正交排列每一列取相同元素所在行作为节点的编码块,得到相应的FR码。构造的FR码可以划分成多个平行类,同时还能调整数据块的重复度和节点的存储容量。仿真结果表明,与传统的里德-所罗门(RS)码和简单再生码(SRC)相比,构造的FR码在修复复杂度、修复带宽开销和修复局部性方面具有更好的性能,修复选择度上虽然是基于表格的修复方案,但选择度依旧可以达到很高。     

Network coding based on hyper‐edge decomposition for wireless network with link failures

This paper is concerned with the construction of network coding for wireless network with link failures. Based on hyper‐edge decomposition, for the wireless network, we first construct the hyper‐edge graph, where each node represents one hyper‐edge (consisting of multiple adjacent edges transmitting the same information) of the wireless network. Then we present a heuristic coloration method for the hyper‐edge graph, and a network coding vector allocation scheme based on maximum distance separable code is proposed to effectively overcome some link failures. Copyright © 2014 John Wiley & Sons, Ltd.     

LOW RATE SPACE-TIME TRELLIS CODES INPOWER LIMITED WIRELESSCOMMUNICATION SYSTEMS

Space-time trellis codes can achieve the best tradeoff among bandwidth efficiency, diversity gain, constellation size and trellis complexity. In this paper, some optimum low rate space-time trellis codes are proposed. Performance analysis and simulation show that the low rate space-time trellis codes outperform space-time block codes concatenated with convolutional code at the same bandwidth efficiency, and are more suitable for the power limited wireless communication system.     

Progressive transmission of images over memoryless noisy channels

An embedded source code allows the decoder to reconstruct the source progressively from the prefixes of a single bit stream. It is desirable to design joint source-channel coding schemes which retain the capability of progressive reconstruction in the presence of channel noise or packet loss. Here, we address the problem of joint source-channel coding of images for progressive transmission over memoryless bit error or packet erasure channels. We develop a framework for encoding based on embedded source codes and embedded error correcting and error detecting channel codes. For a target transmission rate, we provide solutions and an algorithm for the design of optimal unequal error/erasure protection. Three performance measures are considered: the average distortion, the average peak signal-to-noise ratio, and the average useful source coding rate. Under the assumption of rate compatibility of the underlying channel codes, we provide necessary conditions for progressive transmission of joint source-channel codes. We also show that the unequal error/erasure protection policies that maximize the average useful source coding rate allow progressive transmission with optimal unequal protection at a number of intermediate rates     

Distributed Joint Source-Channel Coding of Video Using Raptor Codes

Extending recent works on distributed source coding, this paper considers distributed source-channel coding and targets at the important application of scalable video transmission over wireless networks. The idea is to use a single channel code for both video compression (via Slepian-Wolf coding) and packet loss protection. First, we provide a theoretical code design framework for distributed joint source-channel coding over erasure channels and then apply it to the targeted video application. The resulting video coder is based on a cross-layer design where video compression and protection are performed jointly. We choose Raptor codes - the best approximation to a digital fountain - and address in detail both encoder and decoder designs. Using the received packets together with a correlated video available at the decoder as side information, we devise a new iterative soft-decision decoder for joint Raptor decoding. Simulation results show that, compared to one separate design using Slepian-Wolf compression plus erasure protection and another based on FGS coding plus erasure protection, the proposed joint design provides better video quality at the same number of transmitted packets. Our work represents the first in capitalizing the latest in distributed source coding and near-capacity channel coding for robust video transmission over erasure channels.     

Practical algorithms for tornado codes

Tornado codes have been used in the error control of data transmission in IP network. The efficiency of this erasure codes is critically affected by the short cycles in its bipartite graph. To remove this effect, two algorithms are introduced： （1） while generating the graph, the cycle eliminating algorithm is used to reduce the number of the short cycles in it; （2） in the decoding algorithm, cycles that are inevitably in the graph are used to remove decoding efficiency degradation. The simulation results show that they have a better performance than that of general tornado codes.     

Generalized LDPC codes and generalized stopping sets

A generalized low-density parity check code (GLDPC) is a low-density parity check code in which the constraint nodes of the code graph are block codes, rather than single parity checks. In this paper, we study GLDPC codes which have BCH or Reed-Solomon codes as subcodes under bounded distance decoding (BDD). The performance of the proposed scheme is investigated in the limit case of an infinite length (cycle free) code used over a binary erasure channel (BEC) and the corresponding thresholds for iterative decoding are derived. The performance of the proposed scheme for finite code lengths over a BEC is investigated as well. Structures responsible for decoding failures are defined and a theoretical analysis over the ensemble of GLDPC codes which yields exact bit and block error rates of the ensemble average is derived. Unfortunately this study shows that GLDPC codes do not compare favorably with their LDPC counterpart over the BEC. Fortunately, it is also shown that under certain conditions, objects identified in the analysis of GLDPC codes over a BEC and the corresponding theoretical results remain useful to derive tight lower bounds on the performance of GLDPC codes over a binary symmetric channel (BSC). Simulation results show that the proposed method yields competitive performance with a good decoding complexity trade-off for the BSC.     

无线通信系统中的低码率空时网格码

空时网格编码能在频带利用率、分集增益、调制方式与编码网络图复杂度之间达到最佳的折衷。本文给出了几种低码率空时网格码的好码。理论分析和系统仿真表明,在相同的频带利用率下,该空时网格码可具有比空时块码级联卷积码具有更好的误码率性能,更适合于对频带利用率要求不高的功率受限无线通信系统。