From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-la0-x22c.google.com (mail-la0-x22c.google.com [IPv6:2a00:1450:4010:c03::22c]) (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 E8222201B88 for ; Thu, 7 May 2015 22:12:31 -0700 (PDT) Received: by lagv1 with SMTP id v1so45265751lag.3 for ; Thu, 07 May 2015 22:12:29 -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=JbAaE6WmmMRlMIIlPbsINMFs6XxC87HaWP8hfN5tXtA=; b=Pv9TL0StIyknGxKUG1W/l78UKgF4ZVh6TYEf3ijwc6xiuBFWMwC0lUfoFsSF0d8fRe AvQKaXUsCEwG1+m8xsOCUmJzqng6ZSb5tJ10WngikyHZKQ3t3u2Al3wL4bpPhHfEINBd gdPVbuN4rullbThzOvnwWRg5AqgjhAJcB4GkfNW/Fq5jrhcwRJkD8Okd0CuTVxHDMbTK wz40xQbeSGWMUS5At/69Zy1yczPhqwT1lo+axKDNCVaYEfvi5N6XGwuzuvjy8M84E06s pxeT+GVF2CTkSjo0tLRaffQm4S1An4yH+Rx9iINdIqPLN+LzokktFX+CcwisFDKa7qoU SbcQ== X-Received: by 10.152.23.38 with SMTP id j6mr1444516laf.47.1431061949063; Thu, 07 May 2015 22:12:29 -0700 (PDT) Received: from bass.home.chromatix.fi (188-67-131-101.bb.dnainternet.fi. [188.67.131.101]) by mx.google.com with ESMTPSA id r4sm899698lae.13.2015.05.07.22.12.25 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 07 May 2015 22:12:28 -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: Fri, 8 May 2015 08:12:18 +0300 Content-Transfer-Encoding: quoted-printable Message-Id: References: To: Dave Taht X-Mailer: Apple Mail (2.2098) Cc: cake@lists.bufferbloat.net Subject: Re: [Cake] packet mass, ecn, and a fractional count 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: Fri, 08 May 2015 05:13:00 -0000 > On 8 May, 2015, at 05:32, Dave Taht wrote: >=20 > from observing behaviors with large numbers of flows, fq_codel derived > algorithms start to struggle to achieve the desired delay, cake > seemingly less so, and perhaps this is related to collisions also. >=20 > A thought would be to use a fractional (fixed point) increment to > count rather than "1" when larger numbers of flows are present. Given that cake handles this extreme case better than average already, = I=E2=80=99m not particularly concerned about trying to improve it = further. Adding set-associative hashing (or red-black trees for perfect = isolation, if you prefer) to other FQ qdiscs might be a better idea than = fudging codel. There=E2=80=99s a reasonably straightforward answer for why flow = collisions might cause worse AQM behaviour. Assume a situation with a = very large number of flows, so adding one more flow doesn=E2=80=99t = change the throughput of existing flows much. Now assume that most = queues have just one flow assigned, but there are a few with two each. = (Ignore the possibility of more, for simplicity.) The flows assigned to the doubled queues will have half the throughput = each, compared to those in single queues. This also means that only = half the packets are available for sending congestion signals on, and = since codel marks packets on a fixed schedule once it is triggered, each = flow will therefore receive only half the congestion signals. *BUT* = each flow still gets the same IW, so a doubled queue is twice as full as = singles to begin with. So with perfect flow isolation (and a separate codel per queue), = codel=E2=80=99s signalling rate naturally scales with the number of = flows. With collisions, that doesn=E2=80=99t happen so reliably; it is = at best a sublinear scaling. Without FQ at all, representing the = pessimal collisions case, codel has to wait for its signalling rate to = grow over time in order to match the number of flows, so it won=E2=80=99t = react as quickly to an abruptly imposed load. - Jonathan Morton