Subject: [babel] A couple of things that are unclear in the RFC

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 02 Nov 2015 23:20:59 +0100

So a couple of minor details popped up in the patch review of my Babel
implementation for the Bird daemon. May be nice to clarify:

1. Is a Router ID of 0 valid? A strict reading of the RFC would suggest
   it is, but am not sure if that is an omission?

2. How should an implementation treat an update TLV that specifies AE 1
   (IPv4 address) and sets flag 0x40 (use address as next router ID)? My
   guess would be that it should be treated as invalid, but the RFC
   doesn't explicitly say.

3. The RFC doesn't specify how to treat subsequent TLVs in the same
   packet if a TLV fails to validate. For some TLVs, most notably the
   Router ID, just ignoring the malformed TLV could result in subsequent
   ones being interpreted wrong. So maybe specifying a policy in the RFC
   is a good idea?

4. The TLV specification includes reserved fields that seem to serve as
   memory alignment spacers; but doesn't specify that the TLVs
   themselves need to be aligned. So why are the reserved fields there?
   Or should there be an alignment requirement?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 03 Nov 2015 18:05:16 +0100

> it is, but am not sure if that is an omission?

It's perfectly valid.  Router-ids are opaque identifiers, 0 is not special
in any way.

> (IPv4 address) and sets flag 0x40 (use address as next router ID)?
> My guess would be that it should be treated as invalid, but the RFC
> doesn't explicitly say.

Agreed.  Either specify how the IPv4 address is padded to 64 bits, or
declare it as invalid.

(No current implementation sends IPv4 addresses with flag 0x40.  Babeld
interprets such TLVs by padding the IPv4 address to 64 bits with zeroes on
the left.)

> ones being interpreted wrong. So maybe specifying a policy in the RFC

Agreed.

> memory alignment spacers; but doesn't specify that the TLVs themselves
> need to be aligned.

No, the TLVs don't need to be aligned.

> So why are the reserved fields there?

The original plan was that an implementation MAY choose to align the TLVs.
I've since realised that the benefits of alignment are negligible, and
hence never used the possibility to align TLVs.

If we decide to change the packet format, the reserved fields should be
dropped.  However, since they only appear in the rarer TLVs (the bulk of
Babel traffic is due to Update TLVs, which don't contain any reserved
fields), it doesn't matter enough to warrant an incompatible protocol
change.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 03 Nov 2015 18:12:30 +0100

> It's perfectly valid.  Router-ids are opaque identifiers, 0 is not special

Right, that's what I thought. Upon thinking about it, mind you; my
initial reaction was to just do if(!router_id) to check if a valid
router ID had been received. Going to change that, obviously, but maybe
point it out in the RFC for the benefit of others as naive as me? :)

> interprets such TLVs by padding the IPv4 address to 64 bits with
> zeroes on the left.)

Well, in Bird, the router ID *is* an IPv4 address; right now I'm padding
it to get it to 64 bits. Not sure if the complexity of specifying
padding is worth it to save a single TLV, though?

> No, the TLVs don't need to be aligned.

Right, that's what I thought.

> The original plan was that an implementation MAY choose to align the
> TLVs. I've since realised that the benefits of alignment are
> negligible, and hence never used the possibility to align TLVs.

OK. Fine with me. Will fix my implementation to not assume alignment :)

> If we decide to change the packet format, the reserved fields should
> be dropped. However, since they only appear in the rarer TLVs (the
> bulk of Babel traffic is due to Update TLVs, which don't contain any
> reserved fields), it doesn't matter enough to warrant an incompatible
> protocol change.

Agreed.

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 03 Nov 2015 18:26:14 +0100

> padding is worth it to save a single TLV, though?

Option 1:

  if(addrlen >= 8)
      memcpy(router_id, addr + 8 - addrlen, 8);
  else
      goto invalid;

Option 2:

  if(addrlen >= 8)
      memcpy(router_id + 8 - addrlen, addr, addrlen);
  else
      memcpy(router_id, addr + addrlen - 8, 8);

So I don't think there's much extra complexity, and it does save one TLV
per update in extreme cases (IPv4-only pure mesh networks with router-ids
derived from the IPv4 address).
  
-- Juliusz

---

From: Henning Rogge <[email-masked]>
Date: Tue, 3 Nov 2015 18:26:39 +0100

> OK. Fine with me. Will fix my implementation to not assume alignment :)

Assuming alignment is a very subtle way to break a protocol
implementation... I still want three weekends of debugging back
because someone did it with an plugin for our olsr.org OLSRv1
implementation.

Henning Rogge

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 03 Nov 2015 18:31:54 +0100

> because someone did it with an plugin for our olsr.org OLSRv1

Yup, that was probably going to come back and bite me at some point;
thankfully it was caught in patch review :)

-Toke

---

