Congestion avoidance: Difference between revisions

From Ouroboros
Jump to navigation Jump to search
No edit summary
Tag: Reverted
(Blanked the page)
Tags: Blanking Manual revert
 
Line 1: Line 1:
{{DISPLAYTITLE:mb-ecn - Convergence Analysis}}


This document says what can be '''proven''' about mb-ecn 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 <code>&radic;G &middot; &tau;</code>, 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: formal statements and proofs|appendix]] states and proves
the core results in full.
== Notation ==
Symbols match the algorithm document; a few are added for the
analysis.
{| class="wikitable"
! Symbol !! Units !! Meaning
|-
| <code>r_i</code> || B/s || Paced rate of aggregate <code>i</code>; <code>y = &Sigma; r_i</code>
|-
| <code>C</code> || B/s || Bottleneck capacity
|-
| <code>S</code> || bytes || Packet size (1000 B in all figures)
|-
| <code>q</code> || packets || Bottleneck standing queue
|-
| <code>Q</code> || packets || Marking quantum (4)
|-
| <code>m</code> || <code>ece</code> units || Congestion signal seen by a sender
|-
| <code>M</code> || <code>ece</code> units || Full-congestion reference (512)
|-
| <code>a_i</code> || B/s^2 || Additive slope of aggregate <code>i</code> (<code>C/32</code> when capacity is live)
|-
| <code>T</code> || s || Probe time constant <code>T_probe</code> (8 s)
|-
| <code>&tau;</code> || s || Feedback (loop) delay, ~ path RTT
|-
| <code>W</code> || s || Receiver averaging window
|-
| <code>T_w</code> || s || Washout bucket (~31 ms)
|-
| <code>p</code> || &ndash; || Price: <code>p = min(8q, M) / M &isin; [0, 1]</code>
|-
| <code>U_i</code> || &ndash; || Utility function of aggregate <code>i</code>
|-
| <code>V</code> || &ndash; || Lyapunov (energy) function
|-
| <code>G</code> || 1/s^2 || Loop gain <code>8C/(MS)</code>; <code>&omega;_0 = &radic;G</code>
|-
| <code>N</code> || &ndash; || Number of aggregates at the bottleneck
|}
Starred quantities (<code>r*</code>, <code>q*</code>, <code>m*</code>,
<code>p*</code>) are equilibrium values.
__TOC__
== The fluid model ==
The analysis works on a continuous-time reduction of the CA regime:
one bottleneck of capacity <code>C</code>, <code>N</code> 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
(<code>mb_ecn_increase</code>, <code>mb_ecn_decrease</code> in
<code>mb-ecn.c</code>): the increase adds <code>a &middot; &Delta;t</code>
and <code>r &middot; &Delta;t / T</code> per elapsed time, the decrease
removes <code>r &middot; mark &middot; &Delta;t_ms / (1000 M)</code>,
which per second is <code>r &middot; m / M</code>. The marking relation
comes from the forwarder (<code>ecn = q/Q</code> with <code>Q = 4</code>)
and the receiver (<code>ece = 32 &times;</code> time-mean of
<code>ecn</code>), so in steady state <code>m = 32 q / 4 = 8 q</code>.
One unit note: the drain term <code>r &middot; min(m, M)/M</code> is
applied per second (the code scales by elapsed milliseconds over
1000), so the dimensionless price of the
[[#What the law optimizes|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 <code>m</code> rises between samples — zero at constant <code>m</code>;
* the washout damps rate ''change'' — zero at constant <code>r</code>;
* the <code>r/2</code> 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: local stability|delay section]].
One implementation detail is load-bearing for exactness: the decrease
scales by whole elapsed milliseconds and '''carries the sub-ms
remainder''' (<code>dec_acc</code> in <code>mb_ecn_decrease</code>).
Because no time is dropped, the applied cut integrates to exactly
<code>&int; r m / M dt</code> over any marked interval, up to one
pending control quantum (&lt; 1 ms). Without the carry the effective
decrease would be <code>&kappa; &middot; r m / M</code> with a
rate-dependent <code>&kappa; &isin; (1/2, 1]</code>, 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 <code>dq/dt = 0</code> forces <code>y* = C</code>. Setting each
<code>dr_i/dt = 0</code> at shared signal <code>m*</code> gives
  r_i* = a_i / (m*/M - 1/T)
