Location: Auditorium, ECE MP Building
Title: DETERMINISTIC HEAVY TRAFFIC LIMITS IN QUEUE-BASED RANDOM ACCESS
Speaker: Eyal Castiel, ISAE – Supaero and Toulouse Mathematical Institute
Date: Friday, 26 April 2019
Time: (3:45 Tea) 4:00 – 5:00 PM
Venue: MP building seminar hall, ECE
Abstract: In this talk, we study an adaptive queue-based CSMA scheduling algorithm on a complete interference graph, which can be seen as a polling system with non-zero switch-over time. The idleness induced by the decentralization of decisions entails non-standard heavy traffic behavior: when queue lengths are of order N we need to scale time by N^a+1 for some 0 < a < 1 and the limit is deterministic. In contrast, the standard critical behavior corresponds to a time scale N^2 and the limiting process is typically a reflected Brownian motion. To prove this result we develop a new method to establish a stochastic averaging principle: the schedule evolves “much faster” than queue lengths and the proportion of the time a schedule is chosen is close (in an averaged way) to the invariant measure of the dynamic of the schedule (which depends on queue lengths). This method uses tools from functional analysis, in particular the log-Sobolev inequality. We then give a closed formula for a fluid limit and a heavy traffic approximation by proving a state space collapse for the queue lengths (they live in fact close to a a one-dimensional manifold). We will present the procedure on a complete interference graph with critical arrival rates and deactivation rates polynomial in the queue length.
Bio: Eyal Castiel is with ISAE-Supaero and Toulouse Institute of Mathematics. His research is focused on the analysis of stochastic model, mainly queueing systems. He obtained a bachelor in mathematics and social science at Sorbonne university (Paris) and a Master of Mathematics (Probability and stochastic models) at Université Pierre and Marie Curie (Paris) in 2016.
ALL ARE WELCOME