دانلود مقاله Network Information Flow

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 46, NO. 4, JULY 2000

Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Senior Member, IEEE, and
Raymond W. Yeung, Senior Member, IEEE

Abstract—We introduce a new class of problems called network
information flow which is inspired by computer network applications.
Consider a point-to-point communication network on which
a number of information sources are to be mulitcast to certain sets
of destinations. We assume that the information sources are mutually
independent. The problem is to characterize the admissible
coding rate region. This model subsumes all previously studied
models along the same line. In this paper, we study the problem
with one information source, and we have obtained a simple characterization
of the admissible coding rate region. Our result can be
regarded as the Max-flow Min-cut Theorem for network information
flow. Contrary to one’s intuition, our work reveals that it is in
general not optimal to regard the information to be multicast as a
“fluid” which can simply be routed or replicated. Rather, by employing
coding at the nodes, which we refer to as network coding,
bandwidth can in general be saved. This finding may have significant
impact on future design of switching systems.
Index Terms—Diversity coding, multicast, network coding,
switching, multiterminal source coding.