[Cake] Explicit Load Regulation - was: Control theory and congestion control

[Jonathan Morton]

> On 11 May, 2015, at 14:34, Jonathan Morton <chromatix99 at gmail.com> wrote:
> 
> I’m also now thinking about how to approximate fairness between ELR flows *without* flow isolation.  Since ELR would aim to provide a continuous signal rather than a stochastic one, this is actually a harder problem than it sounds; naively, a new flow would stay at minimum cwnd as long as a competing flow was saturating the link, since both would be given the same up/down signals.  There might need to be some non-obvious properties in the way the signal is provided to overcome that; I have the beginnings of an idea, but need to work it out.

And the result of a good wander is that I think we can, in fact, use the distinction between ECT(0) and ECT(1) to perform this signalling, and therefore we don’t need to somehow find extra bits in the IP headers.  This might take a little while to explain:

When an ELR flow is negotiated by the endpoints, senders set ECT(1) on all relevant packets they originate.  Since most ECN senders currently set ECT(0), and those that use ECT(1) at all tend to alternate between ECT(0) and ECT(1), routers are able to assume with sufficient safety that an ECT(1) packet can be used to carry an ELR signal, and that an ECT(0) packet belongs to a legacy ECN flow.

The “fast down” signal for both ECN and ELR flows is the ECN codepoint set in any packet during one RTT.  This is echoed back to the sender by the receiver, as for legacy ECN.  Compliant senders should halve their congestion window, or perform an equivalent backoff.

In an ELR flow, the ratio of ECT(1) to ECT(0) packets received is significant, and carries the remaining four states of the ELR protocol.  Receivers keep a history of the ECN codepoints in the most recent three data-bearing packets received on the flow.  They echo back to the sender the number of such packets which had ECT(1) set.  The significance of this number is as follows:

0: slow down - sender should perform a small, multiplicative (exponential) backoff in this RTT
1: hold      - sender should not increase send rate in this RTT
2: slow up   - sender may perform only additive (linear) increase in this RTT
3: fast up   - sender may perform multiplicative (exponential) increase (eg. slow start) in this RTT

Since one byte can hold four of these indications, the receiver may indicate a twelve-packet history in this way, allowing for sparse and lost acks.  Senders should perform all of the actions indicated by these signals which have *not* yet been performed, allowing for the possibility of overlap between subsequent signals.

Queues implementing ELR maintain one or more five-state control variables, which may be per flow, per traffic class or global, and reflect the queue's opinion of whether senders associated with each control variable may increase, should hold or should decrease their send rates (and how quickly) in order to match link capacity, or a fair share thereof, at that queue.  In most cases, there will be at most one queue on a given network path for which this opinion is not “may increase rapidly”; this is known as the bottleneck queue.

In the “may increase rapidly” state, the queue performs no modifications to the ECN field.

In the “may increase gradually” state, the queue changes one out of every three ECT(1) packets to ECT(0), and leaves all other packets unchanged.

In the “should hold” state, the queue changes two out of every three ECT(1) packets to ECT(0), and leaves all other packets unchanged.

In the “should decrease gradually” state, the queue changes all ECT(1) packets to ECT(0), and additionally changes some proportion of originally ECT(0) packets to the ECN codepoint, and drops the same proportion of Not-ECT packets.

In the “should decrease rapidly” state, all of the actions performed in “should decrease gradually” state are performed, but also ECT(1) packets are changed to the ECN codepoint at the same rate as ECT(0) packets.

It should be obvious that these five states correspond precisely to the “fast up”, “slow up”, “hold”, “slow down” and “fast down” signals observed by the receiver of a single flow.  Thus an ELR-compliant queue implementing flow isolation is able to precisely control the send rates of each flow passing through it.

The behaviour of multiple flows sharing a single ELR queue with a single control variable is more complex.  Consider the case where one ELR flow is established on the link, and has stabilised in the “hold” state, when a new ELR flow begins.  After the new flow’s initial congestion window is sent and acknowledged, it will also see the same two-out-of-three ECT(0) pattern (on average) as the established flow, and might then appear to be stuck in the “hold” state with its initial congestion window for all subsequent traffic.

However, packets for the new flow will disrupt the regular pattern of the established flow’s ELR signal, and vice versa, resulting in a stochastic distribution of “slow down” and “slow up” signals actually being received by both flows.  The resulting low-amplitude AIMD behaviour should result in the congestion windows of the two flows converging, eventually giving fair sharing of the link.  While convergence time and sensitivity to RTT are both inferior to a flow-isolating queue, they should be no worse than for conventional AQM queues.

 - Jonathan Morton