Subject: RE: [Ospf-wireless-design] any consensus?

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Thu, 27 Oct 2005 08:54:20 -0700

Richard,
You posed the following example.

> Now I will discuss the approach in which routing and adjacencies are
> based on MPRs, i.e., in which adjacencies are formed in both 
> directions
> between each router and its selected MPRs.  First of all, as 
> I discussed
> previously, some restrictions are needed to ensure that the resulting
> adjacency graph is connected.  The following example shows this.
> 
>        1
>       / \
>      /   \
>     2     3
>      \   /
>       \ /
>        4
> 
> 
> If node 1 selects node 2 as an MPR, and node 4 selects
> node 3 as an MPR, then the adjacency graph defined
> by MPRs is not connected.

Can you explain this example a little more clearly?  I think it is
important to this discussion if it is possible to create a disconnected
set of adjacencies when in steady state, but I don't see how this
example proves that.

If you are using reachability and router-id as your criteria for
selection (as in the OR draft), why would node 1 select node 2 as its
MPR.  Both node 2 and 3 have reachability to node 4, but node 3 has a
higher router-id.  

So, I would see the following nodes choosing the following MPRs.
1 -> 3
2 -> 4
3 -> 4
4 -> 3

Thanks,
Phil

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 27 Oct 2005 11:32:46 -0700

Phil,

Actually, I meant to also include a link between nodes 2 and 3
(as when I previously presented this example).

       1
      / \
     /   \
    2 --- 3
     \   /
      \ /
       4

In this case, my previous example is valid if routers do not
use node ID to break ties.  If routers use node ID to break
ties, then nodes 1 and 4 would both select node 3 as you said.
Node 2 would not have any MPRs or MPR selectors, so it is
not connected to other nodes via adjacencies.

An even simpler example is a fully connected network, which
has no MPRs.   For a more complicated example, add a node 5
with links to nodes 1 and 2.  Then node 4 would select node 2
as an MPR (since it covers two 2-hop neighbors 1 and 5), while
node 1 would still select node 3.

As I said, this is easily fixed by using RID or (RtrPri, RID)
to break ties, and by having a router form adjacencies with all
neighbors if it has a larger (RtrPri, RID) than all of its neighbors.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Thu, 27 Oct 2005 12:33:30 -0700

I would like to make a correction and a clarification to my previous
message.  (See below.)

> node 1 would still select node 3.

To make this last example work, switch the IDs of nodes 1 and 2,
so that node 4 selects node 1 as MPR, node 2 selects node 3 as MPR,
node 3 selects node 2 to reach the new node 5, and node 5 selects
node 1 to cover 3 and 4.  Then nodes 5, 1, and 4 are disconnected
from nodes 2 and 3 in the adjacency graph.  (Anyway, this example
is not needed since I gave other examples.)

    5 --- 2
     \   / \
      \ /   \
       1 --- 3
        \   /
         \ /
          4

> neighbors if it has a larger (RtrPri, RID) than all of its neighbors.

To clarify this, I mean that only (RtrPri, RID) should be used,
and NOT the degree or number of 2-hop neighbors covered.  This is a
good property anyway, since it provides better stability than if
node degree or number of covered 2-hop neighbors is used.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 28 Oct 2005 10:31:46 -0700

All,

I would like to make a few more comments on the method that
uses a CDS obtained by pruning MPRs. As I mentioned, this can be
implemented by modifying OSPF-MDR so that MPRs are announced in
Hellos, and a router selects itself as an MDR if the neighbor Rmax
with maximum (MDRLevel, RtrPri, RID) is an MPR selector.
The "dependent neighbors" of an MDR can be taken to be Rmax
and all neighbors of the router that are not neighbors of Rmax.
This implies that each MDR will form an adjacency with Rmax
and with each neighboring MDR that is not a neighbor of Rmax.
The above can also be applied to Backup MPRs, to select Backup MDRs.
Each MDR Other will select two parents as in the OSPF-MDR draft,
and form adjacencies with its parents.

To make the CDS/MDRs as stable as possible, a router should give
priority to existing MDRs when selecting MPR neighbors.
This can be done by giving priority to neighbors with larger
values of (MDRLevel, RtrPri, RID) when selecting MPRs.
Then there is the question of whether priority should be given
to neighbors based on the number of 2-hop neighbors they cover
(differential degree).  If degree is used, e.g., by replacing
the above triplet with (Degree, MDRLevel, RtrPri, RID), then the
CDS and adjacencies will not be as stable, but the number of MDRs
will be smaller.  This can be tried both ways, with and without
using "degree".

Now, if the above is done without using "degree", then the result
will be very similar to the current version of OSPF-MDR, with
the main difference being that the MPR version selects MPRs
while the current version selects MPR selectors (i.e., the router
decides whether its neighbor Rmax would select the router as
an MPR).  Also, since in OSPF-MDR a router considers only its
own neighbors (and not 2-hop neighbors) when deciding whether
to select itself as an MDR, whereas a neighbor (of the router)
that is selecting MPRs considers neighbors (of itself) that
are not necessarily neighbors of the original router, this
may result in slightly fewer MDRs being selected when
the MPR pruning method is used.

The use of MPRs (for selecting the CDS/MDRs) potentially
increases the time required to recover from a link failure, by
adding the extra steps of having to learn *true* 2-hop neighbor
information (the MDR selection algorithm only depends on which
1-hop neighbors are neighbors of each other), select MPRs, and
report MPRs to neighbors.

So, the main drawbacks of using MPRs to select the CDS/MDRs are
increased response time and increased complexity.
Assuming that MPRs are selected without using the number of
2-hop neighbors covered (for stability), the main advantage would
be a slightly smaller number of MDRs.

The two methods for selecting the CDS/MDRs (with and without using MPRs)
can be compared by modifying the GTNetS code for OSPF-MDR according to
the description above. I can help with modifying the code.

Richard