Re: [tsvwg] ECN encapsulation draft - proposed resolution

[Markku Kojo <[e-mail]>]

Bob,

In order to make some progress with this discussion I'll try to take us on 
the same page to begin with as it seems to me I was (again) not able to 
make the point clear on what is important to Standards Track congestion 
control. Please focus on the simplest case, that is, the case of a single 
flow using Standards Track congestion control. That hopefully helps in 
understanding the importance of timing when marking/droping packets.

First, I believe we agree the following:

1.
When the sending bit-rate for a small packet sender is the same as 
for a large packet sender, an AQM using probabilistic packet mode 
dropping/marking will result in dropping/marking more small 
packets(/frames) than large packets(/frames) because random marking 
with the same probability is applied more often to the packet flow of the 
small packet sender than that of the large packet sender.

Consequently, if two senders using Standards Track congestion control are 
sending large packets of the same size and the packets for the sender A 
get splitted in smaller PDUs (e.g., in L2 encapsulator, in a tunnel 
ingress, or fragmented on a router in front of a link with an MTU smaller 
than the packet size) before they arrive at a bottleneck AQM but packets 
for the sender B do not get splitted on the path, then the sender A also 
gets more CE marks (I'll call these excess marks as "extra" marks from 
now on) than sender B. This would be unfair for sender A (bias against 
small PDUs at an AQM) as it systematically results in lower throughput 
for it even though A and B are originally sending packets of the same 
size (e.g., MSS-sized packets for TCP) and A and B are increasing and 
decreasing cwnd exactly with the same AIMD algorithms.

2.
In order to enable fair treatment of A and B above (item 1), the "extra" 
marks for A should be eliminated.

I believe we agree on both items (1. and 2.) above, right?
But at the same time I believe we disagree on *how* to eliminate the 
"extra" marks, or that it matters which of these marks are "extra" the 
marks that should be eliminated.

In addition, I believe we agree that

3.
if the bottleneck AQM in the above example happens to use byte-mode drop, 
then there is no (significant) bias against sender A that gets its 
packets splitted before the AQM, i.e., there is no need for any 
additional measures to eliminate the "extra" marks because byte-mo drop 
already does this (please let's use byte-mode drop/marking here only as a 
reference and refrain frrom arguing whether byte-mode is deployed or not 
{Note 1}).

If someone disagrees with this, please see first my comment inline below 
marked {***} and read carefully the cited note by Sally Floyd on whether 
byte-mode drop gives any advantage for small packets (fragments, or 
similarly to flows splitted to small L2 frames before arriving at a 
bottleneck AQM).

{Note 1} How byte-mode drop works is important to understand when 
discussing how to achieve correct operation when we want to eliminate the 
"extra" marks.

What we don't agree, is

4.
How and where in the network to eliminate these "extra" marks, and

5.
Whether CoDel works effectively pretty much like byte-mode drop(/marking) 
even though it does not use probabilistic dropping/marking but 
deterministic drop/marking (timer-based drop/marking). And here the 
important issues is whether CoDel has bias against small packets like 
probabilistic packet-mode drop mentioned in item 1 above.

My claim is that CoDel does not cause any bias against small packets but 
drops/marks a packet at the same level of congestion (queuing) regardless 
of the packet size. Please see e.g., my example on CoDel behaviour in the 
unanswered email I pointed to in my previous message:

  https://mailarchive.ietf.org/arch/msg/tsvwg/AtEI72QCFhOWOn9d6xNcrssTVzs/

Please particularly consider the importance of the timing with a single 
flow (or with a small number of competing flows) what I try to clarify 
below.

With regard to the item 4 and question "where", let's put it aside for a 
while because we first need to understand what is the correct way of 
eliminating the "extra" marks, i.e., how to do it. Where to do it is 
somewhat related to an architectural debate although there are aspects 
that we need to understand concerning where some functions can 
be implemented correctly.

With regard to the question "how" in the item 4, I now notice that we 
seem to approach the problem from a different perspective. Bob seems to 
think of relatively heavy congestion cases in the first place, i.e., when 
there is likely to be a need for an AQM at the bottleneck to mark packets 
relatively often resulting in marking packets (nearly) every RTT or even 
marking several packets per RTT. If this is the case, the approach Bob has 
been proposing (as I understand it) seems to be pretty much on the correct 
track.

Hovever, the way in which we should eliminate the "extra" marks must work 
also for the case when there is only a limited number of competing flows, 
including the case of a single flow. In such a case, the timing of the 
marks is crucial and it is important to understand why.

To keep it simple as possible, I use only the case of a single flow.

I start with very basics. It is very well understood that a single flow 
operating over a tail drop bottleneck requires BDP worth of queue in the 
bottleneck in order to be able to fully utilize the bottleneck link 
capacity. That is, the sender has reached the maximum cwnd (W=2*BDP) when 
a packet is dropped from a full queue and cwnd is halved. The resulting 
cwnd is W/2=BDP, meaning that after halving the window and starting 
the next congestion control cycle (the famous TCP sawtooth) the flow is 
still able to fully utilize the available link capacity. The cwnd of the 
sender oscillates between W/2 and W, giving the average cwnd of 3/4 W = 
3/2 BDP (note that the resulting flow rate is the bottleneck link rate, 
not 3/2 BDP / nominal RTT, but 3/2 BDP / AWG RTT). If we configure a 
shorter queue at the bottleneck or otherwise cause the queue to drop/mark 
at a lower queue level, the maximum cwnd becomes smaller and the 
packet drop occurs "earlier" in the concestion control cycle, i.e., the 
cycle becomes shorter and the saw tooth "amplitude" is lower. That means 
that when a packet is dropped earlier and cwnd is halved, the resulting 
cwnd < BDP and the flow is not able to fully utilize the available link 
capacity. In other words, the interval between two drops (marks/congestion 
signals) becomes shorter.

