[Ospf-manet] Re: Regarding OSPF MDR

Philippe Jacquet <philippe.jacquet@inria.fr> Wed, 14 February 2007 14:38 UTC

Received: from [] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHLHL-0006wf-QZ; Wed, 14 Feb 2007 09:38:39 -0500
Received: from [] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1HHLHL-0006wa-7O for ospf-manet@ietf.org; Wed, 14 Feb 2007 09:38:39 -0500
Received: from concorde.inria.fr ([]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1HHLHJ-0004S1-Ow for ospf-manet@ietf.org; Wed, 14 Feb 2007 09:38:39 -0500
Received: from [] (sphinx.lix.polytechnique.fr []) (authenticated bits=0) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l1EEbxux032467 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 14 Feb 2007 15:38:00 +0100
Message-ID: <45D31ECA.50007@inria.fr>
Date: Wed, 14 Feb 2007 15:38:02 +0100
From: Philippe Jacquet <philippe.jacquet@inria.fr>
User-Agent: Thunderbird (Macintosh/20061207)
MIME-Version: 1.0
To: Richard Ogier <rich.ogier@earthlink.net>
References: <45B5D944.9010303@inria.fr> <45BD37DF.1050005@earthlink.net> <45C38419.7070208@inria.fr> <45C8C704.8020908@earthlink.net> <45CC98B1.8060907@inria.fr> <45CCD19B.9070604@earthlink.net>
In-Reply-To: <45CCD19B.9070604@earthlink.net>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
X-Miltered: at concorde with ID 45D31EC7.003 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
Content-Transfer-Encoding: quoted-printable
X-MIME-Autoconverted: from 8bit to quoted-printable by concorde.inria.fr id l1EEbxux032467
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 8f374d0786b25a451ef87d82c076f593
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

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.



Richard Ogier a écrit :
> 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:
>> 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.
> 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.
>> 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