Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Things we finally know about network queues (2017)

apenwarr.ca

Post reply on HN
Print view View original

41–47 of 47 posts

Re: Things we finally know about network queues (2017)

#41

Post by toast0 »

HALtheWise wrote: post #36
toast0 wrote: post #31

Earlier quoted context omitted.

This isn't a great idea at the packet level. You get really bad results by intentionally reordering packet in a tcp connection. It's not going to be good for any flow that expects packets to arrive in order for the most part (voip calls etc). Plus accumulating old packets isn't great. FIFO preserves order, but the typical behavior is to drop incomming packets when the buffer is full (or to make an absurdly sized buff…

Can you elaborate more on why applications handle packet reordering badly? Is it just that applications are written to assume in-order packets are the "fast path" and need to use less optimized code when things come in out-of-order, or is there some other heuristics that assume packet reordering is rare that would misfire here?

TCP is going to be not great because when you receive packets out of order, there's a feedback loop that leads to the source retransmitting the presumed missing, but possibly just delayed packets. Adding more duplicate data to your congested queue makes things worse / keeps them bad. It's much better to drop some packets from the flow than to intentionally misorder them. This property does make it harder to load balance tcp over multiple connections; you get better results if you hash flows, so one tcp connection always goes over the same physical connection, and should remain ordered... Round robin packet sending might be nice, since you wouldn't end up with uneven utilization of individual physical connections in an aggregated connection, but the tcp stack behavior would be much worse and real world bandwidth would not be useful. Actually handling tcp packets out of order isn't nice either, but if the options are drop a packet or delay an earlier packet to send after a later one, we're going to have to handle some packets out of order. This is what ECN (explicit congestion notification) was supposed to help, if you could mark packets as congested before the congestion got bad enough to drop packets; of course, that was hard to get deployed.

Things like voip or gaming are going to have trouble with out of order packets too. If you already did something to workaround the missing packet, if it eventually arrives late, you may not have any use for it. If I already played silence (or ??) to get through a missed sample, I can't go back and put in the late sample. Etc. Late at that point is not better than never.

There are certainly ways to make protocols where late is better than never; you could have a bulk file transfer protocol that sent all data once before resending or something, but that's not common.

Re: Things we finally know about network queues (2017)

#42

Post by HALtheWise »

toast0 wrote: post #41
HALtheWise wrote: post #36

Earlier quoted context omitted.

Can you elaborate more on why applications handle packet reordering badly? Is it just that applications are written to assume in-order packets are the "fast path" and need to use less optimized code when things come in out-of-order, or is there some other heuristics that assume packet reordering is rare that would misfire here?

TCP is going to be not great because when you receive packets out of order, there's a feedback loop that leads to the source retransmitting the presumed missing, but possibly just delayed packets. Adding more duplicate data to your congested queue makes things worse / keeps them bad. It's much better to drop some packets from the flow than to intentionally misorder them. This property does make it harder to load bala…

I think TCP's logic is more subtle than "if anything comes in out of order, retransmit", in particular, there's a "Retransmission Timeout" that converges to something like ~2x the average roundtrip latency. I assume that custom UDP-based protocols used by VoIP and such will have similar provisions, where they don't declare a packet "lost" until a significant period of time has elapsed. My understanding is that the reason these mechanisms don't handle multiple connections well is because the two connections might have dramatically different typical latencies, not because the packets may be mildly misordered on the other end.

I'm not sure if more modern "smart" protocols that themselves explicitly try to measure and model the underlying network buffers would be confused by LIFO though, especially since the variance in round trip latency will be higher with a LIFO queue.

https://www.catchpoint.com/blog/tcp-rtt

Re: Things we finally know about network queues (2017)

#43

Post by kqr »

Dowwie wrote: post #19
kqr wrote: post #2

This is a good collection of recommendations. At a new job, I often end up making changes to internal queues that (it turns out) conform to these recommendations, and get better performance and reliability out of it. Though I didn't learn it by engineering networks like the author -- I took the ideas from lean product development and applied them also to software. > Corollary: limit queue length to a statistically la…

I'm very interested in your approach applying lean product development patterns to network engineering.

It's really nothing special, just some general principles that are sensible to me:

- Production levelling/burst smoothing early in the process, so other steps don't have to bother with variability.

- WIP constraints/limited queue sizes both to reveal problems and improve latency.

- Kanban/backpressure to stop the problems at the source, and help troubleshooting.

- Using Little's law as a guideline in tradeoffs between batch size and latency and size of system.

- Deliberately shed load when it cannot be served in time, rather than vainly holding on to it for dear life because "surely we cannot outright reject work?!"

- Dropping at the head of queues to improve latency and serve the fresher requests sooner.

There's probably a lot more, and TFA covers some of it too.

Re: Things we finally know about network queues (2017)

#44

Post by toast0 »

HALtheWise wrote: post #42
toast0 wrote: post #41

Earlier quoted context omitted.

TCP is going to be not great because when you receive packets out of order, there's a feedback loop that leads to the source retransmitting the presumed missing, but possibly just delayed packets. Adding more duplicate data to your congested queue makes things worse / keeps them bad. It's much better to drop some packets from the flow than to intentionally misorder them. This property does make it harder to load bala…

