Since its introduction in the year 2000 by Ahlswede et al., the network coding paradigm has revolutionized the way we understand information flows in networks. Traditionally, information transmitted in a communication network was treated as a commodity in a transportation network, much like cars on highways or fluids in pipes. This approach, however, fails to capture the very nature of information, which in contrast to material goods, can be coded and decoded. The network coding techniques take full advantage of the inherent properties of information, and allow the nodes in a network, not only to store and forward, but also to "mix", i.e., encode, their received data. This approach was shown to result in a substantial throughput gain over the traditional routing and tree packing techniques. In this dissertation, we study applications of network coding for guarantying reliable and secure information transmission in networks with compromised edges. First, we investigate the construction of robust network codes for achieving network resilience against link failures. We focus on the practical important case of unicast networks with non-uniform edge capacities where a single link can fail at a time. We demonstrate that these networks exhibit unique structural properties when they are minimal, i.e., when they do not contain redundant edges. Based on this structure, we prove that robust linear network codes exist for these networks over GF(2), and devise an efficient algorithm to construct them. Second, we consider the problem of securing a multicast network against an eavesdropper that can intercept the packets on a limited number of network links. We recast this problem as a network generalization of the classical wiretap channel of Type II introduced by Ozarow and Wyner in 1984. In particular, we demonstrate that perfect secrecy can be achieved by using the Ozarow-Wyner scheme of coset coding at the source, on top of the implemented network code. Consequently, we transparently recover important results available in the literature on secure network coding. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction. In the last part of this dissertation, we study the connection between index coding, network coding, and matroid linear representation. We devise a reduction from the index coding problem to the network coding problem, implying that in the linear case these two problems are equivalent. We also present a second reduction from the matroid linear representability problem to index coding, and therefore, to network coding. The latter reduction establishes a strong connection between matroid theory and network coding theory. These two reductions are then used to construct special instances of the index coding problem where vector linear codes outperform scalar linear ones, and where non-linear encoding is needed to achieve the optimal number of transmission. Thereby, we provide a counterexample to a related conjecture in the literature and demonstrate the benefits of vector linear codes.

