PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

A novel integer linear programming model for routing and spectrum assignment in optical networks

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Konferencja
Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
Języki publikacji
EN
Abstrakty
EN
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.
Rocznik
Tom
Strony
127--134
Opis fizyczny
Bibliogr. 19 poz., wz., tab., rys.
Twórcy
  • Université Clermont Auvergne, LIMOS (UMR 6158 CNRS), Clermont-Ferrand, France
  • Université Clermont Auvergne, LIMOS (UMR 6158 CNRS), Clermont-Ferrand, France
  • Université Clermont Auvergne, LIMOS (UMR 6158 CNRS), Clermont-Ferrand, France
Bibliografia
  • 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
Uwagi
1. This work was supported by the French National Research Agency grant ANR-17-CE25-0006, project FLEXOPTIM.
2. Track 1: Artificial Intelligence and Applications
3. Technical Session: 12th International Workshop on Computational Optimization
4. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-2aa44561-86e5-463f-ae9d-761ffc3f2a29
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.