Distributed storage plays a crucial role in the current cloud computing framework. After the theoretical bound for distributed storage was derived by the pioneer work of the regenerating code, Reed-Solomon code based regenerating codes were developed. The RS code based minimum storage regeneration code (RS-MSR) and the minimum bandwidth regeneration code (RS-MBR) can achieve theoretical bounds on the MSR point and the MBR point respectively in code regeneration. They can also maintain the MDS property in code reconstruction. However, in the hostile network where the storage nodes can be compromised and the packets can be tampered with, the storage capacity of the network can be significantly affected. In this paper, we propose a Hermitian code based minimum storage regenerating (H-MSR) code and a minimum bandwidth regenerating (H-MBR) code. We first prove that our proposed Hermitian code based regenerating codes can achieve the theoretical bounds for MSR point and MBR point respectively. We then propose data regeneration and reconstruction algorithms for the H-MSR code and the H-MBR code in both error-free network and hostile network. Theoretical evaluation shows that our proposed schemes can detect the erroneous decodings and correct more errors in hostile network than the RS-MSR code and the RS-MBR code with the same code rate. Our analysis also demonstrates that the proposed H-MSR and H-MBR codes have lower computational complexity than the RS-MSR RS-MBR codes in both code regeneration and code reconstruction.
When a storage node in the distributed storage network that employing the conventional @math RS code (such as OceanStore @cite_0 and Total Recall @cite_2 ) fails, the replacement node connects to @math nodes and downloads the whole file to recover the symbols stored in the failed node. This approach is a waste of bandwidth because the whole file has to be downloaded to recover a fraction of it. To overcome this drawback, Dimakis @cite_3 introduced the concept of @math regenerating code. In the context of regenerating code, the replacement node can regenerate the contents stored in a failed node by downloading @math help symbols from @math helper nodes. The bandwidth consumption to regenerate a failed node could be far less than the whole file. A data collector (DC) can reconstruct the original file stored in the network by downloading @math symbols from each of the @math storage nodes. @cite_3 , the authors proved that there is a tradeoff between bandwidth @math and per node storage @math . They find two optimal points: minimum storage regeneration (MSR) and minimum bandwidth regeneration (MBR) points.
@cite_0 @cite_3 @cite_2
2951975749 2606114015 1998021782 2582914554
We consider the setting of data storage across n nodes in a distributed manner. A data collector (DC) should be able to reconstruct the entire data by connecting to any k out of the n nodes and downloading all the data stored in them. When a node fails, it has to be regenerated back using the existing nodes. In a recent paper, have obtained an information theoretic lower bound for the repair bandwidth. Also, there has been additional interest in storing data in systematic form as no post processing is required when DC connects to k systematic nodes. Because of their preferred status there is a need to regenerate back any systematic node quickly and exactly. Replacement of a failed node by an exact replica is termed Exact Regeneration.In this paper, we consider the problem of minimizing the repair bandwidth for exact regeneration of the systematic nodes. The file to be stored is of size B and each node can store alpha = B k units of data. A failed systematic node is regenerated by downloading beta units of data each from d existing nodes. We give a lower bound for the repair bandwidth for exact regeneration of the systematic nodes which matches with the bound given by For d >= 2k-1 we give an explicit code construction which minimizes the repair bandwidth when the existing k-1 systematic nodes participate in the regeneration. We show the existence and construction of codes that achieve the bound for d >= 2k-3. Here we also establish the necessity of interference alignment. We prove that the bound is not achievable for d = 2k-1. Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an @math - @math MSR code @math over @math stores a file @math consisting of @math symbols over @math among @math nodes, each storing @math symbols, in such a way that: 1) the file @math can be recovered by downloading the content of any @math of the @math nodes and 2) the content of any failed node can be reconstructed by accessing any @math of the remaining @math nodes and downloading @math symbols from each of these nodes. In practice, the file @math is typically available in uncoded form on some @math of the @math nodes, known as systematic nodes , and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only . Such codes are called systematic–repair MSR codes . Unfortunately, finite– @math constructions of @math MSR codes are known only for certain special cases: either low rate, namely @math , or high repair connectivity, namely @math . Our main result in this paper is a finite– @math construction of systematic-repair @math MSR codes for all possible values of parameters @math . We also introduce a generalized construction for @math MSR codes to achieve the optimal repair bandwidth for all values of @math simultaneously. We consider a distributed storage system employing some existing regenerate codes where the storage nodes are scattered in a wireless network. The data collector connects to the storage nodes via orthogonal channels and downloads data symbols from these nodes. In the existing data reconstruction schemes for distributed storage systems, the data collector downloads all symbols from a subset of the storage nodes. Such a full-downloading approach becomes inefficient in wireless networks since due to fading, the wireless channels may not offer sufficient bandwidths for full downloading. Moreover, full-downloading is also less power efficient than partial downloading. In this paper, given a coding scheme employed by the wireless distributed storage system, we propose a partial downloading scheme that allows downloading a portion of the symbols from any storage node. We formulate a cross-layer wireless resource allocation problem for data reconstruction in distributed storage systems employing such partial downloading. To derive the fundamental properties of partial downloading as well as to reduce the complexity of wireless resource allocation, we derive necessary and sufficient conditions for data reconstructability for partial downloading, in terms of the numbers of downloaded symbols from the storage nodes. We also propose channel and power allocation schemes for partial downloading in wireless distributed storage systems. Simulation results are provided to demonstrate the significant power savings by the proposed partial downloading scheme compared to the full-downloading methods for distributed storage. We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are @math clusters in total, with @math nodes per cluster. A data file is coded and stored across the @math nodes, with each node storing @math symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of @math clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading @math symbols each from any set of @math other clusters, dubbed remote helper clusters, and also up to @math symbols each from any set of @math surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever @math . We then obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Under functional repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes @math in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing @math not only increases intra-cluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions.