Hi Mike and Levente,
The inequality for extended-P-space in this document is same as the
one mentioned in section 5.3 of RFC7490. Here is the excerpt…
“
/////////////////////////////////////////////////////////////////
//
// Calculate Extended P-space
//
// Note that the "strictly less than" operator is needed to
// avoid ECMP issues.
Compute_Extended_P_Space(fail_intf)
foreach node y in network
y.in_extended_P_space = false
// Extend P-space to the P-spaces of all reachable
// neighbors
foreach interface intf in self
// Exclude failed interface, noting that
// the node reachable via that interface may be
// reachable via another interface (parallel path)
if (intf != fail_intf)
foreach neighbor n in intf.remote_node
// Apply RFC 5286 Inequality 1
*if ( D_opt(n, y) < D_opt(n,self) + D_opt(self, y))
y.in_extended_P_space = true*
“
I don’t see why there will be any confusion.
Thanks
-Pushpasis
From: Mike Shand <[email protected]>
Date: Wednesday, October 28, 2015 at 5:26 PM
To: Pushpasis Sarkar <[email protected]
<mailto:[email protected]>>, Levente Csikor <[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
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.*
