[Babel-users] Route selection using smoothed metrics

[Juliusz Chroboczek]

Dear all,

I'm currently experimenting with a new algorithm to improve the
stability of route selection in Babel.  The algorithm is fully generic
(it should apply to any routing protocol that has flexible route
selection), and, after quite a few rounds of refinement, turns out to be
trivially simple to implement.

A little bit of background
**************************

Babel is designed to react very fast to topology changes -- after
a route is lost, Babel is supposed to switch to an alternate route after
a time that, in the absence of packet lost, is at most 20ms per hop to
the source.  That's pretty cool when the lost route is due to a mobility
event, but causes route flapping in three scenarios:

  (1) metrics with a lot of jitter (e.g. ETX);
  (2) metrics with a feedback loop (e.g. ETX or delay-based);
  (3) drive-by-night or yo-yo routes (routes that appear just for
      a few seconds then disappear).

I've been searching for an algorithm that would reliably solve the three
scenarios above without seriously impacting Babel's convergence speed or
breaking any of Babel's desirable properties.  A number of solutions did
work, but they were very hackish; I think that I've finally found
a simple and clean algorithm that works.

The main insight is that the stability problem is a pure route selection
problem -- there's no reason why it should impact any other pieces of
Babel.  In particular, no changes are made to the ETX estimator or to
the values that we announce to our neighbours.

The algorithm
*************

For every route r, we maintain a value called the smoothed metric.  For
a new route, the smoothed metric is initialised to INFINITY/2; it then
converges towards the "true" metric obeying an exponential decay law.

We switch routes when

  smoothed_metric(new) < smoothed_metric(old) AND
  metric(new) <= metric(old).

That's all there is to it, and the three scenarios above are handled:

  (1) metrics with a lot of jitter get smoothed;
  (2) metrics with a feedback loop get randomised, which gives a better
      chance of finding an equilibrium;
  (3) drive-by-night routes will never achieve a good smoothed metric,
      so they will never be preferred to stable routes.

Additionally, since the smoothed metric of a route with finite metric is
always finite, a route will be chosen by Babel even if its smoothed
metric is very bad (i.e. it's a recent route).  For that reason, while
route flapping is limited, the ability to reconverge fast after a route
is lost is not impaired.

The only tunable of the algorithm is the speed of exponential decay.

Code availability
*****************

You'll find the new code in the 'smoothed-metric' branch of the Git
repository:

  git clone --branch smoothed-metric git://git.wifi.pps.jussieu.fr/babeld
  
or

  git clone --branch smoothed-metric git://github.com/jech/babeld.git

You should then arrange to run babeld with an `-M' parameter, with the
value of the half-life of the exponential decay; your hello interval, or
perhaps twice that, should be fine.

  babeld -M4 wlan0

If you look at the status display (kill -USR1), routes now have two
metrics -- the original metric, and the smoothed metric.

This code is almost completely untested -- it's running on just the one
router right now.  Please let me know of your experiences.

-- Juliusz