An efficient heuristic for restorable energy aware routing in networks with bundled links

Energy aware routing via rerouting traffic or traffic aggregating has received wide attention in the last decade. It is important and challenging to take network reliability into consideration to enhance the resilience to failures at the same time. In this paper, we aim to minimize energy expenditure while ensuring network reliability by restoration. As each request has an active path and disjoint backup path for restoration, the backup path can be used if the active path fails. To this end, we first propose the problem called Restorable Energy Aware Routing Problem in networks with bundled links (REAR-BL) when backup sharing is not allowed. We form a linear integer model to minimize the number of powered-on cables of links while putting idle cables to sleep under constraints of restoration and maximum link utilization. Since REAR-BL is Np-hard, we design a fast heuristic to solve it based on Suurballe algorithm and the analysis of a lower bound and an upper bound of the optimal solution. We evaluate our heuristic through extensive simulations on real and synthetic topologies and obtain considerable energy savings with less time when compared to CPLEX solutions and upper and lower bounds.