Network - Coded Multihop Multicast: Topology and Complexity

In this thesis, we present some novel results on network coding complexity and its relations with the network topology. In particular, the complexity is evaluated in terms of the number of nodes which have to perform coding operations in order to achieve the multicast capacity. Different network topologies and the corresponding complexity are investigated by means of proper simulation algorithms. Both theoretical considerations and simulation guidelines for different networks are presented.
The rest of the thesis is structured as follows. In Chapter 1, we provide an overview on the literature in the field of network coding, by discussing what linear network coding does in order to achieve the multicast capacity. Moreover, we present a brief discussion on graph theory and the main network coding theorem. Finally, we introduce the different definitions of complexity which can be employed for the evaluation. Important theoretical bounds on the minimum number of nodes which have to perform coding operations in order to achieve the network capacity are presented. In Chapter 2 and Chapter 3, we analyze the network coding complexity, defined as the minimum number of coding points, in scenarios where the network topology is defined by a random graph and by pseudo random multihop graph, respectively. This allows to identify topology patterns which require more encoding complexity. In Chapter 4, we propose an analytical framework for network topology characterized by a pseudo random multi-hop graph. Finally, we present and analyze other minimal network topologies with a relatively large number of coding points.