EFFICIENT IDENTIFICATION OF NODE PROTECTION REMOTE LFA TARGET

摘要

A method is implemented by a network device to improve efficiency of computing a node-protecting remote loop-free alternate (LFA) in a network topology graph. The method computes a reverse shortest path first (SPF) algorithm rooted at the primary next hop node, where the reverse SPF algorithm rooted at the primary next hop maintains a reverse path of a shortest path computed by the reverse SPF algorithm rooted at the primary next hop node. The method selects a node that is in both the source node's node-protecting extended P-space that protects the primary next hop node and the primary next hop node's link-protecting Q-space that protects the S-E link. The method traverses the reverse path of the shortest path computed by the reverse SPF algorithm rooted at the primary next hop node starting from the selected node and towards the primary next hop node and assigns the selected node as a node- protecting remote LFA for each S-E destination node visited along the traversal of the reverse path that has not been assigned a node-protecting remote LFA.