Subject: [babel] Redefining the encoding of source-specific updates

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 09 Jun 2016 17:55:04 +0200

Dear all,

Matthieu and I are considering changing the encoding of source-specific
updates in an incompatible manner.  We haven't decided anything yet,
here's a summary of our thinking.

The current encoding of source-specific updates is described in

  https://tools.ietf.org/html/draft-boutier-babel-source-specific-01

In short, a source-specific update is carried by a new TLV type, which is
silently ignored by non-source-specific implementations.  There are two
other new TLV types, for requests for source-specific routes.

Note that source-specific updates cannot be encoded as an ordinary update
with a sub-TLV for the source, since Babel lacks a mandatory bit: the
sub-TLV would be discarded by non-source-specific routers, and the update
would be mis-interpreted, leading to routing pathologies.

Now Babel uses a single Update TLV for both IPv4 and IPv6; IPv4 is
distinguished from IPv6 by the AE, which is a one-octet field with values
1 for IPv4 and 2 for IPv6.  See Section 4.1.3 of RFC 6126.  Unknown TLVs
are silently discarded according to RFC 6126 (although Matthieu has noted
a bug in the implementation with this).

The idea would be to encode source-specific updates using the existing
Update TLV, with two new AE values for v4 source-specific and v6
source-specific.  This avoids the need for three new TLVs, and
significantly simplifies the packet parser.

There are some minor complications; the structure of the Update TLV
changes, but only for the new AEs (so compatibility is preserved).
Additionally, there are some complications with address compression (do we
organise a leak of information between different AEs, or do we make
compression completely independent?  the latter is simpler and cleaner, so
I tend to favour it, while the former gives slightly better compression).

Opinions?

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 9 Jun 2016 20:29:51 +0300

> other new TLV types, for requests for source-specific routes.

Disclaimer: You know I am not big fan of the current encoding :)

> significantly simplifies the packet parser.

I like this.

> I tend to favour it, while the former gives slightly better compression).

I prefer the latter as well. I suspect compression rates are not deal breaker and defining leakage so that it works also in presence of future AEs is bit iffy. e.g. can you do it only in AEs increasing order or..? :-p (if you assume people implement AEs in definition order)

Cheers,

-Markus

---

From: Dave Taht <[email-masked]>
Date: Thu, 9 Jun 2016 13:36:18 -0700

I am sufficiently lazy to ask (rather than try to calculate) what the
difference in compression ratio is and if there are other changes in
encoding that would make it better under various use cases. (I was
impressed by the bmx7 encodings)

If I have 3 source specific gateways, what happens?

If I am using source specific to let me advertise clients deep in the
network that have 3 SS/64s (or /128s) attached, what happens?[1] (Do I
always have to announce all IPs a given device has or can they be
propagated once, refreshed (perhaps based on their assigned lifetime),
or retracted periodically, and merely update reachability info for
that router_id)

Say, you wanted to do SS to a small city, with 1000 SS exit nodes and
a secondary meshy backbone, what happens?

[1] These are my actual use cases for a deployed network that I am
really loathe to make updates to.

On Thu, Jun 9, 2016 at 10:29 AM, Markus Stenberg <[email-masked]> wrote:
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

-- 
Dave Täht
Let's go make home routers and wifi faster! With better software!
http://blog.cerowrt.org

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 09 Jun 2016 23:46:52 +0200

> encoding that would make it better under various use cases.

It depends very much on the nature of the network.

> (I was impressed by the bmx7 encodings)

Yes, Alex has done a good job.  However, he's using inter-packet state,
which gives rise to a whole set of tradeoffs.  In Babel, we only keep
parser state within a single packet, and that's not likely to change.

With the current encoding, only the destination address gets compressed,
and source-specific contributes no compression state, which avoids
confusing non-source-specific abwabel:

So if you're announcing

  2001:db8:1234:5678::/64
  2001:db8:1234:5678:dead:beef:f00:ba4/128
  2001:db8:1234:5678::/64 src 2001:db8:1234::/48
  2001:db8:1234:5678::/64 src 2001:db8:5678::/48
  ::/0 src 2001:db8:5678::/48

you only encode

  2001:db8:1234:5678::/64
  (compressed):dead:beef:f00:ba4/128
  (compressed)::/64 src 2001:db8:5678::/48
  (compressed)::/64 src 2001:db8:5678::/48
  ::/0 src 2001:db8:5678::/48

Note how destination prefixes get compressed away, but there's no
compression for the source prefixes.

What Markus and I have in mind is an encoding in which there are separate
compression states for non-specific and source-specific AEs.  So the above
will compress as
  
  2001:db8:1234:5678::/64
  (compressed):dead:beef:f00:ba4/128
  2001:db8:1234:5678::/64 src 2001:db8:1234::/48
  (compressed)::/64 src (compressed):5678::/48
  ::/0 src (compressed)::/48

Note how both destination and source prefixes get compressed, but the
compression state needs to be reestablished for the first source-specific
update (2001:db8:1234:5678 is explicitly encoded twice, once for
non-source-specific and once for source-specific).

The alternative would be to have some unidirectional leaking between
non-source-specific and source-specific, so as to get

  2001:db8:1234:5678::/64
  (compressed):dead:beef:f00:ba4/128
  (compressed)::/64 src 2001:db8:1234::/48
  (compressed)::/64 src (compressed):5678::/48
  ::/0 src (compressed)::/48

This is likely to gain up to 8 octets for each non-default source-specific
route, but at the cost of a much more complex implementation and
specification, and bad compositionality with further extensions
(TOS-specific is likely to happen).  Note that if all source-specific
routes are default routes, the gain is nil.

-- Juliusz