Matrix games in the multicast networks: maximum information flows with network switching
Matrix games in the multicast networks: maximum information flows with network switching
复制标题
DOI：
10.1109/tit.2006.874517
复制
发表时间：
2006-06
影响因子：
2.5
通讯作者：
Xue-Bin Liang
中科院分区：
文献类型：
--
作者：
Xue-Bin Liang
Ahlswede、Cai、Li和Yeung提出了在多播网络中实现最大信息流的网络编码。他们已经证明，传统的网络交换，而不诉诸网络编码，是在一般情况下不能实现最佳的信息流，已承诺由网络编码。这里出现的一个基本问题是，对于一个给定的多播网络，什么是网络的切换间隙定义为在多播网络中的最大信息流与网络编码的比率，只有网络切换。本文将网络交换看作是网络编码的一种特殊形式，从理论和计算上对多播网络交换的可达信息速率域进行了全面的确定。允许多播网络是循环的或非循环的，其链路具有任意正整数或实值容量。网络交换实质上是组播网络中的组播路由打包问题。在此基础上，我们利用博弈论的理论，制定网络切换之间的第一个“球员”的链路和第二个“球员”的组播路由组播网络的矩阵博弈。我们证明了在信息率区域中的每个概率方向上的最大可实现信息率是相应博弈的值的倒数。因此，最大可实现的信息速率可以在一个简单的方式计算，通过应用现有的理论和算法的矩阵游戏的值的计算，特别是对于这样的多播网络的链路都具有单位容量的Ahlswede-Cai-Li-Yeung多播网络。对于链路容量为任意正实值的多播网络，利用凸优化方法，提出了一种简单有效的迭代算法来求解多播网络切换的最大可达信息速率.对于链路容量为任意正实值的单源多播网络，我们给出了两个最大流最小割定理。单源网络切换的最大信息流是组播网络所有软链路切换中的最小容量，而单源网络编码的最大信息流是组播网络所有硬链路切换中的最小容量。因此，通过应用集合覆盖问题的近似算法理论，我们证明了单源多播网络的切换间隙的上界为n次谐波数Hn=1+1/2+.+ 1/n，其中n是网络中包含给定链路的多播路由的最大数量。对于组合组播网络，该调和数界渐近紧为Oscr（ln n）。对于具有相同汇聚节点集的特殊多播网络，我们比较了网络切换和网络编码的可达信息速率区域
Network coding for achieving the maximum information flow in the multicast networks has been proposed by Ahlswede, Cai, Li, and Yeung. They have demonstrated that the conventional network switching, without resort to network coding, is in general not able to achieve the optimum information flow that has been promised by network coding. A basic problem arising here is that, for a given multicast network, what is the switching gap of the network defined as the ratio of the maximum information flow in the multicast network with network coding to that only with network switching. In the paper, by considering network switching as a special form of network coding, we make a complete theoretical and computational determination of the achievable information rate region for multisource multicast network switching. The multicast networks are allowed to be cyclic or acyclic with links having arbitrary positive integer or real-valued capacity. Network switching is essentially a problem of multicast-route packing in the multicast networks. Based on this, we use the theory of games to formulate the network switching as a matrix game between the first "player" of links and the second "player" of multicast routes in the multicast networks. We prove that the maximum achievable information rate at each probabilistic direction in the information rate region is the reciprocal of the value of the corresponding game. Consequently, the maximum achievable information rate can be computed in a simple way by applying the existing theory and algorithms for the computation of the value of a matrix game, especially for such multicast networks with links all having unit capacity as the Ahlswede-Cai-Li-Yeung multicast networks. For multicast networks with links having arbitrary positive real-valued capacity, by using convex optimization, we develop a simple and efficient iterative algorithm to find the maximum achievable information rates for multisource multicast network switching. For single-source multicast networks whose links have arbitrary positive real-valued capacity, we present two max-flow min-cut theorems. The maximum information flow for single-source network switching is the minimum capacity among all soft link-cuts of the multicast network, while the maximum information flow for single-source network coding is the minimum capacity among all hard link-cuts. Consequently, by applying the theory of approximation algorithms for the set-covering problem, we demonstrate that the switching gap of a single-source multicast network is upper-bounded by the nth harmonic number Hn=1+1/2+...+1/n where n is the largest number of multicast routes containing a given link in the network. This harmonic-number bound is asymptotically tight as Oscr(ln n) for the combination multicast network. For the special class of multisource multicast networks with the same set of sink nodes, we make a comparison between the achievable information rate regions for network switching and network coding