Competitive Power Down Methods in Green Computing

For the power-down problem one considers a device which has states OFF, ON, and a number of intermediate states. The state of the device can be switched at any time. In the OFF state the device consumes zero energy and in the ON state it works at its full power consumption. The intermediate states consume only some fraction of energy proportional to the usage time but switching back to the ON state has has different constant setup cost depending on the current state. Requests for service (i.e. for when the device has to be in the ON state) are not known in advance, thus power-down problems are studied in the framework of online algorithms, where a system has to react without knowledge of future requests. Online algorithms are analyzed in terms of competitiveness, a measure of performance that compares the solution obtained online with the optimal online solution for the same problem, where the lowest possible competitiveness is best. Power-down mechanisms are widely used to save energy and were one of the first problems to be studied in green computing. They can be used to optimize energy usage in cloud computing, or for scheduling energy supply in the smart grid. However, many approaches are simplistic, and do not work well in practice nor do they have a good theoretical underpinning. In fact, it is surprising that only very few algorithmic techniques exist. This thesis widens the algorithmic base for such problems in a number of ways. We study systems with few states which are especially relevant in real wold applications. We give exact ratios for systems with three and five states. We then introduce a new technique, called "decrease and reset", where the algorithm automatically attunes itself to the frequency of requests, and gives a better performance for real world inputs than currently existing algorithms. We further refine this approach by a budget-based methods which keeps a tally of gains and losses as requests are processed. We also analyze systems with infinite states and devise several strategies to transition between states. The thesis gives results both in terms of theoretical analysis as well as a result of extensive simulation.