Layered Multicast Scheduling

by Cai, Qingbo

Layered multicast addresses the problem of heterogeneous end-to-end network bandwidth and consequently is a scalable solution to data dissemination in heterogeneous networks such as the Internet. The performance of layered multicast hinges upon the transmission schedule. In this dissertation, we study the scheduling problem in the layered multicast context. Our objective is to generate a multicast schedule with or without the knowledge of the user subscription profiles such that the long run average latency for a client to retrieve a data item is minimized. This work generalizes the extensively studied multicast scheduling problem (layered and non-layered) by introducing simultaneously data popularity and the interaction among layers, and addresses both the L1 and the strictest L? objective to find a schedule which is good for all individual layers.

We present a simple 2-approximation randomized algorithm for the layered multicast scheduling problem. In the presence of user subscription profiles (the L1 objective), we provide a deterministic 2-approximation algorithm for the general multilayer cases. If the user subscription profiles are absent (the L? objective), we present a combinatorial construction for the two-layer case which is 1.6875-approximation ignoring an additive constant. Further, we provide a polynomial-time approximation algorithm that uses a fundamentally different approach and can address the general layered multicast scheduling problem with an arbitrary number of layers. This algorithm is 1.334-approximation for the two-layer case and 1.862-approximation for the general multi-layer cases.