Information Flow Decomposition for Network Coding

The famous min-cut, max-flow theorem states that a source node can send a commodity through a network to a sink node at the rate determined by the flow of the min-cut separating the source and the sink. Recently it has been shown that by linear re-encoding at nodes in communications networks, the min-cut rate can be also achieved in multicasting to several sinks. Constructing such coding schemes efficiently is the subject of current research. The main idea in this paper is the identification of structural properties of multicast configurations, by decompositing the information flows into a minimal number of subtrees. This decomposition allows us to show that very different networks are equivalent from the coding point of view, and offers a method to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent problems: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive tight bounds on the network code alphabet size and calculate the throughput improvement network coding can offer for different configurations. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose 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 which can easily accommodate future changes in the network, e.g., addition of receivers and loss of links.