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. / Thesis / Doctor of Philosophy (PhD)
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/21017 |
| Date | 01 1900 |
| Creators | Shao, Mingkai |
| Contributors | Wu, Xiaolin, Chen, Jun, Electrical and Computer Engineering |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
Page generated in 0.0024 seconds