Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report

From: Philippe Jacquet <[email-masked]>
Date: Fri, 02 Feb 2007 19:34:01 +0100

Dear Richard,

The simulation code about minCost LSA (in ospf6_neighbor.c, in int 
ospf6_mdr_update_adv_neighbors(struct ospf6_interface *oi)) contains the 
sequence of instructions:

       // Determine costs to j and k (as would be advertised in LSA)
       if (onj->state == OSPF6_NEIGHBOR_FULL) costj = 10;
       else costj = 11;
       if (onk->state == OSPF6_NEIGHBOR_FULL) costk = 10;
       else costk = 11;

I understand that it implicitly gives priority to full neighbors. 
Instead of artificially distorting link cost, could it not be an idea to 
be more explicit in the draft by using the sentence (page 55-56 in 
clause 5) b) and c):

If HCM(j,i) + metric(i,k) < HCM(j,u) + LCM(u,k), or if u does
not exist and HCM(j,i) + metric(i,k) < HCM(j,k), or if k is a full 
neighbor, add k to the set of advertised neighbors.

But of course it will not be possible to know about the adjacencies 
between the other nodes (u,k) or (j,u), other than by specific 
advertizement via a specific TLV in hellos.

I also have difficulties to see how the option OSPF6_LSA_FULLNESS_MINHOP 
(LSAFullness=1?) works. It seems that the link cost distortion causes to 
advertize no more than the full neighbors (like in LSAFullness=0?) and 
not the minCost path as specified in the MDR draft. It seems that 
OSPF6_LSA_FULLNESS_MINHOP2PATHS (LSAFullness=2) is the right option that 
provides shortest path. Therefore when you run the code with option 
LSAFullness=1, one would not get mincost LSA's -- is that correctly 
understood?

Philippe

Richard Ogier a écrit :
> Emmanuel,
> 
> Regarding your simulation results, it looks like using
> MPR adjacency reduction does not reduce overhead much,
> and based on the simulation results I presented recently,
> MDR with adjacency reduction has much lower overhead.
> 
> I think you would have to make major changes to your draft
> before it is competitive with MDR.  For example, you will at
> least have to select MPRs (and "path MPRs" for LSAs) to be more
> stable, which has not yet been described in your draft.
> 
> The MDR draft does not need major changes, but I am making
> changes to improve readability, to simplify the BMDR algorithm,
> and other minor changes such as improving min-cost LSAs.
> This does not change the core methods for flooding and adjacency
> reduction, which have been stable for about two years.
> 
> My point was that, since MPR adjacency reduction is not scalable,
> the main contributions of your draft are MPR LSA reduction
> and multicast retransmitted LSAs (the latter of which is not
> new and was considered in version 00 of the MDR draft), and
> that these two contributions do not by themselves constitute
> an OSPF extension, but are techniques that can be applied
> to either ORs or MDRs.
> 
> I mentioned that I will experiment with multicast retransmitted
> LSAs to see if they improve the performance of MDRs in some
> scenarios, and if they do they can be included as an option.
> This would be a minor change to the MDR draft.
> 
> After we have both finalized our drafts, we should continue
> our discussion then, and perform a fair simulation comparison.
> Until then, I suggest we take a break from this discussion.
> 
> Richard
> 
> 
> 
> Emmanuel Baccelli wrote:
> 
>> Dear Richard,
>>
>> We agree that there is no need to argue. The MPR-OSPF is a consistent
>> extension of OSPFv3 that uses flooding reduction, topology reduction and
>> adjacency reduction based on MPR, with a stable specification ready for
>> experimental status.
>>
>> You suggest that you could introduce some changes in MDR, taking
>> advantage of the experimental status. We do not think that it is needed
>> to introduce the major changes you mentionned (such as including MPR
>> topology reduction or multicast) since they are already featured in the
>> MPR-OSPF extension. However, if you think MDR needs major changes, then
>> MDR is not ready for experimental status.
>>
>> Emmanuel
>>
>>
>> _______________________________________________
>> Ospf-manet mailing list
>> [email-masked]
>> https://www1.ietf.org/mailman/listinfo/ospf-manet
>>
> 
> 
> _______________________________________________
> Ospf-manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-manet
> 
> 

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

---

From: Richard Ogier <[email-masked]>
Date: Tue, 06 Feb 2007 10:20:52 -0800

Philippe,

As I mentioned, the min-cost LSA algorithm will be modified in the
next draft update, which may affect some of your comments, so I
prefer that you comment on the updated version when it comes out.
(I don't plan any MDR presentation at the Prague meeting, so the
next draft update might not come until after the meeting.)

Also note that the simulation results will not be affected
significantly by modifying the min-cost LSA algorithm, since the
LSU overhead will remain low.  The main issue addressed by the
simulations is the large overhead when MPR adjacency reduction
is used.

