Congestion avoidance

This is the companion to mb-ecn (doc/mb-ecn.mediawiki). That document says what the algorithm does; this one says what can be proven about it converging, and at what level of idealization. It is written for engineers and non-expert mathematicians: every proof technique gets a plain-language explanation of what it buys, and every claim is tagged with one of four statuses:

• proven — a theorem; assumptions stated, argument checkable.
• conditional — holds under an explicit inequality or pending routine formalization.
• heuristic — plausible and quantitative, but resting on an approximation.
• false — not true of the real system, and provably so.

The headline, up front: the zero-delay fluid model of mb-ecn has a complete global convergence theory — it is exactly a utility-maximizing controller with the bottleneck queue as its price, and an explicit energy (Lyapunov) function certifies convergence from any starting state. With feedback delay the result is conditional: the stability margin scales as √G · τ, as the algorithm document claims, and the constant in front is numerical, not clean. For the real, quantized, event-driven code, convergence to an exact operating point is false by construction; what holds instead is practical stability: trajectories enter and stay in a band a few packets wide around the ideal point. Each section below develops one of these statements; the appendix states and proves the core results in full.

Notation

Symbols match the algorithm document; a few are added for the analysis.

Symbol	Units	Meaning
r_i	B/s	Paced rate of aggregate i; y = Σ r_i
C	B/s	Bottleneck capacity
S	bytes	Packet size (1000 B in all figures)
q	packets	Bottleneck standing queue
Q	packets	Marking quantum (4)
m	ece units	Congestion signal seen by a sender
M	ece units	Full-congestion reference (512)
a_i	B/s^2	Additive slope of aggregate i (C/32 when capacity is live)
T	s	Probe time constant T_probe (8 s)
τ	s	Feedback (loop) delay, ~ path RTT
W	s	Receiver averaging window
T_w	s	Washout bucket (~31 ms)
p	–	Price: p = min(8q, M) / M ∈ [0, 1]
U_i	–	Utility function of aggregate i
V	–	Lyapunov (energy) function
G	1/s^2	Loop gain 8C/(MS); ω_0 = √G
N	–	Number of aggregates at the bottleneck

Starred quantities (r*, q*, m*, p*) are equilibrium values.

The fluid model

The analysis works on a continuous-time reduction of the CA regime: one bottleneck of capacity C, N aggregates past slow start, all persistently backlogged. Three equations:

 dr_i/dt = a_i + r_i/T - r_i * min(m, M)/M        (sender rate law)
 dq/dt   = (y - C)/S ,  y = sum_i r_i             (queue; held at 0 when empty)
 m       = 8 q                                     (marking + receiver, steady)

The rate law is read directly off the code (mb_ecn_increase, mb_ecn_decrease in mb-ecn.c): the increase adds a · Δt and r · Δt / T per elapsed time, the decrease removes r · mark · Δt_ms / (1000 M), which per second is r · m / M. The marking relation comes from the forwarder (ecn = q/Q with Q = 4) and the receiver (ece = 32 × time-mean of ecn), so in steady state m = 32 q / 4 = 8 q. One unit note: the drain term r · min(m, M)/M is applied per second (the code scales by elapsed milliseconds over 1000), so the dimensionless price of the optimization view implicitly carries 1/s; the algebra is unchanged.

The reduction drops five things the code has, and the dropping is justified at equilibrium because each dropped term is exactly zero or inactive there:

• the one-sided derivative cut fires only when m rises between samples — zero at constant m;
• the washout damps rate change — zero at constant r;
• the r/2 single-step cut cap is far from binding (the equilibrium per-step cut is ~10^-4 of the rate);
• the local first-hop fallback is inactive whenever feedback is live;
• the increase gating is inactive because the aggregate is assumed backlogged.

Away from equilibrium the first two matter a great deal — they are the loop's damping — and they return in the delay section.

One implementation detail is load-bearing for exactness: the decrease scales by whole elapsed milliseconds and carries the sub-ms remainder (dec_acc in mb_ecn_decrease). Because no time is dropped, the applied cut integrates to exactly ∫ r m / M dt over any marked interval, up to one pending control quantum (< 1 ms). Without the carry the effective decrease would be κ · r m / M with a rate-dependent κ ∈ (1/2, 1], and every theorem below would hold only band-wise, with the price effectively different per aggregate. With it, the fluid model is faithful in time-average, full stop.

Equilibrium

Status: proven (existence, uniqueness), under explicit feasibility inequalities.

Setting dq/dt = 0 forces y* = C. Setting each dr_i/dt = 0 at shared signal m* gives

 r_i* = a_i / (m*/M - 1/T)

which is positive and decreasing in m*. Summing and equating to C pins the signal, the queue, and the shares:

 m*   = M (sum_j a_j / C  +  1/T)
 q*   = m*/8 = 64 sum_j a_j / C  +  64/T          [packets]
 r_i* = C a_i / sum_j a_j

With the capacity-derived slope a_i = C/32 for all i and T = 8 s:

 q* = 2 N + 8   packets

