Abstract
This paper addresses the problem of routing many-to-many multicast connections with bandwidth reservation. We devise a routing algorithm which provides not only connectivity but also bandwidth among multicast members at a low cost. After briefly addressing the problem complexity (NP-Complete), we move on to design polynomial time algorithms, for scalability purposes, some of which with worst case bounds on performance. A simulation study is used to illustrate the algorithms' performance and trade offs.
This work was partially supported by CNPq under Grant 201597/93-4(NV), and by GTE, NSF, and MICRO-SUN
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
D. Cavendish, A. Fei, M. Gerla, R. Rom “On the Construction of Low Cost Multicast Trees with Bandwidth Reservation,” UCLA Technical Report Number 970043, December 1997.
S. Deering et al., “The PIM Architecture for Wide-area Multicast Routing”, IEEE/ACM Transactions on Networking, vol. 4, pp.153–162, April 1996.
A. Frank, L. Wittie, and A. Bernstein, “Multicast Communication in Network Computers”, IEEE Software, Vol. 2, No. 3, pp 49–61, 1985.
H. N. Gabow, M. X. Goemans and D. P. Williamson, “An Efficient Approximation Algorithm for the Survivable Network Design Problem”, In Proceedings of the Third MPS Conference on Integer Programming and Combinatorial Optimization, pp. 57–74, 1993.
X. Jiang, “Path Finding Algorithms for Broadband Multicast”, Third Intl. Conf. on High Speed Networking, pp. 153–164, North-Holland, 1991.
M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz, H. B. Hunt, “Bicriteria Network Design Problems”, Proceedings of 22nd International Colloquium on Automata Languages and Programming, LNCS 944, pp. 487–498, 1995.
R. Ravi, M. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt III, “Many Birds with One Stone: Multi-objective Approximation Algorithms”, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pp. 438–447, 1993.
V. J. Rayward-Smith, “The Computation of Nearly Minimal Steiner Trees in Graphs”, Intl. J. Math. Educ. Sci. Tech., Vol. 14(1), pp. 15–23, 1983.
Z. Wang and J. Crowcroft, “Bandwidth-Delay Based Routing Algorithms”, GLOBECOM'95, pp. 2129–2133.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cavendish, D., Fei, A., Gerla, M., Rom, R. (1998). On the construction of low cost multicast trees with bandwith reservation. In: Sloot, P., Bubak, M., Hertzberger, B. (eds) High-Performance Computing and Networking. HPCN-Europe 1998. Lecture Notes in Computer Science, vol 1401. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0037193
Download citation
DOI: https://doi.org/10.1007/BFb0037193
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64443-9
Online ISBN: 978-3-540-69783-1
eBook Packages: Springer Book Archive