An Iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting

Abstract

The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. 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. BSMA's expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1998
Accession Number
ADA461716

Entities

People

  • J.J. Garcia-Luna-Aceves
  • Mehrdad Parsa
  • Qing Zhu

Organizations

  • University of California, Santa Cruz

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Bandwidth
  • California
  • Classification
  • Computers
  • Construction
  • Contracts
  • Cost Reductions
  • Costs
  • Engineering
  • Heuristic Methods
  • Information Operations
  • Instructions
  • Mathematics
  • Simulations

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Operations Research