On the Complexity of Power Minimization Schemes in Data Center Networks

In this paper, we consider migration of virtual machines in a data center to minimize network power consumption. Network power is consumed when switches are turned on, and conserved when they are turned off; the optimization problem then is to site virtual machines within the data center to achieve connectivity and desired bandwidth while turning on as few switches as possible. Depending upon specifics of the permissible optimization, and topology considerations within the data center, this optimization problem can be easy, or hard. We fully taxonomize the suite of optimization problems in this general space, showing that the most complex problem (placement and routing of virtual machines in a topologically-rich data center network) is NP- hard. We offer a placement technique based on a classic VLSI placement algorithm, and demonstrate efficacy on a trace set derived from a production data center.