22 | May | 2012 | Eventually Almost Everywhere

Loss Networks

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 $c_j$ . 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 $A_{jr}$ the incidence matrix of links on routes. Calls arrive as PP( $\nu_r$ )$ 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 $L_r$ , the loss probability. Observe that $(n_r)$ , the number of calls on each route r, is a Markov chain on the truncated space $\{An\leq c\}$ .

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 $H(c)=\mathbb{P}(An\leq c)$ in the linear migration process, we can compute the acceptance probability for the finite capacity system as:

$1-L_r=\frac{H(C-Ae_r)}{H(C)}$

Approximating Blocking Probabilities

We want to calculate $B_j$ , the equilibrium blocking probability, that a given link j is full. We have two methods: firstly, to find the distribution for $(n_r)$ 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 $\pi(n)\propto \prod_r \frac{\nu_r^{n_r}}{n_r!}$ on $\{An\leq c\}$ , 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

$\max\quad \sum_r(x_r\log \nu_r-x_r\log x_r+x_r),\quad\text{s.t. }Ax\leq c$

which has Lagrangian

$L(x,y,z)=\sum_r x_r+\sum_r x_r(\log \nu_r-\log x_r-\sum_j y_jA_{jr})+\sum_j y_jc_j-\sum_j y_jc_j$

We observe that complementary slackness here has the form $y.z=0$ , 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:

$\bar{x}_r=\nu_r e^{-\sum y_jA_{jr}}$

The dual problem is then to minimise

$\min\quad \sum_r \nu_re^{-\sum_jy_jA_{jr}}+\sum_j y_jc_j$

At this point, we make the suggestive substitution $e^{-y_j}=1-B_j$ , 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:

$\sum_rA_{jr}\nu_r\prod_i(1-B_i)^{A_{ir}}\left\{\begin{array}{l l}=c_j& \quad B_j>0\\ \leq c_j & \quad B_j=0\\ \end{array} \right.$

Note that the primal objective function is strictly convex so $\bar{x}$ as discussed is the unique optimum. The dual objective is strictly convex in $yA$ , 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 Continue reading →

Now, suppose each route is given a rate $x_r$ , and there is a utility function $U_r(x_r)$ . Links have capacities as before, so seek to solve the optimisation problem

$\max\quad \sum_r U_r(x_r)\quad\text{s.t.}\quad Ax\leq c$

This is called the SYSTEM problem. However, the system might not know the utility functions U, or the incidence matrix A. We can alternatively consider the USER problem, where for a given route we assume the cost of the rate is linear, and maximise (utility – cost). That is:

$\max\quad U_r(\frac{w_r}{\lambda_r})-w_r,\quad w_r\geq 0$

where the constant of linearity has been absorbed into the utility function. For the NETWORK problem, we essentially repeat the system problem, only under the assumption that utility functions are $w_r\log x_r$ for fixed w. That is

$\max\quad \sum_r w_r\log x_r,\quad\text{s.t.}\quad Ax\leq c$

These optimisation problems are linked formally by the following theorem:

Theorem: We can find $\lambda,w,x$ that solve USER and NETWORK, for which $w_r=\lambda_rx_r$ . Furthermore, x then solves SYSTEM.

To prove this result, write down SYSTEM’s Lagrangian $L(x,z,\mu)=\sum_r U_r(x_r)+\mu^T(c-Ax-z)$ . The Lagrangian of NETWORK is similar, and at the optimum of USER, these Lagrangians are in fact the same, with $\mu_j,\lambda_r$ shadow prices for resources and routes respectively.

We discuss two regimes for fairness of allocations:

1) $(x_r)$ is max-min fair if it is a feasible flow, and if the smallest flow component is as large as possible. That is, if y is another feasible flow, then $\exists r$ such that $y_r>x_r\Rightarrow\exists s: y_s<x_s\leq x_r$ , ie you can’t increase a flow component without taking away from some other component which is smaller to begin with. Such a vector exists if the feasible region is convex, which in all practical examples it ought to be.

2) $(x_r)$ is proportionally fair if it is feasible, and if for any other feasible vector, the change in the sum, weighted by x is non-positive, that is:

$\sum_r \frac{x_r-y_r}{x_r}\leq 0$

Alternatively, can think of this as saying that the sum of the percentage changes in each component is non-positive. We say the distribution is weighted proportionally fair with respect to w if

$\sum_r w_r\frac{x_r-y_r}{x_r}\leq 0$

Then it can be seen by considering behaviour in a neighbourhood of the optimum of the Lagrangian, that x solves NETWORK iff it weighted proportionally fair.

TCP and Lyapunov functions

Assume rates are controlled by the ODE

$\frac{d}{dt}x_r(t)=k_r(w_r-x_r(t)\sum_{j\in r}\mu_j(t))$

where $\mu_j(t)=p_j(\sum_{s\ni j}x_s(t))$ . The motivation is that the increase in flow is linear (we increase it whenever it appears possible) and the decrease is multiplicative (that is, after negative feedback – a sign of failure to transmit a packet – the flow is halved). We seek a so-called Lyapunov function, which is a function of the system monotone along trajectories. In this case, a suitable example is

$U(x)=\sum w_r\log x_r -\sum_j \int_0^{\sum_{s\ni j}x_s}p_j(y)dy$

Such a function is differentiable, and has a unique maximum. Bounding the derivative away from 0 ensures that the maximum is actually attained in every case.

TCP Effective Bandwidth (1) (gkf168.wordpress.com)

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Daily Archives: May 22, 2012

Loss Networks and Erlang’s Fixed Point

Elastic Networks and TCP

Related articles