Congestion avoidance - Revision history

Dimitri at 22:23, 11 July 2026

2026-07-11T22:23:01Z

← Older revision		Revision as of 22:23, 11 July 2026
Line 16:		Line 16:
	RFC 8174) says, but only where they appear in capitals.		RFC 8174) says, but only where they appear in capitals.

	Note: Co-authered by Claude Fable 5.		Note: Co-authered by Anthropic Claude Fable 5.

	== Notation ==		== Notation ==

Dimitri at 22:22, 11 July 2026

2026-07-11T22:22:48Z

← Older revision		Revision as of 22:22, 11 July 2026
Line 16:		Line 16:
	RFC 8174) says, but only where they appear in capitals.		RFC 8174) says, but only where they appear in capitals.

			Note: Co-authered by Claude Fable 5.

	== Notation ==		== Notation ==

Dimitri at 22:14, 11 July 2026

2026-07-11T22:14:31Z

← Older revision		Revision as of 22:14, 11 July 2026
Line 6:		Line 6:
	in the IPCP, once per layer. Within a layer the IPCP controls		in the IPCP, once per layer. Within a layer the IPCP controls
	'''aggregates''': one control loop per (destination address, QoS cube),		'''aggregates''': one control loop per (destination address, QoS cube),
	shared by every flow to that destination~~. The other policy is~~		shared by every flow to that destination.
	~~<code>nop</code>, which does nothing~~.

	This document is about the algorithm: what it does and why. The		This document is about the algorithm: what it does and why. The

Dimitri at 22:13, 11 July 2026

2026-07-11T22:13:43Z

Show changes

Dimitri at 21:25, 11 July 2026

2026-07-11T21:25:12Z

← Older revision		Revision as of 21:25, 11 July 2026
Line 22:		Line 22:
	== Notation ==		== Notation ==

	;<code>r</code>		{\| class="wikitable"
	:Paced send rate~~, bytes per second.~~		! Symbol !! Units !! Meaning
	;<code>C</code>		\|-
	:Bottleneck capacity~~, bytes per second.~~		\| <code>r</code> \|\| B/s \|\| Paced send rate
	;<code>S</code>		\|-
	:Packet size ~~in bytes.~~		\| <code>C</code> \|\| B/s \|\| Bottleneck capacity
	;<code>q</code>		\|-
	:Standing queue occupancy at the bottleneck~~, in packets.~~		\| <code>S</code> \|\| bytes \|\| Packet size
	;<code>Q</code>		\|-
	:Marking quantum, packets per mark unit (4).		\| <code>q</code> \|\| packets \|\| Standing queue occupancy at the bottleneck
	;<code>ecn</code>		\|-
	:Per-packet congestion mark set by a forwarder~~, an unsigned integer~~		\| <code>Q</code> \|\| packets \|\| Marking quantum: packets per mark unit (4)
	~~(on-wire field is 8~~-~~bit).~~		\|-
	;<code>ece</code>		\| <code>ecn</code> \|\| 8-bit code \|\| Per-packet congestion mark set by a forwarder
	:Receiver-side congestion estimate~~, fixed point with LSB = 1/32~~ of an		\|-
	<code>ecn</code> ~~unit, i.e. <code>ece = 32 × (time~~-~~mean ecn)</code>.~~		\| <code>ece</code> \|\| 32 × ecn \|\| Receiver-side congestion estimate (time-mean of <code>ecn</code>)
	;<code>cap8</code>		\|-
	:Path-capacity ~~code carried per packet~~, quarter-log2:		\| <code>cap8</code> \|\| 8-bit code \|\| Path capacity, quarter-log2: <code>C ≈ 2^(cap8 / 4)</code> B/s, 0 = unknown
	<code>C ≈ 2^(cap8 / 4)</code> ~~bytes~~/s, 0 = unknown.		\|-
	;<code>W</code>		\| <code>W</code> \|\| ns \|\| Receiver averaging window
	:Receiver averaging window~~, nanoseconds.~~		\|-
	;<code>a</code>		\| <code>a</code> \|\| B/s^2 \|\| Additive-increase slope
	:Additive-increase slope~~, bytes/s per second.~~		\|-
	;<code>M</code>		\| <code>M</code> \|\| <code>ece</code> \|\| Full-congestion reference level (512)
	~~:Full-congestion reference level of~~ <code>ece</code> (512).		\|-
	;<code>Δt</code>		\| <code>Δt</code> \|\| ns \|\| Elapsed wall-clock time between two events
	:Elapsed wall-clock time between two events~~, nanoseconds.~~		\|-
	;<code>τ</code>		\| <code>τ</code> \|\| — \|\| Path round-trip time (feedback delay); the controller does not measure it
	:Path round-trip time (feedback delay)~~. The~~ controller does not		\|}
	measure it.

	Rate is the control variable throughout.		Rate is the control variable throughout.

Dimitri: /* 2. Forwarder marking */

2026-07-11T20:46:46Z

2. Forwarder marking

← Older revision		Revision as of 20:46, 11 July 2026
Line 110:		Line 110:
	described here.		described here.

	== 2. Forwarder marking ==		== Forwarder marking ==

	A forwarder marks a packet as a function of the packets already queued		A forwarder marks a packet as a function of the packets already queued
Line 154:		Line 154:
	nothing; since only backlogged hops matter, the signal exists exactly		nothing; since only backlogged hops matter, the signal exists exactly
	when it is needed.		when it is needed.


	== 3. Receiver estimate ==		== 3. Receiver estimate ==

Dimitri: /* 1. Overview */

2026-07-11T20:46:34Z

1. Overview

← Older revision		Revision as of 20:46, 11 July 2026
Line 63:		Line 63:
	__TOC__		__TOC__

	== 1. Overview ==		== Overview ==

	mb-ecn is a rate-based, ECN-driven controller with three moving parts,		mb-ecn is a rate-based, ECN-driven controller with three moving parts,
Line 109:		Line 109:
	aggregate is a scheduler property, distinct from the rate law		aggregate is a scheduler property, distinct from the rate law
	described here.		described here.


	== 2. Forwarder marking ==		== 2. Forwarder marking ==

Dimitri: /* 8. Limitations */

2026-07-11T20:46:20Z

8. Limitations

← Older revision		Revision as of 20:46, 11 July 2026
Line 457:		Line 457:
	fairness across them is capacity-weighted; see		fairness across them is capacity-weighted; see
	[[#8. Limitations\|Section 8]].		[[#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 · 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 — 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>√G · τ</code> with~~
	~~<code>√G &prop; √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 ≥ 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.~~

Dimitri: /* 5.7. Regimes */

2026-07-11T20:45:20Z

5.7. Regimes

← Older revision		Revision as of 20:45, 11 July 2026
Line 383:		Line 383:
	+-------------+ first mark seen +----------------+		+-------------+ first mark seen +----------------+
	\| slow start \|--------------------->\| congestion \|		\| slow start \|--------------------->\| congestion \|
	\| r *= e^(t/T)\| \| avoidance \|		\| r *= e^(t/T)\| \| avoidance \|
	+-------------+ \| \|		+-------------+ \| \|
	\| m == 0 ---> ~~additive increase~~		\| m == 0 -> AI \|
	\| m > 0 ---> ~~AI + PD decrease~~		\| m > 0 -> AIPD \|
	+----------------+		+----------------+
	m = fed-back ece, or the local first-hop mark when ece == 0		m = fed-back ece, or the local first-hop mark when ece == 0
	</pre>		</pre>


	== 6. RTT behaviour ==		== 6. RTT behaviour ==

Dimitri: 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..."

2026-07-11T20:39:27Z

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..."

Show changes