School of Computing

Heuristics for atm multicast routing

J.S. Crawford and A.G. Waters

In Demetres Kouvatsos, editor, ATM'98 Sixth IFIP Workshop on Performance Modelling and Evaluation of ATM Networks. Participants Proceedings: Tutorial Papers, pages 182-196, University of Bradford, July 1998. IFIP Workshop TC6 IFIP Working Groups WG6.3 and WG6.4, UK Performance Engineering Workshop.

Abstract

Several multicast routing heuristics have been proposed to support multimedia services, both interactive and distribution, in high speed networks such as B-ISDN/ATM. Since such services may have large numbers of members and have real-time constraints, the objective of the heuristics is to minimise the multicast tree cost while maintaining a bound on delay. Previous evaluation work has compared the relative average performance of some of these heuristics and concludes that they are generally efficient, although some perform better for small multicast groups and others perform better for larger groups.

We present an introduction to the problem and to some key heuristic solutions. Our detailed analysis and evaluation of some of these heuristics illustrates that in some situations their average performance is reversed; a heuristic that in general produces efficient solutions for small multicasts, may sometimes produce a more efficient solution for a particular large multicast/network combination. Also, in a limited number of cases using Dijkstra's algorithm produces the best result. We conclude that the specific efficiency of a heuristic solution depends on the topology of both the network and the multicast, and that it is difficult to predict.

Because of this unpredicatability we propose the integration of two heuristics with Dijkstra's shortest path tree algorithm to produce a hybrid that consistently generates efficient multicast solutions for all possible multicast groups in any network. The constituent heuristics are based on Dijkstra's algorithm, which maintains acceptable time complexity for the hybrid, and they rarely produce inefficient solutions for the same network/multicast. The resulting performance attained is generally good and in the rare worst cases is that of the shortest path tree. Our results show good performance over a wide range of networks, (both flat and hierarchical) and multicast groups, within differing delay bounds. We also study the distribution of path delays to the multicast group members. As might be expected, although the bound is always met, delays are generally longer than those achieved with Dijkstra's shortest path algorithm.

Download publication 342 kbytes (PostScript)

Bibtex Record

@inproceedings{708,
author = {J.S. Crawford and A.G. Waters},
title = {Heuristics for ATM Multicast Routing},
month = {July},
year = {1998},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1998/708},
    address = {University of Bradford},
    booktitle = {ATM'98 Sixth IFIP Workshop on Performance Modelling and Evaluation of ATM Networks. Participants Proceedings: Tutorial Papers},
    editor = {Demetres Kouvatsos},
    organization = {IFIP Workshop TC6 IFIP Working Groups WG6.3 and WG6.4},
    publisher = {UK Performance Engineering Workshop},
    refereed = {yes},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014