Multicast applications, such as content sharing and multimedia broadcasting, is the single most important class of applications over the internet. Multicast applications assume overlay network models, which consist of relevant nodes connected by abstracted virtual logical links. While scalable multicasting in such a network requires error-correction coding, classical coding approaches are highly inefficient due to the fact that virtual links do not enjoy known statistical channel models. To overcome this challenge, this project will develop a systematic coding theory based on a new fountain communication model for efficient multicasting in overlay networks. In fountain communication, the source node encodes a message into an infinite number of packets, a destination decodes the message after the number of received packets exceeds certain threshold.

The investigator will first develop a fountain coding framework for end-to-end multicast transmission over virtual network links. For delay nonsensitive traffic, fountain codes will be developed to achieve ideal rate-error performance with a linear coding complexity. For delay sensitive traffic, fountain coding will be integrated with flow control algorithms to ensure timely information delivery over channels with arbitrary distortions and erasures. The objectives are characterizing fundamental performance limitations and developing practical coding schemes. The project will then investigate multiuser cooperative communication for multicast applications in node-capacitated overlay networks, where the sum upload rate of each node is kept below a predetermined bound. For delay sensitive communication, the objective is to overcome the challenge that network nodes may randomly access or disconnect from the network. For delay nonsensitive communication, the objective is to overcome the "selfish-peer-node" challenge where a peer node disconnects from the network whenever its desired messages become fully decodable.

Project Report

Multicast applications such as content sharing and multimedia broadcasting have become the single most important class of applications in wireline and wireless networks. Multicast applications often assume overlay network models, which consist of relevant nodes connected by virtual logical links abstracted on top of the internet. Conventionally, reliable information delivery in overlay networks is achieved using packet retransmission-based protocols such as the TCP. However, when common information needs to be delivered to multiple destinations, different destinations may demand the retransmissions of different packets. Packet retransmission approaches therefore become inefficient since they use shared network resource to benefit a small subset of destinations. Classical error correction coding-based approaches, on the other hand, are not able to handle unknown arbitrary packet distortions and erasures, which is a fundamental phenomenon in overlay network transmissions. In this project, we developed a fountain channel coding theory for multimedia broadcasting over discrete memoryless channels with arbitrary unknown erasures. Our results demonstrated that communication error probability of the fountain broadcast system can be made to decrease exponentially in the number of received symbols for any fountain rate below the capacity. A near optimal error exponent can be achieved with a coding complexity growing only linearly in the number of received symbols. The proposed fountain coding approach also possesses several interesting properties, such as the rate combining and the rate compatible properties, which are important to broadcasting applications. Meanwhile, we also investigated the problem of channel coding in random access communication systems. As opposed to the traditional view that regards random access communication as a negligible component in the message transmission process, data transmission in modern networks relies increasingly on distributed and random access communication protocols. Fundamental coding limits of these communication models therefore has become a vital missing part in channel coding theory. Under the support of this project, we took an important step to extend Shannon-style channel coding theory from coordinated communication systems to random access communication systems. More specifically, in a random multiple access system, we assume that each transmitter is equipped with multiple codebooks each corresponding to a different set of communication parameter values. Each transmitter is allowed to choose an arbitrary codebook in each time slot to encode its message. Coding decisions are made individually without being shared with other transmitters or with the receiver. The receiver is required either to reliably decode the messages or to report a collision. Our results showed that the fundamental performance limitation of such a system can be characterized by an achievable region that on one hand coincides with the traditional Shannon region but on the other hand possesses a quite different meaning. The research works supported by this project is in line with our long term effort of bridging information theory with network theory. The gap between the two traditional theories is viewed by us as a key bottleneck for the further advance of wireless networks. The particular research progress in fountain communication will help the development of scalable multicast applications. The progress on channel coding for random access communication will help improving the understanding on the fundamental performance limitation of distributed communication systems. The research progresses have been fully integrated into the relevant graduate and undergraduate curriculum and this will help broadening the knowledge and the vision of our graduate and undergraduate students.

Project Start
Project End
Budget Start
2010-09-01
Budget End
2014-08-31
Support Year
Fiscal Year
2010
Total Cost
$240,704
Indirect Cost
Name
Colorado State University-Fort Collins
Department
Type
DUNS #
City
Fort Collins
State
CO
Country
United States
Zip Code
80523