Subject: Re: [manet] OLSRv2 and forwarding based on MPR

From: Richard Ogier <[email-masked]>
Date: Wed, 08 Apr 2009 07:49:47 -0700

Teco Boot wrote:

>Is it correct that this TC is sent on the |-segment ***5 times***?
>
>Forwarding is straightforward (olsrv2-08 page 27):
>  
>
>>>3.  For each OLSRv2 interface of the router
>>>      
>>>
>           *********************
>So I think the answer is YES. If so, this is really bad!!
>

Teco,

Although I am not sure that transmitting the TC message 5 times can
be avoided in your example, selecting MPRs per interface certainly
can result in inefficiency due to unnecessary forwarding.
I also discussed this in my post yesterday, which I am repeating below
since my previous post was from my earthlink address, which some
people are not receiving.

I guess the main limitation of the race condition is that MPRs must
be selected per interface, as discussed.  Not only would selecting
MPRs per node (for all interfaces) result in more efficient flooding
(see the example below), but it would also allow Flooding MPRs to be
the same as Routing MPRs in draft-dearlove-olsrv2-metrics-03, thus
greatly simplifying the protocol.  This would also result in flooding
of topology updates along the routing paths in the reverse direction
(reverse path forwarding), which provides the benefit that updates
related to the path to destination D are received from the next hop
to D (so you know the next hop has the information it needs).

I know there are methods to avoid the race condition.  Philippe
mentioned one, and I know of others.
My point is that (in my opinion) the benefits of being able to
select MPRs per node instead of per interface are great enough
to justify using such an approach.  At least the WG should be
able to consider and experiment with such an alternative.

You can say that OLSRv2 is stable, but that is without metrics.
Your approach to metrics, using Routing MPRs in addition to
Flooding MPRs, appears to be a patch that avoids modifying
the existing flooding mechanism in OLSRv2, whereas if one started
from scratch, the above simplified approach might be better
(in which Flooding MPRs are the same as Routing MPRs).

As shown in the following (obvious) example, having to select MPRs
per interface can be very inefficient in a network that has several
interfaces.
In the example, each link is a separate interface; thus node A must
select all neighbors as MPRs, even though only one MPR is necessary.

  A
 /|\
B C D
 \|/
  E

Richard

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Wed, 8 Apr 2009 17:09:51 +0100

Ricahrd Ogier
> the above simplified approach might be better

Not if metrics are asymmetric. That's actually a fundamental
reason for separating the two. They use the opposite direction
metrics.

********************************************************************
This email and any attachments are confidential to the intended
recipient and may also be privileged. If you are not the intended
recipient please delete it from your system and notify the sender.
You should not copy it or use it for any purpose nor disclose or
distribute its contents to any other person.
********************************************************************

---

From: Richard Ogier <[email-masked]>
Date: Wed, 08 Apr 2009 21:05:29 -0700

I have an additional comment below, in response to an earlier post.

Dearlove, Christopher (UK) wrote:

>Richard Ogier wrote:
It is good to allow the flexibility to use metrics in that
manner to select flooding MPRs.  But it would also be good to
allow the flexibility to select flooding MPRs to be the same
as routing MPRs for simplicity when metrics are not used,
or even when metrics are used.  (In the latter case, TC messages
are forwarded along shortest paths in the reverse direction,
which may not be optimal, but the benefit is simplicity.)
But this option is possible only if MPRs are selected per node
and not per interface.  (The arguments in favor of per-node
MPRs are building up.)

Also, since your last post claimed that the proposed method is
inefficient, I want to repeat the following example as a reminder
that selecting MPRs per node can be MUCH more efficient than
selecting MPRs per interface.
In the example, each link is a separate interface; thus node A must
select all neighbors as MPRs, even though only one MPR is necessary.
This seems like a no brainer to me.

  A
 /|\
B C D
 \|/
  E

Richard

---

From: "Dearlove, Christopher (UK)" <[email-masked]>
Date: Thu, 9 Apr 2009 12:17:02 +0100

> But it would also be good to
> as routing MPRs for simplicity when metrics are not used

Always possible, because the algorithm isn't specified, only
its properties. There's plenty of scope for intelligent tradeoffs
of how to do things.

> which may not be optimal, but the benefit is simplicity.)

There's actually no necessity to use metrics at all for flooding.
(It just improves some things. But for routing use of metrics is
essential.)

> and not per interface.

Not so, you can always select per interface even when you don't
have to (i.e for routing). That's if you value making the same
selection more highly than making an efficient selection.
Adter all, it's even legal to use the simplest MPR selection
algorithm of all - pick all your neighbours. But if you do, I'll
pick someone else's implementation.