We define a discrete-time queueing network where there are restrictions on which queues can be served simultaneously. We give a policy for serving queues which is stable whenever it is possible to stabilize the queueing network.
- Let index the set of queues. We let be the set of schedules. Each is a vector where indicates that queue will be served under schedule and indicates that the queue will not be served by schedule . We let be the convex combination of schedules in .
- We assume that we can always choose not to serve a queue. That is we can always set a component zero: . This avoids the issue of accidentally serving an empty queue and ensures .
- We let be the number of arrivals occurring at each queue at time . Also, we define .
- We let be the size of each queue at time , and use the shorthand .
- We define the MaxWeight scheduling policy to be the policy that solves the optimization
- We could define the above optimization as , i.e. maximizing over convex set instead of the discrete set . This is because any linear program has a solution at an extreme point which must, for these problems, be a subset of the set .
- We assume our network is a single-hop network: once a job is served at its queue it leaves the network.
The following result states that provided the expected arrivals are within the interior of the set of schedules then we can expect the long run queue size to be bounded.
Theorem: If there exists such that for all , and then 1 there exists constants and such that
Proof: Note the crux of this argument is that for all queue sizes , is by some margin strictly less than the MaxWeight choice . Given above, we aim to use , the biggest such that for all time. This can be defined as the biggest such that for all i.e. so the distance of the smallest component to the boundary is maximized. Given this optimization description we observe the following
From this observation, we see one way that we can use to bound the gap between and .
Summing the above expression from , we gain the expression
Rearranging, dividing by , and letting , we obtain the desired expression.
- The above schedule, result, and proof is a special case of the Blackwellâs Approachability Theorem. Here wish to approach the set and our Blackwell condition [Theorem [Blackwell:Blackwell].2] states that for every there exist a such that component-wise.
We now study as a Markov chain. To do this, we assume are independent identically distributed random variables with mean . The result below proves that this Markov chain is transient whenever . Thus is the largest open region for which our Markov chain can be positive recurrent. We show that this Markov chain is positive recurrent for .
- As just described, if it is possible to find a policy to stabilize the queueing network then the MaxWeight scheduler will also stabilize the network. This property is sometimes called maximum stable.
Proposition: Given are iid random variables with mean and finite variance.
If then is a positive recurrent Markov chain.
If then is a transient Markov chain.
Proof: If are iid then is a function of and independent random variable and so defines a discrete-time Markov chain. First suppose . The above Theorem holds. If the Markov chain were not positive recurrent then for all . In particular, this would hold for all such that which would then imply would not hold. Thus by this contradiction, this Markov chain is positive recurrent.
Now suppose . As is convex, there exists a hyper-plane separating and , i.e. there exists a and such that
We define and , the average schedule and arrivals by time . Now
In the second equality, we use the Strong Law of Large Numbers on . In the final inequality, we use our separating hyper-plane . Thus as , our Markov chain visits each set of states finitely many times, for each . So, our Markov chain is transient.
Other maximum stable schedulers exist. For instance, we could estimate and schedule. That is record and chooses a random schedule with mean where is maximal so that . These â and hence â would converge to give a stable queueing network. However, we needed to record the arrival history.
- The MaxWeight scheduler has the advantage that we do not need to record any historical information beyond the queueing networks state in order to construct a schedule. Such policies are often called on-line policies.
- It can be computationally expensive to calculate a solution to at each time-step. So, despite the desirable properties that we have just proven, the MaxWeight policy can be impractical.
- Here is the vector whose components are all ones.â©