University of Winnipeg
Delay constrained multicast routing is a typical problem in many emerging applications such as voice over IP, video on demand and teleconferencing, etc. Equivalently referred to as the Delay Constrained Minimum Steiner Tree (DCMST), this problem requires to find a tree spanning a source and a set of destination nodes such that the total cost is minimized while the delay from the source to each destination node is no more than a preset upper bound. Due to its NP-complete nature, all previous work focused on developing efficient heuristics. In this paper, the authors study this problem from a completely different perspective by using an exact approach, which has never been done before.