Information flow decomposition for network coding

TLDR

The most significant strength of our approach concerns future network coding practice. We propose a method to identify structural properties of multicast network configurations by decomposing networks into regions through which the same information flows. This decomposition shows that very different networks are equivalent from a coding point of view, allows us to divide the network coding problem into two almost independent tasks—graph theory and classical channel coding theory—and provides deterministic algorithms to specify coding operations at network nodes without knowledge of the overall network topology. The approach derives the smallest code alphabet size sufficient for any two‑source network as a function of the number of receivers and yields decentralized designs that easily accommodate future changes such as adding receivers or losing links.

Abstract

We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent tasks: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive the smallest code alphabet size sufficient to code any network configuration with two sources as a function of the number of receivers in the network. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose deterministic algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes that can easily accommodate future changes in the network, e.g., addition of receivers and loss of links