Now, if we apply an AQM at the bottleneck, the only difference is that 
that we use AQM to control the (virtual) queue size. Again, in order to 
fully utilize the bottleneck capacity, we should configure the AQM such 
that it (on average) drops/marks the first packet after the previous 
drop/mark (and cwnd reduction) only after cwnd has reached W = 2*BDP. If 
we configure or otherwise make it to drop/mark "earlier", i.e., we reduce 
the (virtual) queue size, the flow is not able to fully utilize the link 
capacity but gets a lower delay = average RTT.

So, if we have only a single flow at the bottleneck, the AQM marks 
only a single packet per the famous congestion control saw tooth cycle. 
Once a TCP sender (and many other senders following Stds Track congestion 
control principles) has reduced cwnd to a half of its previous size, it 
starts increasing cwnd by one MSS per RTT. The AQM at the bottleneck 
typically does not mark any packets during the early rounds of this cycle 
because the sender has just allowed the bottleneck queue to drain by 
halving cwnd. After some RTTs the queue has build enough such that the 
AQM moves to its main operating range (e.g., the sojourn time with CoDel 
exceeds Target, or AWG queue length in RED exceeds min threshold). Any 
AQM that has been configured to follow probabilistic packet-mode drop 
(e.g., RED or PIE), starts applying random drop/mark on each arriving 
packet using the same probability regardless of the packet size. This 
means that if the original packets that the sender is sending are split 
into smaller fragments (or frames) before they arrive at the bottleneck 
AQM, the AQM marks the first small packet (PDU) "earlier" (= too early) 
than a packet for a flow with non-splitted packets.

"Earlier" means after a smaller number of RTTs i.e., a sender that gets 
its packets splitted (sender A) has not had a chance to increase its 
cwnd to as high value as a sender (sender B) that does not get its 
packets splitted. Note the both senders increase their cwnd with an equal 
amount of bytes (one MSS) per RTT. So, this FIRST mark per congestion 
control cycle is IMPORTANT, it must not occur too *early*. It means that 
in order to get fair treatment with small PDUs (fragments) we need to 
*postpone* marking the first small PDU (fragment), instead of marking 
immediately. This also means that the timer that Bob has suggested 
will mark a PDU immediately if there were no marks within the timer 
period and therefore it would not work correctly. Having no timer as in 
the "skeleton algorithm idea" in RFC 7141 and in draft-13 would not work 
either because the counter would have an infinite memory.

Hopefully this clarifies the importance of timing. CoDel would work 
correcly as it would set the first mark at the same level of congestion, 
i.e., the sender A with splitted packets and the sender B with non-splitted
packets would experience the first mark during the same round trip after 
the previous cwnd reduction, so cwnd that they both halve is of equal 
size, resulting in the same flow rate.

See below inline some additonal answer/comments inline.


On Sun, 6 Jun 2021, Bob Briscoe wrote:

> Markku, see inline [BB] (I'll reply to Jonathan's email yesterday separately)
>
> On 03/06/2021 12:41, Markku Kojo wrote:
>> Hi David, all,
>> 
>> Catching up ...
>> 
>> I'm afraid there is an open/ongoing discussion on this where we have not 
>> reached concensus. Last message on the topic is here:
>> 
>>  https://mailarchive.ietf.org/arch/msg/tsvwg/AtEI72QCFhOWOn9d6xNcrssTVzs/
>> 
>> Note that while this discussion is much about splitting IP packets to 
>> smaller fragments/frames/PDUs and reassembling/decoding these smaller PDUs 
>> back to larger IP packets, it does, however, relate to the problem in ECN 
>> encapsulation draft on what to do when framing boundaries do not 
>> necessarily align with packet boundaries. This is because the case when 
>> boundaries do not align often INVOLVES also the case where IP packets are 
>> splitted into smaller L2 PDUs (or several smaller IP packets are gathered 
>> into a larger L2 PDU). So, the solution should be based on the same 
>> known-to-work method no matter whether we are fragmenting/reassembling IP 
>> packets or encoding/decoding IP packets to/from L2 PDUs. 
>
> [BB] RFC3168 reassembly is not 'known to work', even for fragment reassembly 
> that it is intended for. You acknowledge that it suffers from the fairness 
> problem unless AQMs all use byte-mode marking (and none do - see later). 
> RFC3168 reassembly does not even have any suggestion on what to do if framing 
> boundaries overlap packet boundaries or where packets are smaller than frames 
> - so it is not 'known-to-work' in any case, let alone in every case.

[MK] I have not suggested anywhere that RFC3168 reassembly would work 
correctly with probabilistic packet-mode marking/dropping. With 
'known-to-work' method I mean something that have been shown to work 
correctly, i.e., there is an algorithm (or a set of algorithms) that has 
been published and evaluated and there is rough consensus it works 
correctly.

And, yes, I think I made it perfectly clear in the message referred above 
that we need to solve all cases, including the cases where pkt/frame 
boundaries ovelap or where pkt/frame sizes do not match, as well as 
a mix of these cases (and I never suggested RFC 3168 reassemby for 
this, I only stated that RFC 3168 reassemby would work correctly for 
Stds Track congestion control when IP fragments hit an AQM bottleneck that 
implements byte-mode drop).

