Scalable Multimedia Communication using Network Coding

Abstract

This dissertation devotes itself to algorithmic approaches to the problem of scalable multicast with network coding. Several original contributions can be concluded as follows. We have proved that the scalable multicast problem is NP-hard, even with the ability to perform network coding at the network nodes. Several approximations are derived based on different heuristics, and systematic approaches have been devised to solve those problems. We showed that those traditional routing methods reduce to a special case in the new network coding context. Two important frameworks usually found in traditional scalable multicast solutions, i.e. layered multicast and rainbow multicast, are studied and extended to the network coding scenario. Solutions based on these two frameworks are also presented and compared. Suprisingly, these two distinctive approaches in the traditional sense become connected and share a similar essence of data mixing in the light of network coding. Cases are presented where these two approaches become equivalent and achieve the same Performance. We have made significant advances in constructing good solutions to the scalable multicast problem by solving various optimization problems formulated in our approaches. In the layered multicast framework, we started with a straight-forward extension of the traditional layered multicast to the network coding context. The proposed method features an intra-layer network coding technique which is applied on different optimized multicast graphs. Later on, we further improved this method by introducing the inter-layer network coding concept. By allowing network coding among data from different data layers, more leverage is gained when optimizing the network flow, thus higher performance is achieved. In the rainbow multicast framework, we choose uneven erasure protection (UEP) technique as the practical way of constructing balanced MDC, and optimize this MDC design using the max-flow information of receivers. After the MDC design is finalized, a single linear network broadcast code is employed to deliver MDC encoded data to receivers while satisfying the individual max-flow of all the receivers. Although this rainbow multicast based solution may sacrifice the performance in some cases, it greatly simplifies the rate allocation problem raised in the layered multicast framework. The use of one single network code also makes the network codes construction process a lot clearer. Extensive amount of simulation is performed and the results show that network coding based scalable multicast solutions can significantly outperform those traditional routing based solutions. In addition to the imaginary linear objective function used in the simulation, the practical convex objective function and real video data are also used to verify the effectiveness of the proposed solutions. The role of different parameters in the proposed approaches are analyzed, which gives us more guidelines on how to fine-tune the system.