Vis enkel innførsel

dc.contributor.advisorØverby, Harald
dc.contributor.authorKralevska, Katina
dc.date.accessioned2017-01-02T12:27:17Z
dc.date.available2017-01-02T12:27:17Z
dc.date.issued2016
dc.identifier.isbn978-82-326-2023-4
dc.identifier.issn1503-8181
dc.identifier.urihttp://hdl.handle.net/11250/2425979
dc.description.abstractThe 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 systemsnb_NO
dc.language.isoengnb_NO
dc.publisherNTNUnb_NO
dc.relation.ispartofseriesDoctoral theses at NTNU;2016:341
dc.relation.haspartPaper 1: Kralevska, Katina; Gligoroski, Danilo; Øverby, Harald. Balanced XOR-ed Coding. Lecture Notes in Computer Science 2013 ;Volum 8115. s. 161-172 The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-40552-5_15
dc.relation.haspartPaper 2: Gligoroski, Danilo; Kralevska, Katina. Families of Optimal Binary Non-MDS Erasure Codes. I: IEEE Proceedings on International Symposium on Information Theory (ISIT). IEEE conference proceedings 2014, s. 3150-3154. © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/10.1109/ISIT.2014.6875415
dc.relation.haspartPaper 3: Gligoroski, Danilo; Kralevska, Katina; Øverby, Harald. Minimal Header Overhead for Random Linear Network Coding. I: IEEE International Conference on Communication, ICC 2015, Workshop Proceedings. IEEE Communications Society 2015, s. 680-685 © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/10.1109/ICCW.2015.7247260
dc.relation.haspartPaper 4: Kralevska, Katina; Gligoroski, Danilo; Øverby, Harald. General Sub-Packetized Access-Optimal Regenerating Codes. IEEE Communications Letters 2016 ;Volum 20.(7) s. 1281-1284 © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/10.1109/LCOMM.2016.2561287
dc.relation.haspartPaper 5: HashTag Erasure Codes: From Theory to Practice K. Kralevska, D. Gligoroski, R. E. Jensen, and H. Øverby. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
dc.relation.haspartPaper 6: Balanced Locally Repairable Codes K. Kralevska, D. Gligoroski, and H. Øverby. International Symposium on Turbo Codes and Iterative Information Processing, 2016, © 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/ 10.1109/ISTC.2016.7593121
dc.relation.haspartPaper 7: Kralevska, Katina; Øverby, Harald; Gligoroski, Danilo. Coded Packet Transport for Optical Packet/Burst Switched Networks. I: 2015 IEEE Global Communications Conference (GLOBECOM). IEEE Press 2015 © 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Published version available at http://dx.doi.org/10.1109/GLOCOM.2015.7417372
dc.titleApplied Erasure Coding in Networks and Distributed Storagenb_NO
dc.typeDoctoral thesisnb_NO
dc.subject.nsiVDP::Technology: 500::Information and communication technology: 550::Telecommunication: 552nb_NO


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel