[RFC LOL OMG] pfifo_lat: qdisc that limits dequeueing based on estimated link latency

[Eric Dumazet]

Le mercredi 02 mars 2011 à 16:54 -0500, John W. Linville a écrit :
> This is a qdisc based on the existing pfifo_fast code.  The difference
> is that this qdisc limits the dequeue rate based on estimates of how
> many packets can be in-flight at a given time while maintaining a target
> link latency.
> 
> This work is based on the eBDP documented in Section IV of "Buffer
> Sizing for 802.11 Based Networks" by Tianji Li, et al.
> 
> 	http://www.hamilton.ie/tianji_li/buffersizing.pdf
> 
> This implementation timestamps an skb as it dequeues it, then
> computes the service time when the frame is freed by the driver.
> An exponentially weighted moving average of per fragment service times
> is used to restrict queueing delays in hopes of achieving a target
> fragment transmission latency.  The skb->deconstructor mechanism is
> abused in order to obtain packet service time estimates.
> 
> Signed-off-by: John W. Linville <linville at tuxdriver.com>
> ---
> I took a whack at reimplementing my eBDP patch at the qdisc level.
> Unfortunately, it doesn't seem to work very well and I'm at a loss
> as to why... :-( Comments welcome -- maybe I'm doing something really
> stupid in the math and just can't see it.
> 
> The skb->deconstructor abuse includes adding a union member in the skb
> to record the qdisc->handle on the way out so that it can be used for
> accounting in the deconstructor -- thanks to Neil Horman for the
> suggestion!
> 
> The reason I think this is an idea worth exploring is that existing
> qdisc code doesn't seem to account for the fact that the devices could
> be doing a lot of queueing behind them.  Even Jussi's recent
> sch_fifo_ewma post doesn't seem to take into account how long the device
> holds-on to packets, which limits his ability to fight latency.
> 
> Anyway, all comments appreciated!
> 
>  

Well, many issues in your patch.

skb destructor cannot be used like that (think about locking, and
various context where drivers actually free skbs (from interrupt, from
softirq, or even _before_ sending data on wire).

qdisc_lookup(skb->dev, skb->qdhandle) for example is only safe if run
with RTNL held. Its not meant to be used in fast path at all, but
management code only.

Being able to have a feedback on when a skb is freed (with a
notification of being delivered or dropped) is a recurring idea, so we
might design a stackable infrastructure.