[PATCH] [RFC] Babel: Implement route daming with fixed delay

[Juliusz Chroboczek]

> I would approach the stability problem from an electronics/signal
> processing/control theory background.

I have no signal processing background whatsoever; to my eyes, signal
processing is a fairly advanced for of magic.  (My background is in logic
and programming languages.)

> Frankly I haven't yet been able to reverse-engineer the weird exponential
> smoothing filter behaviour enough to build a model, perhaps you (or
> someone) could expand on the rationale for the smoothing filter
> construction and the addition of hysteresis?

To be honest, we hacked things until we had acceptable worst-case behaviour.

We had two networks to experiment with: Nexedi's production network
(hundreds of tunnels over the public IPv6 Internet) and a simulated
network we built ourselves which we believed represented the worst case (a
bufferbloated diamond network).  We built a first prototype, which we
instrumented to log RTT samples and route flaps, and noticed three things:

1. in the production network, the RTT signal is noisy (see figures 4 and 6
   of [1]);

2. in the bufferbloated diamond network, when we switch away from
   a congested route, we switch back too early, before the buffers have
   had time to drain;

3. in the diamond network, we tend to switch routes as we oscillate around
   a common value.

Hence, the three mechanisms:

1. smoothing of the RTT, to makes the signal less noisy; the smoothing is
   exponential just because it's easy to implement;

2. saturating map from RTT to metric, so that congested routes all appear
   equally bad, and we don't switch back before the buffers drain; this
   was stolen from [2];

3. hysteresis, in order to avoid switching with too high a frequency.

Daniel, if you feel you're competent to work on that, I'd be interested in
collaborating.  I don't currently have funding for Babel, but it should be
easy enough to find some.

References:

[1] https://arxiv.org/pdf/1403.3488.pdf

[2] Atul Khanna and John Zinky. The Revised ARPANET Routing Metric.
    SIGCOMM ’89 Symposium proceedings on Communications architectures and
    protocols, pp. 45-56. ACM New York, NY, USA, 1989.