Minimising packet copies in multicast routing by exploiting geographic spread
- 1 July 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 24 (3) , 47-62
- https://doi.org/10.1145/193285.193296
Abstract
Routing connections in a point-to-point network is typically treated as a shortest path problem in a graph. Nodes represent switching systems, edges represent links and the edge lengths represent the costs associated with using a link. With multicast routing, one is interested in the shortest subtree of the network containing a given set of hosts. This is essentially a Steiner Tree problem in graphs and is known to be NP-complete [Karp]. Traditionally, the multicast routing algorithms proposed for packet switched networks like asynchronous transfer mode (ATM) networks have been aimed at minimising the total link cost of the Steiner tree [Waxman88], [Jaffe83] and do not take the geographical spreading of the connections into account. A dynamic point-to-multipoint routing algorithm is proposed, which takes into account the concept of geographic spread (also defined) of the connections and its performance is evaluated against the KMB near optimal heuristic algorithm for solving the Steiner tree problem [Kou].Keywords
This publication has 13 references indexed in Scilit:
- On multicast path finding algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1991
- Fast connection establishment in high speed networksACM SIGCOMM Computer Communication Review, 1990
- Near field monitoring system for the dsb d‐vorElectronics and Communications in Japan (Part I: Communications), 1990
- Nonblocking copy networks for multicast packet switchingIEEE Journal on Selected Areas in Communications, 1988
- Distributed Multi-Destination Routing: The Constraints of Local InformationSIAM Journal on Computing, 1985
- Routing to Multiple Destinations in Computer NetworksIEEE Transactions on Communications, 1983
- The computation of nearly minimal Steiner trees in graphsInternational Journal of Mathematical Education in Science and Technology, 1983
- The steiner problem in graphsNetworks, 1971
- Random GraphsThe Annals of Mathematical Statistics, 1959
- A note on two problems in connexion with graphsNumerische Mathematik, 1959