A Theory of Network Equivalence-Part I: Point-to-Point Channels

作者：Koetter Ralf; Effros Michelle; Medard Muriel

来源：IEEE Transactions on Information Theory, 2011, 57(2): 972-995.

DOI：10.1109/TIT.2010.2102110

• Capacity
• component models
• equivalence
• network coding

A family of equivalence tools for bounding network capacities is introduced. Given a network N with node set V, the capacity of N is a set of non-negative vectors with elements corresponding to all possible multicast connections in N; a vector R is in the capacity region for N if and only if it is possible to simultaneously and reliably establish all multicast connections across N at the given rates. Any other demand type with independent messages is a special case of this multiple multicast problem, and is therefore included in the given rate region. In Part I, we show that the capacity of a network N is unchanged if any independent, memoryless, point-to-point channel in N is replaced by a noiseless bit pipe with throughput equal to the removed channel's capacity. It follows that the capacity of a network comprised entirely of such point-to-point channels equals the capacity of an error-free network that replaces each channel by a noiseless bit pipe of the corresponding capacity. A related separation result was known previously for a single multicast connection over an acyclic network of independent, memoryless, point-to-point channels; our result treats general connections (e. g., a collection of simultaneous unicasts) and allows cyclic or acyclic networks.

• 出版日期2011-2