The theoretical foundation of network coding was first proposed by Ahlswede et al. in their seminal paper [2], in which, they describe network coding as “employing coding at the nodes”. Unlike conventional networks, network coding allows the intermediate nodes to encode the incoming packets before forwarding them. Inspired by computer network applications, they formulate a problem called “network information flow”, and show that network coding has to be employed to achieve the information’s Max-flow in a multicast network [2]. Stated that network coding is capable to reach the full theoretical network capacity with transmission rate in multi-source multicast scenarios, their result could be regarded as Max-flow Min-cut Theorem for network information flow, which could not be considered as “fluid” or some kinds of physical entity as in classical information theory for point-to-point communication. Network coding soon generated intensive attention for it is considered as an elegant and novel technique to improve future network throughput and performance [3]. Moreover, it offers benefits over wireless network, radio network and is robust against attacks from malicious nodes [4], eavesdropping agents [5] and outside interference such as noise and erasure [6, 7] thanks to the coding nature. Network coding demonstrated its advantages through a number of practical projects such as, Microsoft’s Avalanche, a file distributing P2P system; MIT’s COPE, a new architecture for wireless mesh network [8].

Until now, tons of works have been carried out to lay the foundation of this new trans- mission paradigm. To simplify the network model, Li et al. argue that it is sufficient to achieve the theoretical network capacity by just transmitting messages as a linear combination of messages at input edges of each node, and introduce a sub-class of net- work coding, called linear network coding [9]. They also propose, probably not optimal, a greedy algorithm to construct the network code, which is the set of all coding co- efficients in all network nodes, for acyclic communication network [9]. While network model in [9] is delay free that considers messages as the symbols of a finite field, at the mean time, Koetter and Medard propose a complete algebraic framework to cover up to delay linear network coding [10]. Koetter and Medard deem the complex graph structure of the network by considering the dynamics at each node, model the general network model as a form of linear time invariant system and figure out the relationship between sending information and receiving information through a system matrix [10]. They then analyze the network linear solvability and also consider the problem of net- work recovery for non-ergodic edge failures. Fragouli et al. yet, inspect the properties of linear network code by translating it into the graph coloring problem, then use some tools of discrete mathematics on code construction [11]. On the other hand, in matroids theory manner, Dougherty et al. carry out a series of works to thoroughly study the properties of linear network code [12, 13, 14]. While Li et al. [9] and Koetter et al. [10] state that for a feasible network, the network code always exist when the field size if sufficient large, Dougherty et al. [12] indicate that a multicast network that has a solution for a given field might not have a solution for all larger fields. They continue to claim the limits of linear network code by arguing that the general network code is about 10% greater in capacity than linear network code [13] and by constructing a new class of network called Vamos network from Vamos matroids to prove the insufficiency of Shannon-type information inequalities in computing the network coding capacities [14]. Further studies on linear network code reveal its failures in completely solving multiple- source multicast problems [15]. Later, the capacity of linear network code is discovered by Song et al. [16], where they calculate its inner and outer bounds. As one of the efforts to eliminate such limitations, Barros et al. propose an idea to convert coding at correlated information multi-source to a form of distributed source coding [17]. Indeed, network coding in general has much more potential than the linear one. However, due to the computational complexity and theoretical difficulties, most of works till today still focus on the linear version. The interest in this area is still increasing with the various applications in both theory foundation and practice, and can be viewed from various approaches like coding theory, information theory, algebraic mathematics, networking securities [8].

One of the most primitive topics related to network coding is network code construction. Many algorithms have been proposed corresponding to different context and use-cases with different problem formulations. In transmission network model, it is important that whether the receivers and/or intermediate transmitters know the network topology, be- cause it regulates the way network code is constructed. In the network with known topology, or coherent network, the coding and decoding agents have full knowledge of network structure, so that a central authority can optimally calculate network code that achieves its own transmitting criteria. Deterministic or semi-ramdomized code construc- tion is capable to be conducted in the centralized manner, by a central authority or a super-node. Apart from the very basic code construction introduced along with their main network coding theorem in [9] and [10], there are some others, more effective tech- niques as proposed in Jaggi et al. [18], Harvey et al. [19], Langberg et al. [20]. Jaggi et al ’s algorithm [18] is an improvement of flow path approach proposed in [9], formulate a single source multicast network then find the independent paths from source to receivers, each has a flow equivalent to number of source processes. They utilize existing graph algorithms to re-arrange the nodes in the topological order, then track through edges at a time in such topological order to optimally choose information flow paths. Their algorithm consists of two procedures, one is deterministic linear information flow (DLIF) and the other is semi-randomized linear information flow (LIF) [18]. In the same work, they also present the variances, a faster routine of code choosing by increasing its ran- domized percentage and dealing with path failure. Similarly, Langberg et al. [20] speed up their code design by reduce the network to a minimal encoding nodes. Meanwhile, Harvey et al. [19] present another deterministic algorithm based on maximum-rank completion of mixed matrices, which appears to perform faster than Jaggi et al ’s algo- rithms. When the network topology is unknown to receivers and intermediate nodes, which we usually call non-coherent network, i.e., the INTERNET or intra-net with so many users join and leave that the network structure keeps changing and undefined, the above-mentioned deterministic algorithms are inapplicable and randomized code con- struction becomes the best solution. In the randomized code construction manner, each intermediate node autonomously chooses its own local encoding coefficients every time it performs coding and forwarding messages into output edges, leading to the changing of coding coefficients continuously. Decoding at the receivers could be done by 2 possible techniques, subspace coding at the source [21] or memorizing the coding coefficients in the information packets themselves by adding a redundancy in to the information packet headers at the source [3]. This approach was first proposed by Ho et al. [22] in 2003 and then, re-summarized, standardized and expanded in 2006 [23] with the network model proposed in Koetter et al. [10]. In their work, Ho et al. state that with a sufficiently large base field, the probability that the information is successfully decoded converses to 1 [23]. The code construction problem, now reduces to the problem of choosing appro- priate field sized regarded to network scalability. Because randomized code construction technique is robust against network topology changing, it is said to be highly applicable in practice and attracts much of attention in the literature.

