# An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)

Pages: 118
Proposed Standard

```5.  MRT Lowpoint Algorithm Specification

The MRT Lowpoint algorithm computes one GADAG that is then used by a
router to determine its MRT-Blue and MRT-Red next hops to all
destinations.  Finally, based upon that information, alternates are
selected for each next hop to each destination.  The different parts
of this algorithm are described below.

o  Order the interfaces in the network graph.  See Section 5.1.

o  Compute the local MRT Island for the particular MRT Profile.  See
Section 5.2.

o  Select the root to use for the GADAG.  See Section 5.3.

o  Initialize all interfaces to UNDIRECTED.  See Section 5.4.

o  Compute the DFS value, e.g., D(x), and lowpoint value, L(x).  See
Figure 8.

o  Construct the GADAG.  See Section 5.5.

o  Assign directions to all interfaces that are still UNDIRECTED.
See Section 5.6.

o  From the computing router x, compute the next hops for the MRT-
Blue and MRT-Red.  See Section 5.7.

o  Identify alternates for each next hop to each destination by
determining which one of the MRT-Blue and the MRT-Red the
computing router x should select.  See Section 5.8.

A Python implementation of this algorithm is given in Appendix A.

5.1.  Interface Ordering

To ensure consistency in computation, all routers MUST order
interfaces identically down to the set of links with the same metric
to the same neighboring node.  This is necessary for the DFS in
Lowpoint_Visit in Section 4.3, where the selection order of the
interfaces to explore results in different trees.  Consistent
interface ordering is also necessary for computing the GADAG, where
the selection order of the interfaces to use to form ears can result
in different GADAGs.  It is also necessary for the topological sort
described in Section 5.8, where different topological sort orderings
can result in undirected links being added to the GADAG in different
directions.
```
```   The required ordering between two interfaces from the same router x
is given in Figure 14.

Interface_Compare(interface a, interface b)
if a.metric < b.metric
return A_LESS_THAN_B
if b.metric < a.metric
return B_LESS_THAN_A
if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
return A_LESS_THAN_B
if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
return B_LESS_THAN_A
// Same metric to same node, so the order doesn't matter for
// interoperability.
return A_EQUAL_TO_B

Figure 14: Rules for Ranking Multiple Interfaces (Order Is from Low
to High)

In Figure 14, if two interfaces on a router connect to the same
remote router with the same metric, the Interface_Compare function
returns A_EQUAL_TO_B.  This is because the order in which those
interfaces are initially explored does not affect the final GADAG
produced by the algorithm described here.  While only one of the
links will be added to the GADAG in the initial traversal, the other
parallel links will be added to the GADAG with the same direction
assigned during the procedure for assigning direction to UNDIRECTED
links described in Section 5.6.  An implementation is free to apply
some additional criteria to break ties in interface ordering in this
situation, but those criteria are not specified here since they will
not affect the final GADAG produced by the algorithm.

The Interface_Compare function in Figure 14 relies on the
interface.metric and the interface.neighbor.mrt_node_id values to
order interfaces.  The exact source of these values for different
IGPs and applications is specified in Figure 15.  The metric and
mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is
normative.  The metric and mrt_node_id values for IS-IS Path Control
and Reservation (PCR) in this table should be considered
informational.  The normative values are specified in [IEEE8021Qca].
```
```  +--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id           | metric of                   |
| protocol     | of neighbor           | interface                   |
| and          | on interface          |                             |
| application  |                       |                             |
+--------------+-----------------------+-----------------------------+
| OSPFv2 for   | 4-octet Neighbor      | 2-octet Metric field        |
| IP/LDP FRR   | Router ID in          | for corresponding           |
|              | Link ID field for     | point-to-point link         |
|              | corresponding         | in Router-LSA               |
|              | point-to-point link   |                             |
|              | in Router-LSA         |                             |
+--------------+-----------------------+-----------------------------+
| OSPFv3 for   | 4-octet Neighbor      | 2-octet Metric field        |
| IP/LDP FRR   | Router ID field       | for corresponding           |
|              | for corresponding     | point-to-point link         |
|              | point-to-point link   | in Router-LSA               |
|              | in Router-LSA         |                             |
+--------------+-----------------------+-----------------------------+
| IS-IS for    | 7-octet neighbor      | 3-octet metric field        |
| IP/LDP FRR   | system ID and         | in Extended IS              |
|              | pseudonode number     | Reachability TLV (type 22)  |
|              | in Extended IS        | or Multi-Topology           |
|              | Reachability TLV (type| IS Neighbor TLV (type 222)  |
|              | 22) or Multi-Topology |                             |
|              | IS Neighbor TLV (type |                             |
|              | 222)                  |                             |
+--------------+-----------------------+-----------------------------+
| IS-IS PCR for| 8-octet Bridge ID     | 3-octet SPB-LINK-METRIC in  |
| protection   | created from  2-octet | SPB-Metric sub-TLV (type 29)|
| of traffic   | Bridge Priority in    | in Extended IS Reachability |
| in bridged   | Shortest Path Bridging| TLV (type 22) or            |
|              |SPB Instance sub-TLV   | Multi-Topology              |
| networks     | (type 1) carried in   | Intermediate Systems        |
|              | MT-Capability TLV     | TLV (type 222).  In the case|
|              | (type 144) and 6-octet| of asymmetric link metrics, |
|              | neighbor system ID in | the larger link metric      |
|              | Extended IS           | is used for both link       |
|              | Reachability TLV (type| directions.                 |
|              | 22) or Multi-Topology | (informational)             |
|              | Intermediate Systems  |                             |
|              | TLV (type 222)        |                             |
|              | (informational)       |                             |
+--------------+-----------------------+-----------------------------+

Figure 15: Value of interface.neighbor.mrt_node_id and
interface.metric to Be Used for Ranking Interfaces, for Different
Flooding Protocols and Applications
```
```   The metrics are unsigned integers and MUST be compared as unsigned
integers.  The results of mrt_node_id comparisons MUST be the same as
would be obtained by converting the mrt_node_ids to unsigned integers
using network byte order and performing the comparison as unsigned
integers.  In the case of IS-IS for IP/LDP FRR with point-to-point
links, the pseudonode number (the 7th octet) is zero.  Broadcast
interfaces will be discussed in Section 7.

5.2.  MRT Island Identification

The local MRT Island for a particular MRT profile can be determined
by starting from the computing router in the network graph and doing
a breadth-first-search (BFS).  The BFS explores only links that are
in the same area/level, are not IGP-excluded, and are not MRT-
ineligible.  The BFS explores only nodes that support the particular
MRT profile.  See Section 7 of [RFC7812] for more-precise definitions
of these criteria.

MRT_Island_Identification(topology, computing_rtr, profile_id, area)
for all routers in topology
rtr.IN_MRT_ISLAND = FALSE
computing_rtr.IN_MRT_ISLAND = TRUE
explore_list = { computing_rtr }
while (explore_list is not empty)
for each intf in next_rtr
if (not intf.IN_MRT_ISLAND
and not intf.MRT-ineligible
and not intf.remote_intf.MRT-ineligible
and not intf.IGP-excluded and (intf in area)
and (intf.remote_node supports profile_id) )
intf.IN_MRT_ISLAND = TRUE
intf.remote_intf.IN_MRT_ISLAND = TRUE
if (not intf.remote_node.IN_MRT_ISLAND))
intf.remote_node.IN_MRT_ISLAND = TRUE

Figure 16: MRT Island Identification

5.3.  GADAG Root Selection

In Section 8.3 of [RFC7812], the GADAG Root Selection Policy is
described for the Default MRT Profile.  This selection policy allows
routers to consistently select a common GADAG Root inside the local
MRT Island, based on advertised priority values.  The MRT Lowpoint
algorithm simply requires that all routers in the MRT Island MUST
select the same GADAG Root; the mechanism can vary based upon the MRT
profile description.  Before beginning computation, the network graph
```
```   is reduced to contain only the set of routers that support the
specific MRT profile whose MRTs are being computed.

As noted in Section 7, pseudonodes MUST NOT be considered for GADAG
root selection.

It is expected that an operator will designate a set of routers as
good choices for selection as GADAG root by setting the GADAG Root
Selection Priority for that set of routers to lower (more preferred)
numerical values.  For guidance on setting the GADAG Root Selection
Priority values, refer to Section 9.1.

5.4.  Initialization

Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFS-values,
lowpoint-values, DFS parents, lowpoint-parents, any MRT-computed next
hops, and flags associated with algorithm.

It is assumed that a regular SPF computation has been run so that the
primary next hops from the computing router to each destination are
known.  This is required for determining alternates at the last step.

Initially, all interfaces MUST be initialized to UNDIRECTED.  Whether
they are OUTGOING, INCOMING, or both is determined when the GADAG is
constructed and augmented.

It is possible that some links and nodes will be marked using
standard IGP mechanisms to discourage or prevent transit traffic.
Section 7.3.1 of [RFC7812] describes how those links and nodes are
excluded from MRT Island formation.

MRT-FRR also has the ability to advertise links MRT-Ineligible, as
described in Section 7.3.2 of [RFC7812].  These links are excluded
from the MRT Island and the GADAG.  Computation of MRT next hops will
therefore not use any MRT-ineligible links.  The MRT Lowpoint
algorithm does still need to consider MRT-ineligible links when
computing FRR alternates, because an MRT-ineligible link can still be
the shortest-path next hop to reach a destination.

When a broadcast interface is advertised as MRT-ineligible, then the
pseudonode representing the entire broadcast network MUST NOT be
included in the MRT Island.  This is equivalent to excluding all of
the broadcast interfaces on that broadcast network from the MRT
Island.
```
```5.5.  Constructing the GADAG Using Lowpoint Inheritance

As discussed in Section 4.2, it is necessary to find ears from a node
x that is already in the GADAG (known as IN_GADAG).  Two different
methods are used to find ears in the algorithm.  The first is by
going to a DFS-child that is not IN_GADAG and then following the
chain of lowpoint parents until an IN_GADAG node is found.  The
second is by going to a neighbor that is not IN_GADAG and then
following the chain of DFS parents until an IN_GADAG node is found.
As an ear is found, the associated interfaces are marked based on the
direction taken.  The nodes in the ear are marked as IN_GADAG.  In
the algorithm, first the ears via DFS-children are found and then the
ears via DFS-neighbors are found.

By adding both types of ears when an IN_GADAG node is processed, all
ears that connect to that node are found.  The order in which the
IN_GADAG nodes are processed is, of course, key to the algorithm.
The order is a stack of ears so the most recent ear is found at the
top of the stack.  Of course, the stack stores nodes and not ears, so
an ordered list of nodes, from the first node in the ear to the last
node in the ear, is created as the ear is explored and then that list
is pushed onto the stack.

Each ear represents a partial order (see Figure 4) and processing the
nodes in order along each ear ensures that all ears connecting to a
node are found before a node higher in the partial order has its ears
explored.  This means that the direction of the links in the ear is
always from the node x being processed towards the other end of the
ear.  Additionally, by using a stack of ears, this means that any
unprocessed nodes in previous ears can only be ordered higher than
nodes in the ears below it on the stack.

In this algorithm that depends upon Lowpoint inheritance, it is
necessary that every node has a lowpoint parent that is not itself.
If a node is a cut-vertex, that may not yet be the case.  Therefore,
any nodes without a lowpoint parent will have their lowpoint parent
set to their DFS parent and their lowpoint value set to the DFS-value
of their parent.  This assignment also properly allows an ear between
two cut-vertices.

Finally, the algorithm simultaneously computes each node's localroot,
as described in Figure 12.  This is further elaborated as follows.
The localroot can be inherited from the node at the end of the ear
unless the end of the ear is x itself, in which case the localroot
for all the nodes in the ear would be x.  This is because whenever
the first cycle is found in a block, or an ear involving a bridge is
computed, the cut-vertex closest to the root would be x itself.  In
all other scenarios, the properties of lowpoint/dfs parents ensure
```
```   that the end of the ear will be in the same block, and thus
inheriting its localroot would be the correct localroot for all newly

The pseudocode for the GADAG algorithm (assuming that the adjustment
of lowpoint for cut-vertices has been made) is shown in Figure 17.

Construct_Ear(x, Stack, intf, ear_type)
ear_list = empty
cur_node = intf.remote_node
cur_intf = intf
not_done = true

while not_done
cur_intf.UNDIRECTED = false
cur_intf.OUTGOING = true
cur_intf.remote_intf.UNDIRECTED = false
cur_intf.remote_intf.INCOMING = true

if cur_node.IN_GADAG is false
if ear_type is CHILD
cur_intf = cur_node.lowpoint_parent_intf
cur_node = cur_node.lowpoint_parent
else  // ear_type must be NEIGHBOR
cur_intf = cur_node.dfs_parent_intf
cur_node = cur_node.dfs_parent
else
not_done = false

if (ear_type is CHILD) and (cur_node is x)
// x is a cut-vertex and the local root for
// the block in which the ear is computed
x.IS_CUT_VERTEX = true
localroot = x
else
// Inherit localroot from the end of the ear
localroot = cur_node.localroot
while ear_list is not empty
y = remove_end_item_from_list(ear_list)
y.localroot = localroot
push(Stack, y)

Initialize Stack to empty
```
```             push gadag_root onto Stack
while (Stack is not empty)
x = pop(Stack)
foreach ordered_interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is x))
Construct_Ear(x, Stack, intf, CHILD)
foreach ordered_interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is not x))
Construct_Ear(x, Stack, intf, NEIGHBOR)

Figure 17: Lowpoint Inheritance GADAG Algorithm

5.6.  Augmenting the GADAG by Directing All Links

The GADAG, regardless of the method used to construct it, at this
point could be used to find MRTs, but the topology does not include
all links in the network graph.  That has two impacts.  First, there
might be shorter paths that respect the GADAG partial ordering and so
the alternate paths would not be as short as possible.  Second, there
may be additional paths between a router x and the root that are not
included in the GADAG.  Including those provides potentially more
bandwidth to traffic flowing on the alternates and may reduce
congestion compared to just using the GADAG as currently constructed.

The goal is thus to assign direction to every remaining link marked
as UNDIRECTED to improve the paths and number of paths found when the
MRTs are computed.

To do this, we need to establish a total order that respects the
partial order described by the GADAG.  This can be done using Kahn's
topological sort [Kahn_1962_topo_sort], which essentially assigns a
number to a node x only after all nodes before it (e.g., with a link
incoming to x) have had their numbers assigned.  The only issue with
the topological sort is that it works on DAGs and not ADAGs or

To convert a GADAG to a DAG, it is necessary to remove all links that
point to a root of block from within that block.  That provides the
necessary conversion to a DAG and then a topological sort can be
the block root to other nodes in that block need special handling
because the topological order will not always give the right answer
for those links.  There are three cases to consider.  If the
undirected link in question has another parallel link between the
```
```   same two nodes that is already directed, then the direction of the
undirected link can be inherited from the previously directed link.
In the case of parallel cut links, we set all of the parallel links
to both INCOMING and OUTGOING.  Otherwise, the undirected link in
question is set to OUTGOING from the block root node.  A cut-link can
then be identified by the fact that it will be directed both INCOMING
and OUTGOING in the GADAG.  The exact details of this whole process
are captured in Figure 18.

foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if (i.remote_node.localroot is not x
or i.PROCESSED )
continue
Initialize bundle_list to empty
bundle.UNDIRECTED = true
bundle.OUTGOING = false
bundle.INCOMING = false
foreach interface i2 in x
if i2.remote_node is i.remote_node
if not i2.UNDIRECTED:
bundle.UNDIRECTED = false
if i2.INCOMING:
bundle.INCOMING = true
if i2.OUTGOING:
bundle.OUTGOING = true
if bundle.UNDIRECTED
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.remote_intf.INCOMING = true
else
if (bundle.OUTGOING and bundle.INCOMING)
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.INCOMING = true
i3.remote_intf.INCOMING = true
i3.remote_intf.OUTGOING = true
```
```                         else if bundle.OUTGOING
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.remote_intf.INCOMING = true
else if bundle.INCOMING
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.INCOMING = true
i3.remote_intf.OUTGOING = true

foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING:
i.INCOMING = false
i.INCOMING_STORED = true
i.remote_intf.OUTGOING = false
i.remote_intf.OUTGOING_STORED = true

foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING_STORED
i.INCOMING = true
i.remote_intf.OUTGOING = true
i.INCOMING_STORED = false
i.remote_intf.OUTGOING_STORED = false

foreach node x in topo
node.unvisited = 0
foreach interface i of x
if (i.INCOMING)
node.unvisited += 1
Initialize working_list to empty
Initialize topo_order_list to empty
```
```         add_to_list_end(working_list, gadag_root)
while working_list is not empty
y = remove_start_item_from_list(working_list)
foreach ordered_interface i of y
if intf.OUTGOING
i.remote_node.unvisited -= 1
if i.remote_node.unvisited is 0
next_topo_order = 1
while topo_order_list is not empty
y = remove_start_item_from_list(topo_order_list)
y.topo_order = next_topo_order
next_topo_order += 1

foreach node x in topo
foreach interface i of x
if i.UNDIRECTED:
if x.topo_order < i.remote_node.topo_order
i.OUTGOING = true
i.UNDIRECTED = false
i.remote_intf.INCOMING = true
i.remote_intf.UNDIRECTED = false
else
i.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false

Figure 18: Assigning Direction to UNDIRECTED Links

Proxy-nodes do not need to be added to the network graph.  They
cannot be transited and do not affect the MRTs that are computed.
The details of how the MRT-Blue and MRT-Red next hops are computed
for proxy-nodes and how the appropriate alternate next hops are
selected is given in Section 5.9.
```
```5.7.  Compute MRT Next Hops

As was discussed in Section 4.1, once an ADAG is found, it is
straightforward to find the next hops from any node X to the ADAG
root.  However, in this algorithm, we will reuse the common GADAG and
find not only the one pair of MRTs rooted at the GADAG root with it,
but find a pair rooted at each node.  This is useful since it is
significantly faster to compute.

The method for computing differently rooted MRTs from the common
GADAG is based on two ideas.  First, if two nodes X and Y are ordered
with respect to each other in the partial order, then an SPF along
OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a
decreasing-SPF) can be used to find the increasing and decreasing
paths.  Second, if two nodes X and Y aren't ordered with respect to
each other in the partial order, then intermediary nodes can be used
to create the paths by increasing/decreasing to the intermediary and
then decreasing/increasing to reach Y.

As usual, the two basic ideas will be discussed assuming the network
is 2-connected.  The generalization to multiple blocks is discussed
in Section 5.7.4.  The full algorithm is given in Section 5.7.5.

5.7.1.  MRT Next Hops to All Nodes Ordered with Respect to the Computing
Node

Finding two node-disjoint paths from the computing router X to any
node Y depends upon whether Y>>X or Y<<X.  As shown in Figure 19, if
Y>>X, then there is an increasing path that goes from X to Y without
crossing R; this contains nodes in the interval [X,Y].  There is also
a decreasing path that decreases towards R and then decreases from R
to Y; this contains nodes in the interval [X,R-small] or [R-great,Y].
The two paths cannot have common nodes other than X and Y.

[Y]<---(Cloud 2)<--- [X]
|                    ^
|                    |
V                    |
(Cloud 3)--->[R]--->(Cloud 1)

MRT-Blue path: X->Cloud 2->Y
MRT-Red path: X->Cloud 1->R->Cloud 3->Y

Figure 19: Y>>X
```
```   Similar logic applies if Y<<X, as shown in Figure 20.  In this case,
the increasing path from X increases to R and then increases from R
to Y to use nodes in the intervals [X,R-great] and [R-small, Y].  The
decreasing path from X reaches Y without crossing R and uses nodes in
the interval [Y,X].

[X]<---(Cloud 2)<--- [Y]
|                    ^
|                    |
V                    |
(Cloud 3)--->[R]--->(Cloud 1)

MRT-Blue path: X->Cloud 3->R->Cloud 1->Y
MRT-Red path: X->Cloud 2->Y

Figure 20: Y<<X

5.7.2.  MRT Next Hops to All Nodes Not Ordered with Respect to the
Computing Node

When X and Y are not ordered, the first path should increase until we
get to a node G, where G>>Y.  At G, we need to decrease to Y.  The
other path should be just the opposite: we must decrease until we get
to a node H, where H<<Y, and then increase.  Since R is smaller and
greater than Y, such G and H must exist.  It is also easy to see that
these two paths must be node disjoint: the first path contains nodes
in interval [X,G] and [Y,G], while the second path contains nodes in
interval [H,X] and [H,Y].  This is illustrated in Figure 21.  It is
necessary to decrease and then increase for the MRT-Blue and increase
and then decrease for the MRT-Red; if one simply increased for one
and decreased for the other, then both paths would go through the
root R.
```
```                 (Cloud 6)<---[Y]<---(Cloud 5)<------------|
|                                       |
|                                       |
V                                       |
[G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H]
^                                       |
|                                       |
|                                       |
(Cloud 3)<---[X]<---(Cloud 2)<-----------|

MRT-Blue path: decrease to H and increase to Y
X->Cloud 2->H->Cloud 5->Y
MRT-Red path:  increase to G and decrease to Y
X->Cloud 3->G->Cloud 6->Y

Figure 21: X and Y Unordered

This gives disjoint paths as long as G and H are not the same node.
Since G>>Y and H<<Y, if G and H could be the same node, that would
have to be the root R.  This is not possible because there is only
one incoming interface to the root R that is created when the initial
cycle is found.  Recall from Figure 6 that whenever an ear was found
to have an end that was the root R, the ear was directed from R so
that the associated interface on R is outgoing and not incoming.
Therefore, there must be exactly one node M that is the largest one
before R, so the MRT-Red path will never reach R; it will turn at M
and decrease to Y.

5.7.3.  Computing Redundant Tree Next Hops in a 2-Connected Graph

The basic ideas for computing RT next hops in a 2-connected graph
were given in Sections 5.7.1 and 5.7.2.  Given these two ideas, how
can we find the trees?

If some node X only wants to find the next hops (which is usually the
case for IP networks), it is enough to find which nodes are greater
and less than X, and which are not ordered; this can be done by
running an increasing-SPF and a decreasing-SPF rooted at X and not
exploring any links from the ADAG root.

In principle, a traversal method other than SPF could be used to
traverse the GADAG in the process of determining blue and red next
hops that result in maximally redundant trees.  This will be the case
as long as one traversal uses the links in the direction specified by
the GADAG and the other traversal uses the links in the direction
opposite of that specified by the GADAG.  However, a different
traversal algorithm will generally result in different blue and red
```
```   next hops.  Therefore, the algorithm specified here requires the use
of SPF to traverse the GADAG to generate MRT blue and red next hops,
as described below.

An increasing-SPF rooted at X and not exploring links from the root
will find the increasing next hops to all Y>>X.  Those increasing
next hops are X's next hops on the MRT-Blue to reach Y.  A
decreasing-SPF rooted at X and not exploring links from the root will
find the decreasing next hops to all Z<<X.  Those decreasing next
hops are X's next hops on the MRT-Red to reach Z.  Since the root R
is both greater than and less than X, after this increasing-SPF and
decreasing-SPF, X's next hops on the MRT-Blue and on the MRT-Red to
reach R are known.  For every node Y>>X, X's next hops on the MRT-Red
to reach Y are set to those on the MRT-Red to reach R.  For every
node Z<<X, X's next hops on the MRT-Blue to reach Z are set to those
on the MRT-Blue to reach R.

For those nodes that were not reached by either the increasing-SPF or
the decreasing-SPF, we can determine the next hops as well.  The
increasing MRT-Blue next hop for a node that is not ordered with
respect to X is the next hop along the decreasing MRT-Red towards R,
and the decreasing MRT-Red next hop is the next hop along the
increasing MRT-Blue towards R.  Naturally, since R is ordered with
respect to all the nodes, there will always be an increasing and a
decreasing path towards it.  This algorithm does not provide the
complete specific path taken but just the appropriate next hops to
use.  The identities of G and H are not determined by the computing
node X.

The final case to consider is when the GADAG root R computes its own
next hops.  Since the GADAG root R is << all other nodes, running an
increasing-SPF rooted at R will reach all other nodes; the MRT-Blue
next hops are those found with this increasing-SPF.  Similarly, since
the GADAG root R is >> all other nodes, running a decreasing-SPF
rooted at R will reach all other nodes; the MRT-Red next hops are
those found with this decreasing-SPF.
```
```                 E---D---|              E<--D<--|
|   |   |              |   ^   |
|   |   |              V   |   |
R   F   C              R   F   C
|   |   |              |   ^   ^
|   |   |              V   |   |
A---B---|              A-->B---|

(a)                    (b)
A 2-connected graph    A spanning ADAG rooted at R

Figure 22

As an example, consider the situation depicted in Figure 22.  Node C
runs an increasing-SPF and a decreasing-SPF on the ADAG.  The
increasing-SPF reaches D, E, and R; the decreasing-SPF reaches B, A,
and R.  E>>C.  So, towards E the MRT-Blue next hop is D, since E was
reached on the increasing path through D.  The MRT-Red next hop
towards E is B, since R was reached on the decreasing path through B.
Since E>>D, D will similarly compute its MRT-Blue next hop to be E,
ensuring that a packet on MRT-Blue will use path C-D-E.  B, A, and R
will similarly compute the MRT-Red next hops towards E (which is
ordered less than B, A and R), ensuring that a packet on MRT-Red will
use path C-B-A-R-E.

C can determine the next hops towards F as well.  Since F is not
ordered with respect to C, the MRT-Blue next hop is the decreasing
one towards R (which is B) and the MRT-Red next hop is the increasing
one towards R (which is D).  Since F>>B, for its MRT-Blue next hop
towards F, B will use the real increasing next hop towards F.  So a
packet forwarded to B on MRT-Blue will get to F on path C-B-F.
Similarly, D will use the real decreasing next hop towards F as its
MRT-Red next hop, a packet on MRT-Red will use path C-D-F.

5.7.4.  Generalizing for a Graph That Isn't 2-Connected

If a graph isn't 2-connected, then the basic approach given in
Section 5.7.3 needs some extensions to determine the appropriate MRT
next hops to use for destinations outside the computing router X's
blocks.  In order to find a pair of maximally redundant trees in that
graph, we need to find a pair of RTs in each of the blocks (the root
of these trees will be discussed later) and combine them.
```
```   When computing the MRT next hops from a router X, there are three
basic differences:

1.  Only nodes in a common block with X should be explored in the
increasing-SPF and decreasing-SPF.

2.  Instead of using the GADAG root, X's localroot should be used.
This has the following implications:

A.  The links from X's localroot should not be explored.

B.  If a node is explored in the outgoing SPF so Y>>X, then X's
MRT-Red next hops to reach Y uses X's MRT-Red next hops to
reach X's localroot and if Z<<X, then X's MRT-Blue next hops
to reach Z uses X's MRT-Blue next hops to reach X's
localroot.

C.  If a node W in a common block with X was not reached in the
increasing-SPF or decreasing-SPF, then W is unordered with
respect to X.  X's MRT-Blue next hops to W are X's decreasing
(aka MRT-Red) next hops to X's localroot.  X's MRT-Red next
hops to W are X's increasing (aka MRT-Blue) next hops to X's
localroot.

3.  For nodes in different blocks, the next hops must be inherited
via the relevant cut-vertex.

These are all captured in the detailed algorithm given in
Section 5.7.5.

5.7.5.  Complete Algorithm to Compute MRT Next Hops

The complete algorithm to compute MRT Next Hops for a particular
router X is given in Figure 23.  In addition to computing the MRT-
Blue next hops and MRT-Red next hops used by X to reach each node Y,
the algorithm also stores an "order_proxy", which is the proper cut-
vertex to reach Y if it is outside the block, and which is used later
in deciding whether the MRT-Blue or the MRT-Red can provide an
acceptable alternate for a particular primary next hop.
```
```   In_Common_Block(x, y)
if ( (x.block_id is y.block_id)
or (x is y.localroot) or (y is x.localroot) )
return true
return false

Store_Results(y, direction)
if direction is FORWARD
y.higher = true
y.blue_next_hops = y.next_hops
if direction is REVERSE
y.lower = true
y.red_next_hops = y.next_hops

SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
Store_Results(min_node, direction)
if ((min_node is spf_root) or (min_node is not block_root))
foreach interface intf of min_node
if ( ( ((direction is FORWARD) and intf.OUTGOING) or
((direction is REVERSE) and intf.INCOMING) )
and In_Common_Block(spf_root, intf.remote_node) )
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
else
min_node.next_hops)

SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty
SetEdge(y.localroot)
y.blue_next_hops = y.localroot.blue_next_hops
y.red_next_hops = y.localroot.red_next_hops
y.order_proxy = y.localroot.order_proxy
```
```   Compute_MRT_NextHops(x, gadag_root)
foreach node y
y.higher = y.lower = false
clear y.red_next_hops and y.blue_next_hops
y.order_proxy = y
SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD)
SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE)

// red and blue next hops are stored to x.localroot as different
// paths are found via the SPF and reverse-SPF.
// Similarly, any node whose localroot is x will have its
// red_next_hops and blue_next_hops already set.

// Handle nodes in the same block that aren't the localroot
foreach node y
if (y.IN_MRT_ISLAND and (y is not x) and
(y.block_id is x.block_id) )
if y.higher
y.red_next_hops = x.localroot.red_next_hops
else if y.lower
y.blue_next_hops = x.localroot.blue_next_hops
else
y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_next_hops

// Inherit next hops and order_proxies to other components
if (x is not gadag_root) and (x.localroot is not gadag_root)