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

From: Christian Huitema <[email-masked]>
Date: Fri, 01 Dec 2017 19:46:44 +0000 (UTC)

I like one part of the descending order: immediately obtaining the "largest seen" packet number. If we agree that seeing this "largest seen" is important, then the descending order makes sense. Everything else can be solved with appropriate data structures.

-- 
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-348596574

---

From: MikkelFJ <[email-masked]>
Date: Fri, 01 Dec 2017 19:50:12 +0000 (UTC)

But then it must be required that highest / first ACK range really is the largest seen. There is currently no such requirement AFAIK.

-- 
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-348597515

---

From: Nick Banks <[email-masked]>
Date: Fri, 01 Dec 2017 20:48:09 +0000 (UTC)

Why does it really matter if 'largest acknowledged' (even if it is required to be 'largest seen') be in the ACK frame's header and not just in the last ACK block? You process the entire ACK frame/blocks at essentially the same moment in time (as far as the network is concerned).

And I still I haven't heard a solution to my original problem. Given that set of outstanding sent packets is sorted in ascending order, if the ACK blocks are in descending order (and cannot be traversed in reverse order without first copying to a separate data structure and memory) how are you supposed to efficiently match ACK blocks to outstanding send packets?

The best I can think of requires a search for 'largest acknowledged' and then iteratively (per ACK block) search backwards from that point, effectively O(2n) to find all the ACK blocks; where as if the ACK blocks were in ascending order, the search is only O(n).

For example:

Outstanding Sent Packets: `{1,2,3,....1000}`
ACK Blocks: `{500 - 400},{390-300},{290-1}`

Again, assuming you don't allocate additional memory for an intermediate data structure, processing these ACK blocks in descending order would first require a search through half the Outstanding Sent Packets set to find the largest and then the same part of the set would be walked backwards for the rest of the ACK blocks. But if they were in reverse order that wouldn't be the case.

-- 
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-348610490

---

From: martinduke <[email-masked]>
Date: Fri, 08 Dec 2017 17:33:32 +0000 (UTC)

I concur with all the arguments in favor of descending order.

@nibanks I see that in the general case, largest_acked can have the annoying property of being somewhere in the middle of your packet list. However, I'll note that a single block can easily be processed lowest to highest, which will tend to address your problem because...

1) in the lossless case, there is only one block anyway.
2) If the ACK only advertises one *new* gap, the earlier blocks have presumably been wiped out from your packet queue anyway.

I confess that the situation where there are large numbers of lost packets to travers in the queue could be suboptimal. One can solve this by keeping lost packets in a separate queue, or keeping a pointer to the first packet not declared lost.

Ascending order really shines when an ACK frame reports multiple *new* packet gaps. I'm not sure how to trade that off against the other considerations.

-- 
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-350323275

---

From: Nick Banks <[email-masked]>
Date: Fri, 08 Dec 2017 17:45:38 +0000 (UTC)

@martinduke both of your reasons for saying that a block can be process easily from lowest to highest assumes little to no packet loss. We cannot make that assumption. We have to design for the most common case, which would assume packet loss. Also, in both your scenarios, ascending order processing time would be equal to descending order; but those are the **only** cases where that would be the case. In **all other cases** processing in descending order is a more expensive operation than processing in ascending order.

-- 
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-350326325

---

From: martinduke <[email-masked]>
Date: Fri, 08 Dec 2017 10:00:49 -0800

I don't know that heavy, non-bursty packet loss is the common case.

Anyway, the increased processing expense is offset by lower cost generation of ACK frames. With ascending, I have to figure out the full size of the acknowledgment, start deleting blocks from the top if oversize, and then write into the packet.

This is just about as complex as, on processing, reading all the information in the ACK into memory and then deleting packets from the queue. If you take that approach, it's trivial to start from the lowest number. Indeed, it would be straightforward to execute this approach only if block_count is large.

To summarize:
Descending: Low-cost generation; high-cost processing under the conditions where ACKs report multiple new gaps .

Ascending: High-cost generation, low-cost processing.

-- 
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-350330147

---

From: ianswett <[email-masked]>
Date: Fri, 08 Dec 2017 19:31:53 +0000 (UTC)

I think there are ways to make the processing low cost for descending as well.

