Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Photonic Network Communications 1/2021

02.11.2020 | Original Paper

Solving routing and spectrum allocation problems in flexgrid optical networks using pre-computing strategies

verfasst von: Fernando Lezama, Alberto F. Martínez-Herrera, Gerardo Castañón, Carolina Del-Valle-Soto, Ana Maria Sarmiento, Enrique Muñoz de Cote

Erschienen in: Photonic Network Communications | Ausgabe 1/2021

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

Flexible optical network architectures are considered a very promising solution where spectrum resources are allocated within flexible frequency grids. This paper presents a minimum spectrum utilization (SU) and average path length (APL) approach to solve the (off-line) routing and spectrum allocation problem (RSA) based on combining a simple ordering pre-computation strategy, namely most subcarriers first (MSF) with three nature-inspired algorithms. These algorithms are ant colony optimization, differential evolution based relative position indexing (DE-RPI), and differential evolution general combinatorial (DE-GC). We begin by showing that MSF is the most effective ordering pre-computation strategy when compared to other well-known typical heuristics in the literature, such as first-fit, and longest path first. Then, we apply MSF in combination with the three nature-inspired algorithms to simultaneously optimize the SU and APL. The usefulness of MSF ordering pre-computation strategy is presented via a comparison of results obtained when using and not using MSF under the same scenarios. The algorithms are evaluated in benchmark optical networks, such as the NSFNet, the European optical network, and the 40-node USA network. We show that DE-RPI with MSF ordering pre-computation is the best option to solve the RSA problem, obtaining an average improvement percentage in the range of 0.9772–4.4086% on the SU and from \(-0.1668\) to 0.8511% on the APL when compared to other meta-heuristics, either with or without the MSF ordering policy.

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Fußnoten
1
Parametric analysis (or tuning of parametric) in meta-heuristics is a broad area of research that it is not within the scope of this investigation and is left as further work.
 
