Exhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks

  • Iyad Katib King Abdulaziz University

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

[1] Chen, H.; Zhao, Y.; Zhang, J.; Wang, W.; Zhu, R. (2017). Static routing and spectrum assignment for deadline-driven bulk-data transfer in elastic optical networks. IEEE Access, 5, 13645-13653, 2017.
https://doi.org/10.1109/ACCESS.2017.2727338

[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
Published
2020-08-30
How to Cite
KATIB, Iyad. Exhaustive Search for Optimal Offline Spectrum Assignment in Elastic Optical Networks. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 15, n. 5, aug. 2020. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/3933>. Date accessed: 28 sep. 2020. doi: https://doi.org/10.15837/ijccc.2020.5.3933.