Applied Erasure Coding in Networks and Distributed Storage

The amount of digital data is rapidly growing. There is an increasing use of a wide range of computer systems, from mobile devices to large-scale data centers, and important for reliable operation of all computer systems is mitigating the occurrence and the impact of errors in digital data. The demand for new ultra-fast and highly reliable coding techniques for data at rest and for data in transit is a major research challenge. Reliability is one of the most important design requirements. The simplest way of providing a degree of reliability is by using data replication techniques. However, replication is highly inefficient in terms of capacity utilization. Erasure coding has therefore become a viable alternative to replication since it provides the same level of reliability as replication with significantly less storage overhead. The present thesis investigates efficient constructions of erasure codes for different applications. Methods from both coding and information theory have been applied to network coding, Optical Packet Switching (OPS) networks and distributed storage systems. The following four issues are addressed: - Construction of binary and non-binary erasure codes; - Reduction of the header overhead due to the encoding coefficients in network coding; - Construction and implementation of new erasure codes for large-scale distributed storage systems that provide savings in the storage and network resources compared to state-of-the-art codes; and - Provision of a unified view on Quality of Service (QoS) in OPS networks when erasure codes are used, with the focus on Packet Loss Rate (PLR), survivability and secrecy.


List of Figures
1.1 50-fold growth of the amount of digital data from 2010 to 2020 [IDC12]. -The Introduction chapter (Chapter 1) presents the motivation for applying erasure codes in different networks.
-The Background and Related Works chapter (Chapter 2) gives the necessary background to understand the contributions of the thesis. It also reviews the state-of-the-art for erasure coding, algorithms for header compression in network coding, code constructions for distributed storage and QoS metrics in OPS networks. Some of the challenges faced by the coding and the networking communities that are addressed in the present thesis are listed in the end of each section.
-The Contributions and Concluding Remarks chapter (Chapter 3) presents the research questions answered in the present thesis and the research contributions and results obtained during the PhD period. It also puts the presented research results into a wider context by comparing them to selected references. Finally, conclusions followed by suggestions for future work are presented.
Part II consists of 7 papers where 6 are published and 1 is submitted for publication (Table 3.1).

Motivation
The relentless data growth brings enormous challenges, as well as incredible research and business opportunities. IDC [IDC12] estimates that the total amount of digital data created, replicated and consumed will reach 40000 exabytes, or 40 trillion gigabytes, by 2020. From now until 2020, the amount of digital data is expected to double every two years, as shown in Figure 1.1. Reliable communication through unreliable media is paramount in modern communication systems. Reliable communication requires that all intended receivers of the data receive the data intact, i.e. data must be transferred without errors or loss. The demand for efficient and reliable communication has been accelerated even more by the emergence of large-scale, high-speed data networks for exchange, processing and storage of digital information in public and private spheres. Reliability is achieved by adding redundancy at different levels in the protocol stack. One way is to use Forward Error Correction (FEC) codes as error correction or erasure codes. FEC codes preprocess the data in such a way to provide recovery after data corruption [CC81].
Erasure coding has emerged as a compliment, or an alternative, to Automatic Repeat reQuest (ARQ) and replication in communication networks and distributed storage systems, respectively.
Using erasure coding, or combining it with ARQ, is a better solution instead of only using ARQ. When the PLR is very high, then retransmissions happen frequently and the system throughput is reduced significantly. In this case, combining ARQ with FEC known as Hybrid Automatic Repeat reQuest (HARQ) [CC84,LY82] is useful. ARQ is not feasible for unidirectional broadcast networks or real-time applications, because a return channel may not exist or the Round Trip Time (RTT) delay may be too large. Additionally, when the number of users is very large, scalability issues may prevent the use of return channels. In all these scenarios, the use of erasure codes is imminent.
Replication is not an appropriate enabler of the exabyte era because it increases enormously the storage overhead. Let us take the following example where 3replication and an (9, 6) erasure code provide a similar level of reliability. Three copies of the same file are stored with 3-replication, while the file is divided into 6 fragments and 3 redundancy fragments when constructed with an (9, 6) erasure code. The storage overhead is 200% with 3-replication, while it is only 50% with the erasure code. In this example, erasure coding reduces the cost of storage by 150%, which is a tremendous cost saving when storing exabytes of data. Erasure coding has a clear advantage over replication as it provides the same level of reliability with less storage overhead [WK02].
Although many different erasure codes have been developed, there is no erasure code construction that provides simultaneously optimal performance and reliability. Maximum Distance Separable (MDS) codes such as Reed-Solomon codes [RS60] are fault tolerant optimal, but they are computationally expensive in practice. Low Density Parity Check (LDPC) codes [Gal63] do not offer the same fault tolerance as MDS codes, but tend to be computationally inexpensive and may have regular or irregular fault tolerance. Random Linear Network Coding (RLNC) is a flexible coding scheme that does not follow a predesigned code. Depending on the finite field size, the codes can be fault tolerant optimal. Then the codes are computationally demanding as Reed-Solomon codes. Both the underlying system and the application have a huge impact on which coding scheme gives the best performance. For instance, erasure coding has been currently deployed in Windows Azure [HSX + 12], big data analytics clusters (e.g. Facebook Analytics Hadoop cluster [SAP + 13]), archival storage systems, and peerto-peer storage systems like Cleversafe. Facebook has recently reported that it is archiving old data using a classical Reed-Solomon erasure code implemented on the top of HDFS[SAP + 13], while Microsoft uses a pyramid code as the main storage primitive of its Azure storage service [HCL13]. Reed-Solomon codes, that are the essential building blocks in RAID 6, are optimal in terms of storage capacity utilization in large-scale distributed storage systems, but they perform poorly in terms of other system resources such as disk I/O and network bandwidth. During a recovery of lost or otherwise unavailable data, classical Reed-Solomon codes require a large amount of data to be read and transferred across the network.
Accordingly, the work presented in this thesis has been directed towards constructing efficient erasure codes for different applications. The four topics covered in the present thesis are: -Construction of binary erasure codes (Paper 1 and Paper 2); -Reduction of the header overhead due to coding coefficients in network coding (Paper 3);

Background and Related Works
In this Chapter we review the background and the related works in the main research areas of this dissertation: erasure coding (Section 2.1), header compression algorithms for network coding (Section 2.2), code constructions for distributed storage systems (Section 2.3) and optical packet switched networks (Section 2.4).

Coding Theory
Data reliability, regardless of the medium, is achieved by adding redundancy. FEC (Forward Error Correction) codes are either used as error correction or erasure codes. Error correction codes are usually used at lower layers of the protocol stack, either as standalone codes or in conjunction with error detection checksums (e.g. Cyclic Redundancy Checksum (CRC)) [PB61]. The upper layers deal with erasures (missing data units) after reception or storage/retrieval. Erasure codes are typically used in situations where the exact positions of the missing data units are known a priori (e.g. disk array). In many cases, error correction and erasure codes use the same encoding algorithm but have different decoding algorithms. Since FEC codes treat each symbol as an element of a finite field and they perform extensively operations in finite fields, i.e. Galois fields, first a very brief introduction to Galois fields is given. For a more detailed description of Galois fields, please refer to [LN86].

Galois fields
Finite fields F q , also known as Galois fields GF (q), are fundamental to coding theory. We use both notations F q and GF (q) interchangeably through the present thesis. The main advantage of using a Galois field is its closure property. A field is closed under both addition and multiplication meaning that the result of addition and multiplication of field elements is still a field element. Both operations are associative, distributive and commutative. Every non-zero element has a multiplicative inverse and every element has an inverse additive (negative) element. Working with data in transit or with data at rest in a Galois field means that the data elements are mapped into field elements, the performed operations follow the rules of the field and the data is reconstructed by inverse mapping.
The order of GF (q) is the number of elements in the field. There exists a finite field of order q if, and only if, q is a prime power, i.e. q = p m where p is a prime number called the characteristic of the field, and m is a positive integer. If m = 1, then the field is called a prime field. Working in a prime field GF (p) is quite simple. The prime field is the set of elements from 0 to p − 1 under the operations of addition and multiplication modulo p.
If m ≥ 2, then the field is called an extension field. Galois fields of order 2 m are called binary extension fields. These fields are used ubiquitously in coding theory and cryptography. One way of representing the elements in GF (2 m ) is to use a set of polynomials of degree at most m − 1 where the coefficients are from the binary field GF (2) = {0, 1}: (2.1) Thus, the 4-bit element a = (1, 1, 1, 0) 2 4 has the following polynomial representation The field GF (2 m ) is defined over an irreducible polynomial f (x) of degree m with coefficients from GF (2). An irreducible polynomial is analogous to a prime number in that it cannot be factored as a product of polynomials each of degree less than m. Addition in GF (2) is done with the bitwise XOR operator, while multiplication is performed with the bitwise AND operator. Addition in GF (2 m ) is the usual addition of polynomials with coefficient arithmetic performed modulo 2, while multiplication is more complex. Multiplication of two field elements a and b is performed by polynomial multiplication of a(x) and b(x) and then the product Another useful property of any finite field GF (q) is that the set of all nonzero elements GF (q) × = GF (q) \ 0 form a multiplicative cyclic group (GF (q) × , ×). That means that any nonzero element a ∈ GF (q) × can be represented as a power of a single element α ∈ GF (q) × . Such a generator α is called a primitive element of the finite field. Powers of α repeat with a period length of q − 1, thus, α q−1 = α 0 = 1. This makes multiplication of two elements a = α i and b = α j quite simple and fast. If we write i = log(a) and a =antilog(i), then the product of a, b ∈ GF (2 m ) is computed as ab =antilog(log(a) + log(b)) mod 2 m − 1.

