The type of service and virtual destination node based multicast routing algorithm in ATM network

摘要

This paper presents a heuristic algorithm, referred to as the CMTVD (constrained multicast tree with virtual destination), that can be used for routing multipoint information flows optimally in ATM VP/VC networks. It generates multicast tree T(s, {M}) based on the delay requirements of services, link costs and path overlapping effects for resource saving and QoS satisfaction. For the delay sensitive service type, the cost optimized route is the minimum cost Steiner tree (MCST) connecting all the destination nodes, virtual destination nodes and the source node with least costs, subject to the delay along the path being less than the maximum allowable end to end delay. For the delay insensitive service, the cost optimized multicast route is the MCST connecting all the multicast group with least costs, subject to the traffic load being balanced in the network. The CMTVD algorithm uses the virtual destination node concept in order to find the multicast route that maximizes the overlapping effects of the path between multiple destinations, thus minimizing the number of links used in the multicast communications. Several examples are provided to illustrate how to apply this algorithm in a real ATM network and the cost performance of the algorithm is evaluated by simulation on random graphs.