Subject: [babel] Changing the route retraction

From: Gwendoline <[email-masked]>
Date: Sun, 25 Jun 2017 19:20:16 +0200 (CEST)

Dear all,

I'm implementing the extension for ToS that I designed for Babel. 
It is quite similar to the source-specific extension that Matthieu designed, 
but routes are indexed by (prefix, ToS). I came across the fact that when 
a route with a ToS t is retracted, then all packets with ToS t that should 
have followed this route are dropped for 110 seconds, according to section
3.5.5 in RFC 6126, even if there is a installed route without ToS.

This is satisfying enough for the source-specific extension, since when a 
source-specific route is retracted, we don't want to follow another one. However, 
in the case of a low-delay ToS for example, we'd like to switch right
then to a non ToS-specific route. 

I thought about a way to reduce this delay in most cases in the
non-tos-specific case. I think I found one:

When a Babel node retracts a route, it maintains the route unreachable
only until the first event between
(a) the node received an acknowledgement or the same
route retraction from each of its neighbours
(b) it's been more than 110 seconds (to avoid blocking indefinitely
because of weird neighbours).

This solution would reduce delays even with neighbours that don't
implement it.
It would be the first use of the acknowledgements defined in Babel.
A node should send an acknowledgement for a route retraction even if it
isn't feasible or installed.

We think it works in theory, but we don't know whether it will work in practice.
Could you please tell your thoughts on this?

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 26 Jun 2017 03:23:24 +0200

> We think it works in theory, but we don't know whether it will work in

The theoretical argument goes as follows.  Let nh_A(P) be A's next-hop for
prefix P.  Babel's loop-freedom argument relies on the following
invariant:

  if nh_A(P) = B then B has a selected route for prefix P.

Obviously, this invariant can fail just after B retracts a route for
prefix P and before the retraction has reached A, which is why RFC 6126
requires installing an unreachable route after receiving a retraction and
keeping it around for a couple of minutes (Section 3.5.5).

Gwendoline has noted that the invariant can be satisfied without
respecting a Hold Time by sending the retraction reliably; as soon as all
neighbours have sent the acknowledgement, node B as no longer the next-hop
for any neighbour, and hence the unreachable entry can be removed.

> because of weird neighbours).

I think we can add a case -- it is okay to remove the entry as soon as
each node has either sent the right acknowledgement or send a route
retraction for prefix P.

I think that we can put this as an optional algorithm in rfc6126bis.
It would be nice to have an implementation, though.

> implement it.  It would be the first use of the acknowledgements defined
> in Babel.  A node should send an acknowledgement for a route retraction
> even if it isn't feasible or installed.

Right on all counts.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Tue, 27 Jun 2017 11:54:32 -0700

Gwendoline, Juliusz,

Thanks for writing this up!
To me, this sounds like a good idea that improves the protocol
and as far as I can tell seems mathematically sound.

The only remaining question is: will it fit nicely into the spec?
Can you provide a PR against RFC6126bis?

(I do agree with Juliusz that we'll want an implementation as well)

Thanks,
David Schinazi

> On Jun 25, 2017, at 18:23, Juliusz Chroboczek <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 28 Jun 2017 01:27:11 +0200

> Can you provide a PR against RFC6126bis?

Yeah, we'll do that.  Unfortunately it's exam season right now, so I'm
suffering a mild case of work overload.

-- Juliusz