Mesh Potatos and OLPCs?

[Michael Stone]

On Wed, 23 Mar 2011 at 20:47:44 -0400, Ed McNierney <ed at laptop.org> wrote:
> While I am not familiar with the Mesh Potato, I have spent some time trying to
> figure out whether wireless mesh networking is really as hard as the OLPC
> universe seems to find that it is.

tl;dr: Mesh Potatoes might make decent APs for XOs but physical- and
802.11-level constraints will probably prevent them from succeeding in the
densely packed, radio-congested classroom environments where the XO-1's
draft-802.11(s) implementation presently fails.

See below for the gory details.

> I have come to believe that both wired and wireless mesh networks are really
> doing pretty well out there in the world, *provided* the nodes are immobile, or
> relatively so.

The keys to success seem to be "unicast", "immobile", "sparse", "proactively
routed", "carefully sited", "actively managed", and "better antennas".

> The examples you point to seem to fall into the "immobile wireless" category,
> and I think one is likely to find reasonable success in that field.  And I
> don't mean *really* immobile, but rather "don't move about very much".  The
> wireless multi-room music systems from Sonos, for example, seem to use wireless
> mesh pretty successfully, but the nodes are pretty stable.  And they don't get
> very dense (you don't put 30 sets of stereo speakers in one room).
>
> I have not found any examples of either (a) dense wireless mesh or (b) highly
> mobile wireless mesh.  In case (a) I assume that is normally not a problem, so
> it's not being solved.  In case (b) one encounters the classic OLPC mesh
> problem - 50 laptops scattered about in children's homes at night all want to
> act as mesh nodes, while those same 50 laptops all go into the same classroom
> the next day where they DON'T want to all act as mesh nodes (i.e. they create
> case (a)).  I don't know of anyone who has successfully solved that problem,
> other than by the less-than-satisfactory route of giving the users a switch and
> expecting them to turn mesh on and off as they move.
>
> So I believe many people are having successes with relatively static wireless
> mesh networks, but I also believe that no one is having success in the scenario
> OLPC has always wanted to support.  If my latter perception is wrong I would
> love to know of a counterexample (using any hardware, not just XO laptops).

--8<-- (the gory details) --8<--

Here's what I've learned in the last two years, divided into three sorts of key
points, about why this problem is actually hard:

   a) the media access control algorithm implemented in the XO-1 mesh is a
      jazzed-up version of the 802.11 Distributed Coordination Function (DCF)
      [1]

   b) the 802.11 DCF was analyzed [2] from first principles, with simulations,
      and with physical measurements at MIT in 2001

   b) this choice of MAC algorithm, independent of /all/ higher-level protocol
      considerations, governs the fundamental behavior of the network, and

   c) the from-first-principles results, the simulations, and the experimental
      measurements cited all agree that per-node capacity:

         1) is bounded above by O(n^-0.5) (with annoyingly small constants)
         2) is inversely proportional to node density
         3) is highly sensitive to network congestion

These physical constraints are exacerbated by three sources of broadcast:

   i)   layer 2 route selection, where routes expired every ~5-15
        seconds to cope with a rapidly changing radio environment

   ii)  DHCP broadcast, (and in other designs, IPv6 router advertisements, and
        IPv6 duplicate address detection)

   iii) flood-fill broadcast implementations of IP-level multicast, which was
        primarily used by mDNS and Salut

and by two differences between ad-hoc broadcast and infrastructure unicast,
which are that

   iv)  broadcasts must be sent at a Supported Basic Rate [e.g., of 1 Mbps]
        instead of at the full Transmit Rate [e.g., 54 Mbps], and

   v)   broadcasts are not acked, which forces higher-level protocol retransmit
        timers to fire more often, thereby triggering more broadcasts.

Together, these facts appear to me to be sufficient to explain why the OLPC
XO-1's draft 802.11(s) implementation exhibits the behavior we've all observed:
i.e., tantalizing possibilities in lab experiments with small numbers of nodes
in quiet radio environments and congestion collapse in school-like settings.

Regards,

Michael

[1]: http://standards.ieee.org/getieee802/download/802.11-2007.pdf
[2]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.6218