[babel] Fwd: Re: [Babel-users] Sroamd: Protocol Documentation?

Juliusz Chroboczek <jch@irif.fr> Mon, 26 July 2021 22:54 UTC

Return-Path: <jch@irif.fr>
X-Original-To: babel@ietfa.amsl.com
Delivered-To: babel@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id B55753A085F for <babel@ietfa.amsl.com>; Mon, 26 Jul 2021 15:54:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 1jH_IrFKO4sc for <babel@ietfa.amsl.com>; Mon, 26 Jul 2021 15:54:26 -0700 (PDT)
Received: from korolev.univ-paris7.fr (korolev.univ-paris7.fr [IPv6:2001:660:3301:8000::1:2]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5AFC13A0856 for <babel@ietf.org>; Mon, 26 Jul 2021 15:54:25 -0700 (PDT)
Received: from mailhub.math.univ-paris-diderot.fr (mailhub.math.univ-paris-diderot.fr []) by korolev.univ-paris7.fr (8.14.4/8.14.4/relay1/82085) with ESMTP id 16QMsMN3000976 for <babel@ietf.org>; Tue, 27 Jul 2021 00:54:22 +0200
Received: from mailhub.math.univ-paris-diderot.fr (localhost []) by mailhub.math.univ-paris-diderot.fr (Postfix) with ESMTP id B7EDCC92B7 for <babel@ietf.org>; Tue, 27 Jul 2021 00:54:22 +0200 (CEST)
X-Virus-Scanned: amavisd-new at math.univ-paris-diderot.fr
Received: from mailhub.math.univ-paris-diderot.fr ([]) by mailhub.math.univ-paris-diderot.fr (mailhub.math.univ-paris-diderot.fr []) (amavisd-new, port 10023) with ESMTP id 2WLk8eQPKxZg for <babel@ietf.org>; Tue, 27 Jul 2021 00:54:20 +0200 (CEST)
Received: from pirx.irif.fr (unknown []) (Authenticated sender: jch) by mailhub.math.univ-paris-diderot.fr (Postfix) with ESMTPSA id B67B4C92B5 for <babel@ietf.org>; Tue, 27 Jul 2021 00:54:20 +0200 (CEST)
Date: Tue, 27 Jul 2021 00:54:20 +0200
Message-ID: <87o8aoadpf.wl-jch@irif.fr>
From: Juliusz Chroboczek <jch@irif.fr>
To: babel@ietf.org
References: <40976de9-6b97-34f1-1f5a-6d48d519d0f8@systemli.org> <d4fe9a52-4873-612d-f1e7-7f04020d51d3@systemli.org> <877dhjusqk.wl-jch@irif.fr>
User-Agent: Wanderlust/2.15.9 (Almost Unreal) Emacs/27.1 Mule/6.0
MIME-Version: 1.0 (generated by SEMI-EPG 1.14.7 - "Harue")
Content-Type: multipart/mixed; boundary="Multipart_Tue_Jul_27_00:54:19_2021-1"
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.2.7 (korolev.univ-paris7.fr []); Tue, 27 Jul 2021 00:54:22 +0200 (CEST)
X-Miltered: at korolev with ID 60FF3D1E.000 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)!
X-j-chkmail-Enveloppe: 60FF3D1E.000 from mailhub.math.univ-paris-diderot.fr/mailhub.math.univ-paris-diderot.fr/null/mailhub.math.univ-paris-diderot.fr/<jch@irif.fr>
X-j-chkmail-Score: MSGID : 60FF3D1E.000 on korolev.univ-paris7.fr : j-chkmail score : . : R=. U=. O=. B=0.000 -> S=0.000
X-j-chkmail-Status: Ham
Archived-At: <https://mailarchive.ietf.org/arch/msg/babel/Ygs0P0mXMIWa_n4HR0vckBk_W0o>
Subject: [babel] Fwd: Re: [Babel-users] Sroamd: Protocol Documentation?
X-BeenThere: babel@ietf.org
X-Mailman-Version: 2.1.29
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: Mon, 26 Jul 2021 22:54:33 -0000

Related to Donald's talk, this is the mail describing sroamd that
I recently sent to the babel-users mailing list.  You can get the code by

    git clone https://www.irif.fr/~jch/software/sroamd.git

--- Begin Message ---
> Okay, I found this design description that is very helpful. :)
> https://www.mail-archive.com/babel-users@alioth-lists.debian.net/msg00662.html

Some more details.  Sroamd consists of five pieces:

1. a distributed (replicated) database (flood.c);
2. a table that maps IP addresses to MAC addresses;
3. a table that maps MAC addresses to associated routers;
4. a way to get packets from the network to the right router
5. a way to get packets from the mobile to the right router

1. A distributed database

This is implemented in flood.c.  The database is not reliable (that would
be impossible to do in a distributed manner without a global clock), but
it reliably detects conflicts: if the network gets partitioned, then after
the network is merged again, nodes will realise that there is a conflict,
which the client code will then need to resolve.

Note that using a distributed database is a deliberate choice: the code
could easily be replaced with an ordinary central database node, for
example a RADIUS or DIAMETER server.

2. A table IP -> MAC

This is implemented in lease.c, dhcpv4.c and ra.c.  Sroamd listens to
DHCPv4 and RD requests, and maintains a map

  IPv4 address    -> MAC
  IPv6 /64 prefix -> MAC

For IPv4, we just implement a basic DHCPv4 server (dhcpv4.c).  For IPv6,
we allocate a different /64 to each mobile node by sending a RA over
unicast; it's wasteful, but it's the only way to get IPv6 to work with
Android.  (We could in principle implement stateful DHCPv6, but since it
doesn't work with Android, it seems somewhat pointless to me; let me know
if you disagree.)

There can be only one MAC for an IPv4, but there can be multiple IPv4 for
a single MAC, for example if the network gets partitioned and the node
gets different IPv4 addresses from different routers.

We try to avoid conflicts by flooding a 10s lease before we assign
a permanent one, so that conflicts will typically last just 10s.  There is
a theoretical conflict if the network gets partitioned, in which case we
retract the IPv6 address.  We don't do anything clever with IPv4 yet, in
this unlikely case the user will need to restart their DHCPv4 client (by
disabling and reenabling WiFi, in the case of Android).

3. A table MAC -> associated router

This is implemented in netlink.c and client.c.

We listen no netlink messages, and whenever we notice that a node has
associated to us, we flood a new entry in the distributed database.
Again, conflicts are unavoidable (if a node moves A->B->C in quick
succession, the flooding algorithm might flood C before B, so some nodes
think the node is at B and some at C).  When we detect a conflict, we ping
the node from both routers -- unless the node is associated to both, only
one of the pings should yield a positive result.

4. a way to get packets from the network to the right router

This is implemented in client.c.

This one is easy: the router that believes that the node is associated to
it announces a Babel route to the mobile node.  There might be multiple
routes temporarily after a node has moved, but all but one will disappear
as soon as the conflict detection has converged (see point 3 above).

5. a way to get packets from the mobile node to the right router

This is the tricky bit.  The solution to assign the same IP address to all
edge routers.  When a node associates to a router, the router sends
a gratuitious ARP/ND to the mobile node, which causes its neighbour cache
to be reset to the MAC address of the router.

-- Juliusz

Babel-users mailing list
--- End Message ---