AN ITERATIVE ALGORITHM FOR DELAY-CONSTRAINED MINIMUM-COST MULTICASTING

The bounded shortest multicast algorithm (BSMA) is presented for const ructing minimum-cost multicast trees with delay constraints. BSMA can handle asymmetric link characteristics and variable delay bounds on de stinations, 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 minim um-delay multicast tree and monotonically decreases the cost by iterat ive improvement of the delay-bounded multicast tree, BSMA's expected t ime complexity is analyzed, and simulation results are provided showin g that BSMA can achieve near-optimal cost reduction with fast executio n.