The PAF-FPE Project

This is the website of the PAF-FPE project. A Marie-Curie project run by Leonardo Maccari in the period 2011-2014. I do not plan to update this website anymore, If you are interested in this project, you can find a description and a list of achievements in this short Executive Summary. In that pdf I will also update the publication list as the last papers get published.

Bug in MPR Selection, Omnet++, NS2, NS3

I'm now working on the integration of filtering strategies with the OLSR protocol, in order to exploit the knowledge of the topology to have more efficient filtering. Doing this, I had the intuition on some improvement on the choice of MPR nodes, but while working on it, I found a couple of bugs on the OLSR implementation of MPR selection in Omnet++ implementation, in NS2 and partly in NS3. I have reported the bug in the Omnet mailing list and it has been fixed, I will explain it also here so that other people that are using this code can be correct it (also in the NS3 community).

The original OLSR code comes from Francisco J. Ros and has been ported do NS3 (with some refactoring) and to Omnet++ (Inet package). That code contains two bugs, the first is a wrong iteration on the two-hop neighbors, the second is a comparison with a wrong data structure that makes a function useless. Using as a reference the original OLSR.cc from Ros Blog, starting from line 628 it happens that:
for (nb2hopset_t::iterator it = N2.begin(); it != N2.end(); it++) {
/* [cut]
* loop over two-hop neighbors, add to the MPR set those
* nodes in N (one-hop neighbors), which are the *only* nodes
* to provide reachability to a node in N2
*/

/* If you have one of these nodes, add it to the mpr set
* NOTE: *it == nb2hop_tuple1 */

if (!found) {
state_.insert_mpr_addr(nb2hop_tuple1->nb_main_addr());

/* Now loop again in the N2 set and remove all the
* other nodes that are reachable from the same node */

/*BUG*/ for (nb2hopset_t::iterator it2 = it + 1; it2 != N2.end(); it2++) {
OLSR_nb2hop_tuple* nb2hop_tuple2 = *it2;
if (nb2hop_tuple1->nb_main_addr() == nb2hop_tuple2->nb_main_addr()) {
deleted_addrs.insert(nb2hop_tuple2->nb2hop_addr());
it2 = N2.erase(it2);
it2--;
}
}
it = N2.erase(it);
it--;
}
// [...]
The bug is marked in the second loop. Only the nodes that are after the currently selected one are going to be tested for this condition, which suboptimizes the choice. This bug was present in NS2, in Inet for Omnet++ but it doesn't seem to be present in NS3 since the code has been refactored.

The second bug is in the degree() function:
int
OLSR::degree(OLSR_nb_tuple* tuple) {
int degree = 0;
for (nb2hopset_t::iterator it = nb2hopset().begin(); it != nb2hopset().end(); it++) {
OLSR_nb2hop_tuple* nb2hop_tuple = *it;
if (nb2hop_tuple->nb_main_addr() == tuple->nb_main_addr()) {
OLSR_nb_tuple* nb_tuple =
/*BUG*/ state_.find_nb_tuple(nb2hop_tuple->nb_main_addr());
if (nb_tuple == NULL)
degree++;
}
}
return degree;
}
Again, the marked line is a bug, since the comparison is not done using the two-hop neighbor address, but the corresponding one-hop neighbor address. In practice this function always returns 0. This bug is present in Inet, NS2 and NS3. Thanks my collegue Alessandro Russo here is the patch for NS3 as well.
--- src/olsr/model/olsr-routing-protocol.cc    2012-04-12 16:51:32.000000000 +0200
+++ /tmp/olsr/model/olsr-routing-protocol.cc    2012-04-12 16:51:27.000000000 +0200
@@ -526,7 +526,7 @@
       if (nb2hop_tuple.neighborMainAddr == tuple.neighborMainAddr)
         {
           const NeighborTuple *nb_tuple =
-            m_state.FindNeighborTuple (nb2hop_tuple.neighborMainAddr);
+            m_state.FindNeighborTuple (nb2hop_tuple.twoHopNeighborAddr);
           if (nb_tuple == NULL)
             degree++;
         }
Another issue, that is not properly a bug in the code is the fact that when the MPR choice is not unique, two nodes may end-up choosing the same node twice. Actually when two nodes can be chosen as MPR since they have the same reachability, OLSR does the following:

  • compare the reachability
  • compare the degree

Now, the willingness is a parameter that is set by default to 3, which makes the first check useless, and  degree for the bug before is always 0. OLSR does not specify how to solve this tie (even when the tie is justified and not due to a bug) so that the choice is completely implementation-dependent. In the simulator code the result is that the oldest node is chosen (the one that has been pushed in the list since a larger amount of time). What is the oldest neighbor?  in real life it can be any node that has been switched on as first in the neighborhood but in the simulator all nodes are turned on at the same instant. This means that the first one that sends a packet (HELLO are delayed with a random jitter) is the oldest one for all its neighborhood. As a consequence, if this node is a candidate to be chosen as MPR by any of its neighbors he will be chosen by all of them. This in turns, polarizes the choice of the MPRs and produces a smaller MPR set for the whole network. It is not really a bug, but it is a conceptual error due to the simulation environment.