Premium
Robust spectrum allocation in elastic flexgrid optical networks: Complexity and formulations
Author(s) -
Büsing Christina,
Grub Alexandra,
Koster Arie M. C. A.,
Laube Waldemar,
Tieves Martin
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21785
Subject(s) - frequency allocation , computational complexity theory , integer programming , computer science , mathematical optimization , spectrum (functional analysis) , bandwidth (computing) , enhanced data rates for gsm evolution , time complexity , bandwidth allocation , linear programming , resource allocation , mathematics , algorithm , telecommunications , computer network , physics , quantum mechanics
Flexgrid optical networking technology allows for a more flexible consumption of bandwidth. The spectrum allocation problem consists of the conflict‐free assignment of consecutive spectrum space of different sizes to lightpaths. In this article, we study the computational complexity of spectrum allocation with and without demand uncertainty. First, it is shown that the problem becomes already NP‐hard for cases where wavelength assignment is still polynomial time solvable. Next, five different ways to define the robust counterpart are compared. It is shown (amongst others) that on a single network edge, the two least efficient models are less computationally demanding than the other variants. A computational study using comparable integer linear programming formulations reveals that the additional slots required by these models directly depend on the restrictions of the employed technology. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 342–359 2017