[Olsr-dev] Multipath routing in OLSRD

[Ralf Lübben]

Am Dienstag 03 März 2009 18:56:14 schrieb Hannes Gredler:
> Ralf Lübben wrote:
> > I not only will insert paths with equal cost, but also paths with
> > different costs. (What cost is acceptable is  still a open question!)
>
> irrespective if you do equal cost or less then best cost,
> in any case you need first put in some work in the RIB implementation
> to make sure your route ends up in the kernel with all the nexthops.

Yes, I will start with the routing algorithm first and hopefully the RIB 
implementation isn't a big deal.

>
> > The algorithm I want to use needs information about all nodes on a
> > shortest path, after the shortest path was calculated.
> > E.g:
> > After olsr_spf_run_full() was executed I need the information that the
> > shortest path between node N1 and N5 is: N1 -> N3 -> N8 -> N5.
>
> perhaps you should start differently and think about keeping the cost
> of non-best paths while doing the path relaxation olsr_spf_relax().
I decided to use the algorithm from "Finding the K Shortest Loopless Paths in 
a Network" by Jin Y. Yen.
The algorithm needs the knowledge about all nodes on a shortest path :-(

>
> > Is this information easy accessable? I couldn't find the
> > variable/datastructure which can provide me this information easily.
>
> have a look at olsr_spf.c - the relevant data structures it operates on
> are all in tc_set.h (tc_entry is a node and tc_edge is a link).
>
> its a basic (albeit) speed tuned dijkstra implementation
> which operated in place in the topology database.
>
> startup gdb in a 4 router VM setup and turn on debug logging
> then you learn a lot how it works.
I already have a setup with up to 12 virtual nodes which works fine. In general 
I understood the code in olsr_spf.c and tc_set.h, but I think it isn't 
possible to trace back the shortest path from a tc_entry respectively a entry 
in the path_list.
I think I will need a new variable in tc_entry which stores the shortest path 
to this node.
But maybe I'm wrong on that.

Ralf

>
> /hannes