摘要
This paper considers quality of service in terms of end-to-end delay in planning backup routes for multicast communications. The problem of preplanning backup routes considering both cost minimization and end-to-end delay guarantee for multicast communications in the case a single link failure is investigated. Two delay labels, the limited label and the tolerable label, are defined to evaluate the end-to-end delay requirement. Four heuristic algorithms, including two tree-based algorithms, one subtree-based algorithm, and one link-based algorithm, are proposed to determine the delay-constrained backup routes having the minimum costs. Two procedures to determine a node selection sequence, Random and Minimum-Cost, are used in the tree-based algorithm. Experimental results show that the tree-based algorithm by the Minimum-Cost sequence yields the best performance in cost minimization with guarantee of end-to-end delay. © World Scientific Publishing Co. &: Operational Research Society of Singapore.