On the Stability Region of Maximum Weighted Matching Server Allocation Policy

Abstract

In this paper, we study the stability region of a multi-server queueing system for which Maximum Weighted Matching (MWM) server allocation policy is known to be throughput-optimal. We derive a linear algebraic characterization of the system stability region polytope (or equivalently MWM stability region) by means of a finite set of linear inequalities. Such a characterization of the stability region is useful for solving network stochastic optimization problems and also evaluating the performance of MWM server allocation policy, e.g., deriving explicit performance bounds for the average queueing delay and flow measurement metrics. Furthermore, using the linear algebraic form of the stability region, we derive an upper bound for the average queueing delay of MWM policy.

Keywords:

• Stability region
• maximum weighted matching
• server allocation

Notes

1 denotes the interior of a set which is defined as the union of all its open subsets.