Erasure Coding
Erasure codes, in particular linear block codes, are most appropriate for the applications such as data transmission and storage, which are of interest to the present thesis. The background presented in this subsection is essential to fully understand 2.1. CODING THEORY 9 the work in the present thesis. Some terminology and definitions can be found in [LC83,Pla05].
A block encoder, according to certain rules, transforms each input message of k information symbols into a message of n symbols (n > k). This message of n symbols is called a codeword. If the alphabet of the information source contains q different digits, then there are a total of q k distinct messages of k symbols. To each of the q k possible messages a unique codeword is assigned. This set of q k codewords of n symbols is called a q-ary block code of length n.
Definition 2.1. A block code of length n and q k codewords is called a linear (n,k) code if and only if its q k codewords form a k-dimensional subspace of the vector space of all n-tuples over the finite field GF (q).
The code rate R, or code efficiency, is defined as R = k n . The error detection and error correction capabilities of a (n, k, d) code are defined by its metric, the minimum distance d. Before defining d, it is first necessary to define the Hamming weight of a codeword and the Hamming distance between two codewords.
Definition 2.2. The Hamming weight w H (c) of a codeword c is the number of non-zero elements in c.
Definition 2.3. The Hamming distance d H (c 1 , c 2 ) between two codewords c 1 and c 2 , that have the same number of elements, is the number of elements in which these two codewords differ.
Consider the two codewords c 1 = (0, 1, 0, 0, 1) and c 2 = (1, 1, 0, 1, 1). The Hamming weights of c 1 and c 2 are w H (c 1 ) = 2 and w H (c 2 ) = 4, respectively, while Definition 2.4. The minimum distance of a (n, k) block code C, denoted by d, is the minimum among the Hamming distances between any two different codewords from C. A block code C of length n, q k codewords and minimum distance d is denoted by (n, k, d) code C.
Theorem 2.5. [Sin64] For a (n, k, d) q linear code we have (

2.2)
Codes for which the equality holds are known as Maximum Distance Separable (MDS) codes.
When MDS codes are used as erasure codes, the receiver can recover the k source symbols from any subset of k received symbols out of the n encoded symbols.
The Singleton defect of a (n, k, d) code C, that is defined as s(C) = n − k + 1 − d, measures how far away is C from being a MDS code. Based on the Singleton defect, the codes are divided in two classes: Definition 2.6. A (n, k, d) code C is (i) t-error detecting code iff its minimum distance is at least t + 1; (ii) t-error correcting code iff its minimum distance is at least 2t + 1.
As mentioned earlier, a linear code constitutes a subspace and thus any codeword can be represented by a linear combination of the basis vectors of the subspace, i.e. by a linear combination of linearly independent vectors. The basis vectors can be written as rows of a k × n matrix.
Definition 2.7. Any matrix G ∈ F k×n q whose rows form a basis of C is called a generator matrix for C, i.e.
The injective map F k q F n q , x xG encodes all the q-ary words of length k to words of length n.
A generator matrix is called systematic if it is of the form where I k is an identity matrix of order k and P is a k × (n − k) parity submatrix. The code can either be systematic or non-systematic. The generator matrix of a systematic code has the same form as the matrix represented in (2.4). That means that a systematic linear code does not transform the original k data symbols, but it only generates extra r redundant symbols. If the first k rows in G do not contain an identity matrix, then the code is non-systematic. That is to say, all n generated symbols linearly depend on all original k symbols via G. Systematic codes are less computationally demanding than non-systematic, since they do not require processing of the original data.
Given a generator matrix G of a linear code we can derive its parity-check matrix H (and vice versa).
Codes with generator matrices that are sparse and balanced minimize the maximal computation time of computing any code symbol. The problem of constructing balanced and sparse codes was studied in [DSDY13,HLH16].
Theorem 2.9. [DSDY13] Suppose 1 ≤ k ≤ n and q > n−1 k−1 . Then there always exits a (n, k) q MDS code that has a generator matrix G satisfying the following two conditions: -Sparsest: each row of G has weight n − k + 1; and -Balanced: column weights of G differ from each other by at most one.
Let us explain the encoding and decoding of data with a (8, 5) MDS code. As shown in Figure 2.1, k = 5 source data units represented as a row vector x are encoded into n = 8 data units (a row vector y) with the systematic generator matrix G of a (8, 5) MDS code. The coefficients c i,j , i = 1, . . . , 5 and j = 1, 2, 3, are elements from GF (q). The encoder in Figure 2.2 performs this multiplication. Next, the data is transmitted through unreliable medium to the receiver. Some of the data units may get corrupted (lost) during the transmission. Since the code is MDS, at most 3 data units can be lost. In this example, x 1 , x 4 , r 2 are lost. Namely, the decoder has to receive at least 5 data units in order to reconstruct the source data. Recovery of the source data is done by where x is the source data and y is the subset of k components available at the decoder. The matrix G is the subset of columns from G corresponding to the components of y . The source data x can be reconstructed only if G is non-singular. This means, in general cases, any k × k submatrix extracted from G has to be invertible in order to recover from at most n − k lost data units. In the presented example, the matrix G is obtained by deleting the columns in G that correspond to 1' x 1 x 2 x 3 x 4 x 5 r 1 r 2 r 3 x 1 x 2 x 3 x 4 x 5 r 1 r 3 x 2 x 2 x 3 x 4 x 5

Figure 2.2:
A graphical representation of the encoding/decoding process. The encoder encodes k source units into n. The decoder has to receive at least k data units in order to reconstruct the source data.
Among all codes in the class of block codes, cyclic codes are the most important from practical point of view. Bose-Chaudhuri-Hocquenghem (BCH) codes were discovered independently in the papers by Bose and Chaudhuri (1960) [BRC60] and Hocquenghem (1959) [Hoc59]. BCH codes are cyclic codes that have algebraic decoding algorithms.
Reed Solomon (RS) codes were first described in a paper by Reed and Solomon in 1960 [RS60]. They are non-binary BCH codes defined by the parameters: n = q − 1, n − k = 2t, d = 2t + 1. Since the minimum distance is n − k + 1, RS codes are MDS codes. RS codes are widely implemented in storage devices and communication standards. RS encoding is relatively straightforward, but decoding is complex despite the significant efficiency improvements with Berlekamp-Massey algorithm [Ber68]. The two limitations of RS codes are: the small block size and the high decoding times. The length of a RS code is limited by the field size, for example, it is n ≤ 255 for GF (256). The larger Galois field is, the longer the code can be, but at the same time the operations are getting slower and more complex. Therefore, the values of n and k have to be small if high transmission rates are desired.
The introduction of Turbo codes [BGT93] and LDPC codes [Gal63, MN97, MN95] have been one of the most important milestones in channel coding during the last years. Provided that the information block length is long enough, both Turbo and LDPC codes achieve performance close to the Shannon theoretical limit. However, in practical applications, both schemes have some complexity issues. Specifically, the encoding complexity is very low, but the decoding is more complex with Turbo codes compared to LDPC codes. The contrary occurs for standard LDPC codes. The encoding is more complex with standard LDPC codes, but the decoding is simpler.
LDPC codes were first introduced by Gallager in 1960 [Gal63], but they were impractical for implementation in that time. As the computational power has increased, they become attractive for research and practical implementations. MacKay and Neal rediscovered them in 1995 [MN95]. LDPC codes are defined by sparse parity-check matrices. Sparse bipartite graphs are used to represent LDPC codes where one set of nodes, the variable nodes, corresponds to elements of the codeword and the other set of nodes, the check nodes, corresponds to the set of parity-check constraints which define the code. An example of a regular LDPC code where all nodes of the same type have the same degree is shown in Figure 2.4. The principle of using irregular graphs where the degrees of the variable and the check nodes can vary widely was introduced in [LMS + 97], and it was further studied in [LMSS01b,RSU01]. The degrees of each set of nodes are chosen according to some distribution. The decoding complexity for LDPC codes increases linearly with the block length. LDPC codes are asymptotically good and their recovery performance decreases for small blocks. Garcia-Frias and Zhong introduced Low-Density Generator Matrix (LDGM) codes that are constructed by using systematic sparse generator matrices [GFZ03]. They are a special class of LDPC codes with low encoding and decoding complexity. The amount of processing at the encoder is comparable to that of Turbo codes due to the sparseness of the generator matrix.
LDPC were significantly improved by Luby, Shokrollahi et al. that led to the invention of Tornado [BLMR98], LT [Lub02] and Raptor [Sho06] codes. Tornado codes are the precursor to fountain codes. Fountain or rateless codes are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. These codes do not have a fixed code rate and are known as rateless codes. Both LT and Raptor codes belong to the class of rateless codes.
The fundamental goal of the research presented in the present thesis is to construct erasure codes that have the following desirable properties:

