[olsr-dev] Improvements in the algorithm
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
> DART Project Homepage:
> Scalable Ad Hoc Routing: The Case for Dynamic Addressing - the in-depth
> paper outlining the specifics of the protocol - presented to INFOCOMM 2004
> View my blog:
> olsr-dev mailing list
More information about the Olsr-dev