Reliable Green Routing Using Two Disjoint Paths

Abstract

Network robustness and throughput can be improved by routing each demand d via two disjoint paths (2DP). However, 2DP routing increases energy usage while providing lower linkutilization and redundancy. In this paper, we address an NP-complete problem, called 2DP-EAR, that aims to switch off redundant nodes and links while guaranteeing two constraints:traffic demands must be afforded 2DP, and maximum link utilization. We design an efficient heuristic, called 2DP by Nodes First (2DP-NF). We have extensively evaluated the performance of 2DP-NF on both real and/or synthetic topologies and traffic demands. As compared to using Shortest Path routing, on the GÉANT network, 2DP-NF can save around 20% energy by switching off links only with negligible effects on path delays and link utilization, even for MLU below 30%. Furthermore, 2DP-NF can obtain 39.7% power savings by switching off both nodes and links on the GÉANT network.