# Multiserver Queues: Are two moments enough?

#### Authors: Matthew Dickson, Ifan Johnston, Jesse Pritchard, David Woodford.

#### Supervisors: Sayan Banerjee, Wilfrid S. Kendall

**Introduction**

Queues have become common place both in physical form made up of people and within networking and communications systems. In most cases these queues are of a first-come-first-served nature and often have multiple servers. For people who are designing these queueing systems it is useful to have an understanding of the distribution of the waiting time and in particular to know what the expected waiting time will be so decisions can be made, for example, on whether extra resourcing of the queue is needed.

## Deterministic arrivals

- has deterministic inter-arrival times and Markovian job-size. By the time mesh we will mean the times at which jobs from this queue arrive.
- has Geometric inter-arrival times (disallowing zero inter-arrival) with parameter over a mesh of size . That is, at each time a job arrives with probability independently (and jobs arrive at no other times). Job sizes are exponentially distributied with mean .
- has deterministic arrivals on the mesh and jobs with constant size .
- has exponentially distributed inter-arrival times with parameter and exponentially distributed job-sizes with parameter .
- We will denote by the traffic intensity given by , where is the mean inter-arrival time, and is the mean job-size.

In [1] , they look at the set of waiting times with different job-size distributions (but with fixed first two moments) and investigate the size of this set. That is, they aimed to get upper (and lower) bounds on the infimum (resp. supremum) of these sets.

The bounds that they found are stated in the following theorems

#### Theorem:

For and any finite#### Theorem:

For and any finiteThe two cases and corrspond to light traffic and heavy traffic respectively.

More details can be found here

## Asymptotics of M/M/K queues

As we have seen, the MMK queue has a central role in many of the discussions relating to more general queues, therefore it is useful to gain a better insight into its behaviour. We specifically look at the behaviour of as we increase the number of servers. In order to look at this behavour as we hold the traffic intensity constant by increasing only the arrival rate of the customers.

It is known, see [2], that the stationary distribution of the M/M/K queue is given by

where the normalisation is given by

### Tight bounds in the light traffic case

We have proven tight bounds on for . This bound is given by

for all fixed , as . We also conjecture that this tight bound holds for all , but have not been able to prove this yet.

A graph that encourages this conjecture is seen below.

More details can be found here

#### References

[1] Gupta, Varun, et al. "On the inapproximability of M/G/K: why two moments of job size distribution are not enough." Queueing Systems 64.1 (2010): 5-48.

[2] Adan, Ivo, and Jacques Resing. "Queueing theory." (2002).

#### Acknowledgements

We acknowledge the funding body EPSRC and the support from MASDOC CDT.