On spectrum assignment in elastic optical tree-networks

Jean-Claude Bermond 1 Fatima Zahra Moataz 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : To face the explosion of the Internet trac, a new generation of optical networks is being developed; the Elastic Optical Networks (EONs). EONs use the optical spectrum eciently and flexibly, but that gives rise to more diculty in the resource allocation problems. In this article, we study the problem of Spectrum Assignment (SA) in Elastic Optical Tree-Networks. Given a set of trac requests with their routing paths (unique in the case of trees) and their spectrum demand, a spectrum assignment consists in allocating to each request an interval of consecutive slots (spectrum units) such that a slot on a given link can be used by at most one request. The objective of the SA problem is to find an assignment minimizing the total number of spectrum slots to be used. We prove that SA is NP-hard in undirected stars of 3 links and in directed stars of 4 links, and show that it can be approximated within a factor of 4 in general stars. Afterwards, we use the equivalence of SA with a graph coloring problem (interval coloring) to find constant-factor approximation algorithms for SA on binary trees with special demand profiles.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, In press
Liste complète des métadonnées

https://hal.inria.fr/hal-01962617
Contributeur : Jean-Claude Bermond <>
Soumis le : jeudi 20 décembre 2018 - 17:50:55
Dernière modification le : vendredi 21 décembre 2018 - 11:17:27

Fichier

elasticDAMpreprintsubmission.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01962617, version 1

Collections

Citation

Jean-Claude Bermond, Fatima Zahra Moataz. On spectrum assignment in elastic optical tree-networks. Discrete Applied Mathematics, Elsevier, In press. 〈hal-01962617〉

Partager

Métriques

Consultations de la notice

65

Téléchargements de fichiers

39