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
_______________________________________________
rtgwg mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/rtgwg
