Network Coding

The demand for higher throughput and better efficiency are two important challenges for future communication networks. During the past decades, a lot of research studies have been devoted to investigating and proposing near optimal and efficient schemes and algorithms for point-to-point communication. However, in communication networks, especially in wireless systems, we require more intricate algorithms and coding schemes that are optimized for networks rather than for point-to-point communications. In recent years, the network coding paradigm has opened new opportunities for network information flow algorithms. In the first part of the thesis, we consider a non-coherent transmission scenario in a network performing randomized linear network coding. Our main goal is to find the optimal performance in terms of communication rate in such a transmission scenario and to discover the optimal coding scheme to achieve it. It is observed by Koetter et al. [1] that because the network performs an unknown linear transformation, coding over subspaces spanned by the source packets could be a reasonable coding scheme. In order to make this claim information-theoretically justified, we study a multiplicative matrix channel over a finite field with a uniform and independent distribution over the transfer matrix. The capacity for this unicast communication scenario is characterized and it is shown that coding over subspaces is indeed optimal. A similar result is also derived for the two users multiple access problem in such a non-coherent network coding scenario. We then generalize this model by proposing a more universal scenario which is based on an arbitrarily varying channel approach. This result shows the optimality of subspace coding for a wider class of matrix channels, i.e., the channels where only the rank distribution of the transfer matrix is known. Moreover, the above results show that the overhead of schemes based on coding vectors is negligible for many practical situations, i.e., the situations where the rank of the transfer matrix is concentrated around some integer number. Next, we observe that in a network performing randomized linear network coding, the coding vectors carry topological and state-dependent information about the network. Considering the subspaces spanned by the coding vectors at the relay nodes of the network, we investigate the properties of these subspaces and leverage them for some practical problems including network tomography, network management, and Byzantine attack detection. In the last part of the thesis, we consider the problem of secret key sharing among multiple nodes in a network, in the presence of a passive eavesdropper. We assume that there exists a broadcast channel from one of the trusted nodes to the rest of them (including the eavesdropper). Moreover, we assume that the trusted entities can discuss over a public channel overheard by everyone. The secrecy key generation capacity for this problem is still unknown (in general, there exist only some upper and lower bounds). For the erasure broadcast channel as well as the linear deterministic wireless broadcast channel, we propose optimal and efficient schemes that enable arbitrary number of legitimate entities to share a secret key among themselves. By extending these results, we propose achievability schemes for the non-coherent network coding broadcast channel and the state-dependent Gaussian wireless broadcast channel.