The next topic in network coding theory is to design a secure network channel, which is to design the network code so that it can transmit the source messages securely, be- cause the network is likely to be attacked by some passive or active attackers. We refer here the passive attackers to some outside agents, or eavesdropper trying to wiretap the network and wish to learn some useful information transmitted over the network, while active attacks are some malicious nodes or jammers, who have both eavesdropping and jamming abilities, trying to inject false information into the network, intentionally caus- ing false decoding results. For both attacking schemes, adversaries are assumed to have unlimited computational power and full knowledge of network topology [24]. Similar to network code design, code design for secure network is also divided into coherent case and non-coherent case. Secure communication against eavesdroppers in the context of coherent network coding has been started by Cai and Yeung [25]. This line of works were continued to follow by Feldman et al. [26], Rouayheb et al. [27, 28] and even cyclic network security is also studied in the work of Jain [29]. The main principle of securing the network is to design the network code in a way that mutual information between source messages and the information taken by eavesdroppers is equal to zero, or less than a predefined threshold value. To this end, some may specify the linear operation (pre-encoding at the source node) to define the messages to be actually transmitted [25, 26], the others concentrate on the design of network code to satisfy some additional constraints as well [28]. Network security and good-put are the trade-off, which mean, one can not design a network with full good-put and secure against outside eavesdrop- pers, and the works in this topic are just trying to suppress the degradation of good-put and lower the necessary base field size. Randomized network coding, or non-coherent network coding, on the other hand, has natural security against eavesdropping attack [30]. Network security against active attackers, or jammers can be called network er- ror detection and correction. With the presence of Jammers, network can be suffered from error and erasure, in which, errors come from the channel noise, false packets in- jection by malicious node and erasures come from the path failure. Although different in nature, both error and erasure can be modeled in the same mathematics form, and they are usually called in a simple term, network error. The full definition and problem formulations of network error correction are presented in the works of Cai and Yeung [6, 7], where they extend the classical coding theory into the context of network coding. One of the most effective error detection scheme was proposed in Oggier et al. [31], in which they designed an unconditionally secure authentication code distributed by a trusted authority to all the intermediate nodes and receivers, so that error is checked at every transmission step before reaching the receivers. Dealing with the increasing of network complexity, Ho et al. presented a framework for network management in in term of different network codes, under different failures [32]. They compare 2 types of packet recovery schemes, receiver-based and network-wide in a centralized manner, when the network behavior is known. Network error correction code analysis and con- struction can be reduced to deterministic construction of maximum distance separable (MDS) codes inherited from classical coding theory, and this is possible under some prerequisites. Yang et al. presented a refined version of the Hamming bound, the Sin- gleton bound and the Gilbert-Varshamov bound for coherent network error correction [33]. Matsumoto et al. [34] give a centralized deterministic algorithm for constructing linear network error-correcting codes that attain the Singleton bound of network error- correcting codes based on algorithms of Jaggi et al. Based on the extension of classical error correcting code, one can invent a lot of variances, like the works by Bahramgiri and Lahouti [35], Zhang [36], Guang et al. [37]. On the other hand, non-coherent networks utilize completely different approaches. Randomized network coding is studied in [23], where the randomized construction of network code is said to be possible if the base field size is sufficiently large. Because network code keeps changing, the receivers could not decode the messages in traditional manner, but have to apply statistical decoding [36] or subspace coding [21]. In statistical decoding manner, global encoding vector needs attaching with the message itself, thus, the sender has to append a unitary vector to the header of each message packet [3]. Such unitary vector will be modified when coding operation is performed at each node, become the memory region to store global encoding coefficients. The receivers will read this memory region to construct the de- coding matrix [3]. Two decoding algorithms are proposed in Zhang et al. [36], one is the brute force algorithm based on minimum possible rank of error patterns, and the other is a faster decoder based on Gaussian elimination. Although statistical decoding is easy to implement in practice, it raises some vulnerable security problem. First, global encoding kernel attached to the head of each message is transparent to eavesdroppers, resulting in easily being wiretapped by outside agents. Second, message headers can be corrected and modified, causing the uncontrollable false decoding results at the re- ceivers [36]. Subspace coding solves these problems. Subspace coding is firstly proposed in a work of Koetter and Kschishchang [21] and then quickly adopted by the others, such as Yang et al. [38], Bossert and Gabidulin [39]. In subspace coding, codewords at the source and receivers are not messages but subspaces. The network is considered as a linear operator channel (LOC), transmitting the source space to destination space [38]. The destination space depends only on the source space and network topology, but not network code. In the presence of erasures and errors, received subspace and its dimension will be modified and the decoder will decode the received subspace in term of minimum subspace distance method [21]. A rank metric version of subspace coding is presented by Silva et al. [40], where subspace is converted a matrix and subspace dimension is converted to matrix rank, a practical version of subspace coding. The are some more progress regarding to subspace coding such as Gadouleau et al. [41], Silva et al. [42].

