[Olsr-dev] Freifunk Testing

[Henning Rogge]

Am Montag 16 Juni 2008 14:25:28 schrieb elektra:
> Henning Rogge wrote:
> > There are two main problems with the OlsrV1 RFC and one main problem
> > with the old olsrd (pre version 0.5) routing agent.
> >
> > The first problem of OLSR (as presented in the RFC) is the routing
> > metric. A hopcount metric is a great idea in "nearly no loss"
> > networks, and it works very well in simulated wireless networks as
> > long as you use a "Two-Ray ground" model for layer 1 (standard model
> > in the NS-2 simulator). In reality hopcount metrics try to use the
> > longest (and worst quality !) links and break down within moments. I
> > discovered it myself when I did some simple simulations with a more
> > realistic layer-1 model.
>
> True. Hence the modified ETX algorithm was introduced with 0.4.8. at the
> end of  2004.
Fortunately there were a lot of progress in routing metrics the last year, so 
we plan to add better routing metrics in the next version of olsrd.

> > The second problem is that the MPR algorithm has no redundancy. You
> > hope that one node will receive your and all two-hop neighbor nodes
> > will receive the retransmission. So you should integrate a little bit
> > more intelligence in choosing your "relays". New routing metrics try
> > to integrate the size of the "collision domain" into their alogrithm
> > because of similar reasons. Sending it through all neighbors will be a
> > desaster in dense networks.
>
> MPRs are all about reducing TC redundancy. Locally and network wide. It
> is miserable in reducing protocol overhead. Stability-wise it is even
> worse.
MPR was implemented to reduce routing traffic, but it also reduce TC 
redundancy. So you need some good tradeoff, both extreme values (no MPR or no 
redundancy) is possible a bad idea.

> > The problem with the old olsrd implementation was that it performed
> > (in terms of CPU usage) horrible. This results in packet drop in
> > larger networks.
>
> Sure, sure. But at 30% CPU load the reason for loops was somewhere else...
The olsr 0.4.10 ETX implementation is instable. It use message sequence 
numbers and has no "time normalization" to prevent fast changes in ETX 
through a TC flood.

> > I have read the BATMAN Draft you send to the IETF (not the IEEE ;) )
> > and I have to say BATMAN has one mayor problem too. BATMAN has no
> > "tuning parameters", you have one timer value and I don't see many
> > possibilities to integrate a good routing metric. You just hope that
> > the "flood the hellos and backtrack them" will produce a good routing
> > strategy. You cannot even use the bandwith of a link for routing
> > decissions, because the bandwith cannot be propagated. So my question
> > is where does the BATMAN plan to go from the current state ?
>
> You are right. The draft is about Batman Mark III, while we are using
> Mark IV now, which does carry a metric.
So at best the draft is outdated... is there another draft for v4 ?

> > Fish-Eye algorithms are used to keep the traffic low, but they
> > introduce ADDITIONAL possibilities for routing loops (at the edge of
> > the fish-eye domains). So it's a tradeof between traffic problems and
> > routing update problems.
>
> Highly unlikely, because fish-eye domains overlap. Loops occur amongst
> adjacent nodes, usually involving two or three nodes. Go ahead and
> experiment - disable Fisheye and reduce MPRs redundancy  to a value
> where it is actually doing something - in a large scale deployment such
> as Vienna, and observe the results.
The problem can happen at the edge of a fisheye zone. You get an "update 
border" at this point because some packages are not flooded to the edge of 
the network.

Because of the fast changing etx metric this could produce a routing-loop.

> > If you have problems with payload suppressing routing packets you have
> > to use traffic shaping or priorization, Just creating more routing
> > packets might make the situation even worse.
>
> The problem is radio interference, rather than protocol traffic
> prioritization.
If you use traffic priorization (get routing traffic out first) and maybe even 
shaping (reduce outgoing traffic to keep space for routing) this should be 
managable in sparse networks. At dense networks the ieee802.11 collision 
avoidance algorithm will be a problem, but there is nothing you can do about 
this (except using multiple frequencies to reduce interference).

> > And finally, judging the performance of an algorithm running with not
> > enough CPU power (because of inefficient code) is at least a little
> > bit suspect...
>
> Our recent tests have been performed on 800 MHz x86 CPUs in a 49 node
> grid, at 1-3 % CPU load.
I remember Sven-Ola running olsrd on a webcam with a 20 MHz CPU, so I don't 
think the recent implementation of olsrd has lot's of problems with CPU 
consumption. ^^

--------

Thank you for stopping this flame war and getting back to a technical topic.

Henning


*************************************************
Diplom Informatiker Henning Rogge
Forschungsgesellschaft für
Angewandte Naturwissenschaften e. V. (FGAN) 
Neuenahrer Str. 20, 53343 Wachtberg, Germany
Tel.: 0049 (0)228 9435-961
Fax: 0049 (0)228 9435-685
E-Mail: (spam-protected)
Web: www.fgan.de
************************************************
Sitz der Gesellschaft: Bonn
Registergericht: Amtsgericht Bonn VR 2530
Vorstand: Dr. rer. nat. Ralf Dornhaus (Vors.), Prof. Dr. Joachim Ender 
(Stellv.)