Explicit Characterization of Stability Region for Stationary Multi-Queue Multi-Server Systems

摘要

We derive an explicit characterization of the stability region of stationary multi-queue multi-server (MQMS) queueing system by means of a finite set of linear inequalities. More specifically, we explicitly determine the coefficients of the linear inequalities describing the facet-defining hyperplanes of the stability region polytope. Such a characterization is useful for performance evaluation of certain scheduling algorithms such as maximum weight (MW) policy. Our results can be used for studying the asymptotic behavior of the MW policy and computing bounds for the average queueing delay, as well as limiting moments of the queue sizes in heavy-traffic regime. Furthermore, it may be directly applied as the constraint set of network stochastic optimization problems to provide an offline computational solution for such problems. Finally, we use our methodology to characterize the stability region of a fluid model MQMS system which is described by an infinite number of linear inequalities. For such a model, we present an example and show that depending on the channel distribution, the stability region can be instead characterized by a finite set of non-linear inequalities.