An iterative algorithm for delay-constrained minimum-cost multicasting

Author

Parsa, Mehrdad ; Zhu, Qing ; Garcia-Luna-Aceves, J.J.

Author_Institution

Dept. of Comput. Eng., California Univ., Santa Cruz, CA, USA

Volume

6

Issue

4

fYear

1998

fDate

8/1/1998 12:00:00 AM

Firstpage

461

Lastpage

474

Abstract

The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. The BSMA can handle asymmetric link characteristics and variable delay bounds on destinations, specified as real values, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The BSMA´s expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution

Keywords

computational complexity; computer networks; delays; iterative methods; network topology; optimisation; search problems; telecommunication network routing; trees (mathematics); asymmetric link characteristics; bounded shortest multicast algorithm; computer network; delay-bounded multicast tree; delay-constrained minimum-cost multicasting; fast execution; feasible-search optimization; iterative algorithm; minimum-cost multicast trees; minimum-delay multicast tree; multicast routing tree; near-optimal cost reduction; simulation results; time complexity; Computer networks; Cost function; Delay; Heuristic algorithms; Iterative algorithms; Iterative methods; Multicast algorithms; Quality of service; Routing; Tree graphs;

fLanguage

English

Journal_Title

Networking, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1063-6692

Type

jour

DOI

10.1109/90.720901

Filename

720901