CaltechAUTHORS
  A Caltech Library Service

A Theory of Network Equivalence, Parts I and II

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

[img]
Preview
PDF - Submitted Version
See Usage Policy.

813Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120531-144116913

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 roughly as follows. Given a network of noisy, independent, memoryless point-to-point 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 single-source 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:
URLURL TypeDescription
http://arxiv.org/abs/1007.1033arXivUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5695102&tag=1Related ItemUNSPECIFIED
Alternate Title:A Theory of Network Equivalence. Part I: Point-to-Point 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:20120531-144116913
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120531-144116913
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:31756
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:31 May 2012 21:56
Last Modified:26 Dec 2012 15:17

Repository Staff Only: item control page