University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program


Multiple description coding and rainbow network problems


Prof. Dr. Xiaolin Wu, McMaster University
Hamilton, Ontario, Canada

date & place

Wednesday, 19.10.2005, 16:15 h
Room C252


Networked data communication becomes simpler, faster, and less expensive if the content delivery is on a best-effort basis. No acknowledge from the receiver is needed, nor is there guarantee that the data packets will arrive in order, or at all. This simple send-only machinery shifts the burden of reliability from network protocols to the communication codes. Facing the challenges of the above new paradigm, the past few years have been a proliferation of research literature on multiple description coding (MDC). MDC generates K>=2 descriptions of a content, which can be transmitted to a receiver via up to K different routes. Each individual description can be decoded independently, and multiple descriptions can be jointly decoded to improve the reconstruction quality. The quality achieved by a decoder increases in the number of distinct MDC descriptions rather than the total number of descriptions received. This property makes the problem of optimizing network flows and transmission strategies for MDC, called rainbow network problems, very different from those of conventional network flow. In this talk, we will first introduce the concept of MDC, and then show that the rainbow network flow problem of maximizing the number of distinct MDC packets received, constrained by edge capacities, is NP-hard in general multisource-multisink setting. But the problem can be reduced to one of conventional maximum network flow in the case of single sink, and hence becomes polynomially solvable. Also, for tree network topology we have a dynamic programming algorithm for the rainbow network flow problem.