Online bandwidth-efficient scheduling for video-on-demand with recursive patching

The service bandwidth optimization problem for multicast video-on-demand systems with early service merging is investigated, and a series of on-line algorithms based on recursive patching is proposed. We adopt a simple fixed-threshold starting rule and introduce a control window to regulate the degree of service merging. Our results indicate that cost-aware recursive patching (CARP) with a carefully chosen control window can significantly reduce the service bandwidth consumption. We also study the promoting rule and the limited client buffer effect for practical recursive patching algorithms. Experimental results show that the proposed recursive patching schemes outperform graceful patching by a wide margin, even with a very small client buffer size.