Low-cost ATM Multicast Routing with Constrained Delays

A. Gill Waters and John S. Crawford
Computing Laboratory
University of Kent at Canterbury
Canterbury, Kent, CT2 7NF
England

Abstract. An increasing number of networking applications involve multiple participants and are therefore best supported by multicasting. Where a multicast application consumes high bandwidth, it is important to min-imise the effect on the network by offering economical multicast routes. Many new applications made possible by networks based on ATM involve real-time components and are therefore also delay-sensitive. This paper discusses reasonably simple techniques for multicast routing which tackle both of these constraints, that is:first, the route mak es efficient use of network resources and, secondly , delays to all recipients are kept within a bound. The problem is NP-complete, so we present heuristics which build up a directed graph containing potential routing solutions and use a greedy approach to select a solution from that graph. The heuristics are discussed and evaluated and are shown to offer good results for a variety of situations including both large and small multicast groups. Our approach is also compared with a previous solution to this problem, which has a greater time complexity.