[Olsr-dev] Multipath routing in OLSRD

[Hannes Gredler]

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