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

From: Chris Bowers <[email-masked]>
Date: Wed, 4 Sep 2013 21:21:52 +0000

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