I think this just goes to show how confusing the distance based
definitions of this stuff can be! While I agree that an implementation
may use those techniques, I find it MUCH simpler to understand using the
traditional definitions.
Mike
On 28/10/2015 12:47, Pushpasis Sarkar wrote:
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] <mailto:[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.*
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
