[Bloat] RED against bufferbloat

[Jonathan Morton]

> On 25 Feb, 2015, at 21:25, Hal Murray <hmurray at megapathdsl.net> wrote:
> 
>> That's easy enough. You can fit an awful lot of linked list pointers into
>> the space of a single IP packet. Even if you're only assigning 64KB per
>> subscriber, you can store 43 full packets and still have pointers to spare.
>> A properly functioning AQM should mostly keep the queue smaller than that. 
> 
> Is a slot for the head-of-list pointer all the information you need to 
> remember for an empty queue?  Or do you need some memory of recent traffic?

The Linux implementation of fq_codel uses DRR for the FQ bit.

For that, you need a head pointer (for fast dequeue), a tail pointer (for fast enqueue), and a deficit counter (to implement the fairness) per flow.  With some granularity in the pointers, or else with a fixed queue arena of some tens of megabytes maximum, you can squeeze all that into 8 bytes per flow quite comfortably.

You also need a set of codel variables per flow (these are not large), a free-list of spaces to put new packets, and a ‘next’ pointer per enqueued packet.  The latter two might already be present in some form, depending on the FIFO implementation - that is, if it’s not just a ring buffer.

With these taken into account, I think we’re still looking at 40+ full-size packets in a 64KB arena, or a larger number if smaller packets are mixed in.  DRR will tend to service flows with smaller packets more often, leading to bandwidth fairness.

 - Jonathan Morton