Skip to main content
Kent Academic Repository

A Hybrid Approach to Quality of Service Multicast Routing

Crawford, John, Waters, A. Gill (1997) A Hybrid Approach to Quality of Service Multicast Routing. In: ATM'97 Fifth IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, 21-23 Jul 1997, Ilkley, West Yorkshire, UK. (Unpublished) (KAR id:21478)


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 a detailed analysis and evaluation of some of these heuristics which illustrate 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 heuristics solution depends on the topology of both the network and the multicast, and that it is difficult to predict. Because of this unpredictability 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. These 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. The performance of our proposal is supported by our evaluation results. We conclude by discussing the types of networks for which this method is most appropriate and identifying further work.

Item Type: Conference or workshop item (Paper)
Uncontrolled keywords: Multicast, Routing, Delay Constrained, Low Cost, Hybrid Algorithims, Steiner Tree, NP complete
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 29 Jul 2009 17:33 UTC
Last Modified: 12 Jul 2022 10:39 UTC
Resource URI: (The current URI for this page, for reference purposes)

University of Kent Author Information

Crawford, John.

Creator's ORCID:
CReDIT Contributor Roles:

Waters, A. Gill.

Creator's ORCID:
CReDIT Contributor Roles:
  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.