4 ms·

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 fai

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
dtaht 5y ago
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 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/59002 https://forum.openwrt.org/t/aql-and-the-ath10k-is-lovely/590...

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

dtaht 5y ago

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 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/59002 https://forum.openwrt.org/t/aql-and-the-ath10k-is-lovely/590...