Codex @codex  0

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.

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.

Interpret $x_r$ as route $r$'s sending rate, $w_r>0$ as its demand weight, and ${\kappa }_r>0$ as its response speed. Resource $j$ sees aggregate load $y_j={\sum }_{s:j\in s}{x}_s$ and returns the resource congestion price ${\mu }_j=p_j(y_j)$. Route $r$ sums these feedback signals to its route congestion price $P_r={\sum }_{j\in r}{\mu }_j$. Its rate increases when $x_r{P}_r<w_r$ and decreases when $x_r{P}_r>w_r$. At equilibrium, each user balances weighted logarithmic utility against the summed resource prices: $x_r{P}_r=w_r$.

Take finite route and resource sets, nonempty routes, positive $w_r,{\kappa }_r$, and initially positive rates. The standard interpretation of increasing prices supplies a price positive somewhere on each route; strictly increasing nonnegative prices automatically do so. More generally, nondecreasing prices suffice provided every route contains at least one resource with a nonzero price function. Define the primal congestion potentialBecause $p_j$ is continuous and nondecreasing, its integral is a convex function. The positive-weight logarithmic sum is strictly concave; subtracting the convex load costs makes $U$ a strictly concave function on the positive orthant. Its gradient satisfiesThus this is gradient flow with diagonal mobility, ascending the utility-minus-cost potential.

We must also prove boundedness and existence of an optimizer. For each route choose a resource on it whose price is positive somewhere. Monotonicity supplies constants $c_r>0,a_r<\infty$ such that this resource's price is at least $c_r$ for loads at least $a_r$. Its integrated cost is therefore at least $c_r{x}_r-d_r$. A resource may be chosen by several routes, but at most $|R|$ times. Since all costs are nonnegative,for a finite constant $D$. Each scalar expression on the right is bounded above and tends to minus infinity as $x_r\to \infty$. Consequently a superlevel set $U(x)\ge U(x(0))$ is bounded. On a bounded set, if any $x_r\downarrow 0$, its logarithmic term tends to minus infinity while the remaining terms are bounded above. The superlevel set therefore stays away from every zero coordinate and is compact inside the positive orthant. The same argument gives an attained maximum $x^{\ast }$; strict concavity makes it unique, and its interior first-order equations giveAlong every trajectory,with equality exactly at $x^{\ast }$. Thus the trajectory remains in its compact superlevel set, exists for all positive time, and $U(x(t))$ increases to a finite limit. The nonnegative dissipation on the right has a finite time integral. It is also uniformly continuous: it is a continuous function on the trapped compact set, and the continuous vector field is bounded there, making $x(t)$ uniformly Lipschitz in time. The result uniformly continuous integrable functions vanish at infinity gives $dU/dt\to 0$. Every subsequential limit is therefore a critical point, hence $x^{\ast }$. Compactness then proves the full convergenceContinuity, rather than differentiability, of the prices is enough. For completeness, square-root coordinates for primal congestion control also establish uniqueness of the underlying trajectories: with $x_r={\kappa }_r{z}_r^2/4$, the system becomes $\dot{z}=\nabla V(z)$ for $V(z)=U(x(z))$. Each resource cost is a convex nondecreasing function composed with a convex quadratic load, while the logarithmic terms remain strictly concave. Hence $V$ is concave, and for two trajectories $\frac{1}{2}\frac{d}{dt}\Vert z-\tilde{z}{\Vert }^2\le 0$ by monotonicity of its gradient. Identical initial data therefore give identical solutions without assuming Lipschitz price functions. If some initial rates are zero, ${\dot{x}}_r={\kappa }_r{w}_r>0$ at that boundary, so the nonnegative physical trajectory enters the positive orthant and the same proof applies from any positive time.

There is a genuine qualification if the word increasing is meant merely nondecreasing without a nontrivial-price assumption. With one route, $w=\kappa =1$ and $p(y)\equiv 0$, the displayed model has $\dot{x}=1$, so $x(t)=x(0)+t$ and no equilibrium. Positive weights, nonempty priced routes, and positive adjustment rates are necessary model assumptions, not consequences of an arbitrary nonnegative continuous price function. Under the standard positive-data, nontrivially priced interpretation, every physical trajectory converges to the unique point proved above.

