# A Theory of Network Equivalence, Parts I and II - Computer Science > Information Theory

A Theory of Network Equivalence, Parts I and II - Computer Science > Information Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: A family of equivalence tools for bounding network capacities is introduced.Part I treats networks of point-to-point channels. The main result is roughlyas follows. Given a network of noisy, independent, memoryless point-to-pointchannels, a collection of communication demands can be met on the given networkif and only if it can be met on another network where each noisy channel isreplaced by a noiseless bit pipe with throughput equal to the noisy channelcapacity. This result was known previously for the case of a single-sourcemulticast demand. The result given here treats general demands - including,for example, multiple unicast demands - and applies even when the achievablerate region for the corresponding demands is unknown in the noiseless network.In part II, definitions of upper and lower bounding channel models for generalchannels are introduced. By these definitions, a collection of communicationdemands can be met on a network of independent channels if it can be met on anetwork where each channel is replaced by its lower bounding model andonly ifit can be met on a network where each channel is replaced by its upper boundingmodel. This work derives general conditions under which a network of noiselessbit pipes is an upper or lower bounding model for a multiterminal channel.Example upper and lower bounding models for broadcast, multiple access, andinterference channels are given. It is then shown that bounding the differencebetween the upper and lower bounding models for a given channel yields boundson the accuracy of network capacity bounds derived using those models. Bybounding the capacity of a network of independent noisy channels by the networkcoding capacity of a network of noiseless bit pipes, this approach representsone step towards the goal of building computational tools for bounding networkcapacities.

Author: ** Ralf Koetter, Michelle Effros, Muriel Medard**

Source: https://arxiv.org/