Re: [babel] babel Digest, Vol 17, Issue 5
Tony Przygienda <tonysietf@gmail.com> Fri, 06 January 2017 06:43 UTC
Return-Path: <tonysietf@gmail.com>
X-Original-To: babel@ietfa.amsl.com
Delivered-To: babel@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E7E13129AA3 for <babel@ietfa.amsl.com>; Thu, 5 Jan 2017 22:43:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OX5qbIjIY1V7 for <babel@ietfa.amsl.com>; Thu, 5 Jan 2017 22:42:58 -0800 (PST)
Received: from mail-wm0-x22c.google.com (mail-wm0-x22c.google.com [IPv6:2a00:1450:400c:c09::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 6114E1296B0 for <babel@ietf.org>; Thu, 5 Jan 2017 22:42:58 -0800 (PST)
Received: by mail-wm0-x22c.google.com with SMTP id k184so16235884wme.1 for <babel@ietf.org>; Thu, 05 Jan 2017 22:42:58 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=F/1l945z44rvvnVMUmggdWFh0b0ft1A9usqVraoDNy4=; b=CVVO8lVsID5b45Fr7E+wh7dYulzdII998iHsebsqB4+nZDtPbWfE8WJWxncFwpTaJt y22dv/pdKy9Z5TS78k46oG+V9VQbYpJgGvN2FcvdxAgC2xsk0t3EaRfEDwoBC7aSsQ/t +CVQGPW9oPy/vkwDLJCt8V0tN/t0Jkc6mvIadiGTWTFGT2OJ6P9BYl7CAmjTcoi/lUKM /l8ACckov7JKBF1nrbdnSJASCeqMXoBZG6ASDydATIdgsYr8MQ6AhZFdKCoQhdKAPqgH xFexZK6dUlmHzS0jKQw/p9SrdCsoc8MJpiHY/WTSQIIJXsPEnq2vVno3cEK4zhc2O3/l gNKw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=F/1l945z44rvvnVMUmggdWFh0b0ft1A9usqVraoDNy4=; b=Q6TGOpC+PN1ex/qkxHuf52X78CxH1TBNCxcKGGDlh/UweousKsJW7QnQEvkzATepeG dHK/cZkGOR0zFT9+IVpkEY67nxUnql0FD0QeYIQSPuc9HsOksxLUdlwfL4haCJgFbj9Y nk+Cz+oX6FHLlQnElDnAf0dPMiK918QTKqEoXyeSD5cFlqSqo0Pah8ffFvhpOXBMJZIA fQmYsJzp8CFqf/9lin8wDSAUrFUr8wReralOeR0nb5q3puW2gEq+kbZgTiR6RABkz3Kj iNUDetFccryJfy76cCEDbmNisa8k3WYlg1guuAyeBrAWTS+X4gPoxmdemJYCdk5vkH2s Qq1A==
X-Gm-Message-State: AIkVDXIqPBWvJBRl4prvcVkPM3SRgaiIPrb6OhiZ5ugMC1w01c23bO2PfXzdhb6JYKSU6aJCJtrZyvnkTSN+2A==
X-Received: by 10.28.26.197 with SMTP id a188mr1806265wma.93.1483684976420; Thu, 05 Jan 2017 22:42:56 -0800 (PST)
MIME-Version: 1.0
Received: by 10.80.149.150 with HTTP; Thu, 5 Jan 2017 22:42:15 -0800 (PST)
In-Reply-To: <mailman.1581.1483630892.3886.babel@ietf.org>
References: <mailman.1581.1483630892.3886.babel@ietf.org>
From: Tony Przygienda <tonysietf@gmail.com>
Date: Thu, 05 Jan 2017 22:42:15 -0800
Message-ID: <CA+wi2hM0AeR684ouWv3Rc8kHnCOEdtDVVLjQT3V4+jQCDHwNZg@mail.gmail.com>
To: Babel at IETF <babel@ietf.org>
Content-Type: multipart/alternative; boundary="001a114ccbbafa6d8005456753a9"
Archived-At: <https://mailarchive.ietf.org/arch/msg/babel/EO982zlAD76qbHBO8to2tuHTivY>
Subject: Re: [babel] babel Digest, Vol 17, Issue 5
X-BeenThere: babel@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: "A list for discussion of the Babel Routing Protocol." <babel.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/babel>, <mailto:babel-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/babel/>
List-Post: <mailto:babel@ietf.org>
List-Help: <mailto:babel-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/babel>, <mailto:babel-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 06 Jan 2017 06:43:01 -0000
> 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
- Re: [babel] babel Digest, Vol 17, Issue 5 Tony Przygienda
- Re: [babel] babel Digest, Vol 17, Issue 5 Tony Przygienda
- Re: [babel] babel Digest, Vol 17, Issue 5 Juliusz Chroboczek
- Re: [babel] babel Digest, Vol 17, Issue 5 Juliusz Chroboczek