A new heuristic for ATM multicast routing

Waters, A.G. (1994) A new heuristic for ATM multicast routing. In: UNSPECIFIED. (The full text of this publication is not available from this repository)

The full text of this publication is not available from this repository. (Contact us about this Publication)

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: Faculties > Science Technology and Medical Studies > School of Computing > Systems Architecture Group
Depositing User: Mark Wheadon
Date Deposited: 13 Aug 2009 19:15
Last Modified: 13 Aug 2009 19:15
Resource URI: http://kar.kent.ac.uk/id/eprint/21189 (The current URI for this page, for reference purposes)
  • Depositors only (login required):