4 ms·

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 pa

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.
- zero_iq 5y ago
  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?
  - dtaht 5y ago
    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 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8469111 from: https://datatracker.ietf.org/doc/html/rfc8290 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 |<---------------+ Old +----+ | | | | | +-------+---------+ +------------------+ | | ^ ^ |Credits |Arrival | | |Exhausted v | | | +-----------------+ | | | | | Empty or | | | | New +-------------------+ +-------+ | | Credits Exhausted +-----------------+ Figure 1: Partial State Diagram for Queues between Different States

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.

zero_iq 5y ago
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?
- dtaht 5y ago
  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 https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8469111 from: https://datatracker.ietf.org/doc/html/rfc8290 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 |<---------------+ Old +----+ | | | | | +-------+---------+ +------------------+ | | ^ ^ |Credits |Arrival | | |Exhausted v | | | +-----------------+ | | | | | Empty or | | | | New +-------------------+ +-------+ | | Credits Exhausted +-----------------+ Figure 1: Partial State Diagram for Queues between Different States