Congestion control

Congestion control adjusts user transmission rates in response to load signals from shared resources. A resource can compute its price from local aggregate load, while each user sums prices along its route. Primal congestion potential and dual congestion potential formulations explain equilibrium and stability for suitable monotone response functions.

Maximize a sum of increasing strictly concave utilities $U_r(x_r)$ subject to $Ax\le C$, $x\ge 0$. Suppose capacities are positive, every route is nonempty, and $U_r^{\prime }(0)=\infty$. At its unique positive optimizer $x^{\ast }$, the Karush-Kuhn-Tucker conditions give nonnegative resource congestion prices $p^{\ast }$ and route congestion prices $y_r^{\ast }=U_r^{\prime }(x_r^{\ast })$. Choosing ${\nu }_r^{\ast }=x_r^{\ast }{e}^{y_r^{\ast }}$ makes each user maximize $U_r({\nu }_r{e}^{-y_r^{\ast }})-y_r^{\ast }{\nu }_r{e}^{-y_r^{\ast }}$ at ${\nu }_r^{\ast }$. It also makes $x^{\ast }$ maximize the entropy maximization for loss-network occupancy objective, since its gradient is $\log ({\nu }_r^{\ast }/x_r^{\ast })=(A^T{p}^{\ast }{)}_r$. Thus user and network optima implement the same system optimum.

A resource congestion price signals scarcity at a capacity-constrained link. Under multiplicative resource-price dynamics, its increase indicates excess demand and its decrease indicates spare capacity. A route pays the sum of these prices, its route congestion price. A zero resource congestion price at an optimum satisfies complementary slackness with possible spare capacity.

The total price seen by a route is the sum of resource congestion prices on its links. With weighted logarithmic utility $w_r\log x_r$, maximizing utility minus linear expenditure gives the demand $x_r=w_r/p_r$. This relation links user decisions to multiplicative resource-price dynamics.

For route prices $p=A^T\mu$, logarithmic users demand $x_r=w_r/p_r$, while resource prices adjust asThis model raises prices under excess demand and lowers them under spare capacity. Positive capacities and nonempty routes are standard well-definedness assumptions. Positive initial prices approach the dual optimum; zero prices are invariant and can create boundary equilibria of multiplicative price dynamics that overload a resource.

Routes with positive logarithmic utility weights choose rates inversely proportional to their total resource price. Each resource changes its price multiplicatively according to demand minus its increasing supply. For continuous strictly increasing $q_j$ with $q_j(0)=0$, the potential $V={\sum }_r{w}_r\log ({\sum }_{j\in r}{\mu }_j)-{\sum }_j{\int }_0^{{\mu }_j}{q}_j(u)du$ is strictly concave and has nonnegative derivative along the dynamics. Positive-price convergence for increasing resource supplies requires positivity on used resources; zero-price faces are invariant.

For finite nonempty routes and positive weights, the potential of increasing-supply resource-price dynamics has a unique maximum. Increasing supplies give a linear penalty at large prices, so its superlevel sets are compact, and logarithmic route terms exclude zero route totals. Used resources have uniformly positive demand on a trapped set; a sufficiently small positive price therefore increases, giving a positive lower bound. The potential derivative is ${\sum }_j{\kappa }_j{\mu }_j({\partial }_{j}V{)}^2$. It has finite integral and is uniformly continuous, so it tends to zero by uniformly continuous integrable functions vanish at infinity. Every limit point then satisfies the unique stationary equations. Unused resource prices decay to zero. Only continuity and strict increase of the supply functions are needed.

In multiplicative resource-price dynamics, a zero price remains zero even if demand exceeds supply there. For one route using two resources, unit weight and supplies $q_j(u)=u$, both $(0,1)$ and $(1,0)$ are equilibria, while the unique positive equilibrium is $(1/\sqrt{2},1/\sqrt{2})$. Thus uniqueness on the positive price domain cannot be extended to every nonnegative price trajectory without an extra boundary rule.

