One of the classical problems in queuing theory is to schedule customers/jobs in an optimal way. These problems are known as the scheduling problems. They arise in a wide variety of applications, in particular, whenever there are different customer classes present competing for the same resources. In a recent work “Ergodic control of multi-class M/M/N+M queues in the Halfin-Whitt regime”, Ari Arapostathis, Anup Biswas and Guodong Pang solved an ergodic control problem for multi-class many server queuing networks. The optimal solution of the queuing control problem can be approximated by that of the corresponding ergodic diffusion control problem in the limit. The proof technique introduces a new method of spatial truncation for the diffusion control problem.
In a paper entitled Metastability of Queuing Networks with Mobile Servers, A. Rybko, S. Shlosman, A. Vladimorov and F. Baccelli study symmetric queuing networks with moving servers and FIFO service discipline. The mean-field limit dynamics demonstrates unexpected behavior which is attributed to the meta-stability phenomenon. Large enough finite symmetric networks on regular graphs are proved to be transient for arbitrarily small inflow rates. However, the limiting non-linear Markov process possesses at least two stationary solutions. The mean-field analysis is based on the Non Linear Markov Process developed for this type of queuing networks in Queuing Networks with Varying Topology – A Mean-Field Approach.
With Pranav Madadi, F. Baccelli, and G. de Veciana analyzed the temporal variations in the Shannon rate experienced by a user moving along a straight line in a cellular network represented by a Poisson-Voronoi tessellation. We consider a network that is shared by static users distributed as a Poisson point process and analyzed the time series of the final shared rate and the number of users sharing the network. The first paper On Shared Rate Time Series for Mobile Users in Poisson Networks was focused on the noise limited case. The ongoing research is focused on the general case, with both interference and thermal noise taken into account.
Consider a queue where the server is the Euclidean space, the customers are random closed sets (RACS) of the Euclidean space. These RACS arrive according to a Poisson rain and each of them has a random service time (in the case of hail falling on the Euclidean plane, this is the height of the hailstone, whereas the RACS is its footprint). The Euclidean space serves customers at speed 1. The service discipline is a hard exclusion rule: no two intersecting RACS can be served simultaneously and service is in the First In First Out order (only the hailstones in contact with the ground melt at speed 1, whereas the other ones are queued; a tagged RACS waits until all RACS arrived before it and intersecting it have fully melted before starting its own melting). We prove that this queue is stable for a sufficiently small arrival intensity, provided the typical diameter of the RACS and the typical service time have finite exponential moments.
In Shape Theorems For Poisson Hail on a Bivariate Ground, H. Chang, S. Foss and F. Baccelli have extended this Poisson Hail model to the situation where the service speed is either zero or infinity at each point of the Euclidean space. Tools pertaining to sub-additive ergodic theory are used to establish shape theorems for the growth of the ice-heap under light tail assumptions on the hailstone characteristics. The asymptotic shape depends on the statistics of the hailstones, the intensity of the underlying Poisson point process and on the geometrical properties of the zero speed set.
Spatial point processes involving birth and death dynamics are ubiquitous in networks. Such dynamics are particularly important in peer-to-peer networks and in wireless networks. In the paper “Mutual Service Processes in R^d, Existence and Ergodicity”, Fabien Mathieu (Bell Laboratories), Ilkka Norros (VTT) and François Baccelli proposed a way to analyze the long term behavior of such dynamics on Euclidean spaces using coupling techniques. This line of though is continued by Mayank Manjrekar on other classes of processes like hard core spatial birth and death processes.