The text in section 4.2.1 and 4.2.2 describing the (unextended) P-space
calculation should be removed.
I agree with the Editor's note below in the comments for the
Compute_Extended_P_Space() function in the algorithm pseudocode that the "if
statement may be redundant since the foreach interface intf in self loop
catches all cases." That is, calculating (unextended) P-space is not needed.
The original algorithm text was written to mirror the existing description in
section 4.2.2.
" Another way to describe extended P-space is that it is the union of (
un-extended ) P-space and the set of destinations for which S has a
per-prefix LFA protecting the link S-E. i.e. the repair tunnel end
point can be reached either directly or using a per-prefix LFA."
If we are in agreement that the (unextended) P-space is not needed, then
sections 4.2.1 and 4.2.2 should be rewritten to eliminate or lessen the
importance of (unextended) P-space since it doesn't serve a useful purpose in
the text (except to motivate why it makes sense to use extended P-space.)
In particular, section 4.2.1 contains the following definition of a PQ-node:
"In Figure 1 the intersection of the E's Q-space with S's P-space
defines the set of viable repair tunnel end-points, known as "PQ nodes". "
This definition contradicts the definition of the PQ node in section 1.
"PQ node- A node which is a member of both the extended P-space
and the Q-space."
I am happy to provide new text for sections 4.2.1 and 4.2.2 if we are in basic
agreement on this.
Chris
From: Stewart Bryant [mailto:[email protected]]
Sent: Monday, October 28, 2013 9:33 AM
To: Chris Bowers; [email protected]
Subject: Re: algorithm description for draft-ietf-rtgwg-remote-lfa
Please see notes inline.
Here is the current candidate algorithm text. I added lots of
comments for my personal checking of the algorithm
and my guess is that they will be of use to reader and
reviewers further down the line.
Once this is correct we will need to add a glossary of terms.
4.3. A Cost Based RLFA Algorithm
The preceding text has mostly described the computation of the
remote LFA repair point (PQ) in terms of the intersection of two
reachability graphs computed using SPFs. This section describes a
method of computing the repair point using a cost based algorithm.
The pseudo-code provides in this section avoids unnecessary SPF
computations, but for the sake of readability, it does not otherwise
try to optimize the code. Unconventionally, but for clarity, we
provide the main algorithm followed its procedures. In this
description D_opt(a,b) is the shortest distance from node a to node b
as computed by the SPF.
////////////////////////////////////////////////////////////////////
//
// We have already computed the forward SPF from self to all nodes
// y in network and thus we know D_opt (self, y). This is needed
// for normal forwarding.
// However for completeness.
Compute_and_Store_Forward_SPF(self)
// To extend P-space we compute the SPF at each neighbour except the
// neighbour that is reached via the link being protected.
// We will also need D_opt(fail_intf.remote_node,y) so compute that
// at the same time.
Compute_Neighbor_SPFs()
// Compute the set of nodes {P} reachable other than via the
// failed link
Compute_Extended_P_Space()
// Compute the set of nodes that can reach the node on the far side
// of the failed link without traversing the failed link.
Compute_Q_Space()
// Compute the set of candidate RLFA tunnel endpoints
Bryant, et al. Expires May 01, 2014 [Page 8]
Internet-Draft Remote LFA FRR October 2013
Intersect_Extended_P_and_Q_Space()
// Make sure that we cannot get looping repairs when the
// failure is worse than expected.
if (guarantee_no_looping_on_worse_than_protected_failure)
Apply_Downstream_Constraint()
/////////////////////////////////////////////////////////////////////
//
// This computes the SPF from root, and stores stores the optimum
// distance from root to each node y
Compute_and_Store_Forward_SPF(root)
Compute_Forward_SPF(root)
foreach node y in network
store D_opt(root,y)
/////////////////////////////////////////////////////////////////////
//
// This computes the optimum distance from each neighbour (other than
// the neighbour reachable through the failed link) and every other
// node in the network
Compute_Neighbor_SPFs()
foreach interface intf in self
Compute_and_Store_Forward_SPF(intf.remote_node)
/////////////////////////////////////////////////////////////////////
//
// The reverse SPF computes the cost from each remote node to root.
// This is acheived by running the normal SPF algorithm, but using the
// link cost in the direction from the next hop back towards root
// in place of the link cost in the direction away from root towards
// the next hop.
Compute_and_Store_Reverse_SPF(root)
Compute_Reverse_SPF(root)
foreach node y in network
store D_opt(y,root)
Bryant, et al. Expires May 01, 2014 [Page 9]
Internet-Draft Remote LFA FRR October 2013
/////////////////////////////////////////////////////////////////////
//
// Calculate P space and then extend it by the P-spaces of each
// neighbour other than the one reachable via the link being
// protected. Note the strictly less than operator is needed to
// avoid ECMP issues.
Compute_Extended_P_Space()
foreach node y in network
y.in_extended_P_space = false
// Compute P-space
//
// Editor's note, I think that this if statement may be
// redundent since the foreach interface intf in self loop
// catches all cases.
//
// Editor's note D_opt(fail_intf.remote_node,y) requires an
// SPF from neighbour fail_intf.remote_node so did this as
// part of all neighbours SPF calculation
if (D_opt(self, y) <
D_opt(self, fail_intf.remote_node) +
D_opt(fail_intf.remote_node,y))
y.in_extended_P_space = true
// Extend P-space to the P-spaces of all reachable
// neighbours
foreach interface intf in self
if (intf.remote_node != fail_intf.remote_node)
if ( D_opt(intf.remote_node, y) <
D_opt(intf.remote_node, self) +
D_opt(self,fail_intf.remote_node) +
D_opt(fail_intf.remote_node,y) )
y.in_extended_P_space = true
/////////////////////////////////////////////////////////////////////
//
Compute_Q_Space()
// Compute the cost from every node the network to the
// node normally reachable across the failed link
Compute_and_Store_Reverse_SPF(fail_intf.remote_node)
// Compute the cost from every node the network to self
Compute_and_Store_Reverse_SPF(self)
foreach node y in network
if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) +
Bryant, et al. Expires May 01, 2014 [Page 10]
Internet-Draft Remote LFA FRR October 2013
D_opt(self,fail_intf.remote_node) )
y.in_Q_space = true
else
y.in_Q_space = false
/////////////////////////////////////////////////////////////////////
//
// Compute set of nodes in both extended P-space and in Q-space
Intersect_Extended_P_and_Q_Space()
foreach node y in network
if ( y.in_extended_P_space && y.in_Q_space )
y.valid_tunnel_endpoint = true
else
y.valid_tunnel_endpoint = false
/////////////////////////////////////////////////////////////////////
//
// A downstream route is one where the next hop is strictly
// closer to the destination. By sending the packet to a
// PQ node that is downstream, we know that if the PQ node
// detects a failure, it will not loop the packet back to self.
// This is useful when there are two failures, or a node has
// failed rather than a link.
Apply_Downstream_Constraint()
foreach node y in network
if (y.valid_tunnel_endpoint)
Compute_and_Store_Forward_SPF(y)
if ((D_opt(y,dest) < D_opt(self,dest))
y.valid_tunnel_endpoint = true
else
y.valid_tunnel_endpoint = false
//
/////////////////////////////////////////////////////////////////////
Please can someone verify that the algorithm is correct. See from
the text below that I thought that the original missed some
SPFs
---------
Rest of thread removed to keep below 50kB.
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
