 1/draftietfrtgwgmrtfrralgorithm07.txt 20160110 10:16:07.590547278 0800
+++ 2/draftietfrtgwgmrtfrralgorithm08.txt 20160110 10:16:07.890554636 0800
@@ 1,130 +1,131 @@
Routing Area Working Group G. Enyedi
InternetDraft A. Csaszar
Intended status: Standards Track Ericsson
Expires: June 23, 2016 A. Atlas
+Expires: July 13, 2016 A. Atlas
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
 December 21, 2015
+ January 10, 2016
 Algorithms for computing Maximally Redundant Trees for IP/LDP Fast
+ An Algorithm for Computing Maximally Redundant Trees for IP/LDP Fast
Reroute
 draftietfrtgwgmrtfrralgorithm07
+ draftietfrtgwgmrtfrralgorithm08
Abstract
A solution for IP and LDP FastReroute using Maximally Redundant
Trees is presented in draftietfrtgwgmrtfrrarchitecture. This
document defines the associated MRT Lowpoint algorithm that is used
 in the default MRT profile to compute both the necessary Maximally
+ in the Default MRT profile to compute both the necessary Maximally
Redundant Trees with their associated nexthops and the alternates to
select for MRTFRR.
Status of This Memo
This InternetDraft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
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 June 23, 2016.
+ This InternetDraft will expire on July 13, 2016.
Copyright Notice
 Copyright (c) 2015 IETF Trust and the persons identified as the
+ Copyright (c) 2016 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
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 7
+ 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
 4.2. Finding an Ear and the Correct Direction . . . . . . . . 9
+ 4.2. Finding an Ear and the Correct Direction . . . . . . . . 8
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. Interface Ordering . . . . . . . . . . . . . . . . . . . 19
 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22
 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23
 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23
 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
 inheritance . . . . . . . . . . . . . . . . . . . . . . . 24
 5.6. Augmenting the GADAG by directing all links . . . . . . . 26
 5.7. Compute MRT nexthops . . . . . . . . . . . . . . . . . . 30
+ 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
+ 4.5. Determining LocalRoot and Assigning BlockID . . . . . . 16
+ 5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18
+ 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18
+ 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21
+ 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
+ 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22
+ 5.5. Constructing the GADAG using lowpoint inheritance . . . . 23
+ 5.6. Augmenting the GADAG by directing all links . . . . . . . 25
+ 5.7. Compute MRT nexthops . . . . . . . . . . . . . . . . . . 29
5.7.1. MRT nexthops to all nodes ordered with respect to
 the computing node . . . . . . . . . . . . . . . . . 30
+ the computing node . . . . . . . . . . . . . . . . . 29
5.7.2. MRT nexthops to all nodes not ordered with respect
 to the computing node . . . . . . . . . . . . . . . . 31
+ to the computing node . . . . . . . . . . . . . . . . 30
5.7.3. Computing Redundant Tree nexthops in a 2connected
 Graph . . . . . . . . . . . . . . . . . . . . . . . . 32
 5.7.4. Generalizing for a graph that isn't 2connected . . . 34
 5.7.5. Complete Algorithm to Compute MRT NextHops . . . . . 35
 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37
 5.9. Named ProxyNodes . . . . . . . . . . . . . . . . . . . . 44
 5.9.1. Determining ProxyNode Attachment Routers . . . . . . 44
 5.9.2. Computing if an Island Neighbor (IN) is loopfree . . 45
 5.9.3. Computing MRT NextHops for ProxyNodes . . . . . . . 47
 5.9.4. Computing MRT Alternates for ProxyNodes . . . . . . 53
 6. MRT Lowpoint Algorithm: Nexthop conformance . . . . . . . . 61
 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 61
 7.1. Computing MRT nexthops on broadcast networks . . . . . . 62
+ Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
+ 5.7.4. Generalizing for a graph that isn't 2connected . . . 33
+ 5.7.5. Complete Algorithm to Compute MRT NextHops . . . . . 34
+ 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 36
+ 5.9. Named ProxyNodes . . . . . . . . . . . . . . . . . . . . 43
+ 5.9.1. Determining ProxyNode Attachment Routers . . . . . . 43
+ 5.9.2. Computing if an Island Neighbor (IN) is loopfree . . 44
+ 5.9.3. Computing MRT NextHops for ProxyNodes . . . . . . . 46
+ 5.9.4. Computing MRT Alternates for ProxyNodes . . . . . . 52
+ 6. MRT Lowpoint Algorithm: Nexthop conformance . . . . . . . . 60
+ 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 60
+ 7.1. Computing MRT nexthops on broadcast networks . . . . . . 61
7.2. Using MRT nexthops as alternates in the event of
 failures on broadcast networks . . . . . . . . . . . . . 63
 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 64
 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 104
 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 105
 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 115
 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 115
 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 115
 13. Security Considerations . . . . . . . . . . . . . . . . . . . 115
 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 115
 14.1. Normative References . . . . . . . . . . . . . . . . . . 115
 14.2. Informative References . . . . . . . . . . . . . . . . . 115
 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 117
 Appendix B. Option 3: Computing GADAG using a hybrid method . . 122
 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124
+ failures on broadcast networks . . . . . . . . . . . . . 62
+ 8. Evaluation of Alternative Methods for Constructing GADAGs . . 63
+ 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 64
+ 10. Operational Considerations . . . . . . . . . . . . . . . . . 65
+ 10.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 65
+ 10.2. Destinationrooted GADAGs . . . . . . . . . . . . . . . 65
+ 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 66
+ 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66
+ 13. Security Considerations . . . . . . . . . . . . . . . . . . . 66
+ 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 66
+ 14.1. Normative References . . . . . . . . . . . . . . . . . . 66
+ 14.2. Informative References . . . . . . . . . . . . . . . . . 66
+ Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 67
+ Appendix B. Constructing a GADAG using SPFs . . . . . . . . . . 108
+ Appendix C. Constructing a GADAG using a hybrid method . . . . . 113
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115
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
alternate to use. This document defines how to compute these three
things for use in MRTFRR and describes the algorithm design
decisions and rationale. The algorithm is based on those presented
in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint
 algorithm is required for implementation when the default MRT profile
+ algorithm is required for implementation when the Default MRT profile
is implemented.
Just as packets routed on a hopbyhop basis require that each router
compute a shortestpath tree which is consistent, it is necessary for
each router to compute the MRTBlue nexthops and MRTRed nexthops
in a consistent fashion. This document defines the MRT Lowpoint
algorithm to be used as a standard in the default MRT profile for
MRTFRR.
As now, a router's FIB will contain primary nexthops for the current
@@ 134,38 +135,40 @@
Red for forwarding received traffic on the MRTRed.
What alternate nexthops a pointoflocalrepair (PLR) selects need
not be consistent  but loops must be prevented. To reduce
congestion, it is possible for multiple alternate nexthops to be
selected; in the context of MRT alternates, each of those alternate
nexthops would be equalcost paths.
This document defines an algorithm for selecting an appropriate MRT
alternate for consideration. Other alternates, e.g. LFAs that are
 downstream paths, may be preferred when available and that policy
 based alternate selection process [ID.ietfrtgwglfamanageability]
 is not captured in this document.
+ downstream paths, may be preferred when available. See the
+ Operational Considerations section of
+ [ID.ietfrtgwgmrtfrrarchitecture] for a more detailed discussion
+ of combining MRT alternates with those produced by other FRR
+ technologies.
[E][D] [E]<[D]< [E]>[D]
    ^  
   V   V
[R] [F] [C] [R] [F] [C] [R] [F] [C]
   ^ ^  
     V 
