DETERMINISTIC HEAVY TRAFFIC LIMITS IN QUEUE-BASED RANDOM ACCESS

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