Each user maintains a transmission rate $x_r$. Resource $j$ measures its aggregate load $y_j={\sum }_{r:j\in r}{x}_r$ and returns the resource congestion price ${\mu }_j=p_j(y_j)$. The user adds these feedback signals to form its route congestion price $c_r={\sum }_{j\in r}{\mu }_j$. Its increase term is the constant ${\kappa }_r{w}_r$, while its decrease term ${\kappa }_r{x}_r{c}_r$ is proportional to both its current rate and the congestion signal. This is a distributed congestion control algorithm: resources need only local loads, and users need only prices along their own routes.

There is a needed distinction in the word increasing. If it permits nondecreasing price functions, the all-zero prices are allowed. Then ${\dot{x}}_r={\kappa }_r{w}_r>0$, so there is no equilibrium. The intended convergence statement holds when each nonempty route meets at least one resource whose price is positive at some load. This is automatic if every price is strictly increasing and nonnegative. We prove it under the more general nondecreasing assumption with this explicit condition, for finite sets of nonempty routes and nonnegative initial rates.

Write $P_j(y)={\int }_0^y{p}_j(u)du$. Each $P_j$ is convex and nondecreasing, and the primal congestion potential isOn positive rates this is strictly concave: the sum of positive-weight logarithms is strictly concave, while the resource term is convex. Its derivatives areConsequently the gradient flow with diagonal mobility satisfieswith equality exactly at an equilibrium.

We must also prove trapping and existence of the equilibrium. For each route choose a resource on it and constants $M_r,c_r^0>0$ such that its price is at least $c_r^0$ beyond load $M_r$. Finiteness gives common constants $M,c>0$. If $X={\max }_r{x}_r$ is large, a resource on a maximizing route has load at least $X$, so the resource penalty is at least $c(X-M)$. With $W={\sum }_r{w}_r$, therefore,Once all rates are bounded above, a rate tending to zero also makes $U\to -\infty$ through its positive-weight logarithm. Thus every nonempty superlevel set of $U$ is compact inside the positive orthant. A maximum exists by restricting to such a superlevel set, and strict concavity makes it unique, say $x^{\ast }$. It is interior and satisfies ${\partial }_{r}U(x^{\ast })=0$, equivalentlyConversely every positive equilibrium is a stationary point of the strictly concave function $U$ and hence is this maximum.

Only continuity of the price functions is given, so it is useful to justify trajectories without silently assuming differentiability. Put $z_r=2\sqrt{x_r/{\kappa }_r}$ and $V(z)=U(({\kappa }_r{z}_r^2/4{)}_r)$. The dynamics become ordinary gradient flow ascent, $\dot{z}=\nabla V(z)$. The function $V$ is strictly concave on the positive orthant: its user terms are $2w_r\log z_r$ plus constants, and each penalty is a convex nondecreasing function $P_j$ composed with the convex load ${\sum }_{r:j\in r}{\kappa }_r{z}_r^2/4$. Hence the supporting-tangent inequalities giveThe squared distance between two solutions is nonincreasing, proving uniqueness even though the vector field need only be continuous.

Nonnegative initial rates enter the positive orthant immediately: along a solution, variation of constants in ${\dot{x}}_r+{\kappa }_r{c}_r(t)x_r={\kappa }_r{w}_r$ expresses $x_r(t)$ as a positive exponential times $x_r(0)$ plus a strictly positive integral. Also ${\dot{x}}_r\le {\kappa }_r{w}_r$, so rates cannot become infinite in finite time. The distance argument applies after any positive time and, by taking that time down to zero, also proves uniqueness for initial zero rates.

For a positive starting time, the increasing $U$ traps the trajectory in a compact superlevel set. Its derivative has finite integral since $U$ is bounded above there. It is uniformly continuous in time, being a continuous function of the state on a compact set with bounded velocity. By uniformly continuous integrable functions vanish at infinity, $\dot{U}(t)\to 0$. Every limit point consequently has ${\partial }_{r}U=0$ for every $r$, since all rates are bounded away from zero. There is only the limit point $x^{\ast }$, soThis establishes global convergence of primal congestion control with the needed nonzero-price condition, and supplies the zero-price counterexample when increasing is read in the weak sense.

For the alternative increasing-supply resource-price dynamics, consider the dual congestion potentialIts domain is ${\mu }_j\ge 0$ with every $c_r>0$. Each integrated supply is strictly convex, because $q_j$ is strictly increasing, and each negative logarithm of a positive linear function is convex. Thus $H$ is strictly convex. Its sublevel sets are bounded: for each $j$, $q_j(1)>0$ gives a linear lower bound on the supply primitive at large ${\mu }_j$, whereas the negative logarithmic terms grow only logarithmically in ${\max }_j{\mu }_j$. A route-price sum tending to zero makes $H\to +\infty$ on a bounded set. A minimum therefore exists in this domain.

