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

11–20 of 47 posts

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

#11

Post by ghusbands »

HALtheWise wrote: post #9

It occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?

Then high load will result in some things staying in a stack for arbitrarily long. For generally the same effect without the unfairness, reducing the size of a queue would be equivalent.

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

#12

Post by codeflo »

HALtheWise wrote: post #9

It occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?

Let’s say the buffer is nearly full, and the egress rate matches the ingress rate almost exactly. Wouldn’t that mean that the bottom of the stack (the oldest package) never gets transmitted, while the top of the stack is churned constantly? If such a situation persists, the oldest packages might not get transmitted for hours, which means they’d be lost for all practical purposes, while still taking up valuable buffer space.

However, and this probably is in the same direction as your idea, the author agrees that when deciding what to drop, dropping the oldest packages is better. I’ll quote item 9 in full because I found this a bit surprising (the sentence in parentheses is especially interesting):

> 9. Tail drop is worst drop. There are several variants of AQM (active queue management) with different tradeoffs, but almost all are better than dropping the newest packet when a queue is full. Even the opposite ("head drop") is better in many cases. (Later TCP ACKs encompass all the information from previous ACKs, so if you have to drop one, it might as well be the oldest one.) CoDel is a more refined AQM. Most AQMs are the same speed or only slightly slower than tail drop.

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

#13

Post by ignoramous »

HALtheWise wrote: post #9

It occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?

> ...queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO.

Kind of. Using 'adaptive lifo' with a variant of CoDel is something Facebook explained they do address tail latency:

Most services process queues in FIFO (first-in first-out) order. During periods of high queuing, however, the first-in request has often been sitting around for so long that the user may have aborted the action that generated the request. Processing the first-in request first expends resources on a request that is less likely to benefit a user than a request that has just arrived. Our services process requests using adaptive LIFO. During normal operating conditions, requests are processed in FIFO order, but when a queue is starting to form, the server switches to LIFO mode. Adaptive LIFO and CoDel play nicely together... CoDel sets short timeouts, preventing long queues from building up, and adaptive LIFO places new requests at the front of the queue, maximizing the chance that they will meet the deadline set by CoDel.

Fail at Scale (2015), https://queue.acm.org/detail.cfm?id=2839461

From a networking point of view, (tcp) bufferbloat across hops is a more complicated problem. Ref this exchange between u/jorangreef and others: https://news.ycombinator.com/item?id=10546651

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

#14

Post by iforgotpassword »

mdzn wrote: post #10
HALtheWise wrote: post #9

It occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?

Wouldn't this cause lots of out-of-order packets?

I guess so, if it's not exactly "one out, one in", that would constantly reorder packets. I think head-drop, like the article says is really the best trivial solution the more I think about it.

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

#15

Post by iforgotpassword »

> Drop packets when demuxing. From y to o, it's best to drop packets at o rather than use backpressure from o to y. Otherwise, a single full output queue could starve the others by stopping y. (Example: imagine if a full queue to a 1 Mbps wifi station could stop traffic to a 100 Mbps wifi station. Some Linux wifi drivers suffer from this.)

Aaah, memories. Combined with point 11, pause frames. I was debugging a weird issue with a gbit switch about 15 years ago.

Port A is a server sending to port B and C. C is only capable of 100mbits. I could send from A to B at 950mbits, and A to C at 50, all good. As soon as I didn't artificially throttle the rate to C at A, it would eventually hit 100mbits for A -> C, which resulted in the rate from A to B also dropping to 100mbits, so a total output of 200 at A. After a lot of trying and poking I saw these mysterious pause frames in Wireshark, which I glanced over before because who'd wanna look at anything below IP... Once I looked them up and disabled pause frames on all the machines, I got the expected result of 900 to B and 100 to C. And once I figured that out it was trivial to formulate a google query that resulted in exactly this problem and the solution to it, which I failed at before.

So ever since then disabling pause frames is one of the first things I do when networking is acting weird.

Bonus: Back then when I told an older colleague about my findings, he basically confirmed "pause frames are evil" with another story: Late 90s they started having a problem in another department that entire network segments sometimes became completely unreachable. And the machines in that segment couldn't even communicate with each other. Randomly power-cycling switches and replugging machines solved the problem. After quite some time they tracked it down: Some folks in said department got shiny new laptops, and whenever those entered standby, the NIC "didn't get the message". Its buffer would eventually fill up (as there was no OS running to handle any packets) and from then on, the network segment would get spammed into oblivion with pause frames.

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

#16

Post by w_t_payne »

How should these lessons be understood in the context of queue oriented models of computation like Lee & Park's Dataflow Process networks, Kahn process network semantics etc?

It seems like these models mainly formalise (and aid understanding of) backpressure based mechanisms for message rate control, but have little to say about dropping packets (as this would break the model).

I wonder if there are stochastic models of computation that could help to formalize packet drop? (These probably exist -- and now I'm motivated to go and look for them).

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

#17

Post by oriolid »

ghusbands wrote: post #11
HALtheWise wrote: post #9

It occurs to me that most of these queue size tradeoffs would be eliminated if the queue operated in a LIFO manner (a stack) instead of FIFO. That way, a burst can naturally get absorbed and re-emitted, but steady state high load doesn't result in increased latency, just packet loss. Can someone with more knowledge of networking enlighten me on why this is a terrible idea?

Then high load will result in some things staying in a stack for arbitrarily long. For generally the same effect without the unfairness, reducing the size of a queue would be equivalent.

The simple solution is to drop stuff from the bottom of the stack. Citing the article, "Tail drop is worst drop".

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

#18

Post by [deleted] »

w_t_payne wrote: post #16

How should these lessons be understood in the context of queue oriented models of computation like Lee & Park's Dataflow Process networks, Kahn process network semantics etc? It seems like these models mainly formalise (and aid understanding of) backpressure based mechanisms for message rate control, but have little to say about dropping packets (as this would break the model). I wonder if there are stochastic models…

[deleted]

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

#19

Post by Dowwie »

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.

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

#20

Post by Bluecobra »

To add to this, there is some inherent latency when queuing packets as well so it’s best to avoid it as much as possible if latency is a concern. Low latency/cut-through switches have really shallow buffers on purpose and will quickly drop packets. To avoid queuing/drops you need to make sure you have ample bandwidth to absorb any microbursts. For example, if you have a 1Gb NIC that is constantly bursting at 1.2Gbps you should upgrade it to 10Gb.
Post reply on HN