Internet congestion control: the network problem, the primal algorithm and its Lyapunov function
DefinitionKellyStochasticNetworks_CongestionThe congestion control model of Chapter 7 of Kelly and Yudovina, Stochastic Networks.
A network has resources and routes, with link-route incidence matrix ( when route uses resource ). A flow vector is feasible for when and the induced load on each resource respects its capacity, ; the problem is to maximize the objective
over the feasible set, where weights route .
The primal algorithm (7.5)–(7.6) is the differential equation
with and non-negative, continuous, increasing and not identically zero. It is a caricature of end-to-end control: resource generates congestion signals at rate , these reach every user whose route passes through , and the user responds with a decrease proportional to the signals received plus a steady increase proportional to . Both sums are local, so no machine needs to know .
Its Lyapunov function is
whose first term is the network objective and whose second penalizes resource load.
Formalization Note The link loads reuse the linkFlow of mission IV of this series, so the
incidence-matrix conventions of Chapters 4 and 7 agree. Flow vectors are real-valued and the
natural domain is the open positive orthant, since is meaningless at and
the book's maximum is interior to the orthant. The drift is given as a function of the state,
so a trajectory is a differentiable function whose derivative equals it pointwise.
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Wardrop
namespace KellyStochasticNetworks
/-- The feasible flow vectors of the network problem `network(A, C; w)` of section 7.1:
non-negative route rates whose induced link loads respect the capacities. -/
def networkFeasible {J R : ℕ} (A : Fin J → Fin R → ℝ) (C : Fin J → ℝ) : Set (Fin R → ℝ) :=
{x | (∀ r, 0 ≤ x r) ∧ ∀ j, linkFlow A x j ≤ C j}
/-- The objective `∑_r w_r log x_r` of `network(A, C; w)`. -/
noncomputable def networkObjective {R : ℕ} (w x : Fin R → ℝ) : ℝ :=
∑ r, w r * Real.log (x r)
/-- The utility `U(x) = ∑_r w_r log x_r - ∑_j ∫_0^{y_j} p_j(y) dy` of Theorem 7.6, where
`y_j = ∑_{s : j ∈ s} x_s` is the load on resource `j`. -/
noncomputable def primalUtility {J R : ℕ} (A : Fin J → Fin R → ℝ) (w : Fin R → ℝ)
(p : Fin J → ℝ → ℝ) (x : Fin R → ℝ) : ℝ :=
(∑ r, w r * Real.log (x r)) - ∑ j, ∫ y in (0:ℝ)..(linkFlow A x j), p j y
/-- The right-hand side of the **primal algorithm** (7.5)–(7.6):
`κ_r (w_r - x_r ∑_{j ∈ r} p_j(∑_{s : j ∈ s} x_s))`. -/
noncomputable def primalDrift {J R : ℕ} (A : Fin J → Fin R → ℝ) (w κ : Fin R → ℝ)
(p : Fin J → ℝ → ℝ) (x : Fin R → ℝ) (r : Fin R) : ℝ :=
κ r * (w r - x r * ∑ j, A j r * p j (linkFlow A x j))
end KellyStochasticNetworks