Patent ID: 9479424
Filing Date: 2016-10-25
CPC Classification: H04L

Claim Text:
1. A method executed by a network device to calculate loop free alternative (LFA) for nodes in an intermediate system-intermediate system (IS-IS) area or IS-IS domain where the network device is connected with other nodes via multiple parallel links, where shortest path first (SPF) of the primary paths for the network device tracks directly connected links from each node in the IS-IS area or IS-IS domain to the network device which is a source node for the SPF, the method comprising the steps of: adding, by the network device, the source node to a candidate list with a cost of zero; selecting a least cost candidate node from the candidate list; selecting a next link of the selected candidate node; checking whether the selected candidate node is the source node; saving the selected link in a neighbor data structure as an equal cost multi-path (ECMP) directly connected link for a node connected to other end of the selected link, where the selected candidate node is the source node; checking whether the node connected to the other end of the selected link is in a permanent tree that is a SPF tree; checking whether the node at the other end of the selected link is in the candidate list, where the node at the other end of selected link is not in the permanent tree; adding the node connected to the other end of the selected link to the candidate list, where the node connected to the other end of the selected link is not in the candidate list; checking whether a cost of the selected candidate node plus a cost of the selected link is less than a cost of the node at the other end of the selected link, where the node at the other end of the link is in the candidate list; updating the cost of the node at the other end of the selected link to the cost of the selected candidate plus the cost of the selected link, where the cost of the selected candidate node plus the cost of the selected link is less than the cost of the node at the end of the selected link; setting the selected link as next hop of the node at the other end of the selected link, where the selected candidate node is the source node; inheriting a selected candidate next hop to the node at the other end of the selected link, where the selected candidate node is not the source node; moving the selected candidate node to the permanent tree, where all links of the selected candidate node have been processed; iterating through the above steps for each candidate node in the candidate list and each link of each candidate node; and computing at least one LFA to a destination node in the IS-IS area or IS-IS domain using the directly connected links in the neighbor data structure where the selected link in the LFA conforms to back up eligibility.