  Energy saving is becoming an important issue in the design and use of
computer networks. In this work we propose a problem that considers the use of
rate adaptation as the energy saving strategy in networks. The problem is
modeled as an integral demand-routing problem in a network with discrete cost
functions at the links. The discreteness of the cost function comes from the
different states (bandwidths) at which links can operate and, in particular,
from the energy consumed at each state. This in its turn leads to the
non-convexity of the cost function, and thus adds complexity to solve this
problem. We formulate this routing problem as an integer program, and we show
that the general case of this problem is NP-hard, and even hard to approximate.
For the special case when the step ratio of the cost function is bounded, we
show that effective approximations can be obtained. Our main algorithm executes
two processes in sequence: relaxation and rounding. The relaxation process
eliminates the non-convexity of the cost function, so that the problem is
transformed into a fractional convex program solvable in polynomial time. After
that, a randomized rounding process is used to get a feasible solution for the
original problem. This algorithm provides a constant approximation ratio for
uniform demands and an approximation ratio of $O(\log^{\beta-1} d)$ for
non-uniform demands, where $\beta$ is a constant and $d$ is the largest demand.
