MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEMinimizing Routing Energy Consumption: from Theoretical to Practical Results
par Joanna Moulierac
Several studies exhibit that the traffi c load of the routers only has a small in fluence
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 simpli ed 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 fi nd the routing that minimizes the
number of used links while satisfying all the demands. We fi rst defi ne 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 speci fic 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 e fficient routing on the stretch factor and on fault tolerance.
Page des séminaires
| 
