[Olsr-users] using dijkstra for route calculation

[L. Aaron Kaplan]

On Sep 20, 2010, at 3:40 PM, Adrian Schwartz wrote:

> I was wondering,
> how bad is it using dijkstra for full network routing calculation?
> lets assume that I have 100 nodes and I need to recalculate the path every second?

By now deadly efficient!
This was a big part of the OLSR-NG optimization work. Mainly Hannes optimized Dijkstra until it was so efficient that OLSRd only took a few percent CPU load on a small 200MHz embedded Linksys device which was calculating the shortest path in a up to 1000 node network.

Right now there is a google summer of code project (we did not test it's results yet!) to have an incremental Dijkstra calculation (i.e.: only re-calculate the regions where things changed a lot)

So, don't worry about CPU load right now on OLSR. We scale!


a.

> On Mon, Sep 20, 2010 at 1:58 PM, L. Aaron Kaplan <(spam-protected)> wrote:
> 
> On Sep 20, 2010, at 1:18 PM, Adrian Schwartz wrote:
> 
> > So how does the routing algorithm works?
> > shortest path?
> >
> yes
> 
> 
> -- 
> Olsr-users mailing list
> (spam-protected)
> http://lists.olsr.org/mailman/listinfo/olsr-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-users/attachments/20100920/41ff87b7/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: This is a digitally signed message part
URL: <http://lists.olsr.org/pipermail/olsr-users/attachments/20100920/41ff87b7/attachment.sig>