Dans cette thèse, nous avons étudié le problème de cache codée en construisant la connexion entre le problème de cache codée avec placement non-codé et codage d'index, et en tirant parti des résultats de codage d'index pour caractériser les limites fondamentales du problème de cache codée. Nous avons principalement analysé le problème de cache codée dans le modèle de diffusion à liaison partagée et dans les réseaux combinés. Dans la première partie de cette thèse, pour les réseaux de diffusion de liens partagés, nous avons considéré la contrainte que le contenu placé dans les caches est non-codé. Lorsque le contenu du cache est non-codé et que les demandes de l'utilisateur sont révélées, le problème de cache peut être lié à un problème de codage d'index. Nous avons dérivé des limites fondamentales pour le problème de cache en utilisant des outils pour le problème de codage d'index. Nous avons dérivé un nouveau schéma réalisable de codage d'index en base d'un codage de source distribué. Cette borne interne est strictement meilleure que la borne interne du codage composite largement utilisée. Pour le problème de cache centralisée, une borne externe sous la contrainte de placement de cache non-codé est proposée en base de une borne externe “acyclic” de codage d’index. Il est prouvé que cette borne externe est atteinte par le schéma cMAN lorsque le nombre de fichiers n'est pas inférieur au nombre d'utilisateurs, et par le nouveau schéma proposé pour le codage d’index, sinon. Pour le problème de cache décentralisée, cette thèse propose une borne externe sous la contrainte que chaque utilisateur stocke des bits uniformément et indépendamment au hasard. Cette borne externe est atteinte par le schéma dMAN lorsque le nombre de fichiers n'est pas inférieur au nombre d'utilisateurs, et par notre codage d'index proposé autrement. Dans la deuxième partie de cette thèse, nous avons considéré le problème de cache dans les réseaux de relais, où le serveur communique avec les utilisateurs aidés par le cache via certains relais intermédiaires. En raison de la dureté de l'analyse sur les réseaux généraux, nous avons principalement considéré un réseau de relais symétrique bien connu, `réseaux de combinaison’, y compris H relais et binom {H} {r} utilisateurs où chaque utilisateur est connecté à un r-sous-ensemble de relais différent. Nous avons cherché à minimiser la charge de liaison maximale pour les cas les plus défavorables. Nous avons dérivé des bornes externes et internes dans cette thèse. Pour la borne externes, la méthode directe est que chaque fois que nous considérons une coupure de x relais et que la charge totale transmise à ces x relais peut être limitée à l'extérieur par la borne externes du modèle de lien partagé, y compris binom {x} {r} utilisateurs. Nous avons utilisé cette stratégie pour étendre les bornes externes du modèle de lien partagé et la borne externe “acyclic” aux réseaux de combinaison. Dans cette thèse, nous avons également resserré la borne externe “acyclic” dans les réseaux de combinaison en exploitant davantage la topologie du réseau et l'entropie conjointe des diverses variables aléatoires. Pour les schémas réalisables, il existe deux approches, la séparation et la non-séparation. De plus, nous avons étendu nos résultats à des modèles plus généraux, tels que des réseaux combinés où tous les relais et utilisateurs sont équipés par cache, et des systèmes de cache dans des réseaux relais plus généraux. Les résultats d'optimisation ont été donnés sous certaines contraintes et les évaluations numériques ont montré que nos schémas proposés surpassent l'état de l'art. / In this thesis, we investigated the coded caching problem by building the connection between coded caching with uncoded placement and index coding, and leveraging the index coding results to characterize the fundamental limits of coded caching problem. We mainly analysed the caching problem in shared-link broadcast model and in combination networks. In the first part of this thesis, for cache-aided shared-link broadcast networks, we considered the constraint that content is placed uncoded within the caches. When the cache contents are uncoded and the user demands are revealed, the caching problem can be connected to an index coding problem. We derived fundamental limits for the caching problem by using tools for the index coding problem. A novel index coding achievable scheme was first derived based on distributed source coding. This inner bound was proved to be strictly better than the widely used “composite (index) coding” inner bound by leveraging the ignored correlation among composites and the non-unique decoding. For the centralized caching problem, an outer bound under the constraint of uncoded cache placement is proposed based on the “acyclic index coding outer bound”. This outer bound is proved to be achieved by the cMAN scheme when the number of files is not less than the number of users, and by the proposed novel index coding achievable scheme otherwise. For the decentralized caching problem, this thesis proposes an outer bound under the constraint that each user stores bits uniformly and independently at random. This outer bound is achieved by dMAN when the number of files is not less than the number of users, and by our proposed novel index coding inner bound otherwise. In the second part of this thesis, we considered the centralized caching problem in two-hop relay networks, where the server communicates with cache-aided users through some intermediate relays. Because of the hardness of analysis on the general networks, we mainly considered a well-known symmetric relay networks, combination networks, including H relays and binom{H}{r} users where each user is connected to a different r-subset of relays. We aimed to minimize the max link-load for the worst cases. We derived outer and inner bounds in this thesis. For the outer bound, the straightforward way is that each time we consider a cut of x relays and the total load transmitted to these x relays could be outer bounded by the outer bound for the shared-link model including binom{x}{r} users. We used this strategy to extend the outer bounds for the shared-link model and the acyclic index coding outer bound to combination networks. In this thesis, we also tightened the extended acyclic index coding outer bound in combination networks by further leveraging the network topology and joint entropy of the various random variables. For the achievable schemes, there are two approaches, separation and non-separation. In the separation approach, we use cMAN cache placement and multicast message generation independent of the network topology. We then deliver cMAN multicast messages based on the network topology. In the non-separation approach, we design the placement and/or the multicast messages on the network topology. We proposed four delivery schemes on separation approach. On non-separation approach, firstly for any uncoded cache placement, we proposed a delivery scheme by generating multicast messages on network topology. Moreover, we also extended our results to more general models, such as combination networks with cache-aided relays and users, and caching systems in more general relay networks. Optimality results were given under some constraints and numerical evaluations showed that our proposed schemes outperform the state-of-the-art.

In classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.

