Raptor Codes on Binary Memoryless Symmetric Channels

In this paper, we will investigate the performance of Raptor codes on arbitrary binary input memoryless symmetric channels (BIMSCs). In doing so, we generalize some of the results that were proved before for the erasure channel. We will generalize the stability condition to the class of Raptor codes. This generalization gives a lower bound on the fraction of output nodes of degree 2 of a Raptor code if the error probability of the belief- propagation decoder converges to zero. Using information-theoretic arguments, we will show that if a sequence of output degree distributions is to achieve the capacity of the underlying channel, then the fraction of nodes of degree 2 in these degree distributions has to converge to a certain quantity depending on the channel. For the class of erasure channels this quantity is independent of the erasure probability of the channel, but for many other classes of BIMSCs, this fraction depends on the particular channel chosen. This result has implications on the "universality" of Raptor codes for classes other than the class of erasure channels, in a sense that will be made more precise in the paper. We will also investigate the performance of specific Raptor codes which are optimized using a more exact version of the Gaussian approximation technique.

Raptor codes on symmetric channels

Seyed Omid Etesami, Mehdi Molkaraie, Mohammad Amin Shokrollahi

This paper extends the construction and analysis of Raptor codes originally designed in A. Shokrollahi (2004) for the erasure channel to general symmetric channels. We explicitly calculate the asymptotic fraction of output nodes of degree one and two for capacity-achieving Raptor codes, and discuss techniques to optimize the output degree distribution.

2004

Network Coding

Mahdi Jafari Siavoshani

The demand for higher throughput and better efficiency are two important challenges for future communication networks. During the past decades, a lot of research studies have been devoted to investigating and proposing near optimal and efficient schemes and algorithms for point-to-point communication. However, in communication networks, especially in wireless systems, we require more intricate algorithms and coding schemes that are optimized for networks rather than for point-to-point communications. In recent years, the network coding paradigm has opened new opportunities for network information flow algorithms. In the first part of the thesis, we consider a non-coherent transmission scenario in a network performing randomized linear network coding. Our main goal is to find the optimal performance in terms of communication rate in such a transmission scenario and to discover the optimal coding scheme to achieve it. It is observed by Koetter et al. [1] that because the network performs an unknown linear transformation, coding over subspaces spanned by the source packets could be a reasonable coding scheme. In order to make this claim information-theoretically justified, we study a multiplicative matrix channel over a finite field with a uniform and independent distribution over the transfer matrix. The capacity for this unicast communication scenario is characterized and it is shown that coding over subspaces is indeed optimal. A similar result is also derived for the two users multiple access problem in such a non-coherent network coding scenario. We then generalize this model by proposing a more universal scenario which is based on an arbitrarily varying channel approach. This result shows the optimality of subspace coding for a wider class of matrix channels, i.e., the channels where only the rank distribution of the transfer matrix is known. Moreover, the above results show that the overhead of schemes based on coding vectors is negligible for many practical situations, i.e., the situations where the rank of the transfer matrix is concentrated around some integer number. Next, we observe that in a network performing randomized linear network coding, the coding vectors carry topological and state-dependent information about the network. Considering the subspaces spanned by the coding vectors at the relay nodes of the network, we investigate the properties of these subspaces and leverage them for some practical problems including network tomography, network management, and Byzantine attack detection. In the last part of the thesis, we consider the problem of secret key sharing among multiple nodes in a network, in the presence of a passive eavesdropper. We assume that there exists a broadcast channel from one of the trusted nodes to the rest of them (including the eavesdropper). Moreover, we assume that the trusted entities can discuss over a public channel overheard by everyone. The secrecy key generation capacity for this problem is still unknown (in general, there exist only some upper and lower bounds). For the erasure broadcast channel as well as the linear deterministic wireless broadcast channel, we propose optimal and efficient schemes that enable arbitrary number of legitimate entities to share a secret key among themselves. By extending these results, we propose achievability schemes for the non-coherent network coding broadcast channel and the state-dependent Gaussian wireless broadcast channel.

EPFL2012

Reliability Analysis of Data Storage Systems

Vinodh Venkatesan

Modern data storage systems are extremely large and consist of several tens or hundreds of nodes. In such systems, node failures are daily events, and safeguarding data from them poses a serious design challenge. The focus of this thesis is on the data reliability analysis of storage systems and, in particular, on the effect of different design choices and parameters on the system reliability. Data redundancy, in the form of replication or advanced erasure codes, is used to protect data from node failures. By storing redundant data across several nodes, the surviving redundant data on surviving nodes can be used to rebuild the data lost by the failed nodes if node failures occur. As these rebuild processes take a finite amount of time to complete, there exists a nonzero probability of additional node failures during rebuild, which eventually may lead to a situation in which some of the data have lost so much redundancy that they become irrecoverably lost from the system. The average time taken by the system to suffer an irrecoverable data loss, also known as the mean time to data loss (MTTDL), is a measure of data reliability that is commonly used to compare different redundancy schemes and to study the effect of various design parameters. The theoretical analysis of MTTDL, however, is a challenging problem for non-exponential real-world failure and rebuild time distributions and for general data placement schemes. To address this issue, a methodology for reliability analysis is developed in this thesis that is based on the probability of direct path to data loss during rebuild. The reliability analysis is detailed in the sense that it accounts for the rebuild times involved, the amounts of partially rebuilt data when additional nodes fail during rebuild, and the fact that modern systems use an intelligent rebuild process that will first rebuild the data having the least amount of redundancy left. Through rigorous arguments and simulations it is established that the methodology developed is well-suited for the reliability analysis of real-world data storage systems. Applying this methodology to data storage systems with different types of redundancy, various data placement schemes, and rebuild constraints, the effect of the design parameters on the system reliability is studied. When sufficient network bandwidth is available for rebuild processes, it is shown that spreading the redundant data corresponding to the data on each node across a higher number of other nodes and using a distributed and intelligent rebuild process will improve the system MTTDL. In particular, declustered placement, which corresponds to spreading the redundant data corresponding to each node equally across all other nodes of the system, is found to potentially have significantly higher MTTDL values than other placement schemes, especially for large storage systems. This implies that more reliable data storage systems can be designed merely by changing the data placement without compromising on the storage efficiency or performance. The effect of a limited network rebuild bandwidth on the system reliability is also analyzed, and it is shown that, for certain redundancy schemes, spreading redundant data across more number of nodes can actually have a detrimental effect on reliability. It is also shown that the MTTDL values are invariant in a large class of node failure time distributions with the same mean. This class includes the exponential distribution as well as the real-world distributions, such as Weibull or gamma. This result implies that the system MTTDL will not be affected if the failure distribution is changed to a corresponding exponential one with the same mean. This observation is also of great importance because it suggests that the MTTDL results obtained in the literature by assuming exponential node failure distributions may still be valid for real-world storage systems despite the fact that real-world failure distributions are non-exponential. In contrast, it is shown that the MTTDL is sensitive to the node rebuild time distribution. A storage system reliability simulator is built to verify the theoretical results mentioned above. The simulator is sufficiently complex to perform all required failure events and rebuild tasks in a storage system, to use real-world failure and rebuild time distributions for scheduling failures and rebuilds, to take into account partial rebuilds when additional node failures occur, and to simulate different data placement schemes and compare their reliability. The simulation results are found to match the theoretical predictions with high confidence for a wide range of system parameters, thereby validating the methodology of reliability analysis developed.

EPFL2012

Reliability Analysis of Data Storage Systems

Vinodh Venkatesan

EPFL2012

Network Coding

Mahdi Jafari Siavoshani

EPFL2012