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
On 04/09/2013 22:21, Chris Bowers wrote:
As has been pointed out in other email threads,
the current version of draft-ietf-rtgwg-remote-lfa-02.txt
lacks a formal description of the algorithm being proposed.
Below is a such a formal algorithm description, based on my
reading of the current draft. It would help progress this
draft forward if the authors would correct any errors
in this pseudo-code representation of the algorithm.
The pseudo-code below avoids unnecessary SPF computations, but
for the sake of readability, it does not otherwise try to
optimize the code.
Remote LFA algorithm
Compute_and_Store_Forward_SPF(node root)
Compute_Forward_SPF(root)
foreach node z in network
store D_opt(root,z)
Compute_and_Store_Reverse_SPF(node root)
Compute_Reverse_SPF(root)
foreach node z in network
store D_opt(z,root)
Compute_Neighbor_SPFs()
foreach interface intf in self
if (intf.remote_node != fail_intf.remote_node)
Compute_and_Store_Forward_SPF(intf.remote_node)
SB> Later on we need D_opt(fail_intf.remote_node,y)
SB> The restriction if (intf.remote_node != fail_intf.remote_node)
SB> prevents this calculation.I have therefore removed the
SB> restriction in the text.
Compute_Extended_P_Space()
foreach node y in network
y.in_extended_P_space = false
SB> This first calculation is P_space and since the first hop is
SB> forced, there in no ECMP issue, and so you can go to an equals
SB> operator. I think the preference for less than arises from the
SB> forwarding code in some implementations that might do the
SB> ECMP by mistake.
SB> Also why isn't it adequate to compute the union of the P space
SB> of the neighbours, since by definition packet must go through a
SB> neighbour?
SB>
SB> In other words can't the following if statement be removed?
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
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_and_Store_Reverse_SPF(fail_intf.remote_node)
foreach node y in network
if ( D_opt(y,fail_intf.remote_node) < D_opt(y,self) +
SB> D_opt(y,self) needs
SB> Compute_and_Store_Reverse_SPF(self)
D_opt(self,fail_intf.remote_node) )
y.in_Q_space = true
else
y.in_Q_space = false
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
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
Compute_Neighbor_SPFs()
SB> you need the reverse SPF before here as you need the result in
SB> the extended p-space calculation
Compute_Extended_P_Space()
Compute_Q_Space()
Intersect_Extended_P_and_Q_Space()
if (guarantee_no_looping_on_worse_than_protected_failure)
Apply_Downstream_Constraint()
**********
I would also like to propose that the following text to be
inserted after the last paragraph of
section 4.2.1. "Computing Repair Paths".
It should be noted that using the Q-space of E as a proxy for the Q-space
of each destination can result in failing to identify valid remote LFAs.
The extent to which this reduces the effective protection coverage is
topology dependent.
***********
SB> Added
Thanks,
Chris
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
--
For corporate legal information go to:
http://www.cisco.com/web/about/doing_business/legal/cri/index.html
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
