We could reliably say that most of the cost comes from DRR.
FQ based on virtual times, such as start time, would cost O(log N) where N is the number of packets in the queuing system.
DRR as designed by Varghese provided a good approximation with O(1) cost. So you're not wrong Dave
at least for DRR. But I don't see any other cost to add to the check list.
Of course every algorithm can come with a different constant in terms of cost but that is really implementation dependent.
SFQ in Linux is using Longest Queue Drop which brings back non constant delay cost because
it has to search the longest queue, which give O(log F) (worst case) where F is the number of active flows (with at least one packet in the queue).
Smaller than start time fair queuing.
But DRR, as implemented in fq_codel, does not do that as there is a single AQM per queue.
Which brings more cost in terms of memory but not in terms of time.
I'm not sure about the DRR implementation in CAKE, but there should be no differences in terms of complexity.
M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round-robin," in
IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375-385, June 1996. doi: 10.1109/90.502236