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

Riis, Søren; Gadouleau, Maximilien

Abstract

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, vaguely akin to Kripke's possible worlds from logic and philosophy. Link failures, point failures, changes in network topology during transmission, changes in receivers demands etc. can all be modelled, in a discrete fashion, by considering a multiverse where different possible worlds (hypothetical situations) are modelled as worlds existing in parallel. Nodes with the same labels might represent nodes in parallel worlds that behave, in the same way, as they are unaware of which world becomes the actual world. 2) We introduce the term model, which is a simple, graph-free symbolic approach to communication networks. We use the term model to create an algorithm (based on the max-flow min-cut algorithm) that calculates the information-theoretic limit for the capacity of a given communication network. We notice that different non-isomorphic communication networks might never-the-less be mathematically identical because they lead to the same term model. We illustrate the power of our formalism through a number of examples. 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 and states that the minimal cut value (the channel capacity) can be achieved asymptotically. The theorem is proved by combining Menger's theorem from graph theory with an argument that is similar to the proof of Shannon fundamental theorem for memoryless noisy channels. To prove the theorem we introduce a very weak kind of network coding (network coding lite), which we will refer to as 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. One technical result is a max-flow min-cut theorem for the Rényi 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 the Rényi entropy with order greater than one. We leave the status of the theorem with regards to the ordinary Shannon Entropy measure (Rényi entropy of order one and the limit case between validity or failure of the theorem) as an open question. In non-dynamic static communication networks with a single receiver, a simple application of Menger's theorem shows that the optimal throughput can be achieved without proper use of network coding i.e. just by using ordinary packet-switching. This fails dramatically in relay networks with a single receiver. We show that even a powerful method like linear network coding fails miserably for relay networks. With that in mind, it is noticeable that our rather weak form of network coding (routing with dynamic headers) is asymptotically sufficient to reach capacity.

Citation

Riis, S., & Gadouleau, M. (2019). Max-flow min-cut theorems on dispersion and entropy measures for communication networks. Information and Computation, 267, 49-73. https://doi.org/10.1016/j.ic.2019.03.004

• Journal Article Type: Article
• Online Publication Date: Mar 19, 2019
• Publication Date: Aug 31, 2019
• Deposit Date: Mar 19, 2019
• Publicly Available Date: Mar 19, 2020
• Journal: Information and Computation
• Print ISSN: 0890-5401
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 267
• Pages: 49-73
• DOI: https://doi.org/10.1016/j.ic.2019.03.004
• Public URL: https://durham-repository.worktribe.com/output/1300725