A Universally Stable and Energy-Efficient Scheduling Protocol for Packet Switching Network

Energy efficiency is becoming an important issue in networks. Although some research works have been devoted to this topic, only a little attention has been paid to the stability of the network equipped with the energy conservation mechanisms. In fact, we find that the stability of networks can be undermined in the worst case if it isn´t considered with care by the energy conservation mechanism.In this paper, we propose an energy-efficient scheduling protocol which can guarantee the stability of the network in all cases. We start by building a new model which can be used to verify the stability of the network equipped with the energy conservation mechanisms. With this model, we transform the packet scheduling problem to a Job Shop Scheduling problem. For this problem, we propose a time-stamp based work-conserving scheduling algorithm - G-FSA. Compared with existing methods, this scheduling algorithm guarantees a tighter bound on the make span of the jobs. Then, we integrate G-FSA with a time partition approach to generate our energy-efficient packet scheduling protocol. It is proved that the obtained protocol can guarantee the stability of network in all cases. And its approximation ratio in terms of energy efficiency can be bounded by O((1+∈ )^α) for any ∈ > 0, where is an input parameter depending on the hardware infrastructure. Typically, 1 <; α ≤ 3.