Article ID: | iaor20071857 |
Country: | Singapore |
Volume: | 23 |
Issue: | 1 |
Start Page Number: | 25 |
End Page Number: | 39 |
Publication Date: | Mar 2006 |
Journal: | Asia-Pacific Journal of Operational Research |
Authors: | Wen Ue-Pyng, Shyur Ching-Chir, Yang Chyi-Bao |
Keywords: | heuristics, service |
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 of 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.