Towards fast rerouting-based energy efficient routing

The inefficiency of energy usage on the Internet has become a critical problem with its rapid growth, as all network devices operate at full capacity in spite of the real traffic load. Existing studies try to develop energy efficient routings by aggregating traffic and switching underutilized devices into sleep mode. However, most existing approaches do not address the problem of routing convergence well. Since traffic changes frequently in a network, routing convergence may be triggered frequently for an energy efficient routing, which may induce routing loops and black holes, resulting in severe packet loss. In this paper, we present a fast rerouting-based (FRR-based) energy efficient routing scheme, namely GreenFRR, which leverages the technique of fast rerouting to reduce the convergence time. We first study typical fast rerouting techniques and address the challenge of guaranteeing loop-free routing. Then, we formalize the FRR-based energy efficient routing problem and prove that the problem is NP-hard. In order to solve this problem, we design heuristic algorithms to maximize the number of sleeping links. In particular, we consider link utilization ratio and path stretch in our algorithms. We evaluate our scheme by simulations on real and synthetic topologies with real and synthetic traffic traces. The results show that the power consumed by line cards achieves a saving of 40% and the convergence time can be reduced by 95%.