>> As the discussion referred in the above message is longish, I'll try 
>> summarize the problem space in the end of this message.
>> 
>> And, then there is also another thread that Bob initiated and I seemingly 
>> have not replied although promised (I was away from any IETF work in April 
>> due to family emergency and only resuming now, my apologies). That thread 
>> is about the (additonal but not independent) problem where L3 packet and L2 
>> PDU boundaries do not align. The last message on the thread is here:
>> 
>>  https://mailarchive.ietf.org/arch/msg/tsvwg/3la3kG5-JLU2OPx3zGxxmhWGYEo/
>> 
>> I will send my notes on that very issue separately tomorrow.
>> 
>> I believe that the best solution to allow ECN encap draft to move forward 
>> is that the draft does not say anything on the topic except points to a new 
>> draft (the one that has been envisioned to handle the IP fragmentation 
>> problem and would include also the handling of not aligned packet/frame 
>> boundaries) and we initiate such new draft before ECN encap draft gets 
>> published.
>
> [BB] Let us now start talking about the content of that.
>
> Before we do, can we make sure we're all on the same page regarding some 
> basics that I believe are /facts/ about preserving markings when PDU 
> boundaries change. Do you agree with the following table that I asked about 
> earlier:
>
>                   | marked    marked
>                   | PDUs      bytes
> -------------------+------------------
> preserving prop'n  |  ==        ==
> preserving number  |  !=        ==
>
>
> IOW, do you agree that the three that are tagged as '==' are equivalent ways 
> of expressing the same thing, but different from the one tagged '!=' ?

[MK] For standards track congestion control it is important that timing 
of the congestion signal is correct: not postponed inappropriately, nor 
injected too early (see above).

I am unclear here if you are looking only the case where packet size = PDU 
payload, i.e., when the boundaries do not align?

>> 
>> Below I try to summarize the problem with the two suggested paragraphs with 
>> two SHOULDs.
>> 
>> 1. The two paragraphs (SHOULDs) are contradictory: there is no algorithm 
>> that has been shown to be able to correctly fulfill both requirements 
>> (please see the first message referred above where I explain why the 
>> algorithms that Bob has suggested do not work correctly).
>
> [BB] Since draft-13 (May 2019) I haven't given any specific algorithms 
> (because the chairs requested we don't discuss specifics).

[MK] There have been two earlier suggestions with brief text describing 
the "skeleton/idea of an algorithm".

The first "algorithm" was the one in draft-13 which is essentially the 
same as what RFC 7141 gives in Sec 2.4. It proposed a counter to 
calculate the balance of incoming and outgoing marked octets and to mark 
the outgoing packets such that the number of octets  with congestion 
indications in incoming and outgoing PDUs are equivalent. Such a counter 
has infinite memory and thereby it would remove tens of CE marks present 
in inner fragments (splitted PDUs) in the worst case, postponing the 
congestion indication unacceptably long. I believe we agreed this was 
wrong. And, In particular, it proposed marking an outgoing packet 
immediately with the smallest positive remainder in the counter. This is 
also wrong, because it results in marking an outgoing packet too early 
(see above).

The second "algorithm idea" was presented here:

  https://mailarchive.ietf.org/arch/msg/tsvwg/vmIXNtXhGplqTEK1H-NIsZ1kTEs/

It modified the first one by suggesting to approximately preserve 
the proportion of PDUs with congestion indications arriving and leaving.
In addition, it added a timer with "typical RTT" to ensure immediate
propagation of congestion indication after a timeout period without any
marking. This algorithm has the problem that it also results in marking an 
outgoing packet too early. With lightly congested conditions Standards 
Track congestion control expects receiving congestion signals every Nth 
RTT where N is relative to the maximum congestion window size (W) in the 
prevailing network conditions (N = W/(2*MSS)). A correctly working 
algorithm would need to be able to remove "extra" CE marks during this 
time period. And a decapsulator does not know what the RTT is, and the 
timer period must be different for the case when there is only one flow 
at the bottleneck, compared to the case when there are several flows 
sharing the bottleneck AQM queue.

The third algorithm is presented below.

> Nonetheless, now that the drafts are progressing, I think we're allowed to 
> discuss specifics. Although, let's not discuss implementation efficiency 
> quite yet - let's keep to intent for now.
>
> So here's one example of pseudocode for propagating ECN marking when frames 
> are derived from an ordered byte stream of larger packets, but the frame and 
> packet boundaries do not align:
>
> ----------------->+<---------------------------->+<------------------------------>+<----
> Pkt1       |               Pkt2           | Pkt3                |
> +-------------+-------------+-------------+-------------+-------------+-------------+---
> |    Fr1      |     Fr2     |     Fr3     |    Fr4      | Fr5     |    
> Fr6      |
> +-------------+-------------+-------------+-------------+-------------+-------------+---
>
>
> /* Algorithm A =======================
>  */
> #define TIMEOUT 1ms    // (say) as a default for the public Internet
> bool marked, pending;
>
> // On frame arrival
> marked = ismarked(incoming_frame);
> pending = pending || marked;
>
> // On packet departure
> if (marked|| (pending && time(now) >= expiry_time) ) {
>     mark(outgoing_packet);
>     expiry_time = time(now) + TIMEOUT;
> }
> pending = FALSE;
> //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
>
> Explanation:
> 1) First consider the case where marking is frequent enough that outgoing 
> packets are always marked more often than every 1ms. Then as each outgoing 
> packet is made ready to depart, it will be marked if the last frame to arrive 
> was marked. This is based on the idea Jonathan suggested for preserving the 
> proportion of marked PDUs.
> 2) Now, what if marks arrive infrequently, so that the time since the last 
> outgoing mark exceeds the TIMEOUT? Then the outgoing packet will be marked if 
> /any/ frame that it consists of was marked, because the timer condition and 
> 'pending' will both be true. Because pending toggles on if any frame is 
> marked, and pending is cleared after every packet is sent.

[MK] This marks splitted packets too "early" in most Internet network 
settings. See above.

