65-node simple mesh test (and counting... ;-)

[C. Scott Ananian]

On Fri, May 9, 2008 at 10:57 AM, Marcus Leech <mleech at nortel.com> wrote:
> I'd be *very* interested to compare the distribution on a wired network.
> It seems to me that given
>  the broadcast model, everybody should see everybody else in much
> shorter time than the 55 seconds
>  shown in the outlying cluster on that graph.  For example, if you
> plugged all of those 65 Xos
>  into a wired network (100Mbits/sec), then if the "convergence time"
> shrinks by roughly a factor
>  of two (100Mbits vs 54Mbits), then we know that the wireless
> networking stuff on the XO is
>  basically functioning correctly.  If, however, the convergence time
> becomes *very* much shorter
>  on a wired network (let's say by a factor of 5 or more), then
> something is likely wrong with
>  the 802.11 goop on the XO.

The common, but erroneous, assumption is often made that a wireless
network is just like a wired network, but with the wires removed.

In actual practice, wireless networks are fundamentally different
beasts.  Let's start with the broadcast speed: on a switched wired
network, broadcasts happen at the same rate as all the rest of the
traffic: if you've got a 100Mb ethernet, your broadcasts happen at
100Mb.  Since a wireless network is a shared (not switched/routed)
medium, broadcasts must occur at the fastest rate of the slowest
connected machine.  Since a wireless network doesn't actually provide
any means of enumerating all the connected machines, broadcasts happen
at 1Mb, regardless of the maximum speed of the sender.

On a wired network, if you were successful in sending a packet the
probability is very high that everyone in your local network received
that packet.  For older ethernet networks, this was because
collision-detection told you with high likelihood whether anyone
failed to hear it; for modern hi-speed ethernets this is because your
'switch' is much more akin to a router, and has all sorts of smarts
under the hood to try to prevent your packets from being dropped.

On a wireless network, broadcasts are successfully received with much
lower probability.  RF is mysterious and magical, and all sorts of
connection asymmetries, near-field effects, and radiation lobe
patterns conspire to make it unlikely that *everyone* can hear you
equally at once -- and then you get into remote collisions and other
mechanisms that make you unaware that not everyone heard you.  And
there is not 'ack' mechanism for 802.11 broadcast.

On an access point network, this problem it mitigated somewhat: you're
really not broadcasting directly to everyone else, you're sending your
broadcast to the AP, and the access point is relaying it to everyone
else.  You still don't get any acks, so you've got less reliability
than wireless unicast: you packet can get lost on the way to the AP,
and then of course the packet can disappear on its way from the AP to
everyone else.  But at least the number of paths is limited.

On a mesh, however, everyone who receives a broadcast then turns
around and repeats it to everyone around it who might not have heard
it the first time, for a particular TTL.  In theory this improves
reliability of broadcast in a dense network, since I've got three or
so chances to hear the packet, but in practice the vast volume of
traffic generated makes broadcast much much less bandwidth efficient
and increases the probability of collisions a lot.  On a sparse
network, your probability of receiving the packet is even worse: if p
is single-hop probability of reception, a node N hops away has
something like a p^N chance of successfully receiving the packet.

These are pretty much fundamental physical limitations of wireless
networks.  Attributing it to "802.11 goop" obscures the real issue.
The question ought to be: are there algorithms capable of performing
effective discovery and presence distribution giving the realities of
wireless and mesh networks?  Poly's work attempts to prove by example
that the answer is "yes"; there may well be other algorithms that also
work well on these networks.  I'm not convinced that, say, DHCP is an
algorithm that will work effectively on a wireless or mesh network.
(Note that successful DHCP on 802.11abg often retries multiple times,
which is an early sign that it's reaching its limits.)
 --scott

-- 
 ( http://cscott.net/ )