Network Coding
Network coding as a research area was initiated by the seminal paper by Ahlswede et al. [ACLY00]. They made the key observation that intermediate nodes are allowed to carry out algebraic operations on the incoming data instead of only forwarding the incoming data. Before defining their main result, some essential terminology that can be found in [MS12, Law01, Bol79, RSK10] is introduced.
A communication network is defined as a tuple N = (V, E, S, T ) that consists of: where V is the set of vertices and E is the multiset of directed edge; -a set S ⊂ V of sources; and -a set T ⊂ V of sink nodes.
Vertices model communication nodes within the network, while directed edges model error-free communication channels between the nodes. An edge (i, j) has unit capacity in the sense that it can be used to reliably deliver one symbol from i to j. To allow for greater capacity from i to j, multiple edges between i and j are permitted, i.e. G is in general a multigraph. The capacity of an edge (i, j) ∈ E is given by R ij and let i.e. the total flow into node i is equal to the total flow out of node i.
F ij is referred to as the value of F in the edge (i, j). The value of F is defined as Definition 2.11. F is a max-flow from s to t l in G if F is a flow from s to t l whose value is greater than or equal to any other flow from s to t l .
Definition 2.12. A cut is a set of edges that partition the graph into two sets of vertices.
Definition 2.13. A minimal cut separating s and t is a cut of the smallest cardinality denoted as min-cut(s, t).
A min-cut(s, t) can be regarded as a bottleneck between s and t and it limits the information rate of the flow between s and t.
Theorem 2.14. [Law01]Max-Flow Min-Cut Theorem: For every non-source node t, the minimum value of a cut between the source and a node t is equal to max-flow(s, t).
It is well known from Menger's Theorem [Men] that the number of edge-disjoint paths from s to t is equal to max-flow. A collection of edge-disjoint paths can be found by the Ford-Fulkerson algorithm [FF]. Thus, in a single-sink network, the number of symbols transferred from s to t per time unit is equal to the min-cut of the network where each symbol is sent on a different edge-disjoint path.
Ahlswede et al. [ACLY00] showed that the multicast capacity for a single-source network, i.e. the maximum rate at which s can transfer information to the sinks, cannot exceed the capacity of any cut separating s from the sinks.

Theorem 2.15. [MS12]
The multicast rate R(s, T ) from s to T cannot exceed the transmission rate that can be achieved from s to any element of T . The multicast rate R(s, T ) must satisfy: (2.7) The quantity min t∈T min-cut(s, t) is referred to as the multicast capacity of the given network. The upper bound is achievable (with equality) via network coding [ACLY00].
Li et al. [LYC03] showed that Linear Network Coding (LNC) achieves the upper bound given that the finite field is sufficiently large.
Theorem 2.16. Adapted version of [LYC03,Th.5.1] from [RSK10]: Let q be a sufficient large power of 2. A symbol over F q is treated as a unit of information. In a directed, delay-free, acyclic graph, with a single source s and multiple sinks t 1 , . . . , t k and where the edges have integral capacity, if the capacity of the min-cut from the source to each of the k sinks is at least ν, then there exists a linear network solution that delivers ν units of information to each of the k sinks simultaneously.

NETWORK CODING 17
Koetter and Médard extended further the work by Li et al. [LYC03] to arbitrary networks and robust networking. In [KM03], they presented an algebraic framework for investigating coding rate regions in networks using linear codes.
An efficient distributed randomized approach that asymptotically achieves the capacity for general multi-source multicast networks is presented in [HMK + 06]. Random Linear Network Coding (RLNC) is a simple, randomized coding method that maintains "a vector of coefficients for each of the source processes," which is "updated by each coding node". In other words, RLNC requires messages being communicated through the network to be accompanied by some degree of extra information (a vector of coefficients). The vector of coefficients is updated at each node that performs network coding.
Another definition of network coding is coding at a node in a packet network (where data is split into packets and network coding is applied to the content of packets). We use this definition in the sequel.
A well-known benefit of network coding is an increase of the throughput. This is achieved by using packet transmissions more efficiently, i.e. by communicating more information with fewer packet transmissions. The famous butterfly network in Figure  2.5 illustrates this. Assume that the source node s wants to multicast two packets to the destinations t 1 and t 2 . Assume that the capacity of each link is 1 packet per time unit and the delay of each link is the same. The maximum throughput from the source node s to the destination nodes t 1 and t 2 is 2 packets per time unit, but the maximum throughput cannot be achieved simultaneously if only routing is allowed, since node n 3 can transmit either b 1 or b 2 but not both packets at the same time. Nevertheless, if node n 3 performs the exclusive-OR (XOR) operation on b 1 and b 2 and transmits the XOR-ed packet to node n 4 , then both destinations achieve the maximum throughput simultaneously. Node t 1 decodes correctly b 2 after it receives b 1 from node n 1 and the XOR-ed packet from node n 4 . It is similar for node t 2 .
At the expense of encoding operations at the intermediate nodes and decoding operations at the sink nodes, RLNC improves the network throughput, the efficiency and the scalability, as well as the resilience to attacks and eavesdropping [CY02,BN05]. Inspired by these gains, researchers have applied network coding in many applications such as wireless networks [KRH + 08, KHH + 13], distributed storage systems [ADMK05, DGW + 10], video streaming [NNC10], satellite networks [VB09] and distributed file sharing [WWX10,FR12,GR06].
However, there are some issues with practical implementation of network coding. In order to explain them easily, the generation of a coded packet y k in RLNC is presented in Figure 2.6. The file is divided into n packets of length l and encoding is performed within a group of m packets. This group is called a generation and m is the generation size. Random coefficients are generated and each packet is multiplied with a coefficient. Then, all packets are XOR-ed together, i.e. bitwise XOR-ing of packets with equal length, and y k is generated. The newly generated packet is The exact probability of successful decoding is derived in [TCBOF11]. The probability of generating a linearly independent packet increases with the number of packets in the generation m and the size of the Galois field q. On the other hand, the length of the header overhead due to the coding coefficients becomes significant. This affects the throughput of a system and has a huge impact on the system load for some network scenarios. Thus, it is of a great importance to find a good tradeoff between the parameters. Next, we calculate the encoding complexity of RLNC. The computational complexity of generating the coding coefficients depends on the complexity of generating a random number r that is system specific and the generation size m. Consequently, the complexity of generating the encoding coefficients is O(mr) where r is a constant. After generating the encoding coefficients, the packets are multiplied with them. This has a complexity of O(ml). Finally, the complexity of encoding one packet y k is O(m(l + r)) [HPFL08], while encoding all packets within one generation has 2.2. NETWORK CODING 19 x 2 x m x n !""!""!" x m+1 !""!""!" !""!""!" x 2 x 1 x 1 x 1 Figure 2.6: Generating a coded packet y k in RLNC. The file is split into n packets and encoding is performed within a group of m < n packets. Each packet is multiplied with a random coefficient c ki . All packets are XOR-ed together and y k is generated.

