|
Research |
||||||||||||
|
My research focuses on characterizing the fundamental limits in multi-source multi-sink networks with arbitrary transmission requirements. Distributed schemes were also developed to achieve these fundamental limits for networks with various assumptions. The following is a snapshot of our research results. A complete list of publications can be found in my resume [pdf].
A three-layer network is a special network of which all the nodes are lined up in a three-layer architecture. Any cut in an arbitrary multi-source multi-sink network can be represented by a three-layer network. It is an important tool to study the capacity for general networks by using cut-set bounds. In this work, we determined a tight outer bound for the three-layer networks by analyzing the roles played by different coded information, which significantly improves the classical max-flow min-cut bound. When a given three-layer network is degree-2, i.e., only information from up to two independent sources can be coded together, and the sources and sinks form unicast pairs for transmissions, we determined the exact capacity region.
Publications:
Since each cut in a general multi-source multi-sink network can be represented by a three-layer network, determining the amount of flow through a cut is equivalent to finding the capacity region for the corresponding three-layer network. Taking the intersection of the capacity regions that correspond to all possible cuts in a general network gives an outer bound for the capacity region for original network. When the given network is a regular K-pairs three-layer network, we can arrive at an inner bound through a linear programming approach. This comes from the following observation: If all channels are classified as either main channels (channels that connect to the same source-sink pairs) or side-info channels (channels that connect to disjoint source-sink pairs), then enumerating all possible ways of assigning side information to the main channels, we obtain all possible source entropy rates of linear coding. Thus, this rate assigning problem is equivalent to the maximum weight matrix tiling problem and can be readily solved through a linear programming approach.
Publications:
Except for a few explicit outer bounds that have been discovered recently, Song and Yeung developed the tightest implicit inner and outer bounds that make use of the theory of information inequalities. In this work, we extended their work and closed the gap between the existing inner and outer bounds by refining the constrained regions in the entropy space. This leads to an exact characterization of the capacity region for general acyclic multi-source multi-sink networks with arbitrary transmission requirements. However, since entropy function is itself undetermined, how to explicitly evaluate the so derived capacity region remains an open problem in general.
Publications:
Lyapunov drift technique was originally introduced to design dynamic control algorithms for system queue stability. Subsequently, Neely further extended this technique to achieve joint network stability and performance optimality. However, all these techniques were restricted to the routing networks. To extend to the network coding setting, Ho et al first defined the stability region for networks that perform intra-session network coding and designed dynamic algorithms which achieves the network stability. In this work, we extended Ho's work to design dynamic algorithm that achieves joint network stability and performance optimality in an intra-multicast network coding setting. We also determined the information theoretic capacity region for this class of networks in a time-varying setting by using cut-set bounds and established the equivalence between the physical layer capacity region and Ho's network layer stability region. In analyzing the performance of the proposed algorithm, we derived lower bounds on the end-to-end throughput at which a sink can successfully decode its received data and performance bounds built on the end-to-end throughput. Our analysis shows, when using Lyapunov drift technique for optimal flow control, "one shot" type of linear network codes are sufficient to achieve performance optimality.
Publications:
In this work, we study the error correction capability and the decoding failure probability of random linear network codes in single source multicast networks. As was shown by Zhang, network maximum distance separable (MDS) codes do not exist if the code alphabet size is insufficient. Thus we analyzed the coding loss caused by the insufficient code alphabet size and the random coding operations. This determines the error correction capability of random linear network codes for fixed network redundancy rate, code block length and alphabet size. Also, we determined an upper bound of the failure probability that at one or more destinations, the source messages are not decodable in the existence of errors up to the Singleton bound when the encoding at all nodes are independently and randomly selected according to the uniform distribution in the code base field. Our results suggest with a slight degradation of source message rate as opposed to the maximum allowable capacity, random linear network codes perform fairly well for network error correction. This justifies the power of this completely localized coding method in future applications. As a side result, we compared our obtained bound with Ho et al’s upper bound in error-free networks. The improvements of our bound are three-fold: 1) our bound can be applied to block codes, 2) our bound tightened the order of the decoding failure probability from the number of edges to the number of internal nodes in the network, 3) our upper bound implies that for random linear block codes, the failure probability decays to zero exponentially with increasing block length for a fixed redundancy rate and a fixed code alphabet size.
Publications:
We have recently studied the error correction capability of random network error correction codes. It is proved that when the code alphabet size is limited, random error correction codes suffer from a so-called code degradation, i.e., they can not fully achieve the Singleton bound of network error correction. However, the structures of packet codes and error locations in packet networks enable a more powerful decoding capability than the classical point-to-point decoding, which can be used to compensate the coding degradation for a even more powerful decoding performance. In this paper, we study the decoding problem of network error correction codes. We design decoding algorithms that decode beyond the error correction capability of random network error correction codes up to the minimum distance of a Maximum Distance Separable (MDS) code minus two. We determine upper bounds on the decoding failure probabilities of the proposed decoding algorithms with different decoding complexities. Our results suggest when combined with classical error correcting codes for local protection, random network error correction codes are strong candidates for practical network error correction.
Publications:
|
