[Olsr-dev] Modification to the MPR selection algorithm

[Henning Rogge]

Am Mittwoch 09 Juni 2010, 20:13:56 schrieb Ayan Roy-Chowdhury:
> ** Apologies if the issues raised below have been previously addressed
> in the mailing list - we have missed them if so. **
> 
> 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.

> To achieve this, we are modifying the MPR selection algorithm in the
> OLSR implementation. The metric we use is ETX.
> 
> Our understanding is that, when ETX is used, the MPR set is computed in
> void olsr_calculate_lq_mpr(void) in lq_mpr.c, and not by the functions
> in mpr.c. -- Is this correct?
Yes and no.

mpr.c calculates the MPRs for hopcount... I think it works.
lq_mpr.c should calculate the MPRs for ETX. It does not work well for multi-
interface neighborhoods because the data structures of the neighbor-set are 
slightly wrong.

> 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.

> 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.

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.

Henning Rogge

-- 
1) You can't win.
2) You can't break even.
3) You can't leave the game.
— The Laws of Thermodynamics, summarized
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20100609/2d2cd2af/attachment.sig>