EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1871. Lower and upper bounds for resources allocation in lightpath communication networks
Invited abstract in session TC-25: Graph and network optimization, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Enrico Malaguti
|
| DEI, University of Bologna | |
| 2. | Francesco Cavaliere
|
| DEI, University of Padova | |
| 3. | Federico Michelotto
|
| DEI, University of Bologna | |
| 4. | Michele Monaci
|
| DEI, University of Bologna | |
| 5. | Daniele Vigo
|
| DEI, University of Bologna |
Abstract
We consider the problem of allocating wavelengths of an optical network in order to serve a set of connection requests. In order to provide a robust allocation, communication must be ensured even in case of failure of some link, which is obtained by defining, for each connection request, two disjoint paths in the network. Each connection uses its working path by default, and is rerouted to its unique recovery path in case the working path is unavailable. As uniquely assigning both paths to a single connection may be highly inefficient, we adopt a shared protection policy, in which the same wavelength and path can be shared among different connections, provided that no collision arises. We discuss alternative relaxations for the problem based on Mixed-Integer Linear Programming formulations, and introduce a metaheuristic algorithm based on the Ruin-and-Recreate paradigm. Computational experiments on realistic data show that our algorithms are able to produce feasible solutions with tight optimality gap.
Keywords
- Combinatorial Optimization
- Graphs and Networks
- Telecommunications
Status: accepted
Back to the list of papers