Skip to main content
Springer Nature Link
Log in

Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing

  • Published:
Telecommunication Systems Aims and scope Submit manuscript

Abstract

The advent of various real-time multimedia applications in high-speed networks creates a need for quality of service (QoS) based multicast routing. The Steiner tree problem, is a well-known NP-complete problem, provides the mathematical structure behind multicast communications. Two important QoS constraints are the bandwidth constraint and the end-to-end delay constraint. In this paper, we propose various algorithms to solve the bandwidth-delay-constrained least-cost multicast routing problem based on Tabu Search (TS), addressing issues of the selected initial solution and move type as two major building blocks in short-term memory version of Tabu Search and longer-term memory with associated intensification and diversification strategies as advanced Tabu Search techniques. We evaluate the performance and efficiency of the proposed TS-based algorithms in comparison with other existing TS-based algorithms and heuristics on a variety of random generated networks with regard to total tree cost. Finally we identify the most efficient algorithm uncovered by our testing.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Hakimi, S. L. (1971). Steiner problem in graphs and its implications. Networks, 1, 113–133.

    Article  Google Scholar 

  2. Hwang, F. K., Richards, D. S., & Winter, P. (1992). The Steiner tree problem. Amsterdam: Elsevier Science/North-Holland.

    Google Scholar 

  3. Sun, Q., & Langendörfer, H. (1998). An efficient delay-constrained multicast routing algorithm. Journal of High-Speed Networks, 7(1), 43–55.

    Google Scholar 

  4. Guo, L., & Matta, I. (1999). QDMR: an efficient QoS dependent multicast routing algorithm. In RTAS’99: proceedings of the fifth IEEE real-time technology and applications symposium (pp. 213–222). Vancouver, BC, Canada. Washington: IEEE Comput. Soc.

    Google Scholar 

  5. Rouskas, G. N., & Baldine, I. (1997). Multicast routing with end-to-end delay and delay variation constraints. IEEE Journal on Selected Areas in Communications, 15(3), 346–356.

    Article  Google Scholar 

  6. Garey, M. R., & Johnson, D. S. (1971). Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman.

    Google Scholar 

  7. Kou, L., Markowsky, G., & Berman, L. (1981). A fast algorithm for Steiner trees. Acta Informatica, 15, 141–145.

    Article  Google Scholar 

  8. Rayward-Smith, V. (1983). The computation of nearly minimal Steiner trees in graphs. International Journal of Mathematical Education in Science and Technology, 14(1), 15–23.

    Google Scholar 

  9. Takahashi, H., & Matsuyama, A. (1980). An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 22(6), 573–577.

    Google Scholar 

  10. Kompella, V. P., Pasquale, J. C., & Polyzos, G. C. (1993). Multicast routing for multimedia communication. IEEE/ACM Transactions on Networking, 1(3), 286–292.

    Article  Google Scholar 

  11. Zhu, Q., Parsa, M., & Garcia-Luna-Aceves, J. J. (1995). A source-based algorithm for delay-constrained minimum-cost multicasting. In INFOCOM ’95: proceedings of the fourteenth annual joint conference of the IEEE computer and communication societies (Vol. 1, pp. 377–385). Washington: IEEE Comput. Soc.

  12. Widyono, R. (1994). The design and evaluation of routing algorithms for realtime channels. Technical report TR-94-024, Tenet Group, Department of EECS, University of California at Berkeley.

  13. Raghavan, S., Manimaran, G., & Siva Ram Murthy, C. (1999). A rearrangeable algorithm for the construction delay-constrained dynamic multicast trees. IEEE/ACM Transactions on Networking, 7(4), 514–529.

    Article  Google Scholar 

  14. Salama, H. F., Reeves, D. S., & Viniotis, Y. (1997). Evaluation of multicast routing algorithms for real-time communication on high-speed networks. IEEE Journal on Selected Areas in Communications, 15(3), 332–345.

    Article  Google Scholar 

  15. Grabowski, J., & Wodecki, M. (2004). A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Computers & Operations Research, 31(11), 1891–1909.

    Article  Google Scholar 

  16. Fiechter, C. N. (1994). A parallel tabu search algorithm for large traveling salesman problems. Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science, 51, 243–267.

    Google Scholar 

  17. Hesser, J., Männer, R., & Stucky, O. (1989). Optimization of Steiner trees using genetic algorithms. In Proceedings of the third international conference on genetic algorithms (pp. 231–236). George Mason University, Fairfax, VA. San Francisco: Morgan Kaufmann.

    Google Scholar 

  18. Leung, Y., Li, G., & Xu, Z. B. (1998). A genetic algorithm for the multiple destination routing problems. IEEE Transactions on Evolutionary Computation, 2(4), 150–161.

    Article  Google Scholar 

  19. Haghighat, A. T., Faez, K., Dehghan, M., Mowlaei, A., & Ghahremani, Y. (2003). GA-based heuristic algorithms for QoS based multicast routing. Knowledge-Based Systems, 16(5–6), 305–312.

    Article  Google Scholar 

  20. Haghighat, A. T., Faez, K., Dehghan, M., Mowlaei, A., & Ghahremani, Y. (2004). GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing. Computer Communications, 27(1), 111–127.

    Article  Google Scholar 

  21. Skorin-Kapov, N., & Kos, M. (2003). The application of Steiner trees to delay constrained multicast routing: a tabu search approach. In ConTEL 2003: Proceedings of the seventh international conference on telecommunications (pp. 443–448). Zagreb, Croatia. New York: IEEE Press.

    Google Scholar 

  22. Prim, R. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, 36, 1389–1401.

    Google Scholar 

  23. Youssef, H., Al-Mulhem, A., Sait, S. M., & Tahir, M. A. (2002). QoS-driven multicast tree generation using tabu search. Computer Communications, 25(11–12), 1140–1149.

    Article  Google Scholar 

  24. Dijkstra, E. W. (1959). A note on two problems in connection with graphs. Numerische Mathematik, 1, 269–271.

    Article  Google Scholar 

  25. Wang, H., Wang, J., Wang, H., & Sun, Y. M. (2004). TSDLMRA: an efficient multicast routing algorithm based on tabu search. Journal of Network and Computer Applications, 27(2), 77–90.

    Article  Google Scholar 

  26. Zhang, B., & Mouftah, H. T. (2002). A destination-driven shortest path tree algorithm. In ICC 2002: Proceedings of the IEEE international conference on communications (pp. 2258–2262). New York: IEEE Press.

    Chapter  Google Scholar 

  27. Yen, J. Y. (1971). Finding the K-shortest loopless paths in a network. Management Science, 17(11), 712–716.

    Article  Google Scholar 

  28. Glover, F., & Laguna, M. (1997). Tabu search. Dordrecht: Kluwer Academic.

    Google Scholar 

  29. Gendreau, M., Larochelle, J. F., & Sansò, B. (1999). A tabu search heuristic for the Steiner tree problem. Networks, 34(2), 162–172.

    Article  Google Scholar 

  30. Xu, J., Chiu, S. Y., & Glover, F. (1996). Probabilistic tabu search for telecommunications network design. Combinatorial Optimization: Theory and Practice, 1(1), 69–94.

    Google Scholar 

  31. Glover, F. (1989). Tabu search—part I. INFORMS Journal on Computing, 1(3), 190–206.

    Google Scholar 

  32. Garcia-Luna-Aceves, J. J. (1992). Reliable broadcast of routing information using diffusing computations. In GLOBECOM ’92: IEEE global telecommunication conference (pp. 615–621). Orlando, FL. New York: IEEE Press.

    Google Scholar 

  33. Garcia-Luna-Aceves, J. J., & Behrens, J. (1995). Distributed, scalable routing based on vectors of link states. IEEE Journal on Selected Areas in Communications, 13(8), 1383–1395.

    Article  Google Scholar 

  34. Bertsekas, D., & Gallager, R. (1992). Data networks. Englewood Cliffs: Prentice-Hall.

    Google Scholar 

  35. Jimenez, V. M., & Marzal, A. (1999). Computing the K-shortest paths: a new algorithm and an experimental comparison. In Lecture notes in computer science (Vol. 1668, pp. 15–29). Berlin: Springer.

  36. Xu, J., Chiu, S. Y., & Glover, F. (1998). Optimizing a ring-based private line telecommunication network using tabu search. Management Science, 45(3), 330–345.

    Google Scholar 

  37. Moore, E. F. (1959). The shortest path through a maze. In Proceedings of the international symposium on theory of switching (pp. 285–292). Cambridge: Harvard University Press.

    Google Scholar 

  38. Glover, F., Laguna, M., & Marti, R. (2000). Fundamentals of scatter search and path relinking. Control and Cybernetics, 29(3), 653–684.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Engineering, Islamic Azad University, Tehran-South Branch, Tehran, Iran

    Nejla Ghaboosi

  2. Department of Electrical, Computer & IT, Islamic Azad University, Qazvin Branch, Qazvin, Iran

    Abolfazl T. Haghighat

Authors
  1. Nejla Ghaboosi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abolfazl T. Haghighat
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nejla Ghaboosi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ghaboosi, N., Haghighat, A.T. Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing. Telecommun Syst 34, 147–166 (2007). https://doi.org/10.1007/s11235-007-9031-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11235-007-9031-7

Keywords

Search

Navigation