Subject: [Ospf-manet] Re: Regarding MPR-OSPF

From: Richard Ogier <[email-masked]>
Date: Mon, 12 Mar 2007 14:35:58 -0700

Philippe and Emmanuel,

You did not respond to my following comment posted on 2/19/07:

 > I noticed two possible problems with your GTNetS code for MPR-OSPF.
 > The first one regards the following code in need_adjacency():

 > #ifdef OSPF6_MANET_MPR_ADJ_REDUC_OSPF_MPR
 >       if (on->ospf6_if->synchNode)
 >          return 1;
 >
 >        if (ospf6_lookup_relay_selector(on->ospf6_if, on->router_id))
 >          return 1;
 >        else
 >          return 0;
 > #endif //OSPF6_MANET_MPR_ADJ_REDUC_OSPF_MPR

 > The above code code says that the router forms an adjacency with
 > a neighbor only if the router is a synch node or the neighbor
 > is an MPR selector.  This can cause unidirectional adjacencies,
 > as explained below.  (A similar problem with the OSPF-MDR code
 > was discovered and corrected over a year ago.)
 > ...
 > Therefore, it is necessary for the need_adjacency condition to be
 > symmetric. I.e., node i should consider node j adjacent if and only
 > if node j considers node i adjacent. More specifically, need_adjacency()
 > should also return true if the neighbor is a synch node or an MPR.
 > (Notice that the need_adjacency condition is symmetric in RFC 2328.)

However, you *did* quietly modify your draft to incorporate my
suggestion to make the need_adjacency condition symmetric, in
Section 5.3.2 of your updated draft:

 >   the state of this neighbor MUST be changed to (i) 2-WAY if the neighbor
 >   is not in the MPR set or the MPR selector set, or (ii) ExStart if the
 >   neighbor is in the MPR set or the MPR selector set, or if the
 >   neighbor or the router itself is a synch router.

You also added the S bit to TLV type 4 to allow a router to know
whether a neighbor is a synch router.

I guess I should be happy that you incorporated my suggestion.
But I think I saved you significant effort, since it was not easy
to find this bug in OSFP-MDR more than a year ago, so I think
some sort of thanks would be appropriate.
For consistency, you also need to modify the condition
for forming an adjacency in Section 5.3 (to make the
condition symmetric).

Also, I see you modified the rule for selecting synch routers
to be consistent with your code, i.e.,

o  a MANET router decides it is a synch router if and only if the
   router has a higher ID than any other ID received in Hello packets
   or Router-LSAs.

I see two possible problems with the above rule.
First, you are now ignoring Willingness (or Router Priority),
so a router that has very little remaining battery life
might be selected to be the synch router (and thus become
adjacent with all of its neighbors).
I feel sorry for the router with the largest RID.

Second, this does not work if the highest RID node in the area is
a non-MANET router (does not have a MANET interface).
You could select the synch router to be the MANET router with the
largest RID (and indicate by a bit in the LSA whether a router
is a MANET router), but even this does not work since the largest
RID router might not be reachable via MANET links, or the route
might have to use multiple MANET interfaces.
Therefore, unless you have a way to fix this, I think it is necessary
to select synch routers based on local information, possibly by
looking at all 2-hop neighbors.
Another possible solution is to identify the synch router for each
interface in Hello packets, so a router can be sure that there is
a MANET path to the synch router via the same MANET interface.
However, this could take significant time to converge if the
synch router for a given interface leaves the network
or becomes unreachable.

Richard

_______________________________________________
Ospf-manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-manet

---

From: Emmanuel Baccelli <[email-masked]>
Date: Tue, 13 Mar 2007 14:26:37 +0100

Dear Richard,

We're happy to see that you, subsequent to our long discussions, have 
been working towards improving MDR. The performance results in your 
email indicate important changes to the I-D, which merit study and 
further discussion -- will you be in Prague that we may do that together 
(at the OSPF meeting and otherwise)?

As for the MPR-OSPF draft, as you observed, some minor details which 
were pointed out on the list and elsewhere have been clarified in the 
I-D -- this will, of course, be reflected in the status update in 
Prague. And by the way, here is the link to the update of the draft: 
http://www.ietf.org/internet-drafts/draft-baccelli-ospf-mpr-ext-03.txt

To clarify a point which you indicate that you missed concerning the 
synch router: the willingness parameter influences a routers forwarding 
ability only. If a synch router is outside the MANET, then according to 
the I-D there exists a hybrid router which will synchronise with its 
whole neighbourhood, thus fulfilling the synch role.

We agree that the synch alternatives which you propose are complex and 
potentially less performant, which is why we went with the above 
solution which does the same thing without these inconveniences.

Emmanuel

---

From: Richard Ogier <[email-masked]>
Date: Tue, 13 Mar 2007 13:31:06 -0800

Emmanuel Baccelli wrote:

> synch router: the willingness parameter influences a routers 
> forwarding ability only. If a synch router is outside the MANET, then 
> according to the I-D there exists a hybrid router which will 
> synchronise with its whole neighbourhood, thus fulfilling the synch role.

OK. I knew that a hybrid router must select all neighbors as path MPRs,
but I missed the definition of the MPR set as the union of the path MPRs
and the flooding MPRs. So a router must become adjacent with all of its
flooding/path MPRs and flooding/path MPR selectors.
This could result in a lot of adjacencies when unequal metrics are used
(even more than you are obtaining in your GTNetS simulations).

But still, if there is no hybrid router, then the router with largest RID
is still treated unfairly since, as the synch router, it must become
adjacent with all of its neighbors.  In version 02, you used Willingness
to select synch routers, but I realize you can't do that easily now,
since you are now looking at all routers in the area.
(Note that MDR selection uses Router Priority, so OSPF-MDR does
not have this issue.)

I won't be at the Prague meeting, but plan to present an update
at the Chicago meeting in July.

If you are going to present simulation results at the Prague meeting,
can you provide your updated GTNetS code this week?
Or if you did not make any changes to the code other than making
the need_adjacency condition symmetric (as I suggested), then please
let me know (since I can easily make this change).

Richard

---

From: Richard Ogier <[email-masked]>
Date: Tue, 13 Mar 2007 16:24:26 -0800

> synchronise with its whole neighbourhood, thus fulfilling the synch role.

Emmanuel,

There still seems to be a problem when a router has multiple
MANET interfaces.  You define a hybrid router as follows.

Hybrid router  - a router which has OSPF interfaces of several types,
including the MANET type.

So a router with only MANET interfaces is not a hybrid router.
Consider a router A that has only one MANET interface, but has
only 1-hop neighbors and no 2-hop neighbors on this interface.
(I.e., Hellos received from neighbors on this interface advertise
only routers that are neighbors of router A itself.) As a result,
router A has no MPRs.  Assume it also has no MPR selectors.

A ----- B ----- C

Now suppose router A has a neighbor B which has two MANET
interfaces, one of which connects it to router A, and the other
of which connects it to router C, which is not a neighbor of A.
Assume router C has the largest RID and is therefore the synch router.
Therefore, since router A is not a synch router (nor a neighbor of a
synch router) and has no MPRs or MPR selectors, it has no adjacencies!

Therefore, it still looks like you need to select a synch router
for each MANET interface, or redefine a hybrid router to include
routers with multiple MANET interfaces.  Am I missing something?

Richard