Efficient Energy-Aware Routing With Redundancy Elimination

Energy-aware routing is a promising technique for reducing energy consumption in future networks. Under this scheme, traffic loads are aggregated over a subset of the network links, allowing other links to be turned OFF to save energy. Since the capacity of links is the main limiting constraint in this problem, to further improve energy saving, the idea of using redundancy elimination (RE) in energy-aware routing has been proposed. As performing RE in routers consumes some energy, it should be specified, which routers should perform RE and which links should be deactivated so that the total energy consumption of the network is minimized. As a result, the problem of energy-aware routing with redundancy elimination, which is known to be NP-hard, arises. In this paper, we first model the problem as a mixed integer linear program (MILP). Since this problem is NP-hard, we propose an efficient heuristic solution. For this purpose, we apply Lagrangian relaxation to the problem and then prove that the obtained formulation is totally unimodular. Under this property, we can relax the integer variables to efficiently determine the solution in polynomial time. Simulation results show the advantages of our proposed heuristic solution over previous ones in terms of approximately twice the energy saving, as well as a lower number of active RE-routers. Furthermore, we show that our method can be applied to the generic energy-aware routing problem (i.e., without RE) as well.