[Olsr-dev] Modification to the MPR selection algorithm

Ayan Roy-Chowdhury (spam-protected)
Wed Jun 9 21:52:57 CEST 2010

>> We are implementing the Stable Path Topology Control (SPTC) algorithm
>> which selects the MPR set based on some link stability metric, instead
>> of the hop count. So the shortest path from a source to destination uses
>> links based on the stability metric, instead of the hop count.
> Just one question... do you want to change MPR selection (which is used for
> flooding OLSR packets) or the routes for the data.

At present, we want to change the MPR selection algorithm only. The 
route selection will still be based on shortest path in terms of hop 
count. However, the local view of the network will consist of nodes with
more stable links, and therefore, the shortest paths will be more stable.

>> We have not gone through all the source code - would greatly appreciate
>> if we can be directed to the relevant sections that will {affect | be
>> affected by} any changes to the MPR selection algorithm.
> If you want to affect the route of the traffic, just forget about MPRs and
> work on a better routing metric plugin. I would be happy to see postprocessing
> for ETX that gives instable links a "penalty" and stabilize the metric value
> with this.

Once we have the new MPR algorithm implemented, the next step will be
to change the route selection algorithm to find the optimal routes based
on most stable links (or some other metric). So we will run Dijkstra on
the weighted graph. But this will be possible only after the MPR 
selection algorithm is changed.

>> Also, from reading the default config file olsrd.conf.default.full, it
>> seems that the OLSR MPR optimization does not work in v0.6.0:
> The problem is that the dijkstra algorithm in 0.6.0 cannot handle tc_edges
> that are only announced by one of the nodes of the link. This means MPRs for
> selecting the subset which will be considered for sending traffic does not
> work.
>> Is there any patch for the above?
> I have been working on the master branch to get the dijkstra right, but there
> seem to be a few bugs left.

Would it be possible to get the fix assuming it does the job, despite 
bugs? To compare the overhead between the default OLSR implementation,
and the SPTC algorithm, it is necessary that TC redundancy is set to 0.

> I would advice to directly work on a routing metric plugin that outputs a more
> stable metric value. That would be a GREAT contribution for future OLSRd
> versions.

We are hoping that we will get to that point soon!


More information about the Olsr-dev mailing list