Layered multicast scheduling for the L∞ objective
Qingbo Cai, Vincenzo Liberatore · Symposium on Discrete Algorithms · 2007
Layered multicast is a scalable solution to data dissemination over the Internet. The performance of layered multicast hinges upon the transmission schedule. In this paper, we study the scheduling problem in the layered multicast context. This work generalizes the extensively studied multicast scheduling problem (layered and non-layered) by introducing simultaneously the data popularity and the interaction among layers, and addresses the strictest L∞ objective, i.e., to find a schedule which is good for all individual layers. Compared to the previous work, this paper presents a polynomial-time approximation algorithm that uses a 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 multilayer cases.