Subject: RE: algorithm description for draft-ietf-rtgwg-remote-lfa

From: Chris Bowers <[email-masked]>
Date: Thu, 10 Oct 2013 16:59:59 +0000

Stewart proposed in another thread making this algorithm text part of an appendix (see snippet below.)  I want to emphasize the importance of adding more quantitative content to the normative sections of the text, by illustrating an example of the confusion created by some of the current text.

Today I was in a discussion regarding the criteria for evaluating for use as a tunnel endpoint, a node Y in extended-P space which is reachable from source S by way of S's neighbor N1.  Some confusion arose during the discussion over whether or not the node Y should be rejected for consideration if policy had been applied rejecting N1 as a (local)LFA for reaching Y.  We agreed that the evaluation of Y as a tunnel endpoint for remote LFA should not depend on the policy applied to the (local)LFA to reach Y.

However, the text below in section 4.2.2 leads to confusion on this point.

"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 think this text should be removed and replaced with precise quantitative criteria for membership in extended P-space.  It is likely that remote LFA will be deployed together with (local)LFA with policy determining which type of alternate to use (draft-litkowski-rtgwg-lfa-manageability).  Describing remote LFA in terms of (local)LFA will create confusion for someone trying to apply policy. Quantitative criteria avoid this confusion.

If this text creates such confusion among experts, it is likely to create even more confusion among end-users of the technology, when trying to figure out what is really going on in their network.  While one might argue that this behavior is up to the vendor to document, confusing text in the base rlfa draft will make that task much more difficult.
---------
A response to this algorithm text showed up in another thread so I am cutting
and pasting Stewart Bryant's response from 10/2/13 to this thread to keep things organized.

[SB] "I plan to put in the algorithm text, although having discussed
this with Mike, our inclination is to include this as an
appendix since it is not required for interoperability that
you do the computation that way."
---------

Chris

From: [email-masked] [mailto:[email-masked]] On Behalf Of Chris Bowers
Sent: Wednesday, September 04, 2013 4:22 PM
To: [email-masked]
Subject: algorithm description for draft-ietf-rtgwg-remote-lfa

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)

Compute_Extended_P_Space()
    foreach node y in network
        y.in_extended_P_space = false
        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) +
                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()
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.

***********

Thanks,
Chris

---

From: <[email-masked]>
Date: Fri, 11 Oct 2013 15:29:59 +0200

Completely agree with Chris.

Moreover having the algorithm part described clearly inside the main paragraphs of the document rather than the appendix is completely inline with what has been done for basic LFA specification (RFC 5286 Paragraph 3.6 - Selection procedure).

As mentioned by Chris, it is important to mention that rLFA alternate must not be dependant on any direct LFA selection. rLFA must be able to rely on any LFA (Extended P Space) whatever this LFA is best or not.

Stephane

De : [email-masked] [mailto:[email-masked]] De la part de Chris Bowers
Envoyé : jeudi 10 octobre 2013 19:00
À : [email-masked]
Objet : RE: algorithm description for draft-ietf-rtgwg-remote-lfa

---------

Chris

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]] On Behalf Of Chris Bowers
Sent: Wednesday, September 04, 2013 4:22 PM
To: [email-masked]<mailto:[email-masked]>
Subject: algorithm description for draft-ietf-rtgwg-remote-lfa

Remote LFA algorithm

Compute_Neighbor_SPFs()

Compute_Q_Space()

Compute_Neighbor_SPFs()

**********

***********

Thanks,
Chris

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 28 Oct 2013 14:32:59 +0000

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 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

       // Make sure that we cannot get looping repairs when the
       // failure is worse than expected.

       /////////////////////////////////////////////////////////////////////
       //
       // 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()

       /////////////////////////////////////////////////////////////////////
       //
       // 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)

Bryant, et al.            Expires May 01, 2014                 [Page 10]

Internet-Draft               Remote LFA FRR                 October 2013

       /////////////////////////////////////////////////////////////////////
       //
       // Compute set of nodes in both extended P-space and in Q-space

       /////////////////////////////////////////////////////////////////////
       //
       // 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.

    //
    /////////////////////////////////////////////////////////////////////

Please can someone verify that the algorithm is correct. See from
the text below that I thought that the original missed some
SPFs

> 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.

>         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(y,fail_intf.remote_node) < D_opt(y,self) +
SB> D_opt(y,self) needs
SB> Compute_and_Store_Reverse_SPF(self)
>                 y.valid_tunnel_endpoint = false
SB> you need the reverse SPF before here as you need the result in
SB> the extended p-space calculation

>     Apply_Downstream_Constraint()
SB> Added

> Thanks,
> Chris
>
>
> _______________________________________________
> rtgwg mailing list
> [email-masked]
> 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

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 28 Oct 2013 18:27:45 +0000

On 11/10/2013 14:29, [email-masked] wrote:
> Moreover having the algorithm part described clearly inside the main 
> paragraphs of the document rather than the appendix is completely 
> inline with what has been done for basic LFA specification (RFC 5286 
> Paragraph 3.6 -- Selection procedure).
>
> As mentioned by Chris, it is important to mention that rLFA alternate 
> must not be dependant on any direct LFA selection. rLFA must be able 
> to rely on any LFA (Extended P Space) whatever this LFA is best or not.
>
See version 3 was soon as I can find a home for it and please propose an 
exact change

Stewart

> Stephane
>
> *De :[email-masked] [mailto:[email-masked]] *De la 
> part de* Chris Bowers
> *Envoyé :* jeudi 10 octobre 2013 19:00
> *À :* [email-masked]
> *Objet :* RE: algorithm description for draft-ietf-rtgwg-remote-lfa
>
> Stewart proposed in another thread making this algorithm text part of 
> an appendix (see snippet below.)  I want to emphasize the importance 
> of adding more quantitative content to the normative sections of the 
> text, by illustrating an example of the confusion created by some of 
> the current text.
>
> Today I was in a discussion regarding the criteria for evaluating for 
> use as a tunnel endpoint, a node Y in extended-P space which is 
> reachable from source S by way of S's neighbor N1.  Some confusion 
> arose during the discussion over whether or not the node Y should be 
> rejected for consideration if policy had been applied rejecting N1 as 
> a (local)LFA for reaching Y.  We agreed that the evaluation of Y as a 
> tunnel endpoint for remote LFA should not depend on the policy applied 
> to the (local)LFA to reach Y.
>
> I think this text should be removed and replaced with precise 
> quantitative criteria for membership in extended P-space.  It is 
> likely that remote LFA will be deployed together with (local)LFA with 
> policy determining which type of alternate to use 
> (draft-litkowski-rtgwg-lfa-manageability).  Describing remote LFA in 
> terms of (local)LFA will create confusion for someone trying to apply 
> policy. Quantitative criteria avoid this confusion.
>
> If this text creates such confusion among experts, it is likely to 
> create even more confusion among end-users of the technology, when 
> trying to figure out what is really going on in their network.  While 
> one might argue that this behavior is up to the vendor to document, 
> confusing text in the base rlfa draft will make that task much more 
> difficult.
>
> ---------
>
> *From:[email-masked] <mailto:[email-masked]> 
> [mailto:[email-masked]] *On Behalf Of *Chris Bowers
> *Sent:* Wednesday, September 04, 2013 4:22 PM
> *To:* [email-masked] <mailto:[email-masked]>
> *Subject:* algorithm description for draft-ietf-rtgwg-remote-lfa
>