Subject: [tsvwg] Slides to support discussion of draft-ietf-tsvwg-rfc6040shim-update

From: Bob Briscoe <[email-masked]>
Date: Wed, 8 Apr 2020 14:54:55 +0100

tsvwg chairs, (David, Gorry, Wes) & tsvwg list,

I've produced 4 slides that might be useful to support the fragment 
reassembly discussion on draft-ietf-tsvwg-rfc6040shim-update
http://bobbriscoe.net/presents/2004ietf/2004rfc6040update-shim.pdf

Bob

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/

---

From: Jonathan Morton <[email-masked]>
Date: Wed, 8 Apr 2020 19:30:39 +0300

> On 8 Apr, 2020, at 4:54 pm, Bob Briscoe <[email-masked]> wrote:
> 
> I've produced 4 slides that might be useful to support the fragment reassembly discussion on draft-ietf-tsvwg-rfc6040shim-update

I'd like to get out ahead of the main discussion over the fragment reassembly semantics, because these slides contained some analysis of that problem which I believe to be erroneous.  I was going to mention this during the meeting, but David Black rightly pushed this topic off to mailing list discussion.

It's also worth remembering that this discussion is technically off-topic for rfc6040shim-update, since the latter is supposed to be dropping fragment reassembly semantics as out of scope.  But I think I should present an alternative analysis now, so that we can converge on the truth more quickly.

The analysis as presented appears to proceed along the following lines:

1: CE marking is modelled as a uniform, steady-state probability over all packets, regardless of packet size or AQM type.

2: Traffic sources utilising different packets sizes are contrasted as to fragmentation behaviour when encountering a tunnel, and their packet rate for constant throughput, both on the tunnel path and after reassembly.  Specifically, 1500 byte packets are fragmented into full and runt packets, 1480 byte packets are not fragmented and have the same origin packet rate, and 750 byte packets are not fragmented but have twice the packet rate.

3: There is a well-known equation relating Reno average cwnd to marking probability, and another relating segment size, cwnd (in segments) and RTT to flow throughput.  This is applied to find the relative behaviour of the above traffic sources when experiencing the same, uniform marking probability, somewhere on the tunnel path.

4: Another scenario involving an FQ-AQM is presented, in which the throughput of each flow is equalised and the marking rate and probability calculated from that.  It is pointed out, unsurprisingly, that these end up being different for each flow.

5: The conclusion is explicitly drawn that RFC-3168's existing rule for preserving CE marks on fragment reassembly "is broken".  Implied is an assertion that it needs to be materially changed.

Steps 2, 3, and 4 appear (at first glance) to be sound.  However, the modelling assumption in step 1 is flawed, and I think this torpedoes the conclusion.

The central assumption is that all AQMs mark packets with uniform probability, including those which calculate a timebase marking schedule (eg. Codel) instead of a marking probability (eg. RED).  The analysis as presented is valid only for the latter case.

When timebase marking is in use, the relative sizes of the packets being considered for marking becomes relevant.  A runt fragment of 40 bytes occupies the head position in the queue (where Codel does its marking) for a different length of time than the full 1500-byte fragments either side of it, and this strongly influences the relative probability of it being marked.  Likewise a stream of 750-byte packets will each spend only half the time at the queue head as an otherwise similar stream of 1500-byte packets, so their probability of marking is halved in the same timebase schedule.

Therefore, it is incorrect to convert a timebase marking rate to a uniform marking probability, when packets of significantly different sizes are involved.  A different analysis must therefore be run to establish the effect of a shared timebase AQM on the tunnel path.

Another implicit assumption is that AQMs apply a static marking rate (in whichever paradigm they choose) over a timescale of many seconds.  In fact, they typically react to changes in queue depth over timescales of milliseconds.  This has the effect of concentrating marking events on the flows with highest throughput at the moment congestion occurs, at the peak of each flow's sawtooth.  This is a further factor which may invalidate the assumption of uniform marking probability, even for probabilistic AQMs.

I hope the above will help to inform the main discussion about RFC-3168 semantics, when that is taken up.

 - Jonathan Morton

---

From: "Holland, Jake" <[email-masked]>
Date: Wed, 8 Apr 2020 17:37:20 +0000

I added a link to David's previous on-list advice to the etherpad meeting
notes, even though I didn't think it worth bringing to the queue in
realtime:
https://mailarchive.ietf.org/arch/msg/tsvwg/V_l4laD6ECKz3oinwy4UOPmatBM/

The salient point being:

(From David):
"Note to the wise: It would be unwise to assume that such a new draft
will proceed without discussion or controversy - e.g., as fragmentation
is a mechanism whose use is generally discouraged unless there is no
viable alternative, questions will inevitably arise about how much IETF
time and effort should be devoted a mechanism that the IETF would likely
deprecate if we could.

A wise WG participant will review draft-ietf-intarea-frag-fragile before
responding to this note to the wise (hint) - see
https://datatracker.ietf.org/doc/draft-ietf-intarea-frag-fragile/.  That
draft is IESG-approved to become a BCP (Best Current Practice), and is
currently in the RFC Editor Queue."

