Congestion avoidance: Difference between revisions

From Ouroboros
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:mb-ecn - Multi-bit ECN Congestion Avoidance}} mb-ecn is a congestion-avoidance (CA) policy for the Ouroboros unicast IPCP. It lives in the IPC Process: the flow-and-retransmission task (FRCP) provides reliability, in-order delivery and flow control end-to-end; congestion avoidance is orthogonal and runs per IPCP layer. Within a layer, the IPCP controls '''aggregates''', one loop per (destination address, QoS cube), shared by every flow toward that destina...")
 
(Blanked the page)
Tag: Blanking
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:mb-ecn - Multi-bit ECN Congestion Avoidance}}


mb-ecn is a congestion-avoidance (CA) policy for the Ouroboros unicast
IPCP. It lives in the IPC Process: the flow-and-retransmission task
(FRCP) provides reliability, in-order delivery and flow control
end-to-end; congestion avoidance is orthogonal and runs per IPCP
layer. Within a layer, the IPCP controls '''aggregates''', one loop
per (destination address, QoS cube), shared by every flow toward that
destination. The alternative policy is <code>nop</code> (no congestion
avoidance).
This document describes the algorithm: what the policy does and why.
The implementation follows it ([[#12. References|Section 12]] maps the
pieces to source files). It does not claim properties the algorithm
does not have; [[#8. Limitations|Section 8]] states the known gaps
explicitly.
The keywords "MUST", "SHOULD", "MAY" etc. are used only where they
appear in all capitals, per BCP 14 (RFC 2119, RFC 8174).
== Notation ==
;<code>r</code>
:Paced send rate, bytes per second.
;<code>C</code>
:Bottleneck capacity, bytes per second.
;<code>S</code>
:Packet size in bytes.
;<code>q</code>
:Standing queue occupancy at the bottleneck, in packets.
;<code>Q</code>
:Marking quantum, packets per mark unit (4).
;<code>ecn</code>
:Per-packet congestion mark set by a forwarder, an unsigned integer
(on-wire field is 8-bit).
;<code>ece</code>
:Receiver-side congestion estimate, fixed point with LSB = 1/32 of an
<code>ecn</code> unit, i.e. <code>ece = 32 &times; (time-mean ecn)</code>.
;<code>cap8</code>
:Path-capacity code carried per packet, quarter-log2:
<code>C &asymp; 2^(cap8 / 4)</code> bytes/s, 0 = unknown.
;<code>W</code>
:Receiver averaging window, nanoseconds.
;<code>a</code>
:Additive-increase slope, bytes/s per second.
;<code>M</code>
:Full-congestion reference level of <code>ece</code> (512).
;<code>&Delta;t</code>
:Elapsed wall-clock time between two events, nanoseconds.
;<code>&tau;</code>
:Path round-trip time (feedback delay). The controller does not
measure it.
Rate is the control variable throughout.
All concrete figures in this document &mdash; window bounds, horizons,
rate thresholds &mdash; are instances of the parameter values in
[[#11. Parameters|Section 11]]. The mechanisms and the relations
between parameters are what the algorithm fixes; retuning the
parameters moves the figures together.
__TOC__
== 1. Overview ==
mb-ecn is a rate-based, ECN-driven controller with three moving parts,
one at each point of the loop:
<pre>
        sender                                  forwarder
      +--------------------------------+      +--------------------------+
      |  SFQ virtual-clock pacer      |      |  ecn = MAX(ecn, queue/Q) |
      |  rate r, paced per packet      | data  |  (deepest queue wins)    |
      |  AIMD + PD control on r        |------>|  cap8 = MIN(cap8, link)  |
      +--------------------------------+      +--------------------------+
                ^                                        |
                | ece + cap8 feedback                    | marked data
                |                                        v
      +--------------------------------+      +--------------------------+
      |  reads downstream ece,        |<------|  receiver                |
      |  updates the rate on feedback, |  ece  |  time-mean of ecn over  |
      |  scales floor/slope to cap8    |  cap8 |  an adaptive window      |
      +--------------------------------+      +--------------------------+
</pre>
# The '''forwarder''' marks each packet with a ''multi-bit'' magnitude
  proportional to its standing queue, and MIN-stamps its measured
  outgoing-link capacity into the same PCI.
# The '''receiver''' turns the stream of marks into a time-averaged
  congestion estimate <code>ece</code> and feeds it back to the sender,
  together with the window minimum of the path-capacity codes.
# The '''sender''' paces its rate with a start-time fair-queuing (SFQ)
  virtual clock, and adjusts that rate with additive-increase /
  multiplicative-decrease (AIMD) driven by <code>ece</code>; the rate floor
  and the additive slope derive from the fed-back path capacity.
The controller runs on packet sends and on feedback arrivals. All
increase/decrease steps are scaled by elapsed
wall-clock time, which is what makes the ''allocation'' independent of
RTT (see [[#6. RTT behaviour|Section 6]]).
The unit of control is the '''aggregate''', kept in the IPCP per
<code>(destination address, QoS cube)</code>. Every flow toward that
destination at that QoS shares one controller and one rate: a new
flow joins the aggregate at its current rate, and a departing flow
leaves the rate to the others. The pacer divides the aggregate rate
fairly across the member flows (SFQ), so per-flow fairness within an
aggregate is a scheduler property, distinct from the rate law
described here.
== 2. Forwarder marking ==
A forwarder marks a packet as a function of the packets already queued
on the outgoing link:
  mark = queued / Q                        (Q = 4 packets)
  ecn  = MAX(ecn, mark)                    (saturating, 8-bit field)
The quantum <code>Q</code> is a layer-wide constant: the marks it
quantizes are combined by MAX across hops, so all forwarders in a
layer MUST use the same quantum for the signal to be comparable.
Two properties:
* '''Multi-bit magnitude.''' The mark is an integer proportional to
  queue depth, quantized in steps of <code>Q</code> packets: a coarse
  readout of the standing queue.
* '''MAX along the path.''' A packet crossing several forwarders carries
  the maximum mark, i.e. the deepest queue on its path. MAX keeps the
  signal range-stable and monotone across hops.
There is a '''dead zone''': for <code>queued < Q</code> the mark is 0.
=== Capacity stamping ===
Each forwarder also measures the capacity of its outgoing link and
stamps it into the packet. The estimate is a busy-period drain rate:
the queue is observed at most once per millisecond, and a measurement
window stays open until 16 packets have drained, so its length
'''self-scales with the link rate''' &mdash; the millisecond cadence
bounds it on fast links, the 16-packet drain time on slow ones
(~19 ms at 10 Mbit/s). A window in which more than 1/8 of
the arrivals found the queue empty is discarded as unsaturated;
occasional empty observations (token-bucket shapers grazing zero) are
tolerated. The drain rate of a saturated queue is the link rate; a max
filter with slow decay (1/16 per window) converges on it from below. A
window that opened or closed on an empty queue may have drained into
buffers below at above-wire rate, so it may lower the estimate but
never raise it. The code on the wire is quarter-log2
(<code>cap8 = 4 log2 C</code>, ~19% per step, 0 = unknown) and each hop
MIN-combines its own code into the byte, so a packet arrives carrying
the bottleneck's rate. A hop that has never been backlogged stamps
nothing; since only backlogged hops matter, the signal exists exactly
when it is needed.
== 3. Receiver estimate ==
The receiver converts marks into a smoothed estimate <code>ece</code> over a
time window <code>W</code> that '''adapts to the incoming byte rate'''. It is
a '''boxcar (rectangular) time-integral mean'''. Per packet, with
<code>&Delta;t</code> the gap since the previous packet:
  A += ecn * MIN(&Delta;t, W)              dwell-weighted; one packet
                                          weighs at most one window
  B += S                                  accumulate bytes this window
  ...
  at window close (elapsed >= W, or B >= 2 * B_target with at
                  least the window floor elapsed):
      ece = 32 * A / elapsed              mean over the actual window
      W  += (B_target * elapsed / B - W) / 4    nudge toward the size
                                                that holds the target
      W  = clamp(W, ~1.05 ms, ~4.3 s)
      A  = 0 ; B = 0                    hard reset
At each close the next window is nudged by a quarter-weight moving
average toward the size that would hold about 16 packets at the
measured byte rate, from an initial ~67 ms. The target is byte-based (<code>B_target</code> = 16,000 bytes), so
"16 packets" is exact only at ~1000-byte packets, and the window
converges to it over several closes. The mean always divides by the
'''actual''' elapsed window, so a rate step leaves the current
estimate exact and only re-sizes the ''next'' window. The effect is a roughly constant sample
count &mdash; ~16 packets &mdash; from about 30 kbit/s to 122 Mbit/s;
above that the window floors at ~1 ms (a cadence still carrying
thousands of samples at 10&ndash;100 GbE), and below ~30 kbit/s it
saturates at the ~4.3 s ceiling. The averaging clock stretches with
the flow the way TCP's ACK clock stretches with the RTT. A speed-up
escapes a stretched window early: once twice the target bytes arrive
the window closes anyway (the window floor keeps that cadence bounded
at high rate). The fed-back <code>ece</code> is thus a piecewise-constant
staircase whose step period tracks the rate. Two edge cases:
* '''Onset''' (first mark after an idle estimate) emits the
  instantaneous mark undiluted, so a starting queue is reported without
  a full window of delay.
* '''Gap''' longer than 4 windows resets the window and emits the raw
  sample. The threshold is '''rate-relative''': idle means a few
  ''current'' windows of silence, so a slow flow's normal inter-packet
  gap never reads as idle, while the in-window dwell clamp above bounds
  what a genuine pause can add to the mean before the restart fires.
Alongside the mark integral, the receiver keeps the MIN of the nonzero
capacity codes seen in the current window; each emitted <code>ece</code>
carries that minimum (the raw packet's code on onset/gap restarts) and
the fold then resets, so a reroute to a faster path can raise the
fed-back capacity within one window.
The estimate is fed back to the sender on the reverse flow.
== 4. Sender pacer ==
The sender paces with an SFQ virtual clock. The context keeps a
virtual time <code>V</code>; each flow keeps a finish tag <code>F</code>:
  V    += r * &Delta;t                    virtual time advances by bytes served
  s    = MAX(F, V)                  a packet behind the clock starts now
  F    = s + S                      the one after it queues behind
  wait  = (s - V) / r                time until this packet may go
The <code>wait</code> becomes the flow's scheduling deadline: a packet
already behind the virtual clock is sent immediately
(<code>wait = 0</code>); one ahead waits, deferring only its own flow.
A clock advance across an idle gap longer than 50 ms credits at most
the calling flow's owed lead plus one burst (50 ms of service, at
least one packet): a paced flow slower than one packet per 50 ms
receives its '''true''' elapsed service &mdash; a time-capped credit
would decay such a flow without bound &mdash; while an idle flow still
cannot bank an unbounded burst.
The virtual time <code>V</code> is shared by every flow in the context;
the finish tags are per flow. Because every flow computes its start
tag <code>s</code> against the same <code>V</code>, a flow that has just sent
carries a finish tag ahead of <code>V</code> and waits, while an idle flow
(finish tag at or behind <code>V</code>) starts immediately &mdash; this is
what fairly divides the aggregate rate <code>r</code> across them.
== 5. Rate control (AIMD + PD) ==
The rate law runs on packet sends, at most once per millisecond, and
also on feedback arrivals so that a sender with no traffic of its own
still reacts. Each increase term and the proportional decrease are
scaled by elapsed wall-clock time, each by its own clock: the
increase terms use time banked and '''capped''' at 50 ms (an idle gap
cannot bank an unbounded ramp), while the proportional decrease uses
the '''uncapped''' elapsed time (a starved sender still cuts by the
right amount). The one-sided derivative (Section 5.3) is a per-delta
term.
=== 5.1. Slow start ===
Before the first congestion signal the rate ramps exponentially with a
20 ms time constant:
  r += r * &Delta;t / T_ss                  (T_ss = 20 ms)
Slow start ends the first time a congestion signal arrives &mdash;
fed back from the receiver or observed at the sender's own first hop
&mdash; and never resumes.
Slow start belongs to the aggregate, so it runs '''once per
(destination, QoS cube)''', on the first flow. A flow arriving at an
established aggregate rides the existing estimates: it enters at the
aggregate's current rate and receives its fair share of it through
the pacer (Section 4), with no probing of its own.
=== 5.2. Increase: additive plus proportional probe (always on) ===
Past slow start, two increase terms are applied every step, both
regardless of congestion:
  r += a * &Delta;t                        additive; a defaults to 2^16 B/s^2
  r += r * &Delta;t / T_probe              proportional; T_probe = 8 s
The additive term is a fixed per-context slope (bytes/s per second),
scaled to the path capacity (Section 5.5). The proportional probe
grows the rate by a fixed fraction per unit time (e-folds over
<code>T_probe</code>): a flow recovers in the same number of steps at any
link rate; the fixed additive term's effect vanishes relative to a
fast link. Both are the "probing"
pressure the multiplicative decrease balances at equilibrium; the
probe's cost is a rate-independent standing-queue floor (Section 7).
=== 5.3. Multiplicative decrease (proportional + derivative) ===
With congestion level <code>m</code> (the fed-back <code>ece</code>, or a local
first-hop mark as fallback), the decrease is the sum of a proportional
term and a one-sided derivative term &mdash; a PD controller on the
congestion signal:
  mark = MIN(m, M)                                  M = 512
  rise = MAX(m - m_prev, 0), capped at M            one-sided derivative
  cut  = r * rise / (4 * M)                          derivative, gain 1/4
  cut += r * mark * &Delta;t_ms / (1000 * M)              proportional
  cut  = MIN(cut, r / 2)                            at most a halving
  r    -= cut
  m_prev = m
* The '''proportional''' term is scaled by honest elapsed time in
  milliseconds, so a starved sender that has not run the controller
  for a while still cuts by the right amount.
* The '''derivative''' term (<code>rise</code>) reacts to an ''increase'' in
  the congestion level between samples; it is one-sided and per-delta.
  It sharpens the reaction at the onset of congestion.
* The cut is clamped to <code>r/2</code> per step, bounding the decrease to
  a halving.
<code>M = 512 = 32 &times; 16</code> defines "full congestion" as a mean
<code>ecn</code> of 16, i.e. a mean queue of <code>16 &times; Q = 64</code> packets.
=== 5.4. Staleness ===
Feedback arrives once per receiver window, and the window stretches
with the flow's byte rate (Section 3) &mdash; so the staleness horizon
must stretch with it, or a slow flow's mark would age out ''between''
feedbacks and the rate would ramp against a congested path. The
sender mirrors the receiver: the horizon is four target windows of
bytes at the current rate, floored at ~268 ms so fast flows keep a
fixed horizon; at the default rate floor it is ~8 s. A signal older
than the horizon is aged out (both the fed-back estimate and the
local mark), freeing the rate to ramp once congestion clears. The
rate is clamped to
<code>[r_min, r_max]</code> on every step.
=== 5.5. Capacity-derived floor and slope ===
The fed-back capacity code sets the two rate-scale constants of the
controller, per context:
  target = decode(cap8) / 32              clamped to [2^13, 2^32] B/s
  r_min += (target - r_min) / 2          per feedback (moving average)
  a      = r_min
The defaults are fixed constants (<code>r_min = 2^13 B/s</code>,
<code>a = 2^16 B/s^2</code>), used on paths that never report a capacity;
with the estimator live the fairness floor and the post-cut recovery
slope scale with the bottleneck, and capacity engages wherever
<code>C/32</code> clears the default floor, i.e. above ~2 Mbit/s. A
capacity older than 16 staleness horizons (~4.3 s for fast flows)
reverts both to the defaults. That horizon deliberately outlives the
feedback horizon: feedback stops the moment the marks clear, which is
exactly when the recovery slope is needed; the onset-fresh capacity
(Section 3) re-seeds it on the first mark of the next episode either
way.
=== 5.6. Ramp and recovery ===
Three mechanisms set how fast an aggregate reaches a fast link's
rate, each owning one regime:
* '''From scratch: slow start.''' The exponential ramp reaches any
  physical link rate in well under a second (~200 ms from the seed to
  10 Gbit/s; each further doubling of link speed costs one more
  ~14 ms doubling time). On an uncongested path nothing marks, so
  slow start runs until the aggregate arrives at its bottleneck.
* '''After a cut: the probe.''' A decrease is at most a halving per
  step, and the mark ages out on the rate-relative horizon once
  congestion clears (Section 5.4); the proportional probe then heals
  a halving in <code>T_probe &middot; ln 2 &asymp; 5.5 s</code> at any
  link rate.
* '''At the bottom: the capacity floor.''' The rate sits at most a
  factor 32 below a measured bottleneck, and the additive slope
  refills <code>C/32</code> per second, so the deepest hole is bounded:
  floor to full capacity in tens of seconds, a halving in seconds.
These compose because a deep cut requires sustained congestion,
sustained congestion backlogs the bottleneck queue, and a backlogged
queue is exactly when its capacity is measured and stamped
(Section 2): whenever the controller is cut deep, the scaled floor is
live. The default floor only governs paths that never congested the
sender &mdash; where there is nothing to recover from. This is why
slow start can end for good: the floor and the probe cover every
later recovery.
=== 5.7. Regimes ===
<pre>
  +-------------+  first mark seen    +----------------+
  | slow start  |--------------------->|  congestion    |
  | r *= e^(t/T)|                      |  avoidance    |
  +-------------+                      |                |
                                        | m == 0 ---> additive increase
                                        | m  > 0 ---> AI + PD decrease
                                        +----------------+
    m = fed-back ece, or the local first-hop mark when ece == 0
</pre>
== 6. RTT behaviour ==
Because every increase and decrease is scaled by wall-clock time,
two flows of different RTT that share a bottleneck obey the ''same''
rate law and converge to the ''same'' rate. The steady-state
'''allocation is RTT-independent'''.
This is a property of the equilibrium, not of the dynamics. The
feedback delay in the loop ''is'' the path RTT <code>&tau;</code>, and the
controller does not measure or compensate for it. At low rate the
receiver window (up to its ~4.3 s ceiling) is the dominant lag &mdash;
the loop is slow there in proportion to how slow the flow is, exactly
as a long-RTT TCP is &mdash; while as the rate rises the window shrinks
toward its ~1 ms floor, so the window's contribution to the loop delay
''falls'' with capacity and the path RTT <code>&tau;</code> becomes the
irreducible term. Two mechanisms keep the loop damped: the adaptive
window removes the delay-dominated corner at low <code>&tau;</code>, and a
bucketed '''rate-velocity damping''' (a washout: each ~31 ms bucket
pulls the rate a quarter of the way back toward its value at the
previous bucket) supplies the damping the otherwise
near-double-integrator lacks, which is what holds the loop together at
high capacity and moderate <code>&tau;</code>. What remains is the loop gain
<code>&radic;G &prop; &radic;C</code>: at very high capacity ''and'' large
<code>&tau;</code> the <code>&radic;G &middot; &tau;</code> phase budget is the
binding constraint, and no window or damping trick removes it (see
[[#8. Limitations|Section 8]]). A precise statement is therefore:
'''RTT-fair in equilibrium, and dynamically stable up to a
capacity-dependent RTT limit set by <code>&radic;G &middot; &tau;</code>.'''
== 7. Fairness ==
At equilibrium the two increase terms balance the proportional
decrease, <code>a + r/T_probe = r &middot; m*/M</code>, which pins the
congestion level to <code>m* = M &middot; (a/r + 1/T_probe)</code> and, since
<code>ece = 8q</code> (one mark unit per <code>Q = 4</code> packets, 32 fixed-point
steps per unit), a standing queue of
  q* = 64 * a / r  +  64 / T_probe        (packets, r in bytes/s)
The additive part (<code>64 &middot; a / r</code>) vanishes with rate under
the default slope; with the capacity-derived slope (<code>a = C/32</code>,
Section 5.5) it becomes <code>2 C / r</code> &mdash; about two packets per
competing flow, rate-independent. The proportional-probe part
(<code>64 / T_probe</code>) is a rate-independent floor (~8 packets at
8 s). That floor is the cost of rate-independent convergence, and it
keeps <code>q*</code> above the marking threshold at high rate.
Two flows at the same bottleneck see the same <code>m*</code>, so each
solves <code>r_i = a / (m*/M - 1/T_probe)</code> to the same rate. Under
the network-utility-maximization view this corresponds to
'''proportional fairness''' (equal weights), which is max-min fair at
a single bottleneck.
Measurement fidelity at low rate comes from the estimator itself:
the averaging window stretches with the flow
(Section 3), so a CA-limited flow keeps ~16 packets per window at any
rate down to ~30 kbit/s, and the rate-relative gap threshold keeps its
inter-packet spacing from reading as idle. The default floor
(<code>2^13</code> B/s) only bounds the extremes (window ceiling,
staleness horizon, pacer arithmetic). The floor scales with the
fed-back path capacity (<code>r_min = C/32</code>, Section 5.5), so
roughly 32 CA-limited flows fit above it at any link class. Flows
whose paths differ in bottleneck class derive different slopes, so
fairness across them is capacity-weighted; see
[[#8. Limitations|Section 8]].
== 8. Limitations ==
These are properties the algorithm does '''not''' have. They are
listed so the policy is not credited with more than it does.
* '''Queue-only signal; no bandwidth/rate term.''' The reference
  <code>M</code> is a queue level, so mb-ecn is a standing-queue
  controller: it must build a queue (<code>q* = 64 &middot; a / r +
  64 / T_probe</code>) to see any signal, and cannot hold high utilization
  at an empty queue the way a controller with a rate/bandwidth estimate
  can. The proportional-probe floor (~8 packets) keeps <code>q*</code>
  above the marking threshold at all rates, at the cost of a persistent
  standing queue.
* '''Aggregation is per destination, per QoS cube.''' The aggregate
  stands in for the path: flows toward the same destination are
  assumed to share their bottleneck, and flows toward different
  destinations keep independent loops even when they queue at the
  same hop. Each such loop converges to its own fair share
  (Section 7), so the cost is duplicated state and probing at the
  shared queue rather than unfairness. A future option is to identify
  the queue in the packet: a forwarder stamping a queue identifier
  alongside its mark would let senders key their aggregates on the
  actual bottleneck rather than on the destination, pooling the
  estimate and the probing across everything that queues there.
* '''Capacity is learned, with gaps.''' The floor and slope scale with
  an in-band path-capacity estimate (Sections 2, 5.5), but the estimate
  has limits of its own. A hop only learns its link rate while its
  queue is backlogged, so a rerouted or freshly established bottleneck
  contributes ''unknown'' at first and the path MIN can transiently
  come from faster hops (the sender's smoothing and the next feedback
  bound the excursion). The drain measurement is order-of-magnitude by
  design: quarter-log2 code (~19% per step), burst noise bounded by a
  16-packet minimum window and a max filter, nothing learned below
  ~120 packets per second of busy drain (16 packets inside the
  ~134 ms staleness cap; at MTU that is ~1.4 Mbit/s, below which
  capacity/32 would sit under the default floor anyway). The derived
  floor clamps to <code>[2^13, 2^32]</code> B/s, and flows with
  different path bottlenecks get capacity-weighted, not equal, shares
  at a common queue (Section 7).
* '''The low end trades reactivity, not correctness.''' Below
  ~30 kbit/s the averaging window clips at its ~4.3 s ceiling and
  holds fewer samples; below ~64 kbit/s of offered load an
  ''app-limited'' flow spaces packets past the gap threshold and rides
  the raw onset branch, as it always did. Feedback cadence and the
  staleness horizon at the floor are seconds &mdash; a slow flow
  converges slowly, TCP-style; nothing diverges, but nothing is fast
  either.
* '''No loss response.''' The controller reacts only to ECN marks. Loss
  is handled by FRCP retransmission, out of the CA's view. At a bottleneck
  that drops instead of marking (e.g. a classic drop-tail queue at the
  Ethernet/UDP shim), mb-ecn sees no signal and additive increase keeps
  ramping. mb-ecn is intended for Ouroboros-native bottlenecks where the
  forwarder marks; it does not implement a classic-bottleneck fallback.
* '''Dynamic stability has a capacity-dependent RTT limit.''' As stated
  in Section 6, the allocation is RTT-independent but the dynamics are
  not: the binding constraint is <code>&radic;G &middot; &tau;</code> with
  <code>&radic;G &prop; &radic;C</code>. The adaptive window and the washout push
  this limit out substantially (e.g. a single flow at 10 GbE stays stable
  to ~50 ms RTT in the fluid model), but the extreme long-fat-network
  corner (100 GbE at &ge; 50 ms) is not reachable by a window/damping
  controller and would need explicit-rate signalling.
* '''Fluid-model caveat.''' The offline model in the simulation tooling
  captures the aggregate rate law (sawtooth, standing queue) with a
  boxcar receiver, but sizes the adaptive window in the rate domain
  rather than the byte-folded form of the algorithm above, and treats
  all flows identically, so it is a guide to stability ''trends'', not
  a fairness or exact-quantitative oracle at high link rate.
== 9. Architectural fit ==
Each property the preceding sections build toward attaches to a
structural feature of the recursive architecture. This section makes
the mapping explicit.
* '''Congestion avoidance is fully orthogonal to ARQ and to flow
  control.''' Three concerns, three mechanisms, two scopes: FRCP
  provides retransmission (ARQ) and flow control (the peer pacing the
  sender) end-to-end, per flow; congestion avoidance runs in the
  IPCP, per aggregate. Each signal means one thing. A loss triggers
  a retransmission and nothing else &mdash; a lossy link reads as
  lossy, with the congestion verdict left to the marks (Section 8's
  "no loss response" is this orthogonality stated from the other
  side). The peer's flow-control window paces the endpoint and
  nothing else &mdash; back-pressure from a slow receiver stays
  distinct from congestion in the network. A retransmitted packet is
  ordinary traffic to the pacer. TCP folds all three into one window
  machine, where the receive window bounds the congestion window and
  loss serves as both reliability trigger and congestion signal;
  here each mechanism can be reasoned about, tested and evolved
  alone.
* '''Congestion avoidance sits below application choice.''' Every
  flow in the layer is paced by the same rate law, whatever its QoS:
  a greedy raw sender shares a bottleneck fairly with a reliable
  stream because the control is a property of the layer, on the
  aggregate, rather than a courtesy of the endpoint transport.
* '''A layer defines its own PCI, so the signal can be rich.'''
  Every member of a layer is enrolled into it: the layer is a single
  administrative domain by construction, at whatever scope it spans,
  and its header is layer-internal. Forwarders therefore write a
  multi-bit queue magnitude and a capacity byte directly into the
  packet. The datacenter schemes of
  [[#10. Heritage and positioning|Section 10]] require exactly such a
  domain and find it only inside one operator's fabric; a recursive
  layer supplies it everywhere.
* '''Layer-internal addressing makes the aggregate well-defined.'''
  Flows in a layer run between layer addresses, so the
  (destination, QoS cube) aggregate &mdash; RFC 3124's macroflow
  &mdash; falls out of the naming structure. Controller state scales
  with destinations, and each QoS cube keeps its own loop, so
  service classes keep separate fates.
* '''Flows are allocated, so feedback has a channel.''' Every flow
  has state at both ends and a reverse direction; the receiver's
  <code>ece</code> and the path capacity ride the flow allocator's
  existing exchange.
* '''There is no transport ack clock, and none is relied on.''' The
  layer must control raw flows, which carry no acknowledgements at
  all, so the controller paces on wall-clock time &mdash; and that
  constraint yields the RTT-independent allocation of Section 6. An
  architectural restriction becomes the controller's distinguishing
  property.
* '''Recursion scales the scheme.''' Each layer controls congestion
  over its own scope and timescale; many N-flows ride one N-1 flow,
  so aggregation compounds down the stack. The capacity a layer
  measures at its egress queue is the rate the layer below actually
  provides &mdash; a paced, shared lower flow rather than a nominal
  wire speed &mdash; so the signal stays meaningful at every level,
  and pushback cascades layer by layer.
The fit has a boundary: at a shim over legacy media the layer below
neither enrolls nor marks, which is the deployment edge behind
Section 8's no-loss-response limitation.
== 10. Heritage and positioning ==
mb-ecn is best understood as a rate-based ECN controller in the DECbit /
QCN line, adapted to an acknowledgement-less recursive layer.
The core of the scheme dates to the first Ouroboros
congestion-avoidance policy (2020): a multi-bit queue-depth mark
relayed by forwarders to the receiver, a smoothed multi-bit
<code>ece</code> fed back on the reverse flow at the same 1/32 fixed
point used today, and a sender that paced packets from a time budget
and ran slow start, additive increase and multiplicative decrease on
wall-clock time slots &mdash; rate-based and acknowledgement-free from
the start, with RTT-independent allocation already an objective. The
present algorithm keeps that skeleton and reworks every estimator
around it: per-path aggregation with SFQ pacing, the rate-adaptive
boxcar receiver, elapsed-time-scaled AIMD with a derivative term and
rate-velocity damping, and the in-band capacity signal.
* '''DECbit''' (Ramakrishnan &amp; Jain, 1988; ToCS 1990) established
  binary congestion feedback set by the switch on queue occupancy.
  mb-ecn keeps the switch-sets-on-queue idea and carries a
  ''magnitude''.
* '''The Congestion Manager''' (Balakrishnan et al., SIGCOMM 1999;
  RFC 3124, 2001) aggregates congestion state at the end host: one
  controller per macroflow, a scheduler apportioning its rate across
  the member streams, and new streams joining at the ensemble's
  current state instead of probing from scratch. mb-ecn's
  (destination, QoS cube) aggregate is the same idea placed inside
  the IPCP: every layer manages its own macroflows, recursively, the
  SFQ pacer plays the CM scheduler's role (Section 4), and a joining
  flow rides the aggregate's estimates (Section 5.1). The CM gathers
  its signal from transport feedback at the edge; mb-ecn reads it
  off the wire from the forwarders.
* '''DCTCP''' (Alizadeh et al., SIGCOMM 2010) recovers a queue
  magnitude at the endpoint by averaging a single threshold bit. mb-ecn
  instead reads the magnitude off the wire, then time-averages it at
  the receiver. The additive-increase / proportional-decrease structure
  is shared.
* '''QCN''' (IEEE 802.1Qau, 2010) and '''DCQCN''' (Zhu et al., SIGCOMM
  2015) contribute the rate-based (not window-based) ECN control
  skeleton. mb-ecn's proportional decrease plus a probing increase
  mirrors that skeleton; the increase here is wall-clock scaled rather
  than byte-counter/timer based.
* '''HPCC''' (Li et al., SIGCOMM 2019) and '''PowerTCP''' (Addanki et
  al., NSDI 2022) combine a queue term ''and'' a rate term (via in-band
  telemetry or delay). mb-ecn now carries a coarse in-band rate (the
  quarter-log2 path MIN, Section 2) but uses it only to scale the
  controller's gains; the congestion ''signal'' remains queue-only,
  which is still the main functional difference (Section 8).
* '''L4S / TCP Prague''' (RFC 9330&ndash;9332, 2023) make
  RTT-independence a requirement and use a high-frequency single-bit
  signal. mb-ecn shares the RTT-independent ''allocation'' goal but
  reaches it by wall-clock-scaled rate control, with a low-frequency
  multi-bit signal.
The novel combination is the multi-bit magnitude on the wire fused with
a wall-clock-scaled rate pacer in a setting with no per-flow ack clock.
The trade-off, made explicit above, is a queue-only signal and a
reactivity capped by the averaging window.
== 11. Parameters ==
These are the values every figure in this document instantiates. They
are '''coupled''': the mechanisms compose only while certain relations
hold &mdash; the gap-restart horizon at the rate floor must exceed a
packet's service time (or a floor-rate flow restart-loops at onset),
a floor-rate flow's target window must fit under the window ceiling,
the control interval must sit under the damping bucket under the idle
credit cap, the rate floor must not exceed the slow-start seed, and
the derived-floor ceiling must stay under the rate ceiling. Retune
them as a set, against those invariants.
{| class="wikitable"
! Parameter !! Value !! Meaning
|-
| Marking quantum <code>Q</code> || 4 packets || Mark onset and step; layer-wide
|-
| Feedback resolution || 1/32 <code>ecn</code> unit || Fixed-point LSB of <code>ece</code>
|-
| Full-congestion reference <code>M</code> || 512 || Mean queue of 64 packets
|-
| Receiver window target || 16 packets (16,000 bytes) || Samples per window
|-
| Initial receiver window || ~67 ms || Before rate is known
|-
| Receiver window bounds || ~1.05 ms &ndash; ~4.3 s || Clamp on <code>W</code>
|-
| Window resize weight || 1/4 || Moving average toward target
|-
| Early window close || 2 &times; target bytes || Speed-up escape
|-
| Gap restart || 4 windows || Idle horizon (rate-relative)
|-
| Additive slope <code>a</code> (default) || 2^16 B/s^2 || Lower clamp of derived slope
|-
| Probe time constant <code>T_probe</code> || 8 s || Rate-proportional recovery
|-
| Derivative gain || 1/4 || Onset sharpening
|-
| Rate floor <code>r_min</code> (default) || 2^13 B/s || Lower clamp of derived floor
|-
| Slow-start seed rate || 2^16 B/s || Initial rate
|-
| Slow-start time constant || 20 ms || Exponential ramp
|-
| Rate ceiling <code>r_max</code> || 2^37 B/s || Upper clamp
|-
| Capacity scale || <code>C</code> / 32 || Floor and slope from bottleneck
|-
| Capacity smoothing || 1/2 || Moving average per feedback
|-
| Capacity staleness || 16 &times; feedback horizon || Revert to defaults
|-
| Derived floor ceiling || 2^32 B/s || Upper clamp on derived floor
|-
| Control interval || 1 ms || Minimum spacing of rate updates
|-
| Idle credit cap || 50 ms || Burst allowance / increase banking
|-
| Feedback staleness floor || ~268 ms || Floor of rate-relative horizon
|-
| Damping bucket || ~31 ms || Rate-velocity washout cadence
|-
| Damping fraction || 1/4 || Pullback per bucket
|-
| Estimator fold spacing || 1 ms || Minimum measurement cadence
|-
| Estimator window closure || 16 packets drained || Self-scaling window
|-
| Estimator window staleness || ~134 ms || Discard across traffic gaps
|-
| Estimator idle tolerance || 1/8 of arrivals || Unsaturated-window rejection
|-
| Estimator decay || 1/16 per window || Max-filter convergence from below
|}
== 12. References ==
=== 12.1. Source ===
The implementation follows the algorithm above:
* <code>src/ipcpd/unicast/ca/mb-ecn.c</code>, <code>mb-ecn.h</code> &mdash;
  receiver estimator, pacer and rate control.
* <code>src/ipcpd/unicast/ca/ops.h</code> &mdash; CA policy interface.
* <code>src/ipcpd/unicast/cap.c</code>, <code>cap.h</code> &mdash; link-capacity
  estimator and quarter-log2 codec.
* <code>src/ipcpd/unicast/dt.c</code>, <code>fa.c</code> &mdash; per-hop marking
  and stamping, and the feedback carrying <code>ece</code> + <code>cap8</code>.
* <code>src/ipcpd/unicast/psched.c</code> &mdash; consumes the pacing deadline.
=== 12.2. Literature ===
* K. K. Ramakrishnan, R. Jain, "A Binary Feedback Scheme for Congestion
  Avoidance in Computer Networks" (DECbit), ACM ToCS, 1990.
* H. Balakrishnan, H. S. Rahul, S. Seshan, "An Integrated Congestion
  Management Architecture for Internet Hosts", SIGCOMM 1999;
  H. Balakrishnan, S. Seshan, "The Congestion Manager", RFC 3124, 2001.
* M. Alizadeh et al., "Data Center TCP (DCTCP)", SIGCOMM 2010.
* Y. Zhu et al., "Congestion Control for Large-Scale RDMA Deployments"
  (DCQCN), SIGCOMM 2015.
* R. Mittal et al., "TIMELY: RTT-based Congestion Control", SIGCOMM 2015.
* Y. Li et al., "HPCC: High Precision Congestion Control", SIGCOMM 2019.
* V. Addanki et al., "PowerTCP", NSDI 2022.
* K. De Schepper, B. Briscoe (eds.), "Low Latency, Low Loss, and
  Scalable Throughput (L4S)", RFC 9330/9331/9332.
* F. Kelly, "Charging and Rate Control for Elastic Traffic", 1997;
  R. Srikant, "The Mathematics of Internet Congestion Control", 2004.

Latest revision as of 09:13, 12 July 2026

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