Energy aware network design and management

Information and communication technologies (ICT) are becoming pervasive and expanding at a very fast rate. Recent data confirms that reducing ICT impact on energy consumption and on green-house gases emissions is of paramount importance. Regarding communication networks, energy consumption is due to the consumption of all the single network devices, that has been shown to be independent from network traffic load. Furthermore, networks traffic load varies greatly during the day and rarely reaches capacity limits. Based on these observations, energy management strategies have been proposed that aim at making the consumption proportional to the load without altering the component consumption per se. This is achieved by selectively putting in a low-energy mode unused network devices based on traffic estimates. In this thesis we address the problem of jointly optimizing the design and management of a wired network with an unsplittable routing protocol from an energy aware perspective. We aim at reducing the total cost of the network, by jointly minimizing capital expenditure (capex) and operational expenditure (opex). Capex consists in network installation costs. Opex consists in energy costs for keeping the components active. Energy consumption is reduced by suitably routing the demands and switching off unused network components exploiting the time varying traffic load. Since a bad design could reduce the routing effectiveness it is important to optimize design and management simultaneously. We consider estimates of the traffic load for each time interval, modeling the standard traffic demand behavior during the day. Routing can change in different time intervals. We propose two integer linear programming formulations, a compact arc based one and an extended path based one. For the first formulation we present two families of valid inequalities. For the extended formulation, a Column Generation approach to solve its continuous relaxation is used. We also propose a heuristic based on Column Generation. The approaches are tested on a set of real life instances.