Minimizing Routing Energy Consumption: from Theoretical to Practical Results

Several studies exhibit that the traffic load of the routers only has a small influence on their energy consumption. Hence, the power consumption in networks is strongly related to the number of active network elements, such as interfaces, line cards, base chassis,... The goal thus is to find a routing that minimizes the (weighted) number of active network elements used when routing. In this paper, we consider a simplified architecture where a connection between two routers is represented as a link joining two network interfaces. When a connection is not used, both network interfaces can be turned off. Therefore, in order to reduce power consumption, the goal is to find the routing that minimizes the number of used links while satisfying all the demands. We first define formally the problem and we model it as an integer linear program. Then, we prove that this problem is not in APX, that is there is no polynomial-time constant-factor approximation algorithm. We propose a heuristic algorithm for this problem and we also prove some negative results about basic greedy and probabilistic algorithms. Thus we present a study on specific topologies, such as trees, grids and complete graphs, that provide bounds and results useful for real topologies. We then exhibit the gain in terms of number of network interfaces (leading to a global reduction of approximately 33 MWh for a medium-sized backbone network) for a set of existing network topologies: we see that for almost all topologies more than one third of the network interfaces can be spared for usual ranges of operation. Finally, we discuss the impact of energy efficient routing on the stretch factor and on fault tolerance.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