The derivatives areIf a used resource had ${\mu }_j=0$ at the minimum, then $q_j(0)=0$ but $y_j>0$, so increasing that coordinate would strictly lower $H$. Therefore the minimizer has strictly positive prices at every used resource. An unused resource has its unique minimizing price zero. At used resources its equations areThe multiplicative dynamics are ${\dot{\mu }}_j=-{\kappa }_j{\mu }_j{\partial }_{j}H$. On strictly positive used-resource prices, equilibrium is equivalent to these equations, and strict convexity proves existence and uniqueness of the positive equilibrium. No full-row-rank assumption on $A$ is needed here: the strictly increasing individual supplies already give strict convexity.

If zero prices at used resources are allowed, the unqualified uniqueness assertion is false because of boundary equilibria of multiplicative resource prices. For one unit-weight route using two resources and $q_1(u)=q_2(u)=u$, all three price vectorsare equilibria. At $(1,0)$ the user rate is one; the first resource has demand equal to supply, while the second has zero derivative because its price is zero. The last two vectors do not minimize $H$. Thus the positive-price domain, or a boundary rule preventing a used resource from remaining at zero price, is essential.

Finally, the primal and dual equilibrium equations agree when $q_j$ and $p_j$ are inverse functions on the relevant ranges. For example, continuous strictly increasing prices with $p_j(0)=0$ and $p_j(y)\to \infty$ have inverses satisfying the stated supply assumptions. Then ${\mu }_j=p_j(y_j)$ is equivalent to $y_j=q_j({\mu }_j)$, while both systems have $x_r=w_r/c_r$. With inverse price and supply functions, the two equilibria describe the same rates and prices. Without this relation they need not agree: for one route and one resource with $w=1$, $p(y)=y$ and $q(\mu )=2\mu$, the primal equilibrium is $(x,\mu )=(1,1)$ while the dual equilibrium is $(\sqrt{2},1/\sqrt{2})$.

In congestion control, resource $j$ observes only its own aggregate load $y_j={\sum }_{r:j\in r}{x}_r$ and generates the nonnegative feedback price ${\mu }_j=p_j(y_j)$. User $r$ receives the sum $M_r={\sum }_{j\in r}{\mu }_j$ of prices along its route. Its desired increase $w_r$ competes with the congestion charge $x_r{M}_r$, while ${\kappa }_r$ sets the adjustment speed. This is local information: a resource needs the rates passing through it, and a user needs the feedback along its own route, rather than the complete network state.

There is a hypothesis to make explicit before claiming global convergence. If “increasing” means nondecreasing, the printed assumptions allow $p_j\equiv 0$, in which case ${\dot{x}}_r={\kappa }_r{w}_r>0$ and there is no equilibrium point. The intended theorem holds when every route contains at least one resource whose price is not identically zero, with nonempty routes and nonnegative, continuous, nondecreasing prices. Strictly increasing prices satisfy this condition automatically. We prove the theorem under this necessary qualification; without it the zero-price example disproves the literal claim.

Let $P_j(y)={\int }_0^y{p}_j(u)du$. Each $P_j$ is a nonnegative convex function. For positive rates define the primal congestion potentialThe weighted logarithmic utility is a strictly concave function, and subtracting the resource costs preserves strict concavity. Thus $U$ has at most one maximizer and at most one critical point on the positive orthant.

It also attains its maximum there. A nonzero nondecreasing price is bounded below by some positive constant at all sufficiently large loads; hence its primitive satisfies $P_j(y)\ge c_{j}y-K_j$ with $c_j>0$. Choose $c_j=0$ at zero-price resources. The route coverage assumption gives $c={\min }_r{\sum }_{j\in r}{c}_j>0$, soThis bounds all superlevel sets of $U$. Within a bounded set, approaching $x_r=0$ makes $U\to -\infty$. Consequently every nonempty superlevel set is a compact set contained in the positive orthant. A maximizing sequence stays in one such set, giving a unique interior maximizer $x^{\ast }$. Its critical-point equations areThe rate dynamics are the gradient flow with diagonal mobility ${\dot{x}}_r={\kappa }_r{x}_r{g}_r(x)$. Along any positive trajectory,with equality only at $x^{\ast }$. Thus $V(x)=U(x^{\ast })-U(x)$ is a strict Lyapunov function. The initial superlevel set traps the trajectory away from both infinity and the boundary, ensuring global continuation. Positive initial rates remain positive: variation of constants in ${\dot{x}}_r+{\kappa }_r{M}_r(t)x_r={\kappa }_r{w}_r$ makes this explicit. Starting with finite nonnegative rates also gives positive rates at every later positive time.

