Next: Hopfield model for Neural Up: Transient behaviour of Large Previous: Stability and Euler limits

## Queueing networks

In [6] we also study more applied problems, mainly in the area of Queueing Networks. This means that we study the issue of cyclicity/ acyclicity, scattering probabilities and the computation of the expected drifts to determine the Euler paths.

The following example illustrates that these are non-trivial issues in queueing networks indeed. It is a simple queueing network (with priorities) exhibiting cyclicity and scattering. Customers have 4 jobs of different length, that have to be done in consecutive order. The 1st and 4th jobs have to be done at station 1 and the 2d and 3d at station 2; moreover, type 4 and type 2 jobs have priority over type 1 and type 3 jobs. By calculating the drifts and choosing appropriate job lengths, the queues of type 2 and type 4 jobs ``compete'' for blowing up, provided the system start with an abundance of type 1 and type 3 jobs.

This queueing network was first constructed by Meyn and Down and it is also one of the counterexamples from the literature, discovered only recently (cf. [2]), to the conjecture by Dobrushin that the traffic intensity being smaller than 1 is necessary and sufficient for stability.

In modern queueing theory so-called fluid models play an important role. They are in fact equal to Euler limits, but they are constructed differently. First the fluid equations corresponding to some given type of queueing network are derived: for each given subset of ``full'' nodes, these yield the net flow into or out of each such node. This net flow corresponds to the drifts mentioned above. Secondly, convergence to a solution to the fluid equations is proved. In this case, non-unicity of solutions to the fluid equations corresponds to scattering. However, this phenomenon is not yet very well understood in the existing queueing literature.

In [6] we have derived these fluid equations for several forms of polling models, priority queues and neural networks, thus yielding the required drifts. We show that their Euler limits are acyclic under certain conditions. For example the priority queueing network is acyclic if priorities are conserved and non-increasing. We further investigate general conditions on the network, such that the drifts can be calculated from a finite linear system.

The calculation of scattering probabilities is still an open problem, which is related to the calculation of quasi-stationary distributions.

Next: Hopfield model for Neural Up: Transient behaviour of Large Previous: Stability and Euler limits

J.H.M.Dassen
Fri Mar 20 16:01:06 MET 1998