Subject: [Ospf-manet] Re: Ospf-manet Digest, Vol 11, Issue 11

From: Aniket Desai <[email-masked]>
Date: Fri, 06 Oct 2006 10:23:22 -0400

At 02:29 AM 10/6/2006, you wrote:
>The main concern is that the BMDR algorithm is not easy to understand,
>although it is still O(n^2).  It is based on the Suurballe-Tarjan
>algorithm for computing disjoint paths

I just have to say that it is true that the *difficult* BMDR 
algorithm is not easily understood (I spent a couple of rigorous days 
trying to nail it down, to eventually favor the easier version of the 
algorithm). We preferred easy versions over the difficult versions 
for a variety of reasons. For one, the easier versions for MDR/BMDR 
can be implemented using arrays and hence they are much faster and 
cheaper. In my opinion, this is a big plus, and brings the MDR/BMDR 
algorithm on the same computational ballpark with the MPR algorithm. 
It should be easily possible for us to run a quantify and compare 
running times of the 2 algorithms on the similar topologies. I can 
happily volunteer to do this within the OPNET framework if WG wishes 
so. Secondly, the easier BMDR version results in more number of 
BMDRs, which is actually preferable for added robustness through 
redundancy. Thirdly, I think draft should make easier version 
de-facto to let people get a fair chance at understanding it first 
and make only references to the difficult version.

Finally, from an academic perspective, the MDR/BMDR algorithms are 
interesting, and I think it will be nice if the proofs for 
correctness could be provided in the appendix. Such proofs often shed 
more light on the properties of the algorithm and enable one to 
understand it more thoroughly. Perhaps the draft can consider giving 
some interesting examples of topologies and walk the reader through 
how each node would compute its MDR status starting from its Rmax 
neighbor and building a tree around it. Such graphical illustration 
will help a lot IMHO.

Sincerely,

Aniket

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

---

From: Richard Ogier <[email-masked]>
Date: Fri, 06 Oct 2006 08:50:14 -0700

Aniket,

Aniket Desai wrote:

> I just have to say that it is true that the *difficult* BMDR algorithm 
> is not easily understood (I spent a couple of rigorous days trying to 
> nail it down, to eventually favor the easier version of the 
> algorithm). We preferred easy versions over the difficult versions for 
> a variety of reasons. For one, the easier versions for MDR/BMDR can be 
> implemented using arrays and hence they are much faster and cheaper. 
> In my opinion, this is a big plus, and brings the MDR/BMDR algorithm 
> on the same computational ballpark with the MPR algorithm. It should 
> be easily possible for us to run a quantify and compare running times 
> of the 2 algorithms on the similar topologies. I can happily volunteer 
> to do this within the OPNET framework if WG wishes so. Secondly, the 
> easier BMDR version results in more number of BMDRs, which is actually 
> preferable for added robustness through redundancy. Thirdly, I think 
> draft should make easier version de-facto to let people get a fair 
> chance at understanding it first and make only references to the 
> difficult version.

The actual spec for selecting BMDRs (Section 5.3) allows any algorithm 
to be used
which determines whether or not two disjoint paths exist from the 
neighbor Rmax
to each other neighbor.   It does not require a specific algorithm to be 
used, but
two possible algorithms are provided in Appendix B.  It is not necessary 
to declare
one as the default algorithm.   Both algorithms run in O(n^2) time.  One 
can use
the simpler algorithm if they prefer.  But if someone wants to use 
biconnected
adjacencies (for robustness) and wants to minimize the number of 
adjacencies,
then they are welcome to use the Suurballe-Tarjan algorithm.   My code for
this algorithm is freely available for anyone to use, so they can just 
plug it in!
(This can be found in the GTNetS code available at the Boeing site.)

> interesting, and I think it will be nice if the proofs for correctness 
> could be provided in the appendix. Such proofs often shed more light 
> on the properties of the algorithm and enable one to understand it 
> more thoroughly. Perhaps the draft can consider giving some 
> interesting examples of topologies and walk the reader through how 
> each node would compute its MDR status starting from its Rmax neighbor 
> and building a tree around it. Such graphical illustration will help a 
> lot IMHO.

Yes, I agree that it would be good to include a good example in the draft.
So far, I have included an example in my IETF presentations.
http://www3.ietf.org/proceedings/05nov/slides/ospf-3/sld11.htm
Maybe you can contribute an example for the draft.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 06 Oct 2006 13:34:21 -0700

I want to point out that smart peering has the same issue regarding the
complexity of finding multiple disjoint paths.  This may not be obvious
because the draft does not provide any algorithms for computing such
paths.  I am referring to Step 3b in the flow chart on page 6 of
draft-roy-ospf-smart-peering-01.txt

(3b) Determine if the number of redundant paths to the potential
neighbor is < the maximum configured value.

If biconnected adjacencies are desired, then step (3b) would determine
if two disjoint paths exist from the router to each neighbor via
synchronized links.  The only optimal way to do this is to use
the Suurballe-Tarjan algorithm, similar to the MDR draft.
Or, as in the MDR draft, one can use a simpler algorithm
if one does not need to minimize the number of adjacencies.
(The simpler algorithm would not always find a pair of disjoint
paths even if such a pair exists, but this just results in
additional adjacencies.)

If one does not desire biconnected adjacencies, then it is possible
to select all non-MDRs as BMDRs, just as the OR approach selects
all non-MPRs as backup MPRs (they use different terminology).
As has been argued, the selection of MDRs is no more complex
than the selection of MPRs.

This is one piece of evidence to support my claim that the OR/MPR
approach is not really simpler than the MDR approach.
I am saying this now because Acee's message today implied that the
MPR approach is simpler than the MDR aproach, which I disagree with
(assuming that the MPR approach would use smart peering to achieve
scalability).

Richard