Power efficient PoP design and Auto-configuration

We consider the problem of minimizing the power consumption of Internet backbone networks by means of power aware design and auto configuration of Points of Presence (PoPs). We show that the problem of achieving a power-optimal PoP design under general traffic demands is NP-Hard. The problem is NP-Hard even when the traffic demands are correlated i.e. traffic demands across different source-destination pairs scale uniformly. We first consider the Multi-Chassis PoP Design and Auto-configuration Problem (MC-PDA) which ignores the power consumption of PoP-internal links. We propose the Port-Sorting algorithm which outputs a provably optimal PoP design. Further, we propose an autoconfiguration scheme, that activates minimal number of network components for a given traffic load. We next consider the Single-Chassis PoP Design and Auto-configuration Problem (SC-PDA) which takes the power consumption of PoP-internal links into account. Since the SC-PDA problem is NP-Hard, we propose a heuristic solution based on the Port-Sorting algorithm. Finally, we conduct extensive simulations which demonstrate that our PoP design and autoconfiguration algorithms achieve near-optimal performance over a wide range of traffic instances and significantly outperform other candidate algorithms.