An achievable rate region for joint compression and dispersive information routing for networks

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing (DIR), wherein the intermediate nodes are allowed to split a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems, which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], DIR ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that the proposed approach offers better asymptotic performance than conventional routing techniques. We show that, under certain assumptions on the cost function, the problem of finding the minimum cost under DIR essentially reduces to characterizing an achievable rate region for a new multiterminal information theoretic setup. While it is possible to derive an achievable region for this setup using prior results from general multiterminal source coding [3], these techniques do not exploit the underlying problem structure and thereby lead to suboptimal regions. In this paper, we propose a new coding scheme, using principles from multiple descriptions encoding [2], and show that it strictly improves upon a corresponding variant of coding scheme in [3]. We further show that the new coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm.