I think the key thing here is that while the inequality
(i) D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,E) + D_opt(E,Y)
Is clearly correct. i.e. the path from N1 to Y is shorter than the path
via S-E
Pushpasis inequality
(ii) D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y)
provides the same result since D_opt(S,Y) has two cases
1) the path from S to Y doesn't traverse S-E, in which case Y is clearly
in extended P-space, since it is in fact in P-space, and the inequality
will always be met, since the direct path from Ni to Y will always be
shorter than the path via S, except in the case where the shortest path
actually traverses S. But this doesn't matter since in that case there
will always be another Ni (even if it is Y itself) for which this is not
the case. At least I THINK that is what Pushpasis is saying.
2) The path from S to Y DOES traverse S-E, in which case D_opt(S,Y) =
D_opt(S,E) + D_opt(E,Y), and hence inequality (ii) reduces to inequality
(i) as required.
However, I think the draft would benefit from some explanation of this.
Mike
On 28/10/2015 11:02, Pushpasis Sarkar wrote:
Hi Levente,
From: Levente Csikor <[email protected] <mailto:[email protected]>>
Date: Wednesday, October 28, 2015 at 2:04 PM
To: Pushpasis Sarkar <[email protected]
<mailto:[email protected]>>, "[email protected]
<mailto:[email protected]>" <[email protected] <mailto:[email protected]>>,
"[email protected] <mailto:[email protected]>"
<[email protected] <mailto:[email protected]>>
Subject: Re: New Version Notification for
draft-ietf-rtgwg-rlfa-node-protection-04.txt
Dear Pushpasis,
I agree with you with the previous observations, except the following
can not gracefully leave my mind :)
*[Pushpasis]As per RFC 7490.. Ext-P space(S, S-E) is a union of
P-space(S, S-E) and P-Space(all neighbors of S except E, S-E). In the
example you have chosen Y (later renamed to N2) is in P-Space(S, S-E)
though not in P-Space(N1, S-E). The inequality is a generalised
version that fits other scenarios. Even though the example chosen does
not seem to be a good one to demonstrate the use of this generalised
inequality, the inequality still does work even with this example. :)*
Tell me if I did not get your point, but according to your
inequalities, it seems that N2 being evaluated at first gives an
error, i.e.,
/
//"D_opt(N1, N2) < D_opt(N1,S) + D_opt(S,N2) is not satisfied//
// 2 1 1",/
so N2 is not in extended P-space (hereafter, always assume that
ext.P-space is considered w.r.t. the failed link).
However, as a second (or a further) step, when distance from N2 to N2
itself is evaluated, then
/"D_opt(N2, N2) < D_opt(N2,S) + D_opt(S,N2) is indeed satisfied//
// 0 //1// 1 "/
So, finally "somehow" N2 becomes the part of the extended P-space.
To me, it's still not clear for the following reasons:
i) from an implementation point of view, why should I evaluate the
distance from me, to myself (D_opt(N2,N2))? Isn't it an unnecessary
step that an algorithm should avoid.
*[Pushpasis]Like mentioned before an implementation needs to be
generic enough to handle all kinds of the topology example. If you can
suggest a better inequality I will be more than happy to accommodate
it the document. Please let me know if you have a better inequality in
your mind.*
ii) again, from an implementation point of view, and also according to
the algorithm proposed in RFC7490, if for each node (w.r.t. the failed
link) we store only a binary (boolean) variable to indicate whether it
is in the ext.P-space or not, then who guarantees that in the above
example the final state of this boolean variable of N2 will be True.
It's really typical (at least in usual programming languages ) that
traveling all the nodes in the graph more times, then you definitely
won't get the same order at each case.
So, what I want to tell here, that it could be the case that
"D_opt(N2, N2) < D_opt(N2,S) + D_opt(S,N2)" will be evaluated first
an N2 becomes the part of the ext.P-space, but at the end of the loop,
N2 won't be in the ext.P-space
*[Pushpasis] What you are trying to discuss here is more of like
implementation details. As a implementor I have implemented this for
the company I work for and am sure can be implemented using any
programming language. How to implement this should be outside the
scope of this document. However still here is a high-level algorithm
for your understanding.*
*
*
*For each node ‘X’ in the LSDB*
*- Set X.InExtPSpace ==> FALSE*
* - For each direct neighbor ’N’ in Neighbor-List*
* - If D_opt(N, X) < (D_opt(N,S) + D_opt(S,X) then *
* - Set X.InExtPspace ==> TRUE*
* - Continue to next node in LSDB*
* - EndFor*
*EndFor*
What is your opinion about this?
*[Pushpasis] Hope the above explanation helps clarifying things.*
*
*
*Thanks*
*-Pushpasis*
Regards,
Levente
On 10/27/2015 06:31 PM, Pushpasis Sarkar wrote:
Or, the statement should emphasize in the beginning that node Y is
not in the P-space of S w.r.t. the failed link S-E.
Pls tell me if I'm wrong.
Btw, the inequality for node-protecting extended P-space is valid.
*[Pushpasis] I think you might have misunderstood it.. Ni is not a
single neighbor of S.. The term Ni in the above inequality stands for
all neighbors of S other than E (primary next hop).. Here is the text
once more..*
*
*
"A node Y is in link-protecting extended P-space w.r.t to the link
(S-E) being protected, if and only if, there exists at least one
direct neighbor of S, Ni, other than primary nexthop E, that
satisfies the following condition.
D_opt(Ni,Y) < D_opt(Ni,S) + D_opt(S,Y)"
*So one possible value for Ni can be Y itself.. So now if you
substitute Y for Ni in the above inequality it satisfies the
inequality.. *
*
*
*D_opt(Y, Y) < D_opt(Y,S) + D_opt(S,Y)*
* 0 1 1*
*
*
*However to make it more clear let me rename the Nodes Ni and Y in
the above diagram as N1 and N2. So the diagram now looks like.. *
*
*
* N2
2/ \
N1--S--x--E
| /
B D
\ /
\ /
\ /
A
*
*
*
*Ni = {N1, N2}*
*
*
*Now with N2 as the candidate, *
*
*
*substituting Ni = N1*
*
*
*D_opt(N1, N2) < D_opt(N1,S) + D_opt(S,N2) is not satisfied*
* 2 1 1*
*
*
*However substituting Ni = N2*
*
*
*D_opt(N2, N2) < D_opt(N2,S) + D_opt(S,N2) is indeed satisfied*
* 0 1 1*
*
*
*So N2 is in link-protecting Ext-P-Space of S, wrt S-E link.*
*
*
*Essentially for Y to be in link-protected Extended P-Space(S, S-E) S
(or one of the neighbors of S other than E) should be able to reach Y
without taversing the S-E link.. The above inequality is satisfied by
substituting Ni as Y.*
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
