[OLPC Networking] Path discovery sanity

[Ricardo Carrano]

On Tue, May 13, 2008 at 1:23 PM, C. Scott Ananian <cscott at cscott.net> wrote:

> On Mon, May 12, 2008 at 5:47 PM, Ricardo Carrano <carrano at laptop.org>
> wrote:
> > I just performed another test to demonstrate the relation of costs for
> each
> > PREQ and the occurrence of multihop paths.  More importantly, maybe, the
> > test also confirms that even with hop count as metrics, the multhop
> paths
> > will still form.
> >
> http://wiki.laptop.org/go/Path_Discovery_Mechanism:Sanity#Hop_count_will_indeed_reduce_it.2C_but_not_eliminate
> >
> > More on this soon.
>
> Perhaps we should seriously consider properly implementing the HWMP
> protocol, including the proactive routing components; a proper
> spanning tree would prevent these transient multihop paths in most
> cases.  It may also be worth comparing to a pure proactive approach
> such as OLSR, which is also permitted under 802.11s and may scale
> further than HWMP.  OLSR-based networks have been demonstrated at ~600
> nodes, although the nodes were not very mobile:
> http://www.olsr.org/?q=background.  In contrast, the author of the
> HWMP protocol only expects it to scale to 50 nodes (see attached).
>
> A reactive approach is much more sensitive to the loss of a single
> packet during route-finding; in a proactive approach we have a longer
> time period to converge on stable routes before we need to actually
> send a packet.  Hybrid approaches (such as the one specified in
> 802.11s but not actually implemented by OLPC) may combine the
> strengths of both.



I fear that in a proactive protocol, the overhead in a dense network will
also grow very fast.  It is believed that the virtue of the proactive
approach is that routes are there when they are needed, but this implies
that the nodes are not moving a lot.  That's why it is a successful choice
for WMNs. I am not sure if we have examples of this approach over MANETs (I
really don't know).

The algorithms to process the tables are also more expensive to implement, I
guess.

Also, as Pol pointed out somewhere, the proactive part of the hybrid
approach of HWMP is not exactly a complete table-driven algorithm like OLSR.
Though I feel that the Portal/Root Announcements would be really useful.

But, what I really believe is that we haven't reach the moment to judge our
design choices. We are just starting to do some tests that are not
contaminated by horrid bugs, that render everything inconclusive. I could
give you a lot of examples. One recent is #6589. Could we say that the
reactive approach was not working for us based on a failed implementation?

I feel that before we remove this bugs and optimize what we can, we should
stick to the plan. If we continue to test and optimize we'll soon know our
limits and mistakes. Please don't get me wrong, I am not suggesting that we
stoically resist to some bad decisions. I am just saying that we still don't
know if they were bad. ;-)

Cheers!
Ricardo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.laptop.org/pipermail/networking/attachments/20080513/e867913f/attachment.htm