Mesh Potatos and OLPCs?
michael at laptop.org
Thu Mar 24 01:03:41 EDT 2011
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)
b) the 802.11 DCF was analyzed  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.
More information about the Devel