Now, suppose each route is given a rate , and there is a utility function . Links have capacities as before, so seek to solve the optimisation problem
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:
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 for fixed w. That is
These optimisation problems are linked formally by the following theorem:
Theorem: We can find that solve USER and NETWORK, for which . Furthermore, x then solves SYSTEM.
To prove this result, write down SYSTEM’s Lagrangian . The Lagrangian of NETWORK is similar, and at the optimum of USER, these Lagrangians are in fact the same, with shadow prices for resources and routes respectively.
We discuss two regimes for fairness of allocations:
1) 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 such that , 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) 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:
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
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
where . 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
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)