Applied Erasure Coding in Networks and Distributed Storage

The amount of digital data is rapidly growing. There is an increasing use of a wide range of computer systems, from mobile devices to largescale data centers, and important for reliable operation of all computer systems is mitigating the occurrence and the impact of errors in digital data. The demand for new ultra-fast and highly reliable coding techniques for data at rest and for data in transit is a major research challenge. Reliability is one of the most important design requirements. The simplest way of providing a degree of reliability is by using data replication techniques. However, replication is highly inefficient in terms of capacity utilization. Erasure coding has therefore become a viable alternative to replication since it provides the same level of reliability as replication with significantly less storage overhead. The present thesis investigates efficient constructions of erasure codes for different applications. Methods from both coding and information theory have been applied to network coding, Optical Packet Switching (OPS) networks and distributed storage systems. The following four issues are addressed: • Construction of binary and non-binary erasure codes; • Reduction of the header overhead due to the encoding coefficients in network coding; • Construction and implementation of new erasure codes for largescale distributed storage systems that provide savings in the storage and network resources compared to state-of-the-art codes; and • Provision of a unified view on Quality of Service (QoS) in OPS networks when erasure codes are used, with the focus on Packet Loss Rate (PLR), survivability and secrecy. A major part of the present thesis is the study of both theoretical and practical aspects of code constructions for distributed storage systems. Distributed storage systems typically employ commodity hardware, often mounted in racks, so that the system can be scaled at a low cost. The components may suffer from failures and other factors, such as software glitches and machine reboots during maintenance operations, that result in unavailability of the stored data. The reliability provided by 3-replication is an accepted industry standard for incorporating reliability into storage systems. Nevertheless, the relentless data growth has made erasure coding a valuable alternative to 3-replication, and hence many distributed storage systems such as Hadoop Distributed File System (HDFS), OpenStack SWIFT and Microsoft Azure employ Reed-Solomon (erasure) codes. New metrics for efficient erasure coding solutions have been identified in the literature. Some of these metrics, that are also studied in the present thesis, include: 1) reliability, 2) storage efficiency, 3) repair bandwidth, 4) disk-I/O, 5) repair locality, and 6) update complexity. Each of these metrics has a different relevance to a specific system depending on the system’s architecture and the workload. In the present thesis, we propose two novel constructions of erasure codes for distributed storage. The first construction is called HashTag Erasure Codes (HTECs). HTECs are storage-reliability optimal meaning that they offer maximum fault tolerance for the consumed storage. HTECs are the first codes in the literature that reduce the repair bandwidth for both single and multiple failures for an arbitrary sub-packetization level. The bandwidth savings can go up to 70% and 30% compared to RS codes for single and double failures, respectively. HTECs address also the practical problem of disk I/O operations with the focus on reducing the number of random operations that access locations on the storage devices in a non-contiguous manner. The second construction of erasure codes belongs to the class of Locally Repairable Codes (LRCs). The proposed Balanced Locally Repairable Codes (BLRCs) are suitable for applications that require a low repair locality for single and double failures, low storage overhead, high reliability and low update complexity. The present thesis therefore provides new code constructions and demonstrates how these codes are applied to network coding, OPS networks and distributed storage system