From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x22c.google.com (mail-lf0-x22c.google.com [IPv6:2a00:1450:4010:c07::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id EC4413B25E; Sun, 1 May 2016 00:47:18 -0400 (EDT) Received: by mail-lf0-x22c.google.com with SMTP id m64so3646937lfd.1; Sat, 30 Apr 2016 21:47:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=dnnpzF3Dllv+sRnSI9cAhicbi45TZOoz3jMKknnCL1s=; b=GeW4YITaudoegqqBTTZCV065Q0qZmkVWBu5pP/C1aGuqGMwwb9nhmp4pHtEiBX5+AI 3JUCrAvSK1TjZiVGMujqPSWyWsPQKeXBaLq8Vi8IvGRAr5hvE+3QJLRBA5UtTooISkdv k6CQPP+lHz2H+snqIW6d6VXGkhcXe2yYcUAjnJmAPYCjw/HporzD1l6hhVb6F6q1NDZv 33fM2SFH/myC00HmJv0UfN7Rg7AXGzDzusM9IH/2wd9IFO1wXK5mXp9zAYcZFlI6NkNr GtMAgYSLUcyI6S1J95wSdl4OCWLo1wamWhlTez5pW5S04tFvAPmQEpPqaR9xeZs8VKho eTYw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=dnnpzF3Dllv+sRnSI9cAhicbi45TZOoz3jMKknnCL1s=; b=Um8JkNdid2eNtotv2DtoheoxWRgThbxTNTfwATsaLBFeeiBenSmbZ3xLVu6LDXKN1+ 5Di6oqTaYAxUWLxJXMDhdSt1OITVdB8WJcqmok0McVP8XW0B5lVOLB6Zj/IRgP/oOqDj IR57OlTXdwB9jpgcDKwsGr+uXf5kPCOBe8rJtfGtzGV91zkfh3sn82uWreDYh2O84OES eapGw7EQg8WOC52uMDm9JEepzBVCdoQFhwR3JumLpfQFbvDxr9flEIPrF3Z4HiXdBrC4 QdPLqr+p2KLcbMvANUT/JTc/0aPi5j/PnEqKg5eQdq+/Ao3LrF0eho0txGHnLlJrVevh TvTA== X-Gm-Message-State: AOPr4FWYTcIJrB36RZuGz0fFWv/yrRvexWCJ37wjtxBFCHdFa9IZIXAl/P7bpo6WNhtmvQ== X-Received: by 10.112.95.20 with SMTP id dg20mr12131446lbb.58.1462078037729; Sat, 30 Apr 2016 21:47:17 -0700 (PDT) Received: from bass.home.chromatix.fi (37-33-67-252.bb.dnainternet.fi. [37.33.67.252]) by smtp.gmail.com with ESMTPSA id n37sm3505549lfg.46.2016.04.30.21.47.10 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 30 Apr 2016 21:47:16 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Jonathan Morton In-Reply-To: Date: Sun, 1 May 2016 07:46:53 +0300 Cc: ath10k , "codel@lists.bufferbloat.net" , make-wifi-fast@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: References: To: Dave Taht X-Mailer: Apple Mail (2.3124) Subject: Re: [Make-wifi-fast] fq_codel_drop vs a udp flood X-BeenThere: make-wifi-fast@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 01 May 2016 04:47:19 -0000 > On 1 May, 2016, at 06:41, Dave Taht wrote: >=20 > fq_codel_drop looks through 1024 queues in the mainline version and > 4096 in this. [4] That's *expensive*. Cake originally inherited this behaviour. Some time ago, I changed it to search only the queues in the active = lists. In a simple case like this, that means it only has to consider = 1-2 queues each time, which is a huge improvement and sufficient for any = normal traffic situation. The theoretical worst-case performance (eg. under a DDoS) remains poor. = To fix that, I think we would need to maintain a max-heap of queue = lengths (which is a generalisation of the =E2=80=9Ckeep 3 longest = queues=E2=80=9D idea). On the upside, this heap would only need to be = maintained when drops actually occur, and would remain fast in simple = cases where only one or two queues are disproportionately long. It=E2=80=99s just as easy to head-drop as tail-drop, once you decide to = be queue-fair (which *is* desirable to make DoS attacks harder). It is = the queue-fairness which is CPU intensive (and can be optimised, see = above). Head-drop is theoretically superior, since it gets the = congestion signal to the receiver faster. An unresponsive flow won=E2=80=99= t care either way, but a responsive one will. - Jonathan Morton