From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-we0-f171.google.com (mail-we0-f171.google.com [74.125.82.171]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client did not present a certificate) by huchra.bufferbloat.net (Postfix) with ESMTPS id F388E201261 for ; Tue, 4 Sep 2012 11:35:58 -0700 (PDT) Received: by weys43 with SMTP id s43so7684912wey.16 for ; Tue, 04 Sep 2012 11:35:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=9uTWeip/U3tBn06PkyDCnW7z75PYe1JU/lthc+78HaA=; b=zacv0VFmH6BQZRRqC0SNFHCVrVjL1zX+uMx19TRPAuOdUFw5zrjXlvYtWtGdS1gSEY rn6opeMrxofgslfc8MpwZMF6kI1XWYi9/8COlw4d1Pnd4OuoyDTwXpL55gAuXKgFpPlK e2M6b507972fnx1ucC5zjSkwCJSyushvLlU+NwLeeRdssGF+FezpgSL0bS0s5ZBGfeXf ahA9YnSJAIu/2MFx6R6065Aw7BrjwIgujuOXAZvNngaCgh2pEeSHeQ+TU+aUpfkKL92C c2EejUBA57sBT+6r0RIlTbLOXKb9CTnUa4dSEU7lH8E6VKZlk+xFCoPf7HJOnK/S6cXj ds/g== MIME-Version: 1.0 Received: by 10.180.98.200 with SMTP id ek8mr32494257wib.0.1346783756663; Tue, 04 Sep 2012 11:35:56 -0700 (PDT) Received: by 10.223.159.134 with HTTP; Tue, 4 Sep 2012 11:35:56 -0700 (PDT) Date: Tue, 4 Sep 2012 11:35:56 -0700 Message-ID: From: Dave Taht To: codel@lists.bufferbloat.net Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Subject: [Codel] fq_codel: revenge of the standing queue X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 04 Sep 2012 18:35:59 -0000 As presently implemented, multi-queue fq_codel has a few FIFO codel assumptions baked into it. The first, already fixed, was that codel's state was completely reset when a fq_codel queue was emptied. This has been fixed via a patch to mainline. However there are other places where codel's state is reset where (perhaps!) it shouldn't. I note that I am NOT at this time recommending these changes to the codebase, the current behavior "does little harm", and eventually gets the standing queue down to a reasonable, if not ideal, minimum. I think it has the potential to run away at seriously high numbers of flows, but haven't tested that. I've tried various combinations of fixes below and run into multiple issues. I think some of the stability/fairness problems I've had might be an interaction with TSQ, and need to revise the testbed to be a pure routing environment, and that is going to take time that I don't have right now. I hope that in pointing out these issue others will fiddle, and I do have various patches that I can make available, that try different stuff. My basic test is running 75 TCP_MAERTS streams and 75 TCP_STREAM streams at 10 or 100Mbit, for 60 seconds or more, with which I end up with a standing queue of 80-150 packets (depending on codel version and TSQ) and consequent large RTT. I am mostly using the nearly-current-ns2 model (ported to linux) of codel.h. These results hold as a function of the number of streams. 1) An empty queue in fq_codel has no meaningful information. in: codel_should_drop if (!skb) { vars->first_above_time =3D 0; return false; } I believe the codel intent here was to reset codel's state when the single FIFO queue was emptied. In fq_codel's case, an empty queue contains no information about the state, really, and a if (!skb) { if(sch->qstats.backlog <=3D mtu) vars->first_above_time =3D 0; return false; } comes closer to the intent. That said, the null skb then bleeds into the rest of the algorithm in codel_dequeue if (!skb) { vars->dropping =3D false; return skb; } later on there's if (vars->dropping) { if (!drop) { /* sojourn time below target - leave dropping state= */ vars->dropping =3D false; and the same assumption within the while loop and in the else if(drop)... I'm pretty sure that leaving of dropping state just because this fq_codel queue is (temporarily) empty is not the right thing, and that the main reason for exiting the dropping state should be getting under the target delay. It might make sense to reschedule the next drop on a null skb, perhaps after reducing count... While I've fiddled with these ideas, and got some drainage, I do get fairly big oscillations in queue depth, and starvation of some flows, in various versions of my explorations. Which led me to looking at quantums and... 2) New flows The next issue (at these 10 and 100Mbit rates) is the "new flow" idea in fq_codel. It is VERY useful pushing sparse flows to the fore of the queues, and also provided a boost to long RTT flows. However at high levels of occupancy and low bandwidth, flows empty their queue rapidly, become "new flows", and then mislead codel for that flow into resetting itself again, since we end up with a short delay for the re-entrance. This isn't a particularly horrible behavior, but as my own hope for this feature was to make voip better primarily, and everything else we got from it was a bonus. TSQ really made this oddity show up big. I think on routed traffic it will be less of an issue. Anyway, instead of depending on "empty queue" as a sign of a new flow, I have fiddled with adding the consideration if (list_empty(&flow->flowchain)) { if(codel_time_after(now - flow->cvars.last_delivery, q->cparams.target)) { list_add_tail(&flow->flowchain, &q->new_flo= ws); q->new_flow_count++; flow->deficit =3D q->quantum; } else { list_add_tail(&flow->flowchain, &q->old_flo= ws); } } which seems to do more of what I'd wanted in the first place. (last delivery is set on every delivery from the flow) ... 3) I do kind of like amortizing the slope of the delay over an interval (are we winning? Losing? By how much?) and trying to inform decisions that way... --=20 Dave T=E4ht http://www.bufferbloat.net/projects/cerowrt/wiki - "3.3.8-17 is out with fq_codel!"