0000003: MPR selection issue also in 0.5.5? - OLSR.org bugtracking

Mantis Bug Tracker

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

ID

Project

Category

View Status

Date Submitted

Last Update

0000003

OLSRd

Core

public

2010-05-13 09:03

2010-06-14 10:59

Reporter

icrespo

Assigned To

Henning

Priority

normal

Severity

feature

Reproducibility

always

Status

assigned

Resolution

open

Platform

x86, PPC

OS

Fedora 9 / PPC Linux (custom)

OS Version

Product Version

0.5.6-r8

Target Version

0.7.0

Fixed in Version

Summary

0000003: MPR selection issue also in 0.5.5?

Description

My research group is currenly running OLSRd 0.5.5 on a really simple testbed scenario (see below), but cannot get it to converge when setting TcRedundancy=1 and MPRCoverage=1.

I have read some remarks as to MPR selection being utterly broken in latter (0.5.6) releases (and, as a matter of fact, the latest 0.5.6 daemons would even refuse to start with TcRedundancy=1) , but I'm not sure whether 0.5.5 suffers from the same issue.

Our scenario is like this (all nodes are daisy-chained trough dual wired Ethernet NICs - no VLANs or anything fancy):

           192.168.1.0/24 192.168.2.0/24 192.168.3.0/24
[NODE 1] ------------------ [NODE 2] ------------------ [NODE 3] ------------------ [NODE 4]
dummy0: 1.1.1.1 dummy0: 2.2.2.2 dummy0: 3.3.3.3 dummy0: 4.4.4.4
eth0: 192.168.1.1 eth0: 192.168.2.2 eth0: 192.168.2.3 eth0: 192.168.3.4
                            eth1: 192.168.1.2 eth1: 192.168.3.3


We listed the dummy interfaces first in the olsrd.conf files, so that they will become the main addresses. This allows for easy identification of links in the topology databases.

Al nodes have willingness set to 3 (hard-coded),

Other than that, we are running the daemon in fully "RFC-compliant" mode, i.e., no Link Quality, no fish-eye, no nothing. We are also using the recommended timers for Ethernet in all nodes.

Now, the MPR election process seems to work as expected:

   - NODE 1 chooses NODE 2 as MPR to reach everybody and has no MPRS.
   - NODE 2 chooses NODE 3 as MPR to reach NODE 4 and has NODE 1 and NODE 3 as its MPRS.
   - NODE 3 chooses NODE 2 as MPR to reach NODE 1 and has NODE 4 and NODE 2 as its MPRS.
   - NODE 4 chooses NODE3 as MPR to reach everybody and has no MPRS.

With TcRedundancy=2/3, we see that the topology sets of all the four nodes get populated with a total of six uni-directional links, accounting for the three physical links, i.e:

   1.1.1.1 -> 2.2.2.2
   2.2.2.2 -> 1.1.1.1
   2.2.2.2 -> 3.3.3.3
   3.3.3.3 -> 2.2.2.2
   3.3.3.3 -> 4.4.4.4
   4.4.4.4 -> 3.3.3.3

(Though we I that one of the LSAs at either end is redundant?)

When this happens, all routes get inserted into the kernel and thus we attain full end-to-end connectivity.

However, when we set TcRedundancy=1, we observe that the topology sets of the nodes at either end (NODE 1 and NODE 4) does not adquire one of the links from the opposite end.

E.g.: at NODE 1 we get:

   1.1.1.1 -> 2.2.2.2
   2.2.2.2 -> 1.1.1.1
   2.2.2.2 -> 3.3.3.3
   3.3.3.3 -> 2.2.2.2
   4.4.4.4 -> 3.3.3.3

   (notice that 3.3.3.3 -> 4.4.4.4 is missing)

Wereas at NODE 4 we have:

   1.1.1.1 -> 2.2.2.2
   2.2.2.2 -> 3.3.3.3
   3.3.3.3 -> 2.2.2.2
   3.3.3.3 -> 4.4.4.4
   4.4.4.4 -> 3.3.3.3

   (2.2.2.2 -> 1.1.1.1 is missing here)

NODES 2 and 3 get the same six LSAs as before.

In this situation, NODE 1 doesn't get a route to reach NODE 4 and NODE 4 doesn't get a route to reach NODE 1.

My questions are:

   - Is 0.5.5 also broken with regards to MPR selecion and forwarding?
   - If so, what is the latest release that would run fine and in full compliance with RFC-3626?
   - Are there any plans to have the algorithm fixed anytime soon?

Many thanks in advance and sorry for this lengthy post ;).

Steps To Reproduce

Just try the above scenario with MPRRedundancy=1 and TcRedundacy=1.

Additional Information

Feature request: Rewrite MPR selection algorithm as soon as OLSRv2 databases are available

Tags

No tags attached.

Relationships

child of

new

OLSR.org does not support OLSRv2

Notes
(0000004) Henning (administrator) 2010-05-13 09:59	According to my knowledge MPR selection is broken at to places in the whole 0.5.x tree (and maybe for 0.4.x too). First the dijkstra implementation of 0.5.x cannot handle edges between two nodes of the topology graph that were announced by only one side of the edge. This blocks the usage of MPRs. The second problem is that the OLSR basic neighbor data structures (as defined in the OLSR RFC) are not designed for linkquality based MPR selection. OLSR stores information about two-hop neighbors per node, not per interface. This means the LQ-based MPR cannot store the LQ-costs to two-hop neighbors correctly, which makes the whole implementation instable. The dijkstra in the master branch can handle "asymmetric" announced links, but still lacks the necessary datastructures for a well designed MPR selection. The 0.7.0 release will get reworked datastructures to handle OLSRv2, which will also allow MPR selection.

(0000005) icrespo (reporter) 2010-05-14 14:33	All right, your explanation summarizes the problems I'm finding quite accurately. Thanks for taking the time to explain it to me. Looking forward to 0.7.0 ;).

Issue History
Date Modified	Username	Field	Change
2010-05-13 09:03	icrespo	New Issue
2010-05-13 09:59	Henning	Note Added: 0000004
2010-05-13 09:59	Henning	Assigned To	=> Henning
2010-05-13 09:59	Henning	Status	new => assigned
2010-05-13 10:00	Henning	Product Version	=> 0.5.6-r8
2010-05-13 10:00	Henning	Target Version	=> 0.7.0
2010-05-14 14:33	icrespo	Note Added: 0000005
2010-06-14 10:41	Henning	Relationship added	child of 0000001
2010-06-14 10:59	Henning	Severity	major => feature
2010-06-14 10:59	Henning	Additional Information Updated	View Revisions

Copyright © 2000 - 2010 MantisBT Group