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

[Tony Przygienda <[e-mail]>]

> 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