[Babel-users] [babel] About Babel-RTT

[Juliusz Chroboczek]

Hi Justin,

> Assuming that RTT for all links is any non-negative fixed value, then
> RTT is just another monotonic metric and no loops will be formed.

The RTT metric is a strictly monotonic metric, and thus preserves Babel's
loop-free property -- no routing loops, not even short-lived ones, will
arise.

The issue is not with loops: the issue is about persistent oscillations,
which may arise since the RTT metric induces a feedback loop.  Suppose you
have two parallel routes from A to D, as in your example:

    A
   / \
  B   C
   \ /
    D

Suppose Babel sends its traffic through B; packets get queued at B, which
causes the RTT of the A-B-D route to increase, which in turn causes Babel
to send its traffic through C, which in turn causes the RTT of the A-C-D
route to increase, which in turn causes Babel to send its traffic through
B, which in turn...

Babel doesn't care [1] about oscillations.  However, oscillations might
lead to packet reordering, which reduces the throughput of some transport-
layer protocols, notably TCP.  The hysteresis and smoothing algorithms
used in babeld limit the frequency of oscillations (down to one every few
minutes), but we don't quite understand why they work so well [2].

[1] https://tools.ietf.org/html/draft-chroboczek-babel-doesnt-care-00
[2] https://arxiv.org/pdf/1403.3488.pdf

> Assuming RTT can vary arbitrarily we can contrive an example that produces a loop. It just takes some abnormal (but by no means impossible) values.

>     A
>   /   \
>  B     C
>   \   /
>     D

> Lets say our update interval is 1 second and the latency of all links
> varies between 1 second and 10 seconds. A sends a packet with
> destination D to node B. During this packets 2 second flight the RTT
> between B and D increased to 10 seconds with the other links remaining
> at 1 second, so now on receipt B will send that same packet back to
> A.

The route through A is unfeasible, and will not be taken until a request
is exchanged.  The loop-freedom property of Babel is preserved even with
the RTT metric.

> 2) are there any other possible loop conditions?

I have a reasonably formal proof that there are no loops in Babel in
a pure mesh configuration.  (Short-lived loops may arise if the same
destination prefix is announced by multiple routers.)

-- Juliusz