Max-flow min-cut theorems on dispersion and entropy measures for communication networks

摘要

The paper presents four distinct new ideas and results for communication networks:1) We show that relay-networks (i.e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, akin to Kripke's possible worlds. Changes in the network are modelled by considering a multiverse where different possible situations arise as worlds existing in parallel.2) We introduce the term model, which is a simple, graph-free symbolic approach to communication networks. This model yields an algorithm to calculate the capacity of a given communication network.3) We state and prove variants of a theorem concerning the dispersion of information in single-receiver communications. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks. The proof uses a very weak kind of network coding, called routing with dynamic headers.4) We show that the solvability of an abstract multi-user communication problem is equivalent to the solvability of a single-target communication in a suitable relay network. In the paper, we develop a number of technical ramifications of these ideas and results. We prove a max-flow min-cut theorem for the Renyi entropy with order less than one, given that the sources are equiprobably distributed; conversely, we show that the max-flow min-cut theorem fails for order greater than one. We also show that linear network coding fails for relay networks, although routing with dynamic headers is asymptotically sufficient to reach capacity. (C) 2019 Elsevier Inc. All rights reserved.