An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)
Extracted elements (30)
A stack of ears (ordered list of nodes) is used during GADAG construction so that nodes are processed in partial-order sequence. This guarantees that all ears connecting to a node are found before exploring ears from nodes higher in the partial order, ensuring correct direction assignment for every ear.
After initial GADAG construction, all remaining UNDIRECTED links are assigned directions based on a topological sort (Section 5.6). This augmentation provides shorter alternate paths and additional bandwidth for traffic on MRT alternates, reducing potential congestion compared to using only the links added during ear construction.
Cut-links are identified in the GADAG by being directed both INCOMING and OUTGOING simultaneously. For parallel cut-links, all parallel links are set to both directions so that either direction can serve as an alternate path when the other fails.
SPF (shortest-path first) is required for traversing the GADAG to compute blue and red next hops rather than an arbitrary traversal, because different traversal algorithms produce different next hops; SPF is mandated to ensure all routers produce consistent and interoperable MRT next hops.
The GADAG is computed once and reused to derive MRT next hops rooted at every node, rather than computing separate MRTs for each destination root. This is significantly faster and is enabled by using increasing-SPF (following OUTGOING links) and decreasing-SPF (following INCOMING links) on the common GADAG.
The MRT-FRR coverage guarantee of 100% single-failure recovery for 2-connected networks does not depend on link metrics, because the GADAG structure is based on graph topology alone. This decouples operator traffic-engineering via metrics from the fast-reroute coverage.
Whenever an ear endpoint is the GADAG root R, the ear is always directed away from R (R's interface is OUTGOING). This ensures exactly one node M exists as the largest predecessor of R, so the MRT-Red path for unordered node pairs never passes through R, preventing the intermediary nodes G and H from coinciding at R and breaking disjointness.
For IS-IS IP/LDP FRR, the mrt_node_id is the 7-octet neighbor system ID and pseudonode number from the Extended IS Reachability TLV (type 22) or Multi-Topology IS Neighbor TLV (type 222), and the metric is the 3-octet metric field from the same TLVs. For point-to-point links the pseudonode number (7th octet) is zero.
For OSPFv2, the mrt_node_id of a neighbor is the 4-octet Neighbor Router ID in the Link ID field of the corresponding point-to-point link in the Router-LSA, and the interface metric is the 2-octet Metric field for that link. For OSPFv3, the mrt_node_id is the 4-octet Neighbor Router ID field in the Router-LSA.
On broadcast networks, the pseudonode representing the broadcast LAN is included in the MRT Island and GADAG in place of individual broadcast interfaces. MRT next hops and alternates for broadcast failures are derived from this pseudonode representation as detailed in Section 7.
Parallel links between the same pair of nodes with the same metric are treated as equal by Interface_Compare (returning A_EQUAL_TO_B). The algorithm guarantees that all such parallel links receive the same direction in the final GADAG regardless of which one is explored first during DFS.
All routers in the MRT Island MUST select the same GADAG Root. The Default MRT Profile uses the GADAG Root Selection Policy from RFC 7812 Section 8.3 based on advertised priority values.
All routers MUST order interfaces identically using the Interface_Compare function: first by ascending metric, then by ascending mrt_node_id of the remote neighbor. Consistent ordering is required so that every router produces the same DFS tree, the same GADAG, and the same topological sort.
Initially, all interfaces MUST be set to UNDIRECTED before the GADAG construction begins. Direction (OUTGOING or INCOMING) is assigned during GADAG construction and augmentation.
Interface metrics MUST be compared as unsigned integers, and mrt_node_id comparisons MUST yield the same result as converting the IDs to unsigned integers in network byte order and comparing them as unsigned integers.
Pseudonodes MUST NOT be considered for GADAG root selection.
The MRT Lowpoint algorithm is required for implementation when the Default MRT Profile is implemented, as it is the algorithm defined for that profile to compute MRTs and MRT alternates.
When a broadcast interface is advertised as MRT-ineligible, the pseudonode representing that entire broadcast network MUST NOT be included in the MRT Island, effectively excluding all broadcast interfaces on that network.
A block is a maximal 2-connected cluster, a cut-link, or an isolated node. Any non-2-connected graph decomposes into blocks connected at cut-vertices; MRT computation builds ADAGs independently in each block and combines them into the GADAG.
An ear is a path whose interior nodes are not yet in the GADAG but whose two endpoints already are. Ears are added to the GADAG in a direction determined by the partial order of their endpoints: if X<<Y the ear goes from X toward Y; if X is the root or endpoints are unordered, the ear is directed away from the root.
MRT-Blue and MRT-Red are two Maximally Redundant Trees rooted at the GADAG root. Each spanning tree provides a path from every node to the root such that the two paths share the minimum number of nodes and links; shared nodes are cut-vertices and shared links are cut-links.
Proxy-nodes represent named prefixes (e.g., subnets) that cannot be transited. They are excluded from the GADAG construction but require separate MRT next-hop and alternate computation as described in Section 5.9.
The localroot of a node x is the cut-vertex (or GADAG root) in the same block that is closest to the GADAG root. Two nodes X and Y share a common block if and only if they share the same localroot, or one is the localroot of the other.
The Lowpoint value L(x) for a node x equals the minimum of D(x), the lowest DFS number reachable via a back-edge from x, and the lowest lowpoint value of any DFS tree child of x. It is used to identify cut-vertices (when a child c has L(c) >= D(x), x is a cut-vertex) and to find ears for GADAG construction.
The MRT Island is the set of routers reachable from the computing router via links that are in the same area/level, not IGP-excluded, not MRT-ineligible, and whose remote nodes support the given MRT profile. It is identified by breadth-first search from the computing router.
The MRT Lowpoint algorithm computes one Generalized Almost Directed Acyclic Graph (GADAG) from which a router derives its MRT-Blue and MRT-Red next hops to all destinations, and then selects alternates for each primary next hop. The GADAG encodes a partial order over network nodes relative to the GADAG root.
The order_proxy for a destination D is D itself if D is in the same block as the computing router, or the relevant cut-vertex on the path toward D if D is in a different block. It is used in Select_Alternates to compare the topological position of D relative to the failed next-hop F.
The Select_Alternates function determines for each primary next-hop node F toward destination D whether to use MRT-Blue or MRT-Red as the alternate. It uses the partial-order relationships (higher/lower flags) and topological order of F and D's order_proxy to make this determination, returning USE_BLUE, USE_RED, USE_RED_OR_BLUE, PRIM_NH_IS_D_OR_OP_FOR_D, or PRIM_NH_IN_DIFFERENT_BLOCK.
RFC 7811 does not introduce security mechanisms of its own; the security considerations for MRT-FRR are addressed in the companion architecture document RFC 7812. The algorithm operates on IGP topology information whose integrity depends on the security of the underlying IGP (OSPF or IS-IS).
Each interface in the GADAG is in one of three direction states: UNDIRECTED (initial), OUTGOING (directed away from the local router), or INCOMING (directed toward the local router). An interface may be both OUTGOING and INCOMING simultaneously, indicating it lies on a cut-link. Transitions occur during GADAG construction (Section 5.5) and augmentation (Section 5.6).