two packets per aggregate plus the fixed probe floor — the same q* = 64 a / r + 64 / T_probe as the algorithm document's fairness section, summed over the aggregates.

Three feasibility conditions make this an honest theorem rather than a formula:

• Below saturation: m* < M, i.e. Σ a_j / C + 1/T < 1. At a = C/32 that is N/32 + 1/8 < 1, so N ≤ 27 same-class aggregates. The saturated cut can only hold each rate at (8/7) a_i = C/28: at N = 28 those rates sum to exactly C — a degenerate knee with a continuum of neutrally stable saturated states (any q ≥ 64) — and for N ≥ 29 the sum exceeds C and the fluid queue grows without bound; no equilibrium either way. Note this is a different constraint from the rate floor: the floor admits N ≤ 32 flows at r* = C/N ≥ C/32, but mark saturation binds first, so the algorithm document's "about 32 flows fit above the floor" is 27 in the fluid model — flows 28 through 32 fit above the floor but have no interior equilibrium to sit at.
• Above the dead zone: q* ≥ 64/T = 8 > Q = 4 for any a ≥ 0. The probe term alone keeps the equilibrium out of the no-signal region — that is precisely what the probe floor is for, and here it is a checkable inequality (T < 16 s suffices).
• Inside the clamps: r_min,i ≤ r_i* ≤ r_max.

Uniqueness is elementary: Σ_i r_i(m) is continuous and strictly decreasing in m on the feasible range, so it crosses C exactly once. On the boundary q = 0 there is no equilibrium because dr_i/dt ≥ a_i > 0 with no marks.

Note what is absent from every equation above: the delay τ. The equilibrium allocation is RTT-independent as a theorem, not a slogan — τ simply does not appear in the fixed-point algebra. (Dynamics are another matter; see below.)

What the law optimizes

Status: proven (an algebraic identity plus standard convex duality).

