Spectrum assignment in optical networks: A multiprocessor scheduling perspective

The routing and spectrum assignment problem has emerged as the key design and control problem in elastic optical networks. In this work, we show that the spectrum assignment (SA) problem in mesh networks transforms to the problem of scheduling multiprocessor tasks on dedicated processors. Based on t...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optical communications and networking 2014-08, Vol.6 (8), p.754-763
Main Authors: Talebi, Sahar, Bampis, Evripidis, Lucarelli, Giorgio, Katib, Iyad, Rouskas, George N.
Format: Article
Language:English
Subjects:
Algorithms
Approximation algorithms
Approximation methods
Chains
Elastic optical networks
Links
Lists
Multiprocessor
Multiprocessor scheduling
Network design
Networks
Optical communication
Optical fiber networks
Polynomials
Processor scheduling
Program processors
Routing and spectrum assignment
Schedules
Scheduling
Spectrum assignment
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The routing and spectrum assignment problem has emerged as the key design and control problem in elastic optical networks. In this work, we show that the spectrum assignment (SA) problem in mesh networks transforms 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 or more 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 several 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.
ISSN:1943-0620
1943-0639
DOI:10.1364/JOCN.6.000754