Literatur
1.
Zurück zum Zitat Zhang, G., De Leenheer, M., Morea, A., Mukherjee, B.: A survey on OFDM-based elastic core optical networking. IEEE Commun. Surv. Tutor. 15(1), 65–87 (2013). First CrossRef Zhang, G., De Leenheer, M., Morea, A., Mukherjee, B.: A survey on OFDM-based elastic core optical networking. IEEE Commun. Surv. Tutor. 15(1), 65–87 (2013). First CrossRef
2.
Zurück zum Zitat Kim, B.W., Lee, H.H., Lee, J.H., Kim, B.T.: Wavelength division multiplexing-passive optical network system. US Patent 9,008,513, 14 Apr 2015 Kim, B.W., Lee, H.H., Lee, J.H., Kim, B.T.: Wavelength division multiplexing-passive optical network system. US Patent 9,008,513, 14 Apr 2015
3.
Zurück zum Zitat Christodoulopoulos, K., Tomkos, I., Varvarigos, E.A.: Routing and spectrum allocation in OFDM-based optical networks with elastic bandwidth allocation. In: IEEE Global Telecommunications Conference, pp. 1–6 (2010) Christodoulopoulos, K., Tomkos, I., Varvarigos, E.A.: Routing and spectrum allocation in OFDM-based optical networks with elastic bandwidth allocation. In: IEEE Global Telecommunications Conference, pp. 1–6 (2010)
4.
Zurück zum Zitat Büsing, C., Grub, A., Koster, A.M.C.A., Laube, W., Tieves, M.: Robust spectrum allocation in elastic flexgrid optical networks: complexity and formulations. Networks 70(4), 342–359 (2017) MathSciNetCrossRef Büsing, C., Grub, A., Koster, A.M.C.A., Laube, W., Tieves, M.: Robust spectrum allocation in elastic flexgrid optical networks: complexity and formulations. Networks 70(4), 342–359 (2017) MathSciNetCrossRef
5.
Zurück zum Zitat Jue, J.P., Yang, W.-H., Kim, Y.-C., Zhang, Q.: Optical packet and burst switched networks: a review. IET Commun. 3(3), 334–352 (2009) CrossRef Jue, J.P., Yang, W.-H., Kim, Y.-C., Zhang, Q.: Optical packet and burst switched networks: a review. IET Commun. 3(3), 334–352 (2009) CrossRef
6.
Zurück zum Zitat Velasco, L., Klinkowski, M., Ruiz, M., Comellas, J.: Modeling the routing and spectrum allocation problem for flexgrid optical networks. Photon Netw. Commun. 24, 177–186 (2012) CrossRef Velasco, L., Klinkowski, M., Ruiz, M., Comellas, J.: Modeling the routing and spectrum allocation problem for flexgrid optical networks. Photon Netw. Commun. 24, 177–186 (2012) CrossRef
7.
Zurück zum Zitat Christodoulopoulos, K., Tomkos, I., Varvarigos, E.A.: Elastic bandwidth allocation in flexible OFDM-based optical networks. J. Lightwave Technol. 29(9), 1354–1366 (2011) CrossRef Christodoulopoulos, K., Tomkos, I., Varvarigos, E.A.: Elastic bandwidth allocation in flexible OFDM-based optical networks. J. Lightwave Technol. 29(9), 1354–1366 (2011) CrossRef
8.
Zurück zum Zitat Teixeira, D.B.A., Batista, C.T., Cardoso, A.J.F., Araújo, J.D.S.: A genetic algorithm approach for static routing and wavelength assignment in all-optical WDM networks. In: Portuguese Conference on Artificial Intelligence, pp. 421–432. Springer (2017) Teixeira, D.B.A., Batista, C.T., Cardoso, A.J.F., Araújo, J.D.S.: A genetic algorithm approach for static routing and wavelength assignment in all-optical WDM networks. In: Portuguese Conference on Artificial Intelligence, pp. 421–432. Springer (2017)
9.
Zurück zum Zitat Gong, L., Zhou, X., Wei, L., Zhu, Z.: A Two-population based evolutionary approach for optimizing routing, modulation and spectrum assignments (RMSA) in O-OFDM networks. IEEE Commun. Lett. 16(9), 1520–1523 (2012) CrossRef Gong, L., Zhou, X., Wei, L., Zhu, Z.: A Two-population based evolutionary approach for optimizing routing, modulation and spectrum assignments (RMSA) in O-OFDM networks. IEEE Commun. Lett. 16(9), 1520–1523 (2012) CrossRef
10.
Zurück zum Zitat Wang, Y., Cao, X., Pan, Y.: A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks. In: Proceedings IEEE INFOCOM, pp. 1503–1511 (2011) Wang, Y., Cao, X., Pan, Y.: A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks. In: Proceedings IEEE INFOCOM, pp. 1503–1511 (2011)
11.
Zurück zum Zitat Klinkowski, M., Walkowiak, K.: Routing and spectrum assignment in spectrum sliced elastic optical path network. IEEE Commun. Lett. 15(8), 884–886 (2011) CrossRef Klinkowski, M., Walkowiak, K.: Routing and spectrum assignment in spectrum sliced elastic optical path network. IEEE Commun. Lett. 15(8), 884–886 (2011) CrossRef
12.
Zurück zum Zitat Lezama, F., Castañón, G., Sarmiento, A.M., Martins, I.B.: Differential evolution optimization applied to the routing and spectrum allocation problem in flexgrid optical networks. Photon Netw. Commun. 31(1), 129–146 (2016) CrossRef Lezama, F., Castañón, G., Sarmiento, A.M., Martins, I.B.: Differential evolution optimization applied to the routing and spectrum allocation problem in flexgrid optical networks. Photon Netw. Commun. 31(1), 129–146 (2016) CrossRef
13.
Zurück zum Zitat Wang, Y., Zhang, J., Zhao, Y., Wang, J., Wanyi, G.: ACO-based routing and spectrum allocation in flexible bandwidth networks. Photon Netw. Commun. 25(3), 135–143 (2013) CrossRef Wang, Y., Zhang, J., Zhao, Y., Wang, J., Wanyi, G.: ACO-based routing and spectrum allocation in flexible bandwidth networks. Photon Netw. Commun. 25(3), 135–143 (2013) CrossRef
14.
Zurück zum Zitat Goscien, R., Klinkowski, M., Walkowiak, K.: A tabu search algorithm for routing and spectrum allocation in elastic optical networks. In: International Conference on Transparent Optical Networks, pp. 1–4 (2014) Goscien, R., Klinkowski, M., Walkowiak, K.: A tabu search algorithm for routing and spectrum allocation in elastic optical networks. In: International Conference on Transparent Optical Networks, pp. 1–4 (2014)
15.
Zurück zum Zitat Zhao, J., Wymeersch, H., Agrell, E.: Nonlinear impairment-aware static resource allocation in elastic optical networks. J. Lightwave Technol. 33(22), 4554–4564 (2015) CrossRef Zhao, J., Wymeersch, H., Agrell, E.: Nonlinear impairment-aware static resource allocation in elastic optical networks. J. Lightwave Technol. 33(22), 4554–4564 (2015) CrossRef
16.
Zurück zum Zitat Marković, G.Z.: Routing and spectrum allocation in elastic optical networks using bee colony optimization. Photon Netw. Commun. 34(3), 1–19 (2017) CrossRef Marković, G.Z.: Routing and spectrum allocation in elastic optical networks using bee colony optimization. Photon Netw. Commun. 34(3), 1–19 (2017) CrossRef
17.
Zurück zum Zitat Moniz, D., Eira, A., de Sousa, A., Pires, J.: On the comparative efficiency of non-disruptive defragmentation techniques in flexible-grid optical networks. Opt. Switch. Netw. 25, 149–159 (2017) CrossRef Moniz, D., Eira, A., de Sousa, A., Pires, J.: On the comparative efficiency of non-disruptive defragmentation techniques in flexible-grid optical networks. Opt. Switch. Netw. 25, 149–159 (2017) CrossRef
18.
Zurück zum Zitat Assis, K.D.R., dos Santos, A.F., Queiroz, I.M.: Routing in EON networks under mixed static and dynamic Traffic. In: Optical Metro Networks and Short-Haul Systems IX, vol. 10129, p. 1012908. International Society for Optics and Photonics (2017) Assis, K.D.R., dos Santos, A.F., Queiroz, I.M.: Routing in EON networks under mixed static and dynamic Traffic. In: Optical Metro Networks and Short-Haul Systems IX, vol. 10129, p. 1012908. International Society for Optics and Photonics (2017)
19.
Zurück zum Zitat Shahsavari, S., Beyranvand, H., Salehi, J.A.: Multi-quality of service routing and spectrum assignment in elastic optical networks. In: International Conference on Communications (ICC) (2017) Shahsavari, S., Beyranvand, H., Salehi, J.A.: Multi-quality of service routing and spectrum assignment in elastic optical networks. In: International Conference on Communications (ICC) (2017)
20.
Zurück zum Zitat Chatterjee, B., Sarma, N., Oki, E.: Routing and spectrum allocation in elastic optical networks: a tutorial. IEEE Commun. Surv. Tutor. PP(99), 1 (2015) Chatterjee, B., Sarma, N., Oki, E.: Routing and spectrum allocation in elastic optical networks: a tutorial. IEEE Commun. Surv. Tutor. PP(99), 1 (2015)
21.
Zurück zum Zitat Abkenar, F.S., Rahbar, A.G.: Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs). Opt. Switch. Netw. 23, 5–39 (2017) CrossRef Abkenar, F.S., Rahbar, A.G.: Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs). Opt. Switch. Netw. 23, 5–39 (2017) CrossRef
22.
Zurück zum Zitat Alyatama, A.: Analyzing the relative cost concept in elastic optical networks. In: International Conference on Computing, Networking and Communications (ICNC) (2017) Alyatama, A.: Analyzing the relative cost concept in elastic optical networks. In: International Conference on Computing, Networking and Communications (ICNC) (2017)
23.
Zurück zum Zitat Pavani, G.S., de França Queiroz, A., Pellegrini, J.C.: Analysis of ant colony optimization-based routing in optical networks in the presence of byzantine failures. Inf. Sci. 340, 27–40 (2016) MathSciNetCrossRef Pavani, G.S., de França Queiroz, A., Pellegrini, J.C.: Analysis of ant colony optimization-based routing in optical networks in the presence of byzantine failures. Inf. Sci. 340, 27–40 (2016) MathSciNetCrossRef
24.
Zurück zum Zitat Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997) MathSciNetCrossRef Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11(4), 341–359 (1997) MathSciNetCrossRef
25.
Zurück zum Zitat Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B Cybern. 26(1), 29–41 (1996) CrossRef Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B Cybern. 26(1), 29–41 (1996) CrossRef
26.
Zurück zum Zitat Mellal, M.A., Williams, E.J.: A survey on ant colony optimization, particle swarm optimization, and cuckoo algorithms. In: Handbook of Research on Emergent Applications of Optimization Algorithms, p. 37 (2017) Mellal, M.A., Williams, E.J.: A survey on ant colony optimization, particle swarm optimization, and cuckoo algorithms. In: Handbook of Research on Emergent Applications of Optimization Algorithms, p. 37 (2017)
27.
Zurück zum Zitat Wong, L., Moin, N.H.: Ant colony optimization for split delivery inventory routing problem. Malays. J. Comput. Sci. 30(4), 333–348 (2017) CrossRef Wong, L., Moin, N.H.: Ant colony optimization for split delivery inventory routing problem. Malays. J. Comput. Sci. 30(4), 333–348 (2017) CrossRef
Metadaten
Titel
Solving routing and spectrum allocation problems in flexgrid optical networks using pre-computing strategies
verfasst von
Fernando Lezama
Alberto F. Martínez-Herrera
Gerardo Castañón
Carolina Del-Valle-Soto
Ana Maria Sarmiento
Enrique Muñoz de Cote
Publikationsdatum
02.11.2020
Verlag
Springer US
Erschienen in
Photonic Network Communications / Ausgabe 1/2021
Print ISSN: 1387-974X
Elektronische ISSN: 1572-8188
DOI
https://doi.org/10.1007/s11107-020-00918-4

Weitere Artikel der Ausgabe 1/2021

Photonic Network Communications 1/2021 Zur Ausgabe