On the Complexity of Routing and Spectrum Assignment in Flexible Grid Ring Networks

The adoption of a flexible grid will benefit the network design and control plane of future optical networks by providing increased adaptability of spectral resources to heterogeneous network conditions. Unfortunately, this flexibility is gained at the cost of significant additional complexity in the network design and control. In this paper, we consider the optimization of routing and spectrum allocation in FlexiGrid Ring Networks and explore the trade-off between network cost (in terms of spectrum and transponder utilization) and problem complexity (in terms of number of variables/constraints and computational time). Such tradeoffs are investigated under multiple assumptions in terms of traffic grooming, regeneration, and modulation/baud rate assignment capabilities and contrasted to the case of Fixed grid. We show how in presence of traffic grooming the additional complexity due to the flexible grid has a minor impact on problem complexity. Similarly, in all the considered scenarios, regeneration and modulation/baud rate assignment do not relevantly impact problem complexity. We also consider two possible alternative Integer Linear Programming models: the slice-based and the channel-based approach. The former handles each slice individually, whereas the latter uses precomputed subsets of contiguous slices of different bandwidths. Both models are solved under several different network settings. Complexity comparison of the ILP models shows that the slice-based approach provides better performance than the channel-based approach, and that the performance gap between the two models increases with introduction of additional flexibility and dimensions.