Skip to main content
SpringerLink
Log in

A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms and heuristics in the literature.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Cheng X, Du DZ (2001) Steiner trees in industry. Kluwer Academic, Dordrecht

    Google Scholar 

  2. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York

    MATH  Google Scholar 

  3. Guo L, Matta I (1999) QDMR: An efficient QoS dependent multicast routing algorithm. In: Proceedings of the 5th IEEE real time technology and applications symposium, pp 213–222

  4. Salama HF, Reeves DS, Viniotis Y (1997) Evaluation of multicast routing algorithms for real-time communication on high-speed networks. IEEE J Sel Areas Commun 15:332–345

    Article  Google Scholar 

  5. Yeo CK, Lee BS, Er MH (2004) A survey of application level multicast techniques. Comput Commun 27:1547–1568

    Article  Google Scholar 

  6. Masip-Bruin X, Yannuzzi M, Domingo-Pascual J, Fonte A, Curado M, Monteiro E, Kuipers F, Van Mieghem P, Avallone S, Ventre G, Aranda-Gutierrez P, Hollick M, Steinmetz R, Iannone L, Salamatian K (2006) Research challenges in QoS routing. Comput Commun 29:563–581

    Article  Google Scholar 

  7. Diot C, Dabbous W, Crowcroft J (1997) Multipoint communication: a survey of protocols, functions, and mechanisms. IEEE J Sel Areas Commun 15:277–290

    Article  Google Scholar 

  8. Oliveira CAS, Pardalos PM (2005) A survey of combinatorial optimization problems in multicast routing. Comput Oper Res 32(8):1953–1981

    Article  MATH  Google Scholar 

  9. Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/steininfo.html

    Google Scholar 

  10. Kompella VP, Pasquale JC, Polyzos GC (1993) Multicast routing for multimedia communication. IEEE/ACM Trans Netw 1:286–292

    Article  Google Scholar 

  11. Widyono R (1994) The design and evaluation of routing algorithms for realtime channels. Technical Report, ICSI TR-94-024, International Computer Science Institute, UC Berkeley

  12. Sun Q, Langendoerfer H (1995) Efficient multicast routing for delay-sensitive applications. In: Proceedings of the 2nd workshop on protocols for multimedia systems, pp 452–458

  13. Sun Q, Langendoerfer H (1997) An efficient delay-constrained multicast routing algorithm. Technical Report, Internal Report, Institute of Operating Systems and Computer Networks, TU Braunschweig, Germany

  14. Zhu Q, Parsa M, Garcia-Luna-Aceves JJ (1995) A source-based algorithm for delay-constrained minimum-cost multicasting. In: Proceedings of the 14th annual joint conference of the IEEE computer and communication (INFOCOM’95). IEEE Comput Soc, Boston, pp 377–385

    Google Scholar 

  15. Kompella VP, Pasquale JC, Polyzos GC (1993) Two distributed algorithms for the constrained Steiner tree problem. In: Proceedings of the 2nd international conference on computer communications and networking, pp 343–349

  16. Shaikh A, Shin K (1997) Destination-driven routing for low-cost multicast. IEEE J Sel Areas Commun 15:373–381

    Article  Google Scholar 

  17. Jia X (1998) A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks. IEEE/ACM Trans Netw 6:828–837

    Article  Google Scholar 

  18. Wang XL, Jiang Z (2004) QoS multicast routing based on simulated annealing algorithm. In: Proceedings international and applications, pp 511–516

  19. Kun Z, Heng W, Feng-Yu L (2005) Distributed multicast routing for delay variation-bounded Steiner tree using simulated annealing. Comput Commun 28:1356–1370

    Article  Google Scholar 

  20. Wang Z, Shi B, Zhao E (2001) Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm. Comput Commun 24:685–692

    Article  Google Scholar 

  21. Haghighat AT, Faez K, Dehghan M, Mowlaei A, Ghahremani Y (2004) GA-based heuristic algorithms for bandwidth-delay-constrained least-cost multicast routing. Comput Commun 27:111–127

    Article  Google Scholar 

  22. Zahrani MS, Loomes MJ, JA Malcolm, Dayem Ullah AZM, Steinhofel K, Albrecht AA (2008) Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing. Comput Oper Res 35:2049–2070

    Article  MATH  MathSciNet  Google Scholar 

  23. Kim SJ, Choi MK (2007) Evolutionary Algorithms for route selection and rate allocation in multirate multicast networks. Appl Intell 26(3):197–215

    Article  MATH  Google Scholar 

  24. Youssef H, Al-Mulhem A, Sait SM, MA Tahir (2002) QoS-driven multicast tree generation using tabu search. Comput Commun 25(11–12):1140–1149

    Article  Google Scholar 

  25. Skorin-Kapov N, Kos M (2003) The application of Steiner trees to delay constrained multicast routing: a tabu search approach. In: Proceedings of the seventh international conference on telecommunications, Zagreb, Croatia

  26. Wang H, Fang J, Wang H, Sun YM (2004) TSDLMRA: an efficient multicast routing algorithm based on tabu search. J Netw Comput Appl 27:77–90

    Article  Google Scholar 

  27. Ghaboosi N, Haghighat AT (2006) A tabu search based algorithm for multicast routing with QoS constraints. In: 9th international conference on information technology, pp 18–21

  28. Ghaboosi N, Haghighat AT (2007) A path relinking approach for delay-constrained least-cost multicast routing problem. In: 19th international conference on tools with artificial intelligence, pp 383–390

  29. Skorin-Kapov N, Kos M (2006) A GRASP heuristic for the delay-constrained multicast routing problem. Telecommun Syst 32(1):55–69

    Article  Google Scholar 

  30. Xu Y, Qu R (2009) A GRASP approach for the delay-constrained multicast routing problem. In: Proceedings of the 4th multidisciplinary international scheduling conference (MISTA4). Dublin, Ireland

  31. Qu R, Xu Y, Kendall G (2009) A variable neighborhood descent search algorithm for delay-constrained least-cost multicast routing. In: Stützle T (ed) Proceedings of learning and intelligent optimization (LION3). LNCS, vol 5851. Springer, Berlin, pp 15–29

    Chapter  Google Scholar 

  32. Betsekas D, Gallager R (1992) Data networks, 2nd edn. Englewood Cliffs, Prentice-Hall

    Google Scholar 

  33. Cormen TH, Leiserson CE, Revest RL (1997) Introduction to algorithms. MIT Press, Cambridge

    Google Scholar 

  34. Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28(2):652–673

    Article  MATH  MathSciNet  Google Scholar 

  35. Glover F (1998) A template for scatter search and path relinking. In: Hao JK, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Artificial Evolution. LNCS, vol 1363. Springer, Berlin, pp 3–51

    Chapter  Google Scholar 

  36. Glover F, Laguna M, Martí R (2000) Fundamentals of scatter search and path relinking. Control Cybern 29(3):653–684

    MATH  Google Scholar 

  37. Glover F, Løkketangen A, Woodruff DL (2000) Scatter search to generate diverse MIP solutions. In: Laguna M, González-Velarde JL (eds) OR computing tools for modeling, optimization and simulation: interfaces in computer science and operations research, pp 299–317

  38. Drias H, Khabzaoui M (2001) Scatter search with random walk strategy for SAT and MAX-W-SAT problems. In: LNCS, vol 2070. Springer, Berlin, pp 35-44

    Google Scholar 

  39. Hamiez JP, Hao JK (2002) Scatter search for graph coloring. In: LNCS, vol 2310. Springer, Berlin, pp 168–179

    Google Scholar 

  40. Tang J, Zhang J, Pan Z (2010) A Scatter search for solving vehicle routing problem with loading cost. Expert Syst Appl 37(6):4073–4083

    Article  Google Scholar 

  41. Bastos MP Ribeiro CC (1999) Reactive tabu search with path relinking for the Steiner problem in graphs. In: Proceedings of the third metaheuristics international conference, Angra dos Reis, Brazil

  42. Waxman BM (1988) Routing of multipoint connections. IEEE J Sel Areas Commun 6:1617–1622

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Automated Scheduling, Optimisation and Planning (ASAP) Group, School of Computer Science, The University of Nottingham, Nottingham, NG8 1BB, UK

    Ying Xu & Rong Qu

  2. School of Computer and Communication, Hunan University, Changsha, Hunan, 410082, China

    Ying Xu

Authors
  1. Ying Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rong Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ying Xu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, Y., Qu, R. A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems. Appl Intell 36, 229–241 (2012). https://doi.org/10.1007/s10489-010-0256-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-010-0256-x

Keywords

Search

Navigation