Subject: Re: [babel] Alvaro Retana's Discuss on draft-ietf-babel-rfc6126bis-12: (with DISCUSS and COMMENT)

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 18 Oct 2019 18:22:57 +0200

Dear Alvaro,

Unless I'm mistaken, I have not received a reply to my mail of 21 August.
Thus, I have no idea whether you found my explanation of the issues
related to route oscillation convincing.

I have just added the following appendix to the document, and referred to
it in the (normative) section about route selection.  Please let me know
if it satisfies you, and if it does not, please explain what more you
would like me to do.

A.4.  Route selection

   Route selection (Section 3.6) is the process by which a node selects
   a single route among the routes it has available towards a given
   destination.  With Babel, any route selection procedure that only
   ever chooses feasible routes with a finite metric will yield a set of
   loop-free routes; however, not all route selection policies will
   yield good reasults.

   The obvious route selection procedure is to pick, for every
   destination, the feasible route with minimal metric.  When all
   metrics are stable, this strategy leads to convergence to a tree of
   shortest paths (assuming the metric is left-distributive).  There are
   two reasons, however, why this strategy leads to instability in the
   presence of continously varying metrics such as ETX (Appendix A.2.2).
   First, if two parallel routes oscillate around a common value, then
   the smallest metric strategy will keep switching between one and the
   other.  Second, when a route is selected, congestion along it
   increases, which may increase packet loss, which in turn causes its
   metric to increase; this is a feedback loop, of the kind that is
   prone to cause persistent oscillations.

   A simple strategy to avoid this kind of instabilities is to only
   switch routes when the target route's metric is smaller by some
   constant K than the currently selected metric.  However, this
   approach is difficult to tune well: if K is too small, then it fails
   to avoid oscillations, and if it is too large, then it leads to sub-
   optimal routing.  A better strategy is to apply hysteresis
   (sensitivity to a route's history) to the route selection algorithm.
   The following hysteresis algorithm appears to yield good results with
   a variety of metrics.

   For every route R, in addition to the route's metric m(R) maintain a
   smoothed version of m(R) written ms(R) (we suggest computing ms(R) as
   an exponential average of m(R) with a time constant proportional to
   the Hello interval).  If no route to a given destination is selected,
   then select the route with the smallest metric, ignoring the smoothed
   metric.  If a route R is selected, then switch to a route R' only
   when both m(R') <m(R) and ms(R') <ms(R).

   Intuitively, the smoothed metric is a long-term estimate of the
   quality of a route.  The algorithm above works by only switching
   routes when both the instananeous and the long-term estimate of the
   route's quality indicate that switching is profitable.

---

From: "Vigoureux, Martin (Nokia - FR/Paris-Saclay)" <[email-masked]>
Date: Fri, 18 Oct 2019 22:16:59 +0000

Juliusz,

thanks again.
Based on my understanding of the discussions with Alvaro, the pending 
points were:
(A) he was expecting a RECOMMENDED route selection algo and this could 
for example be the most common algo in babel implems. I'm not sure if 
A.4 strictly addresses that.

(B) the “Plen MUST be 0” issue

(C) is resolved

-m