Subject: [babel] Restarting nodes and seqno requests

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 30 Apr 2018 13:22:10 +0200

I was debugging an issue with routes staying unreachable for a long time
after a node reboots; and decided I wasn't actually sure what the right
behaviour is, so I thought I'd ask.

So, the simple scenario is this:

- Babel nodes A and B have established a neighbour relationship, and node
  B announces prefix P with seqno S.

- Node B restarts (i.e. shuts down, loses its transient state such as
  seqnos and comes back up either immediately or after a relatively
  short time). It will then start announcing prefix P again, but now
  with seqno S' < S.

- Node A sees the new announcements from node B with a lower seqno.
  Since the hold time for P has not expired, these updates are
  unfeasible, so node A sends a seqno request.

- Node B updates its seqno to S'' = S' + 1 and resends the update.

- In many cases, S'' < S, so the update is still unfeasible from A's
  point of view.

The question is, how is this supposed to be resolved? Should A keep
resending the seqno requests each time it gets a new unfeasible update -
and if so, is there any limit to the frequency? Or should A immediately
consider the update with seqno S' as feasible because its selected route
has metric infinity?

I *think* the answer is the former (and that no rate limit is needed),
but I may be missing a reason why it is safe to accept the unfeasible
update during hold time... So what does everyone else think? :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 30 Apr 2018 13:56:07 +0200

>   with seqno S' < S [which is unfeasible for A].

Yes.  The loop avoidance mechanism in Babel is stateful (the source table
contains the state), and if you loose your state, you're in trouble.  That
is why babeld saves its seqno into persistent storage at shutdown and
restores it at startup.

If the seqno is lost (either because a node has crashed or because you
have no persistent storage), then you need to timeout the source table entry:

  - first, the route times out, so its metric becomes infinite;
  - you start sending retractions, and retractions don't update the source
    table;
  - at some point, the source table GC timer triggers, and the source
    entry gets updated.

Note that the total time you wait for the route to become feasible again
is the sum of the route hold time and the source GC time, so its on the
order of a few minutes -- Babel is optimised for the case where links go
up and down, but routers do not reboot often.  If that's not acceptable,
you can work around the issue by changing router ids at every boot, so
that the old and new state don't interact.  Babeld implements this with
the "random-id" option, and it is useful in environments where routers
reboot oftent without saving their seqno.

> The question is, how is this supposed to be resolved?

There's no good solution.  The loop avoidance mechanism is stateful, and
that's a fact of nature.  (BGP avoids the statefulness by putting the
whole state into each update, which causes updates to have an unbounded
size.)

If you have an idea for a good mechanism to avoid the issue, I'm listening.

> Should A keep resending the seqno requests each time it gets a new
> unfeasible update - and if so, is there any limit to the frequency?

Only the usual delay on sending out updates (Section 4, "a Babel node
SHOULD buffer every TLV and delay sending a packet by a small, randomly
chosen delay").  Is that a problem in practice?

> Or should A immediately consider the update with seqno S' as feasible
> because its selected route has metric infinity?

As you mentioned, that would be unsafe.  Consider the following topology:

  ::0 --- A --- B

A loses its Internet connection, so it sets the metric of its selected
route to infinity.  Before it sends a retraction, it receives an
unfeasible update from B (with router-id A) -- routing loop.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 30 Apr 2018 15:08:07 +0200

> reboot oftent without saving their seqno.

Right, that's what I thought. I don't think there's a good way to store
persistent state in Bird, but it may be possible to try harder to do
graceful restarts... I'll look into the options.

> If you have an idea for a good mechanism to avoid the issue, I'm

Not off the top off my head..

> SHOULD buffer every TLV and delay sending a packet by a small,
> randomly chosen delay"). Is that a problem in practice?

No, don't think so, it's just an implementation issue: Bird currently
won't resend the same request until it expires after two seconds. So
when the triggered update arrives with S'' (that is still too low), it
won't ask for another seqno increase. But that is a straight-forward
fix, and with that it converges reasonably quickly (as long as the seqno
is not too high I guess...)

> unfeasible update from B (with router-id A) -- routing loop.

Right, thought so :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 30 Apr 2018 15:36:10 +0200

> is not too high I guess...)

Not sure about that -- it will cause extra background traffic, which may
have unintended consequences.  Note that seqnos are 16 bits, so converging
to a feasible seqno takes 16384 packets on average, 32767 worst case.

I'd recommend:

  - add an option for picking a different router-id each time (but
    don't make it the default, since it makes management more difficult
    without stable router-ids);
  - document the issue;
  - bug the BIRD guys about implementing persistent storage; two octets is
    all we're asking for.

Should I document the issue in 6126bis?  I'll definitely add a paragraph
in applicability-statement.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 30 Apr 2018 17:09:26 +0200