> The value of TIMEOUT can be argued about for ever, but the intent is to 
> ensure it's significantly smaller than most RTTs over the Internet.

[MK] Sure, but if TIMEOUT is smaller than most RTTs over the Internet, it 
results in majority of cases not eliminating the "extra" marks for 
splitted packets, resulting in bias against splitted (small) packets with 
probabilistic packet-mode AQMs that is one of the goals. We also need to 
understand that the pace at which a single connection increases its 
offered load (cwnd) is different from the pace at which two or more 
competing flows increase the offered load (aggregate rate). So, the 
decapsulator does not need to estimate only the RTT but also adjust the 
timer when the number of competing flows changes. Seems quite complex to me.

> Here's an alternative algorithm:
>
> /* Algorithm B =======================
>  */
> #define TIMEOUT 400μs    // (say) as a default for the public Internet
>
> // On frame arrival
> if (ismarked(incoming_frame)) {
>     balance += size(incoming_frame);
> }
>
> // On packet departure
> if (balance > 0) {
>     mark(outgoing_packet);
>     balance -= size(outgoing_packet);
>     expiry_time = time(now) + TIMEOUT;
> } elseif (time(now) >= expiry_time) {
>         balance /= 2;
> }
> //\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
>
> Explanation:
> While marked packets are arriving often enough, this keeps the proportion of 
> outgoing marked bytes the same as the proportion incoming (it therefore also 
> preserves the proportion of marked PDUs).
> But if marks arrive more infrequently, it preserves the /timing/ and 
> therefore the /number/ of marks.

[MK] So, it does not mitigate the bias against splitted packets when 
packet-mode marking is used. Am I missing something?

> More specifically, the algo works is as follows:
> * When a marked frame first arrives, the algo marks an outgoing packet 
> immediately,

[MK] So, it marks too "early" as I explained earlier.

> even if there weren't enough incoming marked bytes for the 
> outgoing packet size. But the algo holds the deficit in balance, so that if 
> more marked bytes appear before the TIMEOUT, they will have to eat up the 
> deficit before causing another outgoing mark. This is what ensures the 
> proportion outgoing balances the proportion incoming.

[MK] But not the correct timing of marks.

> * However, if the balance has been negative for more than the TIMEOUT, it is 
> halved. And after another timeout the deficit is halved again, and so on, 
> until eventually it will round down to zero. Then, with certainty, the next 
> incoming marked frame, whatever its size, will trigger an outgoing mark 
> immediately. In the intervening period, every time the deficit is halved, it 
> becomes more likely that an incoming marked frame will cause an immediate 
> outgoing mark, by taking the balance over zero.
>
> I prefer the approach of gradually transitioning between preserving the 
> proportion of marks and preserving the timing of marks, rather than a hard 
> cut-off between the two. But the latter could be implemented simply by 
> changing '/= 2' to '= 0' and using a longer TIMEOUT. Also note that the 
> balance approach works whether some frames are larger than packets or some 
> packets are larger than frames.
>
> By definition these algorithms resolve a compromise (between preserving 
> fairness and preserving timeliness). So if you're a cup-half-empty sort of 
> person, you will always be able to argue that they're not truly correct. But 
> if you're a cup-half-full-sort of person you will be able to argue that 
> they're never too far off being correct.
>
>
>> 
>> 2. There is no actual algorithm in the draft for a potential implementor 
>> that would allow for a proper implementation (nor is there experimental 
>> evidence showing any such algorithm would work correctly).
>> With the relatively vague first SHOULD, it is very unlikely anyone would 
>> get it right, I think.
>
> [BB] Can you not remember what happened between draft-13 (May 2019) and 
> draft-14 (Nov 2020)? Because we couldn't agree, the chairs asked me to remove 
> the specific algorithm that was in the draft, and solely state requirements 
> (which eventually resulted in the two SHOULDs). The chairs wanted to defer 
> this debate, and not to constrain Layer-2 solutions to a particular algorithm 
> in the mean time.
>
> If you don't agree with that approach, don't argue with me. The chair's 
> intent was that the question of how exactly to mark PDUs while reframing was 
> controversial, so it should be solved in a separate draft, in order that this 
> ecn-encap draft could go through quickly (ironic raised eyebrow).

[MK] I am not arguing with you, but with the proposed text in the draft.
So, I oppose publishing text in a BCP that indicates a behaviour of an 
algorithm for which there is no algorithm that has been shown to work.
I also object publishing vague text that leaves too much to interpret 
without citing at least one way to do it correctly (or, in general, that 
thereis a way of implementing it correctly).

