Re: [tsvwg] ECN encapsulation draft - proposed resolution

[Jonathan Morton <[e-mail]>]

> On 3 Jun, 2021, at 2:41 pm, Markku Kojo <kojo=[e-mail]> wrote:
> 
> I'm afraid there is an open/ongoing discussion on this where we have not reached concensus.

I think I agree with your analysis that preserving the number of bytes marked is probably the wrong thing to do.  The implementation complexity argument is fairly compelling in itself, particularly noting that there isn't any known "running code" which would place some upper bound on what the complexity is.

By contrast the RFC-3168 approach of "if any part of the packet is marked, all of it is marked" is very simple to implement, and this is proved by actual implementations in the wild.  This approach is also consistent with the behaviour when ECN is not in use, since if any fragment of a packet is lost, the packet can't be reassembled and is discarded in whole.

I'd like to try and back this position up with some mathematical rigour from a different direction.

One thing I noticed about Bob's position is that he's trying to preserve the number of bytes marked, but usually the transport is actually sensitive to the number of bytes, or possibly the interval of time, *between* marks.  These are two (or three) very different quantities, and it's important not to get them confused in the debate.

In engineering, a very useful tool for checking whether an answer is correct is "dimensional analysis".  Simply put, work out the units that your inputs and outputs are most naturally expressed as, and check that the formulae linking them are consistent with respect to the units.  In this case, we can look at the units of the AQM's marking function, the units of the transport's congestion control steady state criterion, and whether each approach to resolving ECN marks at reassembly preserves the quality of the marking with respect to those units.

For the purpose of this analysis, we are looking for the quantity that is most nearly preserved if we hold the AQM state constant or the transport in steady state, but vary packet size and/or link bandwidth arbitrarily.

Starting with the AQMs:

1: Codel is a time-domain AQM; its marking function is explicitly a frequency, expressed for performance reasons as a time interval between marks.  For analysis, we can equivalently express this quantity in units of marks/sec or its reciprocal, seconds per mark.  If we change the bandwidth or the packet size while holding Codel's control law constant, the number of bytes in marked packets and/or the number of packets between marks will change, but the time between marks will stay constant.

2: A packet-domain marking function (as used in BLUE and many RED-family AQMs) maintains a probability that any given packet will be marked.  Amortised over a large interval, we can express this as a (fractional) number of marks per packet, or equivalently as packets between marks. If the packet rate increases, so will the number of marks per time interval; if the packet size decreases, so will the number of bytes between marks.

3: A byte-domain marking function, as Markku described for early RED work, is obtained by taking a nominally packet-mode probability function, but multiplying the probability by bytes/packet (and a constant scale factor).  The resulting unit is (fractional) marks per byte, or bytes between marks.

Now the transports:

1: DCTCP's steady state is two marks per RTT.  Since RTT has units of time, the steady-state criterion has units of marks/sec.  This is precisely the same as Codel's marking function.

2: Reno's steady state is BDP/2 RTTs per mark, where BDP has units of bytes (the two time terms in the formula cancel).  The steady-state criterion thus has units of byte-seconds per mark.  This does not exactly match any of the AQMs' control laws, but it seems likely that "seconds per mark" or "bytes between marks" would be a better match than "packets between marks".  Regardless, for constant performance with Reno, we would look for methods that preserve the byte-seconds per mark value.

3: CUBIC's steady state, when not in the Reno compatibility regime, is quoted in RFC-8312 as (BDP/MSS) = 1.054 * RTT^0.75 / p^0.75, where p is the (fractional) number of marks per segment, and the quantity BDP/MSS has units of segments.  But each segment, as seen by the transport, is MSS bytes long, and it is ignorant of any fragmentation that might happen at Layer 3 or 2 along the way - so if that occurs, "segments" is not the same as "packets" as seem by the AQM.  So we can convert p into a byte quantity by dividing it by MSS, yielding (BDP/MSS) = 1.054 * (RTT*MSS / p)^0.75. This reveals that for a constant cwnd, a constant byte-seconds per mark value is required, similar to Reno, and we can probably expect this to be true for other "TCP friendly" congestion controls as well.

So now we can turn to the methods of resolving congestion marks at reassembly.  I'll examine three candidate rules that seem relevant to the debate, though others probably exist:

1: "If any fragment of a packet is marked, the whole packet is marked."  This is the RFC-3168 rule, generalised to also cover the weird Layer 2 fragmentation scheme that sparked this debate.  It is clear that this rule preserves the number of bytes between marks and the time between marks (and therefore also the byte-seconds between marks), but not the number of packets between marks - except for the specific case where a fragment contains portions of more than one packet.  If these packets all belong to the same flow, then this is harmless to Reno and CUBIC since consecutive ECN marks are reported to the sender as a single event.  If multiple flows are involved, then this will stochastically amplify the congestion signal by having more than one flow react to a single mark - which seems tolerable in practice.

2: "Every mark is sacred, every mark is great."  The AQM produces one mark, and exactly one reassembled packet receives that mark; the reassembly process can make a reasonable choice as to which one.  This preserves bytes between marks, time between marks, and byte-seconds between marks *exactly*.

3: "The number of bytes marked should be preserved by reassembly."  This would tend to preserve the number of packets between marks better than the other two options, but that is not useful to any of the transports considered.  The distortion to the bytes between marks and time between marks metrics would be distorted proportionally to the difference between average fragmented and reassembled packet sizes, and the byte-seconds between marks measure would be distorted *quadratically* by that difference.

In summary, the "preserve the number of marked bytes" rule is mathematically unreasonable, as well as being much more complicated to implement than either the existing RFC-3168 rule, or the "sacred mark" rule, which actually preserve the quantities that need to be preserved.

 - Jonathan Morton