In Erlang’s telephone line model discussed in the previous post, we considered users competing for a finite set of resources. When insufficient resources are available, the call is lost. A loss network generalises this situation to more complicated resource configurations. We think of links 1, …, J, each with some integer capacity . Each incoming call requires 1 units of each link in some subset of the set of links, and lasts for a time distributed as an exponential random variable with parameter 1, independent of everything else in the model. We call this subset the route, and denote by the incidence matrix of links on routes. Calls arrive as PP()$ independently for each route: no queueing occurs – a call is lost if some link required is operating at full capacity. We call the probability of this event , the loss probability. Observe that , the number of calls on each route r, is a Markov chain on the truncated space .
By checking the DBEs, it is clear that an ED for this Markov chain is proportional to the ED for the MC without the capacity constraint, with state-space restricted to the truncated space. But without capacity constraints, the system is a linear migration process, for which we discovered the form of the ED in the previous section. If we write in the linear migration process, we can compute the acceptance probability for the finite capacity system as:
Approximating Blocking Probabilities
We want to calculate , the equilibrium blocking probability, that a given link j is full. We have two methods: firstly, to find the distribution for with maximum probability, for which the blocking probabilities appear as shadow prices. And secondly, to make a reasonable approximation about blocking independence, and solve explicitly. We want to show that these methods give the same answers.
To maximise the probability on , we take logs and maximise using Stirling’s approximation, which is reasonable as we are implicitly working under a regime where the throughput tends to infinity while preserving ratios.
The primal problem is
which has Lagrangian
We observe that complementary slackness here has the form , and remember that by Strong Duality, which applies here because everything relevant is convex, this equality holds at the primal optimum. Differentiating the Lagrangian at the optimum allows us to specify the optimal x in terms of y:
The dual problem is then to minimise
At this point, we make the suggestive substitution , observing that this gives B non-negative by default since y is non-negative. After further work, we will deduce that these B do indeed have a sensible interpretation as blocking probabilities, but it should be stressed that this is in no way obvious yet. Now complementary slackness asserts:
Note that the primal objective function is strictly convex so as discussed is the unique optimum. The dual objective is strictly convex in , so if A has full rank J, this induces a unique optimum in terms of y. We assume A is full rank (since for example we can perturb slightly) and that there is no degeneracy in the blocking.
Now we consider a sequence of networks with proportionally increasing arrival rates and capacities
Then we show that . To do this, we observe that , compact. Let B’ be the limit of some subsequence of (B(N)). It is clear that for large enough N, we can replace the slackness condition in B(N) in the above for B’. Concretely,
Dividing by N and applying uniqueness gives B’=B. In the usual way, this implies that the whole sequence . The limit for follows at once.
We can further prove that where , independent, uniformly conditioned on , where are the indices for which B is non-zero.
By Little’s Law, a consequence is:
Note that this is the first concrete result showing B represents blocking, but explains the significance of everything that came before.
Erlang’s Fixed Point
Alternatively, we assume blocking is independent for different links. A link only receives traffic on routes for which the other links are unblocked, so by Erlang’s formula, we can approximate by
This is a continuous map from , so by Brouwer’s Fixed Point Theorem, there is a solution, called the Erlang Fixed Point.
We consider in fact the more general equations (ie for more general A):
We prove these have a unique solution, again making use of optimisation arguments.
Define U(z,c) implicitly by
which is strictly increasing in z. This has a utilisation interpretation as the mean number of circuits in use for an Erlang model with blocking probability . The function is strictly convex in y, and so
has a unique minimum.
The conditions for the minimum precisely assert that is unique. Furthermore uniformly on compact sets in y as . This is because if for an isolated link:
and after a bit of calculation. Finally, since the revised dual converges uniformly to the original dual, the minima converge also: as we would hope.
As a note of caution about the non-uniqueness of these Erlang-type equation sets, consider a model on , where calls are routed directly if possible, otherwise an attempt is made to reroute through a randomly chosen second vertex. Then, assuming independence . So , after thinking carefully about where calls come from.
Letting , we obtain
So if, eg , we have multiple solutions for B.