I think TCP's logic is more subtle than "if anything comes in out of order, retransmit", in particular, there's a "Retransmission Timeout" that converges to something like ~2x the average roundtrip latency. I assume that custom UDP-based protocols used by VoIP and such will have similar provisions, where they don't declare a packet "lost" until a significant period of time has elapsed. My understanding is that the re…

Looking at voip specifically, you've got what's called a jitter buffer, which lets you collect late packets, either out of order or delayed, and still use them, but delay is bad for user experience, so you tend to make that buffer as small as you can. You don't retransmit voip packets, because if they're not fresh, they're not useful. LIFO doesn't make sense for voip, because either you run a very long jitter buffer and nobody wants to talk with you like that, or the delayed packets can't be used.

The tcp retransmit timer is used when you send a packet (or packets) and don't get any acknowledgements. But if you send many packets, and the peer misses one (because it's delayed/out of order), it will send an ack of the last in order sequence (and hopefully selective ack too, it's 2022). If you recieve enough acks of the same packet, that triggers fast retransmit; by rfc2001 and updates, three duplicate acks is the threshold to retransmit, without waiting for the retransmit timer. LIFO would significantly harm the network in case of bursty traffic: if my flow sends 5 packets back to back (which is common with tcp segmentation offloading), and they get queued, they'll get sent to the peer in the exact wrong order, and thaf peer will send the same ack for the first foud packets, before sending a new ack on the fifth. My side will get those first four acks, and retransmit the first packet of the burst, then get the fifth ack, and maybe release a new burst. That's an extra full packet, plus it's typical to only send every other ack normally, so that's extra acks on the return side. Dropping a packet in the flow would still result in extra acks though, but the retransmitted data packet wouldn't be a duplicate through that bottleneck, because the first one was dropped before the bottleneck.

Re: Things we finally know about network queues (2017)

#45

Post by HALtheWise »

toast0 wrote: post #44
HALtheWise wrote: post #42

Earlier quoted context omitted.

I think TCP's logic is more subtle than "if anything comes in out of order, retransmit", in particular, there's a "Retransmission Timeout" that converges to something like ~2x the average roundtrip latency. I assume that custom UDP-based protocols used by VoIP and such will have similar provisions, where they don't declare a packet "lost" until a significant period of time has elapsed. My understanding is that the re…

Looking at voip specifically, you've got what's called a jitter buffer, which lets you collect late packets, either out of order or delayed, and still use them, but delay is bad for user experience, so you tend to make that buffer as small as you can. You don't retransmit voip packets, because if they're not fresh, they're not useful. LIFO doesn't make sense for voip, because either you run a very long jitter buffer…

Makes sense, thanks for the info.

Re: Things we finally know about network queues (2017)

#46

Post by dtaht »

zero_iq wrote: post #30
dtaht wrote: post #28

Earlier quoted context omitted.

Head drop, so long as it preserves a "round" so a malignant sender cannot force all other traffic out of the queue, is great . This is what fq-codel, fq-pie, and cake do.

Can you clarify what you mean by a "round" here, please? Do you mean a complete round-robin pass of clients (or whatever segmentation method is used) in the fair queue?

Close. A major innovation in the fq-codel derived algorithms over former forms of FQ like DRR and SFQ is what we call the sparse flow optimization. Packets from flows that have an arrival rate lower than the departure rate of 1 quantums worth of packets from all other flows (a "round") observe no queueing, where in drr or sfq, new flows always go to the back of the fq'd flows. (still a huge win over fifo or pure aqm)

This among other things made codel's head drop aqm safe and stable enough to deploy.

Paper: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8469111

from: https://datatracker.ietf.org/doc/html/rfc8290

The step that moves an empty queue from the list of new queues to the end of the list of old queues before it is removed is crucial to prevent starvation. Otherwise, the queue could reappear (the next time a packet arrives for it) before the list of old queues is visited; this can go on indefinitely, even with a small number of active flows, if the flow providing packets to the queue in question transmits at just the right rate. This is prevented by first moving the queue to the end of the list of old queues, forcing the scheduler to service all old queues before the empty queue is removed and thus preventing starvation.

   The resulting migration of queues between the different states is
   summarised in the state diagram shown in Figure 1.  Note that both
   the new and old queue states can additionally have arrival and
   dequeue events that do not change the state; these are omitted in the
   figure.

   +-----------------+                +------------------+
   |                 |     Empty      |                  |
   |     Empty       |

Re: Things we finally know about network queues (2017)

#47

Post by dtaht »

zero_iq wrote: post #30
dtaht wrote: post #28

Earlier quoted context omitted.

Head drop, so long as it preserves a "round" so a malignant sender cannot force all other traffic out of the queue, is great . This is what fq-codel, fq-pie, and cake do.

Can you clarify what you mean by a "round" here, please? Do you mean a complete round-robin pass of clients (or whatever segmentation method is used) in the fair queue?

The "sparse" and "rounds" concepts also works really well as a per station wifi scheduler, where it is now the default for a plethora of chipsets in linux. Some plots of which I will forever be proud here:

https://arxiv.org/pdf/1703.00064.pdf

Before/After on an ath10k chip here:

https://forum.openwrt.org/t/aql-and-the-ath10k-is-lovely/590...

Post reply on HN