Minimizing Routing Energy Consumption: from Theoretical to Practical Results

Frédéric Giroire 1 Dorian Mazauric 1, 2 Joanna Moulierac 1 Brice Onfroy 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
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : L'économie d'énergie dans les réseaux peut être accomplie en utilisant des techniques efficaces de routage ou de conception de réseaux. Dans ce papier, nous étudions une architecture simplifiée de réseaux dans laquelle lorsque deux routeurs sont reliés par un lien, les deux équipements extrémités de ce lien doivent être allumés. Chaque équipement ayant une consommation dépendant plutôt de son activation que de la quantité de traffic, notre objectif est de minimiser le nombre total d'équipements réseaux activés. Autrement dit, ce problème revient à effectuer un routage des demandes en minimisant le nombre d'arêtes dans la topologie. Nous proposons un programme linéaire pour résoudre ce problème et montrons des bornes simples sur des topologies particulières telles que la grille, l'arbre ou le graphe complet. Nous montrons des résultats d'inapproximabilité de ce problème, même si l'on considère des instances particulières. Nous proposons ensuite une heuristique dont nous évaluons les performances à l'aide de simulations sur des topologies réelles et sur la grille. Nous étudions ensuite l'impact de ces solutions efficaces en énergie sur la tolérance aux pannes et sur la longueur moyenne des routes. Finalement, nous proposons des structures de routage qui garantissent deux chemins disjoints par demande, ainsi qu'une limite sur la longueur des chemins.
Type de document :
Rapport
[Research Report] RR-7234, INRIA. 2010, pp.34
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00464318
Contributeur : Joanna Moulierac <>
Soumis le : jeudi 10 février 2011 - 14:21:58
Dernière modification le : jeudi 11 janvier 2018 - 16:58:57

Fichier

RR-7234.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00464318, version 3

Collections

Citation

Frédéric Giroire, Dorian Mazauric, Joanna Moulierac, Brice Onfroy. Minimizing Routing Energy Consumption: from Theoretical to Practical Results. [Research Report] RR-7234, INRIA. 2010, pp.34. 〈inria-00464318v3〉

Partager

Métriques

Consultations de la notice

423

Téléchargements de fichiers

286