Subject: [babel] Unscheduled Unicast Hellos: some background on 802.11 link quality estimation

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 20 Jun 2017 14:55:16 +0200

Dear all,

Here's a little bit of background on WiFi link quality estimation.  Please
read at least the conclusions at the end.

On networks comprising WiFi links, it is essential to perform link quality
estimation.  Consider the following topology:

      *     *     *
      |     |     |
  ----A-----B     C

Here A is your ISP-provided CPE, with a shitty WiFi interface.  B is the
nice router in your living-room, which is connected by Ethernet to A.
C is the extra WiFi router with a big antenna that you put in your garden
shed after your daughter complained about poor WiFi coverage in her treehouse.

The route A---B...C has little packet loss, due to the nice WiFi
interfaces in B and C.  Unfortunately, A and C tend to associate, and if
the routing protocol treats all wireless hops as equal, then the lossy
route A...C is preferred to the almost lossless route A---B...C.  This is
not a theoretical argument -- it was a big problem with the first mesh
protocols in the early noughts (Google "gray zones mesh routing").  The
slogan is "shortest-path routing is worst path routing".

The (automated) solution is to measure link quality.  Doing this usefully
requires taking two facts into account:

 1. 802.11 performs ARQ on unicast frames, but not on multicast frames;
 2. 802.11 uses adaptative rate control on unicast frames, but not on
    multicast frames.

There are two approaches:

 A. send periodic multicast frames and measure multicast loss.  Due to the
    lack of ARQ and the lack of rate adaptation on multicast frames, this
    provides reproducible and moderately useful results, but converges
    very slowly.  ETX is the simplest useful algorithm.

 B. send periodic unicast frames and use the information from the
    lower-layer rate controller (Minstrel in the case of the ath9k driver
    on Linux).  This converges very fast given sufficient unicast traffic,
    but tends to provide useless results on links with little unicast
    traffic (e.g. links not chosen by the routing protocol).

Babel uses approach A, just like OLSR-ETX.  ETX has some flaws (it tends
to treat all lossless links as equal, whatever the rate chosen for unicast,
and causes a slight feedback loop, leading to moderate routing
instability), but it is simple to implement and works pretty well with
Babel (which deals rather well with instabilities).

Approach B is tricky to implement, since it requires interacting with the
WiFi driver at a very low level.  Nonetheless, there are at least two
implementations of routing protocols that use approach B: BATMAN-adv and
Lamparter's variant of IS-IS.  The BATMAN-adv people do not speak about
experimental results (at least to me), but Battlemesh experiments have
reproducibly shown disappointing performance [1,2].  Lamparter's
experiments [3,4] indicate that his link-quality algorithm converges much
faster than ETX, but tends to mis-calculate the metric of idle links (due
to too little feedback from unicast frames -- this might or might not be
due to the lack of Unicast Hellos).

[1] http://docs.battlemesh.org/v8/1-the-mesh-of-death-adversity.html#results
[2] https://www.irif.fr/~jch//software/babel/battlemeshv10.html
[3] David Lamparter, private communication in a bar.
[4] Mikael Abrahamsson, posting to homenet@ietf that I'm too lazy to look up.

Now the conclusions relevant to the Unicast Hello discussion:

  1. Approach A is the one that is known to work reasonably well, and it
     MUST NOT be broken.  This means making it possible to use Multicast
     Hellos for link-quality estimation without interference from Unicast
     Hellos -- hence the requirement for unscheduled Unicast Hellos.

  2. While to my knowledge nobody has been able to make approach B work
     reliably, we do not want to prevent people from experimenting with it
     in Babel -- hence the desire for useful Unicast Hellos.

Thanks for your attention,

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 20 Jun 2017 15:36:31 +0200

> [4] Mikael Abrahamsson, posting to homenet@ietf that I'm too lazy to look up.

Mikael says:

    https://www.ietf.org/mail-archive/web/homenet/current/msg06322.html
    https://www.ietf.org/mail-archive/web/homenet/current/msg06360.html

  is my posting I believe you're looking for.

Thanks!

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Tue, 20 Jun 2017 10:26:13 -0700

Juliusz,

Thanks for the explanation, it makes sense to me.
It also helped me realize that my text about combining
the Unicast and Multicasts costs is incorrect. I think a lot
of what you wrote in the previous email would be a valuable
addition to the spec. One could imagine using Multicast + ETX
to determine the loss rate and unicast + driver information to
distinguish between different lossless links. Can you provide text?

David

> On Jun 20, 2017, at 06:36, Juliusz Chroboczek <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 20 Jun 2017 20:35:59 +0200

> Can you provide text?

Yes, I will do.  Please focus on specifying the on-the-wire bits, I'll
take care of the appendix.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Tue, 20 Jun 2017 13:33:14 -0700

> On Jun 20, 2017, at 11:35, Juliusz Chroboczek <[email-masked]> wrote:
> 
>> Can you provide text?
> 

Sounds good to me.

David Schinazi

---

From: Ruben <[email-masked]>
Date: Tue, 20 Jun 2017 22:41:06 +0200

Hello Juliusz,

> Am 20.06.2017 um 14:55 schrieb Juliusz Chroboczek <[email-masked]>:
> 

This is not entirely true, since hostapd is able to send multicast as unicast-frames.

Best regards 

Ruben

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 21 Jun 2017 00:06:33 +0200

> This is not entirely true, since hostapd is able to send multicast as

And this will cause Babel's link-quality estimation to yield incorrect values.

Dynamically computed metrics are an open area of research, and one that is
sadly neglected by the scientific community.  I believe that it is
important, but it is very difficult to publish in that area (FWIW, our
paper about the RTT metric was rejected twice).

ETX is an elegant hack that uses the fact that 802.11 multicast isn't
subject to ARQ.  As you justly note, Ruben, this assumption can fail in
edge cases, and there's nothing that can be done about it.  The obvious
solution would be to have explicit cross-layer signalling, as in the case
of Lamparter's variant of IS-IS.  Doing that right is not easy, and might
(or might not) require changes to the link-layer.

I'm personally interested in that area of research, and I'll probably have
a fair amount of funding in the near future.  However, since the area is
not fashionable, I cannot promise that we'll be able to publish.

-- Juliusz

---

From: Jehan Tremback <[email-masked]>
Date: Tue, 20 Jun 2017 15:55:44 -0700

I'm wondering... what if, in the hypothetical routing protocol "Babble",
one got rid of multicast hellos and ETX entirely, and routed using RTT
measured by unicast hellos. Wouldn't this take delays from ARQ'ed packet
loss into account have results somehow similar to ETX?

On Tue, Jun 20, 2017 at 3:06 PM, Juliusz Chroboczek <[email-masked]> wrote:

> Babel-users mailing list
> [email-masked]
> http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/babel-users
>

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 21 Jun 2017 01:05:59 +0200

> measured by unicast hellos.

Interesting idea.

I think that's a perfectly legitimate implementation of Babel with Unicast
Hellos: we're leaving the cost computation algorithm unspecified, ETX is
just an implementation suggestion in Appendix A.

> Wouldn't this take delays from ARQ'ed packet oss into account have
> results somehow similar to ETX?

802.11 has a default ARQ timeout of 1µs, which is likely to be drowned by
congestion.  I guess the only way to find out is to try it out.  You'll
need to change the packet format of the ETX extension, which only has 1µs
granularity.

-- Juliusz