Subject: [quicwg/base-drafts] ACK Frames should be in Increasing Packet Number Order (#969)

From: Nick Banks <[email-masked]>
Date: Wed, 29 Nov 2017 21:04:56 +0000 (UTC)

The ACK frame consists of blocks in decreasing packet number order and, now that they use variable-length integers, processing these ACK blocks in reverse order is no longer feasible.

Generally, I feel that ACK blocks should be processed in increasing packet number order (start with smallest packet number), for a couple of reasons:

1. Assuming your list of Outstanding Sent Packets is ordered by increasing packet number (oldest packet at the front), for any ACK block you process, you'd expect the smallest packet number in the block to be at or near the front of the Sent Packets list.

2. If the smallest packet number isn't at the front of the Sent Packets list, then it's likely FACK/RACK could kick in, causing the front of the list to be removed immediately, further optimizing the search for the next smallest packet number that was acknowledged.

I can't see any reason for processing ACKs in the current order the frame contains them. Can anyone shed some light on why this order was originally chosen?

-- 
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/969

---

From: MikkelFJ <[email-masked]>
Date: Wed, 29 Nov 2017 21:33:40 +0000 (UTC)

There was a lengthy discussion on this and some consensus on the need of redesigning the ACK frame, but I can't seem to find the issue where this was covered.

-- 
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/969#issuecomment-348003437

---

From: Nick Banks <[email-masked]>
Date: Wed, 29 Nov 2017 21:48:55 +0000 (UTC)

Well, if folks agree with this, it would be easy enough to change the existing ACK frame text. I'd be happy to make the changes. Find/replace in the ACK section:

- 'largest' => 'smallest'
- 'descending' => 'ascending'
- 'preceding' => 'following'

No wire format needs to change as far as I can 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/969#issuecomment-348007750

---

From: ianswett <[email-masked]>
Date: Wed, 29 Nov 2017 21:59:57 +0000 (UTC)

In most cases, it doesn't matter whether it's in ascending or descending order.  If one was using a linked list to store packets, then you would have to skip over a CWND of packets with the current decreasing approach, but that's not a data structure I'd recommend anyway, because it has poor cache locality.  A deque is a fairly good choice.

The original reason it was chosen is that when sending an ack frame, if there wasn't room for all the ack ranges or you didn't want to send all of them for some other reason, it's best to drop the lowest ranges, which are typically the least recently received packets, rather than the highest.  This can be accomplished by doing a first pass through the ack frame and tracking how large it'll serialize to before serializing it, but that's not ideal.

As far as I know, the serialization case is the only case where the order ends up mattering much in either computational complexity/cost or programming complexity.

I don't think I understand your second concern.

-- 
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/969#issuecomment-348010809

---

From: MikkelFJ <[email-masked]>
Date: Wed, 29 Nov 2017 22:12:53 +0000 (UTC)

For decoding I find the order impractical because packets are sorted by packet number oldest first. If the ACK frame had same order, both lists could be walked directly. In praxis it is not that simple because the entire packet must be validated before being processed and because there could be multiple ACK frames in a single packet so one cannot conclude timeout before seeing all.

-- 
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/969#issuecomment-348014279

---

From: Nick Banks <[email-masked]>
Date: Wed, 29 Nov 2017 22:15:41 +0000 (UTC)

@ianswett Can you elaborate on why you think the order doesn't matter when you process the ACK packet? I am envisioning the following pseudo function:

```
process_ack_frame (ack_frame) {
  foreach (ack_block in ack_frame) {
   foreach (pkt_num in ack_block) {
      if ((sent_pkt = find_outstanding_pkt(pkt_num)) != null) {
        on_pkt_acked(sent_pkt)
      } 
    }
  }
}

find_outstanding_pkt (pkt_num) {
  foreach (pkt in outstanding_pkts) {
    if (pkt.num == pkt_num) {
      outstanding_pkts.remove(pkt)
      return pkt
    }
    if (pkt.num > pkt_num) break
  }
  return null
}
```

`process_ack_frame` is most efficient if the ACK frame/blocks are in increasing packet order. Ideally, the find function just pops the head of the list off.

-- 
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/969#issuecomment-348014988

---

From: Subodh Iyengar <[email-masked]>
Date: Thu, 30 Nov 2017 01:41:54 +0000 (UTC)

I think the newest first should be the order. The reason is that QUIC prefers to ACK newer packets over older packets. If we do oldest first, then we would have to do one pass over the packet to calculate the space that we have before we decide which is the oldest packet we can actually encode in the ack. This is harder to do that having the decoder just use a reverse iterator. For this reason I support the current newest first encoding

-- 
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/969#issuecomment-348055583

---

From: Nick Banks <[email-masked]>
Date: Thu, 30 Nov 2017 02:10:08 +0000 (UTC)

@siyengar The use of variable-length integers prevents reverse traversal over the raw ACK frame.

-- 
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/969#issuecomment-348060251

---

From: Subodh Iyengar <[email-masked]>
Date: Wed, 29 Nov 2017 20:08:04 -0800

oh i see what you want to do, you want to handle acks while parsing the frame, ya in that case you can't have a reverse iterator. We parse the packet and then handle the acks which is why we can have a reverse iterator. I can see that it's shitty either way, ascending or descending. It may be less shitty as descending :)