Existing header
Vector of coding coefficients Coded payload a complexity equal to O(m 2 (l + r)). The structure of a coded packet in RLNC is showed in Figure 2.7. The length of the vector of coding coefficients is m log 2 q bits. For instance, a typical packet length in sensor networks is 30 bytes. Consider a sensor network where 60 nodes send data. If RLNC in GF (16) is performed and the generation size is 60, then 30 bytes per packet are used for recording the coding coefficients, i.e. the length of the header overhead is equal to the length of the useful data. Additionally, the header overhead has an impact on the required energy to transmit the coded packets. The energy used to transmit a single bit of data between devices in ad hoc sensor networks is equal to the energy for performing 800 instructions in the devices [MFHH02]. This implies that many applications may benefit by performing local computations rather than sending more bits. Thus, the reduction of the length of transmitted data, while keeping the same functionality of the employed algorithms is a challenging task.
Several header compression algorithms have been suggested in recent literature. Kötter and Kschischang proposed an approach that finds a linear subspace of the ambient vector space, and the coding is just done in that linear subspace [KK08]. This is a challenging task since every combination of source data should result in a distinct union subspace and finding a proper subspace can be a computational challenge.
The concept of sparse coding is well known, and it was first applied for header compression in network coding by Siavoshani et al. [SKFA09]. The number of combined packets in one coded packet is reduced from n to m, where m < n, which results in a header length of O(m log 2 n log 2 q) bits. However, limiting the number of combined packets affects the invertibility of the matrix or it reduces the probability of a redundant packet being innovative [BKW97, HPFM11, FLS + 14, PFS05]. It was proved that m should be at least of order O(log n) so that the matrix has a full rank with high probability.
A header compression algorithm based on erasure decoding and list decoding was presented in [LR10]. The compressed header length under the erasure decoding scheme is m + n/ log 2 q bits. The header length becomes arbitrarily close to m + O(log 2 n)/ log 2 q bits when the list decoding scheme is used. Both schemes are valid for moderate or large values of m.
In [CCW10], the header overhead is the seed for generating the coding coefficients with a known Pseudo-Random Number Generator (PRNG). This effectively reduces the header overhead to the size of the seed, but it does not support re-encoding which is the crucial constituent of RLNC [LWLZ10].
A similar solution where the generation of the coding coefficients is based on modified Vandermonde matrices which can be determined by one symbol is given in [TF12]. Two main drawbacks of this solution are: the network coding nodes can only perform addition operations and the generation size is upper bounded by log 2 q bits due to the cyclic property of the matrices.
Silva showed that precoding with Maximum Rank Distance (MRD) codes virtually eliminates the linear dependency even over a binary field [Sil12]. Coding in small finite fields significantly reduces the overhead in RLNC. This approach implies a moderate increase in the decoding complexity, but it potentially simplifies the operations at intermediate nodes that comes as an additional benefit besides minimizing the total overhead.
Recently, Fulcrum codes were proposed [LPHF14b,LPHF14a]. Fulcrum codes are concatenated codes where a seed for a PRNG is used to end-to-end communicate the coefficients of the outer code, while the inner code requires 1 + r/n bits per packet. Recoding can be performed exclusively over the inner code in GF (2). Encoding and decoding is performed over the outer code in big finite fields.
Although there has been a vast amount of research results for network coding since its emergence, still there have not been many practical applications. The concept 2.3. CODE CONSTRUCTIONS FOR DISTRIBUTED STORAGE SYSTEMS 21 of network coding has been used to derive the bounds of the repair bandwidth in distributed storage systems. This is discussed in the next subsection.
The research in the present thesis addresses one of the main limitations for practical implementation of network coding: -Reducing the length of the vector of coding coefficients.

Code Constructions for Distributed Storage Systems
A distributed storage system is a network of storage disks or nodes where data pertaining to a single file is distributed across the storage nodes. It is a practical choice for storing large amounts of data. The nodes are relatively inexpensive storage devices that may fail, be down during maintenance, or otherwise unavailable due to serving other demands, etc. A distributed storage system has to guarantee a reliable storage of the data over long periods of time even though the nodes might be individually unreliable.
Definition 2.17. Reliability is the probability that a system provides an uninterrupted service during a certain time interval [0, t], i.e.
where T F F is Time to First Failure.
(2.10) It equals the time it takes a given storage system to exhibit enough failures such that at least one block of data cannot be retrieved or reconstructed.
In order to build a highly reliable system, redundancy has to be introduced. The redundancy can either be a simple copy of the data or a linear combination of the original data. Replication is a method of making copies from the original data. The data is available until one copy still exists. In case of storing one extra replica, the storage overhead is 100%, while it is 200% for 2 replicas and so forth. For instance, Google File System [GGL03] and Hadoop File System [SKRC10] store three copies of the data by default. When storing petabytes of data, replication is cost-inefficient. The main advantages of replication are: simple design and verification, low I/O and latency. However, its major disadvantage is the high storage overhead (200% for the industry standard) that translates into a high hardware cost (disk drives and associated equipment), as well as a high operational cost such as building space, power, cooling, maintenance, etc.
Weatherspoon and Kubiatowicz showed in [WK02] that erasure resilient systems use an order of magnitude less bandwidth and storage to provide a similar level of reliability as replicated systems. Hence many distributed storage systems are now turning to Reed-Solomon codes. Two reasons why often RS codes are employed in large-scale distributed systems are their storage optimality (since they are MDS codes) and generic applicability (construction of RS codes for arbitrary n and k). Redundant Arrays of Inexpensive Disks (RAID) is a well known technology for data protection in high performance computing storage systems [PGK88]. RAID based systems use RS codes to recover the data when multiple disks fail simultaneously. In order to avoid the large finite field operations, many code constructions such as EvenOdd [BBBM95], Row-Diagonal Parity [CEG + 04] and flat XOR [GLW10] use only exclusive-OR operations to recover the data. Although RS codes improve the storage efficiency, the amount of accessed and transferred data to repair a failed node is large. We graphically present the repair process of a single systematic node with RS code in Figure 2.10 (a). The parameters in this example are k = 10, r = 4 and M = 100MB. When RS codes are used, each node is recovered by transferring data of size M/k from any k nodes. In order to reconstruct 10MB of data stored in a single node, 10 × 10MB=100MB are read from 10 nodes and transferred across the network to the node performing the decoding computations. Accordingly, RS codes perform poorly in terms of the repair bandwidth since the amount of the repair bandwidth is k times the size of the data to be reconstructed. Additionally, this has a negative effect on the read performance of the system in a degraded mode (there is a read request for a data unit that is missing or unavailable) and the recovery time.
An improvement is to seek for codes that perform better than RS codes. Three major repair cost metrics for new erasure coding solutions have been identified in the recent literature: i) the amount of transferred data during a repair process (repair bandwidth), ii) the number of access operations during each repair (disk-I/O), and iii) the number of nodes that participate in the repair process (repair locality). Two types of repairs have been suggested [DRWS11]: exact (the recovered data has exactly the same content as the lost data) and functional (the newly generated data can be different than the lost one, but it maintains the MDS-property). The research presented in the present thesis focuses only on exact repair, which is preferred from a practical point of view.

