Login | Register

Large-Scale Modeling and Optimization of Routing, Modulation and Spectrum Assignment Problems in Optical Networks

Title:

Large-Scale Modeling and Optimization of Routing, Modulation and Spectrum Assignment Problems in Optical Networks

Mohammed, Adham (2020) Large-Scale Modeling and Optimization of Routing, Modulation and Spectrum Assignment Problems in Optical Networks. Masters thesis, Concordia University.

[thumbnail of Mohammed_MASc_S2021.pdf]
Preview
Text (application/pdf)
Mohammed_MASc_S2021.pdf - Accepted Version
Available under License Spectrum Terms of Access.
1MB

Abstract

One of the crucial decisions in managing flexible optical fiber networks is the provisioning
of connection requests, known as the Routing and Spectrum Assignment (RSA) problem,
and its extension: Routing, Modulation and Spectrum Assignment (RMSA) problem. Such
problems are becoming more and more challenging everyday with the steadily increasing
demand in optical networking. Therefore, considerable research effort has been exerted in
developing models and algorithms to efficiently solve larger problem instances. Yet, there
still exists a gap between the problem sizes that can be solved thanks to the previous research
efforts and the realistic problem sizes. This work is one step forward towards reducing this
gap.

In this thesis, we propose decomposition models for the RSA and RMSA problems based
on lightpath configurations. The proposed models are Integer Linear Programs (ILPs) with
an exponential number of configuration variables. Therefore, we have developed nested
column generation algorithms to exactly solve both problems. Furthermore, Lagrangian
Relaxation is used to compute valid upper bounds on the Integer Linear Programming
(ILP) optimal objective values, in order to compute a measure of solution quality: the
relative optimality gap.

The proposed algorithms are able to efficiently solve instances with sizes beyond what
has been so far published in literature, and more importantly, with considerably higher
quality, i.e., narrower relative optimality gaps.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Mechanical, Industrial and Aerospace Engineering
Item Type:Thesis (Masters)
Authors:Mohammed, Adham
Institution:Concordia University
Degree Name:M.A. Sc.
Program:Industrial Engineering
Date:1 December 2020
Thesis Supervisor(s):Jaumard, Brigitte
Keywords:Flexible Optical Networks; Network Provisioning; Routing, Modulation and Spectrum Assignment; Decomposition Models; Integer Linear Programming; Column Generation; Nested Column Generation; Lagrangian Relaxation
ID Code:987847
Deposited By: Adham Mohammed
Deposited On:27 Oct 2022 13:51
Last Modified:12 Jan 2023 01:00
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top