Efficient tree construction for the multicast problem
Di Fatta, G. and Lo Re, G. (1998) Efficient tree construction for the multicast problem. In: ITS'98 proceedings : SBT/IEEE International Telecommunications Symposium : Maksoud Plaza Hotel, São Paulo, Brazil, August 9-13, 1998. IEEE, Piscataway, N.J., pp. 632-637. ISBN 9780780350304
Full text not archived in this repository.
To link to this item DOI: 10.1109/ITS.1998.718470
A new heuristic for the Steiner Minimal Tree problem is presented here. The method described is based on the detection of particular sets of nodes in networks, the “Hot Spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used CIS comparison terms in the experimental analysis which demonstrates the goodness of the heuristic discussed in this paper.
1. K. Bharath-Kumar and Jaffe, “Routing to Multiple Destinations in Computer Networks”, IEEE Trans on Commun. vol. COM-31, n.3, pp.343 - 351, Mar. 1983 2. P. Winter, “Steiner Problem in Networks: A Survey”, Networks vol. 17 (1987) pp. 129-167 3. F. Bauer, A. Varma, “Distributed Algorithms for Multicast Path Setup in Data Networks”, IEEE/ACM Transactions on Networking, Vol. 4 4. J. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proc. Amer. Math. Soc., vol. 7, pp. 48 - 50, 1956. 5. H. Takahashi, A. Matsuyama, “An Approximate Solution for the Steiner Problem in Graph”, Math. Japonica, vol. 24, n. 6, pp. 573-577, 1980. 6. E.W. Dijkstra, “A Note on Two Problems in Connection with Graphs”, Numer. Math., vol. 1 7. M. B. Doar, I. Leslie, “How Bad is naive multicast routing?’, Roc. of IEEE Infocom, pp. 82 - 89, San Francisco CA, Apri1 1993, 8. M. B. Doar, “TIERS User Manual”, v. 1.1 9. S. Ramanathan, “Multicast Tree Generation in Networks with Asymmetric Links”, IEEE/ACM Transactions on Networking, Vol. 4, N. 4, pp.558-568, August 1996 10. S. Deering, D. Estrin, D. Farinacci, V. Jacobson, C. G. Liu, L. Wei, “The PIM Architecture fox Wide-Area Multicast Routing”, IEEE/ACM Transactions on Networking, Vol. 4, N. 2, pp.153-162, April 1996 ll. V. P. Kompella, J. C. Pasquale, G. C. Polyzos, “Multicast Routing for Multimedia Communication”, IEEE/ACM Transactions on Networking, Vol. 1, N. 3, pp. 286-292, June 1993 12. F. Bauer, A. Vma, “ARIES: A Rearrangeablc Inexpensive Edge-Based On-Line Steiner Algorithm”, IEEE Journal on Selected Areas in Communications, vol. 15, N.3, pp. 382 - 397, April 1997 13. Q. Zhu, M. Parsa, J. J. Garcia-LunaAceves, “A source-based algorithm for delay constrained minimum-cost multicasting”, Proc. of IEEE Infocom, 1995, pp. 377-385 14. B. Waxman, “Routing of Multipoint Connections”, Journal on Selected Areas in Communications, vol. 6, N.9, pp. 1617 - 1622, Dec. 1988.