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)Abstract
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.
References
[2] 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
[3] 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
[4] 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
[5] 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
[6] 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
[7] 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
[8] 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
[9] 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
[10] 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
[11] 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
[12] 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
[13] 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.
[14] 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
[15] 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
[16] 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
[17] 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
Additional Files
Published
Issue
Section
License
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.