For a complementary-slackness optimum ${\mu }^{\ast }$, defineinterpreting a zero-reference summand as ${\mu }_j/{\kappa }_j$. This is a nonnegative generalized reverse-relative-entropy expression for positive resource prices. Along multiplicative resource-price dynamics, with $p=A^T\mu$ and $g=Ax-C$,Its sublevel bounds keep all route prices away from zero and permit the LaSalle invariance principle, including optima with some zero individual prices.

For multiplicative resource-price dynamics with positive capacities, nonempty routes and strictly positive initial prices, full row rank of the link-route incidence matrix makesstrictly concave. There is a unique optimizing price vector, possibly on the boundary, and the relative-entropy Lyapunov function for resource prices proves convergence to it. Row-rank deficiency still gives unique optimal route prices and rates, but resource prices may depend on the initial state. Full column rank alone and unrestricted zero initial prices do not yield the same uniqueness theorem.

In ${\dot{\mu }}_j={\kappa }_j{\mu }_j(y_j-q_j({\mu }_j))$, a zero price remains zero even if resource demand exceeds supply. Such a boundary equilibrium need not minimize the dual congestion potential; uniqueness of its positive minimizer does not imply uniqueness on the nonnegative orthant.

For strictly increasing continuous supply functions $q_j$ with $q_j(0)=0$, this potential is strictly convex on prices with positive route-price sums. Its minimum is interior for every used resource and gives the unique positive-price equilibrium. Multiplicative price dynamics can also have boundary equilibria of multiplicative price dynamics if zero prices are permitted.

This potential subtracts integrated resource prices from weighted logarithmic utility. Continuous nonnegative nondecreasing prices make it strictly concave on positive rates. If every route meets a resource with a nonzero price function, its superlevel sets are compact and its maximizer is unique. The rate adjustment ${\dot{x}}_r={\kappa }_r{x}_r{\partial }_{r}U$ increases it strictly away from equilibrium.

Assume finitely many nonempty routes, positive weights and adjustment rates, and continuous nonnegative nondecreasing resource prices. Each route must meet a resource whose price is positive somewhere. Then the primal congestion potential has compact superlevel sets inside the positive orthant and a unique maximum. Along gradient flow with diagonal mobility, $\dot{U}={\sum }_r{\kappa }_r{x}_r({\partial }_{r}U{)}^2$. The substitution $x_r={\kappa }_r{z}_r^2/4$ makes the dynamics ordinary gradient flow ascent for $V(z)=U(({\kappa }_r{z}_r^2/4{)}_r)$. This $V$ is strictly concave: the logarithmic terms are strictly concave, and each integrated price is convex and nondecreasing, composed with a convex quadratic load. Thus its continuous gradient is monotone decreasing, which proves uniqueness of trajectories even without differentiability of the prices. Compact trapping and the dissipation identity force every limit point to be the unique maximizer. If every price on some route vanishes identically, its rate instead grows linearly and there is no equilibrium.

For positive rates in congestion control, put $x_r={\kappa }_r{z}_r^2/4$ and $V(z)=U(x(z))$, where $U$ is the primal congestion potential. The equation ${\dot{x}}_r={\kappa }_r{x}_r{\partial }_{r}U$ becomes ${\dot{z}}_r={\partial }_{r}V$. Positive logarithmic utility weights make ${\sum }_r{w}_r\log ({\kappa }_r{z}_r^2/4)$ strictly concave on the positive orthant. Each integrated nonnegative nondecreasing resource price is a convex nondecreasing function of its load; composing it with the convex quadratic load in $z$ preserves convexity. Hence $V$ is a strictly concave function, even for prices that are merely continuous. For two solutions, $\frac{1}{2}\frac{d}{dt}\Vert z-\tilde{z}{\Vert }^2=(z-\tilde{z})\cdot [\nabla V(z)-\nabla V(\tilde{z})]\le 0$. This proves uniqueness of the flow without assuming local Lipschitz continuity of the price functions.