 1/draftietfrtgwgmrtfrralgorithm00.txt 20140704 11:14:32.632193398 0700
+++ 2/draftietfrtgwgmrtfrralgorithm01.txt 20140704 11:14:32.752196291 0700
@@ 1,24 +1,24 @@
Routing Area Working Group G. Enyedi, Ed.
InternetDraft A. Csaszar
Intended status: Standards Track Ericsson
Expires: August 18, 2014 A. Atlas, Ed.
+Expires: January 5, 2015 A. Atlas, Ed.
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
 February 14, 2014
+ July 4, 2014
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast
Reroute
 draftietfrtgwgmrtfrralgorithm00
+ draftietfrtgwgmrtfrralgorithm01
Abstract
A complete solution for IP and LDP FastReroute using Maximally
Redundant Trees is presented in [ID.ietfrtgwgmrtfrr
architecture]. This document defines the associated MRT Lowpoint
algorithm that is used in the default MRT profile to compute both the
necessary Maximally Redundant Trees with their associated nexthops
and the alternates to select for MRTFRR.
@@ 30,21 +30,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at http://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
 This InternetDraft will expire on August 18, 2014.
+ This InternetDraft will expire on January 5, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 60,45 +60,48 @@
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
4.2. Finding an Ear and the Correct Direction . . . . . . . . 9
4.3. LowPoint Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15
4.5. Determining LocalRoot and Assigning BlockID . . . . . . 17
5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19
5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20
 5.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 21
+ 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
inheritance . . . . . . . . . . . . . . . . . . . . . . . 22
5.5. Augmenting the GADAG by directing all links . . . . . . . 24
5.6. Compute MRT nexthops . . . . . . . . . . . . . . . . . . 26
5.6.1. MRT nexthops to all nodes partially ordered with
respect to the computing node . . . . . . . . . . . . 27
5.6.2. MRT nexthops to all nodes not partially ordered with
respect to the computing node . . . . . . . . . . . . 28
5.6.3. Computing Redundant Tree nexthops in a 2connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 29
 5.6.4. Generalizing for graph that isn't 2connected . . . . 30
+ 5.6.4. Generalizing for a graph that isn't 2connected . . . 30
5.6.5. Complete Algorithm to Compute MRT NextHops . . . . . 31
5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33
5.8. Finding FRR NextHops for ProxyNodes . . . . . . . . . . 37
 6. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 40
+ 6. MRT Lowpoint Algorithm: Nexthop conformance . . . . . . . . 40
7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40
7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41
 8. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51
 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51
 10. Security Considerations . . . . . . . . . . . . . . . . . . . 51
 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 51
 11.1. Normative References . . . . . . . . . . . . . . . . . . 51
 11.2. Informative References . . . . . . . . . . . . . . . . . 51
+ 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51
+ 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51
+ 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51
+ 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51
+ 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51
+ 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51
+ 13.1. Normative References . . . . . . . . . . . . . . . . . . 51
+ 13.2. Informative References . . . . . . . . . . . . . . . . . 51
+
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53
Appendix B. Option 3: Computing GADAG using a hybrid method . . 58
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
1. Introduction
MRT FastReroute requires that packets can be forwarded not only on
the shortestpath tree, but also on two Maximally Redundant Trees
(MRTs), referred to as the MRTBlue and the MRTRed. A router which
experiences a local failure must also have predetermined which
@@ 383,21 +386,21 @@
root  and the actual algorithm is given in Section 5.4.
In order to understand the basic idea of finding an ADAG, first
suppose that we have already a partial ADAG, which doesn't contain
all the nodes in the block yet, and we want to extend it to cover all
the nodes. Suppose that we find a path from a node X to Y such that
X and Y are already contained by our partial ADAG, but all the
remaining nodes along the path are not added to the ADAG yet. We
refer to such a path as an ear.
 Recall that our ADAG is closely related to a partial order, more
+ Recall that our ADAG is closely related to a partial order. More
precisely, if we remove root R, the remaining DAG describes a partial
order of the nodes. If we suppose that neither X nor Y is the root,
we may be able to compare them. If one of them is definitely lesser
with respect to our partial order (say X<C and C>D are added). If
B >> D, we would add the same path in reverse direction.
If in the partial order where an ear's two ends are X and Y, X << Y,
then there must already be a directed path from X to Y in the ADAG.
The ear must be added in a direction such that it doesn't create a
cycle; therefore the ear must go from X to Y.
@@ 443,23 +446,23 @@
and then finding a path from N to R that doesn't use any links
between R and N. The direction of the cycle can be assigned either
way since it is starting the ordering.
Once a partial ADAG is already present, it will always have a node
that is not the root R in it. As a brief proof that a partial ADAG
can always have ears added to it: just select a nonready neighbor N
of a ready node Q, such that Q is not the root R, find a path from N
to the root R in the graph with Q removed. This path is an ear where
the first node of the ear is Q, the next is N, then the path until
 the first ready node the path reached (that second ready node is the
 other endpoint of the path). Since the graph is 2connected, there
 must be a path from N to R without Q.
