TY - GEN
T1 - Resolution of a Routing and Wavelength Assignment Problem by Independent Sets in Conflict Graphs
AU - Hudry, Olivier
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/6/29
Y1 - 2020/6/29
N2 - In an optical network, a Scheduled Lightpath Demand (SLD) is a connection demand between two nodes, during a certain time and with a certain wavelength. We consider the following NP-hard Routing and Wavelength Assignment problem dealing with SLDs: given a set of SLDs and a number W of wavelengths, maximize the number of SLDs to which we can assign a lightpath (i.e. a routing path and a wavelength) without exceeding the number W of available wavelengths. The constraints are: a same wavelength must be assigned all along the routing path of any SLD; at any time, a given wavelength on a given edge of the network cannot be used to satisfy more than one SLD. To solve this problem, we study an approach stating the problem as the successive searches of independent sets in some conflict graphs. Moreover, we improve this approach thanks to a post-optimization method. The experimental results show that this model and the post-optimization method are quite efficient to provide a large number of routed SLDs.
AB - In an optical network, a Scheduled Lightpath Demand (SLD) is a connection demand between two nodes, during a certain time and with a certain wavelength. We consider the following NP-hard Routing and Wavelength Assignment problem dealing with SLDs: given a set of SLDs and a number W of wavelengths, maximize the number of SLDs to which we can assign a lightpath (i.e. a routing path and a wavelength) without exceeding the number W of available wavelengths. The constraints are: a same wavelength must be assigned all along the routing path of any SLD; at any time, a given wavelength on a given edge of the network cannot be used to satisfy more than one SLD. To solve this problem, we study an approach stating the problem as the successive searches of independent sets in some conflict graphs. Moreover, we improve this approach thanks to a post-optimization method. The experimental results show that this model and the post-optimization method are quite efficient to provide a large number of routed SLDs.
KW - Combinatorial Optimization
KW - Conflict Graphs
KW - Independent Sets
KW - Post-Optimization
KW - Routing and Wavelength Assignment (RWA) Problem
KW - Scheduled Lightpath Demands (SLD)
KW - Wavelength Division Multiplexing (WDM) Optical Networks
UR - https://www.scopus.com/pages/publications/85098250114
U2 - 10.1109/CoDIT49905.2020.9263857
DO - 10.1109/CoDIT49905.2020.9263857
M3 - Conference contribution
AN - SCOPUS:85098250114
T3 - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
SP - 94
EP - 99
BT - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 7th International Conference on Control, Decision and Information Technologies, CoDIT 2020
Y2 - 29 June 2020 through 2 July 2020
ER -