Rate-Adaptive Scheduling Policies for Network Stability and Energy Efficiency

A key problem in the control of packet-switched data networks is to schedule the data so that the queue sizes remain bounded over time. Scheduling policies have been developed in a number of different models that ensure network stability as long as no queue is inherently overloaded. However, this literature typically assumes that each server runs at a fixed maximum rate. Although this is optimal for clearing queue backlogs as fast as possible, it may be suboptimal in terms of energy consumption. Indeed, a lightly loaded server could operate at a lower rate, at least temporarily, to save energy. Within an energy-aware framework, a natural question is how stability and other performance measures such as delay are affected by the reduced processing rate of the servers. In this paper, we demonstrate the following results toward answering that question. Starting with the simplest case of a single server in isolation, we consider two types of rate adaptation policies that exhibit a tradeoff between queue size and energy usage. We also present a lower bound on the best such tradeoff that can possibly be achieved. Next, we study a general network environment and investigate the connectionless model for which connection paths can rapidly change over time. We propose a combination of the above rate adaptation policies with the standard Farthest-to-Go scheduling policy. This approach provides stability in the network setting while using an amount of energy that is within a bounded factor of the optimum.