The problem we study has a simple informal description. There are K queues with static arrival rates, and a single server with static capacity. In addition, the channel gain of each queue varies randomly over time. A scheduler has to dynamically split the capacity of the server among the K queues, taking decisions based on the observed channel gains (and possibly also on the observation of the queue lengths). The meta-question is how to schedule efficiently.
The performance measure we focus on is stability (positive recurrence). A seminal reference for us is [1], which studies the ON/OFF case, where each queue’s channel gain switches between 0 (the OFF state) and a positive value (the ON state). For this case, [1] gives an explicit description of the maximum stability region (MSR) – the set of admissible arrival-rate vectors, i.e. those that some scheduling strategy can stabilise – through a family of simple load inequalities. The paper [2] allows more general channel states, but for that setting a simple description of the MSR is still missing. Both [1] and [2] find maximum-stable policies that heavily rely on observing the queue lengths.
In our work, we shed light on the following questions: (i) How can one decide efficiently whether an arrival-rate vector is admissible? (ii) When it is admissible, how can one design stable policies that are agnostic to the queue lengths? (iii) On a more theoretical side, what are the geometric properties of the MSR?
To answer (i) and (ii), we establish a new connection with network flows with gains, a generalisation of the classical network flows founded by Ford and Fulkerson: existence of a maximum feasible flow decides admissibility, and such a flow yields a stable policy that is agnostic to the queue lengths. To answer (iii), we connect the MSR to a structure called a cephoid, studied in recent years mainly by the convex geometers Rosenmüller and Pallaschke; through this identification, we can borrow their results to describe the MSR in our setting. Finally, for the ON/OFF case, we give a new proof of the explicit condition of Tassiulas and Ephremides [1], based on the max-flow/min-cut theorem for classical network flows, which gives independent insight into the problem.
This is joint work with U. Ayesta and I. M. Verloop (IRIT-CNRS, Toulouse).
References: [1] Tassiulas and Ephremides. Dynamic server allocation to parallel queues with randomly varying connectivity. IEEE Trans. Inf. Theory, 1993. [2] Shakkottai and Stolyar. Scheduling for multiple flows sharing a time-varying channel: the exponential rule. AMS Transl. Ser. 2, vol. 207, 2002.