Subject: [babel] About link estimation in Babel: answer to Mickael's question

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 04 Apr 2016 18:27:57 -0300

There was a very good question by Mickael Abrahamsson at the Babel BoF,
which I'd like to reply to in detail.

Babel is being advertised as suitable for autoconfiguring link metrics,
and Mickael is concerned that this is not explicit in the charter.  It is:
the Charter speaks about metrics, and the link quality estimator is what
defines the metric.

This works in combination with two mechanisms:

  1. the loop avoidance mechanism, which guarantees that even when the
     link quality estimator is unstable the packets are still following
     loop-free paths;

  2. the hysteresis mechanism, which tries to ensure that even when the
     link quality estimator is unstable the routing doesn't flap too
     badly.

In RFC 6126, the body of the document only specifies the properties that
a metric must have.  An example link estimator is in an appendix, and the
RFC tries to encourage experimenting with other link estimators.

No hysteresis algorithm is described in RFC 6126.  I did quite a lot of
experimenting on hysteresis algorithms, and I've described one that
appears to work well in Section IV.B of http://arxiv.org/pdf/1403.3488v1.pdf .

Now please stop reading.

1. The link quality estimator currently implemented and described is very
   naïve, and has horribly slow convergence (you get one bit of data per
   Hello exchange), but it is easy to implement and doesn't require any
   cross-layer interactions.  Much better can be done, either by listening
   to physical layer parameters (as the OpenRouting people have shown), or
   by hooking into the link layer (Minstrel data in the case of Linux).
   This is non-portable and tricky to implement, but the benefits are
   huge.  Since all of our users use Babel in fixed networks, where link
   quality evolves slowly, there is little incentive to work on that.

2. The hysteresis algorithm is clean and works well, but I haven't yet
   found out what properties are desirable for a hysteresis algorithm.

-- Juliusz

---

From: Mikael Abrahamsson <[email-masked]>
Date: Mon, 4 Apr 2016 23:54:14 +0200 (CEST)

> the Charter speaks about metrics, and the link quality estimator is what

My concern is that the working group will be part of routing area (if I 
understand correctly), but in the current Babel implementation, it also 
does link quality estimations and sets metrics.

So in IETF terms, should this link quality estimation still be done by 
this working group which will mostly have routing skillset and not link 
quality estimation skillset (whoever might have that, I don't know).

I just want what is being decided to be perfectly clear to everybody, so 
they don't have to be astonished when they discover that Babel does this 
as I was approximately a year ago.

So either put the link quality estimator/metric setting functionality 
explicitly in the charter as being something that would be in-scope, or 
make it out of scope and move it somewhere else. For Babel to actually 
work the way it was intended and described, it needs this functionality.

The work has to be done somewhere and people should know about this, it 
should not be submerged under some other item where it's not obvious 
what's going on.

-- 
Mikael Abrahamsson    email: [email-masked]

---

From: Uma Chunduri <[email-masked]>
Date: Mon, 4 Apr 2016 22:10:39 +0000

AFAICT, Algorithms to configure link metrics should stay outside of the routing protocols itself as this is an orthogonal functionality.

May be for some deployments this is necessary but I don't see this is a routing functionality and should be separated perhaps from the core protocol.

--
Uma C.

-----Original Message-----
From: babel [mailto:[email-masked]] On Behalf Of Mikael Abrahamsson
Sent: Monday, April 04, 2016 2:54 PM
To: Juliusz Chroboczek
Cc: [email-masked]
Subject: Re: [babel] About link estimation in Babel: answer to Mickael's question

On Mon, 4 Apr 2016, Juliusz Chroboczek wrote:

> There was a very good question by Mickael Abrahamsson at the Babel 
> BoF, which I'd like to reply to in detail.
>
> Babel is being advertised as suitable for autoconfiguring link 
> metrics, and Mickael is concerned that this is not explicit in the charter.  It is:
> the Charter speaks about metrics, and the link quality estimator is 
> what defines the metric.

My concern is that the working group will be part of routing area (if I understand correctly), but in the current Babel implementation, it also does link quality estimations and sets metrics.

So in IETF terms, should this link quality estimation still be done by this working group which will mostly have routing skillset and not link quality estimation skillset (whoever might have that, I don't know).

I just want what is being decided to be perfectly clear to everybody, so they don't have to be astonished when they discover that Babel does this as I was approximately a year ago.

So either put the link quality estimator/metric setting functionality explicitly in the charter as being something that would be in-scope, or make it out of scope and move it somewhere else. For Babel to actually work the way it was intended and described, it needs this functionality.

The work has to be done somewhere and people should know about this, it should not be submerged under some other item where it's not obvious what's going on.

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

---

From: "Joel M. Halpern" <[email-masked]>
Date: Mon, 4 Apr 2016 18:20:35 -0400

My personal opinion is that

1) The link metric estimation extension should be a later piece of work, 
after we do what needs be done to get to PS.

2) If we do such an extension, the mechanisms and any constants it 
recommends should be developed in collaboration with the relevant 
exprtise either here in the IETF or in other places like the IEEE.  (It 
may be that the mechanism can be developed in Babel, and only reviewed 
elsewhere.  The parameters would seem to need tighter collaboration.)

