Skip to main content
Kent Academic Repository

Low-cost ATM Multicast Routing with Constrained Delays

Waters, A. Gill and Crawford, John (1996) Low-cost ATM Multicast Routing with Constrained Delays. In: Pascual, J. and Danthine, A., eds. Multimedia Telecommunications and Applications Third International COST 237 Workshop. Lecture Notes in Computer Science . Springer, Berlin, Germany, pp. 23-40. ISBN 978-3-540-62096-9. E-ISBN 978-3-540-49680-9. (doi:10.1007/BFb0020848) (KAR id:21319)


An increasing number of networking applications involve multiple participants and are therefore best supported by multicasting. Where multicast applications consume high bandwidth, it is important to minimise the effect on the network by offering economical multicast routes. Many new applications involve real-time components and are therefore also delay-sensitive. This paper discusses reasonably simple techniques for multicast routing which tackle both of these constraints, that is: first, the route makes efficient use of network resources and, secondly, delays to all recipients are kept within a bound. The problem is NP-complete, so we present heuristics which build up a directed graph containing potential routing solutions and use a greedy approach to select a solution from that graph. The heuristics are discussed and evaluated and are shown to offer good results for a variety of situations including both small and large multicast groups. Our approach is also compared with a previous solution to this problem, which has a greater time complexity.

Item Type: Book section
DOI/Identification number: 10.1007/BFb0020848
Uncontrolled keywords: multicast, routing, low cost, delay constrained, 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: 25 Aug 2009 20:00 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

Waters, A. Gill.

Creator's ORCID:
CReDIT Contributor Roles:

Crawford, John.

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.