From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-x22b.google.com (mail-lb0-x22b.google.com [IPv6:2a00:1450:4010:c04::22b]) by lists.bufferbloat.net (Postfix) with ESMTPS id B07453B2A2 for ; Sat, 16 Jan 2016 04:05:38 -0500 (EST) Received: by mail-lb0-x22b.google.com with SMTP id oh2so326674452lbb.3 for ; Sat, 16 Jan 2016 01:05:38 -0800 (PST) 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=aF2AlMGnesM+4H+3hSvT5u1kFU//EgjL097c66RO0zI=; b=opVFWhROz1A9FWVHLuLRySxgTB61GMI7AlgkCvpbKIhJdx94BdhO/5DaS4KPJ9mo8d eK07Z0zr/5Aein7L56dOG0bnv0qKSSXKsOH/2ScbYkPHpNDkn5sq290ppT+5mECSYHlr /jESMhVm6zPDThozoyuME8a54o/Rhd7Wa1p34i+xkSZxCA7Q3KTgn9LUDldznS4i1IJ8 nwA8RuDLuAu4P1eRk7gIfaNitWp7isva94JWqiVIRciCyLTbtpwrj08fmy9IiVCXMoj2 bJLnOwj6oxXm78EAo0r6FNCzrZXWduZ87nWbnY+1YB9+iQYrtjuY88ZK8e7uiIbnzfU1 Wtmg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=aF2AlMGnesM+4H+3hSvT5u1kFU//EgjL097c66RO0zI=; b=A0y9V2F6mKiDMWQiWrqw7sU6MQKtpIBkH55AfY7v7D2YejxoXLxuYES4XKfqY1I/e8 Pz1l2L1x/sm2cqX1KFjcbYCOCht74BaT/HUb/O5ON9rK31dkCvDWPmcr/YUddAI/uuOV GrnjRtUPr+Td1FQHi6gJBshuUbRxFOG0UpnypqM9HWClBsQL/DK+VohjLEtiCC+xogXS 00iPqV00gZ6hs15MFW5wDxlJCNkW0fD50/djqb8R1JXRL3g5iRz7Z2NwDDEzjp2YWXbC g0ZT2rYwKQhPuVGH7W9+VoH7ps6ZimXxcDMzUxegOyNRuAX87Qp0qYpsELv/NrOBGfmG pdAQ== X-Gm-Message-State: ALoCoQm2KXZvLAEna8QCUS+DuQwROzbqn5LsNAmdNqieuB8ItHDy3u1/10Hi8zq1Q2qedBkJLOdSz1nCefh2RyMsuYkJIU8Mhw== X-Received: by 10.112.198.72 with SMTP id ja8mr4805675lbc.142.1452935135914; Sat, 16 Jan 2016 01:05:35 -0800 (PST) Received: from [192.168.238.201] (37-33-99-74.bb.dnainternet.fi. [37.33.99.74]) by smtp.gmail.com with ESMTPSA id xo4sm1797819lbb.27.2016.01.16.01.05.34 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sat, 16 Jan 2016 01:05:35 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) From: Jonathan Morton In-Reply-To: Date: Sat, 16 Jan 2016 11:05:30 +0200 Cc: cake@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: 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: moeller0 X-Mailer: Apple Mail (2.3112) 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: Sat, 16 Jan 2016 09:05:39 -0000 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. > 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? 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. Triple isolation also keeps such counters on a per-source-host and = per-destination-host basis (NB: *not* on a per-host-pair basis). 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.) 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. It=E2=80=99s also easy to see that fairness between disjoint host-pairs = is also maintained in the same manner. 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. 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. 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. - Jonathan Morton