Subject: issue#2 in candidate-draft-ietf-rtgwg-remote-lfa-03.txt

From: Chris Bowers <[email-masked]>
Date: Tue, 29 Oct 2013 18:20:44 +0000

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-masked]]
Sent: Monday, October 28, 2013 9:33 AM
To: Chris Bowers; [email-masked]
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.