A Packing Problem Approach to Lightpath Assignment in an Optical Ring

David Poulain 1 Joanna Tomasik 1 Marc-Antoine Weisser 1 Dominique Barth 2
1 E3S - Supélec Sciences des Systèmes [Gif-sur-Yvette]
2 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation
Abstract : We present our work on the dimensioning of a packet-switching wavelength division multiplexing ring in order to reduce its infrastructure (capital expenditure) cost. We study a new all-optical architecture: the packed optical add-drop multiplexer (POADM). We aim to minimize the overall cost of the network by reducing the number of indispensable devices in the nodes and the number of required wavelengths. We formalize the packing problems underlying the ring dimensioning. The elements to be packed are made up of transmissions that share the same destination. We assume that elements can be cut before being packed into boxes. We furnish a complete theoretical analysis of the complexity and approximability of these problems. We define also several measures of quality for a cut and provide an optimal cutting strategy, according to these measures. Our subsequent contribution is a heuristic solution that solves the bi-criteria packing problem (the number of boxes and the number of cuts are minimized simultaneously). The exhaustive numerical results of this heuristic algorithm come next. We rely on our optimal cutting strategy to appraise the efficiency of other strategies. We also adapt the only existing POADM dimensioning algorithm, more restrictive than ours, and we confront it with our solution. The analysis of results allows us to provide network design guidelines to perform the dimensioning in the most efficient way.
Mots-clés : dimensionnement de réseaux problèmes de découpe et de conditionnement approximabilité anneaux optiques
Document type :
Journal articles
Complete list of metadatas
https://hal-supelec.archives-ouvertes.fr/hal-00831550
Contributor : Elodie Dubrac <>
Submitted on : Friday, June 7, 2013 - 11:33:08 AM
Last modification on : Saturday, September 15, 2018 - 1:03:06 AM

Identifiers

Collections

PRISM | SUPELEC | UVSQ | SUP_INFO

Citation

David Poulain, Joanna Tomasik, Marc-Antoine Weisser, Dominique Barth. A Packing Problem Approach to Lightpath Assignment in an Optical Ring. The Computer Journal, Oxford University Press (UK), 2014, 57 (8), pp.1155-1166. ⟨10.1093/comjnl/bxt050⟩. ⟨hal-00831550⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

312

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD