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

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
Ospf-manet@ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-manet