We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Riis, Søren and Gadouleau, Maximilien (2019) 'Max-flow min-cut theorems on dispersion and entropy measures for communication networks.', Information and computation., 267 . pp. 49-73.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2019 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:No date available
Date deposited:19 March 2019
Date of first online publication:19 March 2019
Date first made open access:19 March 2020

Save or Share this output

Look up in GoogleScholar