From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mout.gmx.net (mout.gmx.net [212.227.17.22]) by lists.bufferbloat.net (Postfix) with ESMTPS id B8DA53B2A3 for ; Mon, 18 Jan 2016 04:21:16 -0500 (EST) Received: from [10.9.3.149] ([192.54.209.59]) by mail.gmx.com (mrgmx101) with ESMTPSA (Nemesis) id 0MbKXI-1abewg2Bbo-00Imwt; Mon, 18 Jan 2016 10:21:14 +0100 Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\)) From: moeller0 In-Reply-To: Date: Mon, 18 Jan 2016 10:21:18 +0100 Cc: cake@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: <079A86FB-D2A6-4787-BC42-D2E200AD3290@gmx.de> References: <5693E8FA.4000803@darbyshire-bryant.me.uk> <56941191.1010601@darbyshire-bryant.me.uk> <452D0F47-931B-4412-AC59-C308388AA1E4@gmail.com> <02A10F37-145C-4BF9-B428-BC1BDF700135@gmx.de> To: Jonathan Morton X-Mailer: Apple Mail (2.2104) X-Provags-ID: V03:K0:6z0gGR5tk5X6kSwlNcGmCX+jYOpr8RQ3KeBKGspUXoeUCzvsPnJ bNhggzk46pqrr16WXlKM3xeZylMSxlFCA2Svyz0xB/6Uhq0Ud3eH+tQ5tGGxvK0+hiaBuSJ L1UTLPrzk8G6/MC2DpKQL9fmB07dLEUrmYDjk/IPz7IALA4LssWjM+qA4m9qGsIaxb4A0dc /VUSOH/YzX+tvj1aViJRg== X-UI-Out-Filterresults: notjunk:1;V01:K0:dhfSM6bJCI8=:v8H08MLZFPuHox3yWeLBCj nyPjcmbLFEpMfQmL2yDgZjBCIaqB5y/jpDPfPe1TSIInvQX7B//nfIyJ2iNkhx5fZWCrAosOP 94X8IeMmem5RQOcX5Cs/hwbRj3D96Yj9xXIs7cK0JC8u/a9CzTwOUk4GMDb4g6B54JJ0tZSa3 K7s1gKlDqq3327CR2C9K9Fo8duNMGJwy1FGq4dFvWt6gBMy8Sb1YN0h1O98kVPsigz8ClI0r9 mOntDChnKpywJp9fstz450vj5V0Y83YnD/YQuxD80Dq3CLgCwKAmXXl9DwC0huBXlRyCqiTi/ pQ1NcnG9pYwIKRuw5w0pWXS3dbDVK9YyqtvqyxWIf0lRSKFA5eFsVSNj4GE8vm7x/Q1n45wfN fdWvJspGVEcGqmX91ES8qianUgfiocQkafSB1uNeto1v6d3mlbg7J+xsdXUARJBPuCfMNncG7 82wQjSkktGQprGbNq0WaDE/Bo+VrihnGFafYP5nIpNr8MKdWfqsdFD8K6Yxafl4/yDPicloIu 4DfD1bzOLGE/PZ61AaWOaf+bNjehQ5UlOnFwNHgcU7HQ5T5PzNylBIj7IPOOSjoiMm/nYdb6o 9qvCWtmhxz+vDJbK5qphd3Fnya990zO7a7817QigubvzwfHivKpG/zUEycmYvXnm2BLSwh48y kVlWTtOD/F9DpGKKS7l1DnKtOGlZ3AYX6EgRvotUjrdctmBbKBZyHZHZ2Q05OzogMneiF2qTL 45JWV3v5drhWsgXIEy18vnD3tfhoBSbP4ITpJdkjeH9WTkM+mRjejzqRgadvVlS8Gdbn5MMxe GhwBAWQ Subject: Re: [Cake] triple flow isolation X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 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, 18 Jan 2016 09:21:17 -0000 Hi Jonathan, > On Jan 16, 2016, at 10:05 , Jonathan Morton = wrote: >=20 > I=E2=80=99ve just committed and pushed the fixes required for = triple-isolation to actually work. They are small. My tests now pass. = This is a good feeling. >=20 >> On 15 Jan, 2016, at 10:05, moeller0 wrote: >>=20 >>>> I do not claim I understand what triple-iso intends to accomplish = in detail. >>>=20 >>> The short version is that, in theory at least, I=E2=80=99ve found a = way to ensure fairness without needing to know which side of the = interface is which. =20 >>=20 >> Could you please explain the fairness you are talking about here? First off thanks for taking the time to explain=E2=80=A6. >=20 > As you=E2=80=99re already aware. Cake uses DRR++ to ensure = flow-to-flow fairness. This chiefly means keeping a deficit counter per = flow, skipping over flows that are in deficit, and ensuring that the = counters get incremented at a mutually equal rate, so that they = eventually leave deficit. Okay, I am with you so far... >=20 > Triple isolation also keeps such counters on a per-source-host and = per-destination-host basis (NB: *not* on a per-host-pair basis). =20 Am I right to assume that dust and src host isolation works with = the same counters but simply ignores one of them? Or will only the = relevant counter be kept and updated? > The host deficits are checked first, and unless *both* of the relevant = hosts are out of deficit, the per-flow counters are not even examined. = However, the number of flows deferred due to host deficits is tracked, = which allows the host deficit counters to be batch-incremented at the = correct times. (This proved to be the main source of subtleties.) >=20 > Where two sets of flows have a common source or destination, but = separate hosts at the opposite end, this ensures fair bandwidth sharing = between the separate hosts, no matter which side of the link they happen = to lie or the relative numbers of flows involved. Within each such set, = per-flow fairness is also ensured. This is easy to understand and to = demonstrate. >=20 > It=E2=80=99s also easy to see that fairness between disjoint = host-pairs is also maintained in the same manner. >=20 > More complex situations require more thought to analyse. As you = suggest, the typical situation is where a small number of local hosts = talk to an arbitrary combination of remote hosts through the link. To = keep matters simple, I=E2=80=99ll assume there are two local hosts (A = and B) and that all flows are bulk in the same direction, and assert = that the principles generalise to larger numbers and more realistic = traffic patterns. >=20 > The simplest such case might be where A talks to a single remote host = (C), but B talks to two (D and E). This could be considered competition = between a single webserver and a sharded website. After stepping = through the algorithm with some mechanical aid, I think what will happen = in this case is that C-D-E fairness will govern the system, giving B = more bandwidth than A. In general, I think the side with the larger = number of hosts will tend to govern. Okay. >=20 > The opposite sense would be to have the side with the smaller number = of hosts govern the system. This would, I think, handle both the swarm = and shard cases better than the above, so I=E2=80=99ll see if I can = think of a way to adapt the algorithm to do that. So if all internal hosts talk to one external host, does this = scheme then equal pure per-flow fairness? I am trying to understand how = robust triple-iso is going to be against attempt at shenanigans by = unruly machines on the internal/external networks... Best Regards Sebastian >=20 > - Jonathan Morton >=20