5 ms·

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

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?

toast0 5y ago
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 buffer), when it's usually better to drop older packets than fresh packets.
- HALtheWise 5y ago
  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?
  - toast0 5y ago
    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.
    - HALtheWise 5y ago
      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 https://www.catchpoint.com/blog/tcp-rtt
      - toast0 5y ago
        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.
mdzn 5y ago
Wouldn't this cause lots of out-of-order packets?
- HALtheWise 5y ago
  Yep, but IP doesn't provide an ordering guarantee at the link level anyway, and higher-level protocols have sequence numbers so they can reassemble things correctly. If those higher-level mechanisms aren't up for the task of handling lots of small reorderings, that would obviously be an issue.
- iforgotpassword 5y ago
  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.
ghusbands 5y ago
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.
- oriolid 5y ago
  The simple solution is to drop stuff from the bottom of the stack. Citing the article, "Tail drop is worst drop".
codeflo 5y ago
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.
- HALtheWise 5y ago
  Apologies for not making this clear, I was definitely assuming a LIFO buffer would drop the oldest message when full, since dropping the newest message has the issue you describe. In that case, for a prolonged period of ingress slightly over egress, the buffer will contain the N most recently received messages that haven't been transmitted, which seems optimal, but _also_ will have no queueing-induced latency for new messages. If there's a gap in the incoming data stream, a LIFO buffer would emit the most-recent (and most likely to be useful) data first. Most importantly, there's now no performance drawback for making the buffer bigger, so tuning it is way less dependent on your expected operating environment. One other optimization that would probably make sense in a practical implementation is a "max age" limit on things popped from the stack, so that an old message can't sit around for several seconds if the ingress rate happens to exactly matches egress. This limit can be fairly long though (~1s is fine), since it's just trying to approximate when a higher-level protocol would already have completed a full roundtrip and requested retransmit.
- dtaht 5y ago
  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.
ignoramous 5y ago
> ...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 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 https://news.ycombinator.com/item?id=10546651
- HALtheWise 5y ago
  Switching to LIFO adaptively is a cool idea, thanks for sharing that Facebook is using that at scale, I didn't know that. Thinking about eliminating bufferbloat was the original line of thinking that made me think of LIFO queues, since the latency properties of a drop-oldest LIFO queue are (I think) only related to the burstiness of the traffic flow, not the volume, and so steady flow cannot ever cause any intermediate node to hold a persistently large queue of messages that will ever be transmitted. From the perspective of an application transmitting over the network, a steady flow through a saturated link results in packet loss but not latency, while a bursty flow results in small burst-sized latencies to random packets, and some reordering as a result. Because the _downstream_ traffic from one saturated link is typically not very bursty when it hits the next saturated link, negative effects won't accumulate in the same way that latency does in bufferbloat.

toast0 5y ago

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 buffer), when it's usually better to drop older packets than fresh packets.

HALtheWise 5y ago
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?
- toast0 5y ago
  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.
  - HALtheWise 5y ago
    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 https://www.catchpoint.com/blog/tcp-rtt
    - toast0 5y ago
      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.

mdzn 5y ago

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

HALtheWise 5y ago
Yep, but IP doesn't provide an ordering guarantee at the link level anyway, and higher-level protocols have sequence numbers so they can reassemble things correctly. If those higher-level mechanisms aren't up for the task of handling lots of small reorderings, that would obviously be an issue.
iforgotpassword 5y ago
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.

ghusbands 5y ago

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.

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

codeflo 5y ago

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.

HALtheWise 5y ago
Apologies for not making this clear, I was definitely assuming a LIFO buffer would drop the oldest message when full, since dropping the newest message has the issue you describe. In that case, for a prolonged period of ingress slightly over egress, the buffer will contain the N most recently received messages that haven't been transmitted, which seems optimal, but _also_ will have no queueing-induced latency for new messages. If there's a gap in the incoming data stream, a LIFO buffer would emit the most-recent (and most likely to be useful) data first. Most importantly, there's now no performance drawback for making the buffer bigger, so tuning it is way less dependent on your expected operating environment. One other optimization that would probably make sense in a practical implementation is a "max age" limit on things popped from the stack, so that an old message can't sit around for several seconds if the ingress rate happens to exactly matches egress. This limit can be fairly long though (~1s is fine), since it's just trying to approximate when a higher-level protocol would already have completed a full roundtrip and requested retransmit.
dtaht 5y ago
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.

ignoramous 5y ago

> ...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 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 https://news.ycombinator.com/item?id=10546651

HALtheWise 5y ago
Switching to LIFO adaptively is a cool idea, thanks for sharing that Facebook is using that at scale, I didn't know that. Thinking about eliminating bufferbloat was the original line of thinking that made me think of LIFO queues, since the latency properties of a drop-oldest LIFO queue are (I think) only related to the burstiness of the traffic flow, not the volume, and so steady flow cannot ever cause any intermediate node to hold a persistently large queue of messages that will ever be transmitted. From the perspective of an application transmitting over the network, a steady flow through a saturated link results in packet loss but not latency, while a bursty flow results in small burst-sized latencies to random packets, and some reordering as a result. Because the _downstream_ traffic from one saturated link is typically not very bursty when it hits the next saturated link, negative effects won't accumulate in the same way that latency does in bufferbloat.