I address your comments below.

Philippe Jacquet wrote:

> ospf6_mdr_update_adv_neighbors(struct ospf6_interface *oi)) contains 
> the sequence of instructions:
>
> Instead of artificially distorting link cost, could it not be an idea 
> to be more explicit in the draft by using the sentence (page 55-56 in 
> clause 5) b) and c):

I don't agree that this artificially distorts link costs.
I think it is a good idea to give fully synchronized neighbors
a lower cost, simply because they are more likely to provide good
routes.  Actually, I would not fix the cost at 10 or 11, but
would add 1 to the metric of any neighbor that is not Full.
The draft does not specify how to select metrics, so
the implementation is free to do this.

> neighbor, add k to the set of advertised neighbors.

Step 4 already adds all Full neighbors to the set of
advertised neighbors, so your modification has no effect.
(The goal is that if node i advertises Full neighbor k, then
node u should not advertise k if it is not Full.)

> advertizement via a specific TLV in hellos.

That is why it is useful to add 1 to the metric of neighbors
that are not Full.

Actually, the DNL (dependent neighbor list) TLV implies information
about other adjacencies, and the updated min-cost LSA algorithm may
use this information.  However, these details have a small effect
on performance, compared to adjacency reduction.

>
>
> I also have difficulties to see how the option 
> OSPF6_LSA_FULLNESS_MINHOP (LSAFullness=1?) works. It seems that the 
> link cost distortion causes to advertize no more than the full 
> neighbors (like in LSAFullness=0?)

The use of 11 instead of 10 for a link metric would not affect the
number of hops in computed paths, unless the path has at least 10
hops.  (A 10-hop path with all links having metric 11 would have the
same length as an 11-hop path with all links having metric 10.)
Since Full neighbors alone do not provide min-hop paths, some
non-Full neighbors will also have to be advertised.  Maybe I
do not understand your question.  In any case, it might be better
to wait for the updated min-cost LSA algorithm.

Richard

> and not the minCost path as specified in the MDR draft. It seems that 
> OSPF6_LSA_FULLNESS_MINHOP2PATHS (LSAFullness=2) is the right option 
> that provides shortest path. Therefore when you run the code with 
> option LSAFullness=1, one would not get mincost LSA's -- is that 
> correctly understood?

---

From: Philippe Jacquet <[email-masked]>
Date: Fri, 09 Feb 2007 16:52:17 +0100

Dear Richard,

We have studied the MDR code and draft.

1. The algorithm described in the MDR draft does not provide the feature 
it claims: minimum cost paths in the routing table. Links are not 
guaranteed to be symmetrically advertized and, consequently, part of the 
LSAs will systematically be killed by backlink check.

2. Making a nodes LSA dependent of other nodes LSA is a source of 
circular dependancy.

3. The code for minCost LSA in the GTNet MDR-implementation does not 
implement the algorithm which is described in the MDR draft: For the 
option used in the simulations which you presented lately 
(LSAFullness=1), the code has three embedded loops that in the end make 
a node i to advertize a link to a node j if and only if i is the closest 
node to j. But this does not result in shortest path advertizements.

4. The GTNet MDR implementation artificially distorts link metrics as a 
way of expressing both the actual cost and the property (synchronized or 
not) of the link as one. This approach is, not specified in the MDR 
draft, so also on this point the GTNet MDR implementation and the MDR 
draft exhibit a significant discrepency.

The preliminary conclusions are, therefore:

   - that the algorithms and the claims of the MDR draft do not
     correspond with each other;

   - that the MDR draft and the GTNet MDR implementation do not
     correspond with each other;

and so:

   - that the simulation results presented from GTNet for the MDR-OSPF
     proposal correspond NEITHER to the MDR draft algorithms NOR to the
     properties claimed by the MDR draft.

Sincerely,

Philippe

---

From: Richard Ogier <[email-masked]>
Date: Fri, 09 Feb 2007 11:55:07 -0800

Philippe,

As I mentioned, the MDR draft will be updated soon, and
will include a modified algorithm for min-cost LSAs.
So, PLEASE hold your criticisms of min-cost LSAs
until you see the updated version!

You are correct that the simulation results may
be different with the updated min-cost LSA algorithm,
so I will rerun the simulations once OSPF-MDR is updated.
Hopefully, you will also have some improvements to MPR-OSPF
by then (e.g., to improve the low delivery ratio).
However, the largest contributor to overhead in MPR-OSPF is
DD overhead, 10 times larger than MDR for 100 nodes,
and this result is NOT affected by the choice of LSAs.

I respond to your comments below.

Philippe Jacquet wrote:

> 1. The algorithm described in the MDR draft does not provide the 
> feature it claims: minimum cost paths in the routing table. Links are 
> not guaranteed to be symmetrically advertized and, consequently, part 
> of the LSAs will systematically be killed by backlink check.

