Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective

Abstract

Abstract—The routing and spectrum assignment prob-lem has emerged as the key design and control problem in elastic optical networks. In this work, we show that the spectrumassignment (SA) problem inmesh networks trans-forms to the problem of scheduling multiprocessor tasks on dedicated processors. Based on this new perspective, we show that the SA problem in chain (linear) networks is NP-hard for four ormore links, but is solvable in polynomial time for three links. We also develop new constant-ratio approximation algorithms for the SA problem in chains when the number of links is fixed. Finally, we present sev-eral list scheduling algorithms that are computationally efficient and simple to implement, yet produce solutions that, on average, are within 1%–5 % of the lower bound. Index Terms—Approximation algorithms; Elastic optical networks; Multiprocessor scheduling; Network design;