On the stability of scheduling under a randomly varying channel: insights from generalised network flows and cephoids
Abstract
We study the problem of scheduling a single server among K ∈ ℕ queues in a random environment of M ∈ ℕ time-varying channels. Our framework is essentially that of Shakkottai and Stolyar (2002). We exhibit two distinct mathematical identifications of this problem, which yield complementary insight. The first identification is with a generalised network flow, an object studied in combinatorial optimisation. It yields a new characterisation of stability in terms of the existence of a generalised flow of maximum value and, via Végh (2017), strongly polynomial algorithms both to test the stability of a given arrival-rate vector and to compute a stabilising policy that is agnostic to queue lengths. In the ON/OFF case, first studied in Tassiulas and Ephremides (1993), this identification yields, through the max-flow/min-cut theorem, an independent proof of the explicit characterisation of the maximum stability region obtained there. The second identification is with a cephoid, a structure studied in convex geometry, mainly by Rosenmüller and Pallaschke, whose machinery it puts at our disposal. Under a non-degeneracy assumption on the channel gains, their results apply directly and yield an iterative procedure describing the geometry of the stability region precisely, providing a characterisation of the region by a minimal family of load inequalities as a very particular consequence. For K=2, these load inequalities become explicit in the parameters of the model, and we build on them to associate with any stabilisable arrival-rate vector a stabilising, queue-length-agnostic policy given in closed form.
Related
- Stopping models closed under pgf composition, and the stability of randomly stopped model extensions
- Dynamic subscales and unconditional semi-discrete stability for non-residual VMS approximations of generalised Newtonian flows
- Exponential Mixing for the Randomly Forced NLS Equation
- Mixing time of the lazy and simple random walk on a randomly twisted hypercube
- A Central Limit Theorem for Coprime Pair Counts in Randomly Translated Disks
BibTeX
@misc{sopranoloto2026stability,
title = {{On the stability of scheduling under a randomly varying channel: insights from generalised network flows and cephoids}},
author = {Nahuel Soprano-Loto and Urtzi Ayesta and Ina Maria Maaike Verloop},
howpublished = {HAL},
year = {2026},
month = aug,
url = {https://hal.science/hal-05733315v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the stability of scheduling under a randomly varying channel: insights from generalised network flows and cephoids
AU - Nahuel Soprano-Loto
AU - Urtzi Ayesta
AU - Ina Maria Maaike Verloop
PY - 2026
DA - 2026/08/31
PB - HAL
UR - https://hal.science/hal-05733315v1
AB - We study the problem of scheduling a single server among K ∈ ℕ queues in a random environment of M ∈ ℕ time-varying channels. Our framework is essentially that of Shakkottai and Stolyar (2002). We exhibit two distinct mathematical identifications of this problem, which yield complementary insight. The first identification is with a generalised network flow, an object studied in combinatorial optimisation. It yields a new characterisation of stability in terms of the existence of a generalised flow of maximum value and, via Végh (2017), strongly polynomial algorithms both to test the stability of a given arrival-rate vector and to compute a stabilising policy that is agnostic to queue lengths. In the ON/OFF case, first studied in Tassiulas and Ephremides (1993), this identification yields, through the max-flow/min-cut theorem, an independent proof of the explicit characterisation of the maximum stability region obtained there. The second identification is with a cephoid, a structure studied in convex geometry, mainly by Rosenmüller and Pallaschke, whose machinery it puts at our disposal. Under a non-degeneracy assumption on the channel gains, their results apply directly and yield an iterative procedure describing the geometry of the stability region precisely, providing a characterisation of the region by a minimal family of load inequalities as a very particular consequence. For K=2, these load inequalities become explicit in the parameters of the model, and we build on them to associate with any stabilisable arrival-rate vector a stabilising, queue-length-agnostic policy given in closed form.
ER -