I'm working on an implementation that I believe would have identical performance in both directions.  It's sort of on the back burner, but I can try to finish it soon so it's available in Chromium for people to take a look at?

-- 
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-350351573

---

From: Nick Banks <[email-masked]>
Date: Fri, 08 Dec 2017 12:35:55 -0800

@ianswett I look forward to your proposal.

-- 
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-350365656

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 11 Dec 2017 09:35:50 -0800

Did some quic (sorry for the pun) back of the envelope calculations on the 2 different approaches if you want to iterate while parsing, which I think is not really necessary.

Descending order algorithm:

```
let outstanding -> rb tree, deque / vector of packets in ascending order of packetnum
let m -> num of frames in ack frame
let n -> num of outstanding packets

auto matchEnd = outstanding.end;
for (all frame in ackframe descending order) {
  auto matchedIt = search_for_first_packet_not_less_than(frame.start, outstanding.start, outstanding.end); 
  if (matchedIt == end) {
    continue;
  }
  matchEnd = matchedIt;
  while (matchedIt != outstanding.end) {
    if (matchedIt.start >= frame.start and matchedIt.end <= frame.end) {
	   ack();
	} else {
	  break;
	}
	matchedIt++;
  }
}
```
assuming the search complexity is log n

the worst complexity would probably be:
```
(m  * log n ) | (min(m, n) + min(m, n) log n)

(1) If m >> n, then an attacker would try to make all the blocks not match in which case you would get m log n
(2) If n >> m then an attacker would have greatest advantage by making only 1 block match per frame, to get you do the max number of search operations, however it is still bounded by m or n

However in case (2) the attacker could not exceed m.
so the complexity is actually

m * log n
```

The alternative approach of ascending is 

```
matchStart = outstanding.start
for (all frame in ascending order) {
  auto matchedIt = search_for_first_packet_not_less_than(frame.start, matchStart, outstanding.end); 
  if (matchedIt == end) {
    break;
  }
  matchStart = matchedIt;
  while (matchedIt != outstanding.end) {
    if (matchedIt.start >= frame.start and matchedIt.end <= frame.end) {
	   ack();
	} else {
	  break;
	}
	matchedIt++;
  }
}
```

This seems to be the same worst case complexity, so both approaches have similar DoS capabilities however the best case complexity is better since you can exit early with ascending

Practically though I don't think this is a big deal implementations will have multiple layers in the code, one which parses the data into an in memory frame structure after which you can use either an ascending or descending algorithm. 

For example even with an ascending data structure in the ACK frame you still need to incur high cost again, because you need to know the largest acked packet for loss detection in the case of time based loss detection as well as early retransmit timers which involves iterating over the outstanding packets again, which is much better to do if you can iterate over the frames just once which you can do if you pre-parse the entire data structure into memory.

I would rather make it easier to serialize data into the packet so that senders of ACKs will do the right thing of prioritizing ACKing larger packets over optimizing streaming parsing.

-- 
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-350798049

---

From: MikkelFJ <[email-masked]>
Date: Mon, 11 Dec 2017 09:48:42 -0800

Good input.

Some concerns: assuming you have descending order in frame. If you can seek to the end then process in ascending order, this is probably fine. But if you cannot, you either rely on assumptions about log N handling, or you must allocate a temporary data structure. Earlier there was a limit on 256 entries but this limit is gone. The sender knowns how many entries it creates and can easily keep number of entries below a limit. The receiver can't. Especially if it must expect very large MTU.

The receiver also do not control the frequence of ACK frames and hence the amount of resources to dedicate while the sender does. The sender is also the one that can do DoS.

As to the log N assumption, that doesn't work if you use a bitmap scan. A bitmap scan is resistant to DoS because it is O(N). Since packets now are in incremental order, this is a practical approach. 

Scanning the bitmap from most recent to older probably has a number of problems that I currently do not recall. Generally you want to work with the oldest packet first.

I can see the idea of building in descending order but you can do two passes to compute the size and then build ascending.

-- 
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-350801957

---

From: MikkelFJ <[email-masked]>
Date: Mon, 11 Dec 2017 17:50:15 +0000 (UTC)

