Re: [Cake] triple flow isolation

[Jonathan Morton <chromatix99@gmail.com>]

I’ve 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 <moeller0@gmx.de> wrote:
> 
>>> I do not claim I understand what triple-iso intends to accomplish in detail.
>> 
>> The short version is that, in theory at least, I’ve found a way to ensure fairness without needing to know which side of the interface is which.  
> 
> Could you please explain the fairness you are talking about here?

As you’re 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’s 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’ll 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’ll see if I can think of a way to adapt the algorithm to do that.

 - Jonathan Morton