Skip to main content

A new heuristic for ATM multicast routing

Waters, A. Gill (1994) A new heuristic for ATM multicast routing. In: UNSPECIFIED. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:21189)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.

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.

Item Type: Conference or workshop item (UNSPECIFIED)
Uncontrolled keywords: ATM multicast routing network
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: 13 Aug 2009 19:15 UTC
Last Modified: 16 Nov 2021 09:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21189 (The current URI for this page, for reference purposes)

University of Kent Author Information

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.