+ the first ready node the path reached (that ready node is the other
+ endpoint of the path). Since the graph is 2connected, there must be
+ a path from N to R without Q.
It is always possible to select a nonready neighbor N of a ready
node Q so that Q is not the root R. Because the network is
2connected, N must be connected to two different nodes and only one
can be R. Because the initial cycle has already been added to the
ADAG, there are ready nodes that are not R. Since the graph is
2connected, while there are nonready nodes, there must be a non
ready neighbor N of a ready node that is not R.
Generic_Find_Ears_ADAG(root)
@@ 484,25 +487,25 @@
we will get an ADAG. The method used for finding and selecting the
ears is important; shorter ears result in shorter paths along the
MRTs. The MRT Lowpoint algorithm's method using LowPoint
Inheritance is defined in Section 5.4. Other methods are described
in the Appendices (Appendix A and Appendix B).
As an example, consider Figure 5 again. First, we select the
shortest cycle containing R, which can be RABFDE (uniform link
costs were assumed), so we get to the situation depicted in Figure 5
(b). Finally, we find a node next to a ready node; that must be node
 C and assume we reached it from ready node B. We search a path from C
 to R without B in the original graph. The first ready node along
 this is node D, so the open ear is BCD. Since B<C
 and C>D to the ADAG. Since all the nodes are ready, we stop at this
 point.
+ C and assume we reached it from ready node B. We search a path from
+ C to R without B in the original graph. The first ready node along
+ this is node D, so the open ear is BCD. Since B<C and C>D to the ADAG. Since all the nodes are ready, we stop at
+ this point.
4.3. LowPoint Values and Their Uses
A basic way of computing a spanning tree on a network graph is to run
a depthfirstsearch, such as given in Figure 7. This tree has the
important property that if there is a link (x, n), then either n is a
DFS ancestor of x or n is a DFS descendant of x. In other words,
either n is on the path from the root to x or x is on the path from
the root to n.
@@ 517,25 +520,69 @@
DFS_Visit(w, x)
Run_DFS(node root)
dfs_number = 0
DFS_Visit(root, NONE)
Figure 7: Basic DepthFirst Search algorithm
Given a node x, one can compute the minimal DFS number of the
neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the
 highest attachment point neighbouring x. What is interesting,
 though, is what is the highest attachment point from x and x's
+ earliest attachment point neighbouring x. What is interesting,
+ though, is what is the earliest attachment point from x and x's
descendants. This is what is determined by computing the LowPoint
 value, as given in Algorithm Figure 9 and illustrated on a graph in
 Figure 8.
