Loss network

In queueing theory, a loss network is a stochastic model of a telephony network in which calls are routed around a network between nodes. The links between nodes have finite capacity and thus some calls arriving may find no route available to their destination. These calls are lost from the network, hence the name loss networks.[1]

The loss network was first studied by Erlang for a single telephone link.[2] Frank Kelly was awarded the Frederick W. Lanchester Prize[3] for his 1991 paper Loss Networks[4][5] where he demonstrated the behaviour of loss networks can exhibit hysteresis.

Model

Fixed routing

Consider a network with J links labelled 1, 2, …, J and that each link j has C_j circuits. Let R be the set of all possible routes in the network (combinations of links a call might use) and each route r, write A_jr for the number of circuits route r uses on link j (A is therefore a J x |R| matrix). Consider the case where all elements of A are either 0 or 1 and for each route r calls requiring use of the route arrive according to a Poisson process of rate v_r. When a call arrives if there is sufficient capacity remaining on all the required links the call is accepted and occupies the network for an exponentially distributed length of time with parameter 1. If there is insufficient capacity on any individual link to accept the call it is rejected (lost) from the network.[5]

Write n_r(t) for the number of calls on route r in progress at time t, n(t) for the vector (n_r(t) : r in R) and C = (C₁, C₂, ... , C_J). Then the continuous-time Markov process n(t) has unique stationary distribution[5]

${\displaystyle \pi (n)=G(C)^{-1}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}{\text{ for }}n\in S(C)}$

where

${\displaystyle S(C)=\{n\in \mathbb {Z} _{+}^{R}:An\leq C\}}$

and

${\displaystyle G(C)=\left(\sum _{n\in S(C)}\prod _{r\in R}{\frac {v_{r}^{n_{r}}}{n_{r}!}}\right).}$

From this result loss probabilities for calls arriving on different routes can be calculated by summing over appropriate states.

Computing loss probabilities

There are common algorithms for computing the loss probabilities in loss networks[6]

1. Erlang fixed-point approximation
2. Slice method
3. 3-point slice method

Notes

1. Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 417. ISBN 0201544199.
2. Zachary, S.; Ziedins, I. (2011). "Loss Networks". Queueing Networks. International Series in Operations Research & Management Science. 154. p. 701. doi:10.1007/978-1-4419-6472-4_16. ISBN 978-1-4419-6471-7.
3. "Frederick W. Lanchester Prize". informs. Archived from the original on 2010-12-31. Retrieved 2010-11-17.
4. "Loss networks". Frank Kelly. Retrieved 2010-11-17.
5. Kelly, F. P. (1991). "Loss Networks". The Annals of Applied Probability. 1 (3): 319. doi:10.1214/aoap/1177005872. JSTOR 2959742.
6. Jung, K.; Lu, Y.; Shah, D.; Sharma, M.; Squillante, M. S. (2008). "Revisiting stochastic loss networks". Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems - SIGMETRICS '08 (PDF). p. 407. doi:10.1145/1375457.1375503. ISBN 9781605580050.