[A][B] [A]>[B] [A][B]<
(a) (b) (c)
a 2connected graph MRTBlue towards R MRTRed towards R
Figure 1
 Algorithms for computing MRTs can handle arbitrary network topologies
+ The MRT Lowpoint algorithm can handle arbitrary network topologies
where the whole network graph is not 2connected, as in Figure 2, as
well as the easier case where the network graph is 2connected
(Figure 1). Each MRT is a spanning tree. The pair of MRTs provide
two paths from every node X to the root of the MRTs. Those paths
share the minimum number of nodes and the minimum number of links.
Each such shared node is a cutvertex. Any shared links are cut
links.
[E][D] [J]
    
@@ 190,96 +193,38 @@
Figure 2
2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
3. Terminology and Definitions
 network graph: A graph that reflects the network topology where all
 links connect exactly two nodes and broadcast links have been
 transformed into a pseudonode representation (e.g. in OSPF,
 viewing a Network LSA as representing a pseudonode).

 Redundant Trees (RT): A pair of trees where the path from any node X
 to the root R on the first tree is nodedisjoint with the path
 from the same node X to the root along the second tree. These can
 be computed in 2connected graphs.

 Maximally Redundant Trees (MRT): A pair of trees where the path
 from any node X to the root R along the first tree and the path
 from the same node X to the root along the second tree share the
 minimum number of nodes and the minimum number of links. Each
 such shared node is a cutvertex. Any shared links are cutlinks.
 Any RT is an MRT but many MRTs are not RTs.

 MRT Island: From the computing router, the set of routers that
 support a particular MRT profile and are connected.

 MRTRed: MRTRed is used to describe one of the two MRTs; it is
 used to describe the associated forwarding topology and MTID.
 Specifically, MRTRed is the decreasing MRT where links in the
 GADAG are taken in the direction from a higher topologically
 ordered node to a lower one.

 MRTBlue: MRTBlue is used to describe one of the two MRTs; it is
 used to describe the associated forwarding topology and MTID.
 Specifically, MRTBlue is the increasing MRT where links in the
 GADAG are taken in the direction from a lower topologically
 ordered node to a higher one.

 cutvertex: A vertex whose removal partitions the network.

 cutlink: A link whose removal partitions the network. A cutlink
 by definition must be connected between two cutvertices. If
 there are multiple parallel links, then they are referred to as
 cutlinks in this document if removing the set of parallel links
 would partition the network.

 2connected: A graph that has no cutvertices. This is a graph
 that requires two nodes to be removed before the network is
 partitioned.
+ Please see the Terminology section of
+ [ID.ietfrtgwgmrtfrrarchitecture] for a complete list of
+ terminology relevant to this draft. The list below does not repeat
+ terminology introduced in that draft.
spanning tree: A tree containing links that connects all nodes in
the network graph.
backedge: In the context of a spanning tree computed via a depth
first search, a backedge is a link that connects a descendant of
a node x with an ancestor of x.
 2connected cluster: A maximal set of nodes that are 2connected.
 In a network graph with at least one cutvertex, there will be
 multiple 2connected clusters.

 block: Either a 2connected cluster, a cutlink, or an isolated
 vertex.

 DAG: Directed Acyclic Graph  a digraph containing no directed
 cycle.

 ADAG: Almost Directed Acyclic Graph  a digraph that can be
 transformed into a DAG with removing a single node (the root
 node).

partial ADAG: A subset of an ADAG that doesn't yet contain all the
nodes in the block. A partial ADAG is created during the MRT
algorithm and then expanded until all nodes in the block are
included and it is an ADAG.
 GADAG: Generalized ADAG  a digraph, which has only ADAGs as all of
 its blocks. The root of such a block is the node closest to the
 global root (e.g. with uniform link costs).

DFS: DepthFirst Search

DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS
tree path from the DFS root to x.
DFS descendant: A node n is a DFS descendant of x if x is on the
DFStree path from the DFS root to n.
ear: A path along notyetincludedintheGADAG nodes that starts
at a node that is alreadyincludedintheGADAG and that ends at a
node that is alreadyincludedintheGADAG. The starting and
ending nodes may be the same node if it is a cutvertex.
@@ 287,49 +232,47 @@
X >> Y or Y << X: Indicates the relationship between X and Y in a
partial order, such as found in a GADAG. X >> Y means that X is
higher in the partial order than Y. Y << X means that Y is lower
in the partial order than X.
X > Y or Y < X: Indicates the relationship between X and Y in the
total order, such as found via a topological sort. X > Y means
that X is higher in the total order than Y. Y < X means that Y is
lower in the total order than X.
 proxynode: A node added to the network graph to represent a multi
 homed prefix or routers outside the local MRTfastreroute
 supporting island of routers. The key property of proxynodes is
 that traffic cannot transit them.
+ X ?? Y: Indicates that X is unordered with respect to Y in the
+ partial order.
UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING
or both. Until the directionality of the link is determined, the
link is marked as UNDIRECTED to indicate that its direction hasn't
been determined.
OUTGOING: A link marked as OUTGOING has direction in the GADAG from
the interface's router to the remote end.
INCOMING: A link marked as INCOMING has direction in the GADAG from
the remote end to the interface's router.
4. Algorithm Key Concepts
There are five key concepts that are critical for understanding the
 MRT Lowpoint algorithm and other algorithms for computing MRTs. The
 first is the idea of partially ordering the nodes in a network graph
 with regard to each other and to the GADAG root. The second is the
 idea of finding an ear of nodes and adding them in the correct
 direction. The third is the idea of a LowPoint value and how it can
 be used to identify cutvertices and to find a second path towards
 the root. The fourth is the idea that a non2connected graph is
 made up of blocks, where a block is a 2connected cluster, a cutlink
 or an isolated node. The fifth is the idea of a localroot for each
 node; this is used to compute ADAGs in each block.
+ MRT Lowpoint algorithm. The first is the idea of partially ordering
+ the nodes in a network graph with regard to each other and to the
+ GADAG root. The second is the idea of finding an ear of nodes and
+ adding them in the correct direction. The third is the idea of a
+ LowPoint value and how it can be used to identify cutvertices and
+ to find a second path towards the root. The fourth is the idea that
+ a non2connected graph is made up of blocks, where a block is a
+ 2connected cluster, a cutlink or an isolated node. The fifth is
+ the idea of a localroot for each node; this is used to compute ADAGs
+ in each block.
4.1. Partial Ordering for Disjoint Paths
Given any two nodes X and Y in a graph, a particular total order
means that either X < Y or X > Y in that total order. An example
would be a graph where the nodes are ranked based upon their unique
IP loopback addresses. In a partial order, there may be some nodes
for which it can't be determined whether X << Y or X >> Y. A partial
order can be captured in a directed graph, as shown in Figure 3. In
a graphical representation, a link directed from X to Y indicates
@@ 480,27 +423,29 @@
while there exists connected nodes in graph that are not IN_GADAG
Select a new ear. Let its endpoints be X and Y.
if Y is root or (Y << X)
add the ear towards X to the ADAG
else // (a) X is root or (b)X << Y or (c) X, Y not ordered
Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to find ears and their direction in
2connected graph
 Algorithm Figure 6 merely requires that a cycle or ear be selected
 without specifying how. Regardless of the way of selecting the path,
 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.5. Other methods are described
 in the Appendices (Appendix A and Appendix B).
+ The algorithm in Figure 6 merely requires that a cycle or ear be
+ selected without specifying how. Regardless of the method for
+ selecting the path, 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 uses the LowPoint
+ Inheritance method for constructing an ADAG (and ultimately a GADAG).
+ This method is defined in Section 5.5. Other methods for
+ constructing GADAGs are described in Appendix B and Appendix C. An
+ evaluation of these different methods is given in Section 8
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.
@@ 642,25 +587,25 @@
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
 isolated nodes). To compute GADAGs and thus MRTs, computation is
 done in each block to compute ADAGs or Redundant Trees and then those
 ADAGs or Redundant Trees are combined into a GADAG or MRT.