As I mentioned a few months ago, the min-cost LSA algorithm
will be modified to ensure links are symmetrically advertised.
The next draft update will include this modification.

Once the min-cost LSA algorithm is modified, we can do another
simulation comparison, so the LSU overhead can be compared
fairly.  Also, we can compare MPR-OSPF to OSPF-MDR, using
path-MPR-based LSAs for both protocols.
(Note that path-MPRs are not really MPRs, since they do
not provide multipoint relaying.)
This allows us to compare the two flooding
approaches independently of the LSA algorithm.
Note that OSPF-MDR can use either min-cost LSAs
or path-MPR-based LSAs, so the LSA algorithm is
decoupled from the flooding mechanism.

> 2. Making a nodes LSA dependent of other nodes LSA is a source of 

No.  Node i decides not to advertise a link to neighbor j if
neighbor u is already advertising j (and node i cannot provide
a better path to j).  There is nothing wrong with this.
Maybe you are thinking about what happens if several routers
decide to add j at the same time, which would result in
redundant advertisements.  This is one of the things that
will be improved in the updated version of min-cost LSAs,
using information from Hellos.

> (LSAFullness=1), the code has three embedded loops that in the end 
> make a node i to advertize a link to a node j if and only if i is the 
> closest node to j. But this does not result in shortest path 
> advertizements.

The MDR draft states that min-cost routing is provided only if Hellos
include metric information, which is optional (See the 4th paragraph
of Appendix C.) Otherwise, we have min-hop routing if all metrics
are equal, or metrics can be used to give preference to some links,
e.g. to Full links.  So we get something that is better
than min-hop but not exactly min-cost.  Anyway, the updated
version of the min-cost LSA algorithm will always provide
min-cost routing.  Again, you are criticizing an old version of
an algorithm that I have already said I plan to update.
(Note that LSA reduction was not considered a goal until
recently, so I did not focus on that until recently.)

Also, the LSA algorithm is decoupled from the flooding mechanism.
If we decide that path-MPR-based LSAs are better, then I would
be happy to use them with OSPF-MDR.
But my main point is that MPR-based adjacency reduction generates
much more overhead than MDR-based adjacency reduction.

Richard

>
> 4. The GTNet MDR implementation artificially distorts link metrics as 
> a way of expressing both the actual cost and the property 
> (synchronized or not) of the link as one. This approach is, not 
> specified in the MDR draft, so also on this point the GTNet MDR 
> implementation and the MDR draft exhibit a significant discrepency.
>

---

From: Richard Ogier <[email-masked]>
Date: Sat, 10 Feb 2007 10:24:07 -0800

Philippe,

I didn't reply to the following comment, because I thought I already
addressed it in my previous email.  But I will add a few comments.

> implementation and the MDR draft exhibit a significant discrepency.

I guess the word "artificial" is the opposite of "natural", and the
use of such vague words has already been discussed.

It is acceptable to allow the link metric to depend on link
quality, as you know (since OLSR does this).  Link quality
can be measured in many ways.  For example, if n consecutive
Hellos have been received from the neighbor, the link metric
can be decreased to represent good link quality.
Similarly, if database exchange has been completed with the
neighbor, so that its state becomes Full, this implies the link
is likely to have better quality, so we can decrease the link
metric slightly to prefer it over non-Full neighbors.

Since you are bothered that this is not specified in the MDR
draft, I can add something like the following to the next
draft update: "The router MAY add a small penalty to the metric
of links to neighbors that are not Full".

Also, we can run simulations both with and without this technique,
after the updated version of OSPF-MDR has been implemented
in GTNetS.

Richard

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 14 Feb 2007 15:38:02 +0100

Dear Richard,

In contrast to the claims of the MDR draft, the code (available on the 
Boeing WWW-site and used for the simulations in the milcom06-paper) does 
not provide min-hop path, regardless of backlink check, cost metric and 
cost distortion.

Since the LSA reduction in MDR is still not mature and certainly not 
tested (since no code is available), it is misleading to advertise the 
simulations with anything else but the full LSA option.

Notice that I have not had time to check the MDR simulation code 
thoroughly beyond minCost LSAs, so there may be other potential problems 
and discrepancies with what is specified in the I-D elsewhere which I 
have not yet detected.

Sincerely,

Philippe

---

From: Richard Ogier <[email-masked]>
Date: Thu, 15 Feb 2007 12:07:06 -0800

Philippe,

Philippe Jacquet wrote:

> Boeing WWW-site and used for the simulations in the milcom06-paper) 
> does not provide min-hop path, regardless of backlink check, cost 
> metric and cost distortion.

