Optimum multicast of multimedia streams

Abstract

In a VOD system, multicast is a preferred method for saving network bandwidth. That is, customers requesting the same video program over a small time interval can be arranged in a multicast tree (group), and then the video server sends a video stream via this tree to customers. In this research, we considered how to arrange a set of multicast trees such that the number of customers served is maximized and the link capacity constraint is maintained. For a directed acyclic graph (DAG), we proposed a branch-and-bound algorithm to solve this problem and the solution method is illustrated by example. Next, we extended the algorithm to find an approximate solution for a general graph case. It is shown, through simulations on randomly generated graphs that the solution for our approximation method is very close to the optimal solution. (C) 1999 Elsevier Science Ltd. All rights reserved.