[Olsr-dev] Multipath routing in OLSRD
Tue Mar 3 18:30:03 CET 2009
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.
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.
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 :-)
More information about the Olsr-dev