[Bloat] Designer of a new HW gadget wishes to avoid bufferbloat

[Albert Rafetseder]

Am 26.10.2012 um 20:54 schrieb Michael Spacefalcon:

> Albert Rafetseder <albert.rafetseder+bufferbloat at univie.ac.at> wrote:
> 
>> You must also rule out ATM cell loss and reordering. Otherwise, there is =
>> too little data in your receive buffer to reassemble the transmitted =
>> frame (temporarily with reordering, terminally with loss). This calls =
>> for a timeout of sorts.
> 
> (...)
> The issue of reordering is relevant only when there are 2 or more VCs
> on the same physical circuit, and I have yet to encounter an xDSL
> circuit of any flavor that is set up that way.
> (...)

> Cell loss: it can't be detected directly, and it manifests itself in
> the reassembled AAL5 packets appearing to be corrupt (bad CRC-32 at
> the end).  If the first cell or some middle cell of a packet gets
> lost, only that one packet is lost as a result.  If the last cell of a
> packet gets lost, the overall IP-over-ATM link loses two packets: the
> one whose last cell got lost, and the next one, which appears to be a
> continuation of the previous one.  So that's another way in which ATM
> on an xDSL circuit is worse than Ethernet or HDLC.

I.e., you rule out ATM cell loss and reordering! :-)

>> Suppose you have a list of starts of packets addresses within =
>> your cell transmit ring buffer. Drop the first list element. Head drop! =
>> Done! Once the current packet's cells are transmitted, you jump to the =
>> next start of packet  in the list, wherever it is. As long as you ensure =
>> that packets you receive on the HDLC side don't overwrite the cells you =
>> are currently transmitting, you are fine. (If the buffer was really =
>> small, this probably meant lots of head drop.)
> 
> Let me try to understand what you are suggesting.  It seems to me that
> you are suggesting having two separate elastic buffers between the
> fill side and the drain side: one storing cells, the other storing
> one-element-per-packet information (such as a buffer start address).
> You implement head drop by dropping the head element from the buffer
> that reckons in packets, rather than cells.  But the cells are still
> there, still taking up memory in the cell buffer, and that cell
> storage memory can't be used to buffer up a new ingress packet because
> that storage sits in the middle between cells of a packet in the
> middle of transmission and the next packet which is still "officially"
> in the queue.

I'm suggesting a *ring* buffer. Let me try to sketch what I mean (view in your favorite fixed-space font). ^r is the read pointer (output to SDSL, head of the queue), ^w is the write pointer (input from HDLC, tail). Pointers can only go right, but all addressing is done modulo the buffer size, so you start over on the left side if you were ever to point past the buffer.

Currently, the read pointer processes "2", whereas the write pointer will overwrite "A" next. 

0123456789ABCDEF
  ^r      ^w

Now the read pointer has progressed a bit, but the write pointer was much faster:

xyz3456789rstuvw
   ^w ^r

Obviously, ^w must not overtake ^r. The trick is now to push the read pointer forward a bit instead of holding back the write pointer. Push it how far? Far enough to buy us some headroom, e.g. given how likely you estimate worst-case packets will accumulate. Finally, we will have lost buffer slots (marked with asterisks) from the head of the queue, but were able to save all of the new incoming data, which means no tail drop:

xyz!#$6*****tuvw
      ^w    ^r

> But I can see how perhaps the head drop mechanism you are suggesting
> could be used as a secondary AQM-style packet dropper - but it can't
> be the primary mechanism which ensures that the fill logic doesn't
> overwrite the cell buffer RAM which the drain side is still reading
> from.  I was talking about the latter in my original post when I said
> that I couldn't do anything other than tail drop.

The sketch above applies to both the list of addresses of cell starts and the actual cell buffer. (You could also implement both ring buffers as a single one, as a linked list: Store the address of the start cell of the next packet in front of the cells of the current packet. To head-drop packets, dereference the pointer multiple times. ASCII diagrams on request :-)

> 3. The CoDel (and bufferbloat/AQM) folks in general seem to view the
>   arrival and departure of packets as atomic instantaneous events.
>   While the latter may be true for a software router which receives
>   packets from or hands them over to a hardware Ethernet interface in
>   an instantaneous atomic manner, that model absolutely does not hold
>   for the underlying HW device itself as it reformats a stream of
>   packets from HDLC to SDSL/ATM in a flow-through fashion, without
>   waiting for each packet to be received in its entirety.

That's an interesting notion indeed. Still, even for sending cells from packets that haven't fully gone into the ring buffer from the HDLC side, I think that the approach described would work. The closer the write and read pointers get, the more headaches, though.