Introduction
An integral part of optimizing resources in communication networks is routing of information. In this work we consider the problem of minimizing the communication cost for a general multi-hop network with correlated sources and multiple sinks. A typical multi-hop network is shown in the figure.
This problem is a very recent and exciting development within this project and forms the preliminary basis for a new project funded by NSF under grant CCF-1016861. As part of the new project, we will be fully pursuing this and related directions.
Let a network G be given with N source nodes, M sinks and |V | − N −M intermediate nodes. Each edge e is a network link whose communication cost depends on the edge weight we. Source node i observes random variable Xi. Each sink Sj requests for a subset of sources represented by Vj . Conversely each source Vi is to be reconstructed at a subset of sinks denoted by Si. Our objective is to design joint coding-routing schemes to minimize the overall network cost (calculated given the set of link rates and edge weights) for reconstruction of source information at appropriate sinks.
For the single sink scenario, it has been shown that this problem can be decoupled, without loss of optimality, into two separate subproblems of distributed source coding and finding the optimal routing (transmission structure). It has further been established that, under certain assumptions, such decoupling also applies in the general case of multiple sinks and arbitrary network demands. We showed that these assumptions are significantly restrictive, and further provided examples to substantiate the loss, including settings where removing the assumptions yields unbounded performance gains. An approach to solving the unconstrained problem, where routing and coding cannot be decoupled, was derived based on Han and Kobayashi’s achievability region for multi-terminal coding.
We introduced a new routing paradigm, called dispersive information routing, wherein the intermediate nodes are allowed to forward a subset of the received bits on subsequent paths. This paradigm opens up a rich class of research problems which focus on the interplay between encoding and routing in a network. What makes it particularly interesting is the challenge in encoding sources such that, exactly the required information is routed to each sink, to reconstruct the sources they are interested in. We demonstrated using simple examples that our approach offers better asymptotic performance than conventional routing techniques. We also introduced a variant of the well known random binning technique, called ‘power binning’, to encode and decode sources that are dispersively transmitted, and which asymptotically achieves the minimum communication cost within this routing paradigm.
Inspired by our recent work on distributed source coding and fusion coding, we proposed a practical design approach to implement dispersive information routing. We demonstrated the close similarities between dispersive information routing, 
Multiple descriptions (MD) problem was introduced in late seventies in the information theory community with a motivation towards packet switched networks. The setup involves L channels between a source and a sink, out of which a subset of the channels are assumed to fail. The encoder generates L descriptions, each sent on one of the channels. Depending on the failure, a subset of these L descriptions are lost. It is assumed that the the encoder is unaware of which channels might fail. The objective is to design the L descriptions and the decoders (for each possible received combination of descriptions) with respect to an over all rate-distortion trade-off. The general problem has remained challenging and unsolved. We proposed a new encoding technique called `combinatorial message sharing' using principles from dispersive information routing and showed that the new achievable region is strictly larger than the most popular region for this setup so far due to Venkataramani, Kramer and Goyal.