+ A key idea for the MRT Lowpoint algorithm is that any non2connected
+ graph is made up by blocks (e.g. 2connected clusters, cutlinks,
+ and/or isolated nodes). To compute GADAGs and thus MRTs, computation
+ is done in each block to compute ADAGs or Redundant Trees and then
+ those ADAGs or Redundant Trees are combined into a GADAG or MRT.
[E] [J][I] [P][O]
     
     
[R] [D][C][F] [H][K] [N]
     
     
[A][B] [G] [L][M]
(a) A graph with four blocks that are:
@@ 678,21 +623,21 @@
(b) MRTBlue for destination R
[E] [J]>[I] [P]>[O]
  
V V V
[R] [D]>[C]<[F] [H]<[K] [N]
^  ^  ^ 
 V    V
[A]<[B] [G]< [L]<[M]
 (c) MRTRed for destionation R
+ (c) MRTRed for destination R
Figure 10
Consider the example depicted in Figure 10 (a). In this figure, a
special graph is presented, showing us all the ways 2connected
clusters can be connected. It has four blocks: block 1 contains R,
A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K,
L, M, N, O, P, and block 4 is a cutlink containing H and K. As can
be observed, the first two blocks have one common node (node C) and
blocks 2 and 3 do not have any common node, but they are connected
@@ 734,22 +679,22 @@
else
mark x as cutvertex
Compute_Localroot(c, x)
Compute_Localroot(gadag_root, gadag_root)
Figure 11: A method for computing localroots
There are two different ways of computing the localroot for each
node. The standalone method is given in Figure 11 and better
 illustrates the concept; it is used by the MRT algorithms given in
 the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm
+ illustrates the concept; it is used by the GADAG construction methods
+ given in Appendix B and Appendix C. The MRT Lowpoint algorithm
computes the localroot for a block as part of computing the GADAG
using lowpoint inheritance; the essence of this computation is given
in Figure 12. Both methods for computing the localroot produce the
same results.
Get the current node, s.
Compute an ear(either through lowpoint inheritance
or by following dfs parents) from s to a ready node e.
(Thus, s is not e, if there is such ear.)
if s is e
@@ 787,50 +732,53 @@
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else
Assign_Block_ID(c, cur_block_id)
max_block_id = 0
Assign_Block_ID(gadag_root, max_block_id)
Figure 13: Assigning block id to identify blocks
5. Algorithm Sections
+5. MRT Lowpoint Algorithm Specification
 This algorithm computes one GADAG that is then used by a router to
 determine its MRTBlue and MRTRed nexthops to all destinations.
 Finally, based upon that information, alternates are selected for
 each nexthop to each destination. The different parts of this
 algorithm are described below. These work on a network graph after
 its interfaces have been ordered as per Figure 14.
+ The MRT Lowpoint algorithm computes one GADAG that is then used by a
+ router to determine its MRTBlue and MRTRed nexthops to all
+ destinations. Finally, based upon that information, alternates are
+ selected for each nexthop to each destination. The different parts
+ of this algorithm are described below.
 1. Compute the local MRT Island for the particular MRT Profile.
 [See Section 5.2.]
+ o Order the interfaces in the network graph. [See Section 5.1]
 2. Select the root to use for the GADAG. [See Section 5.3.]
+ o Compute the local MRT Island for the particular MRT Profile. [See
+ Section 5.2]
 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.]
+ o Select the root to use for the GADAG. [See Section 5.3]
 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See
 Figure 8.]
+ o Initialize all interfaces to UNDIRECTED. [See Section 5.4]
 5. Construct the GADAG. [See Section 5.5]
+ o Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See
+ Figure 8]
 6. Assign directions to all interfaces that are still UNDIRECTED.
 [See Section 5.6.]
+ o Construct the GADAG. [See Section 5.5]
 7. From the computing router x, compute the nexthops for the MRT
 Blue and MRTRed. [See Section 5.7.]
+ o Assign directions to all interfaces that are still UNDIRECTED.
+ [See Section 5.6]
 8. Identify alternates for each nexthop to each destination by
+ o From the computing router x, compute the nexthops for the MRT
+ Blue and MRTRed. [See Section 5.7]
+
+ o Identify alternates for each nexthop to each destination by
determining which one of the blue MRT and the red MRT the
 computing router x should select. [See Section 5.8.]
+ 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
@@ 867,25 +815,25 @@
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 that criteria is not specified here since it 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 (or flooding protocol in the case of ISISPCR
 [ID.ietfisispcr]) and applications is specified in Figure 15. The
 metric and mrt_node_id values for OSPFv2, OSPFv3, and ISIS provided
 here is normative. The metric and mrt_node_id values for ISISPCR
 should be considered informational.
+ IGPs and applications is specified in Figure 15. The metric and
+ mrt_node_id values for OSPFv2, OSPFv3, and ISIS provided here is
+ normative. The metric and mrt_node_id values for ISISPCR 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  pointtopoint link 
@@ 928,30 +876,20 @@
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 ISIS for IP/LDP FRR with pointtopoint
links, the pseudonode number (the 7th octet) is zero. Broadcast
interfaces will be discussed in Section 7.
 In the case of ISIS for IP/LDP FRR, this specification allows for
 the use of MultiTopology routing. [RFC5120] requires that
 information related to the standard/default topology (MTID = 0) be
 carried in the Extended IS Reachability TLV #22, while it requires
 that the MultiTopology IS Neighbor TLV #222 only be used to carry
 topology information related to nondefault topologies (with nonzero
 MTIDs). [RFC5120] enforces this by requiring an implementation to
 ignore TLV#222 with MTID = 0. The current document also requires
 that TLV#222 with MTID = 0 MUST be ignored.

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 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.
@@ 972,78 +910,75 @@
intf.remote_node.IN_MRT_ISLAND = TRUE
if (not intf.remote_node.IN_MRT_ISLAND))
intf.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, intf.remote_node)
Figure 16: MRT Island Identification
5.3. GADAG Root Selection
In Section 8.3 of [ID.ietfrtgwgmrtfrrarchitecture], the GADAG
 Root Selection Policy is described for the MRT default profile. In
 [ID.ietfospfmrt] and [ID.ietfisismrt], 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.
+ Root Selection Policy is described for the MRT default 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.
 Analysis has shown that the centrality of a router can have a
 significant impact on the lengths of the alternate paths computed.
 Therefore, it is RECOMMENDED that offline analysis that considers
 the centrality of a router be used to help determine how good a
 choice a particular router is for the role of GADAG root.
+ 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 10.1.
5.4. Initialization
Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFSvalues,
lowpointvalues, DFSparents, lowpointparents, any MRTcomputed
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.
 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.ietfospfmrt] [ID.ietfisismrt] by the
 owner of the interface, so that links are known to be MRTineligible
 and not explored or used in the MRT algorithm. When a either
 interface on a link is advertised as MRTineligible, the link MUST
 NOT be included in the MRT Island, and will thus be excluded from the
 GADAG. Computation of MRT nexthops will therefore not use any MRT
