Network association algorithm

Dan Williams dcbw at
Wed May 2 08:03:58 EDT 2007

On Wed, 2007-05-02 at 07:27 -0400, Walter Bender wrote:
> Wad,
> Thanks for writing this up. A few additional comments:

More things we need to think about.

a) What was the point of doing scans for only 1, 6, 11 again?  We're
scanning for APs on all channels in the infrastructure AP stage anyway.

b) Where do we go of DHCP to the infrastructure AP fails?

c) Where do we go if the AP drops association?  After 1 minute?  After 1

d) What happens when we get an auto-ip address at home (no MPP) and
carry the laptop to school?  Require some manual toggle (like the mesh
circle now) to re-start the whole process?

> (1) We need to characterize the amount of time necessary at each step
> and--at some point--tune the algorithms. For example, we probably
> don't want to wait 30 seconds for each attempt at DHCP.
> (2) We need to expose the status at all steps in the UI. We also
> probably want to enable the child to jump into the flow at different
> points from the UI, such as going directly to search for AP or forcing
> back to the search for a school server.

We need to expose status, but I've got a few reservations.

First, this is a huge state diagram.  Simpler is almost always better.
Much of it is esoteric 802.11 stuff that nobody should ever have to care
about (DHCP vs. static vs. autoip, who cares?)

In the end, all we care about is "can I get to the internet", "can I get
to the school server" or "can I see my friend".  _That's_ what matters.
Obviously technology isn't perfect and things will go wrong, and that's
where the exposure of status comes in.  If stuff is not working we need
to show that it's not working so it's not a black hole.

But I'd argue that showing status should take general forms like "trying
to mesh with a school server" or "trying to connect to an access point".

> (3) We need to determine the most efficient way to know if the state
> of the mesh has changed such that we should reenter the process. E.g.,
> what if you move away from the school server and you had been an MPP.
> Now you have to look for an MPP... There are many anomalous cases we
> need to consider.
> (4) It was proposed that we dedicate one of the LEDs to indicate a AP
> connection and the other to indicate an MPP connection.

Need to talk to Marcelo about this again to make sure that we can
control the behavior of the LED, not just what LED corresponds to what.

> One thing we didn't discuss at all and is probably something we don't
> do for the time being is some sort of gain control. If we have a
> crowded classroom, I assume it would be better to turn down the volume
> on the radios so that everyone is not shouting, but just quietly
> talking to their neighbors. Maybe we want to add an outer loop to the
> whole thing where you start off whispering and gradually crank up the
> volume until you have a connect?

Wow...  Let's not _add_ to the diagram if we can help it.  The larger
the state diagram, the more spots for things to (a) go wrong, (b) us to
forget something, and (c) things to fall through the cracks.  Simpler ==

If there's a lot of nodes around us, and we're meshed, and the nodes
have a pretty high SNR, we could just dial down the transmit power or
something.  It can be pretty dynamic and probably orthogonal to the
connection process.


> -walter
> On 5/1/07, John Watlington <wad at> wrote:
> >
> > Dan,
> >    I'm pretty sure that the attached flowchart documents the network
> > association algorithm developed in today's meeting.
> >
> > There are four end conditions, in rough order of desirability:
> > 1. The XO finds an established MPP (w. DHCP), and uses it for
> > internet access.
> > 2. The XO finds an AP, and becomes an ad-hoc MPP (no DHCP)
> > 3. The XO finds an ad-hoc MPP (no DHCP), and uses it for internet access
> > 4. The XO finds no AP nor MPP, and becomes a mesh node on channel 1
> > w. no internet access
> >
> > It has already been pointed out that for optimum performance, we will
> > eventually want to
> > randomly prefer end condition 3 over condition 2.
> >
> > Cheers,
> > wad
> >
> >
> > _______________________________________________
> > Devel mailing list
> > Devel at
> >
> >
> >
> >

More information about the Devel mailing list