From: "Russ White" <[email-masked]>
Date: Wed, 4 Nov 2015 02:15:58 -0500

> > Well, in Bird, the router ID *is* an IPv4 address; right now I'm
> > padding it to get it to 64 bits. Not sure if the complexity of
> > specifying padding is worth it to save a single TLV, though?

IMHO -- don't tie the router id to an IP address. OSPF and BGP have been
bound up in the mess for years, with all sorts of bad consequences. Instead,
just specify a 64 bit number and --

1. Provide some suggestions on where to get this number from (hash across
all ipv4 addresses, hash across layer 2 addresses, manual configuration,
eui64 address on local box, etc.)

2. Provide something to do when there's a duplicate detected -- somehow the
new device needs to be told there's a problem, and asked to change their id.

:-)

Russ

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 04 Nov 2015 11:23:05 +0100

> eui64 address on local box, etc.)

This is exactly what the Babel RFC does: It specifies that a Router ID
is an arbitrary 64-bit number which "SHOULD be assigned in modified
EUI-64 format" (section 4.1.2).

However, in my Bird implementation I'm re-using the Bird router ID,
which is an IP address; for what I'm guessing is exactly the legacy
reasons you are referring to.

> 2. Provide something to do when there's a duplicate detected --
> somehow the new device needs to be told there's a problem, and asked
> to change their id.

This mechanism does not currently exist in Babel. Not sure there's any
way to detect that; anything else you see on the network with your own
Router ID might just be your own routes being relayed back to you, no?

-Toke

---

From: "Russ White" <[email-masked]>
Date: Wed, 4 Nov 2015 06:59:05 -0500

> > 1. Provide some suggestions on where to get this number from (hash
> > across all ipv4 addresses, hash across layer 2 addresses, manual
> > configuration,
> This is exactly what the Babel RFC does: It specifies that a Router ID is an
> arbitrary 64-bit number which "SHOULD be assigned in modified

Okay -- I would try to make it a point not to use an IP address as the router id. This might seem silly, but it makes a difference when you have bleary eyes at 2am not to confuse the router id with an ip address... Making things easier to sort mentally makes troubleshooting easier. :-)

> This mechanism does not currently exist in Babel. Not sure there's any way
> to detect that; anything else you see on the network with your own Router
> ID might just be your own routes being relayed back to you, no?

I had, in the back of my head, EIGRP externals and duplicate router id detection. Of course it's an issue if there are two routers with the same id in the network -- but we'd have to think through how to detect it without breaking anything. Short of including a cryptographic hash as part of some sort of router advertisement, there's no real way to tell if two routers with the same id are just parallel links, or if they're actually different routers. In a protocol designed for pretty much autonomic operation, being able to detect this might be a good thing. More thought needed here... :-)

:-)

Russ

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 04 Nov 2015 15:11:59 +0100

> I had, in the back of my head, EIGRP externals and duplicate router id
> detection. [...] In a protocol designed for pretty much autonomic
> operation, being able to detect this might be a good thing.

I agree, and this is the reason why Babel router-ids are 64 bits long
rather than 32-bits like in EIGRP -- to make the probability of collision
vanishingly small.

  https://xkcd.com/221/

> Of course it's an issue if there are two routers with the same id in the
> network -- but we'd have to think through how to detect it without
> breaking anything.

If there's no duplication of router-ids, then all routes announced with
router's A router-id should be unfeasible for A.  Therefore, if A sees
a feasible route with its router-id, then it has detected duplication.

If A and B share a router-id, then either A or B is able to detect the
issue (but not necessarily both).

The only caveat -- if A detects router-id duplication just after it
reboots, then it cannot determine whether it's colliding with a different
router B or seeing routes that were announced by A's previous incarnation.

-- Juliusz

---

From: "Russ White" <[email-masked]>
Date: Thu, 5 Nov 2015 20:25:33 -0500

> > Of course it's an issue if there are two routers with the same id in
> > the network -- but we'd have to think through how to detect it without
> > breaking anything.
> 
> router's A router-id should be unfeasible for A.  Therefore, if A sees a
feasible
> route with its router-id, then it has detected duplication.

Actually, this is a useful construction -- you could:

1. Add an additional "router route" to your advertisements. This is an
advertisement of a zero cost route to a second unique number, let's just use
the term nonce for the moment, that will survive a reboot, and cannot be
manually configured by the user.

2. When you come back up, don't advertise this "router route" for some time
(assume max propagation time through the network, perhaps).

3. On booting, if you see a "router route" advertisement from your own id,
then check the "nonce," and if they match -- it's yours. If not, then it's a
duplicate. 

This effectively makes the odds of a duplicate really high, because you have
a locally derived number that can't be user configured, and can't be
changed, combined with the router id, which could be misconfigured.

Just an idea... Haven't thought it through entirely.

:-)

Russ