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

[Richard Ogier <[e-mail]>]

Aniket,

Aniket Desai wrote:

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


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

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


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


>
>
> Sincerely,
>
> Aniket
>
>
>
> _______________________________________________
> Ospf-manet mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/ospf-manet
>
>



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