  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.
