Network information flow
Network information flow
复制标题
DOI：
10.1109/18.850663
复制
发表时间：
2000-07-01
影响因子：
2.5
通讯作者：
Yeung, RW
中科院分区：
文献类型：
--
作者：
Ahlswede, R;Cai, N;Yeung, RW
我们引入了一类新的问题，称为网络信息流，这是计算机网络应用的启发。考虑一个点对点通信网络，在该网络上，多个信息源被多播到某些目的地集合。我们假设信息来源是相互独立的。问题是表征可容许的编码速率区域。这个模型包含了所有以前研究过的模型沿着同一条线。在本文中，我们研究了一个信息源的问题，我们已经得到了一个简单的特征的容许编码率区域。我们的结果可以看作是网络信息流的最大流最小割定理。与人们的直觉相反，我们的工作表明，将多播信息视为可以简单地路由或复制的“流体”通常不是最佳的。相反，通过在节点处采用编码，我们称之为网络编码，通常可以节省带宽。这一发现可能会对未来的交换系统的设计产生重大影响。
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.