Yours,
Joel

---

From: Teco Boot <[email-masked]>
Date: Tue, 5 Apr 2016 00:35:03 +0200

For having consistent behavior with zero-admin, mixed vendor equipment, here has to be a parameter profile for link costs. We cannot ask for example 802 + MOCA + PLC folks to come up with such. It is Homenet WG or Babel WG that come up with a SHOULD BCP. MUST is not needed, babel doesn't care..

RFC 6126 provides default values for timers. IMHO optimization is needed. I expect packet delivery as soon as gig-ethernet LED is green. Timers could be based on link capacity and number of neighbors when medium is shared. Maybe size of topology. Maybe CPU speed, less an issue these days.

Teco

> Op 5 apr. 2016, om 00:10 heeft Uma Chunduri <[email-masked]> het volgende geschreven:
>

---

From: Tony Przygienda <[email-masked]>
Date: Mon, 4 Apr 2016 20:52:50 -0700

all fine but don't forget the "interoperability". The spec + normative
references (if e.g. estimation is provided by another normative reference)
must specify all the values to be implemented (or choices possible) that
will guarantee interoperability out the box (i.e. convergence)

if you think that "babel doesn't care" and any value goes I suggest
extensive simulation over extensive range of values (mixed on different
routers) and see whether you get acceptable convergence behavior &
loop/blackhole free behavior.

--- tony

On Mon, Apr 4, 2016 at 3:35 PM, Teco Boot <[email-masked]> wrote:

> For having consistent behavior with zero-admin, mixed vendor equipment,
> here has to be a parameter profile for link costs. We cannot ask for
> example 802 + MOCA + PLC folks to come up with such. It is Homenet WG or
> Babel WG that come up with a SHOULD BCP. MUST is not needed, babel doesn't
> care..
>
> RFC 6126 provides default values for timers. IMHO optimization is needed.
> I expect packet delivery as soon as gig-ethernet LED is green. Timers could
> be based on link capacity and number of neighbors when medium is shared.
> Maybe size of topology. Maybe CPU speed, less an issue these days.
>
> Teco
>
>
> > AFAICT, Algorithms to configure link metrics should stay outside of the
> routing protocols itself as this is an orthogonal functionality.
> >
> > May be for some deployments this is necessary but I don't see this is a
> routing functionality and should be separated perhaps from the core
> protocol.
> >
> > --
> > Uma C.
> >
> they don't have to be astonished when they discover that Babel does this as
> I was approximately a year ago.
> >
> make it out of scope and move it somewhere else. For Babel to actually work
> the way it was intended and described, it needs this functionality.
> >
> should not be submerged under some other item where it's not obvious what's
> going on.
> >
> > --

-- 
*We’ve heard that a million monkeys at a million keyboards could produce
the complete works of Shakespeare; now, thanks to the Internet, we know
that is not true.*
—Robert Wilensky

---

From: Teco Boot <[email-masked]>
Date: Tue, 5 Apr 2016 14:47:08 +0200

Agreed.

I have my personal opinions on simulation. I prefer testing with real stuff also. Sometimes, different outcomes. I'm still fighting negative feedback with ETX on 802.11 links.

Teco

> Op 5 apr. 2016, om 05:52 heeft Tony Przygienda <[email-masked]> het volgende geschreven:
> 
> all fine but don't forget the "interoperability". The spec + normative references (if e.g. estimation is provided by another normative reference) must specify all the values to be implemented (or choices possible) that will guarantee interoperability out the box (i.e. convergence)
> 
> if you think that "babel doesn't care" and any value goes I suggest extensive simulation over extensive range of values (mixed on different routers) and see whether you get acceptable convergence behavior & loop/blackhole free behavior.
> 
> --- tony
> 
> We’ve heard that a million monkeys at a million keyboards could produce the complete works of Shakespeare; now, thanks to the Internet, we know that is not true.
> —Robert Wilensky

---

From: Gabriel Kerneis <[email-masked]>
Date: Tue, 5 Apr 2016 14:55:57 +0200

Out of curiosity, what do people generally use to simulate wifi (ad-hoc)
links?

Gabriel

On Tue, Apr 5, 2016 at 2:47 PM, Teco Boot <[email-masked]> wrote:

> Agreed.
>
> I have my personal opinions on simulation. I prefer testing with real
> stuff also. Sometimes, different outcomes. I'm still fighting negative
> feedback with ETX on 802.11 links.
>
> Teco
>
>
> > RFC 6126 provides default values for timers. IMHO optimization is
> needed. I expect packet delivery as soon as gig-ethernet LED is green.
> Timers could be based on link capacity and number of neighbors when medium
> is shared. Maybe size of topology. Maybe CPU speed, less an issue these
> days.
> >
> > Teco
> >
> >
> > > AFAICT, Algorithms to configure link metrics should stay outside of
> the routing protocols itself as this is an orthogonal functionality.
> > >
> > > May be for some deployments this is necessary but I don't see this is
> a routing functionality and should be separated perhaps from the core
> protocol.
> > >
> > > --
> > > Uma C.
> > >
> > > My concern is that the working group will be part of routing area (if
> I understand correctly), but in the current Babel implementation, it also
> > > I just want what is being decided to be perfectly clear to everybody,
> so they don't have to be astonished when they discover that Babel does this
> > > The work has to be done somewhere and people should know about this,
> it should not be submerged under some other item where it's not obvious
> what's going on.
> > >
> > > --
> > We’ve heard that a million monkeys at a million keyboards could produce
> that is not true.