Network coding was introduced as a means to increase throughput in communication networks when compared to routing. Network coding can be used not only to communicate messages from some nodes in the network to other nodes but are also useful when some nodes in a network are interested in computing some functions of information generated at some other nodes. Such a situation arises in sensor networks. In this work, we study three problems in network coding. First, we consider the functional source coding with side information problem wherein there is one source that generates a set of messages and one receiver which knows some functions of source messages and demands some other functions of source messages. Cognizant of the receiver's side information, the source aims to satisfy the demands of the receiver by making minimum number of coded transmissions over a noiseless channel. We use row-Latin rectangles to obtain optimal codes for a given functional source coding with side information problem. Next, we consider the multiple receiver extension of this problem, called the functional index coding problem, in which there are multiple receivers, each knowing and demanding disjoint sets of functions of source messages. The source broadcasts coded messages, called a functional index code, over a noiseless channel. For a given functional index coding problem, the restrictions the demands of the receivers pose on the code are represented using the generalized exclusive laws and it is shown that a code can be obtained using the confusion graph constructed using these laws. We present bounds on the size of an optimal code based on the parameters of the confusion graph. For the case of noisy broadcast channel, we provide a necessary and sufficient condition that a code must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting functional index code. In the second problem, we explore relation between network function computation problems and functional index coding and Metroid representation problems. In a network computation problem, the demands of the sink nodes in a directed acyclic multichip network include functions of the source messages. We show that any network computation problem can be converted into a functional index coding problem and vice versa. We prove that a network code that satisfies all the sink demands in a network computation problem exists if and only if its corresponding functional index coding problem admits a functional index code of a specific length. Next, we establish a relation between network computation problems and representable mastoids. We show that a network computation problem in which the sinks demand linear functions of source messages admits a scalar linear solution if and only if it is matricidal with respect to a representable Metroid whose representation fulfils certain constraints dictated by the network computation problem. Finally, we study the usage of the sum-product (SP) algorithm for decoding network codes. Though lot of methods to obtain network codes exist, the decoding procedure and complexity have not received much attention. We propose a SP algorithm based decoder for network codes which can be used to decode both linear and nonlinear network codes. We pose the decoding problem at a sink node as a marginalize a product function (MPF) problem over the Boolean smearing and use the SP algorithm on a suitably constructed factor graph to perform decoding. We propose and demonstrate the usage of trace back to reduce the number of operations required to perform SP decoding. The computational complexity of performing SP decoding with and without trace back is obtained. For nonlinear network codes, we define fast decidability of a network code at sinks that demand all the source messages and identify a sufficient condition for the same. Next, for network function computation problems, we present an MPF formulation for function computation at a sink node and use the SP algorithm to obtain the value of the demanded function.

The network coding is a new paradigm that has been shown to improve throughput, fault tolerance, and other quality of service parameters in communication networks. The basic idea of the network coding techniques is to relish the "mixing" nature of the information flows, i.e., many algebraic operations (e.g., addition, subtraction etc.) can be performed over the data packets. Whereas traditionally information flows are treated as physical commodities (e.g., cars) over which algebraic operations can not be performed. In this dissertation we answer some of the important open questions related to the network coding. Our work can be divided into four major parts. Firstly, we focus on network code design for the dynamic networks, i.e., the networks with frequently changing topologies and frequently changing sets of users. Examples of such dynamic networks are content distribution networks, peer-to-peer networks, and mobile wireless networks. A change in the network might result in infeasibility of the previously assigned feasible network code, i.e., all the users might not be able to receive their demands. The central problem in the design of a feasible network code is to assign local encoding coefficients for each pair of links in a way that allows every user to decode the required packets. We analyze the problem of maintaining the feasibility of a network code, and provide bounds on the number of modifications required under dynamic settings. We also present distributed algorithms for the network code design, and propose a new path-based assignment of encoding coefficients to construct a feasible network code. Secondly, we investigate the network coding problems in wireless networks. It has been shown that network coding techniques can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks each packet transmitted by a device is broadcasted within a certain area and can be overheard by the neighboring devices. When a device needs to transmit packets, it employs the Index Coding that uses the knowledge of what the device's neighbors have heard in order to reduce the number of transmissions. With the Index Coding, each transmitted packet can be a linear combination of the original packets. The Index Coding problem has been proven to be NP-hard, and NP-hard to approximate. We propose an efficient exact, and several heuristic solutions for the Index Coding problem. Noting that the Index Coding problem is NP-hard to approximate, we look at it from a novel perspective and define the Complementary Index Coding problem, where the objective is to maximize the number of transmissions that are saved by employing coding compared to the solution that does not involve coding. We prove that the Complementary Index Coding problem can be approximated in several cases of practical importance. We investigate both the multiple unicast and multiple multicast scenarios for the Complementary Index Coding problem for computational complexity, and provide polynomial time approximation algorithms. Thirdly, we consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to-peer, or massive storage network. Parts of the data can be stored in either original form, or encoded form at multiple network locations. Clients access the parts of the data through simultaneous downloads from several servers across the network. For each link used client has to pay some cost. A client might not be able to access a subset of servers simultaneously due to network restrictions e.g., congestion etc. Furthermore, a subset of the servers might contain correlated data, and accessing such a subset might not increase amount of information at the client. We present a novel efficient polynomial-time solution for this problem that leverages the matroid theory. Fourthly, we explore applications of the network coding for congestion mitigation and over flow avoidance in the global routing stage of Very Large Scale Integration (VLSI) physical design. Smaller and smarter devices have resulted in a significant increase in the density of on-chip components, which has given rise to congestion and over flow as critical issues in on-chip networks. We present novel techniques and algorithms for reducing congestion and minimizing over flows.