I thought this might be an especially useful point to highlight for anyone
newly considering joining the discussion on this topic after seeing the
presentation, so I thought I'd also raise it early in this thread, in hopes
it's helpful to someone.

Best regards,
Jake

On 4/8/20, 6:56 AM, "Bob Briscoe" <[email-masked]> wrote:

    
    Bob

---

From: Bob Briscoe <[email-masked]>
Date: Thu, 9 Apr 2020 00:04:40 +0100

Jonathan,

> Therefore, it is incorrect to convert a timebase marking rate to a uniform marking probability, when packets of significantly different sizes are involved.  A different analysis must therefore be r…

I had looked at the code to check this. When a timer fires, it's the 
/next/ packet to reach the head that gets marked. Not the one being 
dequeued when the timer fires. Usually two fragments will get onto the 
wire back to back, with the runt behind. Then, what happens depends on 
if it's FQ or shared queue, and of course on the specifics of 
implementations, but in general:

* If FQ, the likelihood of marking a runt vs a full-size fragment will 
be roughly the inverse of their sizes (e.g. 40/1540 for the larger 
packets and 1500/1540 for the runts). Then RFC3168 reassembly will still 
roughly double the marking probability for fragmented flows vs 
non-fragmented.

* If shared queue, the runts are more likely to be marked than any other 
packet, because they will generally follow their larger sister fragment. 
The relative likelihood of marking of the rest of the packets will 
depend on how much of the packet mix are fragments. If there's a decent 
amount of non-fragments, the marking probability for the rest of the 
packets will be at least 'fairly equal' to each other.

.....
However, this is all beside the point. This just argues that the effects 
I have laid out will not be quite as pronounced as the simple 
approximations I have used. But the effects will still be there.
* None of what you've said argues /for/ preserving the time of each 
marking during reassembly.
* None of what you've said argues /against/ preserving probability 
rather than timing.

With shared buffers:
* Preserving probability will remove the unfairness effects.
* Preserving timing will tend to have some degree of unfairness effects.

With per-flow scheduling:
* There are (obviously) no unfairness effects anyway.
* The reason I put up the FQ example wasn't fairness, it was to 
illustrate that there is nothing special about the particular time 
between one mark and the next - because flows B&C with identical average 
packet sizes and packet rates converge on different times between marks.

Do you have an argument /for/ preserving the time when individual marks 
occur, given it causes unfairness in shared queue AQMs (even if not to 
the degree my simple calculations have predicted)?

If you haven't got such an argument, it would be helpful if you could 
say so. Then we can move on.

> Another implicit assumption is that AQMs apply a static marking rate (in whichever paradigm they choose) over a timescale of many seconds.  In fact, they typically react to changes in queue depth o…

During a dynamic episode of higher congestion, the fragmented packets 
will still end up with a higher incidence of marking, than if they had 
been identical but non-fragmented packets.

You're not arguing for time-preserving reassembly any more. You're 
picking on second order issues with my approximations. Please try to 
stay focused on the question at hand.

> I hope the above will help to inform the main discussion about RFC-3168 semantics, when that is taken up.

That argument is happening here and now. There's no point writing a 
draft for a new reassembly RFC, if my arguments are flawed.

Bob

---

From: Jonathan Morton <[email-masked]>
Date: Thu, 9 Apr 2020 15:01:38 +0300

Taking the last point first:

> That argument is happening here and now. There's no point writing a draft for a new reassembly RFC, if my arguments are flawed.

What you clearly plan to ask for in that draft is a change to the handling of CE upon reassembly, to a method that is explicitly forbidden by the existing (nearly 20 year old) specification which has been widely implemented.  I think you will not obtain WG consensus for that.  You would need to present compelling and incontrovertible evidence that the existing behaviour is inherently harmful, but the argument presented so far is not that strong.

Separately, if the WG decides that ECT(1) should become an output from the network, then a tightening of the language around reassembly of mixed ECN codepoints will be called for.  I'm willing to take on that task if that is more appropriate.

> I had looked at the code to check this. When a timer fires, it's the /next/ packet to reach the head that gets marked. Not the one being dequeued when the timer fires.

Since we're reading implementation code, may I direct your attention to the "dropping" flag in the Codel state vector, and the code which sets and clears it?  Marking only occurs when that flag is set, but it is cleared as soon as the queue drains.

Which means that when subjected to traffic with the typical AIMD sawtooth, there are relatively short periods with a non-zero marking rate, interspersed with relatively long periods with no marking.  And this is also true for most probability-based AQMs.  This is crucial to understanding why the timing of marks is the important factor to preserve, not the overall probability.  It is dynamic behaviour that is poorly modelled by a static probability, as I pointed out yesterday.

