The minimum cost design of transparent optical networks combining grooming, routing, and wavelength assignment

Agostinho Agra, Amaro de Sousa, Mahdi Doostmohammadi

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.

LanguageEnglish
Pages3702-3713
Number of pages12
JournalIEEE/ACM Transactions on Networking
Volume24
Issue number6
Early online date7 Apr 2016
DOIs
Publication statusPublished - 31 Dec 2016

Fingerprint

Transparent optical networks
Wavelength
Heuristic methods
Fiber optic networks
Linear programming
Costs
Fibers

Keywords

  • grooming
  • hybrid heuristics
  • mixed integer linear programming
  • optical transport networks
  • routing and wavelength assignment
  • valid inequalities

Cite this

@article{270f8ca179c945ac801c1b5e270c44b8,
title = "The minimum cost design of transparent optical networks combining grooming, routing, and wavelength assignment",
abstract = "As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.",
keywords = "grooming, hybrid heuristics, mixed integer linear programming, optical transport networks, routing and wavelength assignment, valid inequalities",
author = "Agostinho Agra and {de Sousa}, Amaro and Mahdi Doostmohammadi",
note = "(c) 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2016",
month = "12",
day = "31",
doi = "10.1109/TNET.2016.2544760",
language = "English",
volume = "24",
pages = "3702--3713",
journal = "IEEE-ACM Transactions On Networking",
issn = "1063-6692",
number = "6",

}

The minimum cost design of transparent optical networks combining grooming, routing, and wavelength assignment. / Agra, Agostinho; de Sousa, Amaro; Doostmohammadi, Mahdi.

In: IEEE/ACM Transactions on Networking, Vol. 24, No. 6, 31.12.2016, p. 3702-3713.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The minimum cost design of transparent optical networks combining grooming, routing, and wavelength assignment

AU - Agra, Agostinho

AU - de Sousa, Amaro

AU - Doostmohammadi, Mahdi

N1 - (c) 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2016/12/31

Y1 - 2016/12/31

N2 - As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.

AB - As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.

KW - grooming

KW - hybrid heuristics

KW - mixed integer linear programming

KW - optical transport networks

KW - routing and wavelength assignment

KW - valid inequalities

UR - http://www.scopus.com/inward/record.url?scp=84963705931&partnerID=8YFLogxK

UR - https://www.research.ed.ac.uk/portal/en/publications/the-minimum-cost-design-of-transparent-optical-networks-combining-grooming-routing-and-wavelength-assignment(ffb9d481-e280-46be-89ad-719f54a81156).html

UR - https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=90

U2 - 10.1109/TNET.2016.2544760

DO - 10.1109/TNET.2016.2544760

M3 - Article

VL - 24

SP - 3702

EP - 3713

JO - IEEE-ACM Transactions On Networking

T2 - IEEE-ACM Transactions On Networking

JF - IEEE-ACM Transactions On Networking

SN - 1063-6692

IS - 6

ER -