Network coding has emerged as an attractive alternative to routing because of the through put improvement it provides by reducing the number of channel uses. In a wireless scenario, in addition, further improvement can be obtained through Physical layer Network Coding (PNC), a technique in which nodes are allowed to transmit simultaneously, instead of transmitting in orthogonal slots. In this thesis, the design and analysis of network coding schemes are considered, for wireless two-way relaying, multi-user Multiple Access Relay Channel (MARC) and wireline networks. In a wireless two-way relay channel with PNC, the simultaneous transmissions of user nodes result in Multiple Access Interference (MAI) at there lay node. The harmful effect of MAI is the presence of signal set dependent deep channel fade conditions, called singular fade states, under which the minimum distance of the effective constellation at the relay become zero. Adaptively changing the network coding map used at the relay according to channel conditions greatly reduces the impact of this MAI. In this work, we obtain these adaptive PNC maps, which are finite in number ,by completing partially filled Latin Squares and using graph vertex coloring. Having obtained the network coding maps, the set of all possible channel realizations is quantized into a finite number of regions, with a specific network coding map chosen in a particular region and such a quantization is obtained analytically for 2λ-PSK signal set. The performance of the adaptive PNC scheme for two-way relaying is analyzed and tight high SNR upper bounds are obtained for the average end-to-end symbol error probability, in terms of the average error probability of a point-to-point fading channel. The adaptive PNC scheme is generalized for two-way relaying with multiple antennas at the nodes. As an alternative to the adaptive PNC scheme for two-way relaying, a Distributed Space Time Coding (DSTC) scheme is proposed, which effectively re-moves the effect of singular fade states at the transmitting nodes itself without any Channel State Information at the Transmitter (CSIT), and without any need to change the PNC map as a function of channel fade conditions. It is shown that the singular fade states can be viewed equivalently as vector subspaces of C2, which are referred to as the singular fade subspaces. DSTC design criterion to minimize the number of singular fade subspaces and maximize the coding gain is formulated and explicit low decoding complexity DSTC designs are provided. For the K-user MARC, in which K source nodes want to transmit messages to a destination node D with the help of are lay node R, a new PNC scheme is proposed. Use of a many-to-one PNC map with conventional minimum squared Euclidean distance decoding at D, results in a loss of diversity order due to error propagation from the relay node. To counter this, we propose a novel low complexity decoder which offers the maximum diversity order of two. Next, we consider wire line networks and explore the connections between linear network coding, linear index coding and discrete polymatroids, which are the multi-set analogue of matroids. We define a discrete polymatroidal network and show that a fractional vector linear solution over a field Fq exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over Fq.An algorithm to construct networks starting from certain class of discrete polymatroids is provided. Every representation over Fq for the discrete polymatroid, results in a fractional vector linear solution over Fq for the constructed network. It is shown that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. Multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.