BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.3.5//EN
BEGIN:VEVENT
UID:954@lincs.fr
DTSTART;TZID=Europe/Paris:20260625T140000
DTEND;TZID=Europe/Paris:20260625T150000
DTSTAMP:20260619T115056Z
URL:https://www.lincs.fr/events/new-results-on-the-stability-of-scheduling
 -under-a-randomly-varying-channel/
SUMMARY:New results on the stability of scheduling under a randomly varying
 channel
DESCRIPTION: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.\nThe 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.\nIn 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?\nTo 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.\nThis is joint work with U. Ayesta
 and I. M. Verloop (IRIT-CNRS\, Toulouse).\nReferences: [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.
CATEGORIES:Seminars
LOCATION:Amphi 3\, 19 Place Marguerite Perey\, Palaiseau\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=19 Place Marguerite Perey\,
 Palaiseau\, France;X-APPLE-RADIUS=100;X-TITLE=Amphi 3:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20260329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR