Two Node-Disjoint Paths Routing for Energy-Efficiency and Network Reliability

摘要

Carrier grade networks are in general over-dimensioned in order to protect against network resource failures and to handle probable traffic peaks. Such network design exhibits non-negligible energy waste. As well known, during network operation, the traffic load varies remarkably over day hours. Typically, a significant amount of energy saving can be achieved by turning off redundant and underutilized resources. Ensuring a sufficient level of reliability while taking into account energy saving objective is a very challenging task. In this paper, we study the multi-commodity reliable network design for carrier Ethernet networks. Each traffic demand is routed along one working path, and a corresponding backup path computed considering dedicated protection scheme. The primary and backup path must be node-disjoint. We also assume that the links of the carrier grade networks are made of multiple physical cables called bundles. We propose an exact method based on an Integer Linear Programming (ILP) formulation for the two node-disjoint paths with energy-aware routing (TNDP-EAR) problem. The studied problem is known to be NP-hard. In order to solve it efficiently, we propose a heuristic-based algorithm called GreenTNDP. Preliminary experimental results show the effectiveness of our algorithms to solve the problem.