|
Abstract:
The size of many of today's stochastic networks prohibits optimal scheduling due to high computational demands, even when optimality merely requires that the network be stable. This motivates the search for simple scheduling algorithms for which throughput guarantees can be
given. We present such a scheduling algorithm.
Our starting point is a set of 'local' scheduling policies, for instance at each station, which can be shown to achieve a given throughput using a quadratic Lyapunov function. We devise a simple policy for the whole network and show that it achieves the same throughput. Informally one can think of our result saying that 'local' stability yields 'global' stability under our policy. The proof relies on the construction of a novel quadratic Lyapunov function for the whole network using the local quadratic Lyapunov functions. Our methodology is applicable to multiclass networks, parallel server networks, networks of switches, and special wireless networks.
Joint work with Jinwoo Shin (ARC, Georgia Tech).
|
|
