[Olsr-dev] Multipath routing in OLSRD
Tue Mar 3 19:17:59 CET 2009
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.
More information about the Olsr-dev