Subject: Re: [babel] babel Digest, Vol 17, Issue 5

From: Tony Przygienda <[email-masked]>
Date: Thu, 5 Jan 2017 22:42:15 -0800

> Hi Tony, good to hear from you.
>

Hey Prof. J. ;-)  I'm loosely following Babel for my personal interest ...

>
> > FSM cannot "overspecify" a protocol unless you are perfectly happy with
> > "undefined" behavior on certain transitions.
>
> Yes, Babel is tolerant of undefined behaviour in many cases.  Please bear
> with me while I lecture a little.
>
> Traditional link-state protocols are based on an algorithm that is
> extremely
> refined: their correctness crucially depends on three non-trivial
> properties:
>
>  1. the LSDBs are synchronised at all times;
>  2. Dijkstra converges;
>  3. the concatenation of each node's truncated tree yields a forest.
>
> These properties are not built into the algorithm, they must be guaranteed
> by the protocol.  (1) is why OSPF and IS-IS use a reliable transport and
> split large routing domains into areas; (2) and (3) are why link-state
> protocols are restricted to integer metrics and lowest-metric route
> selection without filtering (within areas).
>

all correct (except 3., more can be done but that's not the discussion
here). You don't give link-state enough kuddos for convergence speed but
that's not the topic either.

>
> ...
>
> Because the algorithm is so robust, there are fewer requirements on the
> protocol.  For example, property 2.a above can be satisfied by acquiring
> a neighbour as soon as we receive a packet, as soon as we receive a Hello,
> as soon as we receive an IHU, or at any other time as soon as this happens
> often enough.
>
> (Aside: note that filtering is a structured way of violating property 2b.
> That's fine, Babel remains safe in the presence of filtering, although it
> is no longer complete.)
>
> (Aside: as we've discussed before, Tony, property 1.a does not assume
> a global clock -- it merely says that the happens-before relation is
> well-founded.)
>

yepp ... we had those discussions. We're in sync, you gave me an
interesting info with all the one-side-distributive metric thinking in the
process.

>
> > Descriptive language is nothing but ad-hoc extended FSM description
> along the
> > lines "if THAT happens, do THIS" ..
>
> There are a few places in Babel where the protocol says "it doesn't matter
> when you do this, as long as it eventually happens".  I don't know how to
> express that in an FSM, even a non-deterministic one.
>

hmm, I am not a big friend of "eventual consistencies" since I don't like
my customers to "eventually" pay the bills. We do and must live with
epsilon which is what e.g. OSPF is doing and Babel does as well (given they
are simply async distributed algorithms without enough info to provide
concurrent consistency which wouldn't serve much of a purpose albeit one
could argue that all the FRR work is nothing else but a cut-consistency
guarantee while the algorithms themselves are only epsilon consistent @ a
scale which was fine originally [seconds] but is not anymore for lots
deploymens [<50msecs]. Anything else, as we spoke, would necessitate a
global [synchronous] clock or at least clock matrices which are practically
too slow for dynamic routing protocols by the gut-feeling I have from
database work). So what you describe is nothing different than eventual or
in-fact attempted epsilon (timer-based-retransmission) and that can be well
expressed with FSMs. As footnote: strictly said, even OSPF is only
"eventually consistent" and that only within a certain loss probability
envelope so it's nothing new. As any dynamic system, one has to pick either
positive stability @ the cost of slower adaptation or negative stability
like OSPF that gives you faster adaptation to changes but carries a price
in complexity and smaller operating envelope. I digress ;-)

>
> > In OSPF, it was largely a question of "style" given John is
> > a mathematician by trade
>
> The notion of "often enough" is well established in Maths, although it's
> usually called "infinitely often".  Of course, since Babel uses expiry
> timers, "often enough" really means "before the timer expires and flushes
> your incomplete state".
>

