The QoS Steiner Tree Problem asks for the most cost efficient way to multicast multimedia to a heterogeneous collection of users with different data consumption rates. We assume that the cost of using a link is not constant but rather depends on the maximum bandwidth routed through the link. Formally, given a graph with costs on the edges, a source node and a set of terminal nodes, each one with a bandwidth requirement, the goal is to find a Steiner tree containing the source, and the cheapest assignment of bandwidth to each of its edges so that each source-to-terminal path in the tree has bandwidth at least as large as the bandwidth required by the terminal. Our main contributions are: (1) New flow-based integer linear program formulation for the problem; (2) First implementation of 4.311 primal-dual constant factor approximation algorithm; (3) an extensive experimental study of the new heuristics and of several previously proposed algorithms.

Rateless codes, also known as fountain codes, are a class of erasure error-control codes that are particularly well suited for broadcast/multicast systems. Raptor codes, as a particularly successful implementation of digital fountain codes, have been used as the application layer forward error correction (FEC) codes in the third generation partnership program (3GPP) Multimedia Broadcast and Multicast Services (MBMS) standard. However, the application of rateless codes to wireless multimedia broadcast/multicast communications has yet to overcome two major challenges: first, wireless multimedia communications usually has stringent delay requirements. In addition, multimedia multicast has to overcome heterogeneity. To meet these challenges, we propose a rateless code design that takes the layered nature of source traffic as well as the varying quality of transmission channels into account. A convex optimization framework for the application of unequal error protection (UEP) rateless codes to synchronous and asynchronous multimedia multicast to heterogeneous users is proposed. A second thread of the thesis addresses the noisy, bursty and time- varying nature of wireless communication channels that challenge the assumption of erasure channels often used for the wired internet. In order to meet this challenge, the optimal combination of application-layer rateless code and physical layer FEC code rates in time-varying fading channels is investigated. The performance of rateless codes in hybrid error-erasure channels with memory is then studied, and a cross-layer decoding method is proposed to improve decoding performance and complexity. / Thesis (Ph.D, Electrical & Computer Engineering) -- Queen's University, 2011-06-12 16:26:36.136