+ value.
+
+ In order to compute the low point value, the network is traversed
+ using DFS and the vertices are numbered based on the DFS walk. Let
+ this number be represented as DFS(x). All the edges that lead to
+ already visited nodes during DFS walk are backedges. The backedges
+ are important because they give information about reachability of a
+ node via another path.
+
+ The low point number is calculated by finding:
+
+ Low(x) = Minimum of ( (DFS(x),
+ Lowest DFS(n, x>n is a backedge),
+ Lowest Low(n, x>n is tree edge in DFS walk) ).
+
+ A detailed algorithm for computing the lowpoint value is given in
+ Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to
+ a example graph.
+
+ global_variable: dfs_number
+
+ Lowpoint_Visit(node x, node parent, interface p_to_x)
+ D(x) = dfs_number
+ L(x) = D(x)
+ dfs_number += 1
+ x.dfs_parent = parent
+ x.dfs_parent_intf = p_to_x
+ x.lowpoint_parent = NONE
+ for each interface intf of x
+ if D(intf.remote_node) is not set
+ Lowpoint_Visit(intf.remote_node, x, intf)
+ if L(intf.remote_node) < L(x)
+ L(x) = L(intf.remote_node)
+ x.lowpoint_parent = intf.remote_node
+ x.lowpoint_parent_intf = intf
+ else if intf.remote_node is not parent
+ if D(intf.remote_node) < L(x)
+ L(x) = D(intf.remote_node)
+ x.lowpoint_parent = intf.remote_node
+ x.lowpoint_parent_intf = intf
+
+ Run_Lowpoint(node root)
+ dfs_number = 0
+ Lowpoint_Visit(root, NONE, NONE)
+
+ Figure 8: Computing LowPoint value
[E] [J][I] [P][O]
     
     
[R] [D][C][F] [H][K] [N]
     
     
[A][B] [G] [L][M]
(a) a non2connected graph
@@ 559,71 +606,43 @@
     
[R] [D][C][F] [H][K] [N]
(0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
     
     
[A][B] [G] [L][M]
(1,0) (2,0) (7,3) (12,11) (13,11)
(c) with lowpoint values assigned (D(x), L(x))
 Figure 8

 global_variable: dfs_number

 Lowpoint_Visit(node x, node parent, interface p_to_x)
 D(x) = dfs_number
 L(x) = D(x)
 dfs_number += 1
 x.dfs_parent = parent
 x.dfs_parent_intf = p_to_x
 x.lowpoint_parent = NONE
 for each interface intf of x:
 if D(intf.remote_node) is not set
 Lowpoint_Visit(intf.remote_node, x, intf)
 if L(intf.remote_node) < L(x)
 L(x) = L(intf.remote_node)
 x.lowpoint_parent = intf.remote_node
 x.lowpoint_parent_intf = intf
 else if intf.remote_node is not parent
 if D(intf.remote_node) < L(x)
 L(x) = D(intf.remote)
 x.lowpoint_parent = intf.remote_node
 x.lowpoint_parent_intf = intf

 Run_Lowpoint(node root)
 dfs_number = 0
 Lowpoint_Visit(root, NONE, NONE)

 Figure 9: Computing LowPoint value
+ Figure 9: Example lowpoint value computation
From the lowpoint value and lowpoint parent, there are three very
useful things which motivate our computation.
First, if there is a child c of x such that L(c) >= D(x), then there
are no paths in the network graph that go from c or its descendants
 to an ancestor of x  and therefore x is a cutvertex. In Figure 8,
+ to an ancestor of x  and therefore x is a cutvertex. In Figure 9,
this can be seen by looking at the DFS children of C. C has two
children  D and F and L(F) = 3 = D(C) so it is clear that C is a
cutvertex and F is in a block where C is the block's root. L(D) = 0
> 3 = D(C) so D has a path to the ancestors of C; in this case, D can
go via E to reach R. Comparing the lowpoint values of all a node's
DFSchildren with the node's DFSvalue is very useful because it
allows identification of the cutvertices and thus the blocks.
Second, by repeatedly following the path given by lowpoint_parent,
there is a path from x back to an ancestor of x that does not use the
link [x, x.dfs_parent] in either direction. The full path need not
be taken, but this gives a way of finding an initial cycle and then
ears.
 Third, as seen in Figure 8, even if L(x) < D(x), there may be a block
+ Third, as seen in Figure 9, even if L(x) < D(x), there may be a block
that contains both the root and a DFSchild of a node while other
DFSchildren might be in different blocks. In this example, C's
child D is in the same block as R while F is not. It is important to
realize that the root of a block may also be the root of another
block.
4.4. Blocks in a Graph
A key idea for an MRT algorithm is that any non2connected graph is
made up by blocks (e.g. 2connected clusters, cutlinks, and/or
@@ 778,21 +797,21 @@
its interfaces have been ordered as per Figure 14.
1. Compute the local MRT Island for the particular MRT Profile.
[See Section 5.1.]
2. Select the root to use for the GADAG. [See Section 5.2.]
3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.]
4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See
 Figure 9.]
+ Figure 8.]
5. Construct the GADAG. [See Section 5.4]
6. Assign directions to all interfaces that are still UNDIRECTED.
[See Section 5.5.]
7. From the computing router x, compute the nexthops for the MRT
Blue and MRTRed. [See Section 5.6.]
8. Identify alternates for each nexthop to each destination by
@@ 826,43 +845,48 @@
return A_LESS_THAN_B
return B_LESS_THAN_A
Figure 14: Rules for ranking multiple interfaces. Order is from low
to high.
5.1. 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 breadthfirstsearch (BFS), exploring only links that aren't MRT
 ineligible.
+ a breadthfirstsearch (BFS). The BFS explores only links that are
+ in the same area/level, are not IGPexcluded, and are not MRT
+ ineligible. The BFS explores only nodes that are are not IGP
+ excluded, and that support the particular MRT profile. See section 7
+ of [ID.ietfrtgwgmrtfrrarchitecture] for more precise definitions
+ of these criteria.
 MRT_Island_Identification(topology, computing_rtr, profile_id)
+ 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)
next_rtr = remove_head(explore_list)
for each interface in next_rtr
 if interface is not MRTineligible
+ if interface is (not MRTineligible and not IGPexcluded
+ and in area)
if ((interface.remote_node supports profile_id) and
(interface.remote_node.IN_MRT_ISLAND is FALSE))
interface.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, interface.remote_node)
Figure 15: MRT Island Identification
5.2. Root Selection
+5.2. GADAG Root Selection
 In Section 7 of [ID.ietfrtgwgmrtfrrarchitecture], the GADAG Root
 Selection is described for the MRT default profile. In
