The achievable information rate region problem of multisource multisink network coding for general acyclic networks with arbitrary transmission requirements has previously been studied, where inner and outer bounds on the region were derived in terms of Γ*, the fundamental region of entropy functions. In this paper, we derive the exact characterization of the achievable rate region in terms of entropic functions, thus closing the gap between the existing inner and outer bounds.

Randomized linear network code for single source multicast was introduced and analyzed in Ho et al. (IEEE Transactions on Information Theory, October 2006) where the main results are upper bounds for the failure probability of the code. In this paper, these bounds are improved and tightness of the new bounds is studied by analyzing the limiting behavior of the failure probability as the field size goes to infinity. In the linear random coding setting for single source multicast, the minimum distance of the code defined in Zhang, (IEEE Transactions on Information Theory, January 2008) is a random variable taking nonnegative integer values that satisfy the inequality in the Singleton bound recently established in Yeung and Cai (Communications in Information and Systems, 2006) for network error correction codes. We derive a bound on the probability mass function of the minimum distance of the random linear network code based on our improved upper bounds for the failure probability. Codes having the highest possible minimum distance in the Singleton bound are called maximum distance separable (MDS). The bound on the field size required for the existence of MDS codes reported in Zhang, (IEEE Transactions on Information Theory, January 2008) and Matsumoto (arXiv:cs.IT/0610121, Oct. 2006) suggests that such codes exist only when field size is large. Define the degradation of a code as the difference between the highest possible minimum distance in the Singleton bound and the actual minimum distance of the code. The bound for the probability mass function of the minimum distance leads to a bound on the field size required for the existence of network error correction codes with a given maximum degradation. The result shows that allowing minor degradation reduces the field size required dramatically.

In this paper, we study the error correction capability of random linear network error correction codes (Z. Zhang, 2006). We derive bounds on the probability mass function of the minimum distance of a random network error correction code and the field size required for the existence of a network error correction code with a given degradation, which is the difference between the highest possible minimum distance in the Singleton bound and the minimum distance of the code. The main tool that we use to study these problems is an improved bound on the failure probability of random linear network codes that at one or more sinks, the source messages are not decodable. This problem was originally studied in T. Ho et al. (2006).

In this paper, we study the dynamic resource allocation problem for a class of time-varying wireless multicast networks with intra-multicast network coding. We provide distributed and dynamic cross-layer strategy to simultaneously achieve utility optimization and network stability under given power constraints. Our result shows when combined with Lyapunov drift technique for optimal flow control, "one shot" type of network codes, i.e., codes that restrict network coding within packets in a multicast that enter the network in the same timeslot, are sufficient to achieve performance optimality in this class of networks.

The capacity problem for general acyclic multi- source multi-sink networks with arbitrary transmission requirements has been studied by L. Song, et al (2003). Specifically, inner and outer bounds of the capacity region were derived respectively in terms of Gamman* and Gamma macrn*, the fundamental regions of the entropy function. In this paper, we show that by carefully bounding the constrained regions in the entropy space, we obtain the exact characterization of the capacity region, thus closing the existing gap between the above inner and outer bounds.

This paper summarizes our recent works on network error correction codes. We study basic properties of linear network error correction codes in the single source multicast case. We define the minimum distance of a network error correction code which plays the same role as it does in classical coding theory. We construct MDS codes and give sufficient conditions for its existence. We propose basic decoding algorithms and analyze their performance. We propose an improved upper bound for the failure probability of random network code and use it to analyze the performance of randomized network error correction codes [9], [10]. We study the possibility of decoding beyond error correction capability. We propose a hybrid network error correction coding systems. An extensive performance analysis of this coding system is reported in a separate paper.

Ignited by the pioneering work of Ahlswede et al on the characterization of the capacity region for single-source multicast networks, a number of works have been devoted to determining the capacity regions for more general networks. However, except a few interesting outer bounds that have been derived so far, the exact characterization is still restricted to rather simple networks. In this paper, we determine the capacity region for a more general class of networks called degree-2 K-pairs three-layer networks. The result suggests a characterization technique for more general multi-source multi-sink networks

In multi-source multi-sink network coding, messages across different sources are coded to increase the overall throughput. The various types of coded information in the network significantly complicate the determination of its capacity region. In this work, we derive explicit inner and outer bounds for acyclic multi-source multi-sink networks based on a cut-based network decomposition technique and a role-based information characterization technique. In particular, we derive a linear programming inner bound for regular K-pairs acyclic three-layer networks and a network sharing outer bound for arbitrary acyclic multi-source multi-sink networks. The techniques used in this paper reveal some of the basic mechanisms of multi-source multi-sink network coding

The max-flow min-cut bound is a fundamental result in the theory of communication networks, which characterizes the optimal throughput for a point-to-point communication network. The recent work of Ahlswede et al. extended it to single-source multisink multicast networks and Li et al. proved that this bound can be achieved by linear codes. Following this line, Erez and Feder as well as Ngai and Yeung proved that the max-flow min-cut bound remains tight in single-source two-sink nonmulticast networks. But the max-flow min-cut bound is in general quite loose (see Yeung, 2002). On the other hand, the admissible rate region of communication networks has been studied by Yeung and Zhang as well as Song and Yeung, but the bounds obtained by these authors are not explicit. In this work, we prove a new explicit outer bound for arbitrary multisource multisink networks and demonstrate its relation with the minimum cost network coding problem. We also determine the capacity region for a special class of three-layer networks.