[Olsr-dev] Multipath routing in OLSRD

[Ralf Lübben]

I not only will insert paths with equal cost, but also paths with different 
costs. (What cost is acceptable is  still a open question!) 

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.

Is this information easy accessable? I couldn't find the variable/datastructure 
which can provide me this information easily.

Ralf 




Am Tuesday 03 March 2009 17:07:46 schrieben Sie:
> On Tue, Mar 03, 2009 at 04:41:18PM +0100, Ralf L??bben wrote:
> | On Tuesday 03 March 2009 16:30:32 Henning Rogge wrote:
> | > Am Tuesday 03 March 2009 16:18:07 schrieb Ralf L??bben:
> | > > Hi,
> | > >
> | > > I'm working on a multipath extension for olsrd, so far I decided to
> | > > implement a "k shortest path" algorithm in olsrd.
> | > > The algorithm is based on dijkstra, so I can reuse the existing
> | > > functions.
> | >
> | > So you plan to implement source-routing (OLSR use "hop-by-hop" routing)
> | > ?
> |
> | No, the routing should be normal IP routing.
> |
> | To enable multipath routing I think about to use "multiple routing
> | tables" and iptables to utilize the different paths which where
> | calculated before by the "k shortest path" algorithm
> |
> | Ralf
>
> well, then you do not need to change too much on the SPF algorithm side.
>
> what you need to do is:
>
> 1. change the RIB code such that it can manage
>    more than one next-hop.
>
> 2. the only SPF relevant change is that nodes with have an identical
>    cost are added to the next-hop list. see olsr_spf_relax() lines 225+
>    in contrast to just inheriting the upstream node next-hop, which
>    we do today.
>
>    keep performance in mind e.g. by doing some clever pointerwork :-)
>
> HTH,
>
> /hannes