Exhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks
Keywords:Elastic Optical Network (EON), exhaustive search, Spectrum Assignment (SA), Routing and Spectrum Assignment(RSA)
Heuristic-based approaches are widely deployed in solving Spectrum Assignment problem. This causes the results to be unreliable in some test cases when the results are very far from the lowerbound. This paper presents an exhaustive search approach that starts with an initial seed of a solution achieved by a heuristic-based algorithm called “Longest First Fit” (LFF) and tries all possible permutations starting from this initial seed. The algorithm skips some branches and all its descendant permutations if it meets certain criteria that guarantees that those permutations will not lead to a better result. The experimental results show that the new algorithm has succeeded in achieving the lower-bound in 93% of the randomly generated test cases while the heuristic solver LFF can achieve 65%. The algorithm achieves these results in a reasonable running time of less than 10 seconds.
 Dijkstra, E. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, Springer, 1(1), 269-271, 1959. https://doi.org/10.1007/BF01386390
 Fayez, M.; Katib, I.; Rouskas, G.; Faheem, H. (2016). Scheduling-Inspired Spectrum Assignment Algorithms for Mesh Elastic Optical Networks. Advances In Computer Communications And Networks: From Green, Mobile, Pervasive Networking To Big Data Computing, River Publishers, 225, 2016. https://doi.org/10.1109/ICCCN.2015.7288470
 Fayez, M.; Katib, I.; Rouskas, G.; Faheem, H. (2015). Spectrum Assignment in Mesh Elastic Optical Networks. Proceedings Of The 24th International Conference On Computer Communications And Networks (ICCCN), 2015. https://doi.org/10.1109/ICCCN.2015.7288470
 Fayez, M.; Katib, I.; Rouskas, G.; Gharib, T.; Khaleed, H.; Faheem, H. (2019). Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem. Ain Shams Engineering Journal, Elsevier, 2019. https://doi.org/10.1016/j.asej.2019.10.008
 Gerstel, O.; Jinno, M.; Lord, A.; Yoo, S. (2012). Elastic optical networking: a new dawn for the optical layer? Communications Magazine, IEEE, 50(2), s12--s20, 2012. https://doi.org/10.1109/MCOM.2012.6146481
 Goscien, R.; Walkowiak, K.; Klinkowski, M. (2015). Tabu search algorithm for routing, modulation and spectrum allocation in elastic optical network with anycast and unicast traffic. Computer Networks, 79, 148-165, 2015. https://doi.org/10.1016/j.comnet.2014.12.004
 Jaumard, B.; Daryalal, M. (2017). Efficient spectrum utilization in large scale RWA problems. IEEE/ACM Transactions On Networking (TON), IEEE Press, 25(2), 1263-1278, 2017. https://doi.org/10.1109/TNET.2016.2628838
 Klinkowski, M.; Lechowicz, P.; Walkowiak, K. (2018). Survey of resource allocation schemes and algorithms in spectrally-spatially flexible optical networking. Optical Switching And Networking, Elsevier, 27, 58-78, 2018. https://doi.org/10.1016/j.osn.2017.08.003
 Klinkowski, M.; Walkowiak, K. (2011). Routing and spectrum assignment in spectrum sliced elastic optical path network. IEEE Communications Letters, 15(8), 884-886, 2011. https://doi.org/10.1109/LCOMM.2011.060811.110281
 Klinkowski, M.; Zotkiewicz, M.; Walkowiak, K.; Ruiz, M.; Velasco, L.; (2016). Solving large instances of the RSA problem in flexgrid elastic optical networks. IEEE/OSA Journal Of Optical Communications And Networking, IEEE, 8(5), 320-330, 2016. https://doi.org/10.1364/JOCN.8.000320
 Ma, S.; Wang, Y.; Guo, B.; Chen, X.; Li, J.; Chen, Z.; He, Y. (2013). A fairness-aware dynamic spectrum allocation scheme in elastic optical networks. Optoelectronics And Communications Conference And Photonics In Switching, 6, 2013. https://doi.org/10.1364/ACPC.2013.AF2G.30
 Perelló, J.; Spadaro, S. (2012). Lightpath fragmentation for efficient spectrum utilization in dynamic elastic optical networks. 2012 16th International Conference On Optical Network Design And Modelling (ONDM), 1-6, 2012.
 Ramamurthy, R.; Mukherjee, B. (2002). Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks. IEEE/ACM Transactions On Networking, IEEE, 10(3), 351- 367, 2002. https://doi.org/10.1109/TNET.2002.1012367
 Talebi, S.; Alam, F.; Katib, I.; Khamis, M.; Salama, R.; Rouskas, G. (2014). Spectrum management techniques for elastic optical networks: A survey. Optical Switching And Networking, Elsevier, 13, 34-48, 2014. https://doi.org/10.1016/j.osn.2014.02.003
 Talebi, S.; Bampis, E.; Lucarelli, G.; Katib, I.; Rouskas, G. (2014). Spectrum assignment in optical networks: A multiprocessor scheduling perspective. IEEE/OSA Journal Of Optical Communications And Networking, 6(8), 754-763, 2014. https://doi.org/10.1364/JOCN.6.000754
 Wu, J.; Subramaniam, S.; Hasegawa, H. (2019). Efficient dynamic routing and spectrum assignment for multifiber elastic optical networks. IEEE/OSA Journal Of Optical Communications And Networking, IEEE, 11(5), 190-201, 2019. https://doi.org/10.1364/JOCN.11.000190
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.