Multi-Topology design and link weight assignment for green IP networks

In order to reduce the greenhouse effects and environmental pollution, energy saving has become important in designing next the generation networks. Shutting down the network devices carrying light loads and redirecting the traffic flows to other routes is a way to decrease network energy consumption. Since traffic demands among node pairs vary in different time periods, the energy efficient network design is to determine the optimal network topologies for them. However, in current IP network, flows are governed by shortest path routing, thus purely determining the network topology is not enough. A set of link weight metric has to be derived in company with the network topology such that the flows on the active links can meet the physical capacity constraints. Although applying adaptive network topology could save energy consumption, however, the lack of stringent synchronization among routers would cause undesired loops during the transient period of topology changes. Removing routing images inconsistent among routers to prevent loops is a critical issue in energy efficient network and this issue is still not yet considered in the green network design. In this paper, we propose a comprehensive approach that determines network topology and link metric for each time period. Traffic engineering is considered in our design such that flows going on the energy aware network are within a predetermined percentage of the link capacity such that no congestion occurs in a statistical manner. To avoid accurate synchronization among routers, we propose using RFC 4915 Multi-Topology Routing, to resolve the transient loop problem. By controlling the update sequence in MTR, there is no transient loop during the period of topology changes. We formulate an integer linear programming to jointly determine this multi-topology and link weight assignment problem. Due to its NP-hard property, we propose an efficient algorithm, termed Lagrangean Relaxation and Harmonic Series (LR&HS) - - heuristic. Numerical results demonstrate that the proposed LR&HS approach outperforms the other approaches on four benchmark networks and provides up to 35%-50% energy saving in our experimental cases.