Subject: [babel] Open issues with draft-ietf-babel-rtt-extension

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 24 Jul 2019 23:46:38 +0200

Here's my personal take on the issues outlined during Baptiste's talk.

1. Nanosecond granularity

Originally, Baptiste's extension used centiseconds in a 16-bit field,
which gave a granularity of 10ms.  Under Dave Taht's pressure, who was at
the time interested in measuring bufferbloat, Baptiste switched to
microseconds in a 32-bit field.

We still don't have a good example of why this increased prefision is
needed -- in the networks that use this extension in production, the time
scales under consideration are on the order of tens or hundreds of
milliseconds.

Switching to nanoseconds would require switching to 48-bit fields, since
the timestamps must not wrap between two successfully received Hello or
IHU TLVs.  Not a big deal, but a slight implementation issue -- I'd like
to be convinced that this is necessary.

We will be able to switch formats without a flag day.  We first define
a new sub-TLV with nanosecond granularity, and start sending both.  We
wait for a year or so, until most deployed implementations understand the
new format, then we deprecate the old format.  If any old implementations
remain, they will ignore the new sub-TLV, and simply fail to perform any
RTT estimation, falling back to the base protocol.

2. Decoupling timestamps from Hello

Currently, the timestamp data is sent in two pieces:

  - Hello contains the transmit timestamp, which is the same for all
    neighbours;
  - IHU contains the receive timestamp and the timestamp echo, which are
    per-neighbour.

This makes a lot of sense -- after all, IHUs contain per-neighbour data,
while sender data is contained in Hellos.  OTOH, it means that an IHU's
timestamp can only be interpreted if it is sent in a packet that contains
a Hello TLV.

Baptiste outlined two solutions:

  (a) require that all IHUs be sent in packets with a Hello;
  (b) define a new TLV that contains just a timestamp.

In RFC 6126bis, we defined Unicast Hellos and Unscheduled Hellos, which
should in principle make approach (a) easy to implement.  I'd be very
grateful if people could look very carefully at the new kinds of Hello,
and decide whether these mechanisms are enough, or whether we need a new
kind of TLV so we can avoid sending spurious Hellos.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 25 Jul 2019 13:06:34 +0200

> RTT estimation, falling back to the base protocol.

We could also just define a new sub-TLV with the added precision,
couldn't we? I.e., keep the usecs and add 10 additional bits with
the sub-usec fraction.

Either way I'm fine with holding off on defining this until we have
demonstrated that it's useful.

> kind of TLV so we can avoid sending spurious Hellos.

I haven't looked very carefully, but I think you are probably right that
we *can* make do with this. A separate timestamp TLV seems
architecturally cleaner to me, though, although I can't really explain
why...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 25 Jul 2019 13:34:28 +0200

> architecturally cleaner to me, though, although I can't really explain

I have the same feeling.

---

From: Dave Taht <[email-masked]>
Date: Thu, 25 Jul 2019 06:06:10 -0700

I had had a chance to buttonhole baptiste at battlemesh, and also
tried to get a test up and running.

A couple points.

A) Packet loss is not much of a thing on modern wifi networks,
particularly with unicast
B) As you have larger numbers of routes (1000s), congestion control
becomes a problem

My "solution" for some congestion control issues is to start
dynamically increasing the route announcement
interval for stabler routes, while still announcing the most important
ones (like defaults) in the hello. the protocol has an underused
feature where we can announce a per route interval larger than the
default.

i long ago patched out CS6 as it lands in the VO queue which cannot
aggregate on wireless-n in favor of ecn. I've had a variant that just
ecn's the hello, also.

Most of my babel routing failures were congestive in nature before I
did this. (I also, in the end dramatically
reduced the size of my route table and the size of the babel network,
at one point it was 100+ nodes with ~10 route announcements each which
became rather unreliable. Now, it's < 20 with ~3). I do wish more folk
would do the kind of experiments teco did to test larger babel
networks, and I did with the rtod tool on github. Until more core folk
start pushing the protocol (and daemons) to larger numbers of routes
we're not going to have mutually clear insights here.

> microseconds in a 32-bit field.

I have largely been waiting for all the other stuff to land before
pursuing these ideas again. Needed
SS routing, thought unicast would change the game on wifi entirely.

> scales under consideration are on the order of tens or hundreds of

It certainly was my hope at the time to be able to extend this to real
networks, on wifi. nsec
resolution is not required there either, but 10s of usec precision
seemed feasible at the time.

nsec might buy some better ability to detect (when coupled with the
increasingly common hw timestamping and/or hw pacing techniques) -
1gigE+ networks.

> RTT estimation, falling back to the base protocol.

I don't presently see a need for nsec.

> kind of TLV so we can avoid sending spurious Hellos.

Generically I had looked as this as a path forward to getting
congestive controls to start working,
leveraging the must-ack tlv also, whatever it's called. So being able
to include a timestamp at the end of a route burst seemed helpful.

>
> -- Juliusz
>
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

--

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740

---

From: Baptiste Jonglez <[email-masked]>
Date: Thu, 25 Jul 2019 16:57:11 +0200

> >   (b) define a new TLV that contains just a timestamp.

Thank you for summarizing.  You apparently didn't like my "Solution 1"
because you don't even mention it, but I agree it's a bad idea anyway :)

