LVMSR - an efficient algorithm to multicast layered video

Layered video is a video compression technique to encode video data in multiple layers. It typically consists of a base layer and additional layers that provide enhanced video quality. The multicasting operation of a layered video may need to satisfy: i) bounded end-to-end delay from a source to each receiver, ii) minimum total cost, and iii) minimum delay jitter between the various video streams received by the receivers. Because different nodes may request different video quality and because of limited bandwidth on the network's links, different layers of video data may reach their destinations over different distribution trees, and not all receivers may receive all of their requested layers. The problem of computing such data distribution paths is NP-complete, which means that no optimal solution method is available. This paper presents a new heuristic algorithm called LVMSR with O(Rn²) time complexity and O(R²) message complexity, where n is the number of nodes in the network and R is the receiver group size. Our simulation results show that the multicast data paths computed by our algorithm can always satisfy the delay constraint with reasonably small total cost.