>> 
>> 3. RFC 7141 has been used as the guideline for the new proposed text
>>    which makes resolving the issue even more problematic because the
>>    recommendations in RFC 7141 are the origin of the problem on how
>>    to handle fragmentation/reassembly as well as encapsulation/
>>    decapsulation of IP packets/L2 frames when there is an AQM
>>    marking/dropping fragmented/splitted PDUs. As said, this is not
>>    independent of the problem with not aligned packet/frame boundaries.
>
> [BB] RFC7141 is not "the origin of the problem". It described current AQM 
> practice, which was not what researchers thought (and apparently still 
> isn't). It is a BCP and many many people were involved in reaching consensus 
> on it during the 6 years it progressed through the IETF. It explained why AQM 
> practice at the time was not implementing byte-mode drop, and proposed a way 
> to move forward with packet mode drop instead.

[MK] Seems that the AQM practise has evolved since the publication of 
RFC 7141 and the AQM practise (RED) it evaluated is not anymore 
recommended at all.
Since then new AQMs have been introduced (actually were introduced 
already before publishing RFC 7141 but not published in RFC series)

> It included a survey which found that /none/ of the respondents had 
> implemented byte-mode dropping (admittedly only 19% response rate, out of 84 
> vendors contacted. Plus we checked Linux RED, which also did not implement 
> byte-mode drop).
> See https://datatracker.ietf.org/doc/html/rfc7141#appendix-A

[MK] The text in RFC 7141 / appendix A does not cite the survey so all 
details remain unknown. I wonder how many of the 14 vendors that answered 
that they did not implement byte-mode drop did implement byte-mode queue 
measurement? For those who did not, I believe, the question about 
implementing byte-mode drop is not quite relevant given the advise in the 
original RED paper, Section 4:

  "when this option is used [queue is measured in bytes] the
   algorithm would be modified to ensure that the probability
   that a packet is marked is proportional to the packet size
   in bytes."

That is, the advise at the time was only implement byte-mode drop when 
byte-mode queue measerement was implemented.

> RFC7567 is also a BCP, and in section 4.4 it also recommends against 
> byte-mode marking and byte-mode drop.
>
> Since RFC7141 and RFC7567 were published, a new round of AQMs appeared (CoDel 
> and PIE). Contrary to what you say in the first linked email above, CoDel 
> does not do byte-mode drop or byte-mode marking{Note 1}.

[MK} Ehh. Where I have said CoDel does byte-mode drop? I believe I was 
quite clear in saying that CoDel employs deterministic drop/marking. My 
apologies if my wording has been unclear.

> And PIE doesn't  either.
>
> DOCSIS PIE does do a limited form of byte-mode drop{Note 2}, but it does not 
> support ECN and it's not under 'IETF-change-control' anyway (the authors 
> offered to document it as an informational RFC). The only other algorithm I 
> know of that has implemented byte-mode drop is the RED used in the ns2 
> simulator.
>
> Later you say byte-mode drop is common industry practice and that it's the 
> way forward. It's not industry practice at all, so it's hardly going to be 
> the way forward.

[MK] Ehh, again, where have I said byte-mode drop is common industry 
practice?? My point with the byte-mode drop in the first place is to refer 
to a correctly working approach that has  been designed to eliminate 
bias against small packets (fragments) and has been evaluated to work 
correctly (with some later corrections).


> {Note 1}: With CoDel:
> * The likelihood of marking a specific packet does not depend on that 
> specific packet's size, only on the average size of all packets.

[MK] Incorrect. CoDel marking is not probabilistic at all There is no 
likelyhood, but the drop/mark is deterministic if the congestion 
persists, pretty similar to why tail drop is deterministic. Because it is 
deterministic and absolutely independent of packet size. When sojourn 
time exceeds Target, CoDel schedules first mark after an Interval (given 
that sojourn time remains above Target for the time priod of Interval). 
During the Interval period, the bottleneck link deliveres the same amount 
of bytes regardless of packet sizes (though the amount of payload bytes 
is different due to different pkt hdr overhead, of course). That is, if 
two senders are sending packets (TCP segments) of the same size (they use 
same MSS value) over a network path with same characteristics, they send 
the same amount of data during the Interval and increase their cwnd at 
the same pace (and they increase cwnd at the same pace also after the 
previous time they halved cwnd and sojourn time fell below Target but 
before the sojourn time again exceeds Target). 
So, the next time an CoDel AQM at the bottleneck marks a packet 
(fragment), it occurs at the "same point" (at the same time) regardless of 
whether or not a sender got its packets fragmented (splitted) before 
they arrive at the the bottleneck AQM. That is, when a fragment or packet 
is marked, cwnd has the same value in both cases and cwnd is reduced 
(halved) to the same value when the CE mark is signalled to the sender 
(pls ignore the slight difference due to pkt hdr overhead).

> That is 
> packet-mode marking, not byte-mode marking.

[MK] RED, from where these terms come from, uses probabilistic 
dropping/marking. Byte-mode and packet-mode drop/marking is meaningful 
only with probabilistic drop/marking.

> * The control law reduces the time between each mark/drop on a preordained 
> schedule, so the likelihood of any one packet being dropped/marked is higher 
> and increases faster if the average packet rate is lower (which can be 
> because packets are larger on average).

[MK] Well correct but per packet likelyhood is irrelevant. Yes, there are 
less larger packets in between the marks than smaller packets that the 
AQM sees, but the same amount of bytes (= amount of time). What 
matters is that there are the same amount of *original* packets in 
between the marks that the sender is sending (and sees), regardless 
whether the original packets get splitted and merged (fragmented and 
reassembled) an route. The end-point operates on non-splitted units 
(= original packets/TCP segments) it sends and it does not even know what 
happened at lower layers!

> * However, just because CoDel happens to mark packets on a preordained time 
> schedule is not why it's important for a decap to propagate a mark in a 
> timely fashion. The motivation is not specific to CoDel - it's to minimize 
> the delay around the control loop whatever the AQM.

[MK] Please read carefully what I wrote about the importance of timing 
towards the beginning of this message and how timing affects the 
behaviour and performance. And please think of the simplest scenario with 
a single flow. It must work first, only after that we, of course, need to 
think also the cases with a larger number of competing flows).