-- 
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/969#issuecomment-348077116

---

From: Marten Seemann <[email-masked]>
Date: Wed, 29 Nov 2017 22:25:02 -0800

What I like the most about the descending order is that you can just stop writing new ranges, when you notice that the ACK is getting too big.
Furthermore, descending order saves a few bytes on the wire, since for all ranges, you're only encoding packet number differences. For ascending order, you'll need multiple bytes for the first block. It's just a couple of bytes per ACK, but since ACKs are sent frequently, this might something worth considering.

-- 
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/969#issuecomment-348094367

---

From: MikkelFJ <[email-masked]>
Date: Wed, 29 Nov 2017 22:33:32 -0800

It would be good to avoid temp allocation beyond a fixed stack allocation during decoding. There is no longer a 256 entry limit.

-- 
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/969#issuecomment-348095638

---

From: Nick Banks <[email-masked]>
Date: Thu, 30 Nov 2017 14:06:40 +0000 (UTC)

@marten-seemann I don't understand why the ACK frame would be a different size with ascending order? It should be exactly the same, encoding gaps and blocks as packet number differences. For ascending you add the differences as you traverse ACK frame; for descending you subtract.

Also, on the issue of encoding ACK blocks in ascending order, shouldn't it be fairly to traverse you local list of packet number ranges to ACK to calculate how many of them will fit in your packet. Once that is determined, you just start from the smallest of that subset to encode the ACK frame. You can also have some simple heuristics to know (for the simple cases) if all your local ranges would fit in the packet, even if they used the full variable-length encoding for each parameter, so you don't have to calculate each individually.

-- 
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/969#issuecomment-348197240

---

From: Marten Seemann <[email-masked]>
Date: Thu, 30 Nov 2017 19:24:36 +0000 (UTC)

@nibanks: Maybe I don't understand your proposal correctly, so let's take an example. If I want to encode an ACK frame for the packet numbers 1e12 to 1e12+10 (first range) and 1e12+20 to 1e12+30 (second range), then for descending order, I need to encode the large value 1e12+30 once (for the largest acked), and the rest will be small differences which will fit into one byte. For ascending order, as I understand it, you'd need to encode a value O(1e12) twice, which will take more bytes.

Regarding your pseudo code, I think there are a lot of ways to consume an ACK. In quic-go, we chose a completely different approach, since iterating over a range sent by the client would make us vulnerable for DoS (when a peer sends a large range).

-- 
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/969#issuecomment-348293584

---

From: Nick Banks <[email-masked]>
Date: Thu, 30 Nov 2017 20:02:48 +0000 (UTC)

@marten-seemann If we changed the ACK frame to ascending order, `Largest Acknowledged` would become `Smallest Acknowledged` and all the deltas would reverse direction. You wouldn't encode anything twice.

As for the DoS, I agree, the simplistic pseudo code does have issues. Instead you would `find` the start and the end of the range, and return the set of all packets in it. But generally, the same issues apply.

-- 
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/969#issuecomment-348304173