> to a feasible seqno takes 16384 packets on average, 32767 worst case.

Yeah, suppose that would be quite a bit of traffic...

>     without stable router-ids);

Hmm, actually, since Bird sets its router ID from an IPv4 address, the
top 32 bits are always zero (for compatibility with the notion of router
ID that Bird uses for other protocols). My implementation of the
randomisation only randomises the top 32 bits, so there's still a stable
identifier. Maybe it would make sense to default to this behaviour?

>   - bug the BIRD guys about implementing persistent storage; two octets is

Yeah, 16 bits should be enough for everyone, right? ;)

> in applicability-statement.

Hmm, documenting it *somewhere* is needed, certainly. Maybe putting it
into 6126bis is a good idea, since I have a nagging suspicion that not
everyone will read the applicability statement before implementing it... ;)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 30 Apr 2018 19:48:59 +0200

> Hmm, actually, since Bird sets its router ID from an IPv4 address,

What if there's no IPv4 address?  What if two IPv6 routers have the same
IPv4 address (because they're in different NAT domains)?  (FYI, babeld
uses the first MAC address if finds that has the local bit unset, and
falls back to random if no such address is found.)

> My implementation of the randomisation only randomises the top 32 bits,
> so there's still a stable identifier. Maybe it would make sense to
> default to this behaviour?

That would break the optimisation of using the low bits of the IPv6
address to encode the router-id.  Probably not a big deal, except in pure
mesh networks.

I'm not sure how you'd avoid router-id collisions, though.

> Yeah, 16 bits should be enough for everyone, right? ;)

You could always encode it in JSON if you want to use more space.

> into 6126bis is a good idea,

Yeah.  I'll try to find some time to make a new revision tomorrow, if
you'd like to send me a patch, I'd be grateful.  (No promise to keep your
wording, though.)

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 30 Apr 2018 21:20:51 +0200

Juliusz Chroboczek <[email-masked]> writes:

> What if there's no IPv4 address? What if two IPv6 routers have the
> same IPv4 address (because they're in different NAT domains)? (FYI,
> babeld uses the first MAC address if finds that has the local bit
> unset, and falls back to random if no such address is found.)

Well, usually the router ID is manually configured. If not, it'll be the
lowest IP on a non-loopback interface. I have no idea what happens if
there are none... There is quite a bit more configuration needed to get
a basic babel node running with bird than with babeld in general; you'll
need a couple dozen lines of config...

> address to encode the router-id.

Bird doesn't do that anyway.

> I'm not sure how you'd avoid router-id collisions, though.

By chance? With 32 bits of randomness, even in a moderately sized
network the chance of collision is quite low (which means that it will
not happen until it is the most inconvenient, of course...) :)

> You could always encode it in JSON if you want to use more space.

I was actually thinking I should add JSON support to Bird :D

> you'd like to send me a patch, I'd be grateful. (No promise to keep
> your wording, though.)

No promises to send any either ;)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 30 Apr 2018 21:42:10 +0200

> Bird doesn't do that anyway.

That's five lines of code, and saves almost half the traffic in pure IPv6
meshes.

> not happen until it is the most inconvenient, of course...) :)

With 100 nodes, probability of collision is 10^-6.  With 1000 nodes, it's
10^-4.  With 2000 nodes, it's 5*10^-4.  With 5000 nodes, it's 3*10^-3.

I think we're at the very edge of comfort, which is why I chose 64 bits in
the first place.

>> I'll try to find some time to make a new revision tomorrow, if you'd
>> like to send me a patch, I'd be grateful. (No promise to keep your
>> wording, though.)

> No promises to send any either ;)

We have a deal.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 30 Apr 2018 21:55:57 +0200

Juliusz Chroboczek <[email-masked]> writes:

> That's five lines of code, and saves almost half the traffic in pure
> IPv6 meshes.

Right, well the reason I didn't include it was that Bird already has a
notion of a router ID (from BGP), which is 32 bits and based on v4
addresses. And it would be breaking assumptions to just override that.

It could conceivably be a switch, though...

> I think we're at the very edge of comfort, which is why I chose 64
> bits in the first place.

Well, the collision domain would not be all nodes, only those with the
same configured router ID (or v4 address absent any configuration).

But yeah, you're not wrong :)

BTW, in the case where there *is* a stable identifier (whether its
EUI-64 or a v4 address), randomising only parts of the router ID would
be a way to keep the stable identifier? For the v4/32 bit case,
randomising the 32 bits is the obvious solution; for EUI-64 you could
just randomise the FFFE part? That way you could gain the reboot support
but still have stable(-ish) identifiers so you could find your node?

-Toke

-Toke