[olsr-dev] Improvements in the algorithm

onelektra (spam-protected)
Thu Nov 17 13:21:13 CET 2005

Hi Dan -

thanks for your comprehensive post. Olsr doesn't scale to a large level 
and it has a flat subnet hierarchy that doesn't scale to a high level. I 
agree. I don't think we have a point of argument here.

The free networks community needs running code - so if someone comes up 
with a promising solution like DART and code that we can run on our 
machines - we are really glad to test it. That was the reason why we 
started to use mobilemesh first and later olsrd. Olsrd looked very 
promising - not because of the fancy algorithms but because there were 
several implementations supporting more than one OS.

We learned that many ideas that have been considered as optimizations in 
olsr harmed the stability of the ad-hoc network. At the moment we have 
disabled the MPR-feature and the hysteresis. We introduced the 
LQ-Extension and currently we are testing a fisheye-algorithm to allow 
TC broadcasts at higher frequency to avoid routing loops.

I'm tempted to rant at the academic approach to research mesh routing. 
In my opinion the scientific aproach spins far too much about the 
question: Is our algorithm scalable? How can we reduce protocol 
overhead? Rather than: Does it work in a wireless network full of 
collisions, lost packages and interference? I will shamelessly smile at 
any researcher that comes up with an new idea that finds shortest path 
routes at best ;-)

To me they seem to be inebriated by the visons popping up when they say 

Our approach is: Practise on a small level. Worry about scalability 
later as the network grows. The Berlin mesh now has more than 100 
interfaces running olsrd, yet there is no problem with the size of the 
network. We see the CPU-load grow on our WRTs and wonder when we really 
come into trouble. Sure it will be a problem in the not so far future as 
the network grows at high pace....

Stability of our routes when links get saturated - that is the challenge 
at the moment for us. Not avoiding overhead to improve scalability.

The authors of the INRIA olsr draft worried so much about avoiding 
overhead that they forgot the fact that with all the new introduced 
gears, bells and whistles the effort to synchronize this information 
would grow. Since the algorithm depends on synchronized information they 
introduced new instability. And that is where the real problems come in. 
You already adressed that in your previous post.

But what does DART do to address the real life issues of a wireless 
network? I can see nothing addressing this. It is all about theoretical 
ideas to grant scalability and reduce overhead. I'm sure it scales well 
in a simulation. And it may scale well on a wired network. But I'm also 
unsure that it will do anything useful in real life aka ad-hoc mesh. To 
me it seems it is just another academic idea in the academic competition 
about scalability. Still I have seen no large scale mesh running 
successfully with a theoretical protocol that was solely tested in 
simulations. I see they are going to deploy a real life testbed. I'm 
looking forward to a frank report what they learn when they move from 
the simulation to a real life scanario.

I don't say that we don't have to address the flat subnet hierarchy. We 
definetly have to do that as our community networks grow. This is an 
issue and the ideas in DART could be inspiring. And olsrd will of course 
not be able to address this. But it may do its best within a small 
subnet of 200 nodes full of self-generated wireless interference and 
collisions, other networks operating on the same channel, microwave 
ovens and 10 different wireless chipsets and their often buggy drivers.

If olsr is not able to provide a stable subnet of at least 100 nodes 
under the conditions of link saturation I will drop it and look for 
something new. I'm looking forward to the results of the 
LinkQualityFishEye mechanism that was implemented last night :-)

c u elektra

> Here's some light reading material:
> DART Poster - a nice easy summary of the project
> http://www.cs.ucr.edu/~jeriksson/dartweb/DART_Poster_ICNP_03.pdf
> DART Project Homepage:
> http://www.cs.ucr.edu/~jeriksson/dartweb/
> Scalable Ad Hoc Routing: The Case for Dynamic Addressing - the in-depth
> paper outlining the specifics of the protocol - presented to INFOCOMM 2004
> http://www.cs.ucr.edu/~jeriksson/dartweb/DART_INFOCOM_04.pdf
> Cheers,
> Dan
> -------------
> View my blog:
> http://freenetjazz.blogspot.com
> _______________________________________________
> olsr-dev mailing list
> (spam-protected)
> https://www.olsr.org/mailman/listinfo/olsr-dev

More information about the Olsr-dev mailing list