Tag Archives: Lagrangian

Loss Networks and Erlang’s Fixed Point

Posted on by
Reply

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 →

Advertisement

Elastic Networks and TCP

Posted on by
Reply

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.

Related articles

Braess’s Paradox and Traffic Networks

Posted on by
Reply

For a traffic network, we have routes and links as before, only here we specify the delay on a link as a function of the flow along that link D_j(y_j), where y_j=\sum_r A_{jr}x_r as before. Then a natural notion of an equilibrium is a distribution of flows such that no customer stands to gain by changing route. Formally, take S the set of source-destination pairs, H_{sr} the incidence matrix of pairs s and routes r, and S(r) the routes between the same source-destination pair as r.

Then define a Wardrop equilibrium to be a flow vector (x_r,r\in R) such that for any x_r>0,

\sum_j D_j(y_j)A_{jr}=\min_{r'\in S(r)}\sum_j D_j(y_j)A_{jr}

that is, the delay on this route is less than or equal to the delay on any route between that pair of vertices.

A natural assumption would be that D_j(y_j) is increasing in y_j for each j, and if we further assume that each D_j is continuously differentiable, then we can prove that a Wardrop Equilibrium exists.

Why? Consider the optimisation problem

\min\quad\sum_j \int_0^{y_j}D_j(u)du,\quad x\geq 0,Hx=f,Ax=y

where f is the flow requirement. The feasible region is convex and the objective function is convex differentiable so the optimum exists. The Lagrangian is

L(x,y,\lambda,\mu)=\sum_j \int_0^{y_j}D_j(u)du+\lambda\cdot (f-Hx)-\mu\cdot(y-Ax)

and at the minimum

0=D_j(y_j)-\mu_j,\quad 0=-\lambda_{S(r)}+\sum_j \mu_jA_{jr}

So \mu_j the delay on j, and then

\lambda_{S(r)}\left\{\begin{array}{l l}=\sum_j\mu_jA_{jr}& \quad x_r>0\\ \leq \sum_j\mu_jA_{jr} & \quad x_r=0\\ \end{array} \right.

So can interpret \lambda_{S(r)} as the minimum delay for this route, and so a solution to this problem is a Wardrop Equilibrium. If D_js are strictly increasing, then have uniqueness in (y_j), from the optimisation problem, but not in (x_r). For example, you could have two essentially identical routes from A to B, and from B to C, and it then doesn’t matter how you concatenate them to form a flow from A to C.

Note the counterintuitive Braess’s Paradox, where adding a route increasing the size of the delay at the Wardrop Equilibrium. The canonical example can be seen here, where the addition of the road across causes the delay to increase from 83 to 92. And indeed such effects have been observed in ‘real life’ as well.

Note that one explanation for why this seems counter-intuitive is that the objective function isn’t necessarily the most natural one. For a Wardrop equilibrium, the agents are acting entirely selfishly given present information. From the point of view of society, it might make more sense to minimise the average delay \min \sum_jy_jD_j(y_j). In this case the Lagrangian gives

0=D_j(y_j)+y_jD_j'(y_j)-\mu_j,\quad 0=-\lambda_{S(r)}+\sum_j\mu_jA_{jr}

So if add a congestion charge of y_jD_j'(y_j) to the delay function, the Wardrop Equilibrium becomes equal to the societal optimal. Note that this is NOT the societal optimal for (delay + charge). However, we have seen that a toll will enable selfish behaviour to produce a societal optimum. This is an example of mechanism design, which can be considered a branch of game theory, where the aim is to design systems so that agents work in a societally optimal manner.

Related articles