+ In Section 8.3 of [ID.ietfrtgwgmrtfrrarchitecture], the GADAG
+ Root Selection Policy is described for the MRT default profile. In
[ID.atlasospfmrt] and [ID.liisismrt], a mechanism is given for
routers to advertise the GADAG Root Selection Priority and
consistently select a GADAG Root inside the local MRT Island. 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.
Analysis has shown that the centrality of a router can have a
@@ 879,29 +903,32 @@
nexthops, and flags associated with algorithm.
It is assumed that a regular SPF computation has been run so that the
primary nexthops 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.
 Due to manageability consideration
 [ID.ietfrtgwglfamanageability], overload, or a transient cause
 such as [RFC3137], it is possible that some links and nodes will be
 marked as unusable. This constraint must be consistently flooded via
 the IGP [ID.atlasospfmrt] [ID.liisismrt] so that links are
 clearly known to be MRTineligible and not explored or used in the
 MRT algorithm. In the algorithm description, it is assumed that such
 links and nodes will not be explored or used and no more discussion
 is given of this restriction.
+ It is possible that some links and nodes will be marked as unusable
+ using standard IGP mechanisms (see section 7 of
+ [ID.ietfrtgwgmrtfrrarchitecture]). Due to FRR manageability
+ considerations [ID.ietfrtgwglfamanageability], it may also be
+ desirable to administratively configure some interfaces as ineligible
+ to carry MRT FRR traffic. This constraint MUST be consistently
+ flooded via the IGP [ID.atlasospfmrt] [ID.liisismrt] by the
+ owner of the interface, so that links are clearly known to be MRT
+ ineligible and not explored or used in the MRT algorithm. In the
+ algorithm description, it is assumed that such links and nodes will
+ not be explored or used, and no more discussion is given of this
+ restriction.
5.4. MRT Lowpoint Algorithm: Computing 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 not IN_GADAG DFSchild and then following the chain of
lowpoint parents until an IN_GADAG node is found. The second is by
going to a not IN_GADAG neighbor and then following the chain of DFS
parents until an IN_GADAG node is found. As an ear is found, the
@@ 1028,47 +1055,47 @@
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
GADAGs.
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
done. Finally, all UNDIRECTED links are assigned a direction based
 upon the partial ordering. Any UNDIRECTED links that connect to a
 root of a block from within that block are assigned a direction
 INCOMING to that root. The exact details of this whole process are
 captured in Figure 17
+ upon the total ordering. Any UNDIRECTED links that connect to a root
+ of a block from within that block are assigned a direction INCOMING
+ to that root. The exact details of this whole process are captured
+ in Figure 17
Set_Block_Root_Incoming_Links(topo, root, mark_or_clear)
foreach node x in topo
if node x is a cutvertex or root
foreach interface i of x
if (i.remote_node.localroot is x)
if i.UNDIRECTED
i.OUTGOING = true
i.remote_intf.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.UNDIRECTED = false
if i.INCOMING
 if mark_or_clear is mark
+ if mark_or_clear is MARK
if i.OUTGOING // a cutlink
i.STORE_INCOMING = true
i.INCOMING = false
i.remote_intf.STORE_OUTGOING = true
i.remote_intf.OUTGOING = false
i.TEMP_UNUSABLE = true
i.remote_intf.TEMP_UNUSABLE = true
else
i.TEMP_UNUSABLE = false
i.remote_intf.TEMP_UNUSABLE = false
 if i.STORE_INCOMING and (mark_or_clear is clear)
+ if i.STORE_INCOMING and (mark_or_clear is CLEAR)
i.INCOMING = true
i.STORE_INCOMING = false
i.remote_intf.OUTGOING = true
i.remote_intf.STORE_OUTGOING = false
Run_Topological_Sort_GADAG(topo, root)
Set_Block_Root_Incoming_Links(topo, root, MARK)
foreach node x
set x.unvisited to the count of x's incoming interfaces
that aren't marked TEMP_UNUSABLE
@@ 1106,32 +1133,31 @@
i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, root)
Figure 17: Assigning direction to UNDIRECTED links
Proxynodes 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 MRTBlue and MRTRed nexthops are computed
 and how the appropriate alternate nexthops are selected is given in
 Section 5.8.
+ for proxynodes and how the appropriate alternate nexthops are
+ selected is given in Section 5.8.
5.6. Compute MRT nexthops
As was discussed in Section 4.1, once a ADAG is found, it is
straightforward to find the nexthops from any node X to the ADAG
 root. However, in this algorithm, we want to 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. It may also provide easier
 troubleshooting of the MRTRed and MRTBlue.
+ 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 increasingSPF) and an SPF along INCOMING links (a
decreasingSPF) 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.
@@ 1234,40 +1260,42 @@
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 increasingSPF and a decreasingSPF rooted at X and not
exploring any links from the ADAG root. ( Traversal algorithms other
than SPF could safely be used instead where one traversal takes the
links in their given directions and the other reverses the links'
directions.)
An increasingSPF rooted at X and not exploring links from the root
will find the increasing nexthops to all Y >> X. Those increasing
 nexthops are X's nexthops on the MRTBlue to reach Y. An
