Greedy randomised adaptive search procedures for topological design of MPLS networks

Authors

DOI:

https://doi.org/10.26636/jtit.2002.2.126

Keywords:

network design, optimisation, MPLS, GRASP, local search

Abstract

In this paper, the IP/MPLS network cost optimisation problem of selecting localisation of nodes and links, combined with link`s dimensioning, is discussed. As the considered problem is hard, we discuss and propose greedy randomised adaptive search procedure (GRASP) based solution method. GRASP is an iterative randomised sampling technique which combines adaptive randomised greedy function in constructing initial solution with local search optimisation. The effectiveness of the method is illustrated by means of a numerical study. We compare the GRASP results with results for both exact and heuristic methods obtained in previous research concerning topological design problem.

Downloads

Download data is not yet available.

References

[1] M. Pióro, A. Jüttner, J. Harmatos, Á. Szentesi, P. Gajowniczek, and A. Mysłek, "Topological design of telecommunication networks. Nodes and links localization under demand constraints", in 17th Int. Teletraf. Congr., 2001.
View in Google Scholar

[2] M. Minoux, "Network synthesis and optimum network design problems: models, solution methods and application", Networks, vol. 19, pp. 313-360, 1989.
View in Google Scholar

[3] H. H. Hoang, "A computational approach to the selection of an optimal network", Manag. Sci., vol. 19, pp. 488-498, 1973.
View in Google Scholar

[4] D. E. Boyce, A. Farhi, and R. Weischedel, "Optimal network problem: a branch and bound algorithm", Envir. Plan., vol. 5, pp. 519-533, 1973.
View in Google Scholar

[5] R. Dionne and M. Florian, "Exact and approximate algorithms for optimal network design", Networks, vol. 9, pp. 37-59, 1979.
View in Google Scholar

[6] B. Gendron, T. G. Crainic, and A. Fragnioni, "Multicommodity capacitated network design", in Telecommunication Network Planning, B. Sanso and P. Soriano, Eds. Boston: Kluwer, 1996.
View in Google Scholar

[7] A. Balakrishnan, T. L. Magnanti, and R. T. Wong, "A dual-ascent procedure for large-scale uncapacitated network design", Oper. Res., vol. 37, no. 5, pp. 726-740, 1989.
View in Google Scholar

[8] D. S. Johnson, J. K. Lenstra, and A. H. G. Rinnoy Kan, "The complexity of the network design problem", Networks, vol. 8, pp. 279-285, 1978.
View in Google Scholar

[9] M. Pióro, A. Mysłek, A. Jüttner, J. Harmatos, and Á. Szentesi, "Topological design of MPLS networks", in Globecom, San Antonio, 2001.
View in Google Scholar

[10] T. A. Feo, M. G. C. Resende, and S. H. Smith, "Greedy randomized adaptive search procedure for maximum independent set", Oper. Res., vol. 42, no. 5, pp. 860-887, 1994.
View in Google Scholar

[11] T. A. Feo and M. G. C. Resende, "Greedy randomized adaptive search procedures", J. Glob. Opt., vol. 6, pp. 109-133, 1995.
View in Google Scholar

[12] M. G. C. Resende, "GRASP bibliography", http://www.research.att.com/ mgcr/doc/graspbib.pdf
View in Google Scholar

[13] Examples of TNLLP networks, http://www.tele.pw.edu.pl/networks/TNLLP/
View in Google Scholar

Downloads

Submitted

2023-04-07

Published

2002-06-30

Issue

No. 2 (2002)

Section

ARTICLES FROM THIS ISSUE

License

Copyright (c) 2002 Journal of Telecommunications and Information Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
A. Mysłek, “Greedy randomised adaptive search procedures for topological design of MPLS networks”, JTIT, vol. 8, no. 2, pp. 26–32, Jun. 2002, doi: 10.26636/jtit.2002.2.126.