Matrix games in the multicast networks: maximum information flows with network switching

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-so- urce 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 H_n=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