Annals of Computer Science and Information Systems, Volume 18

DOI: http://dx.doi.org/10.15439/2019F188

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 127–134 (2019)

Full text

Abstract. The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years. Existing integer linear programming models for the problem are either very complex and suffer from tractability issues or are simplified and incomplete so that they can optimize only some objective functions. The majority of models uses edge-path formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance. An alternative is to use edge-node formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance. However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions. Our contribution is to provide the first complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model. Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t. several objective functions. We further devise some directions of future research.

References

1. Cai, A., G. Shen, L. Peng, M. Zukerman: Novel Node-Arc Model and Multiiteration Heuristics for Static Routing and Spectrum Assignment in Elastic Optical Networks, in: Journal of Lightwave Technology 2013, 3402-3413. http://dx.doi.org/10.1109/JLT.2013.2282696
2. Christodoulopoulos, K., I. Tomkos and E. Varvarigos: Elastic bandwidth allocation in flexible OFDM based optical networks, IEEE J. Lightwave Technol. 29 (2011), 1354–1366. http://dx.doi.org/10.1109/JLT.2011.2125777
3. Fayez, M., I. Katib, G.N. Rouskas and H.M. Faheem, Spectrum Assign- ment in Mesh Elastic Optical Networks, IEEE Proc. of ICCCN (2015), 1–6. http://dx.doi.org/10.1109/ICCCN.2015.7288470
4. Goldberg, A.V., and Tarjan, R.E.: A New Approach to the Maximum Flow Problem, in: Journal on the Association for Computing Machinery. 35 (1988), 921–940.
5. Gröschel, M., Lovàsz, L., and Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.
6. Jia , X., F. Ning, S. Yin, D. Wang, J. Zhang and S. Huang: An integrated ILP model for Routing, Modulation Level and Spectrum Allocation in the next generation DCN, in: Third International Conference on Cyberspace Technology (CCT) 2015, 1–3. http://dx.doi.org/10.1049/cp.2015.0821
7. M. Jinno, H. Takara, B. Kozicki, Y. Tsukishima, Y. Sone, and S. Matsuoka: Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies, IEEE Commun. Mag. 47 (2009) 66–73. http://dx.doi.org/10.1109/MCOM.2009.5307468
8. Klinkowski, M., J. Pedro, D. Careglio, M. PiÃşro, J. Pires, P. Monteiro, and J. Solé-Pareta: An overview of routing methods in optical burst switching networks, in: Optical Switching and Networking 2010, 41 - 53. http://dx.doi.org/doi.org/10.1016/j.osn.2010.01.001
9. Klinkowski, M., and K. Walkowiak: Routing and Spectrum Assignment in Spectrum Sliced Elastic Optical Path Network, in: IEEE Communi- cations Society 2011, 884 - 886. http://dx.doi.org/10.1109/LCOMM.2011.060811.110281
10. Klinkowski, M., M. Pioro, M. Zotkiewicz, K. Walkowiak, M. Ruiz, and L. Velasco: Spectrum allocation problem in elastic optical networks - a branch-and-price approach, in: 17th International Conference on Transparent Optical Networks (ICTON) 2015, 1–5. http://dx.doi.org/10.1109/ICTON.2015.7193482
11. Klinkowski, M. and K. Walkowiak: A Simulated Annealing Heuristic for a Branch and Price-Based Routing and Spectrum Allocation Algorithm in Elastic Optical Networks, in: Intelligent Data Engineering and Automated Learning Book 2015, 290–299.
12. Net2Plan www.net2plan.com/ocn-book.
13. Ruiz, M. , and M. Pioro, M. Zotkiewicz, and M. Klinkowski and L. Velasco: Column generation algorithm for RSA problems in flexgrid optical networks, in: Photonic Network Communications 2013, 53–64. http://dx.doi.org/10.1007/s11107-013-0408-0
14. Shirazipourazad, S., Ch. Zhou, Z. Derakhshandeh and A. Sen: On routing and spectrum allocation in spectrum sliced optical networks, Proceedings of IEEE INFOCOM (2013), 385–389. http://dx.doi.org/10.1109/INFCOM.2013.6566800
15. Talebi, S., F. Alam, I. Katib, M. Khamis, R. Salama, and G.N. Rouskas: Spectrum management techniques for elastic optical networks: A survey, Optical Switching and Networking 13 (2014), 34–48. http://dx.doi.org/doi.org/10.1016/j.osn.2014.02.003
16. Velasco, L., M. Klinkowski, M. Ruiz, and J. Comellas: Modeling the routing and spectrum allocation problem for flexgrid optical networks, in: Photonic Network Communications 2012, 177–186. http://dx.doi.org/10.1007/s11107-012-0378-7
17. Walkowiak, K., R. Goscien, M. Klinkowski, and M. Wozniak: Opti- mization of Multicast Traffic in Elastic Optical Networks With Distance- Adaptive Transmission, in: IEEE Communications Letters 2014, 2117- 2120. http://dx.doi.org/10.1109/LCOMM.2014.2367511
18. Wang, Y., X. Cao and Y. Pan: A study of the routing and spectrum allo- cation in spectrum-sliced elastic optical path networks, in: Proceedings of IEEE INFOCOM 2011, 1503-1511. http://dx.doi.org/10.1109/INFCOM.2011.5934939
19. Zotkiewicz, M., M. Pioro, M. Ruiz, M. Klinkowski, and L. Velasco: Optimization models for flexgrid elastic optical networks, in: 15th International Conference on Transparent Optical Networks (ICTON) 2013, 1–4. http://dx.doi.org/10.1109/ICTON.2013.6602691