Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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...


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       |<---------------+       Old        +----+
   |                 |                |                  |    |
   +-------+---------+                +------------------+    |
           |                             ^            ^       |Credits
           |Arrival                      |            |       |Exhausted
           v                             |            |       |
   +-----------------+                   |            |       |
   |                 |      Empty or     |            |       |
   |      New        +-------------------+            +-------+
   |                 | Credits Exhausted
   +-----------------+

   Figure 1: Partial State Diagram for Queues between Different States




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: