AN OPTIMAL ITERATIVE ALGORITHM FOR MULTICASTING

Abstract

Multicast service is becoming a key requirement of computer networks supports multimedia applications. Quality of service parameters are used to express the applications requirements which must be quarenteed by the underlying network. Multicast tree construction is the main criteria for optimum utilization of network resources. The bounded shortest-multicast algorithm (BSMA) is discussed and implemented for constructing minimum-cost multicast tree with delay constraints. BSMA can handle nonuniform, positive, and real-valued delay bounds. The delay function on links can take arbitrary positive real values. Instead of using a single pass to construct the tree , BSMA employs a multiple-pass approach to iteratively minimize the cost function of the tree. BSMA can accept asymmetric link costs and delays. The ability to accept asymmetric link costs and delays makes BSMA more versatile and applicable in actual networks because actual networks must be considered as directed graphs when bandwidth and delay must be managed independently in each direction on a link. The BSMA path-switching heuristic and BSMA Greedy heuristic are compared with KMB spanning tree heuristic on the basis of multicast network cost. Simulation results shows that BSMA can achieve near optimal cost reduction with delay constraints.