> {Note 2}: DOCSIS PIE implements limited dependence on packet size, in order 
> to reduce the chance of dropping small control packets (not because it 
> considers that drop should depend on packet size). In the spec, it apologizes 
> for not following RFC7567, but it includes safeguards against the 
> consequential DDoS vulnerability that it opens up.
>
>
>> The problems that we have at hand are as follows:
>> 
>>  a) The original paper on RED suggested byte-mode operation where
>>     byte-mode dropping/marking would adjust drop/mark probability
>>     of smaller fragments (to have lower probability) such that with
>>     the same level of bit-congestion the RED AQM would mark/drop
>>     approximately at the same point a packet for a flow being
>>     fragmented and for a flow with full-sized packets, i.e., it
>>     would treat fragmented and non-fragmented traffic fairly.
>
> [BB] Can you give a more precise description of the AQM scenario you have in 
> your mind here? The words "at the same point" make me suspicious that you 
> might be thinking of something different to byte-mode drop. It's possible 
> you're talking about byte-mode queue measurement (see RFC7141 for 
> definitions). So please describe exactly how you think this AQM is working. 
> I.e. whether there are per-flow queues or a shared queue; in what units it 
> measures the queue, whether it marks packets of different sizes within the 
> same flow with different likelihoods, etc.
>
>
>> That byte-mode drop together with RFC 3168 reassembly logic
>>     results in fair and correct behavior for Standards track
>>     congestion control, loss-based CC included.
>
> [BB] Assuming for now that you are indeed talking about byte mode drop,...
>
> The perfect complementarity you claim between byte-mode drop and RFC3168 
> reassembly never existed, because no-one implemented byte-mode drop. RFC7141 
> did not /cause/ your perfect world to collapse. It investigated and 
> discovered that byte-mode drop didn't exist, worked out why, articulated why, 
> and proposed a way forward that would give the desired complementarity 
> between network and hosts, without relying on byte-mode drop, which was 
> clearly problematic to everyone.
>
> You write the above as if byte-mode was deliberately introduced in RED so 
> that it worked well with the fragmentation. I'm afraid that's a rewrite of 
> history in reverse.
> The interaction between ECN and fragmentation hadn't even 
> been thought about when byte mode and packet mode were included in the 
> original 1993 paper on RED. Byte and packet mode were two options, which 
> Sally Floyd left configurable because it wasn't completely clear at that time 
> which one was most suitable (see the [pktByteEmail] reference in RFC7141 to 
> Sally's 1997 email about this).


[MK] {***}
Well, we seem to be reading a different written history ;)
the [pktByteEmail] reference in RFC7141 seems to point to Sally's not 
updated web page at LBL that is missing an additional email from year 
2000 where Sally explains why there is no bias against small packets 
(fragmented packets) when byte-mode drop is used. I fully agree with 
Sally with her analysis there. Please explain if you disagree with it. 
Please see the complete reference in Sally's ICIR web page:

  https://www.icir.org/floyd/REDaveraging.txt

I cannot speak for Sally and Van, but I believe that they quite carefully 
considered the bias agains small packets when they introduced byte-mode 
drop in their RED paper to mitigate the problem. Cannot tell if they 
thought of fragmentation at the time of designing and writing the RED 
paper but it works just perfectly fine in the case of fragmentation. I 
wouldn't be suprised if fragmenttation was one of the reasons for 
introducing byte-mode drop.

ECN was first introduced around the same time frame, and the leading 
principle there was not to give ECN undeserved preference over loss-based 
congestion control. And RFC 3168 fulfills it suprisingly well, and 
particularly well in terms of addressing fragmentation.

> 6 years later, when ECN first became an experimental RFC, there was still no 
> mention or thought of fragmentation in RFC 2481. I became involved during the 
> late stages of the update from RFC 2481 to what became RFC 3168 - 8 years 
> after the original RED paper. Jon Crowcroft and I pointed out that there was 
> no mention of fragmentation, as part of our attempt to make a more principled 
> division between the IP and TCP parts of RFC3168 - see our review at 
> https://bobbriscoe.net/pubs.html#ECN-IP (we were coming at it from a 
> real-time media perspective. not just TCP). The fragmentation approach that 
> was subsequently added to what became RFC3168 was still highly TCP-specific, 
> even though it was at the IP layer. However, I didn't feel I should hold up 
> RFC3168 to argue any further about it (unlike the present situation in tsvwg, 
> I took the view that I had arrived late at the party, so allowing others to 
> make progress was more important than me continually making the same point 
> over and over, even tho I thought I was right).
>
> Then we reach the 2008-2014 time-frame over which RFC7141 was developed - 
> when it was discovered that no-one was implementing byte-mode drop anyway 
> (see back where I started the story above).
>
>
>> 
>>  b) Recommendation in RFC 7141 to not do byte-mode drop but
>>     instead use packet-mode drop (with equal drop/mark probability
>>     regardless of PDU size) will treat fragmented (splitted)
>>     traffic unfairly, yielding fragmented traffic suboptimal
>>     performance (as Bob has indicated several times). Therefore,
>>     packet-mode drop would need an algorithm at reassembly/decapsulation
>>     that SHOULD approximately preserve the proportion of PDUs(/bytes)
>>     with congestion indications arriving and leaving.
>> 
>>     However, there is no known algorithm that could do this correctly
>>     at reassembly/decapsulation as stated in item 1 above.
>>     More importantly, even if such algorithm existed it cannot
>>     work with non-ECT AQMs, i.e., with loss-based congestion control
>>     for which no adjustment of congestion indications can be done
>>     at the reassembly/decapsulator. But, one can achieve the correct
>>     outcome in a single place: in the AQM algorithm itself by employing
>>     byte-mode dropping/marking; it works correctly also for the majority
>>     of the traffic today, that is, for traffic employing loss-based
>>     congestion control.
>
> [BB] This is nostalgia for a past that never was. When no-one has done what 
> you think they should have done, it is important to try to understand why.

[MK] Well, cannot argue that too many have done it, but the original 
inventors of RED did it, and I believe they somehow understood how 
Standards Track congestion control works and what is the right thing to 
do.

Still, I do not have a good understanding about the actual reasons why 
byte-mide drop seemingly(?) was not much implemented by RED vendors. It 
seems to me that the reason potentially is in complexity of byte-mode in 
general (particulrly byte-mode queue measuring), not the complexity of 
byte-mode drop, and most likely that there was not that good understanding 
of the topic at the time RED was widely implemented, nor was there good 
guidance available either.