The slides of my presentation are here: https://datatracker.ietf.org/meeting/105/materials/slides-105-babel-delay-based-metric-extension-for-the-babel-protocol-00

> architecturally cleaner to me, though, although I can't really explain

I also think unicast/unscheduled Hellos can make (a) work without further
hacks, but indeed it feels somewhat uncomfortable that Hello messages are
used for several roles (neighbour discovery and maintenance, link quality
estimation, RTT estimation).  It works if these roles don't conflict, but
it's walking on a tightrope, as the Unscheduled Hello "hack" shows.

The main issue is that we lack practical experience on this: I didn't
check all implementations, but it seems that nobody actually implemented
unicast Hellos yet?

-- 
Baptiste Jonglez
PhD student
Univ. Grenoble Alpes <https://www.univ-grenoble-alpes.fr/>
LIG lab <https://www.liglab.fr/>
Drakkar team <http://drakkar.imag.fr/>  |  Polaris team at INRIA <https://team.inria.fr/polaris/>

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 26 Jul 2019 23:38:24 +0200

> because you don't even mention it, but I agree it's a bad idea anyway :)

Right, I missed that.  Baptiste's "Solution 1" is to duplicate the transmit
timestamp in all IHUs.

While it yields a somewhat cleaner packet format, it complicates the
implementation somewhat.  The transmit timestamp must be computed as close
as possible to packet transmission, so it gets patched in into the packet
at the very last moment.  In the current packet format, there's just one
transmit timestamp per packet, so we just keep one pointer to the space
reserved for the timestamp.  If the transmit timestamp gets duplicated,
then we need to either maintain a list of places to patch, or reparse the
packet just before we ship it out.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 26 Jul 2019 23:41:34 +0200

> B) As you have larger numbers of routes (1000s), congestion control

I'm pretty sure that packet pacing (spreading the announcements over the
update interval rather then sending them all as a burst as we currently do)
would solve your issues, Dave.

This won't happen for 1.9, which I'd like to release before the summer ends.

> My "solution" for some congestion control issues is to start dynamically
> increasing the route announcement interval for stabler routes, while
> still announcing the most important ones (like defaults) in the
> hello. the protocol has an underused feature where we can announce a per
> route interval larger than the default.

Indeed.  This can be done in addition to packet pacing.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 26 Jul 2019 23:53:51 +0200

> estimation, RTT estimation).

The logic is that:

  - Hello TLVs carry link-local information about the sending peer;
  - IHU TLVs carry link-local information about the receiving peer.

From that point of view, the local timestamp belongs in the Hello packet.

The apparent complication is that Hello packets are also used to carry
negative information: missing enough Hellos indicates that the sending
node has died or moved away.  Hence the need to carry a timeout.

An unscheduled Hello is simply a Hello that opts out from the timeout
subprotocol.

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Fri, 26 Jul 2019 16:30:19 -0700

> would solve your issues, Dave.

I think it would make a big difference yes. Ain't a lot of code,
either, and the upcoming
release of openwrt is mostly 4.14 based. I can go toss the patch together again.

> This won't happen for 1.9, which I'd like to release before the summer ends.

Would love to see that make this openwrt release.

> Indeed.  This can be done in addition to packet pacing.

I think this is a good long term solution to larger numbers of routes
on stabler networks.

In either case the "fitting" algorithm for these two approaches either
separate or combined has to somehow stay below the allocated
bandwidth, and we need more experience with unicast and real networks
than we have as yet.

It's not enough though, to get to my (personal) goal of being able to
carry a full ipv6 route table (64k routes); too many scalability
issues
in the code itself.

> -- Juliusz

I also keep hoping somehow someday we'll get to atomic updates. The
nexthop code finally landed in 5.2? (3?) netlink, so that can safely
wait til after 1,9.

-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740