draft-ietf-rtgwg-mrt-frr-algorithm-07.txt   draft-ietf-rtgwg-mrt-frr-algorithm-08.txt 
Routing Area Working Group G. Enyedi Routing Area Working Group G. Enyedi
Internet-Draft A. Csaszar Internet-Draft A. Csaszar
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: June 23, 2016 A. Atlas Expires: July 13, 2016 A. Atlas
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona 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 Reroute
draft-ietf-rtgwg-mrt-frr-algorithm-07 draft-ietf-rtgwg-mrt-frr-algorithm-08
Abstract Abstract
A solution for IP and LDP Fast-Reroute using Maximally Redundant A solution for IP and LDP Fast-Reroute using Maximally Redundant
Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This
document defines the associated MRT Lowpoint algorithm that is used 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 next-hops and the alternates to Redundant Trees with their associated next-hops and the alternates to
select for MRT-FRR. select for MRT-FRR.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on June 23, 2016. This Internet-Draft will expire on July 13, 2016.
Copyright Notice 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. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 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.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. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 15 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 16
5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18
5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22
5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 5.5. Constructing the GADAG using lowpoint inheritance . . . . 23
inheritance . . . . . . . . . . . . . . . . . . . . . . . 24 5.6. Augmenting the GADAG by directing all links . . . . . . . 25
5.6. Augmenting the GADAG by directing all links . . . . . . . 26 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29
5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30
5.7.1. MRT next-hops to all nodes ordered with respect to 5.7.1. MRT next-hops to all nodes ordered with respect to
the computing node . . . . . . . . . . . . . . . . . 30 the computing node . . . . . . . . . . . . . . . . . 29
5.7.2. MRT next-hops to all nodes not ordered with respect 5.7.2. MRT next-hops to all nodes not ordered with respect
to the computing node . . . . . . . . . . . . . . . . 31 to the computing node . . . . . . . . . . . . . . . . 30
5.7.3. Computing Redundant Tree next-hops in a 2-connected 5.7.3. Computing Redundant Tree next-hops in a 2-connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 32 Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
5.7.4. Generalizing for a graph that isn't 2-connected . . . 34 5.7.4. Generalizing for a graph that isn't 2-connected . . . 33
5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 34
5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 36
5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 43
5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 44 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 43
5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 45 5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 44
5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 47 5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 46
5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 52
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 61 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 60
7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 61 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 60
7.1. Computing MRT next-hops on broadcast networks . . . . . . 62 7.1. Computing MRT next-hops on broadcast networks . . . . . . 61
7.2. Using MRT next-hops as alternates in the event of 7.2. Using MRT next-hops as alternates in the event of
failures on broadcast networks . . . . . . . . . . . . . 63 failures on broadcast networks . . . . . . . . . . . . . 62
8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 64 8. Evaluation of Alternative Methods for Constructing GADAGs . . 63
9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 104 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 64
9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 105 10. Operational Considerations . . . . . . . . . . . . . . . . . 65
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 115 10.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 65
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 115 10.2. Destination-rooted GADAGs . . . . . . . . . . . . . . . 65
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 115 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 66
13. Security Considerations . . . . . . . . . . . . . . . . . . . 115 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 115 13. Security Considerations . . . . . . . . . . . . . . . . . . . 66
14.1. Normative References . . . . . . . . . . . . . . . . . . 115 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 66
14.2. Informative References . . . . . . . . . . . . . . . . . 115 14.1. Normative References . . . . . . . . . . . . . . . . . . 66
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 117 14.2. Informative References . . . . . . . . . . . . . . . . . 66
Appendix B. Option 3: Computing GADAG using a hybrid method . . 122 Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 67
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124 Appendix B. Constructing a GADAG using SPFs . . . . . . . . . . 108
Appendix C. Constructing a GADAG using a hybrid method . . . . . 113
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115
1. Introduction 1. Introduction
MRT Fast-Reroute requires that packets can be forwarded not only on MRT Fast-Reroute requires that packets can be forwarded not only on
the shortest-path tree, but also on two Maximally Redundant Trees the shortest-path tree, but also on two Maximally Redundant Trees
(MRTs), referred to as the MRT-Blue and the MRT-Red. A router which (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which
experiences a local failure must also have pre-determined which experiences a local failure must also have pre-determined which
alternate to use. This document defines how to compute these three alternate to use. This document defines how to compute these three
things for use in MRT-FRR and describes the algorithm design things for use in MRT-FRR and describes the algorithm design
decisions and rationale. The algorithm is based on those presented decisions and rationale. The algorithm is based on those presented
in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint 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. is implemented.
Just as packets routed on a hop-by-hop basis require that each router Just as packets routed on a hop-by-hop basis require that each router
compute a shortest-path tree which is consistent, it is necessary for compute a shortest-path tree which is consistent, it is necessary for
each router to compute the MRT-Blue next-hops and MRT-Red next-hops each router to compute the MRT-Blue next-hops and MRT-Red next-hops
in a consistent fashion. This document defines the MRT Lowpoint in a consistent fashion. This document defines the MRT Lowpoint
algorithm to be used as a standard in the default MRT profile for algorithm to be used as a standard in the default MRT profile for
MRT-FRR. MRT-FRR.
As now, a router's FIB will contain primary next-hops for the current As now, a router's FIB will contain primary next-hops for the current
skipping to change at page 3, line 51 skipping to change at page 4, line 4
Red for forwarding received traffic on the MRT-Red. Red for forwarding received traffic on the MRT-Red.
What alternate next-hops a point-of-local-repair (PLR) selects need What alternate next-hops a point-of-local-repair (PLR) selects need
not be consistent - but loops must be prevented. To reduce not be consistent - but loops must be prevented. To reduce
congestion, it is possible for multiple alternate next-hops to be congestion, it is possible for multiple alternate next-hops to be
selected; in the context of MRT alternates, each of those alternate selected; in the context of MRT alternates, each of those alternate
next-hops would be equal-cost paths. next-hops would be equal-cost paths.
This document defines an algorithm for selecting an appropriate MRT This document defines an algorithm for selecting an appropriate MRT
alternate for consideration. Other alternates, e.g. LFAs that are alternate for consideration. Other alternates, e.g. LFAs that are
downstream paths, may be preferred when available and that policy- downstream paths, may be preferred when available. See the
based alternate selection process [I-D.ietf-rtgwg-lfa-manageability] Operational Considerations section of
is not captured in this document. [I-D.ietf-rtgwg-mrt-frr-architecture] for a more detailed discussion
of combining MRT alternates with those produced by other FRR
technologies.
[E]---[D]---| [E]<--[D]<--| [E]-->[D] [E]---[D]---| [E]<--[D]<--| [E]-->[D]
| | | | ^ | | | | | | ^ | |
| | | V | | V | | | V | | V
[R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C]
| | | ^ ^ | | | | | ^ ^ | |
| | | | | V | | | | | | V |
[A]---[B]---| [A]-->[B] [A]---[B]<--| [A]---[B]---| [A]-->[B] [A]---[B]<--|
(a) (b) (c) (a) (b) (c)
a 2-connected graph MRT-Blue towards R MRT-Red towards R a 2-connected graph MRT-Blue towards R MRT-Red towards R
Figure 1 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 2-connected, as in Figure 2, as where the whole network graph is not 2-connected, as in Figure 2, as
well as the easier case where the network graph is 2-connected well as the easier case where the network graph is 2-connected
(Figure 1). Each MRT is a spanning tree. The pair of MRTs provide (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 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. share the minimum number of nodes and the minimum number of links.
Each such shared node is a cut-vertex. Any shared links are cut- Each such shared node is a cut-vertex. Any shared links are cut-
links. links.
[E]---[D]---| |---[J] [E]---[D]---| |---[J]
| | | | | | | | | |
skipping to change at page 5, line 13 skipping to change at page 5, line 35
Figure 2 Figure 2
2. Requirements Language 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
3. Terminology and Definitions 3. Terminology and Definitions
network graph: A graph that reflects the network topology where all Please see the Terminology section of
links connect exactly two nodes and broadcast links have been [I-D.ietf-rtgwg-mrt-frr-architecture] for a complete list of
transformed into a pseudonode representation (e.g. in OSPF, terminology relevant to this draft. The list below does not repeat
viewing a Network LSA as representing a pseudonode). terminology introduced in that draft.
Redundant Trees (RT): A pair of trees where the path from any node X
to the root R on the first tree is node-disjoint with the path
from the same node X to the root along the second tree. These can
be computed in 2-connected 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 cut-vertex. Any shared links are cut-links.
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.
MRT-Red: MRT-Red is used to describe one of the two MRTs; it is
used to describe the associated forwarding topology and MT-ID.
Specifically, MRT-Red is the decreasing MRT where links in the
GADAG are taken in the direction from a higher topologically
ordered node to a lower one.
MRT-Blue: MRT-Blue is used to describe one of the two MRTs; it is
used to describe the associated forwarding topology and MT-ID.
Specifically, MRT-Blue is the increasing MRT where links in the
GADAG are taken in the direction from a lower topologically
ordered node to a higher one.
cut-vertex: A vertex whose removal partitions the network.
cut-link: A link whose removal partitions the network. A cut-link
by definition must be connected between two cut-vertices. If
there are multiple parallel links, then they are referred to as
cut-links in this document if removing the set of parallel links
would partition the network.
2-connected: A graph that has no cut-vertices. This is a graph
that requires two nodes to be removed before the network is
partitioned.
spanning tree: A tree containing links that connects all nodes in spanning tree: A tree containing links that connects all nodes in
the network graph. the network graph.
back-edge: In the context of a spanning tree computed via a depth- back-edge: In the context of a spanning tree computed via a depth-
first search, a back-edge is a link that connects a descendant of first search, a back-edge is a link that connects a descendant of
a node x with an ancestor of x. a node x with an ancestor of x.
2-connected cluster: A maximal set of nodes that are 2-connected.
In a network graph with at least one cut-vertex, there will be
multiple 2-connected clusters.
block: Either a 2-connected cluster, a cut-link, 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 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 nodes in the block. A partial ADAG is created during the MRT
algorithm and then expanded until all nodes in the block are algorithm and then expanded until all nodes in the block are
included and it is an ADAG. 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: Depth-First Search DFS: Depth-First Search
DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- 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. tree path from the DFS root to x.
DFS descendant: A node n is a DFS descendant of x if x is on the DFS descendant: A node n is a DFS descendant of x if x is on the
DFS-tree path from the DFS root to n. DFS-tree path from the DFS root to n.
ear: A path along not-yet-included-in-the-GADAG nodes that starts ear: A path along not-yet-included-in-the-GADAG nodes that starts
at a node that is already-included-in-the-GADAG and that ends at a at a node that is already-included-in-the-GADAG and that ends at a
node that is already-included-in-the-GADAG. The starting and node that is already-included-in-the-GADAG. The starting and
ending nodes may be the same node if it is a cut-vertex. ending nodes may be the same node if it is a cut-vertex.
skipping to change at page 7, line 15 skipping to change at page 6, line 25
X >> Y or Y << X: Indicates the relationship between X and Y in a 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 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 higher in the partial order than Y. Y << X means that Y is lower
in the partial order than X. in the partial order than X.
X > Y or Y < X: Indicates the relationship between X and Y in the 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 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 that X is higher in the total order than Y. Y < X means that Y is
lower in the total order than X. lower in the total order than X.
proxy-node: A node added to the network graph to represent a multi- X ?? Y: Indicates that X is unordered with respect to Y in the
homed prefix or routers outside the local MRT-fast-reroute- partial order.
supporting island of routers. The key property of proxy-nodes is
that traffic cannot transit them.
UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING
or both. Until the directionality of the link is determined, the or both. Until the directionality of the link is determined, the
link is marked as UNDIRECTED to indicate that its direction hasn't link is marked as UNDIRECTED to indicate that its direction hasn't
been determined. been determined.
OUTGOING: A link marked as OUTGOING has direction in the GADAG from OUTGOING: A link marked as OUTGOING has direction in the GADAG from
the interface's router to the remote end. the interface's router to the remote end.
INCOMING: A link marked as INCOMING has direction in the GADAG from INCOMING: A link marked as INCOMING has direction in the GADAG from
the remote end to the interface's router. the remote end to the interface's router.
4. Algorithm Key Concepts 4. Algorithm Key Concepts
There are five key concepts that are critical for understanding the There are five key concepts that are critical for understanding the
MRT Lowpoint algorithm and other algorithms for computing MRTs. The MRT Lowpoint algorithm. The first is the idea of partially ordering
first is the idea of partially ordering the nodes in a network graph the nodes in a network graph with regard to each other and to the
with regard to each other and to the GADAG root. The second is the GADAG root. The second is the idea of finding an ear of nodes and
idea of finding an ear of nodes and adding them in the correct adding them in the correct direction. The third is the idea of a
direction. The third is the idea of a Low-Point value and how it can Low-Point value and how it can be used to identify cut-vertices and
be used to identify cut-vertices and to find a second path towards to find a second path towards the root. The fourth is the idea that
the root. The fourth is the idea that a non-2-connected graph is a non-2-connected graph is made up of blocks, where a block is a
made up of blocks, where a block is a 2-connected cluster, a cut-link 2-connected cluster, a cut-link or an isolated node. The fifth is
or an isolated node. The fifth is the idea of a local-root for each the idea of a local-root for each node; this is used to compute ADAGs
node; this is used to compute ADAGs in each block. in each block.
4.1. Partial Ordering for Disjoint Paths 4.1. Partial Ordering for Disjoint Paths
Given any two nodes X and Y in a graph, a particular total order 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 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 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 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 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 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 a graphical representation, a link directed from X to Y indicates
skipping to change at page 11, line 22 skipping to change at page 10, line 37
while there exists connected nodes in graph that are not IN_GADAG while there exists connected nodes in graph that are not IN_GADAG
Select a new ear. Let its endpoints be X and Y. Select a new ear. Let its endpoints be X and Y.
if Y is root or (Y << X) if Y is root or (Y << X)
add the ear towards X to the ADAG add the ear towards X to the ADAG
else // (a) X is root or (b)X << Y or (c) X, Y not ordered else // (a) X is root or (b)X << Y or (c) X, Y not ordered
Add the ear towards Y to the ADAG Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to find ears and their direction in Figure 6: Generic Algorithm to find ears and their direction in
2-connected graph 2-connected graph
Algorithm Figure 6 merely requires that a cycle or ear be selected The algorithm in Figure 6 merely requires that a cycle or ear be
without specifying how. Regardless of the way of selecting the path, selected without specifying how. Regardless of the method for
we will get an ADAG. The method used for finding and selecting the selecting the path, we will get an ADAG. The method used for finding
ears is important; shorter ears result in shorter paths along the and selecting the ears is important; shorter ears result in shorter
MRTs. The MRT Lowpoint algorithm's method using Low-Point paths along the MRTs. The MRT Lowpoint algorithm uses the Low-Point
Inheritance is defined in Section 5.5. Other methods are described Inheritance method for constructing an ADAG (and ultimately a GADAG).
in the Appendices (Appendix A and Appendix B). 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 As an example, consider Figure 5 again. First, we select the
shortest cycle containing R, which can be R-A-B-F-D-E (uniform link shortest cycle containing R, which can be R-A-B-F-D-E (uniform link
costs were assumed), so we get to the situation depicted in Figure 5 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 (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 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 C to R without B in the original graph. The first ready node along
this is node D, so the open ear is B-C-D. Since B<<D, we add arc this is node D, so the open ear is B-C-D. Since B<<D, we add arc
B->C and C->D to the ADAG. Since all the nodes are ready, we stop at B->C and C->D to the ADAG. Since all the nodes are ready, we stop at
this point. this point.
skipping to change at page 15, line 24 skipping to change at page 14, line 24
Third, as seen in Figure 9, 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 DFS-child of a node while other that contains both the root and a DFS-child of a node while other
DFS-children might be in different blocks. In this example, C's DFS-children 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 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 realize that the root of a block may also be the root of another
block. block.
4.4. Blocks in a Graph 4.4. Blocks in a Graph
A key idea for an MRT algorithm is that any non-2-connected graph is A key idea for the MRT Lowpoint algorithm is that any non-2-connected
made up by blocks (e.g. 2-connected clusters, cut-links, and/or graph is made up by blocks (e.g. 2-connected clusters, cut-links,
isolated nodes). To compute GADAGs and thus MRTs, computation is and/or isolated nodes). To compute GADAGs and thus MRTs, computation
done in each block to compute ADAGs or Redundant Trees and then those is done in each block to compute ADAGs or Redundant Trees and then
ADAGs or Redundant Trees are combined into a GADAG or MRT. those ADAGs or Redundant Trees are combined into a GADAG or MRT.
[E]---| [J]-------[I] [P]---[O] [E]---| [J]-------[I] [P]---[O]
| | | | | | | | | | | |
| | | | | | | | | | | |
[R] [D]---[C]--[F] [H]---[K] [N] [R] [D]---[C]--[F] [H]---[K] [N]
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]--------[B] [G]---| [L]---[M] [A]--------[B] [G]---| [L]---[M]
(a) A graph with four blocks that are: (a) A graph with four blocks that are:
skipping to change at page 16, line 35 skipping to change at page 15, line 35
(b) MRT-Blue for destination R (b) MRT-Blue for destination R
[E]---| [J]-------->[I] [P]-->[O] [E]---| [J]-------->[I] [P]-->[O]
| | | | | |
V V V V V V
[R] [D]-->[C]<---[F] [H]<---[K] [N] [R] [D]-->[C]<---[F] [H]<---[K] [N]
^ | ^ | ^ | ^ | ^ | ^ |
| V | | | V | V | | | V
[A]<-------[B] [G]<--| [L]<--[M] [A]<-------[B] [G]<--| [L]<--[M]
(c) MRT-Red for destionation R (c) MRT-Red for destination R
Figure 10 Figure 10
Consider the example depicted in Figure 10 (a). In this figure, a Consider the example depicted in Figure 10 (a). In this figure, a
special graph is presented, showing us all the ways 2-connected special graph is presented, showing us all the ways 2-connected
clusters can be connected. It has four blocks: block 1 contains R, 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, 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 cut-link containing H and K. As can L, M, N, O, P, and block 4 is a cut-link containing H and K. As can
be observed, the first two blocks have one common node (node C) and 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 blocks 2 and 3 do not have any common node, but they are connected
skipping to change at page 17, line 46 skipping to change at page 16, line 46
else else
mark x as cut-vertex mark x as cut-vertex
Compute_Localroot(c, x) Compute_Localroot(c, x)
Compute_Localroot(gadag_root, gadag_root) Compute_Localroot(gadag_root, gadag_root)
Figure 11: A method for computing local-roots Figure 11: A method for computing local-roots
There are two different ways of computing the local-root for each There are two different ways of computing the local-root for each
node. The stand-alone method is given in Figure 11 and better node. The stand-alone method is given in Figure 11 and better
illustrates the concept; it is used by the MRT algorithms given in illustrates the concept; it is used by the GADAG construction methods
the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm given in Appendix B and Appendix C. The MRT Lowpoint algorithm
computes the local-root for a block as part of computing the GADAG computes the local-root for a block as part of computing the GADAG
using lowpoint inheritance; the essence of this computation is given using lowpoint inheritance; the essence of this computation is given
in Figure 12. Both methods for computing the local-root produce the in Figure 12. Both methods for computing the local-root produce the
same results. same results.
Get the current node, s. Get the current node, s.
Compute an ear(either through lowpoint inheritance Compute an ear(either through lowpoint inheritance
or by following dfs parents) from s to a ready node e. or by following dfs parents) from s to a ready node e.
(Thus, s is not e, if there is such ear.) (Thus, s is not e, if there is such ear.)
if s is e if s is e
skipping to change at page 19, line 5 skipping to change at page 18, line 5
max_block_id += 1 max_block_id += 1
Assign_Block_ID(c, max_block_id) Assign_Block_ID(c, max_block_id)
else else
Assign_Block_ID(c, cur_block_id) Assign_Block_ID(c, cur_block_id)
max_block_id = 0 max_block_id = 0
Assign_Block_ID(gadag_root, max_block_id) Assign_Block_ID(gadag_root, max_block_id)
Figure 13: Assigning block id to identify blocks 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 The MRT Lowpoint algorithm computes one GADAG that is then used by a
determine its MRT-Blue and MRT-Red next-hops to all destinations. router to determine its MRT-Blue and MRT-Red next-hops to all
Finally, based upon that information, alternates are selected for destinations. Finally, based upon that information, alternates are
each next-hop to each destination. The different parts of this selected for each next-hop to each destination. The different parts
algorithm are described below. These work on a network graph after of this algorithm are described below.
its interfaces have been ordered as per Figure 14.
1. Compute the local MRT Island for the particular MRT Profile. o Order the interfaces in the network graph. [See Section 5.1]
[See Section 5.2.]
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 o Initialize all interfaces to UNDIRECTED. [See Section 5.4]
Figure 8.]
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. o Construct the GADAG. [See Section 5.5]
[See Section 5.6.]
7. From the computing router x, compute the next-hops for the MRT- o Assign directions to all interfaces that are still UNDIRECTED.
Blue and MRT-Red. [See Section 5.7.] [See Section 5.6]
8. Identify alternates for each next-hop to each destination by o From the computing router x, compute the next-hops for the MRT-
determining which one of the blue MRT and the red MRT the Blue and MRT-Red. [See Section 5.7]
computing router x should select. [See Section 5.8.]
o Identify alternates for each next-hop 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]
A Python implementation of this algorithm is given in Appendix A.
5.1. Interface Ordering 5.1. Interface Ordering
To ensure consistency in computation, all routers MUST order To ensure consistency in computation, all routers MUST order
interfaces identically down to the set of links with the same metric interfaces identically down to the set of links with the same metric
to the same neighboring node. This is necessary for the DFS in to the same neighboring node. This is necessary for the DFS in
Lowpoint_Visit in Section 4.3, where the selection order of the Lowpoint_Visit in Section 4.3, where the selection order of the
interfaces to explore results in different trees. Consistent interfaces to explore results in different trees. Consistent
interface ordering is also necessary for computing the GADAG, where interface ordering is also necessary for computing the GADAG, where
the selection order of the interfaces to use to form ears can result the selection order of the interfaces to use to form ears can result
skipping to change at page 20, line 37 skipping to change at page 19, line 40
parallel links will be added to the GADAG with the same direction parallel links will be added to the GADAG with the same direction
assigned during the procedure for assigning direction to UNDIRECTED assigned during the procedure for assigning direction to UNDIRECTED
links described in Section 5.6. An implementation is free to apply links described in Section 5.6. An implementation is free to apply
some additional criteria to break ties in interface ordering in this some additional criteria to break ties in interface ordering in this
situation, but that criteria is not specified here since it will not situation, but that criteria is not specified here since it will not
affect the final GADAG produced by the algorithm. affect the final GADAG produced by the algorithm.
The Interface_Compare function in Figure 14 relies on the The Interface_Compare function in Figure 14 relies on the
interface.metric and the interface.neighbor.mrt_node_id values to interface.metric and the interface.neighbor.mrt_node_id values to
order interfaces. The exact source of these values for different order interfaces. The exact source of these values for different
IGPs (or flooding protocol in the case of ISIS-PCR IGPs and applications is specified in Figure 15. The metric and
[I-D.ietf-isis-pcr]) and applications is specified in Figure 15. The mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is
metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided normative. The metric and mrt_node_id values for ISIS-PCR in this
here is normative. The metric and mrt_node_id values for ISIS-PCR table should be considered informational. The normative values are
should be considered informational. specified in [IEEE8021Qca] .
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id | metric of | | IGP/flooding | mrt_node_id | metric of |
| protocol | of neighbor | interface | | protocol | of neighbor | interface |
| and | on interface | | | and | on interface | |
| application | | | | application | | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field |
| IP/LDP FRR | Router ID in | for corresponding | | IP/LDP FRR | Router ID in | for corresponding |
| | Link ID field for | point-to-point link | | | Link ID field for | point-to-point link |
skipping to change at page 22, line 13 skipping to change at page 21, line 13
flooding protocols and applications flooding protocols and applications
The metrics are unsigned integers and MUST be compared as unsigned The metrics are unsigned integers and MUST be compared as unsigned
integers. The results of mrt_node_id comparisons MUST be the same as 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 would be obtained by converting the mrt_node_ids to unsigned integers
using network byte order and performing the comparison as unsigned using network byte order and performing the comparison as unsigned
integers. In the case of IS-IS for IP/LDP FRR with point-to-point integers. In the case of IS-IS for IP/LDP FRR with point-to-point
links, the pseudonode number (the 7th octet) is zero. Broadcast links, the pseudonode number (the 7th octet) is zero. Broadcast
interfaces will be discussed in Section 7. interfaces will be discussed in Section 7.
In the case of IS-IS for IP/LDP FRR, this specification allows for
the use of Multi-Topology routing. [RFC5120] requires that
information related to the standard/default topology (MT-ID = 0) be
carried in the Extended IS Reachability TLV #22, while it requires
that the Multi-Topology IS Neighbor TLV #222 only be used to carry
topology information related to non-default topologies (with non-zero
MT-IDs). [RFC5120] enforces this by requiring an implementation to
ignore TLV#222 with MT-ID = 0. The current document also requires
that TLV#222 with MT-ID = 0 MUST be ignored.
5.2. MRT Island Identification 5.2. MRT Island Identification
The local MRT Island for a particular MRT profile can be determined The local MRT Island for a particular MRT profile can be determined
by starting from the computing router in the network graph and doing by starting from the computing router in the network graph and doing
a breadth-first-search (BFS). The BFS explores only links that are a breadth-first-search (BFS). The BFS explores only links that are
in the same area/level, are not IGP-excluded, and are not MRT- in the same area/level, are not IGP-excluded, and are not MRT-
ineligible. The BFS explores only nodes that are are not IGP- ineligible. The BFS explores only nodes that are are not IGP-
excluded, and that support the particular MRT profile. See section 7 excluded, and that support the particular MRT profile. See section 7
of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions
of these criteria. of these criteria.
skipping to change at page 23, line 8 skipping to change at page 21, line 47
intf.remote_node.IN_MRT_ISLAND = TRUE intf.remote_node.IN_MRT_ISLAND = TRUE
if (not intf.remote_node.IN_MRT_ISLAND)) if (not intf.remote_node.IN_MRT_ISLAND))
intf.remote_node.IN_MRT_ISLAND = TRUE intf.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, intf.remote_node) add_to_tail(explore_list, intf.remote_node)
Figure 16: MRT Island Identification Figure 16: MRT Island Identification
5.3. GADAG Root Selection 5.3. GADAG Root Selection
In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG
Root Selection Policy is described for the MRT default profile. In Root Selection Policy is described for the MRT default profile. This
[I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for selection policy allows routers to consistently select a common GADAG
routers to advertise the GADAG Root Selection Priority and Root inside the local MRT Island, based on advertised priority
consistently select a GADAG Root inside the local MRT Island. The values. The MRT Lowpoint algorithm simply requires that all routers
MRT Lowpoint algorithm simply requires that all routers in the MRT in the MRT Island MUST select the same GADAG Root; the mechanism can
Island MUST select the same GADAG Root; the mechanism can vary based vary based upon the MRT profile description. Before beginning
upon the MRT profile description. Before beginning computation, the computation, the network graph is reduced to contain only the set of
network graph is reduced to contain only the set of routers that routers that support the specific MRT profile whose MRTs are being
support the specific MRT profile whose MRTs are being computed. computed.
As noted in Section 7, pseudonodes MUST NOT be considered for GADAG As noted in Section 7, pseudonodes MUST NOT be considered for GADAG
root selection. root selection.
Analysis has shown that the centrality of a router can have a It is expected that an operator will designate a set of routers as
significant impact on the lengths of the alternate paths computed. good choices for selection as GADAG root by setting the GADAG Root
Therefore, it is RECOMMENDED that off-line analysis that considers Selection Priority for that set of routers to lower (more preferred)
the centrality of a router be used to help determine how good a numerical values. For guidance on setting the GADAG Root Selection
choice a particular router is for the role of GADAG root. Priority values, refer to Section 10.1.
5.4. Initialization 5.4. Initialization
Before running the algorithm, there is the standard type of Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFS-values, initialization to be done, such as clearing any computed DFS-values,
lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed
next-hops, and flags associated with algorithm. next-hops, and flags associated with algorithm.
It is assumed that a regular SPF computation has been run so that the It is assumed that a regular SPF computation has been run so that the
primary next-hops from the computing router to each destination are primary next-hops from the computing router to each destination are
known. This is required for determining alternates at the last step. known. This is required for determining alternates at the last step.
Initially, all interfaces MUST be initialized to UNDIRECTED. Whether Initially, all interfaces MUST be initialized to UNDIRECTED. Whether
they are OUTGOING, INCOMING or both is determined when the GADAG is they are OUTGOING, INCOMING or both is determined when the GADAG is
constructed and augmented. constructed and augmented.
It is possible that some links and nodes will be marked as unusable It is possible that some links and nodes will be marked using
using standard IGP mechanisms (see section 7 of standard IGP mechanisms to discourage or prevent transit traffic.
[I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability Section 7.3.1 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes how
considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be those links and nodes are excluded from MRT Island formation.
desirable to administratively configure some interfaces as ineligible
to carry MRT FRR traffic. This constraint MUST be consistently MRT-FRR also has the ability to advertise links MRT-Ineligible, as
flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the described in Section 7.3.2 of [I-D.ietf-rtgwg-mrt-frr-architecture].
owner of the interface, so that links are known to be MRT-ineligible These links are excluded from the MRT Island and the GADAG.
and not explored or used in the MRT algorithm. When a either Computation of MRT next-hops will therefore not use any MRT-
interface on a link is advertised as MRT-ineligible, the link MUST
NOT be included in the MRT Island, and will thus be excluded from the
GADAG. Computation of MRT next-hops will therefore not use any MRT-
ineligible links. The MRT algorithm does still need to consider MRT- ineligible links. The MRT algorithm does still need to consider MRT-
ineligible links when computing FRR alternates, because an MRT- ineligible links when computing FRR alternates, because an MRT-
ineligible link can still be the shortest-path next-hop to reach a ineligible link can still be the shortest-path next-hop to reach a
destination. destination.
When a broadcast interface is advertised as MRT-ineligible, then the When a broadcast interface is advertised as MRT-ineligible, then the
pseudo-node representing the entire broadcast network MUST NOT be pseudo-node representing the entire broadcast network MUST NOT be
included in the MRT Island. This is equivalent to excluding all of included in the MRT Island. This is equivalent to excluding all of
the broadcast interfaces on that broadcast network from the MRT the broadcast interfaces on that broadcast network from the MRT
Island. 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 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 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 methods are used to find ears in the algorithm. The first is by
going to a not IN_GADAG DFS-child and then following the chain of going to a not IN_GADAG DFS-child and then following the chain of
low-point parents until an IN_GADAG node is found. The second is by low-point 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 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 parents until an IN_GADAG node is found. As an ear is found, the
associated interfaces are marked based on the direction taken. 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 nodes in the ear are marked as IN_GADAG. In the algorithm, first the
skipping to change at page 26, line 35 skipping to change at page 25, line 22
if ((intf.remote_node.IN_GADAG == false) and if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is not x)) (intf.remote_node.dfs_parent is not x))
Construct_Ear(x, Stack, intf, NEIGHBOR) Construct_Ear(x, Stack, intf, NEIGHBOR)
Construct_GADAG_via_Lowpoint(topology, gadag_root) Construct_GADAG_via_Lowpoint(topology, gadag_root)
Figure 17: Low-point Inheritance GADAG algorithm Figure 17: Low-point Inheritance GADAG algorithm
5.6. Augmenting the GADAG by directing all links 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 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 all links in the network graph. That has two impacts. First, there
might be shorter paths that respect the GADAG partial ordering and so might be shorter paths that respect the GADAG partial ordering and so
the alternate paths would not be as short as possible. Second, there 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 may be additional paths between a router x and the root that are not
included in the GADAG. Including those provides potentially more included in the GADAG. Including those provides potentially more
bandwidth to traffic flowing on the alternates and may reduce bandwidth to traffic flowing on the alternates and may reduce
congestion compared to just using the GADAG as currently constructed. congestion compared to just using the GADAG as currently constructed.
The goal is thus to assign direction to every remaining link marked The goal is thus to assign direction to every remaining link marked
skipping to change at page 64, line 16 skipping to change at page 63, line 16
alternates. For example, when the PLR observes that connectivity to alternates. For example, when the PLR observes that connectivity to
an IP-layer node on a broadcast network has failed, the PLR may an IP-layer node on a broadcast network has failed, the PLR may
choose to still use the broadcast network to reach other IP-layer choose to still use the broadcast network to reach other IP-layer
nodes which are still reachable. Or if the PLR observes that nodes which are still reachable. Or if the PLR observes that
connectivity has failed to several IP-layer nodes on the same connectivity has failed to several IP-layer nodes on the same
broadcast network, it may choose to treat the entire broadcast broadcast network, it may choose to treat the entire broadcast
network as failed. The choice of MRT alternates by a PLR for a network as failed. The choice of MRT alternates by a PLR for a
particular set of failure conditions is a local decision, since it particular set of failure conditions is a local decision, since it
does not require coordination with other nodes. 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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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 [I-D.ietf-rtgwg-mrt-frr-architecture] 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 MRT-FRR in
general, see the Operational Considerations section of
[I-D.ietf-rtgwg-mrt-frr-architecture].
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 off-line 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. Destination-rooted 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 MRT-Red and MRT-
Blue next-hops 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 destination-rooted 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 pseudo-code.
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
[I-D.ietf-rtgwg-mrt-frr-architecture].
14. References
14.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., and R. White, "An Architecture for IP/
LDP Fast-Reroute Using Maximally Redundant Trees", draft-
ietf-rtgwg-mrt-frr-architecture-07 (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,
<http://www.rfc-editor.org/info/rfc2119>.
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, <http://www.omikk.bme.hu/collection
s/phd/Villamosmernoki_es_Informatikai_Kar/2011/
Enyedi_Gabor/ertekezes.pdf>.
[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,
<http://www.ieee802.org/1/pages/802.1ca.html>.
[ISO10589-Second-Edition]
International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode 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,
<http://dl.acm.org/citation.cfm?doid=368996.369025>.
[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,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120,
DOI 10.17487/RFC5120, February 2008,
<http://www.rfc-editor.org/info/rfc5120>.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>.
Appendix A. Python Implementation of MRT Lowpoint Algorithm
Below is Python code implementing the 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 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 .txt version of the draft, one can cut and paste the Python code from
the .xml version. The code is also posted on Github. the .xml version. The code is also posted on Github.
While this Python code is believed to correctly implement the pseudo- While this Python code is believed to correctly implement the pseudo-
code description of the algorithm, in the event of a difference, the code description of the algorithm, in the event of a difference, the
pseudo-code description should be considered normative. pseudo-code description should be considered normative.
skipping to change at page 104, line 44 skipping to change at page 108, line 20
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_MRT_for_All_Sources(topo) Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base) Write_Output_To_Files(topo, res_file_base)
Generate_Basic_Topology_and_Run_MRT() Generate_Basic_Topology_and_Run_MRT()
Generate_Complex_Topology_and_Run_MRT() Generate_Complex_Topology_and_Run_MRT()
<CODE ENDS> <CODE ENDS>
9. Algorithm Alternatives and Evaluation Appendix B. Constructing a GADAG using SPFs
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 Destination-Rooted 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 live-live 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
fast-reroute 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 source-destination
pairs, as seen in the column labeled NP_LLFA. The use of RLFA in
addition to LLFA is generally able to increase the node-protecting
coverage. The percentage of node-protecting coverage with RLFA is
provided in the column labeled NP_RLFA, ranges from 59% to 98% for
these topologies. The node-protecting 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 source-destination 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 metric-based 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 metric-based 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 metric-based path lengths is obvious.
However, we have observed that the metric-based 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
hopcount-based alternate path lengths for topology T208 are fairly
well-behaved.
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
node-protecting LLFA. The third row (labeled NP_LLFA_THEN_NP_RLFA)
is the hopcount distribution when one adds node-protecting RLFA to
increase the coverage. The alternate selection policy used here
first tries to find a node-protecting LLFA. If that does not exist,
then it tries to find an RLFA, and checks if it is node-protecting.
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 node-protecting LLFA. If
a node-protecting 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 node-protecting LLFA exists.
One can see from the data that combining node-protecting 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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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 P-space. The first node
to satisfy this condition was selected as the RLFA. More
sophisticated methods to select node-protecting 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 off-line.
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|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <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 [I-D.ietf-rtgwg-mrt-frr-architecture] 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 pseudo-code.
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
[I-D.ietf-rtgwg-mrt-frr-architecture].
14. References
14.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., and R. White, "An Architecture for IP/
LDP Fast-Reroute Using Maximally Redundant Trees", draft-
ietf-rtgwg-mrt-frr-architecture-07 (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,
<http://www.rfc-editor.org/info/rfc2119>.
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, <http://www.omikk.bme.hu/collection
s/phd/Villamosmernoki_es_Informatikai_Kar/2011/
Enyedi_Gabor/ertekezes.pdf>.
[I-D.ietf-isis-mrt]
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)",
draft-ietf-isis-mrt-01 (work in progress), October 2015.
[I-D.ietf-isis-pcr]
Farkas, J., Bragg, N., Unbehagen, P., Parsons, G.,
Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation
and Reservation", draft-ietf-isis-pcr-04 (work in
progress), December 2015.
[I-D.ietf-ospf-mrt]
Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
"OSPF Extensions to Support Maximally Redundant Trees",
draft-ietf-ospf-mrt-01 (work in progress), October 2015.
[I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-11 (work in progress), June 2015.
[ISO10589-Second-Edition]
International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode 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,
<http://dl.acm.org/citation.cfm?doid=368996.369025>.
[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,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120,
DOI 10.17487/RFC5120, February 2008,
<http://www.rfc-editor.org/info/rfc5120>.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>.
Appendix A. Option 2: Computing GADAG using SPFs
The basic idea in this option is to use slightly-modified SPF The basic idea in this method for constructing a GADAG is to use
computations to find ears. In every block, an SPF computation is slightly-modified SPF computations to find ears. In every block, an
first done to find a cycle from the local root and then SPF SPF computation is first done to find a cycle from the local root and
computations in that block find ears until there are no more then SPF computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops is the path of interfaces indicated by following the previous hops
from the mininized IN_GADAG node back to the SPF root. from the mininized IN_GADAG node back to the SPF root.
To do this, first all cut-vertices must be identified and local-roots To do this, first all cut-vertices must be identified and local-roots
assigned as specified in Figure 12. assigned as specified in Figure 12.
The slight modifications to the SPF are as follows. The root of the The slight modifications to the SPF are as follows. The root of the
block is referred to as the block-root; it is either the GADAG root block is referred to as the block-root; it is either the GADAG root
or a cut-vertex. or a cut-vertex.
skipping to change at page 119, line 4 skipping to change at page 109, line 45
and cand_intf.local_node as TEMP_UNUSABLE and cand_intf.local_node as TEMP_UNUSABLE
if cand_intf.local_node is not block_root if cand_intf.local_node is not block_root
Mark cand_intf.local_node as TEMP_UNUSABLE Mark cand_intf.local_node as TEMP_UNUSABLE
Initialize ear_list to empty Initialize ear_list to empty
end_ear = Mod_SPF(spf_root, block_root) end_ear = Mod_SPF(spf_root, block_root)
y = end_ear.spf_prev_hop y = end_ear.spf_prev_hop
while y.local_node is not spf_root while y.local_node is not spf_root
add_to_list_start(ear_list, y) add_to_list_start(ear_list, y)
y.local_node.IN_GADAG = true y.local_node.IN_GADAG = true
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
if(method is not hybrid) if(method is not hybrid)
Set_Ear_Direction(ear_list, cand_intf.local_node, Set_Ear_Direction(ear_list, cand_intf.local_node,
end_ear,block_root) end_ear,block_root)
Clear TEMP_UNUSABLE from all interfaces between Clear TEMP_UNUSABLE from all interfaces between
cand_intf.remote_node and cand_intf.local_node cand_intf.remote_node and cand_intf.local_node
Clear TEMP_UNUSABLE from cand_intf.local_node Clear TEMP_UNUSABLE from cand_intf.local_node
return end_ear 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 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 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 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<- 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 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 all ears that started at a node before looking at ears starting at
nodes higher in the partial order. In this algorithm, using that nodes higher in the partial order. In this GADAG construction
approach could mean that new ears aren't added in order of their method, using that approach could mean that new ears aren't added in
total cost since all ears connected to a node would need to be found order of their total cost since all ears connected to a node would
before additional nodes could be found. need to be found before additional nodes could be found.
The alternative is to track the order relationship of each node with The alternative is to track the order relationship of each node with
respect to every other node. This can be accomplished by maintaining respect to every other node. This can be accomplished by maintaining
two sets of nodes at each node. The first set, Higher_Nodes, 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 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 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) Set_Ear_Direction(ear_list, end_a, end_b, block_root)
// Default of A_TO_B for the following cases: // Default of A_TO_B for the following cases:
// (a) end_a and end_b are the same (root) // (a) end_a and end_b are the same (root)
// or (b) end_a is in end_b's Lower Nodes // or (b) end_a is in end_b's Lower Nodes
// or (c) end_a and end_b were unordered with respect to each // or (c) end_a and end_b were unordered with respect to each
// other // other
direction = A_TO_B direction = A_TO_B
if (end_b is block_root) and (end_a is not end_b) if (end_b is block_root) and (end_a is not end_b)
direction = B_TO_A direction = B_TO_A
else if end_a is in end_b.Higher_Nodes else if end_a is in end_b.Higher_Nodes
direction = B_TO_A direction = B_TO_A
if direction is B_TO_A if direction is B_TO_A
foreach interface i in ear_list foreach interface i in ear_list
skipping to change at page 120, line 48 skipping to change at page 111, line 48
add i.local_node to x.Higher_Nodes add i.local_node to x.Higher_Nodes
else else
foreach node x where x.localroot is block_root foreach node x where x.localroot is block_root
if end_b is in x.Lower_Nodes if end_b is in x.Lower_Nodes
foreach interface i in ear_list foreach interface i in ear_list
add i.local_node to x.Lower_Nodes add i.local_node to x.Lower_Nodes
if end_a is in x.Higher_Nodes if end_a is in x.Higher_Nodes
foreach interface i in ear_list foreach interface i in ear_list
add i.remote_node to x.Higher_Nodes 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 A goal of this GADAG construction method is to find the shortest
ear is started by going to a neighbor x of an IN_GADAG node y. The cycles and ears. An ear is started by going to a neighbor x of an
path from x to an IN_GADAG node is minimal, since it is computed via IN_GADAG node y. The path from x to an IN_GADAG node is minimal,
SPF. Since a shortest path is made of shortest paths, to find the since it is computed via SPF. Since a shortest path is made of
shortest ears requires reaching from the set of IN_GADAG nodes to the shortest paths, to find the shortest ears requires reaching from the
closest node that isn't IN_GADAG. Therefore, an ordered tree is set of IN_GADAG nodes to the closest node that isn't IN_GADAG.
maintained of interfaces that could be explored from the IN_GADAG Therefore, an ordered tree is maintained of interfaces that could be
nodes. The interfaces are ordered by their characteristics of explored from the IN_GADAG nodes. The interfaces are ordered by
metric, local loopback address, remote loopback address, and ifindex, their characteristics of metric, local loopback address, remote
as in the algorithm previously described in Figure 14. loopback address, and ifindex, based on the Interface_Compare
function defined in Figure 14.
The algorithm ignores interfaces picked from the ordered tree that This GADAG construction method ignores interfaces picked from the
belong to the block root if the block in which the interface is ordered list that belong to the block root if the block in which the
present already has an ear that has been computed. This is necessary interface is present already has an ear that has been computed. This
since we allow at most one incoming interface to a block root in each is necessary since we allow at most one incoming interface to a block
block. This requirement stems from the way next-hops are computed as root in each block. This requirement stems from the way next-hops
was seen in Section 5.7. After any ear gets computed, we traverse are computed as was seen in Section 5.7. After any ear gets
the newly added nodes to the GADAG and insert interfaces whose far computed, we traverse the newly added nodes to the GADAG and insert
end is not yet on the GADAG to the ordered tree for later processing. interfaces whose far end is not yet on the GADAG to the ordered tree
for later processing.
Finally, cut-links are a special case because there is no point in Finally, cut-links are a special case because there is no point in
doing an SPF on a block of 2 nodes. The algorithm identifies cut- doing an SPF on a block of 2 nodes. The algorithm identifies cut-
links simply as links where both ends of the link are cut-vertices. links simply as links where both ends of the link are cut-vertices.
Cut-links can simply be added to the GADAG with both OUTGOING and Cut-links can simply be added to the GADAG with both OUTGOING and
INCOMING specified on their interfaces. INCOMING specified on their interfaces.
add_eligible_interfaces_of_node(ordered_intfs_tree,node) add_eligible_interfaces_of_node(ordered_intfs_tree,node)
for each interface of node for each interface of node
if intf.remote_node.IN_GADAG is false if intf.remote_node.IN_GADAG is false
skipping to change at page 122, line 30 skipping to change at page 113, line 32
ear_end = SPF_for_Ear(cand_intf.local_node, ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.remote_node, cand_intf.remote_node,
cand_intf.remote_node.localroot, cand_intf.remote_node.localroot,
SPF method) SPF method)
y = ear_end.spf_prev_hop y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node( add_eligible_interfaces_of_node(
ordered_intfs_tree, y.local_node) ordered_intfs_tree, y.local_node)
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
Figure 39: SPF-based GADAG algorithm Figure 33: SPF-based 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 lowpoint inheritance and SPF methods. To this end, we process nodes
as they get added to the GADAG just like in the lowpoint inheritance 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 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 maintain lower and higher sets at each node to ascertain ear
directions since the ears will always be directed from the node being 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 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 resort to an SPF to have the possibility of better ears (path
lentghs) thus giving more flexibility than the restricted use of lentghs) thus giving more flexibility than the restricted use of
lowpoint/dfs parents. lowpoint/dfs parents.
skipping to change at page 123, line 12 skipping to change at page 114, line 14
of an ear is pre-determined. Thus, whenever the block already has an of an ear is pre-determined. Thus, whenever the block already has an
ear computed, and we are processing an interface of the block root, 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 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 the ear. This ensures that the SPF terminates at some node other
than the block-root. This in turn guarantees that the block-root has than the block-root. This in turn guarantees that the block-root has
only one incoming interface in each block, which is necessary for only one incoming interface in each block, which is necessary for
correctly computing the next-hops on the GADAG. correctly computing the next-hops on the GADAG.
As in the SPF gadag, bridge ears are handled as a special case. 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) find_spf_stack_ear(stack, x, y, xy_intf, block_root)
if L(y) == D(y) if L(y) == D(y)
// Special case for cut-links // Special case for cut-links
xy_intf.UNDIRECTED = false xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true xy_intf.OUTGOING = true
xy_intf.INCOMING = true xy_intf.INCOMING = true
xy_intf.remote_intf.OUTGOING = true xy_intf.remote_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true xy_intf.remote_intf.INCOMING = true
skipping to change at page 124, line 14 skipping to change at page 115, line 16
root.IN_GADAG = true root.IN_GADAG = true
Initialize Stack to empty Initialize Stack to empty
push root onto Stack push root onto Stack
while (Stack is not empty) while (Stack is not empty)
x = pop(Stack) x = pop(Stack)
for each interface intf of x for each interface intf of x
y = intf.remote_node y = intf.remote_node
if y.IN_GADAG is false if y.IN_GADAG is false
find_spf_stack_ear(stack, x, y, intf, y.block_root) find_spf_stack_ear(stack, x, y, intf, y.block_root)
Figure 40: Hybrid GADAG algorithm Figure 34: Hybrid GADAG construction method
Authors' Addresses Authors' Addresses
Gabor Sandor Enyedi Gabor Sandor Enyedi
Ericsson Ericsson
Konyves Kalman krt 11 Konyves Kalman krt 11
Budapest 1097 Budapest 1097
Hungary Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com Email: Gabor.Sandor.Enyedi@ericsson.com
 End of changes. 61 change blocks. 
807 lines changed or deleted 400 lines changed or added

This html diff was produced by rfcdiff 1.42. The latest version is available from http://tools.ietf.org/tools/rfcdiff/