max-min fair | Eventually Almost Everywhere

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

Tag Archives: max-min fair

Elastic Networks and TCP

Related articles