Yeah, in summary though I don't think Babel is anything new much really in
terms of distributed algo nature and FSMs would do a fine job on Babel as
well. But  if the descriptive is good enough to provide interoperable
implementations, it's a matter of style largely (acknowledging the fact
again that Babel is significantly simpler as algorithm and somewhat more
positively stable than link-states).

To come back to the the original point I was arguing a FSM will never
"overspecify" a protocol since ultimately we're building DFAs here unless
you want to argue that Babel is NFA (i.e. a transition can end up in two
possible states and even then you can write FSMs for it, either as NFA or
epsilon-NFA). We don't parse regexes which is probably only application of
NFAs I know (and even those can be regularized into class-equivalent DFA if
I remember correctly) so the discussion whether choosing whether you
recognize neighbor on receiving a packet or not are two possible
transitions until yoou "eventually" recognize the neighbor is somewhat
interesting. One could argue that OSPF can do that as well (since ignoring
a packet is indistinguishable from loss until you ignore them often enough
you never converge) but I don't think I would consider that as argument
that OSPF is best written using NFAs? And to completely split the hair here
four ways, the proof exists that NFA and class equivalent to DFA so head I
win and tails you loose ;-)

my sum_n=0^\inf 1/n! cents ;-)

--- tony

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 06 Jan 2017 18:37:37 +0100

> You don't give link-state enough kuddos for convergence speed

Ok, here we go.

With a link state algorithm, given enough CPU, convergence speed is almost
entirely predicated on the speed of LSDB synchronisation.  This gives
link-state protocols a fundamental advantage as far as convergence speed
is concerned, at the cost of greater complexity and lesser robustness than
well-designed distance-vector protocols.

-- Juliusz

---

From: Tony Przygienda <[email-masked]>
Date: Fri, 6 Jan 2017 09:50:05 -0800

See, just needed some prodding ;-)

I agree with everything except maybe the complexity, a fully fledged BGP
these days is 10x a fully fledged IGP. But then again, it's apples and
kiwis, IGPs do not attempt to do EVPN or even multicast ;-)  so if we're
talking the "smallest viable routing solution", yes, IGP has a higher price
of admission ;-)

--- tony

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 07 Jan 2017 00:22:40 +0100

I've now had some time to spend on the rest of your mail.

> hmm, I am not a big friend of "eventual consistencies" since I don't like my
> customers to "eventually" pay the bills. We do and must live with epsilon
> which is what e.g. OSPF is doing and Babel does as well

I'm not familiar with the "epsilon" terminology, but if I understand
correctly what you mean -- OSPF encapsulates the probabilistic aspect
within the reliable flooding algorithm.  Assuming that flooding
terminates, OSPF is correct.  Of course, no bound can be given on the
termination of flooding, but at least the probabilistic nature of the
protocol is cleanly encapsulated within the flooding algorithm.  All the
remainder of the protocol is completely deterministic.

This is very different from Babel, which does not rely on a reliable
transport, and therefore carries probabilities throughout the protocol.
Hence the strong invariant (loop-freedom), which has the side benefit of
allowing a somewhat more lax style of specification.

> terms of distributed algo nature

I agree, most of the good ideas in Babel were stolen from other protocols
(RIP, DSDV, EIGRP, BGP).

> and FSMs would do a fine job on Babel as well.

I don't know how to do that.  I don't know how to express in an FSM the
notion that "When to acquire a neighbour is an implementation detail, as
long as a neighbour is acquired soon enough.  A simple strategy is to
create a neighbour table entry as soon as we receive a well-formed Babel
packet from a given IP, but other strategies are possible".

> (acknowledging the fact again that Babel is significantly simpler as
> algorithm and somewhat more positively stable than link-states).

Quoting for my personal enjoyment :-)

> And to completely split the hair here four ways, the proof exists that NFA and
> class equivalent to DFA so head I win and tails you loose ;-) 

I don't think the theorem applies here.  The equivalence only states that
the class of recognised languages is the same, nothing more.

-- Juliusz