+ nexthops are X's nexthops on the MRTBlue to reach Y. A
decreasingSPF rooted at X and not exploring links from the root will
find the decreasing nexthops to all Z << X. Those decreasing next
hops are X's nexthops on the MRTRed to reach Z. Since the root R
is both greater than and less than X, after this increasingSPF and
decreasingSPF, X's nexthops on the MRTBlue and on the MRTRed to
reach R are known. For every node Y >> X, X's nexthops on the MRT
Red to reach Y are set to those on the MRTRed to reach R. For every
node Z << X, X's nexthops on the MRTBlue to reach Z are set to
those on the MRTBlue to reach R.
 For those nodes, which were not reached, we have the nexthops as
 well. The increasing MRTBlue nexthop for a node, which is not
 ordered, is the nexthop along the decreasing MRTRed towards R and
 the decreasing MRTRed nexthop is the nexthop along the increasing
 MRTBlue 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 nexthops to use. The identity
 of G and H is not determined.
+ For those nodes which were not reached by either the increasingSPF
+ or the decreasingSPF, we can determine the nexthops as well. The
+ increasing MRTBlue nexthop for a node which is not ordered with
+ respect to X is the nexthop along the decreasing MRTRed towards R,
+ and the decreasing MRTRed nexthop is the nexthop along the
+ increasing MRTBlue 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 nexthops to
+ use. The identities of G and H are not determined by the computing
+ node X.
The final case to considered is when the root R computes its own
nexthops. Since the root R is << all other nodes, running an
increasingSPF rooted at R will reach all other nodes; the MRTBlue
nexthops are those found with this increasingSPF. Similarly, since
the root R is >> all other nodes, running a decreasingSPF rooted at
R will reach all other nodes; the MRTRed nexthops are those found
with this decreasingSPF.
ED E<D<
@@ 1276,37 +1304,42 @@
R F C R F C
    ^ ^
   V  
AB A>B
(a) (b)
A 2connected graph A spanning ADAG rooted at R
Figure 21
 As an example consider the situation depicted in Figure 21. There
 node C runs an increasingSPF and a decreasingSPF The increasingSPF
 reaches D, E and R and the decreasingSPF reaches B, A and R. So
 towards E the increasing nexthop is D (it was reached though D), and
 the decreasing nexthop is B (since R was reached though B). Since
 both D and B, A and R will compute the next hops similarly, the
 packets will reach E.
+ As an example consider the situation depicted in Figure 21. Node C
+ runs an increasingSPF and a decreasingSPF on the ADAG. The
+ increasingSPF reaches D, E and R and the decreasingSPF reaches B, A
+ and R. E>>C. So towards E the MRTBlue nexthop is D, since E was
+ reached on the increasing path through D. And the MRTRed nexthop
+ towards E is B, since R was reached on the decreasing path through B.
+ Since E>>D, D will similarly compute its MRTBlue nexthop to be E,
+ ensuring that a packet on MRTBlue will use path CDE. B, A and R
+ will similarly compute the MRTRed nexthops towards E (which is
+ ordered less than B, A and R), ensuring that a packet on MRTRed will
+ use path CBARE.
 We have the nexthops towards F as well: since F is not ordered with
 respect to C, the MRTBlue nexthop is the decreasing one towards R
 (which is B) and the MRTRed nexthop is the increasing one towards R
 (which is D). Since B is ordered with F, it will find, for its MRT
 Blue, a real increasing nexthop, so packet forwarded to B will get
 to F on path CBF. Similarly, D will have, for its MRTRed, a real
 decreasing nexthop, and the packet will use path CDF.
+ C can determine the nexthops towards F as well. Since F is not
+ ordered with respect to C, the MRTBlue nexthop is the decreasing
+ one towards R (which is B) and the MRTRed nexthop is the increasing
+ one towards R (which is D). Since F>>B, for its MRTBlue nexthop
+ towards F, B will use the real increasing nexthop towards F. So a
+ packet forwarded to B on MRTBlue will get to F on path CBF.
+ Similarly, D will use the real decreasing nexthop towards F as its
+ MRTRed nexthop, an packet on MRTRed will use path CDF.
5.6.4. Generalizing for graph that isn't 2connected
+5.6.4. Generalizing for a graph that isn't 2connected
If a graph isn't 2connected, then the basic approach given in
Section 5.6.3 needs some extensions to determine the appropriate MRT
nexthops 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 nexthops from a router X, there are three
basic differences:
@@ 1321,22 +1354,22 @@
B. If a node is explored in the outgoing SPF so Y >> X, then X's
MRTRed nexthops to reach Y uses X's MRTRed nexthops to
reach X's localroot and if Z << X, then X's MRTBlue next
hops to reach Z uses X's MRTBlue nexthops to reach X's
localroot.
C. If a node W in a common block with X was not reached in the
increasingSPF or decreasingSPF, then W is unordered with
respect to X. X's MRTBlue nexthops to W are X's decreasing
 aka MRTRed nexthops to X's localroot. X's MRTRed next
 hops to W are X's increasing aka Blue MRT nexthops to X's
