[Ns-bugs] [Bug 740] OLSR MprCompute () works wrong

[code@nsnam.ece.gatech.edu]

http://www.nsnam.org/bugzilla/show_bug.cgi?id=740


Pavel Boyko <boyko at iitp.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |boyko at iitp.ru




--- Comment #5 from Pavel Boyko <boyko at iitp.ru>  2009-11-17 07:49:38 EDT ---
  Hi, Gustavo,

  I will support this bug while Kirill is on the vacation. 

(In reply to comment #4)
> Hi, I am the (mostly-absent) maintainer of the OLSR code, but I see the patch
> was committed without me having time to even look at the issue, much less
> approve.  

  I'm terribly sorry, we will never do it again.

> While I love that a unit test was added, I have serious doubts about
> the patch:

  I agree with you that proposed (and commited) "fix" is completely wrong. 

  As I can see, the real error was in the lines:

          for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin ();
twoHopNeigh != N2.end (); )
            {
              if (twoHopNeigh->neighborMainAddr == neighbor->neighborMainAddr)
                {
                  NS_LOG_LOGIC ("2-hop neigh. " <<
twoHopNeigh->twoHopNeighborAddr << " is already covered by an MPR.");
                  twoHopNeigh = N2.erase (twoHopNeigh);
                }
              else
                {
                  twoHopNeigh++;
                }
            }

  you were used to remove covered 2-hop neighbors from N2 set. This code
ignores the fact that N2 set is made of pairs {neighbor, two hop neighbor} and
that the same 2-hop neighbor can appear multiple times in N2 with different
1-hop neighbors. All this records must be deleted when two hop neighbor is
covered by MPR. 

  The simplest topology which illustrates this is 

  O -- A
  |    |
  B -- C  

  where O selects MPR set and N = {A, B} N2 = {{A, C}, {B, C}}. When A is
selected as MPR your code will remove tuple {A, C} from N2 but will not remove
record {B, C} and this will case B to be erroneously selected as the second
MPR.

  The proposed fix-to-fix is attached (It should be applied to ns-3-dev as is),
please take a look.

> It was never explained in this bug report what MPR set was being selected and
> which one should in theory have been selected. 

  I agree that current unit test topology is overcomplicated. If you don't
object I will simplify existing unit test to reproduce minimal topology drawn
above and add some more MPR selection tests. You can do this by yourself if you
like to.  

>  Keep in mind that OLSR contains
> an heuristic for find a _good_ MPR set; it is not guaranteed to find the _best_
> MPR set.  Find the best set is an NP-complete problem...

  I know. Now we are talking about correct implementation of recommended
heuristic from RFC 3626 8.3.1.

-- 
Configure bugmail: http://www.nsnam.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.