Regenerating Codes
Classical MDS codes are optimal in terms of the storage-reliability tradeoff, but they still do not give a good answer to the key question: How to encode the data in a distributed way while transferring as little data as possible across the network during a repair process?
Under a (n, k) MDS code, a file of size M symbols is divided into k fragments, each of size M k symbols, encoded and stored in n nodes. The original file can be  Figure 2.8 shows an information graph that corresponds to a (5, 3) code where the node S corresponds to the source file. Assume that a (5, 3) MDS code is used to encode the file M = 3MB. The code generates 5 fragments each of size α = 1MB (stored in the nodes x 1 , . . . , x 5 ) with the property that any 3 can be used to reconstruct the original data. The storage node x i is represented by a storage input node x i in and a storage output node x i out . The capacity of the edge between these two nodes is equal to the amount of stored data in node x i . Data collectors connect to subsets of active nodes through edges with infinite capacity. When node x 5 fails, a newcomer x 6 reconstructs the lost data from x 1 , . . . , x 4 . The question is: What is the minimum amount of information that has to be communicated? The new storage node x 6 downloads βMB from d = 4 active nodes. The min-cut separating the source and the data collector must be larger than M = 3MB for a reconstruction to be possible. In this example, the min-cut value is given by 1 + 3β, implying that β ≥ 0.33MB is sufficient and necessary.
A (n, k, d) regenerating code replaces the data from a failed node by downloading where d ≤ n − 1. For d, n, k given, the minimum repair bandwidth γ is (2.14) The repair bandwidth γ decreases as the number of d nodes increases. An optimal tradeoff curve between the storage and the repair bandwidth for a (15, 10, 14) code is shown in Figure 2.9. Regenerating codes achieve each point on this optimal tradeoff curve. The two extremal points on the optimal tradeoff correspond to the points at which the storage and the repair bandwidth are minimized, respectively. Following Theorem 2.19, the both points are attained when d = n − 1, i.e. all n − 1 non-failed nodes called helpers are contacted during a node repair. The codes that attain these points are known as Minimum-Storage Regenerating (MSR) and Minimum-Bandwidth Regenerating (MBR) codes, respectively. MSR codes achieve the pair (2.16) MBR codes require an expansion factor of 2n−2 2n−k−1 in the amount of stored data, thus, they are no longer storage-reliability optimal.
The work in [CJM10] and [SR10] showed that the lower bound of the repair bandwidth for functional repair with MSR codes given in (2.15) is also achieved for exact repair with MSR codes.
The present thesis focuses only on storage-reliability optimal codes with exact repair since they have the biggest practical potential.
We illustrate the benefit of using an MSR code in Figure 2.10 (b). We use the same parameters as for the RS code, i.e. k = 10, r = 4 and M = 100MB. Under the MSR code, the data from an unavailable node is reconstructed by downloading only (")"*#+,"#$("-../"0121314"" -.5'67"8'4/96/:;"&"#$$<=" each node. The total repair bandwidth is only 32.5MB compared to 100MB under RS. MSR codes possess all properties of an MDS code, giving an additional advantage of efficient repair consuming minimum possible bandwidth. This is made possible by using a sub-packetization level, i.e. the data at each node is further divided into blocks. The sub-packetization level α represents the minimum dimension over which all operations are performed. Namely, when the sub-packetization is 1, then each node is recovered by transferring data of size M/k symbols from any k nodes, i.e. the case when RS codes are used. Hence, α > 1 is required to achieve the lower bound of the repair bandwidth. We use a sub-packetization level equal to 64 in Figure 2.10 (b) in order to achieve the minimum repair bandwidth with the (14, 10) MSR code.
The construction of exact-repair codes is a well-studied problem in the literature. Here we only list the most relevant results for our work about MDS codes for storage systems. Exact-MSR codes that are obtained by using the technique of interference alignment, a technique used to efficiently handle multiple interfering channels in wireless communications [CJ08], were presented in [WD09,SR10].
Papailiopoulos et al. in [PDC13] and Cadambe et al. in [CHL11] resolved partly the open problem about designing high-rate MDS codes that achieve the optimal repair bandwidth. The code construction in [PDC13] used Hadamard matrices to construct a two-parity MDS code with optimal repair properties for any single node failure, including the parities. The construction is similar to zigzag codes in [TWB13], but the former one uses bigger finite fields. The zigzag codes provide an optimal recovery of any systematic node and an optimal update for a sub-packetization level of r k . The work was further extended to provide an optimal recovery of both systematic and parity nodes [WTB11].
Furthermore, Tamo et al. [TWB14] showed that the sub-packetization level of an access-optimal MDS code for repairing a failed systematic node is r k r . In [CHLM11], Cadambe et al. proposed codes that repair optimally any systematic node for this sub-packetization level. An alternate construction of access-optimal MSR codes motivated by zigzag codes was presented in [ASVK15]. An essential condition for designing alternate codes with r parity nodes is m = k r to be an integer m ≥ 1 where k is set to rm and α to r m .
Wang et al. constructed codes that optimally repair any systematic or parity node and require a sub-packetization level of r k+1 [WTB11]. High-rate MSR codes with polynomial sub-packetization level were proposed in [SAK15]. However, the work presented in the present thesis focuses only on optimal repair of any systematic node.
Although the aforementioned MSR constructions achieve the lower bound of the repair bandwidth for a single failure, they have not been practically implemented in real-world distributed storage systems. Two main reasons for practical abandonment of existing MSR codes are: either MSR codes require encoding/decoding operations 2.3. CODE CONSTRUCTIONS FOR DISTRIBUTED STORAGE SYSTEMS 27 over an exponentially growing finite field or the sub-packetization level α increases exponentially. There are at least two ways to solve the problem by using small sub-packetization levels and optimizing in terms of I/O operations.
Rashmi et al. reported 35% reduction in the repair bandwidth for any systematic node when the sub-packetization level is 2 compared to a (14, 10) RS code [RSG + 14]. They used the piggyback framework [RSR13] to construct Hitchhiker erasure codes. The basic idea of the piggyback framework is to take multiple instances of an existing code and add carefully designed functions of the data from one instance to another. Other code constructions with small sub-packetization levels are Rotated-RS [KBP + 12], EVENODD [BBBM95] and RDP codes [CEG + 04]. Rotated-RS codes exist only for r ∈ {2, 3} and k ≤ 36, while EVENODD and RDP codes exist for I/O is becoming the primary bottleneck in the performance of cloud storage systems and applications that serve a large number of user requests or perform data intensive computations such as analytics. There are two main types of I/Os: sequential and random operations. Sequential operations access locations on the storage device in a contiguous manner, while random operations access locations on the storage device in a non-contiguous manner. A recent algorithm to transform Product-Matrix-MSR codes [RSK11] into I/O optimal codes (termed PM-RBT codes) while retaining their storage and network optimality was presented in [RNW + 15]. PM-RBT exist only for r ≥ k − 1, i.e. for the low-rate regime.
All MDS erasure codes discussed in the previous paragraphs focus on an efficient repair from a single failure, since single failures present 98.08% of the total failures [RSG + 14]. On the other hand, the authors in [FLP + 10] state that the failures are often correlated. Next we review codes that outperform the aforementioned codes when multiple failures happen.
A cooperative recovery mechanism in the minimum-storage regime for repairing from multiple failures was proposed in [HXW + 10, WXHO10]. Minimum Storage Collaborative Regenerating (MSCR) codes minimize the repair bandwidth while still keeping the MDS property by allowing new nodes to download data from the non-failed nodes and the new nodes to exchange data among them. The repair bandwidth for MSCR codes under functional repair was derived independently in [HXW + 10, KSS11]. The existence of a random linear strong-MDS code under the assumption that the operations are in a sufficiently large finite field was showed in [HXW + 10]. The codes attain the MSR point but the decoding complexity is quite expensive. Adaptive regenerating codes where the numbers of failed and surviving nodes change over time were proposed in [KSS11]. The authors in [LL14] showed that it is possible to construct exact MSCR codes for optimal repair of two failures directly from existing exact MSR codes. MSCR codes that cooperatively repair any number of systematic nodes and parity nodes or a combination of one systematic and one parity node were presented in [CS13]. However, the code rate of these codes is low (n = 2k). A study about the practical aspects of codes with the same code rate (n = 2k) in a system called CORE that supports multiple node failures can be found in [LLL15]. There is no explicit construction of high-rate MDS codes for exact repair of multiple failures at the time of writing of the present thesis.
Practical scenarios [SAP + 13, PJBM + 16, RSG + 14] showed that erasure codes have to provide a satisfactory tradeoff between the metrics such as storage overhead, reliability, repair bandwidth, locality and I/Os. The present thesis tackles this by working on: -MDS code constructions with arbitrary sub-packetization levels for both lowrate and high-rate regimes; and -Locally Repairable Codes.

Locally Repairable Codes
Locally Repairable Codes (LRCs) were independently introduced in [GHSY12, OD11, PLD + 12]. Let C be a (n, k, d) q linear code. Assume that the encoding of x ∈ F k q is by the vector (2.17) Thus, the code C is specified by the set of n points C = {c 1 , . . . , c n } ∈ F k q . The set of points must have a full rank equal to k for C to have k information symbols.
Definition 2.20. For c i ∈ C, we define Loc(c i ) to be the smallest integer l for which there exists L ⊆ C of cardinality l such that (2.18) We further define Loc(C) = max i∈{1,...,n} Loc(c i ).
Definition 2.21. We say that a code C has information locality l if there exists I ⊆ C of full rank such that Loc(c) ≤ l for all c ∈ I. . Both implementations reduce the reconstruction cost by introducing l local and r global parity blocks. The local parity nodes are computed from a subset of the systematic nodes. The locality of a code has also an impact on the fault tolerance and the update efficiency. LRCs tolerate r + 1 arbitrary node failures and l + r theoretically decodable failures. Consider the example with 10 data nodes in Figure 2.10 (c) where a (16, 10) LRC generates 6 (instead of 4) parity nodes. The first four parities (denoted as p 1 , p 2 , p 3 , p 4 ) are global parities and are computed from all systematic nodes. While, for the two other parities, LRC divides the systematic nodes into two equal size groups and computes one local parity node for each group. The local parity p 5 is computed as an XOR combination from 5 systematic nodes in the first group (a 1 , . . . , a 5 ), while the parity p 6 is computed from 5 systematic nodes in the second group (a 6 , . . . , a 10 ).
Let us consider the reconstruction of a 1 . Instead of reading p 1 (or another global parity node) and the remaining 9 systematic nodes, it is more efficient to read p 5 and 4 systematic nodes (a 2 , . . . , a 5 ) from the first group. It is easy to verify that the reconstruction of any systematic node requires accessing only 5 nodes, i.e. significantly less than the RS (10 nodes) and the MSR (13 nodes) code. The locality in this example is equal to 5 for the local parities and equal to 10 for the global parities. Any systematic node is recovered from k l nodes within its local group. Hence, the repair bandwidth for a single systematic node recovery with the (16, 10) LRC is 50MB. If we consider a repair of the parity nodes as well, then the average repair bandwidth for a single node failure is (5 × 12 + 10 × 4) × 10MB/16 = 62.5MB, because the recovery of the global parities is performed in the same way as with RS codes.
The authors of [SAP + 13] improved the recovery of the global parities by introducing an implied parity, but choosing the coefficients for the parities to satisfy the alignment condition is computationally demanding. Tamo et al. introduced a new family of optimal LRCs that are based on re-encoding RS encoded fragments [TPD13]. Although the code construction is simple, it requires a large finite field.
Motivated by practical situations in hot storage, where the data changes dynamically, the metric update complexity has been introduced in [ASV10]. Specifically, if the value of any of the systematic data changes, then the corresponding data has to be updated in the nodes that contain it in order to keep the data consistent.
Definition 2.23. The update complexity of a (n, k, d) q code C is defined as the maximum number of symbols that must be updated when any single information symbol is changed.
Tolerating and recovering efficiently from multiple failures is an important requirement for big data storage systems. Shingled erasure codes (SHEC) are codes with local parities shingled with each other that provide efficient recovery from multiple failures [MNS14]. All parities have the same locality l and support rl k systematic or parity node failures without data loss, but they are not efficient in terms of storage overhead and reliability. There is still a need for new erasure resilient codes that reduce the number of nodes contacted during a repair, while still guaranteeing a low repair bandwidth even when multiple failures occur. Additionally, performing updates consumes bandwidth and energy, so it is of a great interest to construct codes that have small update complexity, i.e. small locality. Thus, one of the research topics in the present thesis is: -A construction of LRCs that have low storage overhead, low average repair bandwidth for single and double failures, high reliability and improved update performance. Although the speed of electronic devices has been increased significantly, it is still not likely to catch up with the transmission speed available at the optical layer. Thus, there is a need to minimize or eliminate the electronic processing in order to fully exploit the potential bandwidth offered by DWDM. This calls for a move of the switching functionalities from the electronic domain to the optical domain, i.e. all-optical networking [OSHT01].

Optical Packet Switched Networks
Furthermore, the traffic has become more data-dominant than voice-dominant. As the traffic nature has changed from continuous to bursty, there is a need for a switching technology that supports efficiently bursty traffic [QY99].
The switching technologies for DWDM are: -Wavelength Routed Optical Switching establishes all-optical circuit switched connections (lightpaths) between edge nodes in the optical core network [RS02]. In Wavelength Routed Optical Networks (WRON), a lightpath is set-up before the data transmission and a dedicated wavelength on every link is reserved.  One of the main differences between OPS and OBS is the data unit that is processed and forwarded through the network. In OPS networks, packets are processed and forwarded, while in OBS networks, incoming packets are aggregated into bursts at an OBS ingress node based on the destination and/or the service class of the packets which are then transmitted in the network. Both OPS and OBS allow switching of data in the optical domain. However, switching decisions are made in the electronic domain [NBG08] as optical processing is still an immature technology.
Another key difference between OPS and OBS is the control information. The control information in OPS is in-band, while it is out-of-band in OBS networks. In particular, reservation is not possible in OPS, because the header follows the rest of the packet. In OBS, the burst transmission is initiated shortly after the burst was assembled and the control packet was sent out. The wavelength is allocated only for the duration of a data packet/burst and can be statistically shared by packets/bursts belonging to different connections. Switching decisions are taken based on the packet header or the burst control packet that undergoes O/E conversion and electronic processing at the switches, while the packet/burst payload is optically switched.
OPS has finer granularity compared to OBS, but requires fast switching, header reading and reinsertion that increase the complexity and the cost at the switching node [NBG08].
An overview of the characteristics of the aforementioned switching technologies is given in Table 2.1 [VCR00].
A crucial issue in OPS/OBS networks is the packet loss at the network layer due to contentions. A contention occurs at a switching node when two or more packets are destined on the same output port, on the same wavelength, at the same time. Contending packets are dropped which leads to increased PLR. For instance, the default behavior is to drop one of the two packets that contend for the same wavelength at the same time. In Figure 2.11 (a), packet b is dropped. It is impossible to buffer the data or retransmit the dropped packets. First, the amount of data is enormous, and, second, there is no Random-Access Memory (RAM) available in OPS/OBS networks. Thus, contending packets cannot be buffered and forwarded when the output port is free.
Several contention resolution mechanisms such as wavelength conversion, Fiber Delay Line (FDL) buffering and deflection routing [CWXQ03] have been proposed to combat packet loss in OPS/OBS networks. Wavelength conversion [DJMS98,EM00] converts the wavelength of one of the contending packets to an idle wavelength on the same output port (Figure 2.11 (b)). FDLs [HCA98] try to mimic electronic buffering by delaying one of the packets in time and scheduling it to the intended wavelength when it is free (Figure 2.11 (c)). A large number of FDLs are needed to implement large buffer capacity and they may add an additional delay. Both wavelength conversion and optical buffering require extra hardware which may increase the system cost. Deflection routing is a multiple-path routing technique that routes the contending packets to other nodes, i.e. output ports on the same wavelength. The performance of deflection routing largely depends on the network topology. A big advantage is that any of these three techniques can be combined. Another contention resolution scheme in OBS networks is burst segmentation. Rather than dropping the entire burst during contention, only the overlapping segments are dropped [VJS02].
FEC has been recently applied in OPS/OBS networks to alleviate PLR ( Figure  2.11 (d)) [YKSC01]. FEC is not a contention resolution scheme, which means it can be combined with wavelength conversion, fiber delay line buffering and deflection routing. Redundant packets are added to a set of data packets at the OPS ingress node and transmitted along with the original data packets to an OPS egress node. Data packets dropped due to a contention can be reconstructed at the OPS egress node by using excess redundant packets, leading to a potential reduced PLR. The Network Layer Packet Redundancy Scheme (NLPRS), introduced in [Ove04], reduces several orders of magnitude the end-to-end PLR due to contentions in an asynchronous OPS ring network with and without a wavelength conversion. The authors in [GA02] evaluate several topology-routing algorithms for deflection routing coupled with erasure coding. The results show the amount of redundancy that is needed in unstructured networks of switches. The forward redundancy mechanism proposed in [VZ06] significantly reduces the packet loss compared to a retransmission-based backward loss recovery mechanism without the need for large ingress electronic buffers or big retransmission delays. Under this mechanism, only the overlapping segments of the contenting bursts are dropped. The dropped segments of a burst can be recovered using the redundant packets at the OBS egress node that were sent in the forward direction, from the ingress to the egress node.
Apostolopoulos used multiple state video coding and path diversity for transferring video over a lossy packet network [Apo01]. Path diversity is defined as sending different subsets of packets over disjoint paths, as opposed to the default scenarios where the packets proceed along a single path. Path diversity provides better performance because the probability that all of the multiple paths are simultaneously congested is much less than the probability that a single path is congested. Nguyen and Zakhor combined a rate allocation algorithm from multiple senders to a receiver with FEC in order to minimize the probability of lost packets due to congestions in a bursty loss environment [NZ02]. The work was further extended in [NZ03] where they presented a scalable, heuristic scheme for selecting a redundant path between an ingress node and an egress node. The disjoint paths from a sender to a receiver are created by using a collection of relay nodes.
Another coding technique for mitigating packet loss is network coding. A straightforward application of the network coding technique is not feasible in OPS/OBS due to the lack of store-and-forward capabilities. However, the idea of combining the packets instead of dropping them reduces the packet loss [BO11].
Survivability is essential in OPS/OBS networks with a throughput of order of terabits per second [ZS00]. The survivability of a network refers to a network's capability to provide continuous service in the presence of failures. The most common types of failures are node and link failure. Service providers have to ensure that their networks are fault tolerant. To meet these requirements, providers use common survivability mechanisms such as predesigned protection techniques [GL03, FV00, SRM02], node and component redundancy, prebuffering [KBOS10], and predetection schemes [BNH02]. The most used protection techniques include 1 + 1 protection, in which the same data is transmitted on two link disjoint paths, and the receiver selects the packets from the path with better quality; 1 : 1 protection, which is similar to 1 + 1, except that traffic is not transmitted on the backup path until a failure occurs; 1 : N protection, which is similar to 1 : 1, except that one path is used to protect N paths; and M : N , where M protection paths are used to protect N working paths. Figure 2.12 shows 1 + 1 and 1 : 2 path protection schemes. Some of the protection techniques can be combined with coding. Kamal first applied network coding to provide 1 + N protection against single link failure [Kam06, Kam07b,Kam08]. The optimal 1 + N protection scheme in [KAK08] requires exactly the same amount of protection resources as in 1 : N and the time to recover from failures is comparable to that of 1 + 1 protection. Kamal extended the approach to protect against multiple link failures [Kam07a, KRLL11]. Menendez and Gannet proposed photonic XOR devices for network coding [MG08]. Savings of up to 33% in links (transmitter, fiber or wavelength channel and receiver) are possible with network coding compared to conventional techniques. The effectivness of network coding to provide robustness against link failures of multicast traffic is presented in [MDXA10].
In OBS, data and control packets are sent out of band. Sending the Burst Header Packet (BHP) prior the transmission of data packets with specific offset time exposes the data payload to different security challenges. The authors in [SMS12] discussed the burst hijacking attack where a source node can maliciously create a copy of the original BCH and modify its value to setup a path to a malicious destination. The data payload is forwarded to the original destination as well as the malicious destination. However, the malicious destination does not send an acknowledgment for this hijacked burst, thus, it escapes from being caught. A solution based on Rivest-Shamir-Adleman (RSA) public-key encryption algorithm 2.4. OPTICAL PACKET SWITCHED NETWORKS 35 that addresses the Data Burst Redirection (DBR) attack in OBS networks is proposed in [CAKSAL + 15]. However, the high capacities of OPS/OBS networks make data encryption in OPS/OBS not feasible as the current computational resources do not match the required encryption processing demands. The encryption mechanisms have to be with low computational complexity, suitable for high-speed implementation and the majority of the header content should not be encrypted since the processing of the headers has to be at ultra high speed [CV08].
One way of providing a certain level of security in a non-cryptographic way is to utilize non-systematic coding. Secrecy as defined in [MS12] provides protection from a passive adversary that is not able to reconstruct the whole packet/burst set by eavesdropping on a single path. This property has not been so far exploited in OPS/OBS networks. The authors in [OLV + 12] showed how secrecy in storage systems is provided even when an eavesdropper knows or can guess some of the missing information.
There is a lack of research work that gives a unified view of the performance metrics in OPS. The scheme proposed in [Ove08] and [OBBT12] provides a 1 + 1 path protection in addition to the packet loss alleviation. In particular, the work in [OBBT12] shows that significant cost savings are achieved by using erasure codes compared to other approaches that provide 1+1 path protection. There is a need for: -An integrated view of QoS in OPS/OBS networks that deals with survivability, packet loss alleviation and secrecy at the same time.

Research Questions
The state-of-the-art in the four main research areas covered in the present thesis was reviewed in the previous Chapter. The detailed literature study brings forth the following research questions. First, it is of utmost importance to identify the desired code properties explained in Subsection 2.1 when constructing erasure codes, properties such as non-MDS or MDS, binary or non-binary codes with as few as possible operations in large finite fields, structure of the generator matrix, generic applicability, fast encoding/decoding etc. Accordingly, it is meaningful to ask: RQ1 How can we construct balanced erasure codes?
The next goal is to address some of the challenges of a practical implementation of network coding. Network coding can increase the data throughput by an orderof-magnitude and also improve the robustness of existing networks. However, one of the main challenges is the header overhead imposed by the coding coefficients as explained in Subsection 2.2. Accordingly, there is an enormous need for new header compression algorithms and this poses the next research question: RQ2 How can we reduce the header overhead in network coding?
Network coding concepts helped to derive the storage-repair bandwidth tradeoff for single node recovery with regenerating codes in distributed storage systems. While MSR codes possess all properties of MDS codes and offer an additional advantage of efficient repair consuming the minimum repair bandwidth (Subsection 2.3.1), locally repairable codes disregard the MDS property and provide a low locality (Subsection 2.3.2). Thus, a more general question about code constructions that are optimal for some of the cost metrics in distributed storage systems is raised: RQ3 How can we construct efficient codes for distributed storage systems? The next question is related to provision of a unified view on QoS in OPS/OBS networks that is explained in Subsection 2.4. It is essential to know the interactions between the survivability, the packet loss rate and the secrecy when erasure codes are applied. Naturally, this poses the following question: RQ4 How can erasure coding be applied to increase the QoS in OPS/OBS networks?

Research Results
The author of the present thesis wrote and contributed to 10 publications and 7 patent applications during the four-year PhD period. Table 3.1 presents a complete list of included publications in the thesis, while Table 3.2 and Table 3.3 list the rest of the publications and patent applications that are not included in the thesis. The order in which the papers are given is not necessarily chronological, but rather related to the research questions so that it is easier and more natural to follow the exposition in the thesis. Figure 3.1 shows the position of the included papers in the thesis with regards to the four research questions. Erasure code constructions are the core and they are used in different applications. The arrows depict the correlations between the included papers. Combinatorics and coding theory go hand in hand acting as powerful tools for design, analysis and implementation of efficient codes. We started with construction of erasure codes from combinatorial designs where we generate codes 3.2. RESEARCH RESULTS 39   Employing some known facts from finite fields, we suggest an algorithm called Small Set of Allowed Coefficients (SSAC) in Paper 3. Network coding is an interesting problem that is well studied with the help of graph theory. By using some concepts of network coding, the lower bound of the repair bandwidth for a single node recovery in distributed storage networks is derived. A general construction of MDS codes for any sub-packetization level for repair of a single systematic node is suggested in Paper 4. The code construction from Paper 4 is further elaborated and optimized in terms of I/O in Paper 5. Later the idea of applying balanced codes as LRCs in distributed storage came. In Paper 6, we relaxed the condition of equal number of non-zero elements per column in the generator matrix. In both Paper 2 and Paper 6, we use hill-climbing search for codes with better performance. The path diversity and the secrecy features from Paper 1 inspired us to apply them in OPS/OBS networks in order to achieve survivability against link failures and non-cryptographic secrecy.

Research Answers
Here we summarize the answers to the research questions defined in Subsection 3.1.
ANS1 Paper 1 and Paper 2 answer RQ1 by introducing a new way of constructing balanced binary codes from combinatorial designs (Latin squares and Latin rectangles).
ANS2 Paper 3 answers RQ2 by proposing a novel algorithm called SSAC for practical network coding. SSAC generates the shortest header overhead by using sparse coding and properties of finite fields.
ANS3 Paper 4, Paper 5 and Paper 6 answer RQ3. Paper 4 and Paper 5 present the first MDS codes for both low-rate and high-rate regimes that provide the lowest repair bandwidth for any sub-packetization level. The practicality of these codes is further investigated in Paper 5. Paper 6 solves partially the open problem of finding a general construction of LRCs with a low locality for any n and k.

ANS4
Paper 7 constitutes a first step for providing a unified view on the interactions between survivability, PLR and secrecy in OPS/OBS networks raised in RQ4.

Summary of the Results Contributing to the Thesis
This Section gives a summary of the papers included in Part II. The contributions of each paper are compared to the most relevant state-of-the-art results. The papers are presented in the order as they give answers to the research questions. Encoding and decoding over GF (2) are up to two orders of magnitude less energy demanding and up to one order of magnitude faster than encoding/decoding operations in higher fields [VPFH10]. Sparse codes minimize the computation time of computing any coded packet, a property that is appealing to systems where computational load-balancing is critical. These are the main motivations to seek for sparse codes only with XOR operations.
The first theoretical work by Riis in [Rii04] shows that every solvable multicast network has a linear solution over GF (2). Afterwards, XOR coding has been applied in wireless networks in [KRH + 08] where random coding with no predefined code construction is used.
In Paper 1, we apply the knowledge from combinatorics for code constructions by introducing a new way of constructing balanced XOR-ed codes from combinatorial designs (Latin squares and Latin rectangles). In this context, balanced means all packets are encoded with equal complexity, i.e. the number of ones in each row and each column is equal. We show that the XOR-ed codes reach the max-flow for single source multicast acyclic networks with delay. Encoding of the original data is done by a nonsingular incidence matrix obtained from a Latin rectangle, while decoding is performed by the inverse matrix of the incidence matrix. Additionally, this paper shows that balanced coding offers plausible secrecy properties. In particular, if the incidence matrix and its inverse matrix switch the roles, then an eavesdropper has to eavesdrop at least max-flow links in order to decode one original packet. The results presented in Paper 1 are further extended in Paper 2. We use the same logic (combinatorial designs) for constructing codes as in Paper 1. First, we define families of optimal binary non-MDS erasure codes. We also introduce the metric vector of exact decoding probability as a measure for how far away a specific (n, k) code is from being an MDS code. The second contribution is a heuristic algorithm for finding those families by using hill climbing techniques over balanced XOR-ed codes. Due to the hill climbing search, those families of codes have always better decoding probability than the codes generated in a typical RLNC scenario. Finally, we show that for small values of k, the decoding probability of balanced XOR-ed codes in GF (2) is very close to the decoding probability of random linear codes in GF (4). Paper 3 presents the only algorithm in the literature called SSAC where the header length does not depend from the size of the finite field. This is achieved by applying sparse coding, using an irreducible polynomial and at least two primitive elements from a finite field.
Although the concept of sparse coding is first used in [SKFA09], there the header length depends from the field size. Our work builds up on sparse coding, but we do not use parity-check matrices of error correcting codes. SSAC generates the header overhead by utilizing a small set Q ⊂ GF (q) of coefficients that multiply the original data. Usually Q consists of 2 primitive elements in GF (q), thus, the header length is decreased from n log 2 q to m(1 + log 2 n) bits where n is the generation size and m is the sparsity parameter. We show that the header length in SSAC does not depend on the size of the finite field where the operations are performed, i.e. it just depends on the number of combined packets. Moreover, our work is the first one that investigates the efficiency of the header compression algorithm in every intermediate node in conjunction with the number of buffered packets in that node. In Paper 4, we propose an algorithm for explicit construction of MDS codes that access and transfer the lowest amount of data when repairing from a single node failure for any sub-packetization level. The amount of accessed and transferred data is the same. The number of helper nodes is n − 1.
The algorithm presented in Paper 4 is so general that it also covers construction of access-optimal MSR codes. Compared to the construction presented in [ASVK15] where k r has to be an integer and the considered sub-packetization level is exclusively equal to r k r , the parameter k r in our work is not necessarily an integer. For instance, the code (14, 10) that is deployed in the data-warehouse cluster of Facebook is out of the scope of applicability with the current proposals in [ASVK15, CHLM11, TWB14], because k r = 2.5 is a non-integer. While the algorithm in Paper 4 constructs a (14, 10, 13) code that reduces the repair bandwidth for any systematic node by 67.5% when the sub-packetization level is r k r = 64 compared to a (14, 10) RS code. The presented codes are simultaneously optimal in terms of storage, reliability and repair bandwidth. We also give an algorithm for exact repair of any systematic node that is linear and highly parallelized. This means a set of α r symbols is independently repaired first and used along with the accessed data from other helper nodes to recover the remaining symbols. The results show how the repair bandwidth decreases as the sub-packetization level increases. The lower bound of the repair bandwidth is achieved for α = r k r (MSR codes). Paper 5 is an extension of Paper 4 where we study both the theoretical and the practical aspects of the explicit construction introduced in Paper 4. Although we first introduced the codes without a specific name, in Paper 5 we call them HashTag Erasure Codes (HTECs) due to the resemblance between the hashtag sign # and the procedure of their construction. The three main contributions of Paper 5 are: an analysis of different concrete instances of HTECs, an elaboration of the correlation between the repair bandwidth and the I/Os with the sub-packetization level, and the repair bandwidth savings with HTECs even for repair of multiple failures.
We have implemented HTECs in C/C++ and performance analysis show up to 30% bandwidth savings compared to Piggyback 1 and Piggyback 2 codes [RSR13]. We also optimize HTECs in terms of the I/Os while still retaining their optimality in terms of the storage and the repair bandwidth. The authors in [RNW + 15] transform Product-Matrix-MSR (PM-MSR) into I/O optimal codes (which they call PM-RBT codes). Compared to HTECs that exist for any code parameters, PM-RBT codes exist only for r ≥ k − 1. We identify the values of sub-packetization levels that give optimal overall system performance. We also show that the scheduling of the indexes in HTECs ensures a gradual increase in the number of random reads, hence no additional algorithms such as hop-and-couple [RSG + 14] are needed to make the reads sequential.
Additionally, HTECs are the first codes in the literature that offer bandwidth savings when recovering from multiple failures for any code parameters including the high-rate regime. Paper 6 solves partially the open problem of finding a general construction of LRCs for any n and k [TPD13]. We suggest BLRCs that provide a good tradeoff between the storage overhead, the repair bandwidth, MTTDL and the update complexity.
The main problem with many existing LRCs [HSX + 12, SAP + 13] is that although they reduce the size of the subset of contacted nodes, they suffer from the drawback that only a single subset of nodes enables the repair of a specific block. If a single 3.5. CONCLUDING REMARKS 45 node from that repair subset is not available, data cannot be repaired "locally" and this increases the repair cost. BLRCs address this problem and provide an efficient repair even when double failures occur. The strict requirement that the repair locality has to be a fixed small number l is relaxed for BLRCs and we allow the repair locality to be either l or l + 1. One of the main features of the proposed codes is that the parity blocks depend in a balanced manner from the systematic data blocks. This means that each systematic block is included in exactly w parity blocks. Additionally, BLRCs are optimal even when double failures occur and this is not the case with other LRCs. We use four metrics such as storage overhead, average repair bandwidth, MTTDL and update complexity to compare our codes with existing LRCs. An extensive reliablity analysis for calculating the MTTDL is also presented. Paper 7 provides a unified view on QoS in OPS/OBS networks. The work in Paper 7 focuses on the interactions between survivability, PLR and secrecy. The authors in [Ove04] and [VZ06] focus only on FEC codes to reduce packet loss in OPS networks. The work in [Ove08] and [OBBT12] extends these schemes to provide 1+1 path protection. Unlike our work, none of these references considers secrecy.
We present the Coded Packet Transport (CPT) scheme, a novel transport mechanism for OPS/OBS networks that exploits the benefits of source coding with erasure codes combined with path diversity. At an OPS/OBS egress node, reconstruction of lost packets due to contentions and link/node failures is enabled by the added redundancy. Sending different subsets of non-systematic coded packets over disjoint paths between the ingress and the egress node provides an end-to-end secrecy against passive adversaries. CPT provides a non-cryptographic secrecy in OPS networks. We combine an attack technique (a combination of partially known coded text and a brute force attack) with the modern recommended levels of security (a long term security level of 128 bits) to analyze the secrecy constraints in CPT. The presented analytical models show how the QoS aspects of CPT are affected by the number of disjoint paths, the packet overhead and the packet loss rate. The number of disjoint paths and the packet overhead should be chosen so that CPT is within the operational range (the secrecy and the survivability constraints are not violated).

Concluding Remarks
As the amount of generated and stored data is exponentially growing, cost-efficient and reliable systems have become increasingly important. One way to ensure efficient reliability are erasure codes with properties as close as possible to MDS codes. Erasure codes have become particularly attractive for fault protection in storage systems. In order to have a practical deployment of new erasure coding techniques in distributed storage, several issues have to be solved. New coding techniques have to provide high resilience to failures as well as low repair bandwidth and fast recovery.
Network coding offers throughput benefits, but at the cost of adding extra overhead. Transmitting a single bit in ad hoc sensor networks is more energy consuming than performing instructions in the devices. The large amount of traffic, has made all-optical network architectures crucial for high-speed transport. OPS is a promising candidate among all-optical network architectures proposed in recent literature. We elaborate the applicability of erasure coding in OPS/OBS networks in order to provide better QoS.
The present thesis has dealt with erasure code constructions, with a particular focus on general binary and non-binary code constructions and the advantages of employing them in different networks. The overall major scientific contributions in the present thesis include: -A novel construction of binary codes suitable for implementation on devices with limited processing and energy capacity from combinatorial designs.
-A new algorithm for header compression in network coding where the header length is 2 to 7 times shorter than the length achieved by related compression techniques.
-Code constructions and implementation of new erasure codes for large scale distributed storage systems that provide savings in the storage and network resources.
• A novel construction of MDS erasure codes that significantly reduce both the repair bandwidth and the random I/Os during a repair of missing or otherwise unavailable data with no additional storage overhead and flexibility in the choice of parameters.
• A code construction optimized for repair locality and update complexity by relaxing the MDS requirement.
-A unified view of QoS in OPS/OBS networks by linking survivability, packet loss rate and secrecy using erasure coding and path diversity.

Future Works
Some proposals for future works are presented in this Section. A natural follow-up of the current work related to large-scale distributed storage is an extension of the HTEC construction to enable construction of high-rate codes that are optimal for recovery of both the systematic and the parity nodes. Several 3.6. FUTURE WORKS 47 high-rate MSR codes for efficient repair of both systematic and parity nodes exist in the literature [WTB11,SAK15,YB16a]. Still for these codes, either the subpacketization level is too large or the constructions are not explicit. An open issue is how to extend the HTEC construction to support an efficient repair of the parity nodes as well.
In Paper 4 and Paper 5, we use the work in [ASVK15] to guarantee the existence of non-zero coefficients from F q so that the code is MDS. However, the lower bound of the size of the finite field is relatively big. On the other hand, in our examples we actually work with very small finite fields (F 16 and F 32 ). Recent results in [YB16b] showed that a code is access-optimal for α = r k r over any finite field F as long as |F| ≥ r k r . Determining the lower bound of the size of the finite field for HTECs remains an open problem.
Repairing the data with regenerating nodes requires contacting n − 1 nodes. This creates a burden in the system and the data from all n − 1 nodes should be always available. LRCs tackle this problem by contacting only l nodes, but the improved performance comes at the expense of extra storage. An interesting research direction is how to combine the benefits from both regenerating and LRC codes.
Another research direction is the development of Error-Correcting Code (ECC) memory. The concept is similar to what we have been working on until now, but instead of recovering lost data distributed over different failure domains such as hard drives, nodes, racks and geographical locations, the concept is applied to memory chips. ECC memory offers error detection in addition to error correction. A memory error is an event that leads to the logical state of one or multiple bits being read differently from how they were last written. A memory error can lead to a machine crash or applications using corrupted data if the system does not support ECCs. Thus, ECCs memory are crucial components in each system. Since the construction of Hamming codes, only very few practical constructions have been designed and employed. Hamming codes are the most common used codes for protecting memory, although triple modular redundancy is used sometimes. Hamming codes are Single-Error-Correcting and Double-Error-Detecting (SECDED). BCH codes are another alternative for practical implementations of ECCs. They have better correcting capabilities than Hamming codes, but imply a higher latency. Thus, another research direction is a construction of low latency ECCs that offer multi-bit detection and correction in one cycle.