Koetter, Ralf and Effros, Michelle and Médard, Muriel (2010) A Theory of Network Equivalence, Parts I and II. . (Submitted) https://resolver.caltech.edu/CaltechAUTHORS:20120531144116913

PDF
 Submitted Version
See Usage Policy. 832kB 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20120531144116913
Abstract
A family of equivalence tools for bounding network capacities is introduced. Part I treats networks of pointtopoint channels. The main result is roughly as follows. Given a network of noisy, independent, memoryless pointtopoint channels, a collection of communication demands can be met on the given network if and only if it can be met on another network where each noisy channel is replaced by a noiseless bit pipe with throughput equal to the noisy channel capacity. This result was known previously for the case of a singlesource multicast demand. The result given here treats general demands  including, for example, multiple unicast demands  and applies even when the achievable rate region for the corresponding demands is unknown in the noiseless network. In part II, definitions of upper and lower bounding channel models for general channels are introduced. By these definitions, a collection of communication demands can be met on a network of independent channels if it can be met on a network where each channel is replaced by its lower bounding model and only if it can be met on a network where each channel is replaced by its upper bounding model. This work derives general conditions under which a network of noiseless bit pipes is an upper or lower bounding model for a multiterminal channel. Example upper and lower bounding models for broadcast, multiple access, and interference channels are given. It is then shown that bounding the difference between the upper and lower bounding models for a given channel yields bounds on the accuracy of network capacity bounds derived using those models. By bounding the capacity of a network of independent noisy channels by the network coding capacity of a network of noiseless bit pipes, this approach represents one step towards the goal of building computational tools for bounding network capacities.
Item Type:  Report or Paper (Working Paper)  

Related URLs: 
 
Alternate Title:  A Theory of Network Equivalence. Part I: PointtoPoint Channels, A Theory of Network Equivalence. Part II: Multiterminal Channels  
Additional Information:  Submitted to the IEEE Transactions on Information Theory on April 14, 2010. Draft 2.  
Subject Keywords:  Capacity, network coding, equivalence, component models  
Record Number:  CaltechAUTHORS:20120531144116913  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:20120531144116913  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  31756  
Collection:  CaltechAUTHORS  
Deposited By:  INVALID USER  
Deposited On:  31 May 2012 21:56  
Last Modified:  03 Oct 2019 03:54 
Repository Staff Only: item control page