Algorithmique et télécommunications : Coloration et multiflot approchés et applications aux réseaux d'infrastructure

Hervé Rivano 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Cette thèse s'intéresse aux problématiques fondamentales d'optimisation combinatoire qui se dégagent de la modélisation structurelle et algorithmique du dimensionnement des réseaux d'infrastructure de télécommunication. L'optimisation de ces réseaux est essentielle aux opérateurs de télécommunication, qui demandent la garantie d'une exploitation efficace des ressources déployées.

Nous donnons une nouvelle modélisation des réseaux optiques WDM multifibres. En considérant un routage agrégé au niveau des câbles, nous optons pour une nouvelle lecture des contraintes d'affectation de longueurs d'onde fondée sur des conflits de groupe.

Nous étudions aussi le problème de coloration de chemins, issu de l'affectation de longueurs d'onde dans les réseaux optiques monofibres. Nous développons, pour la relaxation linéaire de ce problème, un algorithme polynomial efficace dans les arbres de degré borné, puis, par extension, dans les graphes de largeur arborescente bornée. Nous majorons le coût d'une telle coloration dans les arbres binaires et donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la coloration entière dans les arbres de degré borné, ce qui améliore le meilleur algorithme connu pour ce cas.

Nous présentons enfin des avancées algorithmiques pour les problèmes de multiflot entier et fractionnaire. Nous donnons un algorithme d'arrondi aléatoire incrémental pour l'approximation du multiflot entier. Motivés par le besoin d'un calcul rapide de multiflot fractionnaire pour l'algorithme précédent, nous nous intéressons aux approximations combinatoires de ce problème. En employant des techniques de calcul dynamique des plus courts chemins, nous améliorons l'un des meilleurs algorithme de la littérature.
Webstats4U - Free web site statistics
Type de document :
Thèse
Réseaux et télécommunications [cs.NI]. Université Nice Sophia Antipolis, 2003. Français
Liste complète des métadonnées

https://tel.archives-ouvertes.fr/tel-00169842
Contributeur : Hervé Rivano <>
Soumis le : mercredi 5 septembre 2007 - 11:28:36
Dernière modification le : mercredi 5 septembre 2007 - 11:34:20
Document(s) archivé(s) le : jeudi 8 avril 2010 - 19:20:52

Fichiers

Identifiants

  • HAL Id : tel-00169842, version 1

Collections

Citation

Hervé Rivano. Algorithmique et télécommunications : Coloration et multiflot approchés et applications aux réseaux d'infrastructure. Réseaux et télécommunications [cs.NI]. Université Nice Sophia Antipolis, 2003. Français. 〈tel-00169842〉

Partager

Métriques

Consultations de
la notice

514

Téléchargements du document

325