+ (aka MRTRed) nexthops to X's localroot. X's MRTRed next
+ hops to W are X's increasing (aka MRTBlue) nexthops to X's
localroot.
3. For nodes in different blocks, the nexthops must be inherited
via the relevant cutvertex.
These are all captured in the detailed algorithm given in
Section 5.6.5.
5.6.5. Complete Algorithm to Compute MRT NextHops
@@ 1555,22 +1588,22 @@
case (iii) holds true, which means that selecting the Blue nexthop
is safe. Similarly, if F.topo_order>S, we
 should use the Blue nexthop.
+ then decreasing; this path must avoid using F. Similarly, if F>>S,
+ we should use the Blue nexthop.
Additionally, the cases where either F or D is ordered both higher
and lower must be considered; this can happen when one is a block
root or its order_proxy is. If D is both higher and lower than S,
then the MRT to use is the one that avoids F so if F is higher, then
the MRTRed should be used and if F is lower, then the MRTBlue
should be used; F and S must be ordered because they are neighbors.
If F is both higher and lower, then if D is lower, using the MRTRed
to decrease reaches D and if D is higher, using the Blue MRT to
increase reaches D; if D is unordered compared to S, then the
@@ 1579,22 +1612,22 @@
In the case where F< F, then use the MRTBlue (decrease to avoid
that link and then increase). If the link is directed S < F, then
use the MRTRed (increase to avoid that link and then decrease). If
the link is S <> F, then the link must be a cutlink and there is
no nodeprotecting alternate. If there are multiple links between S
and F, then they can protect against each other; of course, in this
situation, they are probably already ECMP.
 Finally, there is the case where D is also F. In this case, only link
 protection is possible. The MRT that doesn't use the indicated
+ Finally, there is the case where D is also F. In this case, only
+ link protection is possible. The MRT that doesn't use the indicated
primary nexthop is used. If both MRTs use the primary nexthop,
then the primary nexthop must be a cutlink so either MRT could be
used but the set of MRT nexthops must be pruned to avoid that
primary nexthop. To indicate this case, Select_Alternates returns
AVOID_LINK_ON_BLUE.
As an example, consider the ADAG depicted in Figure 24 and first
suppose that G is the source, D is the destination and H is the
failed nexthop. Since D>>G, we need to compare H.topo_order and
D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller
@@ 1707,65 +1741,61 @@
return
P.blue_next_hops = R.red_next_hops
P.red_next_hops = R.blue_next_hops
return
After finding the the red and the blue nexthops, it is necessary to
know which one of these to use in the case of failure. This can be
done by Select_Alternates_Inner(). In order to use
Select_Alternates_Internal(), we need to know if P is greater, less
or unordered with S, and P.topo_order. P.lower = B.lower, P.higher =
 A.higher, and any value is OK for P.topo_order, until
+ A.higher, and any value is OK for P.topo_order, as long as
A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not
equal to the topo_order of the failed node. So for simplicity let
P.topo_order=A.topo_order when the nexthop is not A, and
P.topo_order=B.topo_order otherwise. This gives the following
pseudocode:
Select_Alternates_Proxy_Node(S, P, F, primary_intf)
if (F is not P.neighbor_A)
return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower,
P.neighbor_A.higher,
P.neighbor_A.topo_order)
else
return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower,
P.neighbor_A.higher,
P.neighbor_B.topo_order)
Figure 25
6. MRT Lowpoint Algorithm: Complete Specification
+6. MRT Lowpoint Algorithm: Nexthop conformance
This specification defines the MRT Lowpoint Algorithm, which include
the construction of a common GADAG and the computation of MRTRed and
MRTBlue nexthops to each node in the graph. An implementation MAY
select any subset of nexthops for MRTRed and MRTBlue that respect
the available nodes that are described in Section 5.6 for each of the
MRTRed and MRTBlue and the selected nexthops are further along in
the interval of allowed nodes towards the destination.
 For example, the MRTBlue nexthops used when the destination Y >> S,
+ For example, the MRTBlue nexthops used when the destination Y >> X,
the computing router, MUST be one or more nodes, T, whose topo_order
is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y
is T. Similarly, the MRTRed nexthops MUST be have a topo_order in
the interval [Rsmall.topo_order, X.topo_order] or [Y.topo_order,
Rbig.topo_order].
Implementations SHOULD implement the Select_Alternates() function to
pick an MRTFRR alternate.
 In a future version, this section will include pseudocode describing
 the full code path through the pseudocode given earlier in the
 draft.