which is positive and decreasing in <code>m*</code>. Summing and
equating to <code>C</code> 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 <code>a_i = C/32</code> for all
<code>i</code> and <code>T = 8 s</code>:
  q* = 2 N + 8  packets
two packets per aggregate plus the fixed probe floor — the same
<code>q* = 64 a / r + 64 / T_probe</code> 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:''' <code>m* &lt; M</code>, i.e. <code>&Sigma; a_j / C + 1/T &lt; 1</code>. At <code>a = C/32</code> that is <code>N/32 + 1/8 &lt; 1</code>, so '''N &le; 27''' same-class aggregates. The saturated cut can only hold each rate at <code>(8/7) a_i = C/28</code>: at <code>N = 28</code> those rates sum to exactly <code>C</code> — a degenerate knee with a continuum of neutrally stable saturated states (any <code>q &ge; 64</code>) — and for <code>N &ge; 29</code> the sum exceeds <code>C</code> and the fluid queue grows without bound; no equilibrium either way. Note this is a different constraint from the rate floor: the floor admits <code>N &le; 32</code> flows at <code>r* = C/N &ge; C/32</code>, but mark saturation binds first, so the algorithm document's "about 32 flows fit above the floor" is <code>27</code> in the fluid model — flows 28 through 32 fit above the floor but have no interior equilibrium to sit at.
* '''Above the dead zone:''' <code>q* &ge; 64/T = 8 &gt; Q = 4</code> for ''any'' <code>a &ge; 0</code>. 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 (<code>T &lt; 16 s</code> suffices).
* '''Inside the clamps:''' <code>r_min,i &le; r_i* &le; r_max</code>.
Uniqueness is elementary: <code>&Sigma;_i r_i(m)</code> is continuous
and strictly decreasing in <code>m</code> on the feasible range, so it
crosses <code>C</code> exactly once. On the boundary <code>q = 0</code>
there is no equilibrium because <code>dr_i/dt &ge; a_i &gt; 0</code>
with no marks.
Note what is '''absent''' from every equation above: the delay
<code>&tau;</code>. The equilibrium allocation is RTT-independent as a
theorem, not a slogan — <code>&tau;</code> simply does not appear in
the fixed-point algebra. (Dynamics are another matter; see
[[#Delay: local stability|below]].)
== What the law optimizes ==
'''Status: proven''' (an algebraic identity plus standard convex
duality).
Rewrite the rate law by factoring out <code>r_i</code>:
  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 <code>U_i'</code> identifies the utility:
  U_i(r) = a_i ln r + r/T
strictly concave (<code>U_i'' = -a_i/r^2 &lt; 0</code>). 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 &gt; 0)
which is the price half of Arrow&ndash;Hurwicz primal-dual
(saddle-point) dynamics on the capacity constraint, with a step size
<code>8/(MS)</code> welded to the packet size and marking quantum. The <code>q = 0</code> reflection is exactly the projection
<code>p &ge; 0</code>. 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 <code>a_i</code>. At a single bottleneck the linear <code>r/T</code> terms sum to <code>C/T</code> 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 (<code>a_i = C_i/32</code>) give '''capacity-weighted''' shares — also as documented.
* The equilibrium price must be carried as a '''standing queue''' <code>q* = (M/8) p*</code>; the probe term makes <code>p* &ge; 1/T</code>, 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'' <code>r/T</code>; the single-bottleneck results here do not automatically extend. No network-wide claim is made.
== Global convergence at zero delay ==
'''Status: proven''', for <code>N</code> aggregates, any monotone
marking curve, dead zone and saturation included. Assumptions: zero
feedback delay, backlogged aggregates, frozen <code>a_i</code>,
feasibility as [[#Equilibrium|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 <code>P(s) = min(8s, M)/M</code> is the marking curve. The first
part penalizes rate error (it is zero at <code>r_i = r_i*</code>,
positive elsewhere, and blows up at <code>r_i = 0</code> and
<code>&infin;</code>); the second penalizes queue error (nonnegative
because <code>P</code> is nondecreasing through
<code>P(q*) = p*</code>).
Differentiate along trajectories. The rate part, using
<code>dr_i/dt = r_i (U_i'(r_i) - P(q))</code> and the equilibrium
relation <code>U_i'(r_i*) = p*</code>:
  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 <code>dq/dt = (y - C)/S</code> and
<code>C = &Sigma; r_i*</code>:
  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 <code>P</code> except that the ''same''
<code>P(q)</code> appears in the source law and in the queue term.
The cancellation survives any nondecreasing <code>P</code>; turning
<code>dV/dt &le; 0</code> into convergence '''to the point''' needs
two more properties — <code>P</code> continuous, and strictly
increasing through the level <code>p*</code> — which the dead zone
and the saturation leave intact, since the equilibrium sits on the
open ramp. A curve flat exactly at level <code>p*</code> (the
quantized staircase of the
[[#The real system: practical stability|real system]]) gets only
convergence to the set <code>{r*} &times; P^-1(p*)</code>: 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 <code>P</code>, and the cancellation
would fail.)
Two boundary cases close the argument. On <code>q = 0</code> with
<code>y &lt; C</code> the projection zeroes <code>dq/dt</code> and
<code>dV/dt</code> gains the strictly negative term
<code>p*(y - C)</code> — the reflection only helps. And
<code>dV/dt = 0</code> forces <code>r = r*</code>; the only trajectory
that stays there has <code>P(q) = p*</code>, whose preimage is the
single point <code>q*</code> (the level <code>p*</code> sits strictly
inside the increasing ramp of <code>P</code> by feasibility). By
LaSalle's invariance principle — "the system ends up in the largest
set where the energy stops decreasing" — every trajectory converges to
<code>(r*, q*)</code>. Global asymptotic stability.
=== A second, independent proof for one aggregate ===
'''Status: proven''' (single aggregate only).
With one aggregate the state is the plane <code>(r, q)</code>, and
planar systems admit a stronger tool. The Bendixson&ndash;Dulac
criterion says: if some positive weight <code>B(r, q)</code> makes the
weighted divergence of the vector field one-signed, no periodic orbit
can exist. Take <code>B = 1/r</code>:
  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 <code>P</code> and <code>q</code>, on both branches of
<code>P</code> (ramp and saturation). No cycles, no homoclinic loops. Trajectories are bounded
(properness of <code>V</code>), the equilibrium is unique, so the
Poincar&eacute;&ndash;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
<code>N &gt; 1</code> or to delay.
=== Fairness dynamics ===
'''Status: proven''' (zero delay, equal weights).
Subtracting two source laws with <code>a_i = a_j = a</code> 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 <code>P &rarr; p* = 1/T + N a / C</code>, the difference
eventually contracts at rate <code>N a / C</code> — with
<code>a = C/32</code>, that is <code>N/32</code> 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 <code>P</code> above <code>1/T</code>, and from an
empty queue it first grows, at rate at most <code>1/T</code>. Efficiency
(<code>y &rarr; C</code>) 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
<code>&radic;G &middot; &tau;</code> ''scaling'' is intrinsic.
Linearize the smooth model at <code>(C, q*)</code> and give the price
a delay <code>&tau;</code>:
  d(dr)/dt = -(a/C) dr - (C/M) dm(t - &tau;)
  d(dq)/dt = dr / S ,      dm = 8 dq
Eliminating gives the characteristic equation
  s^2 + (a/C) s + G e^(-s&tau;) = 0 ,    G = 8C/(MS) = &omega;_0^2
Without delay this is a harmonic oscillator with natural frequency
<code>&omega;_0 = &radic;(8C/(MS))</code> — rising with the square root
of capacity — and damping <code>a/C = 1/32 s^-1</code>, i.e. next to
none:
{| class="wikitable"
! Link !! <code>C</code> (B/s) !! <code>G</code> (s^-2) !! <code>&omega;_0</code> (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
  &tau;* &asymp; (a/C) / &omega;_0^2 = M S / (256 C) = 2 S / C    (at a = C/32)
'''two packet serialization times''' — 16 &micro;s at 1 Gb/s. (This
is the <code>N = 1</code> case; the collective mode of <code>N</code>
equal aggregates obeys the same law with
<code>a := &Sigma; a_j</code>, so its bare margin is
<code>2NS/C</code> — 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
<code>G &tau; &asymp; 8 s^-1</code>, 250 times the
<code>a/C = 1/32</code> 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 <code>(1 - e^(-s T_w)) / (4 T_w)</code>, with real part <code>(1 - cos &omega;T_w)/(4 T_w) &ge; 0</code> at every frequency, peaking at <code>1/(2 T_w) &asymp; 16 s^-1</code> at <code>&omega;T_w = &pi;</code> (~100 rad/s). The provable statement is one-sided: at any imaginary-axis crossing the balance becomes <code>G sin(&omega;&tau;) = &omega; (a/C + Re H)</code>, so a nonnegative <code>Re H</code> weakly ''extends'' the crossing delay — for frequencies where the continuum model applies, i.e. well below the bucket Nyquist <code>&pi;/T_w</code>. At 10 Gb/s <code>&omega;_0 = 140</code> 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 <code>&omega;_0^2 / 8</code> — 2400 s^-1 at 10 Gb/s.
Compared at the link's own <code>&omega;_0</code> — the only fair
comparison — the washout delivers
<code>(1 - cos &omega;_0 T_w)/(4 T_w) &asymp; &omega;_0^2 T_w / 8</code>,
exactly <code>T_w = 1/32</code> of the lead's
<code>&omega;_0^2 / 8</code>, 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 <code>ece</code> 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(&omega;_0 &tau;) ~ &omega;_0 / 8    =>    &omega;_0 &tau; < ~&pi;/2 ,
  i.e.  &tau;_max ~ (&pi;/2) / &omega;_0  &prop;  1/&radic;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
<code>&omega;_0</code>, a delay eats <code>&omega;_0 &tau;</code>
radians of phase there, and a bounded-phase-lead compensator does not
survive past <code>&omega;_0 &tau; ~ &pi;/2</code> plus its lead
budget. One escape needs closing: a queue-only sender could respond
to <code>m</code> with a smaller gain <code>&epsilon; &lt; 1</code>,
moving the crossover down to <code>&radic;(&epsilon; G)</code> and
buying delay margin with standing queue. Mark saturation bounds the
escape: equilibrium needs
<code>&epsilon; m*/M = &Sigma;a/C + 1/T</code> with
<code>m* &le; M</code>, so <code>&epsilon; &ge; p*</code> and the
crossover can drop by at most
<code>1/&radic;p* &asymp; 2.5&times;</code>. Within the class of
bounded-lead compensation, then, the <code>1/&radic;C</code> 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
[[#Claim ledger|ledger]] carries this row as conditional rather than
proven. That is the algorithm document's
<code>&radic;G &middot; &tau;</code> 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 ~<code>W/2</code> of
group delay and folds into <code>&tau;</code>; at high rate
<code>W</code> 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 <code>ecn</code> step per <code>Q = 4</code> packets of queue, a price staircase of step <code>1/16</code>;
* <code>ece</code> 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 <code>r/2</code> per step and the rate is clamped to <code>[r_min, r_max]</code>.
Because the price can only take staircase values, it generically
'''cannot equal''' <code>p*</code> exactly, so no trajectory can come
to rest at <code>(C, q*)</code>: the system chatters across the
marking step that brackets <code>p*</code>, 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
<code>V</code> still decreases '''outside''' a plateau
<code>{ q : p* between the marking steps at q }</code>; inside it the
signal cannot distinguish the queue from <code>q*</code> and a small
limit cycle is expected instead of a fixed point. The residual band is
  |q - q*|  ~  Q  +  |r - C| (W + &tau;) / 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&ndash;1 MB/s range and
degrade the saturation headroom from <code>N &le; 27</code> toward
<code>N &le; 12</code> 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 (~<code>T_ss ln(C/r_seed)</code>, about 200 ms to 10 Gb/s), the queue builds, a mark arrives, and <code>tx_cav</code> latches permanently. On a path that never marks, the rate parks at the offered-load ceiling or <code>r_max</code> — the documented no-loss-response limitation, outside CA's contract.
* '''The staleness horizon cannot destabilize the equilibrium.''' At a marked equilibrium the receiver emits <code>ece</code> 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 (<code>tx_ecp</code>) and the decrease carry (<code>dec_acc</code>) 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.
{| class="wikitable"
! Claim !! Status !! Where
|-
| Fluid reduction faithful at/near equilibrium (all dropped terms vanish) || proven || [[#The fluid model|model]]
|-
| Decrease integrates exact marked time (&le; 1 control quantum pending) || proven || [[#The fluid model|model]]
|-
| Unique equilibrium <code>r_i* = C a_i/&Sigma;a_j</code>, <code>q* = 2N + 8</code> || proven (feasibility: <code>N &le; 27</code>, clamps interior) || [[#Equilibrium|equilibrium]]
|-
| Equilibrium clears the dead zone at every rate || proven (<code>64/T &gt; Q</code>) || [[#Equilibrium|equilibrium]]
|-
| Allocation is RTT-independent || proven (<code>&tau;</code> absent from fixed-point algebra) || [[#Equilibrium|equilibrium]]
|-
| The law maximizes <code>&Sigma;(a_i ln r_i + r_i/T)</code>, price = queue || proven || [[#What the law optimizes|optimization]]
|-
| Weighted proportional fairness; equal split = max-min at one link || proven || [[#What the law optimizes|optimization]]
|-
| Global convergence, zero delay, N aggregates, any continuous nondecreasing marking strictly increasing at the equilibrium level || proven || [[#Global convergence at zero delay|Lyapunov]]
|-
| Same, single aggregate, by planar phase-plane argument || proven || [[#A second, independent proof for one aggregate|Dulac]]
|-
| Fairness gap contracts once <code>P &gt; 1/T</code>; asymptotic rate <code>Na/C</code> || proven (zero delay) || [[#Fairness dynamics|fairness]]
|-
| Bare smooth loop (<code>N = 1</code>) unstable beyond <code>&tau;* = 2S/C</code> || proven (linear) || [[#Delay: local stability|delay]]
|-
| Washout adds nonnegative damping, peak <code>1/(2T_w)</code> || proven (continuum model, below the bucket Nyquist) || [[#Delay: local stability|delay]]
|-
| Lead + washout extend margin to <code>&omega;_0 &tau; ~ &pi;/2</code>, <code>&tau;_max &prop; 1/&radic;C</code> || heuristic (describing function; sims reach ~5x further) || [[#Delay: local stability|delay]]
|-
| <code>&radic;G &middot; &tau;</code> scaling is intrinsic to queue-only control || conditional (bounded-lead class; gain floor <code>&epsilon; &ge; p*</code> from mark saturation) || [[#Delay: local stability|delay]]
|-
| Exact convergence to a point, real code || false (quantization) || [[#The real system: practical stability|real system]]
|-
| Convergence into a bounded band around <code>(C, q*)</code> || conditional (formalization pending) || [[#The real system: practical stability|real system]]
|-
| Band width <code>~ Q + ripple &times; (W + &tau;)/S</code> || heuristic || [[#The real system: practical stability|real system]]
|-
| Slow start exits in finite time, once || proven || [[#The real system: practical stability|real system]]
|-
| Staleness TTL inactive at marked equilibrium || proven (arithmetic) || [[#The real system: practical stability|real system]]
|}
== Toward a formal proof ==
What a journal-grade write-up would add to this document, in order of
effort. Items 1&ndash;5 are routine for a control theorist — the
[[#Appendix: formal statements and proofs|appendix]] carries out
4&ndash;5 in full, 3 modulo the cited invariance principle for
projected systems, and sketches 1&ndash;2; 6&ndash;7 are real work;
8 is open.
# '''Well-posedness.''' Existence/uniqueness of solutions for the projected (queue &ge; 0) system — standard, the field is Lipschitz and the constraint convex (Filippov solutions).
# '''Trapping region.''' An explicit compact set that all trajectories enter: bounded rates from the saturated cut (<code>dr/dt &lt; 0</code> for <code>r &gt; ~a/(1 - 1/T)</code> once marks saturate), bounded queue from bounded rates.
# '''LaSalle for the projected system''' — the invariance principle applied with the boundary case written out (this document sketches it).
# '''The planar argument''' with the piecewise-C^1 kinks of <code>P</code> and the <code>q = 0</code> boundary handled explicitly in the Green's-theorem step.
# '''The delay crossing.''' Root-crossing and transversality (Hopf) for the quasipolynomial — textbook.
# '''Averaging.''' A theorem tying the event-driven, sampled controller to the ODE on the control timescale, with explicit error bounds from the &le; 1 ms quanta and the once-per-window sampling. This is what turns "the fluid model says" into "the code satisfies, up to &epsilon;".
# '''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).
# '''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&ndash;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.''' <code>a_i</code> and <code>r_min,i</code> 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 <code>&tau;_i</code> 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
[[#The fluid model|fluid model]]. Throughout:
<code>U_i'(r) = a_i/r + 1/T</code>, the price curve
<code>P : [0, &infin;) &rarr; [0, 1]</code> is
<code>P(q) = min(8q, M)/M</code> unless stated otherwise, and
<code>p* = m*/M</code>.
'''Standing assumptions.'''
* '''(A1)''' Every aggregate is backlogged; <code>a_i &gt; 0</code> and <code>T &gt; 1 s</code> are constants.
* '''(A2)''' Feasibility: <code>&Sigma;_j a_j / C + 1/T &lt; 1</code>.
* '''(A3)''' The rate clamps are not binding: <code>r_min,i &lt; r_i* &lt; r_max</code> for all <code>i</code>.
* '''(A4)''' Zero feedback delay (Theorem 1 and its corollaries only).
The proofs use <code>P</code> only through: <code>P</code> continuous,
nondecreasing, <code>P(q*) = p*</code>, and
<code>P^-1(p*) = {q*}</code> — all of which hold for the concrete
curve above under (A2), and equally for a dead-zoned variant, since
<code>q* &ge; 8 &gt; Q</code> 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 <code>{q &ge; 0}</code> 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&ndash;Zhang; Ryan — see
[[#References|references]]).
=== Proposition 1 (equilibrium: existence and uniqueness) ===
''Under (A1)&ndash;(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 <code>q &gt; 0</code> needs
<code>dq/dt = 0</code>, i.e. <code>y = C</code>. Suppose the marking
were saturated there (<code>8q &ge; M</code>, price 1). Then
<code>dr_i/dt = 0</code> forces
<code>r_i = a_i T/(T - 1)</code>, 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 <code>y = C</code>. So
the equilibrium is unsaturated, and <code>dr_i/dt = 0</code> reads
<code>a_i + r_i/T = r_i m/M</code>, which has a positive solution only
for <code>m/M &gt; 1/T</code>, namely
  r_i(m) = a_i / ( m/M - 1/T )
Each <code>r_i(m)</code> is continuous and strictly decreasing on
<code>(M/T, M)</code>, with <code>r_i &rarr; &infin;</code> as
<code>m &darr; M/T</code> and
<code>&Sigma; r_i(M) &lt; C</code> (the display above). Hence
<code>&Sigma;_i r_i(m) = C</code> has exactly one root; solving it
gives <code>m*</code> as displayed, <code>&lt; M</code> by (A2), and
substituting back gives <code>r_i*</code>. On the boundary
<code>q = 0</code> the price is <code>&le; P(0) = 0</code>, so
<code>dr_i/dt &ge; a_i &gt; 0</code>: no equilibrium. Finally
<code>q* = m*/8 &ge; 64/T = 8 &gt; Q</code>: the equilibrium clears
the marking dead zone. &#8718;
=== 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 <code>V &ge; 0</code> with equality only at
<code>(r*, q*)</code>, <code>V</code> is continuously differentiable,
and its sublevel sets <code>{V &le; c}</code> are compact subsets of
<code>(0, &infin;)^N &times; [0, &infin;)</code>.''
''Proof.'' <code>phi_i'(r) = 1 - r_i*/r</code> has the sign of
<code>r - r_i*</code>, so <code>phi_i</code> is convex with a strict
minimum <code>phi_i(r_i*) = 0</code>, and
<code>phi_i &rarr; &infin;</code> both as <code>r &darr; 0</code> and
<code>r &uarr; &infin;</code>. For <code>Psi</code>: the integrand
<code>P(s) - p*</code> is <code>&le; 0</code> for
<code>s &le; q*</code> and <code>&ge; 0</code> for
<code>s &ge; q*</code> (monotonicity of <code>P</code> through
<code>P(q*) = p*</code>), so integrating away from <code>q*</code> in
either direction gives <code>Psi &ge; 0</code>;
<code>Psi(q) = 0</code> for <code>q &ne; q*</code> would force
<code>P &equiv; p*</code> between <code>q</code> and <code>q*</code>,
contradicting <code>P^-1(p*) = {q*}</code>. For
<code>q &gt; M/8</code> the integrand is the constant
<code>1 - p* &gt; 0</code>, so <code>Psi</code> grows linearly and
<code>V</code> is proper (radially unbounded) in every direction.
<code>P</code> continuous makes <code>Psi</code> C^1 with
<code>Psi' = P - p*</code>. &#8718;
=== Theorem 1 (global asymptotic stability, zero delay) ===
''Under (A1)&ndash;(A4), every solution of the fluid model with
<code>r_i(0) &gt; 0</code>, <code>q(0) &ge; 0</code> converges to
<code>(r*, q*)</code>, and the equilibrium is Lyapunov stable.''
''Proof.'' Differentiate <code>V</code> along solutions. For the rate
terms, using <code>dr_i/dt = r_i (U_i'(r_i) - P(q))</code>:
  d/dt phi_i = (1 - r_i*/r_i) dr_i/dt = (r_i - r_i*) ( U_i'(r_i) - P(q) )
Insert <code>U_i'(r_i) = p* - a_i (r_i - r_i*) / (r_i r_i*)</code>
(this is the identity
<code>U_i'(r_i) - U_i'(r_i*) = a_i/r_i - a_i/r_i*</code> plus the
equilibrium relation <code>U_i'(r_i*) = p*</code>):
  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 <code>q &gt; 0</code>, using
<code>C = &Sigma;_j r_j*</code>:
  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 <code>r = r*</code>. On the boundary
<code>q = 0</code> with <code>y &lt; C</code> the projection replaces
<code>dq/dt</code> by 0, so the queue term contributes 0 and the
uncancelled remainder of the rate terms is
<code>(p* - P(0))(y - C) &le; 0</code>: the reflection only makes
<code>dV/dt</code> more negative. So <code>dV/dt &le; 0</code>
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
<code>{dV/dt = 0} = {r = r*}</code>. On
an invariant subset with <code>r &equiv; r*</code>, each
<code>dr_i/dt = 0</code>, so <code>P(q(t)) &equiv; p*</code>, hence
<code>q(t) &equiv; q*</code> by <code>P^-1(p*) = {q*}</code>; this is
consistent since then <code>dq/dt = (C - C)/S = 0</code>. The largest
invariant set is the single point <code>(r*, q*)</code>, so every
solution converges to it. Stability follows since <code>V</code> is a
strict local minimum at the equilibrium and nonincreasing along
solutions. &#8718;
''Remark.'' The proof used only the four bulleted properties of
<code>P</code>: continuous, nondecreasing, <code>P(q*) = p*</code>,
strictly increasing through that level. Any reshaping that keeps them
— dead zone, saturation, a different quantum — leaves the theorem
intact with the same <code>V</code>. Mere monotonicity is not enough
for the last step: a curve flat exactly at level <code>p*</code>
keeps <code>dV/dt &le; 0</code> but has a continuum of equilibria
<code>{r*} &times; P^-1(p*)</code>, and LaSalle then gives
convergence to that set — the fluid preview of the real system's
[[#The real system: practical stability|practical stability]].
=== Corollary 1 (fairness contraction) ===
''For equal slopes <code>a_i = a_j = a</code>,''
  d/dt ( r_i - r_j ) = ( 1/T - P(q(t)) ) ( r_i - r_j )
''exactly, so
<code>|r_i - r_j|(t) = |r_i - r_j|(0) exp( &int;_0^t (1/T - P) )</code>;
by Theorem 1, <code>P &rarr; p* = 1/T + Na/C</code>, so the difference
decays exponentially with asymptotic rate <code>Na/C</code>.''
''Proof.'' Subtract the two source laws; the <code>a</code> terms
cancel and the remainder is linear in the difference. The rest is
Theorem 1. &#8718;
=== Proposition 3 (no cycles in the plane, N = 1) ===
''For a single aggregate and any continuous nondecreasing price
<code>P</code>, the region <code>{r &gt; 0}</code> contains no
periodic orbit — including hybrid orbits with a sliding segment on
<code>q = 0</code>. If moreover <code>P</code> 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
<code>f = (a + r/T - r P(q), (r - C)/S)</code> by
<code>B = 1/r</code>:
  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 <code>P</code>: the
first component loses its <code>q</code>-dependence under
<code>d/dr</code> and the second has none. If a periodic orbit
<code>&Gamma;</code> enclosed a region <code>D</code>, Green's theorem
would give
<code>0 = &oint;_&Gamma; B f &middot; n ds = &int;&int;_D div(B f) &lt; 0</code>
(the line integral vanishes because <code>f</code> is tangent to its
own orbit) — a contradiction. A hybrid loop leaning on the boundary —
a rightward sliding segment on <code>q = 0</code> (sliding needs
<code>r &lt; C</code>; the projected flow there is
<code>(a + r/T, 0)</code>) 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
<code>(0, -1)</code>, the flux is
<code>B f &middot; n = (C - r)/(S r) &gt; 0</code>, so the contour
integral is strictly positive against a strictly negative area
integral. Forward trajectories are bounded (Proposition 2's
<code>V</code> is proper and nonincreasing) and the projected flow is
a well-posed semiflow (standing assumptions), so the
Poincar&eacute;&ndash;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. &#8718;
=== Proposition 4 (the bare delayed loop loses stability at 2S/C) ===
''The linearization of the smooth model at <code>(C, q*)</code> with
feedback delay <code>&tau;</code>,''
  s^2 + (a/C) s + G e^(-s&tau;) = 0 ,    G = 8C/(MS)
''is exponentially stable for <code>&tau; &lt; &tau;*</code> and
unstable for <code>&tau; &gt; &tau;*</code>, where
<code>&tau;* = arctan((a/C)/&omega;_c) / &omega;_c</code> with
<code>&omega;_c^2 = (&radic;((a/C)^4 + 4G^2) - (a/C)^2)/2</code>;
for <code>a/C &lt;&lt; &radic;G</code>,''
  &tau;* &asymp; (a/C) / G  =  M S / (256 C)  =  2 S / C      (at a = C/32, M = 512)
''Proof.'' At <code>&tau; = 0</code> both roots of
<code>s^2 + (a/C)s + G</code> have real part <code>-a/(2C) &lt; 0</code>.
Roots can only enter the right half plane through the imaginary axis;
setting <code>s = i&omega;</code>, <code>&omega; &gt; 0</code>, and
separating real and imaginary parts:
  G cos(&omega;&tau;) = &omega;^2 ,    G sin(&omega;&tau;) = (a/C) &omega;
Squaring and adding: <code>G^2 = &omega;^4 + (a/C)^2 &omega;^2</code>,
so <code>&omega; &asymp; &radic;G</code> when
<code>a/C &lt;&lt; &radic;G</code> (true at every capacity of
interest: <code>1/32</code> vs <code>&ge; 4.4</code>). Dividing:
<code>tan(&omega;&tau;) = (a/C)/&omega;</code>, whose first solution
is <code>&omega;&tau;* &asymp; (a/C)/&radic;G</code>, i.e.
<code>&tau;* &asymp; (a/C)/G</code>. Substituting
<code>a = C/32</code> and <code>G = 8C/(MS)</code> gives
<code>&tau;* = MS/(256C)</code>. Two facts complete the dichotomy:
<code>s = 0</code> is never a root (<code>G &gt; 0</code>), and every
crossing is rightward — implicit differentiation of the
characteristic equation gives <code>Re(ds/d&tau;)</code> a numerator
<code>(a/C)^2 &omega;^2 + 2&omega;^4 &gt; 0</code> — so stability,
once lost at <code>&tau;*</code>, is lost for every larger
<code>&tau;</code>. &#8718;
''Remark.'' For the collective mode of <code>N</code> equal
aggregates, replace <code>a</code> by <code>Na</code>:
<code>&tau;* = 2NS/C</code>, 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
<code>a/C</code>, 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: local stability|delay section]].
== References ==
=== Source ===
* <code>src/ipcpd/unicast/ca/mb-ecn.c</code> — rate law (<code>mb_ecn_increase</code>, <code>mb_ecn_decrease</code>, <code>mb_ecn_washout</code>), receiver estimator, pacer.
* <code>src/ipcpd/unicast/ca/tests/mb_ecn_test.c</code> — pins the constants and invariants used above (incl. <code>test_mb_ecn_decrease_subms_carry</code> for the exact-time property).
=== 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&auml;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&ndash;Dulac and Poincar&eacute;&ndash;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 &ge; 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.''

Latest revision as of 22:23, 19 July 2026

Retrieved from "https://ouroboros.rocks/mediawiki/index.php?title=Congestion_avoidance&oldid=1949"