+ 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 [ID.ietfrtgwgmrtfrrarchitecture] describes how
+ those links and nodes are excluded from MRT Island formation.
+
+ MRTFRR also has the ability to advertise links MRTIneligible, as
+ described in Section 7.3.2 of [ID.ietfrtgwgmrtfrrarchitecture].
+ These links are excluded from the MRT Island and the GADAG.
+ Computation of MRT nexthops will therefore not use any MRT
ineligible links. The MRT algorithm does still need to consider MRT
ineligible links when computing FRR alternates, because an MRT
ineligible link can still be the shortestpath nexthop to reach a
destination.
When a broadcast interface is advertised as MRTineligible, 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. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance
+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 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
associated interfaces are marked based on the direction taken. The
nodes in the ear are marked as IN_GADAG. In the algorithm, first the
@@ 1144,21 +1078,21 @@
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is not x))
Construct_Ear(x, Stack, intf, NEIGHBOR)
Construct_GADAG_via_Lowpoint(topology, gadag_root)
Figure 17: Lowpoint Inheritance GADAG algorithm
5.6. Augmenting the GADAG by directing all links
 The GADAG, regardless of the algorithm used to construct it, at this
+ 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
@@ 2915,21 +2850,237 @@
alternates. For example, when the PLR observes that connectivity to
an IPlayer node on a broadcast network has failed, the PLR may
choose to still use the broadcast network to reach other IPlayer
nodes which are still reachable. Or if the PLR observes that
connectivity has failed to several IPlayer nodes on the same
broadcast network, it may choose to treat the entire broadcast
network as failed. The choice of MRT alternates by a PLR for a
particular set of failure conditions is a local decision, since it
does not require coordination with other nodes.
8. Python Implementation of MRT Lowpoint Algorithm
+8. Evaluation of Alternative Methods for Constructing GADAGs
+
+ This document specifies the MRT Lowpoint algorithm. One component of
+ the algorithm involves constructing a common GADAG based on the
+ network topology. The MRT Lowpoint algorithm computes the GADAG
+ using the method described in Section 5.5. This method aims to
+ minimize the amount of computation required to compute the GADAG. In
+ the process of developing the MRT Lowpoint algorithm, two alternative
+ methods for constructing GADAGs were also considered. These
+ alternative methods are described in Appendix B and Appendix C. In
+ general, these other two methods require more computation to compute
+ the GADAG. The analysis below was performed to determine if the
+ alternative GADAG construction methods produce shorter MRT alternate
+ paths in real network topologies, and if so, to what extent.
+
+ Figure 30 compares results obtained using the three different methods
+ for constructing GADAGs on five different service provider network
+ topologies. MRT_LOWPOINT indicates the method specified in
+ Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods
+ specified in Appendix B and Appendix C, respectively. The columns on
+ the right present the distribution of alternate path lengths for each
+ GADAG construction method. Each MRT computation was performed using
+ a same GADAG root chosen based on centrality.
+
+ For three of the topologies analyzed (T201, T206, and T211), the use
+ of MRT_SPF or MRT_HYBRID methods does not appear to provide a
+ significantly shorter alternate path lengths compared to the
+ MRT_LOWPOINT method. However, for two of the topologies (T216 and
+ T219), the use of the MRT_SPF method resulted in noticeably shorter
+ alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID
+ methods.
+
+ It was decided to use the MRT_LOWPOINT method to construct the GADAG
+ in the algorithm specified in this draft, in order to initially offer
+ an algorithm with lower computational requirements. These results
+ indicate that in the future it may be useful to evaluate and
+ potentially specify other MRT algorithm variants that use different
+ GADAG construction methods.
+
+ ++
+  Topology name  percentage of failure scenarios 
+   protected by an alternate N hops 
+  GADAG construction  longer than the primary path 
+  method ++
+           no 
+       10 12 14  alt
+  0123456789111315 <16
+ +++++++++++
+  T201(avg primary hops=3.5)          
+  MRT_HYBRID  33 26 23 6 3    
+  MRT_SPF  33 36 23 6 3    
+  MRT_LOWPOINT  33 36 23 6 3    
+ +++++++++++
+  T206(avg primary hops=3.7)          
+  MRT_HYBRID  50 35 13 2     
+  MRT_SPF  50 35 13 2     
+  MRT_LOWPOINT  55 32 13      
+ +++++++++++
+  T211(avg primary hops=3.3)          
+  MRT_HYBRID  86 14       
+  MRT_SPF  86 14       
+  MRT_LOWPOINT  85 15 1      
+ +++++++++++
+  T216(avg primary hops=5.2)          
+  MRT_HYBRID  23 22 18 13 10 7 4 2 2
+  MRT_SPF  35 32 19 9 3 1   
+  MRT_LOWPOINT  28 25 18 11 7 6 3 2 1
+ +++++++++++
+  T219(avg primary hops=7.7)          
+  MRT_HYBRID  20 16 13 10 7 5 5 5 3
+  MRT_SPF  31 23 19 12 7 4 2 1 
+  MRT_LOWPOINT  19 14 15 12 10 8 7 6 10
+ +++++++++++
+
+ Figure 30
+
+9. Implementation Status
+
+ [RFC Editor: please remove this section prior to publication.]
+
+ Please see [ID.ietfrtgwgmrtfrrarchitecture] for details on
+ implementation status.
+
+10. Operational Considerations
+
+ This sections discusses operational considerations related to the the
+ MRT Lowpoint algorithm and other potential MRT algorithm variants.
+ For a discussion of operational considerations related to MRTFRR in
+ general, see the Operational Considerations section of
+ [ID.ietfrtgwgmrtfrrarchitecture].
+
+10.1. GADAG Root Selection
+
+ The Default MRT Profile uses the GADAG Root Selection Priority
+ advertised by routers as the primary criterion for selecting the
+ GADAG root. It is RECOMMENDED that an operator 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. Criteria for making this designation
+ are discussed below.
+
+ Analysis has shown that the centrality of a router can have a
+ significant impact on the lengths of the alternate paths computed.
+ Therefore, it is RECOMMENDED that offline analysis that considers
+ the centrality of a router be used to help determine how good a
+ choice a particular router is for the role of GADAG root.
+
+ If the router currently selected as GADAG root becomes unreachable in
+ the IGP topology, then a new GADAG root will be selected. Changing
+ the GADAG root can change the overall structure of the GADAG as well
+ the paths of the red and blue MRT trees built using that GADAG. In
+ order to minimize change in the associated red and blue MRT
+ forwarding entries that can result from changing the GADAG root, it
+ is RECOMMENDED that operators prioritize for selection as GADAG root
+ those routers that are expected to consistently remain part of the
+ IGP topology.
+
+10.2. Destinationrooted GADAGs
+
+ The MRT Lowpoint algorithm constructs a single GADAG rooted at a
+ single node selected as the GADAG root. It is also possible to
+ construct a different GADAG for each destination, with the GADAG
+ rooted at the destination. A router can compute the MRTRed and MRT
+ Blue nexthops for that destination based on the GADAG rooted at that
+ destination. Building a different GADAG for each destination is
+ computationally more expensive, but it may give somewhat shorter
+ alternate paths. Using destinationrooted GADAGs would require a new
+ MRT profile to be created with a new MRT algorithm specification,
+ since all routers in the MRT Island would need to use destination
+ rooted GADAGs.
+
+11. Acknowledgements
+
+ The authors would like to thank Shraddha Hegde, Eric Wu, Janos
+ Farkas, and Stewart Bryant for their suggestions and review. We
+ would also like to thank Anil Kumar SN for his assistance in
+ clarifying the algorithm description and pseudocode.
+
+12. IANA Considerations
+
+ This document includes no request to IANA.
+
+13. Security Considerations
+
+ The algorithm described in this document does not introduce new
+ security concerns beyond those already discussed in the document
+ describing the MRT FRR architecture
+ [ID.ietfrtgwgmrtfrrarchitecture].
+
+14. References
+
+14.1. Normative References
+
+ [ID.ietfrtgwgmrtfrrarchitecture]
+ Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
+ A., Tantsura, J., and R. White, "An Architecture for IP/
+ LDP FastReroute Using Maximally Redundant Trees", draft
+ ietfrtgwgmrtfrrarchitecture07 (work in progress),
+ October 2015.
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119,
+ DOI 10.17487/RFC2119, March 1997,
+ .
+
+14.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, .
+
+ [IEEE8021Qca]
+ IEEE 802.1, "IEEE 802.1Qca Bridges and Bridged Networks 
+ Amendment: Path Control and Reservation  Draft 2.1",
+ (work in progress), June 24, 2015,
+ .
+
+ [ISO10589SecondEdition]
+ International Organization for Standardization,
+ "Intermediate system to Intermediate system intradomain
+ routeing information exchange protocol for use in
+ conjunction with the protocol for providing the
+ connectionlessmode Network Service (ISO 8473)", ISO/
+ IEC 10589:2002, Second Edition, Nov. 2002.
+
+ [Kahn_1962_topo_sort]
+ Kahn, A., "Topological sorting of large networks",
+ Communications of the ACM, Volume 5, Issue 11 , Nov 1962,
+ .
+
+ [MRTLinear]
+ Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
+ Maximally Redundant Trees in Strictly Linear Time", IEEE
+ Symposium on Computers and Comunications (ISCC) , 2009,
+ .
+
+ [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
+ DOI 10.17487/RFC2328, April 1998,
+ .
+
+ [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "MISIS: Multi
+ Topology (MT) Routing in Intermediate System to
+ Intermediate Systems (ISISs)", RFC 5120,
+ DOI 10.17487/RFC5120, February 2008,
+ .
+
+ [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
+ So, "Remote LoopFree Alternate (LFA) Fast Reroute (FRR)",
+ RFC 7490, DOI 10.17487/RFC7490, April 2015,
+ .
+
+Appendix A. Python Implementation of MRT Lowpoint Algorithm
Below is Python code implementing the MRT Lowpoint algorithm
specified in this document. In order to avoid the page breaks in the
.txt version of the draft, one can cut and paste the Python code from
the .xml version. The code is also posted on Github.
While this Python code is believed to correctly implement the pseudo
code description of the algorithm, in the event of a difference, the
pseudocode description should be considered normative.
@@ 4880,587 +5029,26 @@
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
Generate_Basic_Topology_and_Run_MRT()
Generate_Complex_Topology_and_Run_MRT()
9. 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
 computationally more expensive, but may give somewhat shorter
 alternate paths. It may be useful for livelive multicast along
 MRTs.

9.1. Algorithm Evaluation

 The MRT Lowpoint algorithm is the lowest computation of the MRT
 algorithms. Two other MRT algorithms are provided in Appendix A and
 Appendix B. When analyzed on service provider network topologies,
 they did not provide significant differences in the path lenghts for
 the alternatives. This section does not focus on that analysis or
 the decision to use the MRT Lowpoint algorithm as the default MRT
 algorithm; it has the lowest computational and storage requirements
 and gave comparable results.

 Since this document defines the MRT Lowpoint algorithm for use in
 fastreroute applications, it is useful to compare MRT and Remote LFA
 [RFC7490]. This section compares MRT and remote LFA for IP Fast
 Reroute in 19 service provider network topologies, focusing on
 coverage and alternate path length. Figure 30 shows the node
 protecting coverage provided by local LFA (LLFA), remote LFA (RLFA),
 and MRT against different failure scenarios in these topologies. The
 coverage values are calculated as the percentage of source
 destination pairs protected by the given IPFRR method relative to
 those protectable by optimal routing, against the same failure modes.
 More details on alternate selection policies used for this analysis
 are described later in this section.

 +++
  Topology  percentage of failure 
   scenarios covered by 
   IPFRR method 
  +
   NP_LLFA  NP_RLFA  MRT 
 +++++
  T201  37  90  100 
  T202  73  83  100 
  T203  51  80  100 
  T204  55  81  100 
  T205  92  93  100 
  T206  71  74  100 
  T207  57  74  100 
  T208  66  81  100 
  T209  79  79  100 
  T210  95  98  100 
  T211  68  71  100 
  T212  59  63  100 
  T213  84  84  100 
  T214  68  78  100 
  T215  84  88  100 
  T216  43  59  100 
  T217  78  88  100 
  T218  72  75  100 
  T219  78  84  100 
 +++++

 Figure 30

 For the topologies analyzed here, LLFA is able to provide node
 protecting coverage ranging from 37% to 95% of the sourcedestination
 pairs, as seen in the column labeled NP_LLFA. The use of RLFA in
 addition to LLFA is generally able to increase the nodeprotecting
 coverage. The percentage of nodeprotecting coverage with RLFA is
 provided in the column labeled NP_RLFA, ranges from 59% to 98% for
 these topologies. The nodeprotecting coverage provided by MRT is
 100% since MRT is able to provide protection for any source
 destination pair for which a path still exists after the failure.

 We would also like to measure the quality of the alternate paths
 produced by these different IPFRR methods. An obvious approach is to
 take an average of the alternate path costs over all source
 destination pairs and failure modes. However, this presents a
 problem, which we will illustrate by presenting an example of results
 for one topology using this approach ( Figure 31). In this table,
 the average relative path length is the alternate path length for the
 IPFRR method divided by the optimal alternate path length, averaged
 over all sourcedestination pairs and failure modes. The first three
 columns of data in the table give the path length calculated from the
 sum of IGP metrics of the links in the path. The results for
 topology T208 show that the metricbased path lengths for NP_LLFA and
 NP_RLFA alternates are on average 78 and 66 times longer than the
 path lengths for optimal alternates. The metricbased path lengths
 for MRT alternates are on average 14 times longer than for optimal
 alternates.

 +++
   average relative alternate path length 
  ++
 Topology IGP metric  hopcount 
  ++
  NP_LLFA NP_RLFA  MRT NP_LLFA NP_RLFA  MRT 
 ++++++++
  T208  78.2  66.0  13.6 0.99  1.01  1.32 
 ++++++++

 Figure 31

 The network topology represented by T208 uses values of 10, 100, and
 1000 as IGP costs, so small deviations from the optimal alternate
 path can result in large differences in relative path length. LLFA,
 RLFA, and MRT all allow for at least one hop in the alterate path to
 be chosen independent of the cost of the link. This can easily
 result in an alternate using a link with cost 1000, which introduces
 noise into the path length measurement. In the case of T208, the
 adverse effects of using metricbased path lengths is obvious.
 However, we have observed that the metricbased path length
 introduces noise into alternate path length measurements in several
 other topologies as well. For this reason, we have opted to measure
 the alternate path length using hopcount. While IGP metrics may be
 adjusted by the network operator for a number of reasons (e.g.
 traffic engineering), the hopcount is a fairly stable measurement of
 path length. As shown in the last three columns of Figure 31, the
 hopcountbased alternate path lengths for topology T208 are fairly
 wellbehaved.

 Figure 32, Figure 33, Figure 34, and Figure 35 present the hopcount
 based path length results for the 19 topologies examined. The
 topologies in the four tables are grouped based on the size of the
 topologies, as measured by the number of nodes, with Figure 32 having
 the smallest topologies and Figure 35 having the largest topologies.
 Instead of trying to represent the path lengths of a large set of
 alternates with a single number, we have chosen to present a
 histogram of the path lengths for each IPFRR method and alternate
 selection policy studied. The first eight colums of data represent
 the percentage of failure scenarios protected by an alternate N hops
 longer than the primary path, with the first column representing an
 alternate 0 or 1 hops longer than the primary path, all the way up
 through the eighth column respresenting an alternate 14 or 15 hops
 longer than the primary path. The last column in the table gives the
 percentage of failure scenarios for which there is no alternate less
 than 16 hops longer than the primary path. In the case of LLFA and
 RLFA, this category includes failure scenarios for which no alternate
 was found.

 For each topology, the first row (labeled OPTIMAL) is the
 distribution of the number of hops in excess of the primary path
 hopcount for optimally routed alternates. (The optimal routing was
 done with respect to IGP metrics, as opposed to hopcount.) The
 second row(labeled NP_LLFA) is the distribution of the extra hops for
 nodeprotecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA)
 is the hopcount distribution when one adds nodeprotecting RLFA to
 increase the coverage. The alternate selection policy used here
 first tries to find a nodeprotecting LLFA. If that does not exist,
 then it tries to find an RLFA, and checks if it is nodeprotecting.
 Comparing the hopcount distribution for RLFA and LLFA across these
 topologies, one can see how the coverage is increased at the expense
 of using longer alternates. It is also worth noting that while
 superficially LLFA and RLFA appear to have better hopcount
 distributions than OPTIMAL, the presence of entries in the last
 column (no alternate < 16) mainly represent failure scenarios that
 are not protected, for which the hopcount is effectively infinite.

 The fourth and fifth rows of each topology show the hopcount
 distributions for two alternate selection policies using MRT
 alternates. The policy represented by the label
 NP_LLFA_THEN_MRT_LOWPOINT will first use a nodeprotecting LLFA. If
 a nodeprotecting LLFA does not exist, then it will use an MRT
 alternate. The policy represented by the label MRT_LOWPOINT instead
 will use the MRT alternate even if a nodeprotecting LLFA exists.
 One can see from the data that combining nodeprotecting LLFA with
 MRT results in a significant shortening of the alternate hopcount
 distribution.

 ++
   percentage of failure scenarios 
  Topology name  protected by an alternate N hops 
  and  longer than the primary path 
  alternate selection ++
  policy evaluated          no 
       10 12 14  alt
  0123456789111315 <16
 +++++++++++
  T201(avg primary hops=3.5)          
  OPTIMAL  37 37 20 3 3    
  NP_LLFA  37        63
  NP_LLFA_THEN_NP_RLFA  37 34 19      10
  NP_LLFA_THEN_MRT_LOWPOINT  37 33 21 6 3    
  MRT_LOWPOINT  33 36 23 6 3    
 +++++++++++
  T202(avg primary hops=4.8)          
  OPTIMAL  90 9       
  NP_LLFA  71 2       27
  NP_LLFA_THEN_NP_RLFA  78 5       17
  NP_LLFA_THEN_MRT_LOWPOINT  80 12 5 2 1    
  MRT_LOWPOINT_ONLY  48 29 13 7 2 1   
 +++++++++++
  T203(avg primary hops=4.1)          
  OPTIMAL  36 37 21 4 2    
  NP_LLFA  34 15 3      49
  NP_LLFA_THEN_NP_RLFA  35 19 22 4     20
  NP_LLFA_THEN_MRT_LOWPOINT  36 35 22 5 2    
  MRT_LOWPOINT_ONLY  31 35 26 7 2    
 +++++++++++
  T204(avg primary hops=3.7)          
  OPTIMAL  76 20 3 1     
  NP_LLFA  54 1       45
  NP_LLFA_THEN_NP_RLFA  67 10 4      19
  NP_LLFA_THEN_MRT_LOWPOINT  70 18 8 3 1    
  MRT_LOWPOINT_ONLY  58 27 11 3 1    
 +++++++++++
  T205(avg primary hops=3.4)          
  OPTIMAL  92 8       
  NP_LLFA  89 3       8
  NP_LLFA_THEN_NP_RLFA  90 4       7
  NP_LLFA_THEN_MRT_LOWPOINT  91 9       
  MRT_LOWPOINT_ONLY  62 33 5 1     
 +++++++++++

 Figure 32

 ++
   percentage of failure scenarios 
  Topology name  protected by an alternate N hops 
  and  longer than the primary path 
  alternate selection ++
  policy evaluated          no 
       10 12 14  alt
  0123456789111315 <16
 +++++++++++
  T206(avg primary hops=3.7)          
  OPTIMAL  63 30 7      
  NP_LLFA  60 9 1      29
  NP_LLFA_THEN_NP_RLFA  60 13 1      26
  NP_LLFA_THEN_MRT_LOWPOINT  64 29 7      
  MRT_LOWPOINT  55 32 13      
 +++++++++++
  T207(avg primary hops=3.9)          
  OPTIMAL  71 24 5 1     
  NP_LLFA  55 2       43
  NP_LLFA_THEN_NP_RLFA  63 10       26
  NP_LLFA_THEN_MRT_LOWPOINT  70 20 7 2 1    
  MRT_LOWPOINT_ONLY  57 29 11 3 1    
 +++++++++++
  T208(avg primary hops=4.6)          
  OPTIMAL  58 28 12 2 1    
  NP_LLFA  53 11 3      34
  NP_LLFA_THEN_NP_RLFA  56 17 7 1     19
  NP_LLFA_THEN_MRT_LOWPOINT  58 19 10 7 3 1   
  MRT_LOWPOINT_ONLY  34 24 21 13 6 2 1  
 +++++++++++
  T209(avg primary hops=3.6)          
  OPTIMAL  85 14 1      
  NP_LLFA  79        21
  NP_LLFA_THEN_NP_RLFA  79        21
  NP_LLFA_THEN_MRT_LOWPOINT  82 15 2      
  MRT_LOWPOINT_ONLY  63 29 8      
 +++++++++++
  T210(avg primary hops=2.5)          
  OPTIMAL  95 4 1      
  NP_LLFA  94 1       5
  NP_LLFA_THEN_NP_RLFA  94 3 1      2
  NP_LLFA_THEN_MRT_LOWPOINT  95 4 1      
  MRT_LOWPOINT_ONLY  91 6 2      
 +++++++++++

 Figure 33

 ++
   percentage of failure scenarios 
  Topology name  protected by an alternate N hops 
  and  longer than the primary path 
  alternate selection ++
  policy evaluated          no 
       10 12 14  alt
  0123456789111315 <16
 +++++++++++
  T211(avg primary hops=3.3)          
  OPTIMAL  88 11       
  NP_LLFA  66 1       32
  NP_LLFA_THEN_NP_RLFA  68 3       29
  NP_LLFA_THEN_MRT_LOWPOINT  88 12       
  MRT_LOWPOINT  85 15 1      
 +++++++++++
  T212(avg primary hops=3.5)          
  OPTIMAL  76 23 1      
  NP_LLFA  59        41
  NP_LLFA_THEN_NP_RLFA  61 1 1      37
  NP_LLFA_THEN_MRT_LOWPOINT  75 24 1      
  MRT_LOWPOINT_ONLY  66 31 3      
 +++++++++++
  T213(avg primary hops=4.3)          
  OPTIMAL  91 9       
  NP_LLFA  84        16
  NP_LLFA_THEN_NP_RLFA  84        16
  NP_LLFA_THEN_MRT_LOWPOINT  89 10 1      
  MRT_LOWPOINT_ONLY  75 24 1      
 +++++++++++
  T214(avg primary hops=5.8)          
  OPTIMAL  71 22 5 2     
  NP_LLFA  58 8 1 1     32
  NP_LLFA_THEN_NP_RLFA  61 13 3 1     22
  NP_LLFA_THEN_MRT_LOWPOINT  66 14 7 5 3 2 1 1 1
  MRT_LOWPOINT_ONLY  30 20 18 12 8 4 3 2 3
 +++++++++++
  T215(avg primary hops=4.8)          
  OPTIMAL  73 27       
  NP_LLFA  73 11       16
  NP_LLFA_THEN_NP_RLFA  73 13 2      12
  NP_LLFA_THEN_MRT_LOWPOINT  74 19 3 2 1 1 1  
  MRT_LOWPOINT_ONLY  32 31 16 12 4 3 1  
 +++++++++++

 Figure 34

 ++
   percentage of failure scenarios 
  Topology name  protected by an alternate N hops 
  and  longer than the primary path 
  alternate selection ++
  policy evaluated          no 
       10 12 14  alt
  0123456789111315 <16
 +++++++++++
  T216(avg primary hops=5.2)          
  OPTIMAL  60 32 7 1     
  NP_LLFA  39 4       57
  NP_LLFA_THEN_NP_RLFA  46 12 2      41
  NP_LLFA_THEN_MRT_LOWPOINT  48 20 12 7 5 4 2 1 1
  MRT_LOWPOINT  28 25 18 11 7 6 3 2 1
 +++++++++++
  T217(avg primary hops=8.0)          
  OPTIMAL  81 13 5 1     
  NP_LLFA  74 3 1      22
  NP_LLFA_THEN_NP_RLFA  76 8 3 1     12
  NP_LLFA_THEN_MRT_LOWPOINT  77 7 5 4 3 2 1 1 
  MRT_LOWPOINT_ONLY  25 18 18 16 12 6 3 1 
 +++++++++++
  T218(avg primary hops=5.5)          
  OPTIMAL  85 14 1      
  NP_LLFA  68 3       28
  NP_LLFA_THEN_NP_RLFA  71 4       25
  NP_LLFA_THEN_MRT_LOWPOINT  77 12 7 4 1    
  MRT_LOWPOINT_ONLY  37 29 21 10 3 1   
 +++++++++++
  T219(avg primary hops=7.7)          
  OPTIMAL  77 15 5 1 1    
  NP_LLFA  72 5       22
  NP_LLFA_THEN_NP_RLFA  73 8 2      16
  NP_LLFA_THEN_MRT_LOWPOINT  74 8 3 3 2 2 2 2 4
  MRT_LOWPOINT_ONLY  19 14 15 12 10 8 7 6 10
 +++++++++++

 Figure 35

 In the preceding analysis, the following procedure for selecting an
 RLFA was used. Nodes were ordered with respect to distance from the
 source and checked for membership in Q and Pspace. The first node
 to satisfy this condition was selected as the RLFA. More
 sophisticated methods to select nodeprotecting RLFAs is an area of
 active research.

 The analysis presented above uses the MRT Lowpoint Algorithm defined
 in this specification with a common GADAG root. The particular
 choice of a common GADAG root is expected to affect the quality of
 the MRT alternate paths, with a more central common GADAG root
 resulting in shorter MRT alternate path lengths. For the analysis
 above, the GADAG root was chosen for each topology by calculating
 node centrality as the sum of costs of all shortest paths to and from
 a given node. The node with the lowest sum was chosen as the common
 GADAG root. In actual deployments, the common GADAG root would be
 chosen based on the GADAG Root Selection Priority advertised by each
 router, the values of which would be determined offline.

 In order to measure how sensitive the MRT alternate path lengths are
 to the choice of common GADAG root, we performed the same analysis
 using different choices of GADAG root. All of the nodes in the
 network were ordered with respect to the node centrality as computed
 above. Nodes were chosen at the 0th, 25th, and 50th percentile with
 respect to the centrality ordering, with 0th percentile being the
 most central node. The distribution of alternate path lengths for
 those three choices of GADAG root are shown in Figure 36 for a subset
 of the 19 topologies (chosen arbitrarily). The third row for each
 topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the
 results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth
 rows show the alternate path length distibution for the 25th and 50th
 percentile choice for GADAG root. One can see some impact on the
 path length distribution with the less central choice of GADAG root
 resulting in longer path lenghths.

 We also looked at the impact of MRT algorithm variant on the
 alternate path lengths. The first two rows for each topology present
 results of the same alternate path length distribution analysis for
 the SPF and Hybrid methods for computing the GADAG. These two
 methods are described in Appendix A and Appendix B. For three of the
 topologies in this subset (T201, T206, and T211), the use of SPF or
 Hybrid methods does not appear to provide a significant advantage
 over the Lowpoint method with respect to path length. Instead, the
 choice of GADAG root appears to have more impact on the path length.
 However, for two of the topologies in this subset(T216 and T219) and
 for this particular choice of GAGAG root, the use of the SPF method
 results in noticeably shorter alternate path lengths than the use of
 the Lowpoint or Hybrid methods. It remains to be determined if this
 effect applies generally across more topologies or is sensitive to
 choice of GADAG root.

 ++
  Topology name  percentage of failure scenarios 
   protected by an alternate N hops 
  MRT algorithm variant  longer than the primary path 
  ++
  (GADAG root          no 
  centrality percentile)      10 12 14  alt
  0123456789111315 <16
 +++++++++++
  T201(avg primary hops=3.5)          
  MRT_HYBRID ( 0 percentile)  33 26 23 6 3    
  MRT_SPF ( 0 percentile)  33 36 23 6 3    
  MRT_LOWPOINT ( 0 percentile)  33 36 23 6 3    
  MRT_LOWPOINT (25 percentile)  27 29 23 11 10    
  MRT_LOWPOINT (50 percentile)  27 29 23 11 10    
 +++++++++++
  T206(avg primary hops=3.7)          
  MRT_HYBRID ( 0 percentile)  50 35 13 2     
  MRT_SPF ( 0 percentile)  50 35 13 2     
  MRT_LOWPOINT ( 0 percentile)  55 32 13      
  MRT_LOWPOINT (25 percentile)  47 25 22 6     
  MRT_LOWPOINT (50 percentile)  38 38 14 11     
 +++++++++++
  T211(avg primary hops=3.3)          
  MRT_HYBRID ( 0 percentile)  86 14       
  MRT_SPF ( 0 percentile)  86 14       
  MRT_LOWPOINT ( 0 percentile)  85 15 1      
  MRT_LOWPOINT (25 percentile)  70 25 5 1     
  MRT_LOWPOINT (50 percentile)  80 18 2      
 +++++++++++
  T216(avg primary hops=5.2)          
  MRT_HYBRID ( 0 percentile)  23 22 18 13 10 7 4 2 2
  MRT_SPF ( 0 percentile)  35 32 19 9 3 1   
  MRT_LOWPOINT ( 0 percentile)  28 25 18 11 7 6 3 2 1
  MRT_LOWPOINT (25 percentile)  24 20 19 16 10 6 3 1 
  MRT_LOWPOINT (50 percentile)  19 14 13 10 8 6 5 5 10
 +++++++++++
  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 36

10. Implementation Status

 [RFC Editor: please remove this section prior to publication.]

 Please see [ID.ietfrtgwgmrtfrrarchitecture] for details on
 implementation status.

11. Acknowledgements

 The authors would like to thank Shraddha Hegde, Eric Wu, and Janos
 Farkas for their suggestions and review. We would also like to thank
 Anil Kumar SN for his assistance in clarifying the algorithm
 description and pseudocode.

12. IANA Considerations

 This document includes no request to IANA.

13. Security Considerations

 The algorithm described in this document does not introduce new
 security concerns beyond those already discussed in the document
 describing the MRT FRR architecture
 [ID.ietfrtgwgmrtfrrarchitecture].

14. References

14.1. Normative References

 [ID.ietfrtgwgmrtfrrarchitecture]
 Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
 A., Tantsura, J., and R. White, "An Architecture for IP/
 LDP FastReroute Using Maximally Redundant Trees", draft
 ietfrtgwgmrtfrrarchitecture07 (work in progress),
 October 2015.

 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
 Requirement Levels", BCP 14, RFC 2119,
 DOI 10.17487/RFC2119, March 1997,
 .

14.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.ietfisismrt]
 Li, Z., Wu, N., <>, Q., Atlas, A., Bowers, C., and J.
 Tantsura, "Intermediate System to Intermediate System (IS
 IS) Extensions for Maximally Redundant Trees (MRT)",
 draftietfisismrt01 (work in progress), October 2015.

 [ID.ietfisispcr]
 Farkas, J., Bragg, N., Unbehagen, P., Parsons, G.,
 AshwoodSmith, P., and C. Bowers, "ISIS Path Computation
 and Reservation", draftietfisispcr04 (work in
 progress), December 2015.

 [ID.ietfospfmrt]
 Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
 "OSPF Extensions to Support Maximally Redundant Trees",
 draftietfospfmrt01 (work in progress), October 2015.

 [ID.ietfrtgwglfamanageability]
 Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
 Horneffer, M., and P. Sarkar, "Operational management of
 Loop Free Alternates", draftietfrtgwglfa
 manageability11 (work in progress), June 2015.

 [ISO10589SecondEdition]
 International Organization for Standardization,
 "Intermediate system to Intermediate system intradomain
 routeing information exchange protocol for use in
 conjunction with the protocol for providing the
 connectionlessmode Network Service (ISO 8473)", ISO/
 IEC 10589:2002, Second Edition, Nov. 2002.

 [Kahn_1962_topo_sort]
 Kahn, A., "Topological sorting of large networks",
 Communications of the ACM, Volume 5, Issue 11 , Nov 1962,
 .

 [MRTLinear]
 Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
 Maximally Redundant Trees in Strictly Linear Time", IEEE
 Symposium on Computers and Comunications (ISCC) , 2009,
 .

 [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
 DOI 10.17487/RFC2328, April 1998,
 .

 [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "MISIS: Multi
 Topology (MT) Routing in Intermediate System to
 Intermediate Systems (ISISs)", RFC 5120,
 DOI 10.17487/RFC5120, February 2008,
 .

 [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
 So, "Remote LoopFree Alternate (LFA) Fast Reroute (FRR)",
 RFC 7490, DOI 10.17487/RFC7490, April 2015,
 .

Appendix A. Option 2: Computing GADAG using SPFs
+Appendix B. Constructing a GADAG using SPFs
 The basic idea in this option is to use slightlymodified SPF
 computations to find ears. In every block, an SPF computation is
 first done to find a cycle from the local root and then SPF
 computations in that block find ears until there are no more
+ The basic idea in this method for constructing a GADAG is to use
+ slightlymodified SPF computations to find ears. In every block, an
+ SPF computation is first done to find a cycle from the local root and
+ then SPF computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops
from the mininized IN_GADAG node back to the SPF root.
To do this, first all cutvertices must be identified and localroots
assigned as specified in Figure 12.
The slight modifications to the SPF are as follows. The root of the
block is referred to as the blockroot; it is either the GADAG root
or a cutvertex.
@@ 5513,48 +5101,49 @@
and cand_intf.local_node as TEMP_UNUSABLE
if cand_intf.local_node is not block_root
Mark cand_intf.local_node as TEMP_UNUSABLE
Initialize ear_list to empty
end_ear = Mod_SPF(spf_root, block_root)
y = end_ear.spf_prev_hop
while y.local_node is not spf_root
add_to_list_start(ear_list, y)
y.local_node.IN_GADAG = true
y = y.local_node.spf_prev_intf

if(method is not hybrid)
Set_Ear_Direction(ear_list, cand_intf.local_node,
end_ear,block_root)
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 37: Modified SPF for GADAG computation
+ Figure 31: Modified SPF for GADAG construction
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.5, 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.
+ nodes higher in the partial order. In this GADAG construction
+ method, 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
second set, Lower_Nodes, contains all nodes that are known to be
 ordered below the node. This is the approach used in this algorithm.
+ ordered below the node. This is the approach used in this GADAG
+ construction method.
Set_Ear_Direction(ear_list, end_a, end_b, block_root)
// Default of A_TO_B for the following cases:
// (a) end_a and end_b are the same (root)
// or (b) end_a is in end_b's Lower Nodes
// or (c) end_a and end_b were unordered with respect to each
// other
direction = A_TO_B
if (end_b is block_root) and (end_a is not end_b)
direction = B_TO_A
@@ 5585,41 +5174,43 @@
add i.local_node to x.Higher_Nodes
else
foreach node x where x.localroot is block_root
if end_b is in x.Lower_Nodes
foreach interface i in ear_list
add i.local_node to x.Lower_Nodes
if end_a is in x.Higher_Nodes
foreach interface i in ear_list
add i.remote_node to x.Higher_Nodes
 Figure 38: Algorithm to assign links of an ear direction
+ Figure 32: Algorithm to assign links of an ear direction
 A goal of the algorithm is to find the shortest cycles and ears. An
 ear is started by going to a neighbor x of an IN_GADAG node y. The
 path from x to an IN_GADAG node is minimal, since it is computed via
 SPF. Since a shortest path is made of shortest paths, to find the
 shortest ears requires reaching from the set of IN_GADAG nodes to the
 closest node that isn't IN_GADAG. Therefore, an ordered tree is
 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.
+ A goal of this GADAG construction method is to find the shortest
+ cycles and ears. An ear is started by going to a neighbor x of an
+ IN_GADAG node y. The path from x to an IN_GADAG node is minimal,
+ since it is computed via SPF. Since a shortest path is made of
+ shortest paths, to find the shortest ears requires reaching from the
+ set of IN_GADAG nodes to the closest node that isn't IN_GADAG.
+ Therefore, an ordered tree is 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, based on the Interface_Compare
+ function defined 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
 was seen in Section 5.7. 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.
+ This GADAG construction method ignores interfaces picked from the
+ ordered list 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 was seen in Section 5.7. 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
@@ 5664,25 +5255,25 @@
ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.remote_node,
cand_intf.remote_node.localroot,
SPF method)
y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node(
ordered_intfs_tree, y.local_node)
y = y.local_node.spf_prev_intf
 Figure 39: SPFbased GADAG algorithm
+ Figure 33: SPFbased method for GADAG construction
Appendix B. Option 3: Computing GADAG using a hybrid method
+Appendix C. Constructing a GADAG using a hybrid method
 In this option, the idea is to combine the salient features of the
+ The idea of this method is to combine the salient features of the
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.
@@ 5693,21 +5284,21 @@
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
only one incoming interface in each block, which is necessary for
correctly computing the nexthops on the GADAG.
As in the SPF gadag, bridge ears are handled as a special case.
 The entire algorithm is shown below in Figure 40
+ The entire algorithm is shown below in Figure 34
find_spf_stack_ear(stack, x, y, xy_intf, block_root)
if L(y) == D(y)
// Special case for cutlinks
xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true
xy_intf.INCOMING = true
xy_intf.remote_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true
@@ 5743,21 +5334,21 @@
root.IN_GADAG = true
Initialize Stack to empty
push root onto Stack
while (Stack is not empty)
x = pop(Stack)
for each interface intf of x
y = intf.remote_node
if y.IN_GADAG is false
find_spf_stack_ear(stack, x, y, intf, y.block_root)
 Figure 40: Hybrid GADAG algorithm
+ Figure 34: Hybrid GADAG construction method
Authors' Addresses
Gabor Sandor Enyedi
Ericsson
Konyves Kalman krt 11
Budapest 1097
Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com