Some new results about an old model: The M/G/1 queue


Stochastic networks are an integral part of everyone’s daily life. For example, traffic jams, waiting lines in a supermarket, communication systems and etc. are all examples of such networks. One classic model in this direction is the  M/G/1 queue, i.e., assume that there is a single server with customers who arrive according to a Poisson process. There is an incredible amount of existing

about this queue, but still there are some open questions that deserve answers: 1. Externalities: Assume that the service discipline is first-comes, first-served and at time t = 0, the existing workload in the system is v ≥ 0 minutes. What would be the impact (on the waiting times of the other customers) of an additional customer who arrives at time t = 0 and requests x > 0 minutes of service? It turns out that the aggregate impact yields a stochastic process which we call the externalities process. We discover its properties. Furthermore, we give a similar analysis also for the analogue

process when the service discipline is last-comes, first-served preemptiveresume. 2. Moments of functionals of the M/G/1 workload: There are many functionals of the workload that appear in literature, e.g., the length of a busy period, the number of customers who arrive during a busy period, the total waiting-time of customers who arrive during a busy period, the area

below the workload process during a busy period. In this work, we observe that all of these functionals are special cases of a random measure which is determined by the workload process. Then, this fact is exploited in order to derive a general recursive formula for the high-order joint moments of these functionals. Furthermore, there is an interesting relation to certain

Poisson’s equation in a corresponding Markov process. 

Supervisors Michel Mandjes (UvA)

Royi Jacobovic


University of Amsterdam (UvA)