Looking back to the past 15 years of network coding history, a considerable works have been done. With the concrete theoretical bases such as algebra, coding theory, graph theory, information theory, the development of network coding theory were as simple as “expanding the base to a new land”. However, most of the those works focus on non- delay model of network coding. Although in [10, 23], the basic model of delay network coding is presented, there is no further investigation and decoding scheme proposed. Moreover, their delay linear network coding solvability is based on z-transform, which is hard to implement in practice because it requires the transmission over a infinite time curve. Recently, Lvov et al. [43] apply LTI system theory into delay network coding, where they consider the delay linear network coding as a discrete LTI system, and analyse the system respond the discover the information transmission characteristics. In our work, we take the similar approach to Lvov et al ’s. We develop a complete decoding algorithms for multicast network, extend the network coding error correction technique to delay network context.

We first defines develops an equivalent framework with [10] in time domain based on the Gauss Jordan elimination which includes an algorithm to reconstruct source processes and define new notions: decoding delay and transmission rate. We then extend the classical NEC to the case of DLNC, propose an algorithm to design codebook that achieves maximum possible size. The network error control problem in such network can be done by extending the classical network error- correcting code (NEC). We construct a DLNC based linear operation channel (LOC) and apply the distance measure proposed in [1] to our LOC. After that, we provide the numerical examples for the theory developed in this thesis. Such examples range from setting up a network from scratch, calculating network properties, recovering source processes in error-free network to codebook design and correcting error in erroneous network.

We developed a theoretical framework to work with erroneous delay linear network coding. The errors in the network, maybe of any form: attacking from outside agent, malicious node, edge failures or simply noise during the transmission. To this end, we first developed a Gauss Jordan elimination based decoding algorithm to reconstruct source processes at each receiver. The algorithm is in time domain, and successfully implemented in Matlab. The algorithm proposed in this thesis is equivalent with that of [10]. Moreover, it is more practical and easier to implement by a programming language. Based on this result, we form a practical linear operation channel, apply the existing weight and distance measures to analyze the network error-correcting capability. This formulation of LOC significantly reduces the dimension of codebook and minimizes the number of linear operations, making it much easier to design a minimum weight decoder to correct network errors. The work results in the concept and definition of codebook in coherent DLNC for both cases: full rate and not full rate. Here, we carefully define necessary objects and spaces to deal with the case of non-full rate network. To practically construct and set up an optimal codebook for the network, we proposed an algorithm to design a codebook that achieves the maximum possible size. Before that, we proved the upper and lower bounds for the maximum possible size of the codebook. The accuracy of the algorithm and optimality of the output are thoroughly proved. Finally, we provided the numerical examples to demonstrate our theory. We set up the butterfly network parameters from scratch, calculated network properties such as decoding delay and transmission rate. We also wrote a demo application in Matlab to execute the decoding algorithm and got the accurate decoding results. We then simulated the errors in the network by injecting a random signal at one edge of the network. With this model, we constructed an LOC, distance measure. We design the codebook by proposed algorithm and confirm the accuracy by comparing it with upper and lower bounds. Finally, we wrote a demo application to decode and correct that error. The application return the accurate value of source processes, which once more demonstrates the accuracy of the MWD mechanism.

Future directions may concern with the development of NEC for the specific classes of network errors; design of network code to release some NEC design constraints to increase the network error-correcting capability; application of other NEC for DLNC such as convolutional code and NEC for non-coherent network. If we narrow the classes of error, for examples when we design a local network system, it is possible to know which edges are erroneous and which edges are secure, we are able to design an error class driven NEC, which focuses on correcting such kind of error but not a general one. With the knowledge of error’s class, we can also design a network code, in which the error is minimally transfered to every receivers. Thus, we can design NEC with less minimum distance and larger size, resulting in increase of good-put. We may apply other NEC for DLNC, such as convolutional code. Finally, non-coherent DLNC, where the network code keeps changing randomly and continuously, needs other NECs, such as subspace coding or rank metric code.