>> 
>>     Moreover, doing adjustment at the reassembly/decapsulator is
>>     architecturally not very good solution because we would
>>     need such an algorithm at several places (at receiving
>>     enpoints, at tunnel egress, at L2 decapsulator) which
>>     introduces quite unnecessary complexity in several places.
>
> [BB] Quite the opposite. The whole approach is designed to minimize 
> in-network processing, and move it to the end-systems.
> See https://datatracker.ietf.org/doc/html/rfc7141#section-3.5

[MK] When an L2 decapsulator or an tunnel egress has become an end-point 
in the Internet architecture?

Efficiency is one aspect but it is much more important to see first where 
a function can be implemented correctly. An end-point (or any node in 
the Internet) cannot implement correctly a function when it does not know 
whether the function is needed or not. That is, if an end-point (or 
tunnel egress, or decapsulator) does not know what kind of AQM has marked 
the fragments, it cannot try to compensate the bias that the AQM 
potentially did with the fragments, right?

> At most decaps (including all tunnels), the framing doesn't change. 
> Fragmentation is deprecated.

[MK] Deprcated?? Which RFC? I thought much of the fragmentation seen in 
the Internet is due to tunnels?? What am I missing, please advise?

> And few networks apply ECN marking where there 
> is no IP-awareness.
>
>
>> 
>>  c) Recommendation in RFC 7141 is not applicable with AQMs that do
>>     not use probabilistic dropping/marking. E.g., it would result
>>     in incorrect behavior with CoDel AQM that employs deterministic
>>     dropping (please see more detailed explanation in the first
>>     message referred above) and with any potential new AQM that
>>     does not employ probabilistic dropping/marking.
>
> [BB] Incorrect. See explanation earlier in this email.

[MK] You never replied my previeous email that I pointed to and where I 
explained why CoDel does not bias agains small packets. Please read 
carefully the explanation in there and in this message as well, and 
please kindly indicate where my explanation in your view is incorrect.

>> 
>>  d) Although RFC 7141 is BCP, the recommendation in it is not based
>>     on any deployed mechanism (or at least I am not aware of any such
>>     best practice) nor on any published/evaluated algorithm that has
>>     shown to work. On the other hand, there is quite a bit of
>>     experimental evaluation on RFC 3168 reassembly & byte-mode
>>     drop/mark (although more high-quality evaluation would be useful).
>
> [BB] This is completely the reverse of reality. As explained above, RFC7141 
> was based on a survey of AQM implementations at the time, and it recorded 
> industry practice at the time. That practice has continued since then in 
> CoDel, PIE and now PI2, DCTCP, etc.

[MK] I should have pointed clearly to the recommendation I meant (RFC 
7141, Section 2.4):

  One can think of a splitting or merging process as if all the
  incoming congestion-marked octets increment a counter and all the
  outgoing marked octets decrement the same counter.  In order to
  ensure that congestion indications remain timely, even the smallest
  positive remainder in the conceptual counter should trigger the next
  outgoing packet to be marked (causing the counter to go negative).

Has an algorithm that implements this recommendation been described in 
detail, evaluated, analysed, and/or deployed somehere such that we could 
say it is the "best current practise"?

> In contrast, AFAICT, the /only/ use of byte-mode marking has been in the 
> research community.

[MK] Mayby so, but at least there is a crisp enough description of the 
simple algorithm and quite a bit of evaluation, even such that a small 
error in the calculation of the drop probability was revealed and a 
correction introduced.

Regards,

/Markku