There also ought to be a requirement that if there are multiple ACK frames in a packet, they must be in ascending order, which of course puts even more strain on the sender, but it is for the same reason. It is simpler to require that there is at most one ACK frame per packet.

-- 
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-350802423

---

From: janaiyengar <[email-masked]>
Date: Mon, 11 Dec 2017 18:59:02 +0000 (UTC)

I don't see a reason at the moment to have two ACK frames per packet (especially with the varint representations). That said, I don't see this perf issue as a reason to require it... we can certainly recommend it strongly (SHOULD).

-- 
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-350822514

---

From: MikkelFJ <[email-masked]>
Date: Mon, 11 Dec 2017 11:29:05 -0800

If there is a MUST, the receiver can have an implementation that takes an ACK frame, makes conclusion on age and time, and do updates. With SHOULD, it needs to add additional complexity to manage information from both frames, even if a second frame is rare. Granted, the ACK frame must be parced once to validate the packet, but it is still simpler with at most one.

-- 
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-350831277

---

From: janaiyengar <[email-masked]>
Date: Mon, 11 Dec 2017 19:31:20 +0000 (UTC)

The receiver doesn't need to do any ack info aggregation per packet. Just treat it like two separate ACK frames were received.

-- 
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-350831894

---

From: MikkelFJ <[email-masked]>
Date: Mon, 11 Dec 2017 11:32:45 -0800

OK, that simplifies things.

-- 
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-350832309

---

From: Nick Banks <[email-masked]>
Date: Mon, 11 Dec 2017 12:08:57 -0800

> Practically though I don't think this is a big deal implementations will have multiple layers in the code, one which parses the data into an in memory frame structure after which you can use either…

There is no reason to require an implementation to use any structure other than the wire format. Why can't it process the packet directly?

As far as the complexity of each design, I agree they can essentially have the same worst case, but then our decision should be based on the common case. Generally, ACKs will be received for the oldest outstanding packets, correct? And if the oldest packet number ACKed in an ACK frame is significantly newer than your oldest outstanding packet, then you will be throwing (mark as lost) that old packet out anyways.

If you use ascending order then you could rely exclusively on a linear walk of your outstanding packets, starting at the beginning. For each packet in your list the packet, that is less than the min of the current ACK block, it will either be ACKed or lost (for the most part). Once you get to the last packet number being ACKed in the frame, you stop walking the list.

Your worst case then is a single ACK block that ACKs your most recent packet; but in that case, it would likely cause you to throw away all your older packets anyways, which require you to walk the entire list.

-- 
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-350842888

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 11 Dec 2017 22:29:13 +0000 (UTC)

@nibanks I agree with you, there is no reason for an implementation to require any structure other than a wire format. For example the for loop could just be an iterator adapter in C++ that lazily processes packets. There are just tradeoffs with both approaches and I was just trying to point out the tradeoffs.

>  Generally, ACKs will be received for the oldest outstanding packets, correct?

In the common case the ACK  would be received for the most recently received packet first. Quic's loss detection algorithms rely on the sender prioritizing ACKing higher packets first for example for stuff like TLP or RTO to work correctly. A descending first algorithm kind of makes this feel more natural to to serialize packets correctly. 

Even if you use ascending order with streaming parsing you'd have to probably iterate over the packets again anyway after you're done processing the acks. There are 2 types of loss detection in QUIC. For timer based loss detection you'd have to know what the largest acked packet is before triggering it on all the packets. Even for packet order based loss detection you probably need to iterate over most of the packets in the common case because there is no guarantee given acked packet n, packets below it are less than n - kReorderingThreshold, I haven't worked out the algorithmic details for that yet and we might be able to make this more efficient by caching the minOutstandingPacketNumber, but I don't think that will change the complexity analysis.

-- 
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-350879570

---

From: Nick Banks <[email-masked]>
Date: Tue, 12 Dec 2017 09:16:12 -0800

@siyengar I agree that ACKs will be sent for the most recently received packets. But I am assuming that most of the time, all received packets will be able to be ACKed; that most of the time, space won't be an issue and all the ACK blocks will fit. There might be a couple gaps on average (it would be great if someone had some numbers related to the size and consistency of ACK blocks with certain network conditions).