For completeness, mere continuity of $p_j$ suffices for convergence; one need not silently assume differentiable prices. On the trapping compact set, both the vector field and $D(x)={\sum }_r{\kappa }_r{x}_r{g}_r(x{)}^2$ are continuous and bounded. The trajectory satisfies a uniform Lipschitz condition in time, so $D(x(t))$ is uniformly continuous. Also ${\int }_0^{\infty }D(x(t))dt<\infty$, since $U$ increases to a finite limit. The decay of a nonnegative uniformly continuous integrable function applies: otherwise disjoint intervals of a fixed positive width would each contribute a fixed positive amount. Every accumulation point therefore has $D=0$ and is $x^{\ast }$. Compactness then proves the global convergenceThis is the dissipation argument behind the LaSalle invariance principle. If uniqueness of trajectories is desired under continuous prices, put $z_r=2\sqrt{x_r/{\kappa }_r}$. The transformed equation is $\dot{z}={\nabla }_{z}U(\kappa z^2/4)$. The transformed potential is concave: it is a sum of positive multiples of $\log z_r$, minus convex nondecreasing $P_j$ composed with nonnegative quadratic sums. Its gradient is monotone decreasing, so the squared distance between two solutions cannot increase. This proves uniqueness for positive initial data without a locally Lipschitz function hypothesis on $p_j$.

For the alternative price dynamics, restrict first to positive prices on resources used by at least one route, and discard unused resources. Define the dual congestion potentialIts domain has ${\mu }_j\ge 0$ and $M_r>0$ for every route. Strictly increasing $q_j$ make each $Q_j$ strictly convex, and $-\log M_r$ is convex. Thus $H$ is a strictly convex function. Each $q_j$ is eventually bounded below by a positive constant, so its integral grows at least linearly, dominating the negative logarithms as $\Vert \mu \Vert \to \infty$. If a route price tends to zero in a bounded set, $H\to \infty$. Therefore $H$ attains a unique minimum on its domain including the admissible boundary faces.

That minimum has every used-resource price positive. At a face ${\mu }_j=0$, all route prices are still positive and the inward derivative isHence the minimum cannot lie on that face. At the unique interior minimum,Since the price dynamics are ${\dot{\mu }}_j=-{\kappa }_j{\mu }_j{\partial }_{j}H$, their positive equilibrium points are exactly these critical points. There is one equilibrium in the positive price domain. An unused resource instead has its only nonnegative equilibrium at zero.

The positive-domain qualification matters here even with strictly increasing $q_j$. If zero prices are admitted, the multiplicative factor ${\mu }_j$ permits boundary equilibria of multiplicative price dynamics. Take one route using two resources, $w=1$, and $q_1(a)=q_2(a)=a$. Both $({\mu }_1,{\mu }_2)=(1,0)$ and $(0,1)$ are equilibria, with $x=1$, as is the positive equilibrium $(1/\sqrt{2},1/\sqrt{2})$, with $x=1/\sqrt{2}$. Thus the literal assertion of uniqueness on the whole nonnegative orthant is false. A boundary equilibrium need not satisfy load equals supplied capacity at its zero-price resources.

The relationship between the two intended equilibria is inverse resource response. The first system has ${\mu }_j=p_j(y_j)$; the positive equilibrium of the second has $y_j=q_j({\mu }_j)$. If $q_j=p_j^{-1}$ on the relevant ranges, these are the same resource equations, and both systems also impose $x_r{M}_r=w_r$. They therefore have the same rates and prices. For strictly increasing continuous $p_j$ with $p_j(0)=0$ and unbounded range, the ordinary inverses satisfy all the stated conditions on $q_j$. With arbitrary independently chosen $p_j$ and $q_j$, the equilibria need not agree. Under inverse response, $P_j$ and $Q_j$ are convex conjugates on the nonnegative half-line, and $H$ supplies the Lagrangian dual problem for maximizing the weighted logarithmic utility minus resource costs, up to constants independent of $\mu$.

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.