[Ospf-manet] Re: Regarding OSPF MDR

Richard Ogier <rich.ogier@earthlink.net> Fri, 09 February 2007 19:55 UTC

Received: from [] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFbq4-000153-Tl; Fri, 09 Feb 2007 14:55:20 -0500
Received: from [] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HFbq4-00014s-0b for ospf-manet@ietf.org; Fri, 09 Feb 2007 14:55:20 -0500
Received: from pop-cowbird.atl.sa.earthlink.net ([]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HFbpy-0004qC-R9 for ospf-manet@ietf.org; Fri, 09 Feb 2007 14:55:19 -0500
Received: from dialup- ([]) by pop-cowbird.atl.sa.earthlink.net with esmtp (Exim 3.36 #1) id 1HFbpt-0007W4-00; Fri, 09 Feb 2007 14:55:10 -0500
Message-ID: <45CCD19B.9070604@earthlink.net>
Date: Fri, 09 Feb 2007 11:55:07 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: philippe.jacquet@inria.fr
References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr>
In-Reply-To: <45CC98B1.8060907@inria.fr>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 3a4bc66230659131057bb68ed51598f8
Cc: ospf-manet@ietf.org
Subject: [Ospf-manet] Re: Regarding OSPF MDR
X-BeenThere: ospf-manet@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussions of OSPFv3 extensions supporting MANET <ospf-manet.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-manet>, <mailto:ospf-manet-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/ospf-manet>
List-Post: <mailto:ospf-manet@ietf.org>
List-Help: <mailto:ospf-manet-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-manet>, <mailto:ospf-manet-request@ietf.org?subject=subscribe>
Errors-To: ospf-manet-bounces@ietf.org


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:

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

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 
> circular dependancy.

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.

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

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.


> 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

Ospf-manet mailing list