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 paper On Shared Rate Time Series for Mobile Users in Poisson Networks was focused on the noise limited case.
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.
In this paper, Abishek Sankararaman and François Baccelli introduce a new form of spatial dynamics motivated by ad-hoc wireless networks. They study a birth death process where particles arrive in space as a Poisson process in space and time, and depart the system on completion of file transfer. The instantaneous rate of file transfer of any link is given by the Shannon formula of treating interference as noise. As the instantaneous interference seen by a link is dependent on the configuration of links present, this dynamics is an example of one where dynamics shapes geometry and in turn the geometry shapes the dynamics. In this paper, the authors establish a sharp phase-transition for stability of such dynamics. Moreover, whenever such dynamics is stable, they prove that the steady state is a clustered point process. Through simulations, they also argue that such dynamics cannot be simplified to any form of non-spatial queuing type dynamics. Lately, this paper with Sergey Foss extended the dynamics on grids to show a similar stability phase-transition in the case of infinite network, i.e. in an infinite grid.