On Routing and Spectrum Assignment in Elastic Optical Networks

In recent years, OFDM has been the focus of extensive research efforts in optical transmission and networking, initially as a means to overcome physical impairments in optical communications. However, unlike, say, in wireless LANs or xDSL systems where OFDM is deployed as a transmission technology in a single link, in optical networks it is being considered as the technology underlying the novel elastic network paradigm. Hence, we dedicate this work to study and propose different solution methods for elastic optical networks (EONs) topologies.;In Chapter 1, we discuss the necessity of applying EONs along with all the benefits it brings to the optical networks. We also review the set of constraints (i.e. spectrum contiguity and continuity constraints) that must be satisfied during traffic demands allocation to the spectrum. Then, we classify existing spectrum management techniques for EONs, including offline and online routing and spectrum assignment (RSA), distance-adaptive RSA, fragmentation-aware RSA, traffic grooming, survivability, and multi-path RSA problems in Chapter 2.;We then provide a new insight into the spectrum assignment (SA) problem in mesh networks in Chapter 3 and show that the SA problem transforms to the problem of scheduling multiprocessor tasks on dedicated processors. Similarly, we prove that the RSA problem with fixed-alternate routing in general-topology (mesh) networks (and, hence, in rings as well) is a special case of a multiprocessor scheduling problem.;Based on this new perspective, we show in Chapter 4 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 chain networks with the fixed number of links. Finally, we introduce a suite of 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.;In Chapter 5, we consider bidirectional ring networks and investigate two problems: (1) the SA problem under the assumption that each demand is routed along a single fixed path (e.g., the shortest path), and (2) the general case of the RSA problem whereby a routing decision along the clockwise and counter-clockwise directions must be made jointly with spectrum allocation. Based on insights from multiprocessor scheduling theory, we investigate the complexity of these two problems and develop new constant-ratio approximation algorithms with a ratio that is strictly smaller than the best known ratio to date.;We also show that the distance-adaptive RSA (DA-RSA) problem in mesh networks is a special case of a multiprocessor scheduling problem in Chapter 6. We then develop a suite of efficient and effective DA-RSA algorithms that build upon list scheduling concepts. The numerical results indicate that as the network size increases beyond a point that depends on the traffic demand distribution, the spectrum overhead associated with using a long path becomes sufficiently high that it is always best to use the shortest path. Overall, the best algorithm is always within 10-20% of the lower bound, indicating that scheduling concepts can be successfully adapted to address network design problems.;In Chapter 7, we examine the complexity of the DA-RSA problem for general (mesh) networks and derive a set of conditions that makes this problem either NP-hard or polynomially solvable. We also develop an efficient and effective algorithm for mesh networks that builds upon list scheduling concepts in which routing and spectrum allocation decisions are made jointly. We then run an extensive simulations for DA-RSA in mesh networks to estimate the required amount spectrum for different size networks. Our work explores the tradeoffs involved in DA-RSA algorithm design, and opens up new research directions in leveraging the vast literature in scheduling theory to address important and practical problems in network design.;Finally, we discuss future research directions for the SA and RSA problems in EONs in Chapter 8.