> Regards
>
>
> Bob
>
>> 
>> 
>> Thanks,
>> 
>> /Markku
>> 
>> On Tue, 25 May 2021, David Black wrote:
>> 
>>> 
>>> As draft shepherd and a WG chair, I believe that these drafts resolve the 
>>> last of the open issues from WG
>>> Last Call.
>>> 
>>> 
>>> 
>>> In the next week or two, I will prepare the shepherd writeups and submit 
>>> these drafts to our AD for further
>>> review towards IETF Last Call and publication as RFCs.
>>> 
>>> 
>>> 
>>> Thanks, --David
>>> 
>>> 
>>> 
>>> From: Bob Briscoe <[e-mail]>
>>> Sent: Tuesday, May 25, 2021 10:35 AM
>>> To: Black, David; [e-mail]
>>> Cc: Donald Eastlake; John Kaippallimalil
>>> Subject: Re: [tsvwg] ECN encapsulation draft - proposed resolution
>>> 
>>> 
>>> 
>>> [EXTERNAL EMAIL]
>>> 
>>> David, tsvwg list,
>>> 
>>> As promised yesterday, we just posted a new rev of 
>>> ecn-encap-guidelines-16, with text based on your
>>> (David's) suggestions below. To add the references and to avoid some 
>>> repetition, I twiddled the order round,
>>> but otherwise kept the text intact.
>>> 
>>> I also took the opportunity to post a new rev of rfc6040update-shim, 'cos 
>>> I noticed Geneve has been
>>> published as an RFC. There were also a couple of words edited in my local 
>>> copy as agreed on the list a few
>>> months ago.
>>> 
>>> https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-ecn-encap-guidelines 
>>> [datatracker.ietf.org]
>>> https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-rfc6040update-shim 
>>> [datatracker.ietf.org]
>>> 
>>> Cheers
>>> 
>>> 
>>> 
>>> Bob
>>> 
>>> On 24/05/2021 13:50, Bob Briscoe wrote:
>>> 
>>>       David, Thx for bringing this one up. See [BB] inline,
>>> 
>>>       On 22/05/2021 01:02, Black, David wrote:
>>> 
>>>       On another topic, I believe that I have good news to pass along on 
>>> the ECN encapsulation
>>>       drafts.
>>> 
>>> 
>>> 
>>>       The current situation is that the 6040update-shim draft is ready for 
>>> RFC publication to be
>>>       requested, but there's an open issue in the ecn-encap draft on the 
>>> contents of this
>>>       paragraph in Section 4.6 (Reframing and Congestion Markings),
>>> https://datatracker.ietf.org/doc/html/draft-ietf-tsvwg-ecn-encap-guidelines-15#section-4.6
>>>       [datatracker.ietf.org]
>>> 
>>> 
>>> 
>>>          Congestion indications SHOULD be propagated on the basis that an
>>> 
>>>          encapsulator or decapsulator SHOULD approximately preserve the
>>> 
>>>          proportion of PDUs with congestion indications arriving and 
>>> leaving.
>>> 
>>> 
>>> 
>>>       Digging further, this area appears to be dealt with in greater 
>>> length and detail by RFC
>>>       7141 (Byte and Packet Congestion Notification) Section 2.4 
>>> (Recommendation on Handling
>>>       Congestion Indications When Splitting or Merging Packets),
>>>       https://datatracker.ietf.org/doc/html/rfc7141#section-2.4 
>>> [datatracker.ietf.org]  The
>>>       short summary is that the quoted sentence is generally correct with 
>>> RFC 7141 containing a
>>>       more comprehensive discussion including an exception.  As RFC 7141 
>>> is a BCP, I suggest
>>>       treating it as authoritative on this matter for now, leaving 
>>> redesign in this area to a
>>>       possible future draft (as we did in the 6040update-shim draft wrt 
>>> RFC 3168 fragment
>>>       reassembly requirements).
>>> 
>>> 
>>> 
>>>       To carry this out, here's an initial ecn-encap draft text change 
>>> suggestion (begins with
>>>       last two sentences in second paragraph of Section 4.6):
>>> 
>>> 
>>> 
>>>       OLD
>>> 
>>>             Where framing boundaries do not necessarily align
>>> 
>>>          with packet boundaries, the following guidance will be needed.  
>>> It
>>> 
>>>          explains how to propagate ECN markings from layer-2 frame headers
>>> 
>>>          when they are stripped off and IP PDUs with different boundaries 
>>> are
>>> 
>>>          reassembled for forwarding.
>>> 
>>> 
>>> 
>>>          Congestion indications SHOULD be propagated on the basis that an
>>> 
>>>          encapsulator or decapsulator SHOULD approximately preserve the
>>> 
>>>          proportion of PDUs with congestion indications arriving and 
>>> leaving.
>>> 
>>> 
>>> 
>>>          The mechanism for propagating congestion indications SHOULD 
>>> ensure
>>> 
>>>          that any incoming congestion indication is propagated 
>>> immediately,
>>> 
>>>          not held awaiting the possibility of further congestion 
>>> indications
>>> 
>>>          to be sufficient to indicate congestion on an outgoing PDU.
>>> 
>>> 
>>> 
>>>       NEW
>>> 
>>>             Where framing boundaries do not necessarily align
>>> 
>>>          with packet boundaries, the provisions of Section 2.4 of RFC 7141
>>> 
>>>          apply to propagation of ECN markings from layer-2 frame headers
>>> 
>>>          when they are stripped off and IP PDUs with different boundaries 
>>> are
>>> 
>>>    reassembled for forwarding. Those provisions include: "The general
>>> 
>>>    rule to follow is that the number of octets in packets with
>>> 
>>>    congestion indications SHOULD be equivalent before and after merging
>>> 
>>>    or splitting." See RFC 7141 for the complete provisions and related
>>> 
>>>    discussion, including an exception to that general rule.
>>> 
>>> 
>>> 
>>>          In addition to adhering to the provisions of RFC 7141 Section 
>>> 2.4,
>>> 
>>>          the mechanism for congestion indication propagation SHOULD ensure
>>> 
>>>          that any incoming congestion indication is propagated 
>>> immediately,
>>> 
>>>          and not held awaiting possible arrival of further congestion
>>> 
>>>          indications sufficient to indicate congestion for all of the 
>>> octets
>>> 
>>>          of an outgoing IP PDU.
>>> 
>>> 
>>> 
>>>       END
>>> 
>>> 
>>> [BB] OK, this is indeed progress.
>>> 
>>> 
>>> 
>>> 
>>>       RFC 7141 (a BCP) would be added as a normative reference.
>>> 
>>> 
>>> [BB] I'll write that up now. And post a revised draft.
>>> 
>>> 
>>> Bob
>>> 
>>> 
>>> 
>>> 
>>> 
>>>       Comments?
>>> 
>>> 
>>> 
>>>       Thanks, --David (as draft shepherd)
>>> 
>>> 
>>> 
>>>       David L. Black, Sr. Distinguished Engineer, Technology & Standards
>>> 
>>>       Infrastructure Solutions Group, Dell Technologies
>>> 
>>>       mobile [phone] [e-mail]
>>> 
>>> 
>>> 
>>> 
>>> 
>>> -- 
>>> 
>>> ________________________________________________________________
>>> 
>>> Bob Briscoe                               http://bobbriscoe.net/ 
>>> [bobbriscoe.net]
>>> 
>>> 
>>> 
>>> -- 
>>> 
>>> ________________________________________________________________
>>> 
>>> Bob Briscoe                               http://bobbriscoe.net/ 
>>> [bobbriscoe.net]
>>> 
>>> 
>
> -- 
> ________________________________________________________________
> Bob Briscoe                               http://bobbriscoe.net/
>
>