From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-02-iad.dyndns.com (mxout-230-iad.mailhop.org [216.146.32.230]) by lists.bufferbloat.net (Postfix) with ESMTP id C56D52E0050 for ; Mon, 21 Feb 2011 08:12:20 -0800 (PST) Received: from scan-02-iad.mailhop.org (scan-02-iad.local [10.150.0.207]) by mail-02-iad.dyndns.com (Postfix) with ESMTP id A18D8834D1D for ; Mon, 21 Feb 2011 16:12:21 +0000 (UTC) X-Spam-Score: 0.0 () X-Mail-Handler: MailHop by DynDNS X-Originating-IP: 76.96.62.17 Received: from qmta10.westchester.pa.mail.comcast.net (qmta10.westchester.pa.mail.comcast.net [76.96.62.17]) by mail-02-iad.dyndns.com (Postfix) with ESMTP id 2CDCB834CA7 for ; Mon, 21 Feb 2011 16:12:21 +0000 (UTC) Received: from omta08.westchester.pa.mail.comcast.net ([76.96.62.12]) by qmta10.westchester.pa.mail.comcast.net with comcast id AgCL1g0040Fqzac5AgCLkJ; Mon, 21 Feb 2011 16:12:20 +0000 Received: from [192.168.1.119] ([98.229.99.32]) by omta08.westchester.pa.mail.comcast.net with comcast id AgCG1g00e0hvpMe3UgCJGv; Mon, 21 Feb 2011 16:12:20 +0000 Message-ID: <4D628EDE.1010102@freedesktop.org> Date: Mon, 21 Feb 2011 11:12:14 -0500 From: Jim Gettys Organization: Bell Labs User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.13) Gecko/20101208 Lightning/1.0b2 Thunderbird/3.1.7 MIME-Version: 1.0 To: bloat-devel@lists.bufferbloat.net Subject: Re: [RFC v2] mac80211: implement eBDP algorithm to fight bufferbloat References: <1297907356-3214-1-git-send-email-linville@tuxdriver.com> <1298064074-8108-1-git-send-email-linville@tuxdriver.com> <1298302086.3707.13.camel@jlt3.sipsolutions.net> In-Reply-To: <1298302086.3707.13.camel@jlt3.sipsolutions.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Mon, 21 Feb 2011 08:19:25 -0800 Cc: Dan Williams , Javier Cardona , Dave Woodhouse X-BeenThere: bloat-devel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Developers working on AQM, device drivers, and networking stacks" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 21 Feb 2011 16:12:21 -0000 On 02/21/2011 10:28 AM, Johannes Berg wrote: > On Fri, 2011-02-18 at 16:21 -0500, John W. Linville wrote: >> This is an implementation of the eBDP algorithm as 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 before handing it to the >> hardware driver, 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. >> >> Signed-off-by: John W. Linville >> --- >> v1 -> v2: >> - execute algorithm separately for each WMM queue >> - change ewma scaling parameters >> - calculate max queue len only when new latency data is received >> - stop queues when occupancy limit is reached rather than dropping >> - use skb->destructor for tracking queue occupancy >> >> Johannes' comment about tx status reporting being unreliable (and what >> he was really saying) finally sunk-in. So, this version uses >> skb->destructor to track in-flight fragments. That should handle >> fragments that get silently dropped in the driver for whatever reason >> without leaking queue capacity. Correct me if I'm wrong! > > Yeah, I had that idea as well. Could unify the existing skb_orphan() > call though :-) > > However, Nathaniel is right -- if the skb is freed right away during > tx() you kinda estimate its queue time to be virtually zero. That > doesn't make a lot of sense and might in certain conditions exacerbate > the problem, for example if the system is out of memory more packets > might be allowed through than in normal operation etc. > > Also, for some USB drivers I believe SKB lifetime has no relation to > queue size at all because the data is just shuffled into an URB. I'm not > sure we can solve this generically. I'm not really sure how this works > for USB drivers, I think they queue up frames with the HCI controller > rather than directly with the device. Let me give a concrete example: I checked with Javier Cardona about the Marvell module (libertas driver) used on OLPC a couple months ago. It turns out there are 4 packets of buffering out in the wireless module itself (clearly needed for autonomous forwarding). There is also one packet buffer in the device driver itself; Dave Woodhouse says it simplified the driver greatly. I don't know if anyone has been thinking about how to manage the buffering from top to bottom, with devices that may do internal buffering in various places. > > Finally, this isn't taking into account any of the issues about > aggregation and AP mode. Remember that both with multiple streams (on > different ACs) and even more so going to different stations > (AP/IBSS/mesh modes, and likely soon even in STA mode with (T)DLS, and > let's not forget 11ac/ad) there may be vast differences in the time > different frames spend on a queue which are not just due to bloated > queues. I'm concerned about this since none of it has been taken into > account in the paper you're basing this on, all evaluations seem to be > pretty much based on a single traffic stream. > > Overall, I think there should be some more research first. This might > help in some cases, but do we know it won't completely break throughput > in other cases? > - Jim