Video-on-demand based on delayed-multicast: Algorithmic support

Publication Type:
Journal Article
Citation:
Computer Journal, 2004, 47 (5), pp. 545 - 559
Issue Date:
2004-09-21
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2004000167.pdf1.34 MB
Adobe PDF
In this paper, we examine algorithmic issues related to the delayed multicast technique for video-on-demand delivery. We introduce the minimum total memory (MTM), minimum total traffic (MTT) and the minimum maximum memory per node (MMMN) delayed-multicast allocation problems. We examine these problems on two networks of practical interest, namely, the chandelier and the broom networks. We provide polynomial time algorithms for solving the MTM and the MTT problems on the chandelier network and the MTM problem on the broom network. We also show that a version of the decision-MMMN problem on a general graph is NP-complete. Finally, we present a heuristic method for obtaining a solution for the MTM problem on tree networks. © The British Computer Society; all rights reserved.
Please use this identifier to cite or link to this item: