From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ob0-x234.google.com (mail-ob0-x234.google.com [IPv6:2607:f8b0:4003:c01::234]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id E051C21F283 for ; Mon, 13 Apr 2015 08:50:07 -0700 (PDT) Received: by oblw8 with SMTP id w8so40596128obl.0 for ; Mon, 13 Apr 2015 08:50:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=ee88xXptEhjBKdoHysFHU/ZU+nxq4BxQz5lVEN/InnU=; b=x+XtmfSpLMJ63qBTEpBBKRC9219hmYLG5vL7IxAePxQeDjHrSklAeQdxiOGpRgeFMy b/DUYq7ap9qssg8HkvzjIjFprvey6LlH4JLjgUlArpZy0rDS3+N+CrUBJVi/3YCw+8l1 quokoyTa6qNnWForaKKdcG+OzGty5uCx1Ab8BkOLnmexKSNYdaJ0wD9/aHrXsCZ4IpBn rBk9KIt/H+Ay9ni5R6pX+CQgo2R3EF1U5zAJLwsaRPXUWLyeOuKioWi63Ir9DcGidvpe 6JmM6kEbPy9HW1VjgEyf+AOVZxPsbNPrCwGo76Gl8c0PVUpF5NOoqauvIhpJJyTL8Teh xsUw== MIME-Version: 1.0 X-Received: by 10.202.71.84 with SMTP id u81mr7850485oia.81.1428940206899; Mon, 13 Apr 2015 08:50:06 -0700 (PDT) Received: by 10.202.51.66 with HTTP; Mon, 13 Apr 2015 08:50:06 -0700 (PDT) In-Reply-To: <548E5D50-943F-46F2-BF7C-BB25E704B1D6@gmail.com> References: <548E5D50-943F-46F2-BF7C-BB25E704B1D6@gmail.com> Date: Mon, 13 Apr 2015 08:50:06 -0700 Message-ID: From: Dave Taht To: Jonathan Morton Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Cc: cake@lists.bufferbloat.net Subject: Re: [Cake] tail drop on complete overload X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 13 Apr 2015 15:50:36 -0000 On Sun, Apr 12, 2015 at 4:42 PM, Jonathan Morton wr= ote: > >> On 13 Apr, 2015, at 01:16, Dave Taht wrote: >> >> The full flow space search on complete overload is terribly expensive, >> moreover it is not deterministic, and touches a lot of cache. > > I would be interested to see if anyone can actually trigger this in pract= ice. It=E2=80=99s a slow-path function, which I assume would be rarely cal= led - only when the queue is physically full. By then, the overload mechan= isms would already be in operation, dropping packets instead of marking the= m. So it=E2=80=99s probably quite a lot easier to trigger it using a local= sender than an external one - and if you *can* trigger it externally, then= you=E2=80=99ve probably got enough CPU headroom to deal with it the right = way. A ping flood will trigger it trivially but briefly. A more sophisticated attack would send udp on many different ports. > Also, I don=E2=80=99t think it=E2=80=99s quite as expensive as you think.= Note that instead of iterating over the lists of flows, it iterates over = the array of flow *backlog* counters in each class. In the default configu= ration, that=E2=80=99s four 4KB arrays, accessed in ascending linear order = (which on most practical memory architectures is the optimal pattern). Thi= s is simply to pinpoint the longest queue, which I believe is desirable beh= aviour. I note that most L1 dcaches are 32k-64k in size. Wiping out the dcache is not a good idea. > I don=E2=80=99t see how it can be non-deterministic. Cache misses make it non-deterministic. > The actual drop is as efficient as it can be. Tail-drop would be *more* = efficient, sure, since it just involves an early error return in enqueue(),= but has its own behavioural risks. I agree that it carries it's own behavioral risks and those should be exami= ned. > It may be feasible - and in hardware would probably be easy - to keep tra= ck of the identity of the longest queue opportunistically. This would redu= ce the cost of identifying that queue when it is necessary to do so, at the= cost of a little extra overhead on processing every packet. Is that worth= it? Might be a good idea to try to keep the biggest queue ptr around, yes. Would you like to sit through a typical cloudflare presentation on the kinds of DDOSes they see? The one I went through was right after my talk at nznog. > > - Jonathan Morton > --=20 Dave T=C3=A4ht Open Networking needs **Open Source Hardware** https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67