On the geometry of the stability regions of randomlymodulated queuing systems

We study the maximum stability region (MSR) of a scheduling problem involving multiple queues, a single server, and randomly modulated dynamics. In the case where the modulation process is autonomous, takes values in a finite set, and is in stationary regime, we characterise the stability region as a Minkowski sum of deGua simplices, structures known as cephoids in the convex geometry literature. Beyond endowing the stability region with a rich mathematical structure, this apparently novel connection enables an explicit description of the MSR in the 2-queue case, and provides a simple iterative scheme to obtain its minimal Hdescription in the general case.