It is because of the backlink check that it does not provide min-hop
paths, since the old min-cost LSA algorithm did not advertise neighbors
symmetrically. (Note that min-COST routing would require Hellos to
advertise neighbor costs, which is an option not implemented in GTNetS.)
As I pointed out, INRIA's original code for MPR-OSPF did not
even perform a backlink check (but has now been corrected).
Frankly, I think it would be better if we could omit the backlink
check, but that would not be compatible with legacy OSPF.

The cost "distortion" is simply a small penalty to favor the use
of synchronized links, and does not affect the hop length for paths
less than 10 hops.  Also, this penalty is optional.
The updated min-cost LSA problem (to be announced soon), will
advertise neighbors symmetrically and will always provide
min-cost paths.

> simulations with anything else but the full LSA option.

I don't agree.  For example, one can use the "minimal LSA" option with
MDR, which allows only synchronized links to be used for routing.
This does not provide min-hop or min-cost routing, but some applications
may be willing to trade off path optimality to achieve much lower overhead.
Also, I am sure you would not object if MDR uses path-MPR-based LSAs.
I plan to compare path-MPR-based LSAs to the updated min-cost LSA
algorithm, and I would be happy to use whichever method turns out to
perform better.

You are focusing on LSAs, which are decoupled from flooding and
adjacency reduction in OSPF-MDR.
You are right that my simulation results did not provide a fair
comparison of LSU overhead, but they *did* provide a fair comparison
of synchronization (DD) overhead, since the choice of LSAs have no
effect on DD overhead (assuming that each router originates an LSA).

I  plan to compare the following three protocols:

1. MPR-OSPF (with path-MPR-based LSAs)
2. OSPF-MDR with path-MPR-based LSAs
3. OSPF-MDR with the updated min-cost LSA algorithm.

Comparing 1 and 2 will allow the flooding and adjacency reduction
methods to be compared independently of the choice of LSAs.
Comparing 2 and 3 will determine which LSA algorithm performs better
with OSPF-MDR.

Also, we can try using multicast LSA retransmissions with OSPF-MDR.
For fairness, any technique that is used with one protocol and that
can be used to improve the performance of the other protocol, should
be used by both protocols.

In order for MPR-OSPF to provide min-cost paths (based on metrics),
you will have to select "path MPRs" and advertise these and link
costs in Hellos, along with MPRs.
Your Appendix C describes a Path MPR Selection Heuristic,
which is not implemented in GTNetS.  So I guess we are
both experimenting with LSA algorithms that are not yet
mature.  That is fine, since the need for LSA reduction was
not considered a goal until relatively recently.  That is why
Cisco's OR/SP drafts do not specify an algorithm for LSA
reduction.

Richard

P.S. BTW, the min-cost LSA algorithm could be called
"path-MPR-source-based LSAs".  I.e., a router selects
MPR sources (equivalent to MPR selectors) instead of MPRs.
But I think using the term MPR in both cases is inappropriate,
since path-MPRs are not used for multipoint relaying.
I prefer the more generic term "selected advertised neighbors".

---

From: Richard Ogier <[email-masked]>
Date: Mon, 19 Feb 2007 09:36:17 -0800

Philippe,

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.)

Suppose node i forms an adjacency with node j either because
node i is a synch node or node j is an MPR selector.
Suppose that node j later misses a few Hellos from node i,
so that node j changes the state of neighbor i to Down and then
to 2-Way, without sending a Hello that indicates neighbor i is Down
(or perhaps node j sends one such Hello that is not received by i).
Node j does not consider node i adjacent, since j is not a
synch node and i is not an MPR selector. (The need_adjacency()
condition is not symmetric.)

Also suppose that node i never misses any Hellos from node j (or misses
only one Hello from j).  Then node i will still think node j is fully
adjacent, even though node j does not consider node i adjacent.
Thus, a unidirectional adjacency can exist.

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.)

The other problem I noticed regards the selection of synch routers.
Your GTNetS code does not agree with your draft.
In your code, only one router in the entire network (area) is
selected as a synch node, i.e., the one with the largest RID.
This does not agree with your draft, which says:

 >   A router decides it is a synch router if and only if:
 >   o  the router is a wireless router that has the highest willingness
 >      in its neighborhood (in case of ties, the router that also has the
 >      greatest ID is elected).

Also, what if the router with the largest (willingness, RID) is not
a MANET router?  And what if you have multiple MANET interfaces,
in addition to non-MANET interfaces?
I think you are safer if you consider only MANET neighbors on a
given interface when deciding whether a router is a synch router
(as in your draft).
I realize that this would result in more adjacencies and more
overhead, but it may also improve robustness.
Also, if you select only a single synch router (as in your code), it is
not clear how to extend this to multiple interfaces or networks that
include non-MANET interfaces.  Please let us know which rule you
plan to use for selecting synch routers.

Richard