Subject: Re: [quicwg/base-drafts] Improve ACK_ECN frame encoding (e.g., use bit-vector) (#1439)

From: MikkelFJ <[email-masked]>
Date: Wed, 01 Aug 2018 01:08:14 -0700

I like the idea of avoiding counters, but depending on how packet history is handled, couldn't this lead to more overhead?

Consider a sliding bitmap tracking all packets that are not yet ACK'ed. If ECN state is explicit, more bits might be required in the bitmap - or they could just be dropped - but I am not sufficiently into ECN processing to tell.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-409488588

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 01 Aug 2018 04:24:33 -0700

@martinthomson That is an interesting design.

I can understand the motivation for having more bits to represent the size of an ACK block using just one octet. OTOH, the complexity of the design makes me anxious.

The issue with the design is that, if there is an exception (i.e. packets received with more than two types of flags) you need to either iterate though the PN list more than once or to generate multiple ACK frames concurrently while iterating though the PN list.

Honestly speaking, I think that the multi-modal block approach that uses 2 bits per block (the one you suggested in 
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-397157328) is dense enough. It would mean that we can pack up to 16 packet numbers into a single-octet ACK block. I do not think that spending a second octet for the 17th packet number is an issue, because it means spending at worst 0.5 bit more for every packet that you receive.

If we need to care that much about the bandwidth consumed by ACKs, I think we should rather consider how to reduce the frequency of sending acknowledgements, considering the fact that we have at least 18-octet overhead for every packet that we send.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-409542558

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 22 Aug 2018 06:51:57 -0700

I spent some time analyzing the overhead impact of these two proposals and compared them against the original. In this analysis I have looked at cost of encoding gaps/loss and ECN-CE marks for a varying number of packets included in a single acking. As loss gaps as well as CE marks are expected to result in immediate acking the most realistic cases are that a single ACK even with one or two RTTs of overlap actually will not contain more than one or two loss or CE mark sequences. Thus I focused on these. But I also looked at the cost if one gets a lot of transitions back and forth. I also would like to note that this is focused on the case with working ECN so no strange behaviors. 

The overhead for what is currently in -14:

Loss/gap | CE | Packets per   ACK |   |   |   |   |   |   |   |  
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
  |   | 1 | 2 | 5 | 10 | 21 | 56 | 112 | 319 | 2000 | 8000
0 | 0 | 19 | 19 | 19 | 19 | 19 | 19 | 21 | 21 | 21 | 21
0 | 1 | 19 | 19 | 19 | 19 | 19 | 19 | 21 | 21 | 21 | 21
1 | 0 | - | 21 | 21 | 21 | 21 | 21 | 21 | 25 | 25 | 25
1 | 1 | - | 21 | 21 | 21 | 21 | 21 | 21 | 25 | 25 | 25
2 | 1 | - | 23 | 23 | 23 | 23 | 23 | 23 | 29 | 29 | 29
2 | 2 | - | 23 | 23 | 23 | 23 | 23 | 23 | 29 | 29 | 29
0 | 2 | - | 19 | 19 | 19 | 19 | 19 | 21 | 21 | 21 | 21
0 | All | 19 | 19 | 19 | 19 | 19 | 19 | 21 | 21 | 21 | 21
5 | 15 | - |   | - | 29 | 29 | 29 | 29 | 29 | 41 | 41
20 | 50 | - |   |   |   | 59 | 59 | 59 | 59 | 59 | 101
100 | 300 |   |   |   |   |   |   | 219 | 219 | 219 | 219

For Martins proposal above but encoding marking in the frame type:

Loss / GAP | CE | Packets per   ACK |   |   |   |   |   |   |   |  
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
  |   | 1 | 2 | 5 | 10 | 21 | 56 | 112 | 319 | 2000 | 8000
0 | 0 | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 8 | 8 | 8
0 | 1 | 14 | 14 | 14 | 16 | 16 | 16 | 22 | 22 | 22 | 22
1 | 0 |   | 9 | 9 | 9 | 9 | 9 | 13 | 13 | 13 | 13
1 | 1 |   | 18 | 18 | 18 | 18 | 18 | 20 | 26 | 26 | 26
2 | 1 |   | 20 | 20 | 20 | 20 | 20 | 22 | 30 | 30 | 30
2 | 2 |   | 24 | 24 | 24 | 24 | 24 | 24 | 38 | 38 | 38
0 | 2 |   | 7 | 20 | 20 | 20 | 20 | 20 | 30 | 30 | 30
0 | All | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 8 | 8 | 8
5 | 15 |   |   |   |   | 82 | 82 | 82 | 82 | 154 | 154
20 | 50 |   |   |   |   |   | 252 | 252 | 252 | 252 | 494
100 | 300 |   |   |   |   |   |   |   | 1412 | 1412 | 1412

For the single octet blocks with 2-bit marking type:

Loss / GAP | CE | Packets per   ACK |   |   |   |   |   |   |   |  
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
  |   | 1 | 2 | 5 | 10 | 21 | 56 | 112 | 319 | 2000 | 8000
0 | 0 | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 11 | 38 | 131
0 | 1 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 12 | 38 | 132
1 | 0 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 12 | 38 | 132
1 | 1 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 12 | 39 | 132
2 | 1 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 14 | 38 | 134
2 | 2 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 41 | 131
0 | 2 | 9 | 9 | 9 | 9 | 9 | 9 | 9 | 12 | 39 | 132
0 | All | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 11 | 38 | 131
5 | 15 |   |   |   |   |   | 27 | 27 | 27 | 48 | 132
20 | 50 |   |   |   |   |   | 78 | 78 | 78 | 78 | 149
100 | 300 |   |   |   |   |   |   |   | 408 | 408 | 408

The conclusions I can draw that is that Martin's scheme for one or two changes in the range being acked are basically equivalent to the current scheme while providing more explicit information about which packets being marked. The single byte ack block outperforms both the current and martins proposal for low rate of changes and for ack vector lengths up to a few hundred packets. After that the ACK vector growth becomes larger due to the one byte per 64 packets. However, this growth is low enough that a single minimal MTU (1280 bytes) will be able to ack a range that is more than 70000 packets. Compare this to the Bandwidth delay product to packet rate table above for perspective. 

For cases with high frequency of alternating marking the one byte scheme will be more efficient. This because if one have mix of packet losses and CE marks (likely under severe congestion) then one ends up encoding both CE marks and losses as gaps in the ECT ack vector. Thus martins proposal will have a higher total number of transitions needed to be encoded than the one byte proposal. I will note that calculation performed is the worst case when it comes to transitions with them evenly spread between arriving packets both gaps and CE marks. 

There is also a difference when it comes to performing verification of the ECN between these solutions. So Martin's proposal require for different markings or frame types to express if a packet arrived with Not-Ect, ECT(0), ECT(1), and ECN-CE. The 1-byte block can only do marking in two bits by employing information loss for a non-expected case. The non-default ECT marking will have to be reported in the Not-ECT type to indicate this non-expected behavior. And if anyone like to use this for a QUIC connection that uses both ECT(0) and ECT(1) it will not be possible to carry through, even if one could define a transport parameter to say that there is no default ECT and both shall be reported as ECT. 

In the end I think this comes down to the question of how much processing overhead the schemes incur versus the differences there actually are between them. I personally need to think a bit more about that.  

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-415039038

---

From: Magnus Westerlund <[email-masked]>
Date: Fri, 24 Aug 2018 07:27:32 -0700

After having read Martin's updated proposal on the mailing list I wanted to post overhead figures for that encoding also. So this is the case of using 2 bits per block to encode the change delta value of the type so that all 5 types can be used, and then have a variant of the variable length encoding but with 2 less usable bits for values. 

Loss / GAP | CE | Packets per   ACK |   |   |   |   |   |   |   |   |   |   |  
--- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---
  |   | 1 | 2 | 5 | 10 | 21 | 56 | 112 | 319 | 2000 | 8000
0 | 0 | 7 | 7 | 7 | 7 | 8 | 8 | 8 | 8 | 8 | 9
0 | 1 | 8 | 8 | 8 | 8 | 8 | 10 | 10 | 10 | 10 | 10
1 | 0 | 8 | 8 | 8 | 8 | 8 | 10 | 10 | 10 | 10 | 10
1 | 1 | 9 | 9 | 9 | 9 | 9 | 12 | 12 | 12 | 12 | 12
2 | 1 | 10 | 10 | 10 | 10 | 10 | 10 | 14 | 14 | 14 | 14
2 | 2 | 11 | 11 | 11 | 11 | 11 | 11 | 16 | 16 | 16 | 16
0 | 2 | 9 | 9 | 9 | 9 | 9 | 12 | 12 | 12 | 12 | 12
0 | All | 7 | 7 | 7 | 7 | 7 | 7 | 8 | 8 | 8 | 9
5 | 15 |   |   |   |   |   | 27 | 27 | 27 | 48 | 48
20 | 50 |   |   |   |   |   | 78 | 78 | 78 | 149 | 149
100 | 300 |   |   |   |   |   |   |   | 408 | 408 | 809

As I see it this has the best properties when it comes to overhead. More efficient for small ack vectors, efficient encoding for larger ranges. Yes the additional byte comes at 16 rather than 64 consecutive packets but the the other choices are worse from my perspective. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/1439#issuecomment-415775598