Optimization Online


Stochastic RWA and Lightpath Rerouting in WDM Networks

Maryam Daryalal(m.daryalal***at***mail.utoronto.ca)
Merve Bodur(bodur***at***mie.utoronto.ca)

Abstract: In a telecommunication network, Routing and Wavelength Assignment (RWA) is the problem of finding lightpaths for incoming connection requests. When facing a dynamic traffic, greedy assignment of lightpaths to incoming requests based on predefined deterministic policies leads to a fragmented network that cannot make use of its full capacity due to stranded bandwidth. At this point service providers try to recover the capacity via a defragmentation process. We study this setting from two perspectives: (i) while granting the connection requests via the RWA problem and (ii) during the defragmentation process by lightpath rerouting. For both problems, we present the first two-stage stochastic integer programming model incorporating incoming request uncertainty to maximize the expected grade of service. We develop a decomposition-based solution approach, which uses various relaxations of the problem and a newly developed problem-specific cut family. Simulation of two-stage policies for a variety of instances in a rolling-horizon framework of 52 stages shows that our stochastic models provide high-quality solutions compared to traditionally used deterministic ones. Specifically, the proposed provisioning policies yield improvements of up to 19% in overall grade of service and 20% in spectrum saving, while the stochastic lightpath rerouting policies grant up to 36% more requests using up to just 4% more bandwidth spectrum.

Keywords: Two-stage Stochastic Programming, Routing and Wavelength Assignment, Lightpath Rerouting, Optical Networks

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/17/2020
Entry Accepted: 12/18/2020
Entry Last Modified: 12/17/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society