This is an RFC on how to select the “next hop” for fast reroute protections. The default next hop is called “primary” and therefore the one used for fast reroute is called “alternate” next hop. The alternate next hop is not necessary to be in the shortest path, but it has to be loop-free. This RFC defines the term, loop-free alternate (LFA) to represent these nodes.
Considering a source \(S\) and a destination \(D\). Let the shortest-path distance between two nodes denoted by \(d(X,Y)\). The neighbour of \(S\), node \(N\), is a loop-free neighbour for \(S\) to \(D\) if the following inequality is satisfied: \(d(N,D) < d(N,S) + d(S,D).\)
Moreover, if a node \(N\) is a downstream of the path from \(S\) to \(D\), it must satisfy the downstream path criteron: \(d(N,D) < d(S,D).\)
Now we found the following:
- An LFA must satisfy the loop-free condition \(d(N,D) < d(N,S) + d(S,D)\)
- An LFA node \(N\) that is protecting node \(E\) from failure must satisfy the node-protecting criteria \(d(N,D) < d(N,E)+d(E,D)\). This is to mean that node \(N\) must not traverse node \(E\)
- In order for a LFA to protect the failure of a non-broadcast multi-access link, we model the NBMA link as a pseudonode and do node-protection against it
The RFC drafts the way to find an LFA for a primary next-hop so that it can do protection by fast reroute. The selection is done by a router and prefers node-protecting over link-protecting LFAs. The algorithm is as follows. Here we defines
- \(S\) and \(D\) to be the source and destination routers
- \(N_1\) to \(N_j\) to be the neighbours of \(S\)
- A next hop is defined as a 2-tuple: (outgoing-link, neighbour)
- \(H_1\) to \(H_k\) to be the candidate next hops
- \(P_1\) to \(P_p\) to be primary next hops
and the objective is to find an LFA for \(P_i\)
P_i.alt_next_hops := {}
P_i.alt_type := NONE
P_i.alt_link-protect := FALSE
P_i.alt_node-protect := FALSE
P_i.alt_srlg-protect := {}
for each H_h in H_1, ..., H_k:
cand_type := NONE
cand_link_protect := FALSE
cand_node_protect := FALSE
cand_srlg_protect := {}
next if H_h == P_i
if (H_h.link is administratively allowed to be used as an alternate
AND cost(H_h.link) < maximum
AND reverse_cost(H_h) < maximum
AND H_h.neighbor is not overloaded (for IS-IS)
AND H_h.link is bidirectional)
then
H_h can be considered as an alternate
else
next H_h
if d(H_h.neighbor, D) >= d(H_h.neighbor, S) + d(S, D) then
next H_h as it is not loop-free
else
cand_type = LOOP-FREE.
if H_h is a primary next-hop then
card_type = PRIMARY
if H_h.link != P_i.link then
card_link-protect := TRUE
if d(H_h.neighbor, D) < d(H_h.neighbor, P_i.neighbor) + d(P_i.neighbor, D) then
cand_node-protect := TRUE.
if the router considers SRLGs, then
cand_srlg-protect := SRLGs traversed on the path from S via P_i.link to P_i.neighbor
Remove from card_srlg-protect the SRLGs to which H_h belongs
Remove from cand_srlg-protect the SRLGs traversed on the path from H_h.neighbor to D
/* Now cand_srlg-protect holds the SRLGs to which P_i belongs
and that are not traversed on the path from S via H_h to D. */
if (cand_type == PRIMARY
AND the router prefers other primary next-hops for use as the alternate
AND P_i.alt_type != PRIMARY)
then
goto DONE
if (cand_type != PRIMARY
AND P_i.alt_type == PRIMARY
AND the router prefers other primary next-hops for use as the alternate)
then
next H_h
if (cand_node_protect == TRUE
AND P_i.alt_node_protect == FALSE)
then
goto DONE
if (cand_link_protect == TRUE AND P_i.alt_link_protect == FALSE) then
goto DONE
if (cand_srlg_protect contains P_i.alt_srlg_protect) then
goto DONE
if (cand_srlg_protect != P_i.alt_srlg_protect) then
select between H_h and P_i.alt_next_hops based upon distance, IP addresses
if H_h is preferred then
goto DONE
else if P_i.alt_next_hops is preferred then
next H_h
if ( d(H_h.neighbor, D) < d(S, D)
AND d(P_i.alt_next_hops, D) >= d(S, D) )
then
/* now H_h is a downstream alternate
P_i.alt_next_hops is simply an LFA, H_h is preferred */
goto DONE
if (H_h is preferred to P_i.alt_next_hops based upon alternate types, distances, etc) then
goto DONE
if (P_i.alt_next_hops is preferred to H_h) then
next H_h
P_i.alt_next_hops := UNION(P_i.alt_next_hops, H_h)
P_i.alt_type := Better of H_h.alt_type and P_i.alt_type
next H_h
DONE:
P_i.alt_next_hops := {H_h}
P_i.alt_type := cand_type
P_i.alt_link_protect := cand_link_protect
P_i.alt_node_protect := cand_node_protect
P_i.alt_srlg_protect := cand_srlg_protect
Bibliographic data
@misc{
title = "Basic Specification for IP Fast Reroute: Loop-Free Alternates",
author = "A. Atlas and A. Zinin",
howpublished = "RFC5286",
year = "2008",
}