We can confirm this by observing that your exemplar marking rates are one per 1.7 seconds, or less often than that.  But at default settings, the lowest marking frequency in Codel is 10 per second, so in these conditions Codel spends about a 16:1 ratio of time in the quiescent state; the 1.7 second marking rate comes entirely from the period of the sawtooth, not from any characteristic of the AQM.  The "fat flow" then only requires a single CE mark to drain the queue.  An FQ-AQM is designed to ensure that signal goes to the correct flow immediately; with a single queue and single AQM, this occurs probabilistically.

> Usually two fragments will get onto the wire back to back, with the runt behind. Then, what happens depends on if it's FQ or shared queue, and of course on the specifics of implementations, but in general:
> 
> * If FQ, the likelihood of marking a runt vs a full-size fragment will be roughly the inverse of their sizes (e.g. 40/1540 for the larger packets and 1500/1540 for the runts). Then RFC3168 reassembly will still roughly double the marking probability for fragmented flows vs non-fragmented.
> 
> * If shared queue, the runts are more likely to be marked than any other packet, because they will generally follow their larger sister fragment. The relative likelihood of marking of the rest of the packets will depend on how much of the packet mix are fragments. If there's a decent amount of non-fragments, the marking probability for the rest of the packets will be at least 'fairly equal' to each other.

I'm glad you're thinking at this level of detail, for once.

It's possible to imagine a Codel implementation which corrects for this effect, by looking ahead into the serialisation time of the packet currently under consideration.  Reference Codel doesn't do this, because it doesn't know the transmission rate of the link.  It's something I could theoretically add to my own qdiscs, because they have built-in rate shapers and can therefore calculate the serialisation time.

A probabilistic AQM could multiply its marking probability by the size of the packet to achieve a similar correction.  Does PIE or PI2 do this?  I'm pretty sure it isn't a standard RED feature.

These fixes presuppose that correcting this effect is worthwhile.  It might be.  But consider the following point, again derived from your own example:

To maintain equal throughput, the fragmented 1500-byte flow and the unfragmented 1480-byte flow require the same rate of marking, one per 1.7 seconds.

The unfragmented 750-byte flow requires marks half as often, on a quarter of the fraction of its packets; the period of its sawtooth is twice as long because each CE mark removes twice as many segments from the cwnd, which are replenished at the same rate of one per RTT.  (This appears to show an error in your calculations, as you gave a marking frequency of a *quarter* of the others for this flow, as well as a marking probability of a quarter.)

If we assume (as a worst case for the sake of argument) that CE marks are doubled by the reassembly process, then this would correspond to a sqrt(2) reduction in average cwnd and throughput for the affected flow.

But if we were to apply the same marking frequency to that 750-byte flow as to the others, it would run sqrt(2) slower; if we were to apply the same marking *probability* as to the 1480-byte flow, it would run at half speed.  That is what you would get if these flows shared an idealised Codel or probabilistic AQM respectively.

So the notional doubling of CE marks has a smaller effect than that of halving the segment size of a TCP flow - probably the reverse of what you expected.

Moreover, if you did try to compensate for the CE "doubling" effect at reassembly time, by preserving the fraction of marked packets, it means that a fragmented flow would need two CE marks to perform one sawtooth cycle, rather than only one.  A single-queue AQM therefore has a doubled chance of accidentally signalling to the wrong flow as well as the correct one, when the correct flow happens to be fragmented.  This is not the correct result.

> However, this is all beside the point. This just argues that the effects I have laid out will not be quite as pronounced as the simple approximations I have used. But the effects will still be there.
> * None of what you've said argues /for/ preserving the time of each marking during reassembly.
> * None of what you've said argues /against/ preserving probability rather than timing.

I think I have addressed those points above, fairly thoroughly.

> * Preserving timing will tend to have some degree of unfairness effects.

I argue that the reverse is true.  RFC-3168 had good reasons to preserve individual congestion marks at reassembly, and those seem to still be relevant even in this case.

> * The reason I put up the FQ example wasn't fairness, it was to illustrate that there is nothing special about the particular time between one mark and the next - because flows B&C with identical average packet sizes and packet rates converge on different times between marks.

But the reason for the difference in marking frequency is not due to AQM behaviour, but due to the slower growth rate of the flow with the smaller MSS, and thus the slower sawtooth period.  Also, I identified calculation errors in this example.

If you disagree with my analysis here, the best way forward might be to run a practical test to see what the real behaviour is.

> Do you have an argument /for/ preserving the time when individual marks occur, given it causes unfairness in shared queue AQMs (even if not to the degree my simple calculations have predicted)?

The "given" in this question is refuted, so the question is irrelevant.

> During a dynamic episode of higher congestion, the fragmented packets will still end up with a higher incidence of marking, than if they had been identical but non-fragmented packets.

I think, ultimately, we just have to accept this as one of the downsides of using fragmentation.  Perhaps we could even highlight it as an incentive to tunnel vendors to fix their implementations, so that they do not emit fragmented traffic.  And refer to draft-ietf-intarea-frag-fragile.

 - Jonathan Morton