Abstract:
In this paper, we examine algorithmic issues related to the delayed multicast
technique [8] for Video-on-Demand delivery. We introduce the minimum
total memory (MTM), minimum total traffic (MIT), and the minimum maximum
memory per node (MMMN) delayed-multicast allocation problems.
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.
