School of Computing

A Hybrid Approach to Quality of Service Multicast Routing in High Speed Networks

John Crawford

PhD thesis, University of Kent at Canterbury, November 1998.


Multimedia services envisaged for high speed networks may have large numbers of users, require high volumes of network resources and have real-time delay constraints. For these reasons, several multicast routing heuristics that use two link metrics have been proposed with the objective of minimising 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.

This thesis presents a detailed analysis and evaluation of these heuristics which illustrate that in some situations their average performance is prone to wide variance for a particular multicast in a specific network. It concludes that the efficiency of an heuristic solution depends on the topology of both the network and the multicast, which is difficult to predict.

The integration of two heuristics with Dijkstra�s shortest path tree algorithm is proposed, to produce a hybrid that consistently generates efficient multicast solutions for all possible multicast groups in any network. The evaluation results show good performance over a wide range of networks (flat and hierarchical) and multicast groups, within differing delay bounds.

The more efficient the multicast tree is, the less stable it will be as multicast group membership changes. An efficient heuristic is extended to ensure multicast tree stability where multicast group membership is dynamic. This extension decreases the efficiency of the heuristic�s solutions, although they remain significantly cheaper than the worst case, a shortest delay path tree.

This thesis also discusses how the hybrid and the extended heuristic might be applied to multicast routing protocols for the Internet and ATM Networks.

Additionally, the behaviour of the heuristics is examined in networks that use a single link metric to calculate multicast trees and concludes one of the heuristics may be of benefit in such networks.

Download publication 822 kbytes (PostScript)

Bibtex Record

author = {John Crawford},
title = {{A Hybrid Approach to Quality of Service Multicast Routing in High Speed Networks}},
month = {November},
year = {1998},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    publication_type = {phdthesis},
    school = {University of Kent at Canterbury},
    submission_id = {27498_944731253},

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

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

Last Updated: 21/03/2014