[Codel] SfqCodel

[Jonathan Morton]

SFQ is quite simple in essence. It performs flow isolation, allowing
packets from different flows to bypass each other.

A flow is defined as packets possessing a common 5-tuple of source address,
destination address, protocol (TCP, UDP, ICMP etc), source port and
destination port.

Ideally, Fair Queuing would perfectly separate all flows into queues, then
service each of them equally and fairly in turn, for some measure of
equality and fairness. This would provide ideal flow isolation.

SFQ is not quite this ideal model. The 5-tuple is converted into a hash
value which is used directly to index into a fixed list of queues; thus
hash collisions can occur which mix traffic from multiple flows in the same
queue. It also services queues in a strict round-robin, delivering one
packet per cycle, regardless of the relative sizes of these packets. These
are compromises intended to minimise CPU overhead and implementation
complexity. (They made sense at the time when SFQ was cutting edge, which
was a long time ago.)

Fq_codel as implemented in Linux is not the same as sfq_codel as
implemented in ns2. Instead of using SFQ to provide flow isolation, it uses
DRR++, which provides bytewise fairness and a priority boost to sparse
flows. Recent work has also found a way to significantly reduce the hash
collision problem without imposing much additional overhead, and this has
been incorporated into cake.

- Jonathan Morton
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/codel/attachments/20150410/333fce6a/attachment-0002.html>