© University of Kent - Contact | Feedback | Legal | FOI | Cookies
A new heuristic for ATM multicast routing
A.G. Waters
In 2nd IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, pages 182-196. University of Bradford, July 1994.Abstract
Many services envisaged for B-ISDN and ATM networks involve point-to-multipoint working. Multipoint services with many recipients can impose a much heavier burden on the network than simple point-to-point services, so multicast routing should aim to minimise their demand on the network. Many B-ISDN services are also delay-sensitive. Appropriate multicast routing algorithms for ATM networks are therefore subject to two constraints: they must be economic in their use of network resources and they should offer a delay bound for all recipients. To date, most work on multicast routing algorithms has concerned minimising the total cost of a multicast tree; this problem is known to be NP-complete, being the Steiner tree problem. Combining minimal cost with bounded delay is therefore also an NP-complete problem.
Our approach to a heuristic for both constraints works as follows. First, a delay bound is found using Dijkstra's algorithm, which also gives the edges of the original network graph available to a bounded delay solution. An iterative techniques is then used to reduce this graph to a low-cost tree. The paper presents preliminary results comparing our heuristic with solutions obtained using Dijkstra's algorithm alone for delays (which generally gives a high-cost solution) and a heuristic for a low-cost solution based in the Minimum Spanning Tree approach (which in general can give high delays). In both cases, our heuristic performs well. We also compare it with some of our earlier work in which the cost metric was proportional to delay. A reasonably simple solution can be found under this assumption using a minor change to the normal coding of Dijkstra's algorithm.
Bibtex Record
@conference{434,
author = {Waters, A.G.},
title = {{A} new heuristic for {ATM} multicast routing},
month = {July},
year = {1994},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1994/434},
booktitle = {2nd IFIP Workshop on Performance Modelling and Evaluation of ATM Networks},
organization = {University of Bradford},
refereed = {Yes},
}