So if we assume that generally, all packets received are acknowledged then we are back to my original argument. The oldest packet number in the ACK frame will generally be your oldest outstanding packet (or close to it). So if you process both sets, ACK blocks and outstanding packets, together, in ascending order, you will be able to do a single pass of both and determine if an outstanding packet is ACKed, Lost, or Still Pending. And at most, you will only process your outstanding packet list up to the largest ACKed packet in the 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-351120309

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 12 Dec 2017 18:56:19 +0000 (UTC)

Ya agree, that sounds like a perfectly reasonable assumption, in the common case you won't have to process loss.

-- 
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-351153364

---

From: Nick Banks <[email-masked]>
Date: Tue, 19 Dec 2017 17:46:30 +0000 (UTC)

@ianswett Any updates? I still don't see a way that descending order could ever be as good as ascending order. I'm still thinking of this example where you have a couple of gaps of lost packets.

Assuming the final result is that packets `{1-290}, {300-390}, {400-500}` are acknowledged and packets `{291-299}, {391-399}` are marked as lost (FACK), that means you would have to traverse the entire first 500 packets of the outstanding list. If you walk the list in ascending order, you only touch each packet once, and no more packets than necessary. But to do that (without an extra preprocessing step and associated temporary memory) you would need the ACK blocks in ascending order.

-- 
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-352834033

---

From: ianswett <[email-masked]>
Date: Tue, 19 Dec 2017 19:16:38 +0000 (UTC)

No updates, but I'll explain what my approach is.

I store an IntervalSet of the previously acknowledged packets from the lowest one I'm tracking to the largest previously acknowledged.  When I read the ack frame, I'm incrementally comparing the intervals I'm parsing with the IntervalSet of previously acknowledged packets and storing any newly acknowledged packets in a list and adding them to the IntervalSet for the future.  Then I do a second pass over the full data structure with the newly acknowledged packets in the list.  The list isn't necessary, so you could do it in one pass, but it fits into my current implementation better, so it's what I'm doing for now.  My congestion control APIs take a list of newly acked packets and their size in bytes, so I have to create that list anyway.

You have to ensure you don't allow someone to acknowledge packets larger than the largest ever sent, or you can allocate a ton of extra temporary memory(a perk of doing this without a temporary list), but otherwise, this should turn out to be slightly faster for decreasing order, since I can ignore any extra ack ranges that are below the smallest packet I'm still waiting for an acknowledgement for.

-- 
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-352858775

---

From: Nick Banks <[email-masked]>
Date: Tue, 19 Dec 2017 21:00:41 +0000 (UTC)

Thanks @ianswett for the detailed explanation. Do you use this IntervalSet of previously acknowledged packets for anything other than this purpose? Otherwise, to me this still seems just like an intermediate data structure for processing the ACK block. We haven't had need of a similar object in our code and I would be hesitant to add it just for this.

My ideal goal is still:

1. Process ACK block directly from the wire format.
2. Require no extra processing steps or temporary storage.
3. Process the necessary outstanding packet structures only.

I see a solution with ascending order but descending order breaks at least one of the above goals.

-- 
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-352884900

---

From: ianswett <[email-masked]>
Date: Tue, 19 Dec 2017 22:13:30 +0000 (UTC)

It has two purposes.  One is this, and the other is that reusing the existing ack frame trades a small amount of memory for a large-ish reduction in memory allocations.  It might even be possible for it to be a net savings of memory allocated in the typical case, by removing the redundant information of what has already been acknowledged from the more complete data structure, but I haven't tried that yet.

So this gives you 1, 2, and 3 with the only cost being complexity of an optimized data structure to speed part 3, which happens to look exactly like how you likely store the QUIC ack frame you're putting received packets into and sending.  It does assume you're using a deque or something similar that makes it fast to seek to a given entry, but that's the best style I've found in practice.

How are you intending to store and find newly acked packets?  It's worth keeping in mind that after loss, you'll likely want to track packets that have already been retransmitted for a while, in case they were spuriously retransmitted, so you may commonly end up skipping over those on the way up.  It's also worth keeping in mind that linked lists have awful performance from a CPU cache 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/969#issuecomment-352902490

---

From: MikkelFJ <[email-masked]>
Date: Tue, 19 Dec 2017 14:33:22 -0800

Given that packet numbers are in incremental order it can be done much more efficiently in time and space by scanning chained blocks of bitmaps. If there is a large gap you just link two bitmaps. Doing this efficiently requires ack's in increasing order. If your chain grows too long, you are subject to abuse, or conditions too bad to maintain a connection.

The initial descend into the bitmap can be done by remembering the previous start location, or by using an efficient index into each bitmap block.

If you arbitrarily loose every second packet, an interval map is using a lot of memory in comparison, not to mention a log2 lookup.

So, it would be rather sad to have to allocate a lot of temporary memory for no good reason.

-- 
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-352907087

---

From: MikkelFJ <[email-masked]>
Date: Tue, 19 Dec 2017 14:42:40 -0800

Well, maybe chained bitmaps could be revised to be scanned in the opposite direction but you likely need a second pass to make retransmission decisions.

-- 
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-352909128

---

From: ianswett <[email-masked]>
Date: Tue, 19 Dec 2017 22:54:19 +0000 (UTC)

I haven't thought through the details of using bitmaps as much, except to say that real-world packet loss works well with ranges, even if bitmaps have better worst case properties.  I also find it convenient that ranges match up with the ack format nicely.  If packet loss was random, GQUIC would likely have used bitmaps for the ack format.

Marking packets as lost is currently a separate pass in the GQUIC code, because initially we were using pluggable loss detection.  Doing descending order works fine for detecting lost packets, and it doesn't matter which order packets are lost in to make retransmission decisions, because we can decide what to send after all lost packets are determined.

If one did use a linked list without any sort of side data structure, I don't think it matters which direction you iterate in.  Either way, you're going to have to check all packets being tracked in the list between the largest acked packet and the smallest.  I don't think the iteration order matters?  You would have to store an extra pointer to quickly access the packet larger than the largest previously acknowledged to speed access to largest acked, but that seems simple.

-- 
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-352911751

---

From: Nick Banks <[email-masked]>
Date: Tue, 19 Dec 2017 15:01:04 -0800

If you store a linked list without any side structure, and the largest packet number is the first value you process, you have to process the items from the beginning to the largest twice. Once to find the actual largest item, and then another as you walk backward to process the ACK blocks.

-- 
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-352913107

---

From: MikkelFJ <[email-masked]>
Date: Tue, 19 Dec 2017 15:09:06 -0800

@nibanks you just reverse the list order in the first pass :) (never mind messing with the cache)

-- 
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-352914706

---

From: ianswett <[email-masked]>
Date: Tue, 19 Dec 2017 23:09:45 +0000 (UTC)

The beginning being the smallest packet?  You can start at the largest, or even better, whichever is closer to largest acked(the largest sent or the largest previously acked).  It does mean touching a few extra elements, but typically those are being acknowledged and going to be accessed anyway.

That being said, in many scenarios, having a side data structure is going to make this faster.

-- 
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-352914823

---

From: Nick Banks <[email-masked]>
Date: Tue, 19 Dec 2017 15:18:12 -0800

When you get an ACK frame, on average, where do you expect the packet number ranges to reside, in relation to our set of outstanding packets? Generally for the oldest outstanding packets?

Then, assuming FACK, if you do receive ACK blocks/frame for packet numbers more recent (larger) than your oldest packets, you would mark those 'skipped' packets as lost, therefore removing them from your outstanding packets set, right?

In that case, you essentially 'touch' all the oldest packets, up to the largest packet number in the ACK frame. So why not just walk both the ACK frame and your set of outstanding packets, in ascending order, together marking packets as either lost or ACK?

-- 
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-352916357

---

From: MikkelFJ <[email-masked]>
Date: Tue, 19 Dec 2017 15:40:58 -0800

Although my previous comment wasn’t entirely serious, if you do insist on using a list, and the ack order is reverse, then it makes sense to root the list at largest acked and point to older packets, then root a separate list in forward direction with a tail pointer. You move elements from the forward list to the reverse list while searching for a new largets acked and add new packets at the tail.

-- 
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-352920288

---

From: ianswett <[email-masked]>
Date: Wed, 20 Dec 2017 06:37:19 -0800

You generally expect the next packets acknowledged to be close to the largest acked.

We've found it's important to keep around older packets for a while after they've been lost to detect spurious retransmits, which are not that infrequent.  Currently, we keep around about an RTT of old packets, in the hopes that QUIC can tolerate a full RTT of reordering in the worst case.  That's probably overkill for most cases, but ideally it only costs a bit of memory that doesn't end up being accessed, so there should be little to no CPU overhead.

But the key difference here is the data structure we're discussing using.  For a deque or anything similar to it, I think something like the approach I described works well and order doesn't matter.  If you use only a linked list, then ascending order is simpler to implement efficiently, but I think the real-world performance of either direction is very similar if you follow some of MikkelFJ's suggestions.

-- 
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-353079348

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Dec 2017 14:51:02 +0000 (UTC)

Thanks @ianswett. Really appreciate the information. I agree that if you use a more complicated data structure to represent your outstanding packets than a list, you have the ability to process ACK blocks, independent of order, pretty much the same.

But I am still trying to understand why not use ascending order. The main argument I have heard is that, if you have too many packet numbers to ACK, then you always want to ACK the largest/most recent ones; and that is easier to do if you start at the largest and just continue to write the ACK blocks until you run out of room. I agree that it is easier. I would propose two solutions:

1. Keep track of the amount of space it would require you to encode your current set of ACK'ed packet numbers and only keep around what can fit into a single packet.

2. Have writing the ACK frame be a two step process. First to walk the your list in descending order to figure out how many packet numbers would fit in the packet. Then, starting at the smallest that would fit, work upward and encode.

Neither of those seem too complicated to me, and don't require more complicated data structures or significant extra processing time.

-- 
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-353082961

---

From: ianswett <[email-masked]>
Date: Wed, 20 Dec 2017 06:58:05 -0800

Re 1, the issue is really if you'd like to bundle an ack with data.  If you only send acks in ack-only packets, it should be fairly easy to ensure it always fits, though the combination of varints and ranges potentially being merged makes it more complex than you'd think, if you want to stay close to the limit.  I would not advise anyone write this code, because I think it's error-prone.

Re 2, sure that can definitely be done.  And that's what I'd recommend if we did increasing order, but given processing acks in decreasing order is easy(in my case, it's equivalently costly and equivalent complexity), I think this double-pass is more complex and costly than the processing acks in decreasing order.  

-- 
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-353084959

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Dec 2017 07:01:57 -0800

> I think this double-pass is more complex and costly than the processing acks in decreasing order.

I would generally agree, and I did do exactly that before the varint changes. But with varint, I cannot process the ACK block in reverse order without first copying it to some other format in some other memory. Assuming worst case of a a full packet with a lot of 1 byte gaps/blocks encoded with varint, that could quickly explode if my temporary data structure uses the full  8 bytes to represent each.

-- 
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-353086079

---

From: MikkelFJ <[email-masked]>
Date: Wed, 20 Dec 2017 07:08:32 -0800

just a thought: I like the current varint format, but if varints were encoded with highbit in all but last byte, then they could be processed in both directions if you know when to stop. utf-8 is similar self-sync'ing 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-353087918

---

From: Marten Seemann <[email-masked]>
Date: Wed, 20 Dec 2017 15:18:49 +0000 (UTC)

> But with varint, I cannot process the ACK block in reverse order without first copying it to some other format in some other memory. Assuming worst case of a a full packet with a lot of 1 byte gaps/blocks encoded with varint

I don't think varint changes anything here. The old ACK format also allowed for 1 byte gaps / blocks.

>  that could quickly explode if my temporary data structure uses the full 8 bytes to represent each.

The thought of having a ~ 10 kb data structure to represent the ranges of a single ACK frame is unpleasant, however, if you're concerned about allocations, you only need one of those per connection, if you reuse it.

-- 
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-353090923

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Dec 2017 07:22:11 -0800

@marten-seemann The temporary structure wasn't needed before varints, as I could parse the wire format in reverse. As to having the 10kb structure always allocated with the connection, I agree that is a solution, though it seems pretty wasteful, considering that worst case will almost never be hit.

-- 
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-353091937

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Dec 2017 15:24:58 +0000 (UTC)

Also, it could get more complicated, as the max size of the temporary data structure would depend on MTU, which could change, or just outright, be very large. Again, worst case if 64KB was the MTU, then that temporary structure is HUGE.

-- 
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-353092734

---

From: ianswett <[email-masked]>
Date: Wed, 20 Dec 2017 15:59:39 +0000 (UTC)

You can close the connection if any packets larger than largest acked are acknowledged and skip over any ranges less than the smallest packet you're still tracking, so I believe any portion of an ack frame you have to process is still much smaller than the datastructure of outstanding packets.

-- 
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-353103151

---

From: Lars Eggert <[email-masked]>
Date: Wed, 20 Dec 2017 21:21:46 +0000 (UTC)

I don't know where the 10KB size comes from. See https://web.engr.oregonstate.edu/~erwig/papers/Diet_JFP98.pdf which is what I use in https://github.com/NTAP/quant/blob/master/lib/src/diet.c. It uses 24B per 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-353185784

---

From: Christian Huitema <[email-masked]>
Date: Wed, 20 Dec 2017 20:49:17 -0800

Note that there are two problems. The ACK list needs access both up and down, but a doubly linked list does that. The ACK generation needs a SACK dashboard similar to that of TCP, and that requires a small list of range descriptors, but that's not hard either.

I would much rather keep the spec as is. Nick is raising a performance optimization issue. Personally, I would rather like to see the spec stabilize before working full hog on performance optimization. 

-- 
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-353257559

---

From: MikkelFJ <[email-masked]>
Date: Thu, 21 Dec 2017 00:09:11 -0800

The ACK format is fundamental to the implementations data-structures at a deep level, it needs to be roughly sorted out in v1. I can't imagine two completely different approaches running side by side to support v1 and v2 even if I can agree that performance details in general can be sorted later. Even if it is not that hard to run in either direction, once you choose a direction, it is hard to change unless you use a very simplistic approach.

-- 
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-353285387

---

From: MikkelFJ <[email-masked]>
Date: Thu, 21 Dec 2017 01:02:09 -0800

Here is one way the reverse list could be processed in ascending order, assuming MTU < 2^64.

- Stack allocate a 2-byte offset stack of 100 entries (or more if you like)
- Scan the ack frame by pushing an offset for 1 in every 100 range entries seen.
- If the offset table is exhausted, drop the rest of the ACK frame, or cry abuse / bad connection
- Stack allocate a range table of 100 ranges (2 x 8 bytes x 100).
- While offset stack not empty pop an offset from the offset table and fill the range table by reading up to 100 ranges then process that range back to front.

Optimisations:

- Treat the last offset (first in while loop) specially since it does not represent a fixed 100 ranges, and often is the only offset to process.
- Use recursion with max depth = 100 to implement the offset stack, but pass the prealocated range table by reference for memory reuse.
- When the ACK frame has a count of ranges in the header as opposed to a terminal null range, it is easy to detect if there are at most 100 ranges and go for the fast path immediately.

This has low memory overhead and works in L1 cache by reusing the same temp table repeatedly. Likewise, dual passes over the ACK frame is cheap from a cache perspective. Varints are reasonably easy to scan without decoding in the first pass.

While the algorithm may sound a bit involved, it is probably simpler and faster than encoding the ACK frame in ascending order.

-- 
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-353296139

---

From: MikkelFJ <[email-masked]>
Date: Thu, 21 Dec 2017 10:10:57 +0000 (UTC)

With the above algorithm I can sort of buy into the descending ACK argument, but that leaves me with:

The transport doc does not currently explicitly state the ACK Block Count is variable length, but I presume that it is. If so, how do you efficiently do a single pass ACK frame construction when you don't know the size of the count field? Do you just use a large enough integer encoding? Do you use memmove to retro-fit? Do you preprocess to decide?

Transport 8.15:
> ACK Block Count:
The number of Additional ACK Block (and Gap) fields after the First ACK Block.

-- 
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-353312082

---

From: Nick Banks <[email-masked]>
Date: Thu, 21 Dec 2017 15:20:41 +0000 (UTC)

@mikkelfj an easy solution to the ACK Block Count variable is to always encode it using 2 bytes, even if the value could have used 1 byte. That way, you can go back and write the field afterwards.

-- 
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-353377160