Patent ID: 8165121

Claim:
A method comprising: with a network device, selecting a primary next hop to use in forwarding network traffic from the network device to a destination network device in a network, and wherein selecting the primary next hop comprises selecting the primary next hop based on link-state routing information exchanged using a link-state routing protocol; with the network device, selecting an alternate next hop to use in forwarding network traffic from the network device to the destination in the event the primary next hop becomes unavailable, wherein a path to the destination device associated with the alternate next hop does not loop through the network device and wherein selecting the alternate next hop comprises selecting the alternate next hop based on the link-state routing information exchanged using the link-state routing protocol; receiving network traffic destined for the destination; and forwarding the network traffic using one of the primary next hop and the alternate next hop, wherein selecting the alternate next hop comprises: computing optimal distances from a plurality of neighboring devices of the network device to the network device, wherein a number of Shortest Path First (SPF) computations required for computing the optimal distances is independent of the number of neighboring devices in the network; identifying as candidate alternate next hops those neighboring devices having distances to the destination that are less than the sum of the optimal distance from the neighboring device to the network device and the optimal distance from the network device to the destination; storing the identified candidate alternate next hops and corresponding distances to the destination; and selecting the alternate next hop from among the stored candidate alternate next hops.