draft-ietf-rtgwg-mrt-frr-algorithm-00.txt   draft-ietf-rtgwg-mrt-frr-algorithm-01.txt 
Routing Area Working Group G. Enyedi, Ed. Routing Area Working Group G. Enyedi, Ed.
Internet-Draft A. Csaszar Internet-Draft A. Csaszar
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: August 18, 2014 A. Atlas, Ed. Expires: January 5, 2015 A. Atlas, Ed.
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
February 14, 2014 July 4, 2014
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-
Reroute Reroute
draft-ietf-rtgwg-mrt-frr-algorithm-00 draft-ietf-rtgwg-mrt-frr-algorithm-01
Abstract Abstract
A complete solution for IP and LDP Fast-Reroute using Maximally A complete solution for IP and LDP Fast-Reroute using Maximally
Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr-
architecture]. This document defines the associated MRT Lowpoint architecture]. This document defines the associated MRT Lowpoint
algorithm that is used in the default MRT profile to compute both the algorithm that is used in the default MRT profile to compute both the
necessary Maximally Redundant Trees with their associated next-hops necessary Maximally Redundant Trees with their associated next-hops
and the alternates to select for MRT-FRR. and the alternates to select for MRT-FRR.
skipping to change at page 1, line 41 skipping to change at page 1, line 41
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 August 18, 2014. This Internet-Draft will expire on January 5, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2014 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
skipping to change at page 2, line 25 skipping to change at page 2, line 25
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 . . . . . . . . . . . . . . . . . . . 7
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 . . . . . . . . 9
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 . . . . . . . . . . . . . . . . . . . . 15
4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17
5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19
5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20 5.1. MRT Island Identification . . . . . . . . . . . . . . . . 20
5.2. Root Selection . . . . . . . . . . . . . . . . . . . . . 21 5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 inheritance . . . . . . . . . . . . . . . . . . . . . . . 22
5.5. Augmenting the GADAG by directing all links . . . . . . . 24 5.5. Augmenting the GADAG by directing all links . . . . . . . 24
5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26 5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26
5.6.1. MRT next-hops to all nodes partially ordered with 5.6.1. MRT next-hops to all nodes partially ordered with
respect to the computing node . . . . . . . . . . . . 27 respect to the computing node . . . . . . . . . . . . 27
5.6.2. MRT next-hops to all nodes not partially ordered with 5.6.2. MRT next-hops to all nodes not partially ordered with
respect to the computing node . . . . . . . . . . . . 28 respect to the computing node . . . . . . . . . . . . 28
5.6.3. Computing Redundant Tree next-hops in a 2-connected 5.6.3. Computing Redundant Tree next-hops in a 2-connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 Graph . . . . . . . . . . . . . . . . . . . . . . . . 29
5.6.4. Generalizing for graph that isn't 2-connected . . . . 30 5.6.4. Generalizing for a graph that isn't 2-connected . . . 30
5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31 5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31
5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33
5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37
6. MRT Lowpoint Algorithm: Complete Specification . . . . . . . 40 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40
7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40
7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41
8. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51
9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51
10. Security Considerations . . . . . . . . . . . . . . . . . . . 51 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51
11.1. Normative References . . . . . . . . . . . . . . . . . . 51 12. Security Considerations . . . . . . . . . . . . . . . . . . . 51
11.2. Informative References . . . . . . . . . . . . . . . . . 51 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51
13.1. Normative References . . . . . . . . . . . . . . . . . . 51
13.2. Informative References . . . . . . . . . . . . . . . . . 51
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53
Appendix B. Option 3: Computing GADAG using a hybrid method . . 58 Appendix B. Option 3: Computing GADAG using a hybrid method . . 58
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60
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
skipping to change at page 3, line 39 skipping to change at page 3, line 42
received traffic on the MRT-Blue and primary next-hops for the MRT- received traffic on the MRT-Blue and primary next-hops for the MRT-
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 prefered when available and that policy- downstream paths, may be prefered when available and that policy-
based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] based alternate selection process[I-D.ietf-rtgwg-lfa-manageability]
is not captured in this document. is not captured in this document.
[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 |
skipping to change at page 9, line 30 skipping to change at page 9, line 30
root - and the actual algorithm is given in Section 5.4. root - and the actual algorithm is given in Section 5.4.
In order to understand the basic idea of finding an ADAG, first In order to understand the basic idea of finding an ADAG, first
suppose that we have already a partial ADAG, which doesn't contain suppose that we have already a partial ADAG, which doesn't contain
all the nodes in the block yet, and we want to extend it to cover all all the nodes in the block yet, and we want to extend it to cover all
the nodes. Suppose that we find a path from a node X to Y such that the nodes. Suppose that we find a path from a node X to Y such that
X and Y are already contained by our partial ADAG, but all the X and Y are already contained by our partial ADAG, but all the
remaining nodes along the path are not added to the ADAG yet. We remaining nodes along the path are not added to the ADAG yet. We
refer to such a path as an ear. refer to such a path as an ear.
Recall that our ADAG is closely related to a partial order, more Recall that our ADAG is closely related to a partial order. More
precisely, if we remove root R, the remaining DAG describes a partial precisely, if we remove root R, the remaining DAG describes a partial
order of the nodes. If we suppose that neither X nor Y is the root, order of the nodes. If we suppose that neither X nor Y is the root,
we may be able to compare them. If one of them is definitely lesser we may be able to compare them. If one of them is definitely lesser
with respect to our partial order (say X<<Y), we can add the new path with respect to our partial order (say X<<Y), we can add the new path
to the ADAG in a direction from X to Y. As an example consider to the ADAG in a direction from X to Y. As an example consider
Figure 5. Figure 5.
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 | | | | | V | | V | |
A---B---| A-->B---| A-->B---| A---B---| A-->B---| A-->B---|
(a) (b) (c) (a) (b) (c)
(a) A 2-connected graph (a) A 2-connected graph
(b) Partial ADAG (C is not included) (b) Partial ADAG (C is not included)
(c) Resulting ADAG after adding path (or ear) B-C-D (c) Resulting ADAG after adding path (or ear) B-C-D
Figure 5 Figure 5
In this partial ADAG, node C is not yet included. However, we can In this partial ADAG, node C is not yet included. However, we can
find path B-C-D, where both endpoints are contained by this partial find path B-C-D, where both endpoints are contained by this partial
ADAG (we say those nodes are *ready* in the sequel), and the ADAG (we say those nodes are "ready" in the following text), and the
remaining node (node C) is not contained yet. If we remove R, the remaining node (node C) is not contained yet. If we remove R, the
remaining DAG defines a partial order, and with respect to this remaining DAG defines a partial order, and with respect to this
partial order we can say that B<<D, so we can add the path to the partial order we can say that B<<D, so we can add the path to the
ADAG in the direction from B to D (arcs B->C and C->D are added). If ADAG in the direction from B to D (arcs B->C and C->D are added). If
B >> D, we would add the same path in reverse direction. B >> D, we would add the same path in reverse direction.
If in the partial order where an ear's two ends are X and Y, X << Y, If in the partial order where an ear's two ends are X and Y, X << Y,
then there must already be a directed path from X to Y in the ADAG. then there must already be a directed path from X to Y in the ADAG.
The ear must be added in a direction such that it doesn't create a The ear must be added in a direction such that it doesn't create a
cycle; therefore the ear must go from X to Y. cycle; therefore the ear must go from X to Y.
In the case, when X and Y are not ordered with each other, we can In the case, when X and Y are not ordered with each other, we can
select either direction for the ear. We have no restriction since select either direction for the ear. We have no restriction since
neither of the directions can result in a cycle. In the corner case neither of the directions can result in a cycle. In the corner case
when one of the endpoints of an ear, say X, is the root (recall that when one of the endpoints of an ear, say X, is the root (recall that
the two endpoints must be different), we could use both directions the two endpoints must be different), we could use both directions
again for the ear because the root can be considered both as smaller again for the ear because the root can be considered both as smaller
and as greater than Y. However, we strictly pick that direction in and as greater than Y. However, we strictly pick that direction in
which the root is lower than Y. The logic for this decision is which the root is lower than Y. The logic for this decision is
explained in Section 5.6 explained in Section 5.6
A partial ADAG is started by finding a cycle from the root R back to A partial ADAG is started by finding a cycle from the root R back to
itself. This can be done by selecting a non-ready neighbor N of R itself. This can be done by selecting a non-ready neighbor N of R
and then finding a path from N to R that doesn't use any links and then finding a path from N to R that doesn't use any links
between R and N. The direction of the cycle can be assigned either between R and N. The direction of the cycle can be assigned either
way since it is starting the ordering. way since it is starting the ordering.
Once a partial ADAG is already present, it will always have a node Once a partial ADAG is already present, it will always have a node
that is not the root R in it. As a brief proof that a partial ADAG that is not the root R in it. As a brief proof that a partial ADAG
can always have ears added to it: just select a non-ready neighbor N can always have ears added to it: just select a non-ready neighbor N
of a ready node Q, such that Q is not the root R, find a path from N of a ready node Q, such that Q is not the root R, find a path from N
to the root R in the graph with Q removed. This path is an ear where to the root R in the graph with Q removed. This path is an ear where
the first node of the ear is Q, the next is N, then the path until the first node of the ear is Q, the next is N, then the path until
the first ready node the path reached (that second ready node is the the first ready node the path reached (that ready node is the other
other endpoint of the path). Since the graph is 2-connected, there endpoint of the path). Since the graph is 2-connected, there must be
must be a path from N to R without Q. a path from N to R without Q.
It is always possible to select a non-ready neighbor N of a ready It is always possible to select a non-ready neighbor N of a ready
node Q so that Q is not the root R. Because the network is node Q so that Q is not the root R. Because the network is
2-connected, N must be connected to two different nodes and only one 2-connected, N must be connected to two different nodes and only one
can be R. Because the initial cycle has already been added to the can be R. Because the initial cycle has already been added to the
ADAG, there are ready nodes that are not R. Since the graph is ADAG, there are ready nodes that are not R. Since the graph is
2-connected, while there are non-ready nodes, there must be a non- 2-connected, while there are non-ready nodes, there must be a non-
ready neighbor N of a ready node that is not R. ready neighbor N of a ready node that is not R.
Generic_Find_Ears_ADAG(root) Generic_Find_Ears_ADAG(root)
Create an empty ADAG. Add root to the ADAG. Create an empty ADAG. Add root to the ADAG.
Mark root as IN_GADAG. Mark root as IN_GADAG.
Select an arbitrary cycle containing root. Select an arbitrary cycle containing root.
Add the arbitrary cycle to the ADAG. Add the arbitrary cycle to the ADAG.
Mark cycle's nodes as IN_GADAG. Mark cycle's nodes as IN_GADAG.
Add cycle's non-root nodes to process_list. Add cycle's non-root nodes to process_list.
skipping to change at page 11, line 34 skipping to change at page 11, line 34
we will get an ADAG. The method used for finding and selecting the we will get an ADAG. The method used for finding and selecting the
ears is important; shorter ears result in shorter paths along the ears is important; shorter ears result in shorter paths along the
MRTs. The MRT Lowpoint algorithm's method using Low-Point MRTs. The MRT Lowpoint algorithm's method using Low-Point
Inheritance is defined in Section 5.4. Other methods are described Inheritance is defined in Section 5.4. Other methods are described
in the Appendices (Appendix A and Appendix B). in the Appendices (Appendix A and Appendix B).
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 C and assume we reached it from ready node B. We search a path from
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 B->C this is node D, so the open ear is B-C-D. Since B<<D, we add arc
and C->D to the ADAG. Since all the nodes are ready, we stop at this B->C and C->D to the ADAG. Since all the nodes are ready, we stop at
point. this point.
4.3. Low-Point Values and Their Uses 4.3. Low-Point Values and Their Uses
A basic way of computing a spanning tree on a network graph is to run A basic way of computing a spanning tree on a network graph is to run
a depth-first-search, such as given in Figure 7. This tree has the a depth-first-search, such as given in Figure 7. This tree has the
important property that if there is a link (x, n), then either n is a important property that if there is a link (x, n), then either n is a
DFS ancestor of x or n is a DFS descendant of x. In other words, DFS ancestor of x or n is a DFS descendant of x. In other words,
either n is on the path from the root to x or x is on the path from either n is on the path from the root to x or x is on the path from
the root to n. the root to n.
skipping to change at page 12, line 23 skipping to change at page 12, line 23
DFS_Visit(w, x) DFS_Visit(w, x)
Run_DFS(node root) Run_DFS(node root)
dfs_number = 0 dfs_number = 0
DFS_Visit(root, NONE) DFS_Visit(root, NONE)
Figure 7: Basic Depth-First Search algorithm Figure 7: Basic Depth-First Search algorithm
Given a node x, one can compute the minimal DFS number of the Given a node x, one can compute the minimal DFS number of the
neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the
highest attachment point neighbouring x. What is interesting, earliest attachment point neighbouring x. What is interesting,
though, is what is the highest attachment point from x and x's though, is what is the earliest attachment point from x and x's
descendants. This is what is determined by computing the Low-Point descendants. This is what is determined by computing the Low-Point
value, as given in Algorithm Figure 9 and illustrated on a graph in value.
Figure 8.
In order to compute the low point value, the network is traversed
using DFS and the vertices are numbered based on the DFS walk. Let
this number be represented as DFS(x). All the edges that lead to
already visited nodes during DFS walk are back-edges. The back-edges
are important because they give information about reachability of a
node via another path.
The low point number is calculated by finding:
Low(x) = Minimum of ( (DFS(x),
Lowest DFS(n, x->n is a back-edge),
Lowest Low(n, x->n is tree edge in DFS walk) ).
A detailed algorithm for computing the low-point value is given in
Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to
a example graph.
global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number
L(x) = D(x)
dfs_number += 1
x.dfs_parent = parent
x.dfs_parent_intf = p_to_x
x.lowpoint_parent = NONE
for each interface intf of x
if D(intf.remote_node) is not set
Lowpoint_Visit(intf.remote_node, x, intf)
if L(intf.remote_node) < L(x)
L(x) = L(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else if intf.remote_node is not parent
if D(intf.remote_node) < L(x)
L(x) = D(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
Run_Lowpoint(node root)
dfs_number = 0
Lowpoint_Visit(root, NONE, NONE)
Figure 8: Computing Low-Point value
[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 non-2-connected graph (a) a non-2-connected graph
skipping to change at page 13, line 41 skipping to change at page 14, line 41
| | | | | | | | | | | |
[R] [D]---[C]---[F] [H]----[K] [N] [R] [D]---[C]---[F] [H]----[K] [N]
(0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) (0, ) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]---------[B] [G]----| [L]------[M] [A]---------[B] [G]----| [L]------[M]
(1,0) (2,0) (7,3) (12,11) (13,11) (1,0) (2,0) (7,3) (12,11) (13,11)
(c) with low-point values assigned (D(x), L(x)) (c) with low-point values assigned (D(x), L(x))
Figure 8 Figure 9: Example lowpoint value computation
global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number
L(x) = D(x)
dfs_number += 1
x.dfs_parent = parent
x.dfs_parent_intf = p_to_x
x.lowpoint_parent = NONE
for each interface intf of x:
if D(intf.remote_node) is not set
Lowpoint_Visit(intf.remote_node, x, intf)
if L(intf.remote_node) < L(x)
L(x) = L(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else if intf.remote_node is not parent
if D(intf.remote_node) < L(x)
L(x) = D(intf.remote)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
Run_Lowpoint(node root)
dfs_number = 0
Lowpoint_Visit(root, NONE, NONE)
Figure 9: Computing Low-Point value
From the low-point value and lowpoint parent, there are three very From the low-point value and lowpoint parent, there are three very
useful things which motivate our computation. useful things which motivate our computation.
First, if there is a child c of x such that L(c) >= D(x), then there First, if there is a child c of x such that L(c) >= D(x), then there
are no paths in the network graph that go from c or its descendants are no paths in the network graph that go from c or its descendants
to an ancestor of x - and therefore x is a cut-vertex. In Figure 8, to an ancestor of x - and therefore x is a cut-vertex. In Figure 9,
this can be seen by looking at the DFS children of C. C has two this can be seen by looking at the DFS children of C. C has two
children - D and F and L(F) = 3 = D(C) so it is clear that C is a children - D and F and L(F) = 3 = D(C) so it is clear that C is a
cut-vertex and F is in a block where C is the block's root. L(D) = 0 cut-vertex and F is in a block where C is the block's root. L(D) = 0
> 3 = D(C) so D has a path to the ancestors of C; in this case, D can > 3 = D(C) so D has a path to the ancestors of C; in this case, D can
go via E to reach R. Comparing the low-point values of all a node's go via E to reach R. Comparing the low-point values of all a node's
DFS-children with the node's DFS-value is very useful because it DFS-children with the node's DFS-value is very useful because it
allows identification of the cut-vertices and thus the blocks. allows identification of the cut-vertices and thus the blocks.
Second, by repeatedly following the path given by lowpoint_parent, Second, by repeatedly following the path given by lowpoint_parent,
there is a path from x back to an ancestor of x that does not use the there is a path from x back to an ancestor of x that does not use the
link [x, x.dfs_parent] in either direction. The full path need not link [x, x.dfs_parent] in either direction. The full path need not
be taken, but this gives a way of finding an initial cycle and then be taken, but this gives a way of finding an initial cycle and then
ears. ears.
Third, as seen in Figure 8, even if L(x) < D(x), there may be a block Third, as seen in Figure 9, even if L(x) < D(x), there may be a block
that contains both the root and a 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 an MRT algorithm is that any non-2-connected graph is
made up by blocks (e.g. 2-connected clusters, cut-links, and/or made up by blocks (e.g. 2-connected clusters, cut-links, and/or
skipping to change at page 19, line 21 skipping to change at page 19, line 21
algorithm are described below. These work on a network graph after algorithm are described below. These work on a network graph after
its interfaces have been ordered as per Figure 14. its interfaces have been ordered as per Figure 14.
1. Compute the local MRT Island for the particular MRT Profile. 1. Compute the local MRT Island for the particular MRT Profile.
[See Section 5.1.] [See Section 5.1.]
2. Select the root to use for the GADAG. [See Section 5.2.] 2. Select the root to use for the GADAG. [See Section 5.2.]
3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] 3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.]
4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See 4. Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See
Figure 9.] Figure 8.]
5. Construct the GADAG. [See Section 5.4] 5. Construct the GADAG. [See Section 5.4]
6. Assign directions to all interfaces that are still UNDIRECTED. 6. Assign directions to all interfaces that are still UNDIRECTED.
[See Section 5.5.] [See Section 5.5.]
7. From the computing router x, compute the next-hops for the MRT- 7. From the computing router x, compute the next-hops for the MRT-
Blue and MRT-Red. [See Section 5.6.] Blue and MRT-Red. [See Section 5.6.]
8. Identify alternates for each next-hop to each destination by 8. Identify alternates for each next-hop to each destination by
skipping to change at page 20, line 30 skipping to change at page 20, line 30
return A_LESS_THAN_B return A_LESS_THAN_B
return B_LESS_THAN_A return B_LESS_THAN_A
Figure 14: Rules for ranking multiple interfaces. Order is from low Figure 14: Rules for ranking multiple interfaces. Order is from low
to high. to high.
5.1. MRT Island Identification 5.1. 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), exploring only links that aren't MRT- a breadth-first-search (BFS). The BFS explores only links that are
ineligible. in the same area/level, are not IGP-excluded, and are not MRT-
ineligible. The BFS explores only nodes that are are not IGP-
excluded, and that support the particular MRT profile. See section 7
of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions
of these criteria.
MRT_Island_Identification(topology, computing_rtr, profile_id) MRT_Island_Identification(topology, computing_rtr, profile_id, area)
for all routers in topology for all routers in topology
rtr.IN_MRT_ISLAND = FALSE rtr.IN_MRT_ISLAND = FALSE
computing_rtr.IN_MRT_ISLAND = TRUE computing_rtr.IN_MRT_ISLAND = TRUE
explore_list = { computing_rtr } explore_list = { computing_rtr }
while (explore_list is not empty) while (explore_list is not empty)
next_rtr = remove_head(explore_list) next_rtr = remove_head(explore_list)
for each interface in next_rtr for each interface in next_rtr
if interface is not MRT-ineligible if interface is (not MRT-ineligible and not IGP-excluded
if ((interface.remote_node supports profile_id) and and in area)
(interface.remote_node.IN_MRT_ISLAND is FALSE)) if ((interface.remote_node supports profile_id) and
interface.remote_node.IN_MRT_ISLAND = TRUE (interface.remote_node.IN_MRT_ISLAND is FALSE))
add_to_tail(explore_list, interface.remote_node) interface.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, interface.remote_node)
Figure 15: MRT Island Identification Figure 15: MRT Island Identification
5.2. Root Selection 5.2. GADAG Root Selection
In Section 7 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG Root In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG
Selection is described for the MRT default profile. In Root Selection Policy is described for the MRT default profile. In
[I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for [I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for
routers to advertise the GADAG Root Selection Priority and routers to advertise the GADAG Root Selection Priority and
consistently select a GADAG Root inside the local MRT Island. The consistently select a GADAG Root inside the local MRT Island. The
MRT Lowpoint algorithm simply requires that all routers in the MRT MRT Lowpoint algorithm simply requires that all routers in the MRT
Island MUST select the same GADAG Root; the mechanism can vary based Island MUST select the same GADAG Root; the mechanism can vary based
upon the MRT profile description. Before beginning computation, the upon the MRT profile description. Before beginning computation, the
network graph is reduced to contain only the set of routers that network graph is reduced to contain only the set of routers that
support the specific MRT profile whose MRTs are being computed. support the specific MRT profile whose MRTs are being computed.
Analysis has shown that the centrality of a router can have a Analysis has shown that the centrality of a router can have a
skipping to change at page 21, line 39 skipping to change at page 21, line 39
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.
Due to manageability consideration It is possible that some links and nodes will be marked as unusable
[I-D.ietf-rtgwg-lfa-manageability], overload, or a transient cause using standard IGP mechanisms (see section 7 of
such as [RFC3137], it is possible that some links and nodes will be [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability
marked as unusable. This constraint must be consistently flooded via considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be
the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] so that links are desirable to administratively configure some interfaces as ineligible
clearly known to be MRT-ineligible and not explored or used in the to carry MRT FRR traffic. This constraint MUST be consistently
MRT algorithm. In the algorithm description, it is assumed that such flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the
links and nodes will not be explored or used and no more discussion owner of the interface, so that links are clearly known to be MRT-
is given of this restriction. ineligible and not explored or used in the MRT algorithm. In the
algorithm description, it is assumed that such links and nodes will
not be explored or used, and no more discussion is given of this
restriction.
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance
As discussed in Section 4.2, it is necessary to find ears from a node 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
skipping to change at page 22, line 49 skipping to change at page 22, line 49
If a node is a cut-vertex, that may not yet be the case. Therefore, If a node is a cut-vertex, that may not yet be the case. Therefore,
any nodes without a low-point parent will have their low-point parent any nodes without a low-point parent will have their low-point parent
set to their DFS parent and their low-point value set to the DFS- set to their DFS parent and their low-point value set to the DFS-
value of their parent. This assignment also properly allows an ear value of their parent. This assignment also properly allows an ear
between two cut-vertices. between two cut-vertices.
Finally, the algorithm simultaneously computes each node's local- Finally, the algorithm simultaneously computes each node's local-
root, as described in Figure 12. This is further elaborated as root, as described in Figure 12. This is further elaborated as
follows. The local-root can be inherited from the node at the end of follows. The local-root can be inherited from the node at the end of
the ear unless the end of the ear is x itself, in which case the the ear unless the end of the ear is x itself, in which case the
local-root for all the nodes in the ear would be x. This is because local-root for all the nodes in the ear would be x. This is because
whenever the first cycle is found in a block, or an ear involving a whenever the first cycle is found in a block, or an ear involving a
bridge is computed, the cut-vertex closest to the root would be x bridge is computed, the cut-vertex closest to the root would be x
itself. In all other scenarios, the properties of lowpoint/dfs itself. In all other scenarios, the properties of lowpoint/dfs
parents ensure that the end of the ear will be in the same block, and parents ensure that the end of the ear will be in the same block, and
thus inheriting its local-root would be the correct local-root for thus inheriting its local-root would be the correct local-root for
all newly added nodes. all newly added nodes.
The pseudo-code for the GADAG algorithm (assuming that the adjustment The pseudo-code for the GADAG algorithm (assuming that the adjustment
of lowpoint for cut-vertices has been made) is shown in Figure 16. of lowpoint for cut-vertices has been made) is shown in Figure 16.
skipping to change at page 24, line 47 skipping to change at page 24, line 47
topological sort[Kahn_1962_topo_sort] which essentially assigns a topological sort[Kahn_1962_topo_sort] which essentially assigns a
number to a node x only after all nodes before it (e.g. with a link number to a node x only after all nodes before it (e.g. with a link
incoming to x) have had their numbers assigned. The only issue with incoming to x) have had their numbers assigned. The only issue with
the topological sort is that it works on DAGs and not ADAGs or the topological sort is that it works on DAGs and not ADAGs or
GADAGs. GADAGs.
To convert a GADAG to a DAG, it is necessary to remove all links that To convert a GADAG to a DAG, it is necessary to remove all links that
point to a root of block from within that block. That provides the point to a root of block from within that block. That provides the
necessary conversion to a DAG and then a topological sort can be necessary conversion to a DAG and then a topological sort can be
done. Finally, all UNDIRECTED links are assigned a direction based done. Finally, all UNDIRECTED links are assigned a direction based
upon the partial ordering. Any UNDIRECTED links that connect to a upon the total ordering. Any UNDIRECTED links that connect to a root
root of a block from within that block are assigned a direction of a block from within that block are assigned a direction INCOMING
INCOMING to that root. The exact details of this whole process are to that root. The exact details of this whole process are captured
captured in Figure 17 in Figure 17
Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) Set_Block_Root_Incoming_Links(topo, root, mark_or_clear)
foreach node x in topo foreach node x in topo
if node x is a cut-vertex or root if node x is a cut-vertex or root
foreach interface i of x foreach interface i of x
if (i.remote_node.localroot is x) if (i.remote_node.localroot is x)
if i.UNDIRECTED if i.UNDIRECTED
i.OUTGOING = true i.OUTGOING = true
i.remote_intf.INCOMING = true i.remote_intf.INCOMING = true
i.UNDIRECTED = false i.UNDIRECTED = false
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
if i.INCOMING if i.INCOMING
if mark_or_clear is mark if mark_or_clear is MARK
if i.OUTGOING // a cut-link if i.OUTGOING // a cut-link
i.STORE_INCOMING = true i.STORE_INCOMING = true
i.INCOMING = false i.INCOMING = false
i.remote_intf.STORE_OUTGOING = true i.remote_intf.STORE_OUTGOING = true
i.remote_intf.OUTGOING = false i.remote_intf.OUTGOING = false
i.TEMP_UNUSABLE = true i.TEMP_UNUSABLE = true
i.remote_intf.TEMP_UNUSABLE = true i.remote_intf.TEMP_UNUSABLE = true
else else
i.TEMP_UNUSABLE = false i.TEMP_UNUSABLE = false
i.remote_intf.TEMP_UNUSABLE = false i.remote_intf.TEMP_UNUSABLE = false
if i.STORE_INCOMING and (mark_or_clear is clear) if i.STORE_INCOMING and (mark_or_clear is CLEAR)
i.INCOMING = true i.INCOMING = true
i.STORE_INCOMING = false i.STORE_INCOMING = false
i.remote_intf.OUTGOING = true i.remote_intf.OUTGOING = true
i.remote_intf.STORE_OUTGOING = false i.remote_intf.STORE_OUTGOING = false
Run_Topological_Sort_GADAG(topo, root) Run_Topological_Sort_GADAG(topo, root)
Set_Block_Root_Incoming_Links(topo, root, MARK) Set_Block_Root_Incoming_Links(topo, root, MARK)
foreach node x foreach node x
set x.unvisited to the count of x's incoming interfaces set x.unvisited to the count of x's incoming interfaces
that aren't marked TEMP_UNUSABLE that aren't marked TEMP_UNUSABLE
skipping to change at page 26, line 30 skipping to change at page 26, line 30
i.remote_intf.OUTGOING = true i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, root) Add_Undirected_Links(topo, root)
Figure 17: Assigning direction to UNDIRECTED links Figure 17: Assigning direction to UNDIRECTED links
Proxy-nodes do not need to be added to the network graph. They Proxy-nodes do not need to be added to the network graph. They
cannot be transited and do not affect the MRTs that are computed. cannot be transited and do not affect the MRTs that are computed.
The details of how the MRT-Blue and MRT-Red next-hops are computed The details of how the MRT-Blue and MRT-Red next-hops are computed
and how the appropriate alternate next-hops are selected is given in for proxy-nodes and how the appropriate alternate next-hops are
Section 5.8. selected is given in Section 5.8.
5.6. Compute MRT next-hops 5.6. Compute MRT next-hops
As was discussed in Section 4.1, once a ADAG is found, it is As was discussed in Section 4.1, once a ADAG is found, it is
straightforward to find the next-hops from any node X to the ADAG straightforward to find the next-hops from any node X to the ADAG
root. However, in this algorithm, we want to reuse the common GADAG root. However, in this algorithm, we will reuse the common GADAG and
and find not only the one pair of MRTs rooted at the GADAG root with find not only the one pair of MRTs rooted at the GADAG root with it,
it, but find a pair rooted at each node. This is useful since it is but find a pair rooted at each node. This is useful since it is
significantly faster to compute. It may also provide easier significantly faster to compute.
troubleshooting of the MRT-Red and MRT-Blue.
The method for computing differently rooted MRTs from the common The method for computing differently rooted MRTs from the common
GADAG is based on two ideas. First, if two nodes X and Y are ordered GADAG is based on two ideas. First, if two nodes X and Y are ordered
with respect to each other in the partial order, then an SPF along with respect to each other in the partial order, then an SPF along
OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a
decreasing-SPF) can be used to find the increasing and decreasing decreasing-SPF) can be used to find the increasing and decreasing
paths. Second, if two nodes X and Y aren't ordered with respect to paths. Second, if two nodes X and Y aren't ordered with respect to
each other in the partial order, then intermediary nodes can be used each other in the partial order, then intermediary nodes can be used
to create the paths by increasing/decreasing to the intermediary and to create the paths by increasing/decreasing to the intermediary and
then decreasing/increasing to reach Y. then decreasing/increasing to reach Y.
skipping to change at page 28, line 9 skipping to change at page 28, line 9
MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Blue path: X->Cloud 3->R->Cloud 1->Y
MRT-Red path: X->Cloud 2->Y MRT-Red path: X->Cloud 2->Y
Figure 19: Y << X Figure 19: Y << X
5.6.2. MRT next-hops to all nodes not partially ordered with respect to 5.6.2. MRT next-hops to all nodes not partially ordered with respect to
the computing node the computing node
When X and Y are not ordered, the first path should increase until we When X and Y are not ordered, the first path should increase until we
get to a node G, where G >> Y. At G, we need to decrease to Y. The get to a node G, where G >> Y. At G, we need to decrease to Y. The
other path should be just the opposite: we must decrease until we get other path should be just the opposite: we must decrease until we get
to a node H, where H << Y, and then increase. Since R is smaller and to a node H, where H << Y, and then increase. Since R is smaller and
greater than Y, such G and H must exist. It is also easy to see that greater than Y, such G and H must exist. It is also easy to see that
these two paths must be node disjoint: the first path contains nodes these two paths must be node disjoint: the first path contains nodes
in interval [X,G] and [Y,G], while the second path contains nodes in in interval [X,G] and [Y,G], while the second path contains nodes in
interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is interval [H,X] and [H,Y]. This is illustrated in Figure 20. It is
necessary to decrease and then increase for the MRT-Blue and increase necessary to decrease and then increase for the MRT-Blue and increase
and then decrease for the MRT-Red; if one simply increased for one and then decrease for the MRT-Red; if one simply increased for one
and decreased for the other, then both paths would go through the and decreased for the other, then both paths would go through the
root R. root R.
skipping to change at page 28, line 40 skipping to change at page 28, line 40
MRT-Blue path: decrease to H and increase to Y MRT-Blue path: decrease to H and increase to Y
X->Cloud 2->H->Cloud 5->Y X->Cloud 2->H->Cloud 5->Y
MRT-Red path: increase to G and decrease to Y MRT-Red path: increase to G and decrease to Y
X->Cloud 3->G->Cloud 6->Y X->Cloud 3->G->Cloud 6->Y
Figure 20: X and Y unordered Figure 20: X and Y unordered
This gives disjoint paths as long as G and H are not the same node. This gives disjoint paths as long as G and H are not the same node.
Since G >> Y and H << Y, if G and H could be the same node, that Since G >> Y and H << Y, if G and H could be the same node, that
would have to be the root R. This is not possible because there is would have to be the root R. This is not possible because there is
only one incoming interface to the root R which is created when the only one incoming interface to the root R which is created when the
initial cycle is found. Recall from Figure 6 that whenever an ear initial cycle is found. Recall from Figure 6 that whenever an ear
was found to have an end that was the root R, the ear was directed was found to have an end that was the root R, the ear was directed
from R so that the associated interface on R is outgoing and not from R so that the associated interface on R is outgoing and not
incoming. Therefore, there must be exactly one node M which is the incoming. Therefore, there must be exactly one node M which is the
largest one before R, so the MRT-Red path will never reach R; it will largest one before R, so the MRT-Red path will never reach R; it will
turn at M and decrease to Y. turn at M and decrease to Y.
5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 5.6.3. Computing Redundant Tree next-hops in a 2-connected Graph
skipping to change at page 29, line 22 skipping to change at page 29, line 22
case for IP networks), it is enough to find which nodes are greater case for IP networks), it is enough to find which nodes are greater
and less than X, and which are not ordered; this can be done by and less than X, and which are not ordered; this can be done by
running an increasing-SPF and a decreasing-SPF rooted at X and not running an increasing-SPF and a decreasing-SPF rooted at X and not
exploring any links from the ADAG root. ( Traversal algorithms other exploring any links from the ADAG root. ( Traversal algorithms other
than SPF could safely be used instead where one traversal takes the than SPF could safely be used instead where one traversal takes the
links in their given directions and the other reverses the links' links in their given directions and the other reverses the links'
directions.) directions.)
An increasing-SPF rooted at X and not exploring links from the root An increasing-SPF rooted at X and not exploring links from the root
will find the increasing next-hops to all Y >> X. Those increasing will find the increasing next-hops to all Y >> X. Those increasing
next-hops are X's next-hops on the MRT-Blue to reach Y. An next-hops are X's next-hops on the MRT-Blue to reach Y. A
decreasing-SPF rooted at X and not exploring links from the root will decreasing-SPF rooted at X and not exploring links from the root will
find the decreasing next-hops to all Z << X. Those decreasing next- find the decreasing next-hops to all Z << X. Those decreasing next-
hops are X's next-hops on the MRT-Red to reach Z. Since the root R hops are X's next-hops on the MRT-Red to reach Z. Since the root R
is both greater than and less than X, after this increasing-SPF and is both greater than and less than X, after this increasing-SPF and
decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to
reach R are known. For every node Y >> X, X's next-hops on the MRT- reach R are known. For every node Y >> X, X's next-hops on the MRT-
Red to reach Y are set to those on the MRT-Red to reach R. For every Red to reach Y are set to those on the MRT-Red to reach R. For every
node Z << X, X's next-hops on the MRT-Blue to reach Z are set to node Z << X, X's next-hops on the MRT-Blue to reach Z are set to
those on the MRT-Blue to reach R. those on the MRT-Blue to reach R.
For those nodes, which were not reached, we have the next-hops as For those nodes which were not reached by either the increasing-SPF
well. The increasing MRT-Blue next-hop for a node, which is not or the decreasing-SPF, we can determine the next-hops as well. The
ordered, is the next-hop along the decreasing MRT-Red towards R and increasing MRT-Blue next-hop for a node which is not ordered with
the decreasing MRT-Red next-hop is the next-hop along the increasing respect to X is the next-hop along the decreasing MRT-Red towards R,
MRT-Blue towards R. Naturally, since R is ordered with respect to all and the decreasing MRT-Red next-hop is the next-hop along the
the nodes, there will always be an increasing and a decreasing path increasing MRT-Blue towards R. Naturally, since R is ordered with
towards it. This algorithm does not provide the complete specific respect to all the nodes, there will always be an increasing and a
path taken but just the appropriate next-hops to use. The identity decreasing path towards it. This algorithm does not provide the
of G and H is not determined. complete specific path taken but just the appropriate next-hops to
use. The identities of G and H are not determined by the computing
node X.
The final case to considered is when the root R computes its own The final case to considered is when the root R computes its own
next-hops. Since the root R is << all other nodes, running an next-hops. Since the root R is << all other nodes, running an
increasing-SPF rooted at R will reach all other nodes; the MRT-Blue increasing-SPF rooted at R will reach all other nodes; the MRT-Blue
next-hops are those found with this increasing-SPF. Similarly, since next-hops are those found with this increasing-SPF. Similarly, since
the root R is >> all other nodes, running a decreasing-SPF rooted at the root R is >> all other nodes, running a decreasing-SPF rooted at
R will reach all other nodes; the MRT-Red next-hops are those found R will reach all other nodes; the MRT-Red next-hops are those found
with this decreasing-SPF. with this decreasing-SPF.
E---D---| E<--D<--| E---D---| E<--D<--|
skipping to change at page 30, line 18 skipping to change at page 30, line 18
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 2-connected graph A spanning ADAG rooted at R A 2-connected graph A spanning ADAG rooted at R
Figure 21 Figure 21
As an example consider the situation depicted in Figure 21. There As an example consider the situation depicted in Figure 21. Node C
node C runs an increasing-SPF and a decreasing-SPF The increasing-SPF runs an increasing-SPF and a decreasing-SPF on the ADAG. The
reaches D, E and R and the decreasing-SPF reaches B, A and R. So increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A
towards E the increasing next-hop is D (it was reached though D), and and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was
the decreasing next-hop is B (since R was reached though B). Since reached on the increasing path through D. And the MRT-Red next-hop
both D and B, A and R will compute the next hops similarly, the towards E is B, since R was reached on the decreasing path through B.
packets will reach E. Since E>>D, D will similarly compute its MRT-Blue next-hop to be E,
ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R
will similarly compute the MRT-Red next-hops towards E (which is
ordered less than B, A and R), ensuring that a packet on MRT-Red will
use path C-B-A-R-E.
We have the next-hops towards F as well: since F is not ordered with C can determine the next-hops towards F as well. Since F is not
respect to C, the MRT-Blue next-hop is the decreasing one towards R ordered with respect to C, the MRT-Blue next-hop is the decreasing
(which is B) and the MRT-Red next-hop is the increasing one towards R one towards R (which is B) and the MRT-Red next-hop is the increasing
(which is D). Since B is ordered with F, it will find, for its MRT- one towards R (which is D). Since F>>B, for its MRT-Blue next-hop
Blue, a real increasing next-hop, so packet forwarded to B will get towards F, B will use the real increasing next-hop towards F. So a
to F on path C-B-F. Similarly, D will have, for its MRT-Red, a real packet forwarded to B on MRT-Blue will get to F on path C-B-F.
decreasing next-hop, and the packet will use path C-D-F. Similarly, D will use the real decreasing next-hop towards F as its
MRT-Red next-hop, an packet on MRT-Red will use path C-D-F.
5.6.4. Generalizing for graph that isn't 2-connected 5.6.4. Generalizing for a graph that isn't 2-connected
If a graph isn't 2-connected, then the basic approach given in If a graph isn't 2-connected, then the basic approach given in
Section 5.6.3 needs some extensions to determine the appropriate MRT Section 5.6.3 needs some extensions to determine the appropriate MRT
next-hops to use for destinations outside the computing router X's next-hops to use for destinations outside the computing router X's
blocks. In order to find a pair of maximally redundant trees in that blocks. In order to find a pair of maximally redundant trees in that
graph we need to find a pair of RTs in each of the blocks (the root graph we need to find a pair of RTs in each of the blocks (the root
of these trees will be discussed later), and combine them. of these trees will be discussed later), and combine them.
When computing the MRT next-hops from a router X, there are three When computing the MRT next-hops from a router X, there are three
basic differences: basic differences:
skipping to change at page 31, line 14 skipping to change at page 31, line 19
B. If a node is explored in the outgoing SPF so Y >> X, then X's B. If a node is explored in the outgoing SPF so Y >> X, then X's
MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to
reach X's local-root and if Z << X, then X's MRT-Blue next- reach X's local-root and if Z << X, then X's MRT-Blue next-
hops to reach Z uses X's MRT-Blue next-hops to reach X's hops to reach Z uses X's MRT-Blue next-hops to reach X's
local-root. local-root.
C. If a node W in a common block with X was not reached in the C. If a node W in a common block with X was not reached in the
increasing-SPF or decreasing-SPF, then W is unordered with increasing-SPF or decreasing-SPF, then W is unordered with
respect to X. X's MRT-Blue next-hops to W are X's decreasing respect to X. X's MRT-Blue next-hops to W are X's decreasing
aka MRT-Red next-hops to X's local-root. X's MRT-Red next- (aka MRT-Red) next-hops to X's local-root. X's MRT-Red next-
hops to W are X's increasing aka Blue MRT next-hops to X's hops to W are X's increasing (aka MRT-Blue) next-hops to X's
local-root. local-root.
3. For nodes in different blocks, the next-hops must be inherited 3. For nodes in different blocks, the next-hops must be inherited
via the relevant cut-vertex. via the relevant cut-vertex.
These are all captured in the detailed algorithm given in These are all captured in the detailed algorithm given in
Section 5.6.5. Section 5.6.5.
5.6.5. Complete Algorithm to Compute MRT Next-Hops 5.6.5. Complete Algorithm to Compute MRT Next-Hops
skipping to change at page 33, line 38 skipping to change at page 33, line 43
Compute_MRT_NextHops(x, root) Compute_MRT_NextHops(x, root)
Figure 22 Figure 22
5.7. Identify MRT alternates 5.7. Identify MRT alternates
At this point, a computing router S knows its MRT-Blue next-hops and At this point, a computing router S knows its MRT-Blue next-hops and
MRT-Red next-hops for each destination in the MRT Island. The MRT-Red next-hops for each destination in the MRT Island. The
primary next-hops along the SPT are also known. It remains to primary next-hops along the SPT are also known. It remains to
determine for each primary next-hop to a destination D, which of the determine for each primary next-hop to a destination D, which of the
MRTs avoids the primary next-hop node F. This computation depends MRTs avoids the primary next-hop node F. This computation depends
upon data set in Compute_MRT_NextHops such as each node y's upon data set in Compute_MRT_NextHops such as each node y's
y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower
and topo_orders. Recall that any router knows only which are the and topo_orders. Recall that any router knows only which are the
nodes greater and lesser than itself, but it cannot decide the nodes greater and lesser than itself, but it cannot decide the
relation between any two given nodes easily; that is why we need relation between any two given nodes easily; that is why we need
topological ordering. topological ordering.
For each primary next-hop node F to each destination D, S can call For each primary next-hop node F to each destination D, S can call
Select_Alternates(S, D, F, primary_intf) to determine whether to use Select_Alternates(S, D, F, primary_intf) to determine whether to use
the MRT-Blue next-hops as the alternate next-hop(s) for that primary the MRT-Blue next-hops as the alternate next-hop(s) for that primary
skipping to change at page 36, line 10 skipping to change at page 36, line 15
case (iii) holds true, which means that selecting the Blue next-hop case (iii) holds true, which means that selecting the Blue next-hop
is safe. Similarly, if F.topo_order<D.topo_order, we should select is safe. Similarly, if F.topo_order<D.topo_order, we should select
the Red next-hop. The situation is almost the same if both F and D the Red next-hop. The situation is almost the same if both F and D
are less than S. are less than S.
Recall that we have added each link to the GADAG in some direction, Recall that we have added each link to the GADAG in some direction,
so it is impossible that S and F are not ordered. But it is possible so it is impossible that S and F are not ordered. But it is possible
that S and D are not ordered, so we need to deal with this case as that S and D are not ordered, so we need to deal with this case as
well. If F<<S, we can use the Red next-hop, because that path is well. If F<<S, we can use the Red next-hop, because that path is
first increasing until a node definitely greater than D is reached, first increasing until a node definitely greater than D is reached,
than decreasing; this path must avoid using F. Similarly, if F>>S, we then decreasing; this path must avoid using F. Similarly, if F>>S,
should use the Blue next-hop. we should use the Blue next-hop.
Additionally, the cases where either F or D is ordered both higher Additionally, the cases where either F or D is ordered both higher
and lower must be considered; this can happen when one is a block- and lower must be considered; this can happen when one is a block-
root or its order_proxy is. If D is both higher and lower than S, root or its order_proxy is. If D is both higher and lower than S,
then the MRT to use is the one that avoids F so if F is higher, then then the MRT to use is the one that avoids F so if F is higher, then
the MRT-Red should be used and if F is lower, then the MRT-Blue the MRT-Red should be used and if F is lower, then the MRT-Blue
should be used; F and S must be ordered because they are neighbors. should be used; F and S must be ordered because they are neighbors.
If F is both higher and lower, then if D is lower, using the MRT-Red If F is both higher and lower, then if D is lower, using the MRT-Red
to decrease reaches D and if D is higher, using the Blue MRT to to decrease reaches D and if D is higher, using the Blue MRT to
increase reaches D; if D is unordered compared to S, then the increase reaches D; if D is unordered compared to S, then the
skipping to change at page 36, line 34 skipping to change at page 36, line 39
In the case where F<<S<<F and D and S are unordered, the direction of In the case where F<<S<<F and D and S are unordered, the direction of
the link in the GADAG between S and F should be examined. If the the link in the GADAG between S and F should be examined. If the
link is directed S -> F, then use the MRT-Blue (decrease to avoid link is directed S -> F, then use the MRT-Blue (decrease to avoid
that link and then increase). If the link is directed S <- F, then that link and then increase). If the link is directed S <- F, then
use the MRT-Red (increase to avoid that link and then decrease). If use the MRT-Red (increase to avoid that link and then decrease). If
the link is S <--> F, then the link must be a cut-link and there is the link is S <--> F, then the link must be a cut-link and there is
no node-protecting alternate. If there are multiple links between S no node-protecting alternate. If there are multiple links between S
and F, then they can protect against each other; of course, in this and F, then they can protect against each other; of course, in this
situation, they are probably already ECMP. situation, they are probably already ECMP.
Finally, there is the case where D is also F. In this case, only link Finally, there is the case where D is also F. In this case, only
protection is possible. The MRT that doesn't use the indicated link protection is possible. The MRT that doesn't use the indicated
primary next-hop is used. If both MRTs use the primary next-hop, primary next-hop is used. If both MRTs use the primary next-hop,
then the primary next-hop must be a cut-link so either MRT could be then the primary next-hop must be a cut-link so either MRT could be
used but the set of MRT next-hops must be pruned to avoid that used but the set of MRT next-hops must be pruned to avoid that
primary next-hop. To indicate this case, Select_Alternates returns primary next-hop. To indicate this case, Select_Alternates returns
AVOID_LINK_ON_BLUE. AVOID_LINK_ON_BLUE.
As an example, consider the ADAG depicted in Figure 24 and first As an example, consider the ADAG depicted in Figure 24 and first
suppose that G is the source, D is the destination and H is the suppose that G is the source, D is the destination and H is the
failed next-hop. Since D>>G, we need to compare H.topo_order and failed next-hop. Since D>>G, we need to compare H.topo_order and
D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller
skipping to change at page 37, line 47 skipping to change at page 38, line 6
individual proxy-node can be individually added to the GADAG. The individual proxy-node can be individually added to the GADAG. The
proxy-node is connected to at most two nodes in the GADAG. proxy-node is connected to at most two nodes in the GADAG.
Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the
proxy-node attachments MUST be determined. The degenerate case where proxy-node attachments MUST be determined. The degenerate case where
the proxy-node is attached to only one node in the GADAG is trivial the proxy-node is attached to only one node in the GADAG is trivial
as all needed information can be derived from that attachment node; as all needed information can be derived from that attachment node;
if there are different interfaces, then some can be assigned to MRT- if there are different interfaces, then some can be assigned to MRT-
Red and others to MRT_Blue. Red and others to MRT_Blue.
Now, consider the proxy-node that is attached to exactly two nodes in Now, consider the proxy-node that is attached to exactly two nodes in
the GADAG. Let the order_proxies of these nodes be A and B. Let the the GADAG. Let the order_proxies of these nodes be A and B. Let the
current node, where next-hop is just being calculated, be S. If one current node, where next-hop is just being calculated, be S. If one
of these two nodes A and B is the local root of S, let A=S.local_root of these two nodes A and B is the local root of S, let A=S.local_root
and the other one be B. Otherwise, let A.topo_order < B.topo_order. and the other one be B. Otherwise, let A.topo_order < B.topo_order.
A valid GADAG was constructed. Instead doing an increasing-SPF and a A valid GADAG was constructed. Instead doing an increasing-SPF and a
decreasing-SPF to find ordering for the proxy-nodes, the following decreasing-SPF to find ordering for the proxy-nodes, the following
simple rules, providing the same result, can be used independently simple rules, providing the same result, can be used independently
for each different proxy-node. For the following rules, let for each different proxy-node. For the following rules, let
X=A.local_root, and if A is the local root, let that be strictly X=A.local_root, and if A is the local root, let that be strictly
lower than any other node. Always take the first rule that matches. lower than any other node. Always take the first rule that matches.
Rule Condition Blue NH Red NH Notes Rule Condition Blue NH Red NH Notes
1 S=X Blue to A Red to B 1 S=X Blue to A Red to B
skipping to change at page 39, line 47 skipping to change at page 39, line 47
return return
P.blue_next_hops = R.red_next_hops P.blue_next_hops = R.red_next_hops
P.red_next_hops = R.blue_next_hops P.red_next_hops = R.blue_next_hops
return return
After finding the the red and the blue next-hops, it is necessary to After finding the the red and the blue next-hops, it is necessary to
know which one of these to use in the case of failure. This can be know which one of these to use in the case of failure. This can be
done by Select_Alternates_Inner(). In order to use done by Select_Alternates_Inner(). In order to use
Select_Alternates_Internal(), we need to know if P is greater, less Select_Alternates_Internal(), we need to know if P is greater, less
or unordered with S, and P.topo_order. P.lower = B.lower, P.higher = or unordered with S, and P.topo_order. P.lower = B.lower, P.higher =
A.higher, and any value is OK for P.topo_order, until A.higher, and any value is OK for P.topo_order, as long as
A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not
equal to the topo_order of the failed node. So for simplicity let equal to the topo_order of the failed node. So for simplicity let
P.topo_order=A.topo_order when the next-hop is not A, and P.topo_order=A.topo_order when the next-hop is not A, and
P.topo_order=B.topo_order otherwise. This gives the following P.topo_order=B.topo_order otherwise. This gives the following
pseudo-code: pseudo-code:
Select_Alternates_Proxy_Node(S, P, F, primary_intf) Select_Alternates_Proxy_Node(S, P, F, primary_intf)
if (F is not P.neighbor_A) if (F is not P.neighbor_A)
return Select_Alternates_Internal(S, P, F, primary_intf, return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower, P.neighbor_B.lower,
P.neighbor_A.higher, P.neighbor_A.higher,
P.neighbor_A.topo_order) P.neighbor_A.topo_order)
else else
return Select_Alternates_Internal(S, P, F, primary_intf, return Select_Alternates_Internal(S, P, F, primary_intf,
P.neighbor_B.lower, P.neighbor_B.lower,
P.neighbor_A.higher, P.neighbor_A.higher,
P.neighbor_B.topo_order) P.neighbor_B.topo_order)
Figure 25 Figure 25
6. MRT Lowpoint Algorithm: Complete Specification 6. MRT Lowpoint Algorithm: Next-hop conformance
This specification defines the MRT Lowpoint Algorithm, which include This specification defines the MRT Lowpoint Algorithm, which include
the construction of a common GADAG and the computation of MRT-Red and the construction of a common GADAG and the computation of MRT-Red and
MRT-Blue next-hops to each node in the graph. An implementation MAY MRT-Blue next-hops to each node in the graph. An implementation MAY
select any subset of next-hops for MRT-Red and MRT-Blue that respect select any subset of next-hops for MRT-Red and MRT-Blue that respect
the available nodes that are described in Section 5.6 for each of the the available nodes that are described in Section 5.6 for each of the
MRT-Red and MRT-Blue and the selected next-hops are further along in MRT-Red and MRT-Blue and the selected next-hops are further along in
the interval of allowed nodes towards the destination. the interval of allowed nodes towards the destination.
For example, the MRT-Blue next-hops used when the destination Y >> S, For example, the MRT-Blue next-hops used when the destination Y >> X,
the computing router, MUST be one or more nodes, T, whose topo_order the computing router, MUST be one or more nodes, T, whose topo_order
is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y
is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in
the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, the interval [R-small.topo_order, X.topo_order] or [Y.topo_order,
R-big.topo_order]. R-big.topo_order].
Implementations SHOULD implement the Select_Alternates() function to Implementations SHOULD implement the Select_Alternates() function to
pick an MRT-FRR alternate. pick an MRT-FRR alternate.
In a future version, this section will include pseudo-code describing
the full code path through the pseudo-code given earlier in the
draft.
7. Algorithm Alternatives and Evaluation 7. Algorithm Alternatives and Evaluation
This specification defines the MRT Lowpoint Algorithm, which is one This specification defines the MRT Lowpoint Algorithm, which is one
option among several possible MRT algorithms. Other alternatives are option among several possible MRT algorithms. Other alternatives are
described in the appendices. described in the appendices.
In addition, it is possible to calculate Destination-Rooted GADAG, In addition, it is possible to calculate Destination-Rooted GADAG,
where for each destination, a GADAG rooted at that destination is where for each destination, a GADAG rooted at that destination is
computed. Then a router can compute the blue MRT and red MRT next- computed. Then a router can compute the blue MRT and red MRT next-
hops to that destination. Building GADAGs per destination is hops to that destination. Building GADAGs per destination is
skipping to change at page 51, line 5 skipping to change at page 51, line 5
| T219(avg primary hops=7.7) | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | |
| MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| | 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_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 ( 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 (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7|
| MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 32 Figure 32
8. Algorithm Work to Be Done 8. 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.
9. Algorithm Work to Be Done
Broadcast Interfaces: The algorithm assumes that broadcast Broadcast Interfaces: The algorithm assumes that broadcast
interfaces are already represented as pseudo-nodes in the network interfaces are already represented as pseudo-nodes in the network
graph. Given maximal redundancy, one of the MRT will try to avoid graph. Given maximal redundancy, one of the MRT will try to avoid
both the pseudo-node and the next hop. The exact rules need to be both the pseudo-node and the next hop. The exact rules need to be
fully specified. fully specified.
9. IANA Considerations 10. Acknowledgements
This doument includes no request to IANA. The authors would like to thank Shraddha Hegde for her suggestions
and review.
10. Security Considerations 11. IANA Considerations
This document includes no request to IANA.
12. Security Considerations
This architecture is not currently believed to introduce new security This architecture is not currently believed to introduce new security
concerns. concerns.
11. References 13. References
11.1. Normative References 13.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-architecture] [I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Envedi, G., Csaszar, A., Tantsura, Atlas, A., Kebler, R., Bowers, C., Enyedi, G., Csaszar,
J., Konstantynowicz, M., and R. White, "An Architecture A., Tantsura, J., Konstantynowicz, M., and R. White, "An
for IP/LDP Fast-Reroute Using Maximally Redundant Trees", Architecture for IP/LDP Fast-Reroute Using Maximally
draft-ietf-rtgwg-mrt-frr-architecture-03 (work in Redundant Trees", draft-rtgwg-mrt-frr-architecture-04
progress), July 2013. (work in progress), July 2014.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
11.2. Informative References 13.2. Informative References
[EnyediThesis] [EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute", Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics, Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D. Budapest University of Technology and Economics Ph.D.
Thesis, February 2011, <http://www.omikk.bme.hu/ Thesis, February 2011, <http://www.omikk.bme.hu/collection
collections/phd/Villamosmernoki_es_Informatikai_Kar/2011/ s/phd/Villamosmernoki_es_Informatikai_Kar/2011/
Enyedi_Gabor/ertekezes.pdf>. Enyedi_Gabor/ertekezes.pdf>.
[I-D.atlas-mpls-ldp-mrt] [I-D.atlas-mpls-ldp-mrt]
Atlas, A., Tiruveedhula, K., Tantsura, J., and I. Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ.
Wijnands, "LDP Extensions to Support Maximally Redundant Wijnands, "LDP Extensions to Support Maximally Redundant
Trees", draft-atlas-mpls-ldp-mrt-00 (work in progress), Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress),
July 2013. July 2014.
[I-D.atlas-ospf-mrt] [I-D.atlas-ospf-mrt]
Atlas, A., Hegde, S., cbowers@juniper.net, c., and J. Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF
Tantsura, "OSPF Extensions to Support Maximally Redundant Extensions to Support Maximally Redundant Trees", draft-
Trees", draft-atlas-ospf-mrt-01 (work in progress), atlas-ospf-mrt-02 (work in progress), July 2014.
October 2013.
[I-D.ietf-rtgwg-ipfrr-notvia-addresses] [I-D.ietf-rtgwg-ipfrr-notvia-addresses]
Bryant, S., Previdi, S., and M. Shand, "A Framework for IP Bryant, S., Previdi, S., and M. Shand, "A Framework for IP
and MPLS Fast Reroute Using Not-via Addresses", draft- and MPLS Fast Reroute Using Not-via Addresses", draft-
ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress),
May 2013. May 2013.
[I-D.ietf-rtgwg-lfa-manageability] [I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and p. psarkar@juniper.net, "Operational Horneffer, M., and p. psarkar@juniper.net, "Operational
management of Loop Free Alternates", draft-ietf-rtgwg-lfa- management of Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-03 (work in progress), February 2014. manageability-03 (work in progress), February 2014.
[I-D.ietf-rtgwg-remote-lfa] [I-D.ietf-rtgwg-remote-lfa]
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S. Bryant, S., Filsfils, C., Previdi, S., Shand, M., and S.
Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-04 Ning, "Remote LFA FRR", draft-ietf-rtgwg-remote-lfa-06
(work in progress), November 2013. (work in progress), May 2014.
[I-D.li-isis-mrt] [I-D.li-isis-mrt]
Li, Z., Wu, N., Zhao, Q., Atlas, A., cbowers@juniper.net, Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
c., and J. Tantsura, "Intermediate System to Intermediate Tantsura, "Intermediate System to Intermediate System (IS-
System (IS-IS) Extensions for Maximally Redundant Trees IS) Extensions for Maximally Redundant Trees(MRT)", draft-
(MRT)", draft-li-isis-mrt-00 (work in progress), October li-isis-mrt-01 (work in progress), July 2014.
2013.
[Kahn_1962_topo_sort] [Kahn_1962_topo_sort]
Kahn, A., "Topological sorting of large networks", Kahn, A., "Topological sorting of large networks",
Communications of the ACM, Volume 5, Issue 11 , Nov 1962, Communications of the ACM, Volume 5, Issue 11 , Nov 1962,
<http://dl.acm.org/citation.cfm?doid=368996.369025>. <http://dl.acm.org/citation.cfm?doid=368996.369025>.
[LFARevisited] [LFARevisited]
Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP
Fast ReRoute: Loop Free Alternates Revisited", Proceedings Fast ReRoute: Loop Free Alternates Revisited", Proceedings
of IEEE INFOCOM , 2011, <http://opti.tmit.bme.hu/~tapolcai of IEEE INFOCOM , 2011,
/papers/retvari2011lfa_infocom.pdf>. <http://opti.tmit.bme.hu/~tapolcai/papers/
retvari2011lfa_infocom.pdf>.
[LightweightNotVia] [LightweightNotVia]
Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP
Fast ReRoute: Lightweight Not-Via without Additional Fast ReRoute: Lightweight Not-Via without Additional
Addresses", Proceedings of IEEE INFOCOM , 2009, Addresses", Proceedings of IEEE INFOCOM , 2009,
<http://mycite.omikk.bme.hu/doc/71691.pdf>. <http://mycite.omikk.bme.hu/doc/71691.pdf>.
[MRTLinear] [MRTLinear]
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE Maximally Redundant Trees in Strictly Linear Time", IEEE
skipping to change at page 54, line 10 skipping to change at page 54, line 24
should not be used during the SPF computation. This prevents should not be used during the SPF computation. This prevents
ears from starting and ending at the same node and avoids cycles; ears from starting and ending at the same node and avoids cycles;
the exception is because cycles to/from the block-root are the exception is because cycles to/from the block-root are
acceptable and expected. acceptable and expected.
c. Do not explore links to nodes whose local-root is not the block- c. Do not explore links to nodes whose local-root is not the block-
root. This keeps the SPF confined to the particular block. root. This keeps the SPF confined to the particular block.
d. Terminate when the first IN_GADAG node z is minimized. d. Terminate when the first IN_GADAG node z is minimized.
e. Respect the existing directions (e.g. INCOMING, OUTGOING, e. Respect the existing directions (e.g. INCOMING, OUTGOING,
UNDIRECTED) already specified for each interface. UNDIRECTED) already specified for each interface.
Mod_SPF(spf_root, block_root) Mod_SPF(spf_root, block_root)
Initialize spf_heap to empty Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity Initialize nodes' spf_metric to infinity
spf_root.spf_metric = 0 spf_root.spf_metric = 0
insert(spf_heap, spf_root) insert(spf_heap, spf_root)
found_in_gadag = false found_in_gadag = false
while (spf_heap is not empty) and (found_in_gadag is false) while (spf_heap is not empty) and (found_in_gadag is false)
min_node = remove_lowest(spf_heap) min_node = remove_lowest(spf_heap)
skipping to change at page 55, line 18 skipping to change at page 55, line 31
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 33: Modified SPF for GADAG computation Figure 33: Modified SPF for GADAG computation
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 path should be y->x...q->z but if y >> z, then the path should be y<-
y<-x...q<-z. In Section 5.4, the same problem was handled by finding x...q<-z. In Section 5.4, the same problem was handled by finding
all ears that started at a node before looking at ears starting at 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 algorithm, using that
approach could mean that new ears aren't added in order of their approach could mean that new ears aren't added in order of their
total cost since all ears connected to a node would need to be found total cost since all ears connected to a node would need to be found
before additional nodes could 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
skipping to change at page 57, line 17 skipping to change at page 57, line 17
maintained of interfaces that could be explored from the IN_GADAG maintained of interfaces that could be explored from the IN_GADAG
nodes. The interfaces are ordered by their characteristics of nodes. The interfaces are ordered by their characteristics of
metric, local loopback address, remote loopback address, and ifindex, metric, local loopback address, remote loopback address, and ifindex,
as in the algorithm previously described in Figure 14. as in the algorithm previously described in Figure 14.
The algorithm ignores interfaces picked from the ordered tree that The algorithm ignores interfaces picked from the ordered tree that
belong to the block root if the block in which the interface is belong to the block root if the block in which the interface is
present already has an ear that has been computed. This is necessary present already has an ear that has been computed. This is necessary
since we allow at most one incoming interface to a block root in each since we allow at most one incoming interface to a block root in each
block. This requirement stems from the way next-hops are computed as block. This requirement stems from the way next-hops are computed as
will be seen in Section 5.6. After any ear gets computed, we was seen in Section 5.6. After any ear gets computed, we traverse
traverse the newly added nodes to the GADAG and insert interfaces the newly added nodes to the GADAG and insert interfaces whose far
whose far end is not yet on the GADAG to the ordered tree for later end is not yet on the GADAG to the ordered tree for later processing.
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 58, line 38 skipping to change at page 58, line 37
add_eligible_interfaces_of_node( add_eligible_interfaces_of_node(
ordered_intfs_tree, ordered_intfs_tree,
y.local_node) y.local_node)
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
Figure 35: SPF-based GADAG algorithm Figure 35: SPF-based GADAG algorithm
Appendix B. Option 3: Computing GADAG using a hybrid method Appendix B. Option 3: Computing GADAG using a hybrid method
In this option, the idea is to combine the salient features of the In this option, the idea is to combine the salient features of the
above two options. To this end, we process nodes as they get added lowpoint inheritance and SPF methods. To this end, we process nodes
to the GADAG just like in the lowpoint inheritance by maintaining a as they get added to the GADAG just like in the lowpoint inheritance
stack of nodes. This ensures that we do not need to maintain lower by maintaining a stack of nodes. This ensures that we do not need to
and higher sets at each node to ascertain ear directions since the maintain lower and higher sets at each node to ascertain ear
ears will always be directed from the node being processed towards directions since the ears will always be directed from the node being
the end of the ear. To compute the ear however, we resort to an SPF processed towards the end of the ear. To compute the ear however, we
to have the possibility of better ears (path lentghs) thus giving resort to an SPF to have the possibility of better ears (path
more flexibility than the restricted use of lowpoint/dfs parents. lentghs) thus giving more flexibility than the restricted use of
lowpoint/dfs parents.
Regarding ears involving a block root, unlike the SPF method which Regarding ears involving a block root, unlike the SPF method which
ignored interfaces of the block root after the first ear, in the ignored interfaces of the block root after the first ear, in the
hybrid method we would have to process all interfaces of the block hybrid method we would have to process all interfaces of the block
root before moving on to other nodes in the block since the direction root before moving on to other nodes in the block since the direction
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
 End of changes. 69 change blocks. 
193 lines changed or deleted 233 lines changed or added

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