MASARYK UNIVERSITY FACULTY OF INFORMATICS Forward error correction for storage applications BACHELOR'S THESIS Michal Virgovič Brno, Spring 2018 MASARYK UNIVERSITY FACULTY OF INFORMATICS Forward error correction for storage applications BACHELOR'S THESIS Michal Virgovič Brno, Spring 2018 This is where a copy of the official signed thesis assignment and a copy of the Statement ofan Author is located in the printed version of the document. Declaration Hereby I declare that this paper is my original authorial work, which I have worked out on my own. A l l sources, references, and literature used or excerpted during elaboration of this work are properly cited and listed in complete reference to the due source. Michal Virgovič Advisor: Ing. Milan Brož i Acknowledgements Foremost, I would like to express my sincere gratitude to my advisor for the continuous support, guidance and the opportunity to work on this project. Secondly, I would like to thank my family for their support and patience. Finally, I would like to thank the developers of open-source l i braries mentioned in this thesis without which this work wouldn't be possible. iii Abstract Forward error correction algorithms are a vital element of many storage systems that require insurance of the reliability of data. These algorithms are based on various mathematical theories, and they are useful for different applications. They can use complex arithmetic operations like multiplication in Galois field or simple operations like XOR. A l l these factors contribute to the fact that the performances of these algorithms differ. Because storage is a crucial commodity of information society and the assurance of the integrity of data is essential, there is a high demand for algorithms that can ensure the data integrity aside from mirroring, which is not space-optimal. This demand is a reason why many open-source libraries emerged from different sources and back- grounds. In this work, we describe the basics on which these algorithms stand. We choose the most used codes in applications to explain the current situation of the theory. Then, we analyze the performance of these codes implemented by several libraries. Finally, we present our results of performance and discuss them along with other properties of these codes. iv Keywords forward error correction, erasure codes, storage, RAID, Ceph, ReedSolomon, Low-density parity-check, Veritysetup v Contents 1 Introduction 1 1.1 Goals 2 1.2 Scope of the thesis 3 2 Storage and errors 5 2.1 RAID 5 2.1.1 RAID levels 5 2.1.2 RAID issues 6 2.2 Object-storage systems 7 2.2.1 Ceph 7 2.3 Errors 8 2.3.1 Soft errors 8 2.3.2 Hard errors 9 2.4 Bit-errors and security 9 3 Forward Error Correction 11 3.1 Categories ofFEC codes 11 3.2 Encodingfunction 12 3.3 Systematic codes 12 3.4 Minimum distance 13 3.5 Trivial decoding 13 3.6 Erasures and errors 13 3.7 Einear codes 14 3.7.1 Generator matrix 14 3.7.2 Parity check matrix 15 3.7.3 Syndrome decoding 15 3.8 Arithmetic operations in finite fields 16 3.9 Cyclic codes 16 3.10 Failure coverage 17 3.11 Interleaving 18 4 Error-correcting codes 19 4.1 Reed-Solomon 19 4.1.1 Linear (classic) approach 20 4.1.2 Cauchy optimization 21 4.1.3 Cyclic (BCH) approach 21 vii 4.2 Low-density parity-check 22 4.2.1 Simple LDPC construction 23 4.2.2 Parity check matrix 23 4.2.3 Generator matrix 24 4.2.4 Decoding 25 4.2.5 Properties 25 4.3 RAID-6 codes 25 4.3.1 Anvin's optimization of RS encoding for RAID-6 26 4.3.2 Minimal density RAID-6 codes 26 5 Open-source libraries 27 5.1 Libfec 27 5.1.1 Cyclic RS codes 27 5.1.2 Veritysetup 28 5.2 Jerasure 29 5.2.1 Classic RS codes 29 5.2.2 Cauchy RS codes 29 5.2.3 M D S array codes 30 5.3 Intel Intelligent Storage Acceleration Library (ISA-L) . . . . 30 5.4 OpenFEC 30 5.4.1 LDPC-Staircase encoder and decoder 31 6 Performance comparison 33 6.1 Measurements 33 6.2 MDS codes 33 6.2.1 Cyclic Reed-Solomon codes 34 6.2.2 Original Reed-Solomon and Cauchy Reed-Solomon codes 36 6.2.3 RAID-6 codes 39 6.3 LDPC codes 39 6.3.1 Encoding performance 39 6.3.2 Decoding performance 40 7 Conclusion 45 7.1 Consequences for applications using FEC 46 7.2 Future work 46 A Software documentation 47 viii A.l Building the software A.2 Directories A3 Implemented codecs A.4 Scripts B LDPC tests Bibliography List of Tables xi List of Figures 3.1 Codeword of a block code. 11 3.2 Systematic and nonsystematic encoding. 12 3.3 Recovery from errors with and without interleaving. 18 4.1 Graphical representation of the SPC code. 23 4.2 Graphical representation of the code C. 24 6.1 Encoding performance for cyclic RS codes. 34 6.2 Decoding errors and erasures with cyclic RS codes. 35 6.3 Erasure codes performance [6,2]. 36 6.4 Erasure codes performance [14,7]. 37 6.5 RAID-6 codes performance. 38 6.6 Encoding performance for LDPC-staircase codes. 40 6.7 Decoding speed of LDPC-Staircase codes. 41 6.8 Decoding performance for LDPC-Staircase codes. 42 6.9 Additional symbols decoding probability. 43 B.l Decoding speed for code with CR=2/3 and Nl=7. 53 B.2 Decoding capabilities for code with CR=2/3 and Nl=7. 54 xiii 1 Introduction Forward error correction (FEC) is a method used for detection and correction of random errors in transmitted or stored data by adding redundant information. The redundant information is a complex function of the original data [1]. The computation of this redundant information causes additional overhead, and therefore, the trade-off between additional storage and cost of reconstruction must be considered. The modern development of FEC codes in 1947 is due to R. W. Hamming [2]. A description of Hamming's code appeared in C. Shannon's "A Mathematical Theory of Communication" and was generalized by M . J. E. Golay in 1949 [3]. In the next 20 years, new codes and approaches were discovered that are still being used. The most important of these codes are Reed-Muller codes (1954), cyclic codes (1957), Bose-Chaudhuri-Hocquenghem (BCH) codes (1959/1960) and Reed-Solomon codes (1960), all based on Galois field algebra [4, 5]. In 1960, R. G . Gallager developed L D P C codes, based on bipartite graph. They were overlooked for a long time and rediscovered only recently. L D P C codes are capacity-approaching codes. In 1993, new class of high-performance codes were developed called Turbo codes. They are competing with LDPC codes which provide similar performance [6]. Over the last few decades, many FEC codes were discovered with different properties. Their application vary from deep space transmission [7] to security enforcement [8]. L D P C codes are used for error correction in satellite transmission [9], ethernet and wireless connection [10]. Reed-Solomon codes are the most used of the FEC codes in many applications. Their application includes consumer technologies such as CDs, DVDs, Blu-ray Discs, data transmission, broadcast systems and storage systems such as RAID-6 [11] and Ceph [12]. They also find their usage in satellite communication [13]. The scope of patents has not been defined well for FEC algorithms. This patent issue caused a degradation of research and implementation in error-correcting codes. Tornado codes, LT codes and Raptor codes are all patented, therefore only few implementations exist. Multiple cases could be found when patent issues ceased a development on open-source projects. For example, professor James Plank, a renowned 1 i . INTRODUCTION researcher in erasure coding, was forced to abandon development of his open-source library Jerasure after complications with patents [14]. Despite patent issues, numerous open-source libraries of various coding techniques are available to the general public [15]. In this thesis, I compare multiple open-source libraries that came from different backgrounds. Some were developed by major corporations such as Intel, others were developed by individual professionals in the field, like the above mentioned Professor James Plank. Considerable research which was lead into FEC codes and their implementations in the last decades motivated researchers to make a comparison of their performance. However, these scientific papers often focus on the performance of FEC codes with regard to their applications in computer networks and data transmission [16,17,18]. The main target of this thesis is to summarize the state-of-the-art FEC codes used in storage applications. A n example of FEC implementation is a device-mapper target dm- verity1 which implements Reed-Solomon codes based on the library Libfec2 . Device-mapper (DM) is a infrastructure in the Linux kernel that provides a generic way to create virtual layers of block devices. D M target verity (dm-verity) provides read-only transparent integrity checking of block devices using kernel crypto API. Libfec is the only library implementing general Reed-Solomon codes in Linux kernel. Veritysetup is a tool used for user-space configuration of dm-verity and it allows encoding in user-space and decoding both in kernel-space and user-space. The library Libfec is well-known and frequently used. However, new and more modern techniques were developed over the years, as this thesis aims to demonstrate. 1.1 Goals The goal of this work is to describe state-of-the-art FEC algorithms and make a comparison of their open-source implementations. The primary issue in the application of coding theory is a great variety of these codes and their complexity. In perfect world, storage administrators would understand the complicated mathematics 1. https://gitlab.com/cryptsetup/cryptsetup/wikis/DMVerity 2. https://github.com/quiet/libfec 2 i . INTRODUCTION behind FEC, and thus, they would be able to choose the code with properties that would fit their system perfectly Fortunately, with all open-source implementations, it is enough to know only some properties of the construction like ability to correct certain number of errors per block or encoding and decoding speed. This thesis aims to make an introduction into the coding theory, describe chosen FEC algorithms, and compare their performance and other properties in storage applications. Therefore, it gives storage administrators some perspective on the current situation in errorcorrecting codes and their implementations. 1.2 Scope of the thesis This work consists of seven chapters. The first chapter is the introduction. In the second chapter we describe why and how is the FEC used in storage systems. Furthermore, we introduce the common types of errors in data storage. In the third chapter we make a brief introduction into the coding theory. In the fourth chapter we describe the chosen FEC codes - Reed-Solomon, LDPC and RAID-6 codes. The fifth chapter contains a summarization of the open-source libraries used for comparison. The sixth chapter presents the results of the performance comparison along with a brief description of implementation and methodology. In the seventh chapter we summarize the thesis. The appendix contains documentation for the software included with this thesis. 3 2 Storage and errors Information storage is an essential part of every IT infrastructure. During last decade, information storage has developed into a highly sophisticated technology which provides numerous functions. Its importance is highlighted by the fact that we live in a digital era in which the world's stored information is more than doubling every two years [19]. For this reason we can't use mirroring as a solution for every storage system demanding reliance. Therefore, new techniques had to be found that guarantee lower storage overhead and cost of reconstruc- tion. 2.1 RAID Even in the past when demand for storage was significantly smaller, the concept of storing data on a single drive has proven to be insufficient. Single Large Expensive Drive (SLED) couldn't meet performance requirements because of the limited number of I/Os, therefore it was replaced by Redundant Array of Independent Disks (RAID) [11]. Disk drives are susceptible to failures due to mechanical wear and other environmental factors which could result in data loss. With a growing number of disk drives in storage array increases a probability of failure. For example, consider a storage array of 100 disks, each with an average life expectancy, or Mean Time To Failure (MTTF), of 500,000 hours. The MTTF of this collection is 500,000/100 or 5,000 hours. This means that a disk drive in this array fails on average every 5,000 hours [20]. 2.1.1 RAID levels A l l RAID levels are defined from the three basic RAID techniques: striping, mirroring and parity. These techniques determine the data availability and performance characteristics of a RAID set. Striping is a technique enabling parallel usage of drives by spreading data divided to strips across multiple drives. 5 2. STORAGE A N D ERRORS A stripe consists of strips divided across the drives and a strip refers to the data slice on an individual drive. Stripe size is a multiple of strip size by the number of data disks in the array. Strip size determines the maximum amount of data that can be written to or read from a single disk in the array at once. Smaller strip size means that data are spread over disks in smaller pieces. For example, in a five disks array set with a strip size of 64KB, the stripe size is 64KB x 5 = 320KB [11]. The following RAID levels are the most used in practice [20]. • RAID-0 uses only data striping techniques. Therefore, it does not provide any data protection and it utilises the full storage capacity of the RAID array. • RAID-1 is based on disk mirroring. Drives in RAID array contain data in multiple copies. This technique provides fault tolerance. In case of a failure, no complex calculations are needed, therefore it is more suitable for applications requiring high availability and reliability. However, mirroring is too expensive to be used in every storage system. • Combinations of RAID-0 and RAID-1 provide both redundancy and better performance. Two different combinations exists: RAID 1+0 and RAID 0+1. They have different properties and benefits. • RAID-4 stripes data for performance and uses parity for fault tolerance. Parity is stored on a dedicated disk. • RAID-5 is same as the RAID-4, but there is no dedicated disk for parity. Parity is distributed across all disks in array, which removes the bottleneck of writing all parity data on one disk. • RAID-6 works in the same way as the RAID-5, but it adds parity element and enables two disk failures in array. 2.1.2 RAID issues Current data storage systems based on RAID arrays were not designed to scale to the type of data growth we experience today. Results are increase in cost of RAID-based storage systems (additional mirroring) 6 2. STORAGE A N D ERRORS or degradation of data protection, resulting in permanent data loss [21]. Scalability is the main issue of RAID schemes. In past, likelihood of failure of more than two drives, which would result in permanent data loss, was not an issue. However, with the continuous growth of drive capacities (beyond petabytes), the probability of multiple disks failure is unacceptable [22]. 2.2 Object-storage systems The issues with RAID forced companies to come up with better solutions for data storage and protection. Object-storage systems are computer data storage architectures that manage data as objects. Object includes data, a variable amount of metadata and a globally unique identifier [23]. Apart from object storage architectures, data can be managed as files (file systems) or in blocks within sectors and tracks (block storage). A great example of a software that implements object-storage is Ceph [12]. 2.2.1 Ceph Ceph is a distributed file system that manages data placement with a pseudo-random data distribution function (CRUSH) designed for heterogeneous and dynamic clusters of unreliable object storage devices (OSDs). It stores data objects in logical partitions called "Pools". The pools can be created for particular types of data or just to separate one group of users from another [12]. To ensure durability of data, pool can maintain multiple copies or employ erasure coding. In replication pools, the C R U S H algorithm provides physical separation of data and copies across separate hardware. Erasure-coded pools mostly employ Reed-Solomon algorithm. The objects are partitioned into k + m = n chunks where k represents data chunks and m are coding chunks. They are distributed to n separate OSDs which means that the system can tolerate m failures [24]. 7 2. STORAGE A N D ERRORS 2.3 Errors Physical disks often experience random errors caused by factors ranging from manufacturing defects to environmental factors such as cosmic rays and overheating. One possible hardware error is a bit-error which is unauthorized transition from 0 to 1, or from 1 to 0 [25]. 2.3.1 Soft errors Soft error is a bit-error that will not damage system's hardware. It can only cause damage to the data being processed. Soft errors could be categorized by the cause of error into chip-level and system-level [26]. • Chip-level soft errors are caused by cosmic rays, radiation, overheating or other environmental factors [27]. Cosmic rays are high-energy radiation, which upon impact with the Earth's atmosphere produces high-energy protons, neutrons and other particles. If they get near the wrong part of a chip, the electrons they trail can cause bit-flips. This issue is being investigated by major technology corporations like Intel and IBM [28]. They found that more soft errors occurred in higher altitudes, while in caves there were nearly none. That also proved that cosmic rays were behind soft errors. As memory chips decrease in size, this error will occur with higher frequency. This problem could be a major limiter of a computer reliability in the next decade. One of the proposed solution is a built-in cosmic ray detector. When triggered, it could activate some repair mechanism. This is where FEC codes would be very useful [27]. • System-level soft errors occur as a result of system failure. Typically when data being processed are hit with a noise phenomenon, while data are on a data bus. Result of data and noise is processed and stored which can cause later problems [26]. 8 2. STORAGE A N D ERRORS 2.3.2 Hard errors Hard error is caused by a hardware failure or defect. The difference between soft and hard errors is that hard errors are not rectified after the computer is rebooted. Today, line between soft and hard errors is thin [29]. For example, disk can have built-in error detection and after detecting a bit-flip caused by radiation, the system evaluates the disk as failed. After rebooting, computer remembers that the disk is failed and will not try to recheck the data. 2.4 Bit-errors and security The obvious danger from bit-errors is a data corruption which can be considered to be a security compromise. Bit-errors in combination with other error injection attacks can defeat numerous security mechanisms [25, 30]. A study was introduced that measure a probability of successful attack on an existing program using a random single-bit error [31]. One of the results is that a text-segment memory error would compromise ssh with about 0.1% probability. Another study found that secrets in cryptographic protocols could be recovered by exploiting random hardware errors [32]. Smart cards are susceptible to glitches that cause to dump encryption keys from smart card memory. These glitches can be introduced by application of electric changes to smart card electronics [33]. Physical access is a critical element of the attacks which exploit random errors. A n attacker can, for example, introduce errors by overheating or radiation. However, there also exist random errors introduced by the environment (cosmic rays) and the attacker can exploit the probability with which they occur. A study found that if the attacker is allowed to provide a program to be executed, this program could be designed in such a way that a single-bit error in the process address space gives him a 70% probability of completely taking over the J V M to execute arbitrary code [34]. Almost all these attack could be prevented by employing FEC mechanism. However, in the low-profit-margin PC market, additional FEC memory is usually not provided. 9 3 Forward Error Correction Forward Error Correction (FEC) [1] is a mechanism that allows recovery of original data from encoded data with a limited number of errors. Encoding [35] is a process of calculating encoded message from original message by adding redundant data. The set of all possible encoded messages is called an error-correcting code. Decoding is a process that attempts a reconstruction of the original message by examining possibly corrupted version of encoded message and then making a decision. I am going to assume that our information symbols are bits (Os and Is) or bit-vectors of length w (word size). Galois field of order 2W ( GF(2W )) is a field under which are defined operations addition (exclusive-OR) and multiplication over these information symbols. 3.1 Categories of FEC codes The two main categories of FEC codes are block codes and convolutional codes [36]. Block codes encode a k source symbols, into a codeword coin encoding symbols where n > k (Figure 3.1). Which means that original message is divided into blocks of k source symbols each. Convolutional codes use a sliding window technique. Therefore, a certain amount of memory is needed by the encoder [4]. In this thesis I concentrate only on block codes because they are more suitable for storage applications. That is because of the difference between decoders of block and convolutional codes. k n-k Original information Redundant i information I Figure 3.1: Codeword of a block code. 11 3- FORWARD ERROR CORRECTION Block codes are decoded using hard-decision algorithm which provides sufficient speed and acceptable overall performance. Convolutional codes employ soft-decision algorithm for decoding which can provide better error-correcting performance, however, for a price in slow decoding. Convolutional codes are therefore used for transmission as the retransmission of message can be more costly than its slow reconstruction [37]. 3.2 Encoding function The projection of vectors consisting of k information symbols into vectors consisting of n encoding symbols (codewords) is called an encodingfunction. A set of these codewords is called a code of length n and dimension k. We denote this code as an [n,k] code [35]. The ratio k/n is called rate of the code [38] and the difference (n — k) is the redundancy introduced by the code. 3.3 Systematic codes The codes described in this thesis are called systematic codes [36]. Difference between systematic and nonsystematic codes is that in a codeword of a systematic code we can separate source symbols from redundant symbols while in nonsystematic codes, the redundant symbols are mixed into codeword (Figure 3.2). Systematic codes have in each codeword n symbols, where k symbols are source symbols while the other m = n — k symbols are used for error detection and correction. Source symbols Encoding Source symbols Redundant , symbols i Encoding symbols • • i Systematic code Nonsystematic code Figure 3.2: Systematic and nonsystematic encoding. 12 3- FORWARD ERROR CORRECTION 3.4 Minimum distance Hamming distance (dn) [38] is the number of coordinates in which two codewords differ and the weight of a codeword is its Hamming distance to the all-zero vector. Minimum distance (d) of code C is defined as: d = min{dn{OjV) : a ^ b,a,b G C } (3.1) Minimum distance of code defines error-correcting properties of code. Therefore, we denote [n, k] code with a minimum distance d as an [n,k, d] code. A n [n,k, d] code can correct up to [(d — l)/2j errors and detect up to (d — 1) errors [35]. In coding theory, one of the goals is to find codes with the code rate and minimum distance as large as possible [38]. However, parameters n, k and d are constrained by certain bounds. These bounds are discussed in the next sections. 3.5 Trivial decoding Let's denote a vector r a s a possibly corrupted version of a codeword a in code C and let's assume that no more than [(d — 1)/2\ errors occurred. Then we can decode vector r by checking whether it is in the code C or not. If the vector r is in the code, then we can be sure that r is not corrupted (r = a). Otherwise, we compare r with every codeword in C and find the codeword a which has the smallest Hamming distance to r [35]. This method includes exhaustive search over set of all codewords and therefore it is not practical for large codes. 3.6 Erasures and errors Bit erasure [35] is not same as bit error. A n erased bit is bit that cannot be read but we know its position in an erroneous vector. Thus, we only have to decide whether it is 1 or 0. Bit error, on the other hand, is hard to detect, and determine its location. Therefore, it is easier to correct erasures than errors. We are able to correct up to (d — 1) erasures as to only [(d — 1) /2j errors. We 13 3- FORWARD ERROR CORRECTION may also want to simultaneously correct errors and erasures. In that case, in a code with minimum distance d, we can correct up to s errors together with t erasures whenever 2s + t < d — 1 [35]. A n example of erasure can be a disk drive failure in RAID array. We know positions of symbols stored on failed disk but we do not know their value. A n erasure-correcting algorithm must only decide value of the erased data. Examples of random errors are soft-errors - we do not know if they occurred. A n error-correcting algorithm must first perform errordetection and then try their correction. 3.7 Linear codes Linear codes [35] are error-correcting codes that can be described only by k base linearly independent codewords. Moreover, linear codes are more efficient to encode and decode and hence they are more suitable for implementation in applications. Code C is a linear [36] if it is subspace of GF(^)W where q is a number of elements in the field (q = 28 = 256 for 8-bits information symbol) and n is number of information symbols in a codeword. Furthermore, if C is linear, it contains the all-zero vector and sum of any two codewords in code C is also a codeword. There are two important matrices defining a linear error-correcting code. Generator matrix is used for encoding, and parity check matrix for error-detection and correction [38]. These matrices are mutually dependent and conversion between them is possible. 3.7.1 Generator matrix Generator matrix [38] has dimension k x n. Rows of generator matrix for code C forms linearly independent codewords [38] which are the basis. Set of vectors is linearly independent when it doesn't contains any vectors that are result of combinations of vectors in this set. Encoding with a generator matrix is simple. Let u be an information vector of length k and G a k x n generator matrix. Then u is encoded into a vector v of length n by: v = uG (3.2) 14 3- FORWARD ERROR CORRECTION Encoding depends on the choice of a generator matrix. If we want a systematic code [35], the generator matrix must be written as G=(Ik\V) (3.3) 4 is k x k identity matrix and V is a k x (n — k) matrix. We can transform any generator matrix into systematic form using matrix opera- tions. 3.7.2 Parity check matrix Parity check matrix [38] has dimension (n — k) x n and we say that matrix H is a parity check matrix of an [n, k] code C if and only if for all c G C , cHT = 0 (3.4) HT denotes the transpose of matrix H and 0 is the all-zero vector of length n — k. Systematic parity check matrix [35] can be found easily from systematic generator matrix as H = (VT \In-k) or from nonsystematic parity check matrices using simple matrix transformations. 3.7.3 Syndrome decoding Syndrome decoding [38] is an efficient method of decoding a linear code. Let C be a linear [n, k, d] code with parity check matrix H. Let's denote a codeword in C as u and possibly erroneous version of u as r. We say that the syndrome of r is the vector s of length n — k given by s = rHT (3.5) If no errors occurred, the syndrome s is the all-zero vector. Let's denote e as an error vector, therefore r = u ® e. Notice that, s = r_HT = (u © e)HT = uHT © e_HT = e_HT (3.6) Since u is in C, the expression uHT is equal to the all-zero vector. Thus, we can see that the syndrome does not depend on the received vector but only on the error vector [35]. 15 3- FORWARD ERROR CORRECTION It is not too hard to prove that there is a 1-1 correspondence between errors [38] of weight < \_(d — 1) /2j and syndromes. This knowledge gives us a key to the decoding method better than the exhaustive search. We firstly construct a table of correspondence between syndromes and error vectors of weight < [_(d — 1)/2j. Then we calculate syndrome of possibly corrupted vector r, we find corresponding erroneous vector e in the table and then we apply this vector to r: u = r © e (3.7) This method of decoding is more efficient than exhaustive search, however, it is still too complex for large codes. 3.8 Arithmetic operations in finite fields Addition and multiplication of bit-vectors in GF(2H ; ) [39] are the main operations of any F E C algorithm. Therefore, their efficient implementation is a key factor of performance. Addition is easy to implement using the fast XOR operation. Multiplication can be implemented with multiplication table. However, this solution is appropriate only for bit-vectors of length w < 8. This is because of bad scalability. The table size, for w = 8, is 28 x 28 = 65536 elements. Another solutions, suitable for w < 16, use log and anti-log. This method has better scalability, for w = 8, we need to keep only 28 + 28 = 512 elements. However for larger w, tables are too extensive and the only other option is slow, iterative method [40]. 3.9 Cyclic codes Cyclic codes [38] are error-correcting codes that have algebraic properties which are convenient for efficient error detection and correction. We say that linear code C over GF(2H ; ) of length n is cyclic if for any codeword (c0rclr...rcn-2,cn-1) G C , then (cn-lrc0rclr...,cn-2) G C . In other words, circular shifts of each codeword in C gives another codeword that belongs to the code C [35]. If we define polynomial of degree < n with coefficients in GF(2W ) as c(x) then we can say that if c(x) G C then x.c(x) mod (x11 — 1) G 16 3- FORWARD ERROR CORRECTION C. Thus, if c(x) E C , then for any polynomial u(x) it holds that u(x)c(x) mod (xn — 1) G C . Let's denote polynomial of degree (n — A:) that divides xn — 1 as If divides every C(JC) G C , that is c(x) G C -<=>• exists M(JC), such that c(x) = u(x)g(x)(mod xw — 1) (3.8) and deg(u) < k, then we call g(x) a generator polynomial of cyclic code C [38]. This process of multiplication of polynomial u(x) by g(x) is called encoding in code generated by the polynomial g(x) into a codeword c(x). This simple encoding scheme does not produce a systematic code [35]. The systematic encoder for cyclic codes is composed of multiple steps, where the final codeword c(x) has the first k coefficients (of monomials with the lowest orders) identical to those of u(x). The other coefficients are chosen in such a way that c(x) becomes divisible byg(x). 3.10 Failure coverage Failure coverage [41] is a key property of error-correcting and erasure codes. There are four ways how we can specify failure coverage: • Threshold is a precise number of always tolerated errors or erasures. For example, a system can always tolerate 3 erasures. • Average number of erasures or errors that the system can tolerate. For example, the system can recover from an average of 4,13 errors. • Overhead factor (/) is equal to the number of encoding symbols required for reconstruction (k ) divided by number of information symbols (k). f = | (3.9) Thus, f > 1. 17 3- FORWARD ERROR CORRECTION • Maximum distance separable (MDS) [n, k, d] codes have the greatest possible minimum distance of code, d = n — k — 1. This is called the Singleton bound. M D S codes are capable to correct up to (n — k) erasures or [(d — 1) /2J errors. MDS codes are space-optimal and their overhead factor / is equal to 1 [35]. 3.11 Interleaving Interleaving is a technique used to improve decoding performance of FEC codes [35]. Errors occur in bursts more often than independently [42]. For example, it is probable that cosmic rays or noise on a bus while data are being processed will affect multiple bytes in contiguous sequence. If the length of this sequence of errors in codeword exceeds the error-correcting capability of used FEC code, then it fails to recover the original message (Figure 3.3). Interleaving approaches this problem by shuffling encoding symbols across several codewords. Thus, in case of burst error, a uniform distribution of errors is created. Modern codes like Turbo codes and LDPC assume an independent distribution of errors. Therefore, systems using these codes typically employ additional interleaving [35]. No interleaving Codeword 1 Codeword 2 Codeword 3 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 ; Errors V I_LJJ_LLLJ_L_LÜ 1 2 2 2 2 3 3 |_3j 3 |_3j 3 3 3 Fails to recover Interleaving Codeword 1 Codeword 2 Codeword 3 i . ] . [ . ] . i i 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 Interleaving of symbols ! , 2 3 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 ; Errors 1 2 3 J 1 J 2 3:12 3 2 3 1 2 3 1 1 1 2 3 , 2 3 ; Uniform distribution of errors ; 1 ® ® < h i < < M1 (f) 2 2 2 2 2 2 2 ( § ) 3 3 3 3 3 3 3 V Recovery Figure 3.3: Recovery from errors with and without interleaving. 18 4 Error-correcting codes 4.1 Reed-Solomon Reed-Solomon (RS) codes were developed in 1960 by Irving S. Reed and Gustave Solomon. The paper was titled "Polynomial Codes over Certain Finite Fields" [43]. Since introduction of the original construction scheme of RS codes, new algorithms and approaches were presented to increase performance and ease implementation [5]. RS codes based on the original construction scheme were not cyclic and they used method of exhaustive search over all polynomials of code in decoding which is impractical for all but simplest of cases. This issue was resolved by replacement of the original scheme by BCH code like scheme [44]. BCH codes [36] form a class of cyclic error-correcting codes. They use polynomial representations and they are encoded and decoded through the use of finite field arithmetic. The great advantage of BCH code like scheme are great decoding capabilities. Further improvements to B C H scheme decoder were made in 1969 by Elwyn Berlekamp and James Massey which is since known as Berlekamp-Massey decoding algorithm. In 1975, based on the extended Euclidean algorithm, another improved B C H scheme decoder was introduced by Yasuo Sugiyama. The original scheme decoder was improved in 1986 by introduction of Berlekamp-Welch algorithm, in 1996 by invention of soft decoders and in 2002 by development of a new decoding algorithm based on the extended Euclid algorithm [45]. Performance of RS codes is determined by implementation of expensive arithmetic operation - multiplication. We know that multiplication can be implemented efficiently using lookup tables or log and anti-log tables. Cauchy Reed-Solomon codes deal with this problem by replacing the standard Vandermonde matrix used in the original scheme by Cauchy matrix and substituting multiplication by multiple XORs[46]. The RS codes are well-suited for applications where errors occur in bursts [35]. This is because it does not matter how many bits in one encoding symbol are erroneous, it only counts as one failed symbol. 19 4. ERROR-CORRECTING CODES If we are working in GF(2W ) where w = 32 (one symbol comprises 32 bits), then in one contiguous sequence can fail up to 32 bits in such a manner that only one symbol is declared as erroneous. O n the other hand, in applications, where single bit errors are frequent, employment of other correction code might be a better option. 4.1.1 Linear (classic) approach In the original view ofRS codes, every codeword in an [n,k] code is a sequence offunction values of a polynomial of degree less than k [44]. Suppose that we have information m consisting of k information symbols, {mi, mi,m^}, taken from a finite field of n elements GF(n) = {a\, «2/ •••/an). We can use these symbols to construct a polynomial p(x) = m\ + mix + ... + m^xk ~r . Encoding is a process of evaluating p(x) at each of n elements in GF(n). Codeword c is then a vector of these values. c = (p(ai),p(a2),p(a„)) (4.1) This means that the encoding function C(m) is a linear mapping C : GF(n)k —> GF(n)n , that satisfies C(m) = mA for the following (k x n)-matrix A with elements from the GF(n): a' 1 1 • •• i a\ ai a\ a\ • a» k-i 4 - 1 •• • ak ~x Matrix A is the transpose of a Vandermonde matrix over GF(n). Utilisation of transposed Vandermonde matrix as a generator matrix in construction of RS code means that this code is linear and space-optimal (MDS) [44]. It is known that for any linear code there exist an eqivalent systematic code [47]. The generator matrix G for systematic code must be of the form: 20 4. ERROR-CORRECTING CODES G=(Ik\V) (4.2) Theoretical decoder corrects errors by finding the most popular message polynomial out of potential polynomials [44]. Potential polynomials are produced by choosing k values out of n values in a codeword. The most suitable is chosen as the correct polynomial. The number of these potential polynomials is (^), which makes this decoder impractical for almost all applications. More suitable for real-world applications is Berlekamp-Welch decoder. However, if we can rely on that only erasures occurred, decoding is much simpler. As we know the location of erasures, we only have to calculate their values. This can be done using generator matrices [15]. 4.1.2 Cauchy optimization In 1995, two significant performance improvements to the classic ReedSolomon scheme, termed Cauchy Reed-Solomon (CRS) coding were presented by Blomer et al. [48]. The first of the improvements is that CRS codes employ Cauchy matrices instead of Vandermonde matrices which improves the performance of matrix inversion for the decoding. The second improvement is the elimination of the expensive multiplications by converting them into multiple XOR operations. CRS doesn't operate on single information symbols. Instead, data is partitioned into strips and encoding strip is XOR of all data strips selected by generator matrix. Generator matrix consists only of Is and Os and is of dimension wn x wk [15]. 4.1.3 Cyclic (BCH) approach In the BCH view ofRS codes, every codeword c is a sequence of coefficients [35], C = (Co, Ci, C 2 , C „ _ i ) > c(x) = Co + C\X + C2X2 + ... + Cn-\Xn ~X (4.3) as opposed to the classic approach to RS codes where codewords are viewed as a sequence of values. 21 4. ERROR-CORRECTING CODES If an [n, k] code is cyclic then it is always defined by a generator polynomial in form: g(x) =go + gix + g2x2 + ..g„-kxn -k (4.4) A vector c is a codeword in the code C if and only if its corresponding polynomial c(x) is a multiple of the generator polynomial g(x) defining this code [36]. Because a finite field with q elements is unique up to isomorphisms, we can name our elements freely. The order of an element a in finite field of q elements, GF(q), is the smallest positive integer m such that ocm = 1. A finite field always contains at least one element, called a primitive element, that has order (q — 1). Let a be the primitive element of G¥(q). Since (q — 1) consecutive powers of ex., 1, a, a2 ,cfl~2 , must be distinct, we can use them as a representation of the nonzero elements in GF(^) [44]. The generator polynomial g(x) is defined for RS codes as the polynomial whose roots are exactly g(x) = f{(x - oc1 ) (4.5) i=l The choice of the generator polynomial in this form offers us a powerful and efficient set of decoding algorithms because to check if the codeword is valid, we only need to verify that it has as roots the elements a1 , a2 ,ccn ~k [44]. 4.2 Low-density parity-check Low-density parity-check (LDPC) codes are linear forward error correction codes, published in 1962 as a PhD thesis by Robert G. Gallager [49]. At that time, the LDPC codes were impractical to implement and thus forgotten until 1996 when they were rediscovered by David J. C. MacKay and Radford M . Neal [50]. Today, L D P C codes find their applications in various standards where they are outperforming before-used RS codes [51]. Turbo codes are another class of codes developed in 1993. LDPC codes are nowadays competing with Turbo codes which provide similar performance [6]. 22 4. ERROR-CORRECTING CODES 4.2.1 Simple LDPC construction In the following examples is considered only binary information consisting of Os and Is. The essential idea of LDPC codes is to find parity check bits for subsets of original information bits. The simplest possible coding scheme is the single parity check (SPC) code which involves only one additional bit [52]. If we have original information m, consisting of bits m\, mi,mk and we add one parity check bit c, then every codeword consists of bits m\, mi,mk, c which satisfy the constraint mi © mi © ... © mk © c = 0. (4.6) LDPC codes are constructed using a sparse bipartite graph [36]. A bipartite graph [52] is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V (Figure 4.1). m\ mi • • • } Information bits Constraints 1Check bits Figure 4.1: Graphical representation of the SPC code. The SPC code is insufficient for most applications. It is very simple, however, it can detect only odd number of errors and it cannot indicate which bit, or bits, were inverted. To detect and correct multiple bits, we need to add more parity check bits C\, Ci,cn_k. 4.2.2 Parity check matrix Let's denote a [6,3] code as C, where the original information is composed of bits m\,mi,m2 for which we add check bits C\,Ci,c^. This code is constructed using bipartite graph (Figure 4.2) and it is defined 23 4. ERROR-CORRECTING CODES by these equations: mx © m 2 © ci = 0 (4.7) m2 © m 3 © c2 = 0 (4.8) mx © m 2 © m 3 © c3 = 0 (4.9) mi 7W2 m.3 / \ Cl C2 C3 Figure 4.2: Graphical representation of the code C. These constraints are often written in matrix form [52]. This matrix is called parity check matrix. Parity check matrix is sparse (lowdensity) which means that most of its elements are zeros. Code C can be represented by parity check matrix H, as (\ l 0 1 0 o\ H = 0 l 1 0 1 0 Vi l 1 0 0 1/ As we can see, the matrix H is not sparse. But as the length of a codeword increases, the ratio between Os and Is in the parity check matrix declines. LDPC codes can be classified according to the construction method used for generating the corresponding parity check matrix H into random and structured L D P C codes [35]. The random L D P C codes show slightly better correction capabilities. However, the structured LDPC codes are much easier to encode and decode. 4.2.3 Generator matrix Any parity check matrix can be transformed into generator matrix [38]. For example, from parity check matrix H we get the following generator matrix G: 24 4. ERROR-CORRECTING CODES H = (V\In_k) —> G = (Ik\VT ) (4.10) (\ l 0 l 0 o\ (\ 0 0 1 0 l \ H = 0 l l 0 1 0 —• G = 0 1 0 1 1 1 Vi l l 0 0 1/ Vo 0 1 0 1 1/ Finally, the encoding is for the linear codes process of multiplying bit-vector information by generator matrix [35]. 4.2.4 Decoding LDPC decoder first calculates syndrome of a codeword using paritycheck matrix. Then, according to syndrome's values decoder determines whether the codeword is in the code or not. Finally, decoder picks the most suitable codeword, to which was original information most likely encoded. This decoder is called the Maximum Likelihood (ML) decoder [52,35]. 4.2.5 Properties LDPC codes are asymptotically MDS, their failure coverage is represented by overhead factor / >= 1. RS codes are MDS, however, LDPC codes outperform them in encoding and decoding speed. The reason is that the construction scheme of L D P C codes allows them to be efficiently implemented and this implementation doesn't require expensive finite field multiplication [51]. 4.3 RAID-6 codes RAID-6 codes are erasure codes that were specifically designed to be used in RAID systems. These codes are MDS. However, in a RAID system with k disks containing data and m disks, whose contents are calculated from the original k devices, RAID-6 codes are limited only for case when m = 2 [15]. Hence, as discussed before, this limitation 25 4. ERROR-CORRECTING CODES introduces a great issue with scalability [22]. Nonetheless, due to their simplicity and other properties (MDS, great performance), they still find their uses in numerous applications. In RAID-6, we conventionally denote D ; as the disks carrying the original data (0 < i < k — 1), the first parity disk is denoted as P and the second as Q. The P disk is equivalent to the parity disk in RAID-4 system, and the Q disk is defined by parity equation specific for a code. 4.3.1 Anvin's optimization of RS encoding for RAID-6 This optimization was posted by Hans R Anvin in 2004 [53]. It ensures better encoding performance for systems where m = 2. On the first coding device P is stored parity data from other devices. The second device, Q, is calculated from the data devices: Q = E2, 'D »" <4 -12 ) i=0 All arithmetic is in GF(2H ; ) and since the multiplication by two may be implemented much faster than general multiplication in GF(2W ), this optimizes the performance of encoding. 4.3.2 Minimal density RAID-6 codes Minimal density RAID-6 codes is a family of codes to which belongs codes like Blaum-Roth [54], Liberation [55] and Liber8tion [56]. In the process of encoding, these codes require a generator bitmatrix G. To create a bit-matrix, we need to expand a generator matrix (k x n) in G¥{2W ) by w in each direction (kw x nw) [57]. The formation of this bit-matrix is quite constrained. The first kw columns of G compose of identity matrix, because the code is systematic. A n d in order for the P disk to contain parity data, the next w columns must contain k identity matrices. The only flexibility in construction of code is in the last w columns of the G [15]. If k < w, the last w columns must have at least kw + k — 1 ones for the code to be MDS. The codes described by the M D S matrices achieving this lower bound are called Minimal Density codes [58]. 26 5 Open-source libraries The tested libraries are all freely available under one of the open source licenses - BSD, GPL, MIT, etc. Open source licenses allow software to be freely used, modified, and shared. These four libraries were chosen as a representation of the current situation in implementation of FEC codes. They range from erasurescorrecting libraries Qerasure, ISA-L, OpenFEC) to the libraries correcting both errors and erasures (Libfec). 5.1 Libfec The version 1.0 of the library Libfec1 was released in 2001. The author of this library is Phil Karn and it is heavily based on earlier work by Robert Morelos-Zaragoza and Hari Thirumoorthy. It may be used under the terms of the G N U Lesser General Public License (LGPL). Libfec is a C library that provides a set of functions implementing several FEC algorithms and some low-level routines. The implemented FEC algorithms are several convolutional codes mainly used for transmission ("Voyager" code, "Cassini" code, etc.) with Viterbi decoders, and Reed-Solomon (RS) codes. These algorithms can correct both errors and erasures. This library makes use of various SIMD (Single Instruction, Multiple Data) instruction sets when available. We only implement RS encoder and decoder, and test performance with errors and erasures. 5.1.1 Cyclic RS codes The RS codes implemented in this library use B C H (cyclic) approach. The library Libfec is widely used mainly in transmission (satellite communications) - it provides an optimized encoder for the Consultative Committee for Space Data Systems (CCSDS) standard (255, 223) RS code [59]. It is also the only implementation of the RS code in the Linux kernel. For variety of applications, three sets of functions are supplied. The functions with names ending in int handle data in integer arrays, 1. https: / /github .com /quiet /libfec 27 5. OPEN-SOURCE LIBRARIES permitting at most 32 bits per information symbol. The functions with names ending in _char take unsigned char arrays and can handle codes with symbols of 8 bits or less (codeword has at most 255 symbols). The functions ending with 8 implement a specific (255, 253) code with 8-bit symbols and a generator specified in CCSDS standard. They however use the conventional polynomial representation instead of the special form specified by CCSDS. For full CCSDS compatibility, the functions with names in ccsds convert between these forms using lookup tables and then call the 8 functions. The functions with names ending in char and int require as an attribute a control structure. This structure is initiated by calling init_rs_char or i n i t _ r s _ i n t . It contains elements specifying properties of the created code. Symsize is the number of bits per symbol (< 8 for _char and < 32 for _int), codewords have 2s ymsize — 1 symbols. The codeword may be shortened with the pad parameter - the number of leading consecutive zeroed symbols. Nroots is the number of parity symbols per codeword. We must also specify the generator polynomial (gfpoly), the first consecutive root of the RS code (fcr), and the primitive element in the GF, used to generate the generator polynomial (prim). The resulting RS code has parameters (n, k), where n = 2s ymsize — pad — 1 and k = n — nroots. The decoders have as an attribute the number of erased symbols and their positions, the code is MDS and therefore it can repair (n — k) erasures. If no erasures are detected, decoder uses syndrome decoding and can correct up to [(n — k)/2)\ errors. If a combination of errors and erasures occurs, it can repair s errors and t erasures, whenever 2s + t < n - k. 5.1.2 Veritysetup Veritysetup implements encoder and decoder from Libfec which works with arrays of chars. It also employs additional interleaving. The interleaver takes only one byte from each block (k blocks) and gives these bytes to encoder or decoder. This means a great improvement of decoding capabilities - instead of contiguous sequence of [(n — k)/2\ bytes, it can correct sequence consisting of [(n — k)/2\ blocks. However, this is only possible using additional memory. 28 5. OPEN-SOURCE LIBRARIES 5.2 Jerasure The revision 1.0 of the library Jerasure2 was released in 2007. The author of this library is James S. Plank. The library itself is protected by the New BSD License. In 2013, because of the patent issues [14], professor Plank was forced to end support for Jerasure and GF-Complete library which implements arithmetic operations under finite fields. The official repositories of Jerasure and GF-Complete were removed, although a new repositories emerged that are still being maintained. Jerasure is a C library that supports a variety of erasure codes including original RS coding, CRS coding, general Generator matrix and bit-matrix coding and Minimal Density RAID-6 coding. The implementation of these codes have customizable word size (w) and can make use of a variety of optimizations [15]. The library Jerasure assumes that we have k devices that hold data and m devices whose contents will be calculated from the original k devices. The codes implemented in Jerasure are all MDS, this means that the entire system will be able to tolerate the loss of any m devices. 5.2.1 Classic RS codes This library implements the classic RS codes employing the Vandermonde matrix and special case of RS codes optimized for RAID-6 where the m is equal to 2. In order to encode data using classic RS codes we need to specify k, m and word size w. Data are partitioned into k blocks and all arithmetic operations are performed on w-bit vectors over GF(2i y ). The result of this encoding are m encoded data blocks of same size as the original data blocks. The word size w must be for both classic RS and RAID 6 optimization for RS codes 8,16 or 32. 5.2.2 Cauchy RS codes The implementation of Cauchy RS erasure codes in Jerasure does not use the classic Cauchy matrices. It constructs the generator matrix by optimizing the classic Cauchy matrix in multiple steps. This procedure, 2. http://jerasure.org/ 29 5. OPEN-SOURCE LIBRARIES however, does not guarantee an optimal number of ones in the final generator matrix. The number of ones in generator matrix should be minimal to reduce the number of XOR operations. 5.2.3 MDS array codes Jerasure implements multiple RAID-6 codes. It optimizes RS for use in RAID-6 and implements RAID-6 codes: Liberation, Liber8tion and Blaum-Roth. We can specify number of disks k and word size w for Liberation and Blaum-Roth. The word size w is for Liber8tion equal to 8 and all these RAID-6 algorithms has the number of parity disks m equal to 2. 5.3 Intel Intelligent Storage Acceleration Library (ISA-L) The library Intel ISA-L3 provides tools for storage applications on Intel architecture. The open-source version of this library contain multiple units that implement functions for erasure codes, data protection, compression, hashing and encryption. The erasure code functions implement the classic RS codes with a possibility to use Cauchy matrix instead of Vandermonde. The arithmetic operations are performed over GF(28 ) and the multiplication is implemented using multiplication table. The encoding and decoding functions are represented in multiple versions which are optimized for various processor instructions - AVX, AVX2, SSE4.1. 5.4 OpenFEC OpenFEC4 is a library that implements multiple erasure codes - RS, LDPC. This library makes use of a code from Radford Neal's LDPC library and Luigi Rizzo's Reed-Solomon implementation which is partly derived from code by Phil Karn (Libfec). 3. https://github.com/01org/isa-l 4. http://openfec.org/ 30 5. OPEN-SOURCE LIBRARIES Therefore, it is governed by several licences. The main license is CeCCIL-C which is very similar to G N U / L G P L license. CeCCIL is licence for the LDPC-Staircase code. It shares some similarities with the G N U / G P L licence. Other licences are Radford Neal's LDPC simulator licence and Luigi Rizzo's Reed-Solomon licence. The openFEC library provides codecs for RS over GF(28 ) and GF(2m ), 1D-2D parity check matrix, LDPC-Staircase and LDPC specified from file. 5.4.1 LDPC-Staircase encoder and decoder The LDPC-Staircase encoder are described in RFC 5170 [60]. These codes requires specification of the number of source symbols k, repair symbols m and the size of symbol in bytes. The maximum number of source and repair symbols depends on the kind of decoder used. If the maximum likelihood (ML) decoder is enabled then these limits should not be too high since the decoding might finish with a Gaussian elimination on the simplified system. M L decoding enables to reach the best erasure recovery capabilities. However, this is possible at the expense of significant computation loads depending on the size and complexity of the simplified system at the end of iterative (IT) decoding. The default number of maximum source and repair symbols is for M L decoding 50000. In the case when the M L decoder is disabled and the decoding is restricted solely to the IT, the main limit is the available memory. The default number of maximum source and repair symbols is thus 100000. Next, the encoder requires the specification of a seed used to build a code (prng_seed) and the target number of Is per column (Nl) in the left side of the parity check matrix. The encoder creates a single repair symbol at a time. This symbol depends on the source symbols and previous repair symbol. 31 6 Performance comparison In order to compare the encoding and decoding capabilities of diverse FEC algorithms, it is not enough to just measure the encoding and decoding speeds. The reason is their varying encoding and decoding properties which make them suitable for different applications. We perform experiments to test the encoding performance and decoding capabilities. To measure the encoding and decoding speed we split random data into k blocks and utilise the encoding and decoding functions provided by the tested open-source libraries which calculate the m redundant blocks. We iterate over these functions multiple times to ensure the minimal variations in results. 6.1 Measurements The machine used for experimentation is an Asus notebook with a 64-bit 2.50GHz Intel Core i7-4710HQ processor, with 8GB of R A M , L i d and L l i cache of 32KB, L2 cache of 256KB and L3 cache of 6MB. The machine has 4 cores and 8 threads, the encoders and decoders use all of them. The operating system is Kali Linux with kernel version 4.15.0. The encoders and decoders are executed in user-space while no other user programs are being executed. We recorded speed of memcpy () at 9.7 GB/sec. For time measurement, we used two functions: getrusage and clock_gettime. The function getrusage is able to measure time in miliseconds and clock_gettime in nanoseconds. They provide similar functionality and we used them both to test the accuracy of our results. 6.2 MDS codes The reason why we chose to divide the measurement of performance into two parts (MDS, LDPC) is that to evaluate MDS codes it is enough to describe how the encoder and decoder works with data, and measure the encoding and decoding speed. On the other hand, to evaluate 33 6. PERFORMANCE COMPARISON non-MDS codes like LDPC codes we need to run additional tests which measure their decoding capabilities - overhead factor. The decoding speed is for M D S codes always measured on the worst-case scenarios - [(n — k) /2\ errors or (n — k) erasures. 6.2.1 Cyclic Reed-Solomon codes In Figure 6.1 is presented encoding performance of the library Lib fee and the speed measurement of encoding by Veritysetup which employs additional interleaver. We chose to implement cyclic Reed-Solomon codes from the library Libfec and represent the symbols as chars - same as in the Veritysetup. Furthermore, we chose to implement codes with two different generator polynomials - x8 + x4 + x3 + x2 + 1 and x8 + x7 + x2 + x +1. These polynomials are represented as arrays of unsigned chars which have the Oth coefficient in the low bit. The polynomial x8 + x4 + x3 + x2 + 1 is represented as 0x1 ID and x8 + x7 + x2 + x + 1 as 0x187. The generator polynomial 0x1 ID is also used in Veritysetup, therefore this graph shows the overhead which causes the interleaver. The codeword is always of length n = k + m = 255 symbols and we measure the encoding speed with increasing number or check symbols m per codeword. We can notice, that as the rate of the code (k/n) declines, the encoding process takes much longer time. 34 6. PERFORMANCE COMPARISON D e c o d i n g errors C h a r s with gfpoly 0x11 D — H — -C h a r s with gfpoly 0 x 1 8 7 — * — V e r i t y s e t u p — * — - 8 10 12 14 16 18 2 0 2 2 2 4 2 6 2 8 30 32 N u m b e r of c h e c k s y m b o l s in o n e block (m) D e c o d i n g e r a s u r e s C h a r s with gfpoly 0 x 1 1 D — i — (.,nar:5 Wll ' g i poiy L X l ö r - * — ^ :>l:>ri :• — e — —*— 10 12 14 16 18 20 22 24 Word size (w) « 0 0 4000 ? 3500 I 3000 |> 2500 g 2000 1500 1000 Jerasure Original F Jerasure Cai-dy F eec Solomo Solomo —e —*— NN 10 12 14 16 18 20 22 24 Word size (w) Figure 6.3: Erasure codes performance [6,2]. 36 6. PERFORMANCE COMPARISON Figure 6.4: Erasure codes performance [14,7]. Moreover, the choice of the word size w affects mainly Cauchy RS codes. The Cauchy RS codes with smaller w seem to perform better. The choice of w affect the Jerasure implementation of the original RS codes minimally and in the library ISA-L are implemented Cauchy RS codes only for w — 8. As we found out, the difference in speed between erasure codes (original RS, CRS) and cyclic RS is enormous. This is because the codes presented in this section are made for use cases when the numbers of blocks k and m are as small as possible and the block sizes are in Megabytes and Gigabytes. The main drawback of this is that one detected failed bit can cause the system to recalculate whole block as opposed to the Libfec RS codes where it would cause only recalculation of one codeword (255 bytes - for char arrays). Thus, if we want to implement the library Jerasure to our system, we must consider a few factors. Firstly, the library Jerasure implements erasure codes which means that we need some mechanism to detect erasures. Secondly, we must consider the occurrence of failures. This implementation is not too suitable for bit-flips distributed across the storage devices. It is more applicable on systems where whole disk/device can fail (similar to RAID). Finally, we should consider using Cauchy RS codes instead of the original RS as they generally perform better. Also, there are available multiple implementations of these codes so we should choose the best suited for our system depends on the architecture, optimization for processor instructions and other parameters. 37 6. PERFORMANCE COMPARISON Encoding 7000 6000 5000 4000 - 3000 l 1 1 1 1 1 1 1 1 1 r R6 Reed-Solomon Liberation Liber8tion Blaum-Roth 2000 1000 J I L J I L J I L 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 Word size (w) Decoding i 1 r l 1 1 1 1 1 1— R6 Reed-Solomon — e Liberation — * - Liber8tion Blaum-Roth 7000 6000 - 5000 4000 3000 2000 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 Word size (w) Figure 6.5: RAID-6 codes performance. 38 6. PERFORMANCE COMPARISON 6.2.3 RAID-6 codes Now, we present the performance evaluation of RAID-6 codes (m = 2). As we can see in Figure 6.5, the Anvin's optimization made RS codes to perform slightly better than the original RS erasure codes. The other tested codes have very similar performance which can be as high as 5 GB/sec. These are the highest encoding and decoding speeds we reached. However, as we discussed in Section 2.1.2, the limitation on m poses a great issue for high-capacity storage. 6.3 LDPC codes The LDPC codes are asymptotically MDS which means that apart from encoding and decoding speed we need to test the failure coverage and determine the overhead factor. We test a specific implementation of LDPC codes from the library OpenFEC called the LDPC-Staircase codes [60]. This implementation offers us a possibility to determine a number of Is (Nl) in column of a parity check matrix and the numbers of data and check symbols - k,m. We show how these parameters influence the encoding and decoding speed. Furthemore, we will show how the overhead factor differ for varying code rate (CR) and N l . 6.3.1 Encoding performance In Figure 6.6, we divide the encoding speed of LDPC-Staircase codes into two groups according to the rate of code. Similarities between these two groups can be seen - with the growing N l the encoding speed declines. This is because the N l controls the number of operations in the encoding algorithm. If the N l is too high, the encoder is slow but the code has better decoding capabilities (as shown later). Encoding of a code with rate 1 /2 is slower as of a code with rate 2/3 - smaller rate of the code means that the encoding process is slower (as shown in Figure 6.1). 39 6. PERFORMANCE COMPARISON Encoding 1/2 2/3 Code rate Figure 6.6: Encoding performance for LDPC-staircase codes. 6.3.2 Decoding performance We cannot test the worst-case scenario as with M D S codes, thus we choose an interval of loss percentage and show separately how the varying loss influence the decoding speed (Figure 6.7). If a code is MDS and its rate is 2/3 then the maximum amount of erasures that could be repaired is 33,33% of the encoding symbols. For example, if we have M D S [300,200] code then we are able to tolerate up to 100 erasures - to reconstruct all original symbols we need only 200 which is the minimum (k = 200). The overhead factor is equal to 1. However, L D P C codes are not M D S - only asymptotically. That means that the number of encoding symbols that are required for reconstruction is slightly larger than k. The employed iterative decoder will successfully recover the original symbols with certain probability which depends on number of constraints (number of check vertices in LDPC bipartite graph) and the positions of Is in the parity check matrix of the code. The decoding capability of LDPC codes also depends on the complexity of constraints (number of edges in LDPC bipartite graph). The probability that the decoding will fail is described in Figure 6.8. There are two separate graphs as the percentage of tolerated erasures 40 6. PERFORMANCE COMPARISON Code rate = 2/3 12 14 16 18 20 22 24 26 28 30 32 34 Loss rate (%) Code rate = 1/2 12 14 16 18 20 22 24 26 28 30 32 34 Loss rate (%) Figure 6.7: Decoding speed of LDPC-Staircase codes. 41 6. PERFORMANCE COMPARISON Code rate = 2/3 1.00000 I I -N1=5 — i — N1=7 — * — N1=9 iI I -N1=5 — i — N1=7 — * — N1=9 p rf 0.10000 / rf - 0.01000 - 0.00100 - 0.00100 / 0.00010 r / • • •••••« * A - 31 31.5 32 32.5 33 33.5 34 34.5 Loss rate (%) Code rate = 1/2 1.00000 M M M ,5 — i —1.00000 M M M .9 - f 0.10000 f / / . / i - 0.01000 / 1 i. _ : : / : : / f 0.00100 • J ? + t i 0.00010 -i —- 43 43.5 44 44.5 45 45.5 46 46.5 47 47.5 48 48.5 49 49.5 50 Loss rate (%) Figure 6.8: Decoding performance for LDPC-Staircase codes. differs for codes with varying rates. We can see that as the loss percentage in code with CR=2/3 increases to the limit 33.33%, the probability of decoding failure is close to 1 - if there are 33.33% erasures, the decoding will always fail. We can also notice that the number of Is per column of the parity check matrix influence the decoding capability - as the number of Is in parity check matrix increases, the decoder is able to recover from higher percentage of erasures with greater probability. How many more symbols are needed to repair a codeword with certain probability is shown in Figure 6.9. We usedfc=1024symbols. 42 6. PERFORMANCE COMPARISON Code rate = 2/3 1020 1030 1040 1050 1060 Number of available symbols Code rate = 1/2 1020 1030 1040 1050 1060 Number of available symbols Figure 6.9: Additional symbols decoding probability. 43 7 Conclusion We analyzed implementations of multiple FEC codes with different encoding and decoding properties and described their attributes. We have shown that the process of encoding and decoding depends on multiple factors and described in some cases how they can be optimized. We offer the following lessons learned from our experimenta- tion: • Erasures vs. errors: The only tested library that could correct both erasures and errors was Libfec. It employs complex mathematical operations which results in slower encoding and decoding. Despite this issue, the library Libfec has great decoding capabilities which could be enhanced with interleaver. • RS vs. CRS: CRS codes [46] outperform the original RS codes in encoding and decoding speed almost in all cases. To optimize the CRS coding, the word size w should be as small as possible [15]. • RAID-6: The tested RAID codes outperformed all the codes except CRS which is well optimized in Jerasure for use case when m = 2. The great encoding and decoding performance of RAID codes indicates why they are still used despite their issues [22]. • LDPC: The encoding and decoding process of L D P C codes heavily depends on the number of Is in parity check matrix [60]. Despite not being MDS, the decoder of L D P C codes perform well as they decode with almost 100% probability with just 2% additional overhead (overhead factor / = 1.02). Moreover they outperform in encoding and decoding speed the cyclic and original RS codes which is one of the reason why they replace RS codes in applications [51]. 45 7. CONCLUSION 7.1 Consequences for applications using FEC Veritysetup1 is an example of application where the replacement of the current implementation of cyclic RS codes by LDPC codes would enhance the encoding and decoding performance. Veritysetup implements the library Libfec which is also implemented in the Linux kernel and Android. These applications could all utilise the LDPC codes as they use the FEC on a similar principle encode piece of memory and produce smaller encoding information which should be stored on physically separate memory. Another application which could benefit from coding capabilities of LDPC codes is Ceph [12]. Currently, Ceph uses RS codes to calculate the parity chunks which are then distributed across multiple object storage devices. The implemented LDPC-Staircase codes could be of a great use here. Moreover, as we have shown in Figures 6.3 and 6.4, the Cauchy RS codes have great performance and thus, they could serve as a replacement of the original scheme which uses Vandermonde matrix and is significantly slower. 7.2 Future work In this thesis we concentrated only on block codes which provide sufficient coding capabilities and good performance. The convolutional codes provide great coding capabilities [6], however, for a price in decoding speed. The concatenated codes combine the efficiency of block codes and reliability of convolutional codes. They can combine Viterbi-decoded convolutional codes with RS block codes which could yield great results. These constructions could find their usage in object-storage applications like Ceph [12]. Another class of erasure codes that could find their application in storage is Fountain codes [61]. They provide a possibility of producing a potentially limitless sequence of encoding symbols - for RS codes over GF(28 ), it is limited to m, where m = 255 — k. To this class belong Rapid tornado (Raptor) codes and Luby transform (LT) codes. However, Raptor codes are heavily covered by patents which makes it difficult for their application. 1. https://gitlab.com/cryptsetup/cryptsetup/wikis/DMVerity 46 A Software documentation This appendix contains the documentation of the software provided with this thesis. The source code can be found in the archive file included in the thesis repository of Masaryk University. It is also accessible online at GitLab1 . The software is written in the C language and the scripts which serve for automation of tests are written in Bash. A.l Building the software The software was written for use on Unix platforms. This project requires multiple libraries, and therefore, it was easier to implement demonstration programs into the directories of the libraries and adjust the instructions for compilation of the libraries. This way was easier as it doesn't require additional pre-installed libraries. However, there are few exceptions. To build all the libraries, run the script configure. sh which automates the building process by building each library using its own constructions. This script builds the following libraries: • Libfec2 uses CMake and doesn't require any additional preinstalled libraries. • Jerasure3 requires the package gf-complete-tools (Debian) to be installed then the project utilises the G N U build system4 . • OpenFEC5 uses CMake and doesn't require any additional preinstalled libraries. The source code of the library ISA-L6 was omitted from the repository because of the license under which it was issued. However, the source code of the demonstration program can be found in the directory libs. 1. https://gitlab.com/xvirgov/fec-thesis-source 2. https://github.com/quiet/libfec 3. http://jerasure.org/ 4. https://www.gnu.org/software/automake/manual/html_node/Autotools- Introduction.html 5. http://openfec.org/ 6. https://github.com/01org/isa-l 47 A . SOFTWARE DOCUMENTATION To ease the demonstration and testing on the Linux systems, the binaries of the programs measuring performance can be found in the directories of the tested libraries. A.2 Directories The software directory contains the following subdirectories: • results contains subdirectory for each unit of results. Each subdirectory contains files with results in csv format and dem files which serve as a description for plotting graphs by gnuplot. By default, these directories contains the results of measurements performed with my computer (see Section 6.1). • scripts consists of bash scripts which run the tests and then write the results into the directory results. • src contains the measurement of memcpyO by multiple functions and a generator of sequence of unique random numbers. • libs contains source codes of the libraries and source codes of demonstration programs. • libs/Unused directory contains the libraries that we tested but weren't able to fit into this thesis. The library Zfec7 is based on work by Phil Karn (Libfec), Longhair8 and Wirehair9 implements fast Cauchy RS codes and LDPC codes, L D P C - 4 Q T 1 0 is a C++ wrapper for the original library1 1 by Radford Neal and the library Libcorrect1 2 implements a convolutional codec. A.3 Implemented codecs In directory libs/Libfec_Veritysetup/libfec-master/speed_tests 7. https://github.com/tahoe-lafs/zfec 8. https://github.com/catid/longhair 9. https://github.com/catid/wirehair 10. https://github.com/jontio/LDPC-4Qt 11. https://github.com/radfordneal/LDPC-codes 12. https://github.com/quiet/libcorrect 48 A . SOFTWARE DOCUMENTATION • enc_char_lld. c, enc_char_187. c encode block using _char encoder with different generator polynomials multiple times. As arguments, they require number of symbols in codeword (n) and a number of source symbols (k). • dec_erasures_char_lld.c and dec_erasures_char_187.c decodes blocks with known positions of erased symbols. • dec_errors_char_lld. canddec_errors_char_187. c decodes blocks with unknown positions of erroneous symbols. In directory libs/jerasure.git/Examples • encoder. c and decoder. c were provided with the library. However, we adjusted the time measurement - we used getrusage. • Files ending with enc. c or dec. c are our implementations of encoders and decoders of Jerasure. They require varying arguments - more specified in the source code. In directory libs/openfec_vl.4.2/tests • ldpc_enc. c is our implementation of encoder from the library OpenFEC. It requires as arguments the number of source symbols and the number of symbols in codeword. • Our implementation of the decoder can be found in this directory too. However, to construct graphs, we used the implementation of performance measurement which offers the library OpenFEC because of great capabilities of these tools (see A p pendix B). In directory libs • isa-l_encode_decode. c is the adjusted encoder and decoder (provided by the library ISA-L) for our use - it measure time using getrusage and runs the test multiple times to minimise variations in results. 49 A . SOFTWARE DOCUMENTATION A.4 Scripts The executable scripts in the root directory perform each different task. • conf igure. sh tries to automate the compilation of libraries. • run_tests . sh runs tests by running the executable scripts in the directory scripts. To run this script, we need to run the script conf igure. sh. • plot_graphs . sh creates graphs in the directory results (in eps format) from the csv files and by the dem files. This script requires the tool gnuplot to be installed and it can be run even without configure. sh and run_tests. sh because in the directory results can be found results from our experimentations. If this script is run with "r" as a parameter then it removes all the eps files. The executable scripts in the directory scripts run the demonstration programs. • Libfec scripts (start with l i b f ec_) measure the encoding and decoding performance for 2 different polynomials, with symsize = 8 and no padding. The performance of the encoding and decoding of Libfec implementation in Veritysetup is done by creating a device with command dd and filling it with random data from /dev/urandom. For corruption of the device is used script corrupt_vs_dev. sh which corrupts the maximum amount of blocks tolerated by decoder. The Veritysetup decodes the erroneous blocks, however, it doesn't correct them on device - we should consider adding the possibility to correct data in Veritysetup (in user-space), for now it only finds out if the device can be corrected and prints the number of errors. • The files jerasure_erasure_enc. sh, j erasure_erasure_dec.sh and jerasure_raid_enc_dec. sh utilise the encoder and decoder provided in the library Jerasure which is modified for my tests. They demonstrate how this library intends to work with data - separate them into k blocks, compute redundant m 50 A . SOFTWARE DOCUMENTATION blocks, erase random m blocks, recreate the original k blocks and compare the recovered data with the original data. This works fine, however, we implemented these encoders and decoders individually for each algorithm to compare results - they could be found in directory libs/jerasure.git/Examples (ending with _enc. c and _dec. c). • Tests for LDPC encoding are in l d p c e n c . sh. 51 B LDPC tests The library OpenFEC1 provides tools for measurement of recovering performance. The executable scripts can be found in the directory libs/openfec_vl.4.2/perf_eval: • run_tests . p i runs the tests specified by input file. In the input file can be specified number of iterations, symbol size, code rate and other properties. The documentation for this file can be found in file libs/openfec_vl.4.2/perf_eval/params.txt. • plot_graphs . p i plots the graphs from the results. The results directories that can be found in the directory libs/openfec_vl.4.2/ perf_eval are from my experiments. In Figure B.l is the sample graph produced by these tools. It records the average decoding speed and the minimal and maximal values that were measured. In Figure B.2 is represented the decoding capabilities of the implemented decoder for same code rate and Nl. 20 25 loss percentage Figure B.l: Decoding speed for code with CR=2/3 and Nl=7. 1. http://openfec.org/ 53 B. LDPC TESTS 1.00000 & 0.10000 2 0.01000 o 0.00100 CD 7D 0.00010 LDPC-Staircase (N1=7) CR=0.666 K=1024 Symb.S=4 20 25 30 loss percentage 35 1.00000 0.10000 0.01000 0.00100 0.00010 t- 1 1 r nb samples (tot. :26790 ) i LDPl-Staircase (N1=7) CR=0.666 k=1024 5000 7000 6000 4000 3000 2000 1000 in a> Q. E CD CD n E 1020 1030 1040 1050 1060 Number of received symbols Figure B.2: Decoding capabilities for code with CR=2/3 and Nl=7. 54 Bibliography 1. H A M M I N G , R. W. Error detecting and error correcting codes. The Bell System Technical Journal [online]. 1950, vol. 29, pp. 147-160 [visited on 2018-04-05]. ISSN 0005-8580. Available from: https : //archive. org/details/bstj29-2-147. 2. T H O M P S O N , T. M . From Error-Correcting Codes Through Sphere Packings to Simple Groups. 1st ed. Mathematical Association of America, 1983. ISBN 9780883850374. Available also from: http: //www. j stor. org/stable/10.4169/j.ctt5hh9fv. 3. S H A N N O N , C. E. A Mathematical Theory of Communication. SIGMOBILE Mob. Comput. Commun. Rev. [online]. 2001, vol. 5, no. 1, pp. 3-55 [visited on 2018-04-05]. ISSN 1559-1662. Available from: http://doi.acm.org/10.1145/584091.584093. 4. MICHELONI, R. et al. Error Correction Codes for Non-Volatile Memories. 1st. Springer Publishing Company, Incorporated, 2010. ISBN 9048178649, 9789048178643. 5. REED, I. S. A brief history of the development of error correcting codes. Computers & Mathematics with Applications [online]. 2000, vol. 39, no. 11 [visited on 2018-04-05]. ISSN 0898-1221. Available from: www . sciencedirect.com/science/article/pii/S0898122100001127. 6. TAHIR, B.; SCHWARZ, S.; RUPP, M . BER comparison between Convolutional, Turbo, LDPC, and Polar codes. In: 2017 24th International Conference on Telecommunications (ICT) [online]. Limassol, Cyprus: IEEE, 2017 [visited on 2018-04-05]. Available from: ieeexplore . ieee.org/document/7998249/. 7. H A M K I N S , J. et al. Formulation of Forward Error Correction Coding Recommendations for Future N A S A Space Communications. In: 2008 IEEE Aerospace Conference [online]. 2008, pp. 1-18 [visited on 2018-04-05]. ISSN 1095-323X. Available from: https: //ieeexplore. ieee.org/document/4526321/. 55 BIBLIOGRAPHY 8. SHIH, C ; X U , Y.Y.; W A N G , Y Secure and Reliable IPTV Multimedia Transmission Using Forward Error Correction. International Journal of Digital Multimedia Broadcasting [online]. 2012 [visited on 2018-04-05]. Available from: https : //www. hindawi . com/j ournals/ ijdmb/2012/720791/. 9. MORELLO, A.; MIGNONE, V. DVB-S2X: The New Extensions to the Second Generation DVB Satellite Standard DVB-S2. Int. f. Satell. Commun. Netw. [online]. 2016, vol. 34, no. 3, pp. 323-325 [visited on 2018-04-05]. ISSN 1542-0973. Available from: https: //doi . org/10. 1002/sat.ll67. 10. IEEE Standard for Information technology- Local and metropolitan area networks- Specific requirements- Part 11: Wireless L A N Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput. IEEE Std 802.11n-2009 (Amendment to IEEE Std 802.11-2007 as amended by IEEE Std 802.11k-2008, IEEE Std 802.11r-2008, IEEE Std 802.11y- 2008, and IEEE Std 802.11w-2009) [online], pp. 1-565 [visited on 2018-04-05]. Available from: https : / / ieeexplore . ieee . org/ document/5307322/. 11. G N A N A S U N D A R A M , S.; SHRIVASTAVA, A. Information storage and management: storing, managing, and protecting digital information in classic, virtualized, and cloud environments. 2nd ed. John Wiley & Sons, 2012. 12. WEIL, S. A . et al. Ceph: A scalable, high-performance distributed file system. In: Proceedings of the 7th symposium on Operating systems design and implementation [online]. Berkeley, C A , 2006, pp. 307-320 [visited on 2018-04-05]. Available from: https : / / d l . acm . org/ citation.cfm?id=1298485. 13. Y U A N , Z.; Z H A O , X. Introduction of forward error correction and its application. In: 2nd International Conference on Consumer Electronics, Communications and Networks (CECNet) [online]. Three Gorges, YiChang, Hubei, China, 2012 [visited on 2018-04-05]. Available from: https://ieeexplore.ieee.org/document/6201904/. 14. M A S N I C K , M . Patent Troll Kills Open Source Project On Speeding Up The Computation Of Erasure Codes [online]. Techdirt, 2014 [visited on 2018-04-05]. Available from: https : / /www . techdirt . com/ 56 BIBLIOGRAPHY articles / 20141115 / 07113529155 /patent - t r o l l - k i l l s - opensource - pro j ect - speeding - up - computation - erasure - codes . shtml. 15. P L A N K , J. S. et al. A Performance Evaluation and Examination of Open-Source Erasure Coding Libraries for Storage. In: 7th USENIX Conference on File and Storage Technologies (FAST 09) [online]. San Francisco, CA: USENIX Association, 2009 [visited on 2018-04-05]. Available from: https : //www. usenix. org/legacy/event/f ast09/ tech/full_papers/plank/plank_html/. 16. S C H M A L E N , L.; A L V A R A D O , A.; RIOS-MULLER, R. Performance Prediction of Nonbinary Forward Error Correction in Optical Transmission Experiments. Journal of Lightwave Technology [online]. 2017, vol. 35, no. 4 [visited on 2018-04-05]. ISSN 0733-8724. Available from: https://ieeexplore.ieee.org/document/7570166/. 17. OGUZ, N . C ; A Y A N O G L U , E. Performance analysis of two-level forward error correction for lost cell recovery in A T M networks. In: INFOCOM '95. Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Bringing Information to People. Proceedings. IEEE [online]. Boston, M A : IEEE, 1995 [visited on 2018-04-05]. ISSN 0743-166X. Available from: https : //ieeexplore. ieee. org/ document/515852/. 18. SAAD, R. et al. Evaluating Forward Error Correction performance in BitTorrent protocol. In: IEEE Local Computer Network Conference [online]. Chickago, IL: IEEE, 2010 [visited on 2018-04-05]. ISSN 0742- 1303. Available from: https : //ieeexplore . ieee . org/document/ 5735842/. 19. The Digital Universe of Opportunities: Rich Data and the Increasing Value of the Internet of Things [online]. EMC, 2014 [visited on 2017-12-09]. Available from: https : / /www . emc . com /leadership / d i g i t a l - universe/2014iview/executive-summary.htm. 20. Introduction to RAID [online]. Cisco, 2018 [visited on 2018-04-05]. Available from:https://www.cisco.com/c/en/us/td/docs/unified_ computing/ucs/c/sw/raid/conf igurat ion/guide/RAID_ GUIDE/ IntroToRAID.html. 57 BIBLIOGRAPHY 21. SCHROEDER B.and Gibson, G . A Disk Failures in the Real World: What Does an MTTF of 1,000,000 Hours Mean to You? In: 5th USENIX Conference on File and Storage Technologies (FAST 09) [online]. San Jose, CA: USENIX Association, 2007 [visited on 2018-04-05]. Available from: http://www.cs.toronto.edu/~bianca/papers/fast07. pdf. 22. Why RAID is Deadfor Big Data Storage [online]. Cleversafe, 2011 [visited on 2018-04-05]. Available from: http : / /docs . media . bitpipe . com/io_10x/io_ 103356/item_496432/Cleversafe0 /„20-°/„20Why°/o 20RAID, /.20is, /.20Dead, /.20for, /.20Big, /.20Data, /.20Storage.pdf. 23. BENJAMIN, M . et al. A saga of smart storage devices: an overview of object storage. ;login:, the Magazine of USENIX [online]. 2014, vol. 39, no. 1 [visited on 2018-04-05]. Available from: https: //www. usenix. org/system/f iles/login/articles/02_benj amin.pdf. 24. Red Hat Ceph Storage 2: Architecture Guide [online]. Red Hat, 2018 [visited on 2018-04-05]. Available from: https : / / access . redhat . com / documentation / en - us / red _ hat _ ceph _ storage / 2 / pdf / architecture_guide/Red_Hat_Ceph_Storage-2- Architecture_ Guide-en-US.pdf. 25. DINABURG, A. Bitsquatting: D N S Hijacking without Exploitation [online]. 2011 [visited on 2018-04-05]. Available from: https : // media.blackhat.com/bh-us-ll/Dinaburg/BH_US_ll_Dinaburg_ Bitsquatting_WP.pdf. 26. MITRA, S. et al. Robust system design with built-in soft-error resilience. Computer [online]. 2005, vol. 38, no. 2, pp. 43-52 [visited on 2018-04-05]. ISSN 0018-9162. Available from: https : / /media . blackhat . com / bh - us - 11 / Dinaburg / BH _ US _ 11 _ Dinaburg _ Bitsquatting_WP.pdf. 27. N G U Y E N , H . T. et al. Chip-level soft error estimation method. IEEE Transactions on Device and Materials Reliability [online]. 2005, vol. 5, no. 3, pp. 365-381 [visited on 2018-04-05]. ISSN 1530-4388. Available from: https://ieeexplore.ieee.org/document/1545897/. 58 BIBLIOGRAPHY 28. O ' G O R M A N , T.J. et al. Field testing for cosmic ray soft errors in semiconductor memories. IBM Journal of Research and Development [online]. 1996, vol. 40,no. 1,pp. 41-50 [visited on 2018-04-05]. ISSN 0018- 8646. Available from: https : //ieeexplore . ieee . org/document/ 5389436/. 29. NI, X. et al. ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection. In: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis [online]. Denver, Colorado: A C M , 2013 [visited on 2018-04-05]. Available from: http: //doi. acm. org/10.1145/2503210.2503266. 30. Cutting-edge hack gives super user status by exploiting DRAM weakness [online]. Ars Technica, 2015 [visited on 2018-04-05]. Available from: https://arstechnica.com/information-technology/2015/03/ cutting-edge-hack-gives-super-user-status-by-exploiting- dram-weakness/. 31. XU, J. et al. A n experimental study of security vulnerabilities caused by errors. In: 2001 International Conference on Dependable Systems and Networks [online]. Goteborg, Sweden: IEEE, 2001, pp. 421-430 [visited on 2018-05-05]. Available from: https : / /ieeexplore . ieee . org/abstract/document/941426/. 32. B O N E H , D.; DEMILLO, R.A.; LIPTON, R.J. O n the importance of checking cryptographic protocols for faults. In: International conference on the theory and applications of cryptographic techniques [online]. Springer, 1997, pp. 37-51 [visited on 2018-05-05]. Available from: https : / / l i n k , springer . com/chapter/10 . 1007/3-540-69053- 0_4. 33. A N D E R S O N , R.; K U H N , M . Tamper Resistance - a Cautionary Note in proceedings of the Second USENIX Workshop on Electronic Commerce Proceedings [online]. Oakland, CA, 1996 [visited on 2018-05-05]. Available from: https : / /www . usenix . org/legacy/publications / library/proceedings/ec96/full_papers/kuhn/. Technical re- port. 34. GOVINDAVAJHALA, S.; APPEL, A.W. Using memory errors to attack a virtual machine. In: Symposium on Security and Privacy, 2003. [online]. Berkeley, CA: IEEE, 2003, pp. 154-165 [visited on 2018-05-05]. 59 BIBLIOGRAPHY ISSN 1081-6011. Available from: https : //ieeexplore . ieee. org/ abstract/document/1199334/. 35. KURTAS, E. M . ; VASIC, B. Advanced error control techniques for data storage systems. CRC Press, 2005. 36. TOMLINSON, M . et al. Error-Correction Coding and Decoding. Springer, 2017. ISBN 978-3-319-51103-0. 37. H E H N , T.; HUBER, J.B. L D P C codes and convolutional codes with equal structural delay: a comparison. Journal of the societyfor industrial and applied mathematics [online]. 1960, vol. 8, no. 2, pp. 300-304 [visited on 2018-05-05]. Available from: https: //ieeexplore. ieee. org/document/5089507/. 38. C O H E N , G. et al. Covering codes. Elsevier, 1997. ISBN 0444825118. 39. PAAR, Christof; PELZL, Jan. Understanding cryptography: a textbookfor students and practitioners. Springer Science & Business Media, 2009. ISBN 978-3-642-04100-6. 40. M . , Greenan K. et al. Optimizing Galois Field Arithmetic for Diverse Processor Architectures and Applications. In: 2008 IEEE International Symposium on Modeling, Analysis and Simulation of Computers and Telecommunication Systems. Baltimore, M D , 2008, pp. 1-10. ISSN 1526-7539. 41. P L A N K , J. S. Erasure Codes for Storage Applications. In: 4th USENIX Conference on File and Storage Technologies (FAST 05) [online]. San Francisco, C A : USENIX Association, 2005 [visited on 2018-04-05]. Available from: https : / /web . eecs . utk . edu/ -plank /plank/ papers/FAST-2005.pdf. 42. Q., Shi Y. et al. Interleaving for combating bursts of errors. IEEE Circuits and Systems Magazine [online]. 2004, vol. 4, no. 1, pp. 29^2 [visited on 2018-05-05]. ISSN 1531-636X. Available from: https : //ieeexplore.ieee.org/document/1286985/. 43. REED, I.S.; SOLOMON, G. Polynomial codes over certain finite fields [online] [visited on 2018-05-05]. Available from: https : //epubs . siam.org/doi/abs/10.1137/0108018?j ournalCode=smjmap.1. 44. WICKER, S.B.; BHARGAVA, V.K. Reed-Solomon codes and their applications. John Wiley & Sons, 1999. ISBN 9780780353916. 60 BIBLIOGRAPHY 45. BLAHUT, R E . Theory and practice of error control codes. Addison-Wesley Reading (Ma) etc., 1983. ISBN 9780201101027. 46. P L A N K , J. S.; X U , L. Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Network Storage Applications. In: Fifth IEEE International Symposium on Network Computing and Applications (NCA'06). Cambridge, M A , 2006, pp. 173-180. 47. BRAUCHLE, J.; KOETTER, R. A Systematic Reed-Solomon Encoder with Arbitrary Parity Positions. In: GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference. Honolulu, HI, 2009, pp. 1-4. ISSN 1930-529X. 48. BLOMER, J. et al. A n XOR-Based Erasure-Resilient Coding Scheme. In: Technical Report TR-95-048 [online]. 1995 [visited on 2018-05-05]. Available from: f t p : //ftp. i c s i .berkeley. edu/pub/techreports/ 1995Ar-95-048.pdf. 49. GALLAGER, R. Low-density parity-check codes [online] [visited on 2018-05-05]. Available from: https : / / ieeexplore . ieee . org/ abstract/document/1057683/. 50. M A C K A Y , D.J.C.; N E A L , R.M. Near Shannon limit performance of low density parity check codes. Electronics Letters [online]. 1996, vol. 32, no. 18 [visited on 2018-05-05]. ISSN 0013-5194. Available from: https : / / ieeexplore . ieee . org / abstract / document / 533358/. 51. Z H O U , B. et al. Non-binary L D P C codes vs. Reed-Solomon codes. In: 2008 Information Theory and Applications Workshop [online]. San Diego, CA: IEEE, 2008, pp. 175-184 [visited on 2018-05-05]. Available from: https : //ieeexplore . ieee . org/abstract/document/ 4601044/. 52. MATTOUSSI, F. Design and optimization ofAL-FEC codes: the GLDPCStaircase codes [online]. Grenoble, 2014 [visited on 2018-05-05]. Available from: https://tel.archives-ouvertes.fr/tel-00969573/ document. PhD thesis. Universite de Grenoble. 53. A N V I N , H . P The mathematics of RAID-6 [online]. 2004 [visited on 2018-05-05]. Available from: https: //mirrors . edge .kernel. org/ pub/linux/kernel/people/hpa/raid6.pdf. 61 BIBLIOGRAPHY 54. B L A U M , M . ; ROTH, R.M. On lowest density MDS codes. IEEE Transactions on Information Theory [online]. 1999, vol. 45, no. 1, pp. 46- 59 [visited on 2018-05-05]. ISSN 0018-9448. Available from: https: //ieeexplore.ieee.org/document/746771/. 55. P L A N K , J.S. The RAID-6 Liberation Codes. In: FAST-2008: 6th Usenix Conference on File and Storage Technologies [online]. San Jose, C A : USENIX Association, 2008 [visited on 2018-05-05]. Available from: http : / /web.eecs.utk.edu/~plank/plank/papers/FAST-2008. html. 56. P L A N K , J.S. The Raid-6 Liber8Tion Code. Int. J. High Perform. Comput. Appl. [online]. 2009, vol. 23,no. 3,pp. 242-251 [visited on2018-05-05]. ISSN 1094-3420. Available from: https : / / d l . acm. org/citation. cfm?id=1572227. 57. P L A N K , J.S. et al. Minimum density RAID-6 codes. ACM Transactions on Storage (TOS) [online]. 2011, vol. 6, no. 4 [visited on 2018-05-05]. Available from: https : //dl. acm. org/citation. cf m?id=1970338. 1970340. 58. B L A U M , M . ; ROTH, R.M. On lowest density MDS codes. IEEE Transactions on Information Theory [online]. 1999, vol. 45, no. 1, pp. 46- 59 [visited on 2018-05-05]. ISSN 0018-9448. Available from: https: //ieeexplore.ieee.org/abstract/document/746771/. 59. H A B I N C , S. A CCSDS Reed-Solomon Encoder Core and Radiation Hard Device. In: ESA Workshop on Microeletronicsfor Satellite Aplications [online]. Noordwijk, The Netherlands: European Space Agency, 1996 [visited on 2018-05-05]. Available from: microelectronics . esa.int/vhdl/doc/Rescue.pdf. 60. ROCA, V.; N E U M A N N , C ; FURODET, D. Eow Density Parity Check (EDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes [Internet Requests for Comments]. RFC Editor, 2008 [visited on 2018-05-05]. ISSN 2070-1721. Available from: https: //tools. i e t f . org/html/rf c5170. RFC. RFC Editor. 61. Y U A N , X.; S U N , R.; PING, L. Simple capacity-achieving ensembles of rateless erasure-correcting codes. IEEE Transactions on Information Theory [online]. 2010, vol. 58, no. 1, pp. 110-117 [visited on 2018-05-05]. ISSN 0090-6778. Available from: https: //ieeexplore. ieee.org/document/5397905/. 62