Rewrite the rate law by factoring out r_i:

 dr_i/dt = r_i * ( U_i'(r_i) - p ) ,   with  U_i'(r) = a_i/r + 1/T
                                       and   p = min(8q, M)/M

Integrating U_i' identifies the utility:

 U_i(r) = a_i ln r + r/T

strictly concave (U_i = -a_i/r^2 < 0). This is the classic Kelly primal source law: climb your own marginal utility, pay the network's price. And the price here is not a computed variable — it is the physical queue, evolving as

 dp/dt = (8/(MS)) (y - C)          (below saturation, q > 0)

which is the price half of Arrow–Hurwicz primal-dual (saddle-point) dynamics on the capacity constraint, with a step size 8/(MS) welded to the packet size and marking quantum. The q = 0 reflection is exactly the projection p ≥ 0. So the zero-delay fluid model is a primal-dual algorithm for

 maximize   sum_i ( a_i ln r_i + r_i/T )
 subject to sum_i r_i <= C

Consequences, all inherited from convex duality:

• Weighted proportional fairness with weights a_i. At a single bottleneck the linear r/T terms sum to C/T on the constraint and drop out of the argmax, so equal weights give the equal split — which at one link is max-min fair. This is the algorithm document's fairness claim, now as the KKT point of an explicit program.
• Different capacity classes (a_i = C_i/32) give capacity-weighted shares — also as documented.
• The equilibrium price must be carried as a standing queue q* = (M/8) p*; the probe term makes p* ≥ 1/T, i.e. at least 8 packets. The queue-only signal costs a permanent queue; the optimization view shows the cost is structural, not a tuning artifact.
• In a multi-link network the objective is proportional fairness plus a linear throughput bias r/T; the single-bottleneck results here do not automatically extend. No network-wide claim is made.

Global convergence at zero delay

Status: proven, for N aggregates, any monotone marking curve, dead zone and saturation included. Assumptions: zero feedback delay, backlogged aggregates, frozen a_i, feasibility as above.

A Lyapunov function is an energy: a nonnegative quantity that the dynamics can only decrease. If it is zero only at the equilibrium and grows toward the edges of the state space, then "energy only decreases" forces every trajectory to the equilibrium. The right energy here is the standard primal-dual one:

 V(r, q) = sum_i [ r_i - r_i* - r_i* ln(r_i / r_i*) ]
         + S * integral from q* to q of ( P(s) - p* ) ds

where P(s) = min(8s, M)/M is the marking curve. The first part penalizes rate error (it is zero at r_i = r_i*, positive elsewhere, and blows up at r_i = 0 and ∞); the second penalizes queue error (nonnegative because P is nondecreasing through P(q*) = p*).

Differentiate along trajectories. The rate part, using dr_i/dt = r_i (U_i'(r_i) - P(q)) and the equilibrium relation U_i'(r_i*) = p*:

 d/dt [rate part] = sum_i (r_i - r_i*) ( U_i'(r_i) - P(q) )
                  = - sum_i a_i (r_i - r_i*)^2 / (r_i r_i*)
                    + (p* - P(q)) * sum_i (r_i - r_i*)

The queue part, using dq/dt = (y - C)/S and C = Σ r_i*:

 d/dt [queue part] = (P(q) - p*) * sum_i (r_i - r_i*)

Add them: the indefinite cross terms cancel identically, leaving

 dV/dt = - sum_i a_i (r_i - r_i*)^2 / (r_i r_i*)  <=  0

This cancellation is the entire proof, and it is worth staring at: it used nothing about P except that the same P(q) appears in the source law and in the queue term. The cancellation survives any nondecreasing P; turning dV/dt ≤ 0 into convergence to the point needs two more properties — P continuous, and strictly increasing through the level p* — which the dead zone and the saturation leave intact, since the equilibrium sits on the open ramp. A curve flat exactly at level p* (the quantized staircase of the real system) gets only convergence to the set {r*} × P^-1(p*): the fluid model's own preview of practical stability. The fragility of mb-ecn, such as it is, is not in the marking nonlinearity. (It is also why the sub-ms carry matters: a rate-dependent gain in front of the price would be a per-aggregate distortion of P, and the cancellation would fail.)

Two boundary cases close the argument. On q = 0 with y < C the projection zeroes dq/dt and dV/dt gains the strictly negative term p*(y - C) — the reflection only helps. And dV/dt = 0 forces r = r*; the only trajectory that stays there has P(q) = p*, whose preimage is the single point q* (the level p* sits strictly inside the increasing ramp of P by feasibility). By LaSalle's invariance principle — "the system ends up in the largest set where the energy stops decreasing" — every trajectory converges to (r*, q*). Global asymptotic stability.

A second, independent proof for one aggregate

Status: proven (single aggregate only).

With one aggregate the state is the plane (r, q), and planar systems admit a stronger tool. The Bendixson–Dulac criterion says: if some positive weight B(r, q) makes the weighted divergence of the vector field one-signed, no periodic orbit can exist. Take B = 1/r:

 div( B f ) = d/dr [ a/r + 1/T - P(q) ]  +  d/dq [ (r - C)/(S r) ]
            = - a / r^2  +  0   <  0        for all r > 0

independent of P and q, on both branches of P (ramp and saturation). No cycles, no homoclinic loops. Trajectories are bounded (properness of V), the equilibrium is unique, so the Poincaré–Bendixson theorem — "a bounded planar trajectory must end at an equilibrium or a cycle" — leaves only the equilibrium. This confirms the Lyapunov result by a completely different route, but it is intrinsically two-dimensional: it does not extend to N > 1 or to delay.

Fairness dynamics

Status: proven (zero delay, equal weights).

Subtracting two source laws with a_i = a_j = a kills the additive terms and leaves an exact scalar equation for the difference:

 d(r_i - r_j)/dt = ( 1/T - P(q(t)) ) * (r_i - r_j)

Since P → p* = 1/T + N a / C, the difference eventually contracts at rate N a / C — with a = C/32, that is N/32 per second, a 32/N-second timescale at any capacity. The gap never changes sign (no oscillation between flows); it shrinks monotonically once the queue holds P above 1/T, and from an empty queue it first grows, at rate at most 1/T. Efficiency (y → C) converges on the fast oscillator timescale below; fairness converges on this slow one. The two are decoupled.

Delay: local stability

Status: the oscillator structure and the bare-loop margin are proven (linear analysis); the stabilized margin is conditional / heuristic, resting on a describing-function approximation; the √G · τ scaling is intrinsic.

Linearize the smooth model at (C, q*) and give the price a delay τ:

 d(dr)/dt = -(a/C) dr - (C/M) dm(t - τ)
 d(dq)/dt = dr / S ,      dm = 8 dq

Eliminating gives the characteristic equation

 s^2 + (a/C) s + G e^(-sτ) = 0 ,     G = 8C/(MS) = ω_0^2

Without delay this is a harmonic oscillator with natural frequency ω_0 = √(8C/(MS)) — rising with the square root of capacity — and damping a/C = 1/32 s^-1, i.e. next to none:

Link	C (B/s)	G (s^-2)	ω_0 (rad/s)	period
10 Mb/s	1.25e6	19.5	4.4	~1.4 s
100 Mb/s	1.25e7	195	14	~450 ms
1 Gb/s	1.25e8	1953	44	~140 ms
10 Gb/s	1.25e9	19531	140	~45 ms

The bare loop is a near-undamped oscillator, and delay is poison to those. The first root crossing of the characteristic equation sits at

 τ* ≈ (a/C) / ω_0^2 = M S / (256 C) = 2 S / C     (at a = C/32)

two packet serialization times — 16 µs at 1 Gb/s. (This is the N = 1 case; the collective mode of N equal aggregates obeys the same law with a := Σ a_j, so its bare margin is 2NS/C — the lone aggregate is the worst case.) Two honest conclusions follow. First: the smooth AIMD law by itself is provably unstable at any realistic RTT, so no Lyapunov argument for the delayed bare law can exist (this is a fact, not a missing trick: holding even a 4 ms RTT at 1 Gb/s needs damping of order G τ ≈ 8 s^-1, 250 times the a/C = 1/32 the smooth model has). Second: whatever holds the real controller together must be exactly the two terms the smooth reduction dropped. It is:

• The washout (rate-velocity damping). Continuum-averaging its once-per-bucket pullback gives the transfer function (1 - e^(-s T_w)) / (4 T_w), with real part (1 - cos ωT_w)/(4 T_w) ≥ 0 at every frequency, peaking at 1/(2 T_w) ≈ 16 s^-1 at ωT_w = π (~100 rad/s). The provable statement is one-sided: at any imaginary-axis crossing the balance becomes G sin(ωτ) = ω (a/C + Re H), so a nonnegative Re H weakly extends the crossing delay — for frequencies where the continuum model applies, i.e. well below the bucket Nyquist π/T_w. At 10 Gb/s ω_0 = 140 exceeds that Nyquist and the continuum figure is an extrapolation into the aliased regime.
• The one-sided derivative (the rise term). Replacing the rectifier by its average gain on a sinusoid (a describing function — the standard engineering approximation for such nonlinearities) makes it half of a full derivative feedback, contributing a delayed damping of about ω_0^2 / 8 — 2400 s^-1 at 10 Gb/s.

Compared at the link's own ω_0 — the only fair comparison — the washout delivers (1 - cos ω_0 T_w)/(4 T_w) ≈ ω_0^2 T_w / 8, exactly T_w = 1/32 of the lead's ω_0^2 / 8, at every capacity below the bucket Nyquist: in the describing-function model the lead dominates everywhere, not just at high capacity (and lead-only margins are already generous at the low end: ~114 ms at 10 Mb/s). What the washout actually owns is what the describing function cannot see: the rise term is quantized — ripple smaller than one ece unit between feedbacks fires no lead cut at all — and the whole decrease path is dead while the path is unmarked, whereas the washout runs unconditionally. It is the small-signal and unmarked-phase damping: the backstop that keeps quantization ripple and post-episode ramps from ringing. (This corrects the emphasis of the algorithm document's RTT-behaviour section, which credits the washout with the high-capacity damping.) Balancing the lead against the delay's phase loss gives the margin estimate

 tan(ω_0 τ) ~ ω_0 / 8    =>    ω_0 τ < ~π/2 ,
 i.e.  τ_max ~ (π/2) / ω_0  ∝  1/√C

At 10 Gb/s the describing-function estimate is ~10 ms; simulations of the full fluid model (with amplitude effects, the cut cap, and the washout all live) hold to ~50 ms. The gap between those numbers is precisely the heuristic part. The scaling is on much firmer ground: a double integrator crosses unity gain at ω_0, a delay eats ω_0 τ radians of phase there, and a bounded-phase-lead compensator does not survive past ω_0 τ ~ π/2 plus its lead budget. One escape needs closing: a queue-only sender could respond to m with a smaller gain ε < 1, moving the crossover down to √(ε G) and buying delay margin with standing queue. Mark saturation bounds the escape: equilibrium needs ε m*/M = Σa/C + 1/T with m* ≤ M, so ε ≥ p* and the crossover can drop by at most 1/√p* ≈ 2.5×. Within the class of bounded-lead compensation, then, the 1/√C scaling survives any retuning; a class with unbounded lead (cascaded lead stages buying phase with high-frequency gain) is excluded by assumption, not by proof — which is why the ledger carries this row as conditional rather than proven. That is the algorithm document's √G · τ limit, derived rather than asserted. Removing it would require a rate term in the signal (explicit-rate feedback), which is a design change, not a tuning.

The receiver window enters as a low-pass with ~W/2 of group delay and folds into τ; at high rate W sits at its 1 ms floor and is negligible against the path RTT. The adaptive window's real contribution to stability is at low rate, where it keeps the loop's sampling matched to the flow — the delay-dominated corner the algorithm document describes.

The real system: practical stability

Status: exact point convergence — false. Ultimate boundedness — conditional (the argument is solid; a fully formal hybrid write-up is pending). The width of the residual band — heuristic (order-of-magnitude).

The shipped controller is not an ODE. It differs from the fluid model in ways that are quantized, sampled, and event-driven:

• marks are integers: one ecn step per Q = 4 packets of queue, a price staircase of step 1/16;
• ece is 1/32 fixed point; capacity is quarter-log2 (~19% steps);
• feedback arrives once per receiver window, not continuously;
• the control law runs on packet sends, at most once per millisecond, and the decrease defers up to one control quantum in the sub-ms carry;
• the cut is capped at r/2 per step and the rate is clamped to [r_min, r_max].

Because the price can only take staircase values, it generically cannot equal p* exactly, so no trajectory can come to rest at (C, q*): the system chatters across the marking step that brackets p*, a relay oscillation. Exact asymptotic convergence to a point is therefore false — permanently and harmlessly. The correct notion is practical stability: there is a bounded set around the ideal point that trajectories enter and never leave. The Lyapunov argument survives with the staircase price read as set-valued (its monotonicity was all the cancellation needed), so V still decreases outside a plateau { q : p* between the marking steps at q }; inside it the signal cannot distinguish the queue from q* and a small limit cycle is expected instead of a fixed point. The residual band is

 |q - q*|  ~  Q  +  |r - C| (W + τ) / S       [packets]

one marking quantum plus what the rate ripple writes into the queue per feedback interval. At the defaults this is a few packets of queue ripple at every rate — the same order as the standing queue itself, and rate-uniform thanks to the sub-ms carry (a truncating decrease would inflate the band up to 2x in the 0.2–1 MB/s range and degrade the saturation headroom from N ≤ 27 toward N ≤ 12 in that band).

Three structural facts do hold exactly:

• Slow start terminates. On any path that ever marks, exponential growth reaches the bottleneck in finite time (~T_ss ln(C/r_seed), about 200 ms to 10 Gb/s), the queue builds, a mark arrives, and tx_cav latches permanently. On a path that never marks, the rate parks at the offered-load ceiling or r_max — the documented no-loss-response limitation, outside CA's contract.
• The staleness horizon cannot destabilize the equilibrium. At a marked equilibrium the receiver emits ece every window and the sender's horizon is four windows' worth of bytes at the same rate; feedback outruns expiry by 4x, so the TTL only ever acts after congestion clears, shaping recovery, not steady state.
• Episodes are memoryless. The rise term's memory (tx_ecp) and the decrease carry (dec_acc) both reset when the signal clears, so each congestion episode starts from the same controller state — the hybrid analysis of one episode covers them all.

Claim ledger

The one-table summary; each row is argued in the section referenced.

Claim	Status	Where
Fluid reduction faithful at/near equilibrium (all dropped terms vanish)	proven	model
Decrease integrates exact marked time (≤ 1 control quantum pending)	proven	model
Unique equilibrium r_i* = C a_i/Σa_j, q* = 2N + 8	proven (feasibility: N ≤ 27, clamps interior)	equilibrium
Equilibrium clears the dead zone at every rate	proven (64/T > Q)	equilibrium
Allocation is RTT-independent	proven (τ absent from fixed-point algebra)	equilibrium
The law maximizes Σ(a_i ln r_i + r_i/T), price = queue	proven	optimization
Weighted proportional fairness; equal split = max-min at one link	proven	optimization
Global convergence, zero delay, N aggregates, any continuous nondecreasing marking strictly increasing at the equilibrium level	proven	Lyapunov
Same, single aggregate, by planar phase-plane argument	proven	Dulac
Fairness gap contracts once P > 1/T; asymptotic rate Na/C	proven (zero delay)	fairness
Bare smooth loop (N = 1) unstable beyond τ* = 2S/C	proven (linear)	delay
Washout adds nonnegative damping, peak 1/(2T_w)	proven (continuum model, below the bucket Nyquist)	delay
Lead + washout extend margin to ω_0 τ ~ π/2, τ_max ∝ 1/√C	heuristic (describing function; sims reach ~5x further)	delay
√G · τ scaling is intrinsic to queue-only control	conditional (bounded-lead class; gain floor ε ≥ p* from mark saturation)	delay
Exact convergence to a point, real code	false (quantization)	real system
Convergence into a bounded band around (C, q*)	conditional (formalization pending)	real system
Band width ~ Q + ripple × (W + τ)/S	heuristic	real system
Slow start exits in finite time, once	proven	real system
Staleness TTL inactive at marked equilibrium	proven (arithmetic)	real system

Toward a formal proof

What a journal-grade write-up would add to this document, in order of effort. Items 1–5 are routine for a control theorist — the appendix carries out 4–5 in full, 3 modulo the cited invariance principle for projected systems, and sketches 1–2; 6–7 are real work; 8 is open.

1. Well-posedness. Existence/uniqueness of solutions for the projected (queue ≥ 0) system — standard, the field is Lipschitz and the constraint convex (Filippov solutions).
2. Trapping region. An explicit compact set that all trajectories enter: bounded rates from the saturated cut (dr/dt < 0 for r > ~a/(1 - 1/T) once marks saturate), bounded queue from bounded rates.
3. LaSalle for the projected system — the invariance principle applied with the boundary case written out (this document sketches it).
4. The planar argument with the piecewise-C^1 kinks of P and the q = 0 boundary handled explicitly in the Green's-theorem step.
5. The delay crossing. Root-crossing and transversality (Hopf) for the quasipolynomial — textbook.
6. Averaging. A theorem tying the event-driven, sampled controller to the ODE on the control timescale, with explicit error bounds from the ≤ 1 ms quanta and the once-per-window sampling. This is what turns "the fluid model says" into "the code satisfies, up to ε".
7. Quantization. The set-valued price Lyapunov argument plus a relay-cycle amplitude bound — turns the heuristic band width into a theorem (hybrid-systems machinery; tedious, not deep).
8. Nonlinear delayed stability with washout + lead. The describing function is an approximation with no error bound here. The serious route is absolute-stability / IQC analysis of the rectified derivative (Zames–Falb multipliers for the monotone nonlinearity), or accepting the fluid-model simulations as the certificate. Open in the strict sense.

Limitations of this analysis

In the house tradition: what the mathematics above does not cover.

• Backlogged sources only. The offered-load gating, the source-limited ceiling, and slow-start re-entry are switching behaviors outside the model. The convergence claims are for aggregates that keep the pacer busy.
• Frozen slopes. a_i and r_min,i adapt slowly to the in-band capacity estimate; the analysis freezes them (quasi-static assumption). A formal two-timescale argument would be item 6's sibling.
• One bottleneck. The global theorem is single-link. Multi-link networks change the objective (the linear bias no longer cancels) and no network-wide claim is made. Aggregates keyed to different destinations sharing a hop still converge individually, as the algorithm document notes, at the cost of duplicated probing.
• Heterogeneous delays, dynamically. The equilibrium is delay-independent (proven); the transient with distinct τ_i is analyzed only through the collective mode. Residual unfairness during ripple is bounded by the ripple amplitude times the delay spread — heuristic.
• No loss path. As in the algorithm document: a dropping, non-marking bottleneck is invisible to CA and outside every claim here.
• The SFQ pacer is taken as given. Per-flow fairness inside an aggregate is the scheduler's (deterministic) property; this document only ever analyzes the aggregate rate.

Appendix: formal statements and proofs

Everything here is self-contained given the fluid model. Throughout: U_i'(r) = a_i/r + 1/T, the price curve P : [0, ∞) → [0, 1] is P(q) = min(8q, M)/M unless stated otherwise, and p* = m*/M.

Standing assumptions.

• (A1) Every aggregate is backlogged; a_i > 0 and T > 1 s are constants.
• (A2) Feasibility: Σ_j a_j / C + 1/T < 1.
• (A3) The rate clamps are not binding: r_min,i < r_i* < r_max for all i.
• (A4) Zero feedback delay (Theorem 1 and its corollaries only).

The proofs use P only through: P continuous, nondecreasing, P(q*) = p*, and P^-1(p*) = {q*} — all of which hold for the concrete curve above under (A2), and equally for a dead-zoned variant, since q* ≥ 8 > Q places the equilibrium on the strictly increasing ramp.

Two housekeeping notes. (A3) is not used by the propositions below — the model as written has no clamps; it is the condition under which the clamp-free model is faithful to the code. And well-posedness is taken from the literature: the field is locally Lipschitz and the constraint set {q ≥ 0} convex, so the projected system has unique absolutely continuous solutions with continuous dependence on initial data, and LaSalle's invariance principle holds in this setting (Nagurney–Zhang; Ryan — see references).

Proposition 1 (equilibrium: existence and uniqueness)

Under (A1)–(A2) the fluid model has exactly one equilibrium:

 m* = M ( sum_j a_j / C + 1/T ) < M ,   q* = m*/8 ,   r_i* = C a_i / sum_j a_j

Proof. An equilibrium with q > 0 needs dq/dt = 0, i.e. y = C. Suppose the marking were saturated there (8q ≥ M, price 1). Then dr_i/dt = 0 forces r_i = a_i T/(T - 1), and summing,

 y = T/(T-1) * sum_j a_j  <  T/(T-1) * (1 - 1/T) C  =  C

using (A2) in the middle step — contradicting y = C. So the equilibrium is unsaturated, and dr_i/dt = 0 reads a_i + r_i/T = r_i m/M, which has a positive solution only for m/M > 1/T, namely

 r_i(m) = a_i / ( m/M - 1/T )

Each r_i(m) is continuous and strictly decreasing on (M/T, M), with r_i → ∞ as m ↓ M/T and Σ r_i(M) < C (the display above). Hence Σ_i r_i(m) = C has exactly one root; solving it gives m* as displayed, < M by (A2), and substituting back gives r_i*. On the boundary q = 0 the price is ≤ P(0) = 0, so dr_i/dt ≥ a_i > 0: no equilibrium. Finally q* = m*/8 ≥ 64/T = 8 > Q: the equilibrium clears the marking dead zone. ∎

Proposition 2 (the energy function is valid)

Define

 V(r, q) = sum_i phi_i(r_i) + S * Psi(q)
 phi_i(r) = r - r_i* - r_i* ln(r / r_i*)
 Psi(q)   = integral from q* to q of ( P(s) - p* ) ds

Then V ≥ 0 with equality only at (r*, q*), V is continuously differentiable, and its sublevel sets {V ≤ c} are compact subsets of (0, ∞)^N × [0, ∞).

Proof. phi_i'(r) = 1 - r_i*/r has the sign of r - r_i*, so phi_i is convex with a strict minimum phi_i(r_i*) = 0, and phi_i → ∞ both as r ↓ 0 and r ↑ ∞. For Psi: the integrand P(s) - p* is ≤ 0 for s ≤ q* and ≥ 0 for s ≥ q* (monotonicity of P through P(q*) = p*), so integrating away from q* in either direction gives Psi ≥ 0; Psi(q) = 0 for q ≠ q* would force P ≡ p* between q and q*, contradicting P^-1(p*) = {q*}. For q > M/8 the integrand is the constant 1 - p* > 0, so Psi grows linearly and V is proper (radially unbounded) in every direction. P continuous makes Psi C^1 with Psi' = P - p*. ∎

Theorem 1 (global asymptotic stability, zero delay)

Under (A1)–(A4), every solution of the fluid model with r_i(0) > 0, q(0) ≥ 0 converges to (r*, q*), and the equilibrium is Lyapunov stable.

Proof. Differentiate V along solutions. For the rate terms, using dr_i/dt = r_i (U_i'(r_i) - P(q)):

 d/dt phi_i = (1 - r_i*/r_i) dr_i/dt = (r_i - r_i*) ( U_i'(r_i) - P(q) )

Insert U_i'(r_i) = p* - a_i (r_i - r_i*) / (r_i r_i*) (this is the identity U_i'(r_i) - U_i'(r_i*) = a_i/r_i - a_i/r_i* plus the equilibrium relation U_i'(r_i*) = p*):

 d/dt phi_i = - a_i (r_i - r_i*)^2 / (r_i r_i*)  +  (r_i - r_i*)(p* - P(q))

For the queue term, in the interior q > 0, using C = Σ_j r_j*:

 d/dt [ S Psi ] = ( P(q) - p* ) ( y - C ) = ( P(q) - p* ) sum_i ( r_i - r_i* )

Summing, the two sign-indefinite terms are negatives of each other and cancel exactly, leaving

 dV/dt = - sum_i a_i ( r_i - r_i* )^2 / ( r_i r_i* )  <=  0

with equality if and only if r = r*. On the boundary q = 0 with y < C the projection replaces dq/dt by 0, so the queue term contributes 0 and the uncancelled remainder of the rate terms is (p* - P(0))(y - C) ≤ 0: the reflection only makes dV/dt more negative. So dV/dt ≤ 0 everywhere, on a state space where (Proposition 2) sublevel sets are compact and forward invariant.

By LaSalle's invariance principle — applicable to the projected flow by the well-posedness noted in the standing assumptions — every solution approaches the largest invariant set inside {dV/dt = 0} = {r = r*}. On an invariant subset with r ≡ r*, each dr_i/dt = 0, so P(q(t)) ≡ p*, hence q(t) ≡ q* by P^-1(p*) = {q*}; this is consistent since then dq/dt = (C - C)/S = 0. The largest invariant set is the single point (r*, q*), so every solution converges to it. Stability follows since V is a strict local minimum at the equilibrium and nonincreasing along solutions. ∎

Remark. The proof used only the four bulleted properties of P: continuous, nondecreasing, P(q*) = p*, strictly increasing through that level. Any reshaping that keeps them — dead zone, saturation, a different quantum — leaves the theorem intact with the same V. Mere monotonicity is not enough for the last step: a curve flat exactly at level p* keeps dV/dt ≤ 0 but has a continuum of equilibria {r*} × P^-1(p*), and LaSalle then gives convergence to that set — the fluid preview of the real system's practical stability.

Corollary 1 (fairness contraction)

For equal slopes a_i = a_j = a,

 d/dt ( r_i - r_j ) = ( 1/T - P(q(t)) ) ( r_i - r_j )

exactly, so |r_i - r_j|(t) = |r_i - r_j|(0) exp( ∫_0^t (1/T - P) ); by Theorem 1, P → p* = 1/T + Na/C, so the difference decays exponentially with asymptotic rate Na/C.

Proof. Subtract the two source laws; the a terms cancel and the remainder is linear in the difference. The rest is Theorem 1. ∎

Proposition 3 (no cycles in the plane, N = 1)

For a single aggregate and any continuous nondecreasing price P, the region {r > 0} contains no periodic orbit — including hybrid orbits with a sliding segment on q = 0. If moreover P is locally Lipschitz (the concrete curve is piecewise linear), solutions are unique, and combined with boundedness and Proposition 1 every trajectory converges to the equilibrium.

Proof. Weight the vector field f = (a + r/T - r P(q), (r - C)/S) by B = 1/r:

 div( B f ) = d/dr [ a/r + 1/T - P(q) ] + d/dq [ (r - C)/(S r) ]
            = - a / r^2  +  0   <   0

Note the divergence never needs a derivative of P: the first component loses its q-dependence under d/dr and the second has none. If a periodic orbit Γ enclosed a region D, Green's theorem would give 0 = ∮_Γ B f · n ds = ∫∫_D div(B f) < 0 (the line integral vanishes because f is tangent to its own orbit) — a contradiction. A hybrid loop leaning on the boundary — a rightward sliding segment on q = 0 (sliding needs r < C; the projected flow there is (a + r/T, 0)) closed by an interior arc — falls to the same computation: the interior arc is tangent and contributes nothing, while on the sliding segment, with outward normal (0, -1), the flux is B f · n = (C - r)/(S r) > 0, so the contour integral is strictly positive against a strictly negative area integral. Forward trajectories are bounded (Proposition 2's V is proper and nonincreasing) and the projected flow is a well-posed semiflow (standing assumptions), so the Poincaré–Bendixson trichotomy applies as in the smooth case: each omega-limit set is an equilibrium or a cycle; cycles of both kinds are excluded, and Proposition 1 leaves one equilibrium. ∎

Proposition 4 (the bare delayed loop loses stability at 2S/C)

The linearization of the smooth model at (C, q*) with feedback delay τ,

 s^2 + (a/C) s + G e^(-sτ) = 0 ,     G = 8C/(MS)

is exponentially stable for τ < τ* and unstable for τ > τ*, where τ* = arctan((a/C)/ω_c) / ω_c with ω_c^2 = (√((a/C)^4 + 4G^2) - (a/C)^2)/2; for a/C << √G,

 τ* ≈ (a/C) / G  =  M S / (256 C)  =  2 S / C      (at a = C/32, M = 512)

Proof. At τ = 0 both roots of s^2 + (a/C)s + G have real part -a/(2C) < 0. Roots can only enter the right half plane through the imaginary axis; setting s = iω, ω > 0, and separating real and imaginary parts:

 G cos(ωτ) = ω^2 ,     G sin(ωτ) = (a/C) ω

Squaring and adding: G^2 = ω^4 + (a/C)^2 ω^2, so ω ≈ √G when a/C << √G (true at every capacity of interest: 1/32 vs ≥ 4.4). Dividing: tan(ωτ) = (a/C)/ω, whose first solution is ωτ* ≈ (a/C)/√G, i.e. τ* ≈ (a/C)/G. Substituting a = C/32 and G = 8C/(MS) gives τ* = MS/(256C). Two facts complete the dichotomy: s = 0 is never a root (G > 0), and every crossing is rightward — implicit differentiation of the characteristic equation gives Re(ds/dτ) a numerator (a/C)^2 ω^2 + 2ω^4 > 0 — so stability, once lost at τ*, is lost for every larger τ. ∎

Remark. For the collective mode of N equal aggregates, replace a by Na: τ* = 2NS/C, so the lone aggregate is the worst case. Proposition 4 is the negative result that frames the whole delay story: it proves the smooth law's own damping budget is a/C, worth microseconds of delay tolerance at gigabit capacity, and therefore that the real controller's delay robustness must come entirely from the washout and the one-sided derivative — the terms outside this appendix's reach, analyzed by describing function and simulation in the delay section.

References

Source

• src/ipcpd/unicast/ca/mb-ecn.c — rate law (mb_ecn_increase, mb_ecn_decrease, mb_ecn_washout), receiver estimator, pacer.
• src/ipcpd/unicast/ca/tests/mb_ecn_test.c — pins the constants and invariants used above (incl. test_mb_ecn_decrease_subms_carry for the exact-time property).
• doc/mb-ecn.mediawiki — the algorithm document; notation and parameter table shared with this one.

Literature

• F. Kelly, A. Maulloo, D. Tan, "Rate control for communication networks: shadow prices, proportional fairness and stability", J. Oper. Res. Soc., 1998. The primal source law and the utility framework.
• R. Srikant, "The Mathematics of Internet Congestion Control", Birkhäuser, 2004. Primal/dual/primal-dual taxonomy, Lyapunov constructions of the type used here.
• S. Low, F. Paganini, J. Doyle, "Internet Congestion Control", IEEE Control Systems Magazine, 2002. Survey; queue-as-price models.
• J. Wen, M. Arcak, "A unifying passivity framework for network flow control", IEEE Trans. Automatic Control, 2004. The passivity pairing behind the cross-term cancellation.
• H. Khalil, "Nonlinear Systems", 3rd ed., Prentice Hall, 2002. Lyapunov theory, LaSalle, practical stability / ultimate boundedness.
• L. Perko, "Differential Equations and Dynamical Systems", Springer. Bendixson–Dulac and Poincaré–Bendixson.
• A. Filippov, "Differential Equations with Discontinuous Righthand Sides", Kluwer, 1988. Solutions of the projected / staircase system.
• A. Nagurney, D. Zhang, "Projected Dynamical Systems and Variational Inequalities with Applications", Kluwer, 1996. Well-posedness of the projected (queue ≥ 0) dynamics.
• E. P. Ryan, "An integral invariance principle for differential inclusions with applications in adaptive control", SIAM J. Control Optim., 1998. LaSalle in the nonsmooth / projected setting.
• G. Zames, P. Falb, "Stability conditions for systems with monotone and slope-restricted nonlinearities", SIAM J. Control, 1968. The multiplier route to item 8.