[Babel-users] Unscheduled Unicast Hellos: some background on 802.11 link quality estimation

[Juliusz Chroboczek]

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 at 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