---

From: Tony Przygienda <[email-masked]>
Date: Tue, 5 Apr 2016 06:36:36 -0700

simulations are controlled experiments and can be rerun. Big advantage.
Yes, if the model/simulation does not capture relevant aspects of reality,
it's only an academic exercise -)

---

From: Teco Boot <[email-masked]>
Date: Tue, 5 Apr 2016 16:10:48 +0200

I'm using CORE ( http://www.nrl.navy.mil/itd/ncs/products/core ), because it is simple to use and lightweight. It runs real code. RF links can be simulated with add-on EMANE tool ( http://www.nrl.navy.mil/itd/ncs/products/emane ), I don't use EMANE that much.

The negative feedback loop has to do with queuing & WME support in kernel / wireless drivers or NIC. Hard to simulate.

I had some fun playing around with MPTCP and SADR in a Homenet config. In Praque, Henning hacked SADR in olsrd2. I'll enjoy myself with babeld this IETF.

Teco

> Op 5 apr. 2016, om 14:55 heeft Gabriel Kerneis <[email-masked]> het volgende geschreven:
> 
> Out of curiosity, what do people generally use to simulate wifi (ad-hoc) links?
> 
> Gabriel
>

---

From: Uma Chunduri <[email-masked]>
Date: Tue, 5 Apr 2016 20:08:01 +0000

Agree with Tony on what he said below.

Just a quick reply for the subsequent mail below.

                >For having consistent behavior with zero-admin, mixed vendor equipment, here has to
             >be a parameter profile for link costs.

[Uma]: Here obviously you are talking about a requirement where zero-admin is required for a deployment .
             I am sure couple of other requirements for link quality estimation etc. also would be documented in
             some sort of requirement document once WG is   formed.
            This would help in multiple fronts on why protocol is doing the way it is doing currently.

             >We cannot ask for example 802 + MOCA + PLC
             >folks to come up with such.

[Uma]: I see multiple use cases here.. would there be any difference w.r.t to requirements ??

              >It is Homenet WG or Babel WG that come up with a SHOULD BCP.
             >MUST is not needed, babel doesn't care..

[Uma]: Yes, Babel shouldn’t care .. and hence this should be separate from Babel core document.

--
Uma C.

From: Tony Przygienda [mailto:[email-masked]]
Sent: Monday, April 04, 2016 8:53 PM
To: Teco Boot
Cc: Uma Chunduri; Juliusz Chroboczek; [email-masked]; Mikael Abrahamsson
Subject: Re: [babel] About link estimation in Babel: answer to Mickael's question

--- tony

On Mon, Apr 4, 2016 at 3:35 PM, Teco Boot <[email-masked]<mailto:[email-masked]>> wrote:
For having consistent behavior with zero-admin, mixed vendor equipment, here has to be a parameter profile for link costs. We cannot ask for example 802 + MOCA + PLC folks to come up with such. It is Homenet WG or Babel WG that come up with a SHOULD BCP. MUST is not needed, babel doesn't care..

Teco

> Op 5 apr. 2016, om 00:10 heeft Uma Chunduri <[email-masked]<mailto:[email-masked]>> het volgende geschreven:
>
> From: babel [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Mikael Abrahamsson
> Cc: [email-masked]<mailto:[email-masked]>
> Mikael Abrahamsson    email: [email-masked]<mailto:[email-masked]>
>
> [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>

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

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 05 Apr 2016 18:32:36 -0300

> quality estimation skillset (whoever might have that, I don't know).

[...]

> make it out of scope and move it somewhere else.

Uh-huh.

But I'm not sure it belongs in the charter -- shouldn't that be decided by
the WG rather than the people drafting the charter?

---

From: Alia Atlas <[email-masked]>
Date: Tue, 5 Apr 2016 20:39:06 -0400

> the WG rather than the people drafting the charter?

The WG does the work the charter specifies.   It's a negotiation process
between the AD, proponents, and future WG chairs.

The link metric work should be called out separately and done so it can
also be reused by other protocols,  depending on stability requirements.

Alia _______________________________________________

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 05 Apr 2016 23:20:42 -0300

>> But I'm not sure it belongs in the charter -- shouldn't that be decided
>> by the WG rather than the people drafting the charter?

> between the AD, proponents, and future WG chairs. 

Clear.

> also be reused by other protocols, depending on stability requirements. 

So a Babel WG would only specify what properties a metric MUST have for it
to be suitable to be used by Babel?

-- Juliusz