From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-la0-x230.google.com (mail-la0-x230.google.com [IPv6:2a00:1450:4010:c03::230]) (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 6B39F21F228 for ; Sun, 12 Apr 2015 16:43:03 -0700 (PDT) Received: by lagv1 with SMTP id v1so45651496lag.3 for ; Sun, 12 Apr 2015 16:43:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=/0SjDtul82xGPGWMAdXEt24FR7Hxvcki0p71HF1e1dA=; b=B99O7gbj6bE/HQAyug045BU1DXARfQLM/cuR4V64lf0eIlXi2JLgFE2X1DsIbLt/3R xPPSzzZWSkOX3LhhAZPm1bwoJZ+Y84y2pyTuhangWfOaZGH+YQ6Y0tMPv6VvkIoh4aKB qVtHf0dLuG7lB+ZKULcS/aVeoVdaOmCErgiTgFzGMmWAZP4KP7nwgCdG+HgNP/0Ef3MF oQpVwmYYx4fIEr+kWpsAaVA5b0Q2335oNRZ+RGrrwnyxy5QLYKrnkl+2dWXY8BXE9PE8 npXS814YGoyK6g8JzRc31aGoJkxak4NXkjXKfnem1EbBWyDfn0MEEJHhO6x7Qvx4F+EG Ya3w== X-Received: by 10.112.130.129 with SMTP id oe1mr4451292lbb.37.1428882180885; Sun, 12 Apr 2015 16:43:00 -0700 (PDT) Received: from bass.home.chromatix.fi (87-93-27-145.bb.dnainternet.fi. [87.93.27.145]) by mx.google.com with ESMTPSA id 7sm1275326lax.44.2015.04.12.16.42.57 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 12 Apr 2015 16:43:00 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2098\)) From: Jonathan Morton In-Reply-To: Date: Mon, 13 Apr 2015 02:42:52 +0300 Content-Transfer-Encoding: quoted-printable Message-Id: <548E5D50-943F-46F2-BF7C-BB25E704B1D6@gmail.com> References: To: Dave Taht X-Mailer: Apple Mail (2.2098) 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: Sun, 12 Apr 2015 23:43:31 -0000 > On 13 Apr, 2015, at 01:16, Dave Taht wrote: >=20 > 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 = practice. It=E2=80=99s a slow-path function, which I assume would be = rarely called - only when the queue is physically full. By then, the = overload mechanisms would already be in operation, dropping packets = instead of marking them. 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. 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 configuration, that=E2=80=99s four 4KB arrays, accessed in = ascending linear order (which on most practical memory architectures is = the optimal pattern). This is simply to pinpoint the longest queue, = which I believe is desirable behaviour. I don=E2=80=99t see how it can be 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. It may be feasible - and in hardware would probably be easy - to keep = track of the identity of the longest queue opportunistically. This = would reduce 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? - Jonathan Morton