7. Algorithm Alternatives and Evaluation
This specification defines the MRT Lowpoint Algorithm, which is one
option among several possible MRT algorithms. Other alternatives are
described in the appendices.
In addition, it is possible to calculate DestinationRooted GADAG,
where for each destination, a GADAG rooted at that destination is
computed. Then a router can compute the blue MRT and red MRT next
hops to that destination. Building GADAGs per destination is
@@ 2204,107 +2234,118 @@
 T219(avg primary hops=7.7)          
 MRT_HYBRID ( 0 percentile)  20 16 13 10 7 5 5 5 3
 MRT_SPF ( 0 percentile)  31 23 19 12 7 4 2 1 
 MRT_LOWPOINT ( 0 percentile)  19 14 15 12 10 8 7 6 10
 MRT_LOWPOINT (25 percentile)  19 14 15 13 12 10 6 5 7
 MRT_LOWPOINT (50 percentile)  19 14 14 12 11 8 6 6 10
+++++++++++
Figure 32
8. Algorithm Work to Be Done
+8. Implementation Status
+
+ [RFC Editor: please remove this section prior to publication.]
+
+ Please see [ID.ietfrtgwgmrtfrrarchitecture] for details on
+ implementation status.
+
+9. Algorithm Work to Be Done
Broadcast Interfaces: The algorithm assumes that broadcast
interfaces are already represented as pseudonodes in the network
graph. Given maximal redundancy, one of the MRT will try to avoid
both the pseudonode and the next hop. The exact rules need to be
fully specified.
9. IANA Considerations
+10. Acknowledgements
 This doument includes no request to IANA.
+ The authors would like to thank Shraddha Hegde for her suggestions
+ and review.
10. Security Considerations
+11. IANA Considerations
+
+ This document includes no request to IANA.
+
+12. Security Considerations
This architecture is not currently believed to introduce new security
concerns.
11. References
+13. References
11.1. Normative References
+13.1. Normative References
[ID.ietfrtgwgmrtfrrarchitecture]
 Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura,
 J., Konstantynowicz, M., and R. White, "An Architecture
 for IP/LDP FastReroute Using Maximally Redundant Trees",
 draftietfrtgwgmrtfrrarchitecture03 (work in
 progress), July 2013.
+ Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar,
+ A., Tantsura, J., Konstantynowicz, M., and R. White, "An
+ Architecture for IP/LDP FastReroute Using Maximally
+ Redundant Trees", draftrtgwgmrtfrrarchitecture04
+ (work in progress), July 2014.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References
+13.2. Informative References
[EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D.
 Thesis, February 2011, .
[ID.atlasmplsldpmrt]
 Atlas, A., Tiruveedhula, K., Tantsura, J., and I.
+ Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ.
Wijnands, "LDP Extensions to Support Maximally Redundant
 Trees", draftatlasmplsldpmrt00 (work in progress),
 July 2013.
+ Trees", draftatlasmplsldpmrt01 (work in progress),
+ July 2014.
[ID.atlasospfmrt]
 Atlas, A., Hegde, S., cbowers@juniper.net, c., and J.
 Tantsura, "OSPF Extensions to Support Maximally Redundant
 Trees", draftatlasospfmrt01 (work in progress),
 October 2013.
+ Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF
+ Extensions to Support Maximally Redundant Trees", draft
+ atlasospfmrt02 (work in progress), July 2014.
[ID.ietfrtgwgipfrrnotviaaddresses]
Bryant, S., Previdi, S., and M. Shand, "A Framework for IP
and MPLS Fast Reroute Using Notvia Addresses", draft
ietfrtgwgipfrrnotviaaddresses11 (work in progress),
May 2013.
[ID.ietfrtgwglfamanageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and p. psarkar@juniper.net, "Operational
management of Loop Free Alternates", draftietfrtgwglfa
manageability03 (work in progress), February 2014.
[ID.ietfrtgwgremotelfa]
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S.
 Ning, "Remote LFA FRR", draftietfrtgwgremotelfa04
 (work in progress), November 2013.
+ Ning, "Remote LFA FRR", draftietfrtgwgremotelfa06
+ (work in progress), May 2014.
[ID.liisismrt]
 Li, Z., Wu, N., Zhao, Q., Atlas, A., cbowers@juniper.net,
 c., and J. Tantsura, "Intermediate System to Intermediate
 System (ISIS) Extensions for Maximally Redundant Trees
 (MRT)", draftliisismrt00 (work in progress), October
 2013.
+ Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
+ Tantsura, "Intermediate System to Intermediate System (IS
+ IS) Extensions for Maximally Redundant Trees(MRT)", draft
+ liisismrt01 (work in progress), July 2014.
[Kahn_1962_topo_sort]
Kahn, A., "Topological sorting of large networks",
Communications of the ACM, Volume 5, Issue 11 , Nov 1962,
.
[LFARevisited]
Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP
Fast ReRoute: Loop Free Alternates Revisited", Proceedings
 of IEEE INFOCOM , 2011, .
+ of IEEE INFOCOM , 2011,
+ .
[LightweightNotVia]
Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP
Fast ReRoute: Lightweight NotVia without Additional
Addresses", Proceedings of IEEE INFOCOM , 2009,
.
[MRTLinear]
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE
@@ 2406,22 +2446,22 @@
Clear TEMP_UNUSABLE from all interfaces between
cand_intf.remote_node and cand_intf.local_node
Clear TEMP_UNUSABLE from cand_intf.local_node
return end_ear
Figure 33: Modified SPF for GADAG computation
Assume that an ear is found by going from y to x and then running an
SPF that terminates by minimizing z (e.g. y<>x...q<>z). Now it is
necessary to determine the direction of the ear; if y << z, then the
 path should be y>x...q>z but if y >> z, then the path should be
 y<x...q<z. In Section 5.4, the same problem was handled by finding
+ path should be y>x...q>z but if y >> z, then the path should be y<
+ x...q<z. In Section 5.4, the same problem was handled by finding
all ears that started at a node before looking at ears starting at
nodes higher in the partial order. In this algorithm, using that
approach could mean that new ears aren't added in order of their
total cost since all ears connected to a node would need to be found
before additional nodes could be found.
The alternative is to track the order relationship of each node with
respect to every other node. This can be accomplished by maintaining
two sets of nodes at each node. The first set, Higher_Nodes,
contains all nodes that are known to be ordered above the node. The
@@ 2482,24 +2522,23 @@
maintained of interfaces that could be explored from the IN_GADAG
nodes. The interfaces are ordered by their characteristics of
metric, local loopback address, remote loopback address, and ifindex,
as in the algorithm previously described in Figure 14.
The algorithm ignores interfaces picked from the ordered tree that
belong to the block root if the block in which the interface is
present already has an ear that has been computed. This is necessary
since we allow at most one incoming interface to a block root in each
block. This requirement stems from the way nexthops are computed as
 will be seen in Section 5.6. After any ear gets computed, we
 traverse the newly added nodes to the GADAG and insert interfaces
 whose far end is not yet on the GADAG to the ordered tree for later
 processing.
+ was seen in Section 5.6. After any ear gets computed, we traverse
+ the newly added nodes to the GADAG and insert interfaces whose far
+ end is not yet on the GADAG to the ordered tree for later processing.
Finally, cutlinks are a special case because there is no point in
doing an SPF on a block of 2 nodes. The algorithm identifies cut
links simply as links where both ends of the link are cutvertices.
Cutlinks can simply be added to the GADAG with both OUTGOING and
INCOMING specified on their interfaces.
add_eligible_interfaces_of_node(ordered_intfs_tree,node)
for each interface of node
if intf.remote_node.IN_GADAG is false
@@ 2551,28 +2590,29 @@
add_eligible_interfaces_of_node(
ordered_intfs_tree,
y.local_node)
y = y.local_node.spf_prev_intf
Figure 35: SPFbased GADAG algorithm
Appendix B. Option 3: Computing GADAG using a hybrid method
In this option, the idea is to combine the salient features of the
 above two options. To this end, we process nodes as they get added
 to the GADAG just like in the lowpoint inheritance by maintaining a
 stack of nodes. This ensures that we do not need to maintain lower
 and higher sets at each node to ascertain ear directions since the
 ears will always be directed from the node being processed towards
 the end of the ear. To compute the ear however, we resort to an SPF
 to have the possibility of better ears (path lentghs) thus giving
 more flexibility than the restricted use of lowpoint/dfs parents.
+ lowpoint inheritance and SPF methods. To this end, we process nodes
+ as they get added to the GADAG just like in the lowpoint inheritance
+ by maintaining a stack of nodes. This ensures that we do not need to
+ maintain lower and higher sets at each node to ascertain ear
+ directions since the ears will always be directed from the node being
+ processed towards the end of the ear. To compute the ear however, we
+ resort to an SPF to have the possibility of better ears (path
+ lentghs) thus giving more flexibility than the restricted use of
+ lowpoint/dfs parents.
Regarding ears involving a block root, unlike the SPF method which
ignored interfaces of the block root after the first ear, in the
hybrid method we would have to process all interfaces of the block
root before moving on to other nodes in the block since the direction
of an ear is predetermined. Thus, whenever the block already has an
ear computed, and we are processing an interface of the block root,
we mark the block root as unusable before the SPF run that computes
the ear. This ensures that the SPF terminates at some node other
than the blockroot. This in turn guarantees that the blockroot has