draft-ietf-rtgwg-mrt-frr-algorithm-02.txt   draft-ietf-rtgwg-mrt-frr-algorithm-03.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: July 23, 2015 A. Atlas, Ed. Expires: September 10, 2015 A. Atlas, Ed.
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
January 19, 2015 March 9, 2015
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-02 draft-ietf-rtgwg-mrt-frr-algorithm-03
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 July 23, 2015. This Internet-Draft will expire on September 10, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 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 24 skipping to change at page 2, line 24
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 . . . . . . . . . . . . . . . . . . . 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. Interface Ordering . . . . . . . . . . . . . . . . . . . 19
5.2. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22
5.3. Initialization . . . . . . . . . . . . . . . . . . . . . 21 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23
inheritance . . . . . . . . . . . . . . . . . . . . . . . 22 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
5.5. Augmenting the GADAG by directing all links . . . . . . . 24 inheritance . . . . . . . . . . . . . . . . . . . . . . . 24
5.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 26 5.6. Augmenting the GADAG by directing all links . . . . . . . 26
5.6.1. MRT next-hops to all nodes partially ordered with 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 28
respect to the computing node . . . . . . . . . . . . 27 5.7.1. MRT next-hops to all nodes partially ordered with
5.6.2. MRT next-hops to all nodes not partially ordered with respect to the computing node . . . . . . . . . . . . 29
respect to the computing node . . . . . . . . . . . . 28 5.7.2. MRT next-hops to all nodes not partially ordered with
5.6.3. Computing Redundant Tree next-hops in a 2-connected respect to the computing node . . . . . . . . . . . . 30
Graph . . . . . . . . . . . . . . . . . . . . . . . . 29 5.7.3. Computing Redundant Tree next-hops in a 2-connected
5.6.4. Generalizing for a graph that isn't 2-connected . . . 30 Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
5.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 31 5.7.4. Generalizing for a graph that isn't 2-connected . . . 32
5.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 33 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 33
5.8. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 37 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 35
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 40 5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 39
7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 40 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 42
7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 41 7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42
8. Implementation Status . . . . . . . . . . . . . . . . . . . . 51 7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 43
9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 51 8. Implementation Status . . . . . . . . . . . . . . . . . . . . 53
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 51 9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 53
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 51 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53
12. Security Considerations . . . . . . . . . . . . . . . . . . . 51 11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 51 12. Security Considerations . . . . . . . . . . . . . . . . . . . 53
13.1. Normative References . . . . . . . . . . . . . . . . . . 51 13. References . . . . . . . . . . . . . . . . . . . . . . . . . 53
13.2. Informative References . . . . . . . . . . . . . . . . . 51 13.1. Normative References . . . . . . . . . . . . . . . . . . 53
13.2. Informative References . . . . . . . . . . . . . . . . . 53
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 53 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 56
Appendix B. Option 3: Computing GADAG using a hybrid method . . 58 Appendix B. Option 3: Computing GADAG using a hybrid method . . 61
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 60 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 63
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
skipping to change at page 9, line 20 skipping to change at page 9, line 20
disjoint from the decreasing paths. E.g. in the previous example disjoint from the decreasing paths. E.g. in the previous example
node B has multiple possibilities to forward packets along an node B has multiple possibilities to forward packets along an
increasing path: it can either forward packets to C or F. increasing path: it can either forward packets to C or F.
4.2. Finding an Ear and the Correct Direction 4.2. Finding an Ear and the Correct Direction
For simplicity, the basic idea of creating a GADAG by adding ears is For simplicity, the basic idea of creating a GADAG by adding ears is
described assuming that the network graph is a single 2-connected described assuming that the network graph is a single 2-connected
cluster so that an ADAG is sufficient. Generalizing to multiple cluster so that an ADAG is sufficient. Generalizing to multiple
blocks is done by considering the block-roots instead of the GADAG blocks is done by considering the block-roots instead of the GADAG
root - and the actual algorithm is given in Section 5.4. root - and the actual algorithm is given in Section 5.5.
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
skipping to change at page 10, line 27 skipping to change at page 10, line 27
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.7
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
skipping to change at page 11, line 27 skipping to change at page 11, line 27
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 Algorithm Figure 6 merely requires that a cycle or ear be selected
without specifying how. Regardless of the way of selecting the path, without specifying how. Regardless of the way of selecting the path,
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.5. 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 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
skipping to change at page 13, line 12 skipping to change at page 13, line 12
Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to
a example graph. a example graph.
global_variable: dfs_number global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x) Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number D(x) = dfs_number
L(x) = D(x) L(x) = D(x)
dfs_number += 1 dfs_number += 1
x.dfs_parent = parent x.dfs_parent = parent
x.dfs_parent_intf = p_to_x x.dfs_parent_intf = p_to_x.remote_intf
x.lowpoint_parent = NONE x.lowpoint_parent = NONE
for each interface intf of x for each interface intf of x
if D(intf.remote_node) is not set if D(intf.remote_node) is not set
Lowpoint_Visit(intf.remote_node, x, intf) Lowpoint_Visit(intf.remote_node, x, intf)
if L(intf.remote_node) < L(x) if L(intf.remote_node) < L(x)
L(x) = L(intf.remote_node) L(x) = L(intf.remote_node)
x.lowpoint_parent = intf.remote_node x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf x.lowpoint_parent_intf = intf
else if intf.remote_node is not parent else if intf.remote_node is not parent
if D(intf.remote_node) < L(x) if D(intf.remote_node) < L(x)
skipping to change at page 14, line 33 skipping to change at page 14, line 33
[A]---------[B] [G]----| [L]------[M] [A]---------[B] [G]----| [L]------[M]
(1, ) (2, ) (7, ) (12, ) (13, ) (1, ) (2, ) (7, ) (12, ) (13, )
(b) with DFS values assigned (D(x), L(x)) (b) with DFS values assigned (D(x), L(x))
[E]----| [J]---------[I] [P]------[O] [E]----| [J]---------[I] [P]------[O]
(5,0) | (10,3) (9,3) (16,11) (15,11) (5,0) | (10,3) (9,3) (16,11) (15,11)
| | | | | | | | | | | |
| | | | | | | | | | | |
[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,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 9: Example lowpoint value computation Figure 9: Example lowpoint value computation
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 9, 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.
skipping to change at page 16, line 5 skipping to change at page 16, line 5
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
isolated nodes). To compute GADAGs and thus MRTs, computation is isolated nodes). To compute GADAGs and thus MRTs, computation is
done in each block to compute ADAGs or Redundant Trees and then those done in each block to compute ADAGs or Redundant Trees and then those
ADAGs or Redundant Trees are combined into a GADAG or MRT. 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:
3 2-connected clusters and a cut-link three 2-connected clusters
and one cut-link
[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 | |
[A]------->[B] [G]---| [L]-->[M] [A]------->[B] [G]---| [L]-->[M]
(b) MRT-Blue (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 (c) MRT-Red for destionation 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
through a cut-link that is block 4. No two blocks can have more than through a cut-link that is block 4. No two blocks can have more than
one common node, since two blocks with at least 2 common nodes would one common node, since two blocks with at least two common nodes
qualify as a single 2-connected cluster. would qualify as a single 2-connected cluster.
Moreover, observe that if we want to get from one block to another, Moreover, observe that if we want to get from one block to another,
we must use a cut-vertex (the cut-vertices in this graph are C, H, we must use a cut-vertex (the cut-vertices in this graph are C, H,
K), regardless of the path selected, so we can say that all the paths K), regardless of the path selected, so we can say that all the paths
from block 3 along the MRTs rooted at R will cross K first. This from block 3 along the MRTs rooted at R will cross K first. This
observation means that if we want to find a pair of MRTs rooted at R, observation means that if we want to find a pair of MRTs rooted at R,
then we need to build up a pair of RTs in block 3 with K as a root. then we need to build up a pair of RTs in block 3 with K as a root.
Similarly, we need to find another pair of RTs in block 2 with C as a Similarly, we need to find another pair of RTs in block 2 with C as a
root, and finally, we need the last pair of RTs in block 1 with R as root, and finally, we need the last pair of RTs in block 1 with R as
a root. When all the trees are selected, we can simply combine them; a root. When all the trees are selected, we can simply combine them;
skipping to change at page 17, line 33 skipping to change at page 17, line 33
4.5. Determining Local-Root and Assigning Block-ID 4.5. Determining Local-Root and Assigning Block-ID
Each node in a network graph has a local-root, which is the cut- Each node in a network graph has a local-root, which is the cut-
vertex (or root) in the same block that is closest to the root. The vertex (or root) in the same block that is closest to the root. The
local-root is used to determine whether two nodes share a common local-root is used to determine whether two nodes share a common
block. block.
Compute_Localroot(node x, node localroot) Compute_Localroot(node x, node localroot)
x.localroot = localroot x.localroot = localroot
for each DFS child c for each DFS child node c of x
if L(c) < D(x) //x is not a cut-vertex if L(c) < D(x) //x is not a cut-vertex
Compute_Localroot(c, x.localroot) Compute_Localroot(c, x.localroot)
else else
mark x as cut-vertex mark x as cut-vertex
Compute_Localroot(c, x) Compute_Localroot(c, x)
Compute_Localroot(root, root) Compute_Localroot(root, 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 MRT algorithms given in
the Appendices Appendix A and Appendix B. The MRT Lowpoint algorithm the Appendices Appendix A and Appendix B. 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. in Figure 12. Both methods for computing the local-root produce the
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
for each node x in the ear that is not s for each node x in the ear that is not s
x.localroot = s x.localroot = s
else else
for each node x in the ear that is not s or e for each node x in the ear that is not s or e
skipping to change at page 19, line 15 skipping to change at page 19, line 15
5. Algorithm Sections 5. Algorithm Sections
This algorithm computes one GADAG that is then used by a router to This algorithm computes one GADAG that is then used by a router to
determine its MRT-Blue and MRT-Red next-hops to all destinations. determine its MRT-Blue and MRT-Red next-hops to all destinations.
Finally, based upon that information, alternates are selected for Finally, based upon that information, alternates are selected for
each next-hop to each destination. The different parts of this each next-hop to each destination. The different parts of this
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.2.]
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.3.]
3. Initialize all interfaces to UNDIRECTED. [See Section 5.3.] 3. Initialize all interfaces to UNDIRECTED. [See Section 5.4.]
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 8.] Figure 8.]
5. Construct the GADAG. [See Section 5.4] 5. Construct the GADAG. [See Section 5.5]
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.6.]
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.7.]
8. Identify alternates for each next-hop to each destination by 8. Identify alternates for each next-hop to each destination by
determining which one of the blue MRT and the red MRT the determining which one of the blue MRT and the red MRT the
computing router x should select. [See Section 5.7.] computing router x should select. [See Section 5.8.]
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, where to the same neighboring node. This is necessary for the DFS, where
the selection order of the interfaces to explore results in different the selection order of the interfaces to explore results in different
trees, and for computing the GADAG, where the selection order of the trees, and for computing the GADAG, where the selection order of the
interfaces to use to form ears can result in different GADAGs. The interfaces to use to form ears can result in different GADAGs. The
required ordering between two interfaces from the same router x is required ordering between two interfaces from the same router x is
given in Figure 14. given in Figure 14.
Interface_Compare(interface a, interface b) Interface_Compare(interface a, interface b)
if a.metric < b.metric if a.metric < b.metric
return A_LESS_THAN_B return A_LESS_THAN_B
if b.metric < a.metric if b.metric < a.metric
return B_LESS_THAN_A return B_LESS_THAN_A
if a.neighbor.loopback_addr < b.neighbor.loopback_addr if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
return A_LESS_THAN_B return A_LESS_THAN_B
if b.neighbor.loopback_addr < a.neighbor.loopback_addr if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
return B_LESS_THAN_A return B_LESS_THAN_A
// Same metric to same node, so the order doesn't matter anymore for // Same metric to same node, so the order doesn't matter for
// interoperability. // interoperability.
// To have a unique, consistent total order, return A_EQUAL_TO_B
// tie-break in OSPF based on the link's linkData as
// distributed in an OSPF Router-LSA
if a.link_data < b.link_data
return A_LESS_THAN_B
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 In Figure 14, if two interfaces on a router connect to the same
remote router with the same metric, the Interface_Compare function
returns A_EQUAL_TO_B. This is because the order in which those
interfaces are initially explored does not affect the final GADAG
produced by the algorithm described here. While only one of the
links will be added to the GADAG in the initial traversal, the other
parallel links will be added to the GADAG with the same direction
assigned during the procedure for assigning direction to UNDIRECTED
links described in Section 5.6. An implementation is free to apply
some additional criteria to break ties in interface ordering in this
situation, but that criteria is not specified here since it will not
affect the final GADAG produced by the algorithm.
The Interface_Compare function in Figure 14 relies on the
interface.metric and the interface.neighbor.mrt_node_id values to
order interfaces. The exact source of these values for different
IGPs (or flooding protocol in the case of ISIS-PCR
[I-D.farkas-isis-pcr]) and applications is specified in Figure 15.
The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS
provided here is normative. The metric and mrt_node_id values for
ISIS-PCR should be considered informational.
+--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id | metric of |
| protocol | of neighbor | interface |
| and | on interface | |
| application | | |
+--------------+-----------------------+-----------------------------+
| OSPFv2 for | 4 octet Neighbor | 2 octet Metric field |
| IP/LDP FRR | Router ID in | for corresponding |
| | Link ID field for | point-to-point link |
| | corresponding | in Router-LSA |
| | point-to-point link | |
| | in Router-LSA | |
+--------------+-----------------------+-----------------------------+
| OSPFv3 for | 4 octet Neighbor | 2 octet Metric field |
| IP/LDP FRR | Router ID field | for corresponding |
| | for corresponding | point-to-point link |
| | point-to-point link | in Router-LSA |
| | in Router-LSA | |
+--------------+-----------------------+-----------------------------+
| IS-IS for | 7 octet neighbor | 3 octet metric field |
| IP/LDP FRR | system ID and | in Extended IS |
| | pseudonode number | Reachability TLV #22 |
| | in Extended IS | or Multi-Topology |
| | Reachability TLV #22 | IS Neighbor TLV #222 |
| | or Multi-Topology | |
| | IS Neighbor TLV #222 | |
+--------------+-----------------------+-----------------------------+
| ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in |
| protection | created from 2 octet | SPB-Metric sub-TLV (type 29)|
| of traffic | Bridge Priority in | in Extended IS Reachability |
| in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology |
| networks | (type 1) carried in | Intermediate Systems |
| | MT-Capability TLV | TLV #222. In the case |
| | #144 and 6 octet | of asymmetric link metrics, |
| | neighbor system ID in | the larger link metric |
| | Extended IS | is used for both link |
| | Reachability TLV #22 | directions. |
| | or Multi-Topology | (informational) |
| | Intermediate Systems | |
| | TLV #222 | |
| | (informational) | |
+--------------+-----------------------+-----------------------------+
Figure 15: value of interface.neighbor.mrt_node_id and
interface.metric to be used for ranking interfaces, for different
flooding protocols and applications
The metrics are unsigned integers and MUST be compared as unsigned
integers. The results of mrt_node_id comparisons MUST be the same as
would be obtained by converting the mrt_node_ids to unsigned integers
using network byte order and performing the comparison as unsigned
integers. Also note that these values are only specified in the case
of point-to-point links. Therefore, in the case of IS-IS for IP/LDP
FRR, the pseudonode number (the 7th octet) will always be zero.
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
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 20, line 52 skipping to change at page 22, line 49
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 and not IGP-excluded if interface is (not MRT-ineligible and not IGP-excluded
and in area) and in area)
if ((interface.remote_node supports profile_id) and if ((interface.remote_node supports profile_id) and
(interface.remote_node.IN_MRT_ISLAND is FALSE)) (interface.remote_node.IN_MRT_ISLAND is FALSE))
interface.remote_node.IN_MRT_ISLAND = TRUE interface.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, interface.remote_node) add_to_tail(explore_list, interface.remote_node)
Figure 15: MRT Island Identification Figure 16: MRT Island Identification
5.2. 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. In
[I-D.atlas-ospf-mrt] and [I-D.li-isis-mrt], a mechanism is given for [I-D.ietf-ospf-mrt] and [I-D.ietf-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
significant impact on the lengths of the alternate paths computed. significant impact on the lengths of the alternate paths computed.
Therefore, it is RECOMMENDED that off-line analysis that considers Therefore, it is RECOMMENDED that off-line analysis that considers
the centrality of a router be used to help determine how good a the centrality of a router be used to help determine how good a
choice a particular router is for the role of GADAG root. choice a particular router is for the role of GADAG root.
5.3. 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 as unusable
using standard IGP mechanisms (see section 7 of using standard IGP mechanisms (see section 7 of
[I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability
considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be
desirable to administratively configure some interfaces as ineligible desirable to administratively configure some interfaces as ineligible
to carry MRT FRR traffic. This constraint MUST be consistently to carry MRT FRR traffic. This constraint MUST be consistently
flooded via the IGP [I-D.atlas-ospf-mrt] [I-D.li-isis-mrt] by the flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the
owner of the interface, so that links are clearly known to be MRT- owner of the interface, so that links are clearly known to be MRT-
ineligible and not explored or used in the MRT algorithm. In the ineligible and not explored or used in the MRT algorithm. In the
algorithm description, it is assumed that such links and nodes will algorithm description, it is assumed that such links and nodes will
not be explored or used, and no more discussion is given of this not be explored or used, and no more discussion is given of this
restriction. restriction.
5.4. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 5.5. 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
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 23, line 9 skipping to change at page 25, line 9
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 17.
Construct_Ear(x, Stack, intf, type) Construct_Ear(x, Stack, intf, ear_type)
ear_list = empty ear_list = empty
cur_node = intf.remote_node cur_node = intf.remote_node
cur_intf = intf cur_intf = intf
not_done = true not_done = true
while not_done while not_done
cur_intf.UNDIRECTED = false cur_intf.UNDIRECTED = false
cur_intf.OUTGOING = true cur_intf.OUTGOING = true
cur_intf.remote_intf.UNDIRECTED = false cur_intf.remote_intf.UNDIRECTED = false
cur_intf.remote_intf.INCOMING = true cur_intf.remote_intf.INCOMING = true
if cur_node.IN_GADAG is false if cur_node.IN_GADAG is false
cur_node.IN_GADAG = true cur_node.IN_GADAG = true
add_to_list_end(ear_list, cur_node) add_to_list_end(ear_list, cur_node)
if type is CHILD if ear_type is CHILD
cur_intf = cur_node.lowpoint_parent_intf cur_intf = cur_node.lowpoint_parent_intf
cur_node = cur_node.lowpoint_parent cur_node = cur_node.lowpoint_parent
else type must be NEIGHBOR else // ear_type must be NEIGHBOR
cur_intf = cur_node.dfs_parent_intf cur_intf = cur_node.dfs_parent_intf
cur_node = cur_node.dfs_parent cur_node = cur_node.dfs_parent
else else
not_done = false not_done = false
if (type is CHILD) and (cur_node is x) if (ear_type is CHILD) and (cur_node is x)
//x is a cut-vertex and the local root for // x is a cut-vertex and the local root for
//the block in which the ear is computed // the block in which the ear is computed
localroot = x localroot = x
else else
// Inherit local-root from the end of the ear // Inherit local-root from the end of the ear
localroot = cur_node.localroot localroot = cur_node.localroot
while ear_list is not empty while ear_list is not empty
y = remove_end_item_from_list(ear_list) y = remove_end_item_from_list(ear_list)
y.localroot = localroot y.localroot = localroot
push(Stack, y) push(Stack, y)
Construct_GADAG_via_Lowpoint(topology, root) Construct_GADAG_via_Lowpoint(topology, root)
root.IN_GADAG = true root.IN_GADAG = true
root.localroot = root root.localroot = None
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)
foreach interface intf of x foreach interface intf of x
if ((intf.remote_node.IN_GADAG == false) and if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is x)) (intf.remote_node.dfs_parent is x))
Construct_Ear(x, Stack, intf, CHILD) Construct_Ear(x, Stack, intf, CHILD)
foreach interface intf of x foreach interface intf of x
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, root) Construct_GADAG_via_Lowpoint(topology, root)
Figure 16: Low-point Inheritance GADAG algorithm Figure 17: Low-point Inheritance GADAG algorithm
5.5. 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 algorithm 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.
skipping to change at page 24, line 50 skipping to change at page 26, line 50
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 total ordering. Any UNDIRECTED links that connect to a root upon the total ordering. Any UNDIRECTED links that connect to a root
of a block from within that block are assigned a direction INCOMING of a block from within that block are assigned a direction INCOMING
to that root. The exact details of this whole process are captured to that root. The exact details of this whole process are captured
in Figure 17 in Figure 18
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
skipping to change at page 25, line 35 skipping to change at page 27, line 35
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
Initialize working_list to empty Initialize working_list to empty
Initialize topo_order_list to empty Initialize topo_order_list to empty
add_to_list_end(working_list, root) add_to_list_end(working_list, root)
while working_list is not empty while working_list is not empty
y = remove_start_item_from_list(working_list) y = remove_start_item_from_list(working_list)
add_to_list_end(topo_order_list, y) add_to_list_end(topo_order_list, y)
foreach interface i of y foreach interface i of y
if (i.OUTGOING) and (not i.TEMP_UNUSABLE) if (i.OUTGOING) and (not i.TEMP_UNUSABLE)
i.remote_node.unvisited -= 1 i.remote_node.unvisited -= 1
if i.remote_node.unvisited is 0 if i.remote_node.unvisited is 0
add_to_list_end(working_list, i.remote_node) add_to_list_end(working_list, i.remote_node)
next_topo_order = 1 next_topo_order = 1
while topo_order_list is not empty while topo_order_list is not empty
y = remove_start_item_from_list(topo_order_list) y = remove_start_item_from_list(topo_order_list)
y.topo_order = next_topo_order y.topo_order = next_topo_order
next_topo_order += 1 next_topo_order += 1
Set_Block_Root_Incoming_Links(topo, root, CLEAR) Set_Block_Root_Incoming_Links(topo, root, CLEAR)
Add_Undirected_Links(topo, root) Add_Undirected_Links(topo, root)
Run_Topological_Sort_GADAG(topo, root) Run_Topological_Sort_GADAG(topo, root)
foreach node x in topo foreach node x in topo
foreach interface i of x foreach interface i of x
if i.UNDIRECTED if i.UNDIRECTED
if x.topo_order < i.remote_node.topo_order if x.topo_order < i.remote_node.topo_order
i.OUTGOING = true i.OUTGOING = true
i.UNDIRECTED = false i.UNDIRECTED = false
i.remote_intf.INCOMING = true i.remote_intf.INCOMING = true
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
else else
i.INCOMING = true i.INCOMING = true
i.UNDIRECTED = false i.UNDIRECTED = false
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 18: 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
for proxy-nodes and how the appropriate alternate next-hops are for proxy-nodes and how the appropriate alternate next-hops are
selected is given in Section 5.8. selected is given in Section 5.9.
5.6. Compute MRT next-hops 5.7. 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 will reuse the common GADAG and root. However, in this algorithm, we will reuse the common GADAG and
find not only the one pair of MRTs rooted at the GADAG root with it, find not only the one pair of MRTs rooted at the GADAG root with it,
but find a pair rooted at each node. This is useful since it is but find a pair rooted at each node. This is useful since it is
significantly faster to compute. significantly faster to compute.
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.
As usual, the two basic ideas will be discussed assuming the network As usual, the two basic ideas will be discussed assuming the network
is two-connected. The generalization to multiple blocks is discussed is two-connected. The generalization to multiple blocks is discussed
in Section 5.6.4. The full algorithm is given in Section 5.6.5. in Section 5.7.4. The full algorithm is given in Section 5.7.5.
5.6.1. MRT next-hops to all nodes partially ordered with respect to the 5.7.1. MRT next-hops to all nodes partially ordered with respect to the
computing node computing node
To find two node-disjoint paths from the computing router X to any To find two node-disjoint paths from the computing router X to any
node Y, depends upon whether Y >> X or Y << X. As shown in node Y, depends upon whether Y >> X or Y << X. As shown in
Figure 18, if Y >> X, then there is an increasing path that goes from Figure 19, if Y >> X, then there is an increasing path that goes from
X to Y without crossing R; this contains nodes in the interval [X,Y]. X to Y without crossing R; this contains nodes in the interval [X,Y].
There is also a decreasing path that decreases towards R and then There is also a decreasing path that decreases towards R and then
decreases from R to Y; this contains nodes in the interval decreases from R to Y; this contains nodes in the interval
[X,R-small] or [R-great,Y]. The two paths cannot have common nodes [X,R-small] or [R-great,Y]. The two paths cannot have common nodes
other than X and Y. other than X and Y.
[Y]<---(Cloud 2)<--- [X] [Y]<---(Cloud 2)<--- [X]
| ^ | ^
| | | |
V | V |
(Cloud 3)--->[R]--->(Cloud 1) (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 2->Y MRT-Blue path: X->Cloud 2->Y
MRT-Red path: X->Cloud 1->R->Cloud 3->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y
Figure 18: Y >> X Figure 19: Y >> X
Similar logic applies if Y << X, as shown in Figure 19. In this Similar logic applies if Y << X, as shown in Figure 20. In this
case, the increasing path from X increases to R and then increases case, the increasing path from X increases to R and then increases
from R to Y to use nodes in the intervals [X,R-great] and [R-small, from R to Y to use nodes in the intervals [X,R-great] and [R-small,
Y]. The decreasing path from X reaches Y without crossing R and uses Y]. The decreasing path from X reaches Y without crossing R and uses
nodes in the interval [Y,X]. nodes in the interval [Y,X].
[X]<---(Cloud 2)<--- [Y] [X]<---(Cloud 2)<--- [Y]
| ^ | ^
| | | |
V | V |
(Cloud 3)--->[R]--->(Cloud 1) (Cloud 3)--->[R]--->(Cloud 1)
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 20: Y << X
5.6.2. MRT next-hops to all nodes not partially ordered with respect to 5.7.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 21. 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.
(Cloud 6)<---[Y]<---(Cloud 5)<------------| (Cloud 6)<---[Y]<---(Cloud 5)<------------|
| | | |
| | | |
V | V |
[G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H] [G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H]
^ | ^ |
| | | |
| | | |
(Cloud 3)<---[X]<---(Cloud 2)<-----------| (Cloud 3)<---[X]<---(Cloud 2)<-----------|
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 21: 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.7.3. Computing Redundant Tree next-hops in a 2-connected Graph
The basic ideas for computing RT next-hops in a 2-connected graph The basic ideas for computing RT next-hops in a 2-connected graph
were given in Section 5.6.1 and Section 5.6.2. Given these two were given in Section 5.7.1 and Section 5.7.2. Given these two
ideas, how can we find the trees? ideas, how can we find the trees?
If some node X only wants to find the next-hops (which is usually the If some node X only wants to find the next-hops (which is usually the
case for IP networks), it is enough to find which nodes are greater 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.
than SPF could safely be used instead where one traversal takes the
links in their given directions and the other reverses the links' In principle, an traversal method other than SPF could be used to
directions.) traverse the GADAG in the process of determining blue and red next-
hops that result in maximally redundant trees. This will be the case
as long as one traversal uses the links in the direction specified by
the GADAG and the other traversal uses the links in the direction
opposite of that specified by the GADAG. However, a different
traversal algorithm will generally result in different blue and red
next-hops. Therefore, the algorithm specified here requires the use
of SPF to traverse the GADAG to generate MRT blue and red next-hops,
as described below.
An increasing-SPF rooted at X and not exploring links from the root 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. A 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-
skipping to change at page 30, line 16 skipping to change at page 32, line 24
| | | | ^ | | | | | ^ |
| | | V | | | | | V | |
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 22
As an example consider the situation depicted in Figure 21. Node C As an example consider the situation depicted in Figure 22. Node C
runs an increasing-SPF and a decreasing-SPF on the ADAG. The runs an increasing-SPF and a decreasing-SPF on the ADAG. The
increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A
and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was
reached on the increasing path through D. And the MRT-Red next-hop reached on the increasing path through D. And the MRT-Red next-hop
towards E is B, since R was reached on the decreasing path through B. towards E is B, since R was reached on the decreasing path through B.
Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, 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 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 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 ordered less than B, A and R), ensuring that a packet on MRT-Red will
use path C-B-A-R-E. use path C-B-A-R-E.
C can determine the next-hops towards F as well. Since F is not C can determine the next-hops towards F as well. Since F is not
ordered with respect to C, the MRT-Blue next-hop is the decreasing ordered with respect to C, the MRT-Blue next-hop is the decreasing
one towards R (which is B) and the MRT-Red next-hop is the increasing one towards R (which is B) and the MRT-Red next-hop is the increasing
one towards R (which is D). Since F>>B, for its MRT-Blue next-hop one towards R (which is D). Since F>>B, for its MRT-Blue next-hop
towards F, B will use the real increasing next-hop towards F. So a towards F, B will use the real increasing next-hop towards F. So a
packet forwarded to B on MRT-Blue will get to F on path C-B-F. packet forwarded to B on MRT-Blue will get to F on path C-B-F.
Similarly, D will use the real decreasing next-hop towards F as its 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. MRT-Red next-hop, a packet on MRT-Red will use path C-D-F.
5.6.4. Generalizing for a graph that isn't 2-connected 5.7.4. Generalizing for a graph that isn't 2-connected
If a graph isn't 2-connected, then the basic approach given in 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.7.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:
1. Only nodes in a common block with X should be explored in the 1. Only nodes in a common block with X should be explored in the
increasing-SPF and decreasing-SPF. increasing-SPF and decreasing-SPF.
skipping to change at page 31, line 27 skipping to change at page 33, line 35
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 MRT-Blue) 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.7.5.
5.6.5. Complete Algorithm to Compute MRT Next-Hops 5.7.5. Complete Algorithm to Compute MRT Next-Hops
The complete algorithm to compute MRT Next-Hops for a particular The complete algorithm to compute MRT Next-Hops for a particular
router X is given in Figure 22. In addition to computing the MRT- router X is given in Figure 23. In addition to computing the MRT-
Blue next-hops and MRT-Red next-hops used by X to reach each node Y, Blue next-hops and MRT-Red next-hops used by X to reach each node Y,
the algorithm also stores an "order_proxy", which is the proper cut- the algorithm also stores an "order_proxy", which is the proper cut-
vertex to reach Y if it is outside the block, and which is used later vertex to reach Y if it is outside the block, and which is used later
in deciding whether the MRT-Blue or the MRT-Red can provide an in deciding whether the MRT-Blue or the MRT-Red can provide an
acceptable alternate for a particular primary next-hop. acceptable alternate for a particular primary next-hop.
In_Common_Block(x, y) In_Common_Block(x, y)
if (((x.localroot is y.localroot) and (x.block_id is y.block_id)) if ( (x.block_id is y.block_id))
or (x is y.localroot) or (y is x.localroot)) or (x is y.localroot) or (y is x.localroot) )
return true return true
return false return false
Store_Results(y, direction, spf_root, store_nhs) Store_Results(y, direction)
if direction is FORWARD if direction is FORWARD
y.higher = true y.higher = true
if store_nhs y.blue_next_hops = y.next_hops
y.blue_next_hops = y.next_hops if direction is REVERSE
if direction is REVERSE y.lower = true
y.lower = true y.red_next_hops = y.next_hops
if store_nhs
y.red_next_hops = y.next_hops
SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs) SPF_No_Traverse_Root(spf_root, block_root, direction)
Initialize spf_heap to empty Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty Initialize nodes' spf_metric to infinity and next_hops to empty
spf_root.spf_metric = 0 spf_root.spf_metric = 0
insert(spf_heap, spf_root) insert(spf_heap, spf_root)
while (spf_heap is not empty) while (spf_heap is not empty)
min_node = remove_lowest(spf_heap) min_node = remove_lowest(spf_heap)
Store_Results(min_node, direction, spf_root, store_nhs) Store_Results(min_node, direction)
if ((min_node is spf_root) or (min_node is not block_root)) if ((min_node is spf_root) or (min_node is not block_root))
foreach interface intf of min_node foreach interface intf of min_node
if (((direction is FORWARD) and intf.OUTGOING) or if ( ( ((direction is FORWARD) and intf.OUTGOING) or
((direction is REVERSE) and intf.INCOMING) and ((direction is REVERSE) and intf.INCOMING) )
In_Common_Block(spf_root, intf.remote_node)) and In_Common_Block(spf_root, intf.remote_node) )
path_metric = min_node.spf_metric + intf.metric path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric intf.remote_node.spf_metric = path_metric
if min_node is spf_root if min_node is spf_root
intf.remote_node.next_hops = make_list(intf) intf.remote_node.next_hops = make_list(intf)
else else
intf.remote_node.next_hops = min_node.next_hops intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node) insert_or_update(spf_heap, intf.remote_node)
else if path_metric is intf.remote_node.spf_metric else if path_metric is intf.remote_node.spf_metric
if min_node is spf_root if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf) add_to_list(intf.remote_node.next_hops, intf)
else else
add_list_to_list(intf.remote_node.next_hops, add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops) min_node.next_hops)
SetEdge(y) SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty if y.blue_next_hops is empty and y.red_next_hops is empty
if (y.local_root != y) { if (y.localroot != y)
SetEdge(y.localroot) SetEdge(y.localroot)
} y.blue_next_hops = y.localroot.blue_next_hops
y.blue_next_hops = y.localroot.blue_next_hops y.red_next_hops = y.localroot.red_next_hops
y.red_next_hops = y.localroot.red_next_hops y.order_proxy = y.localroot.order_proxy
y.order_proxy = y.localroot.order_proxy
Compute_MRT_NextHops(x, root) Compute_MRT_NextHops(x, root)
foreach node y foreach node y
y.higher = y.lower = false y.higher = y.lower = false
clear y.red_next_hops and y.blue_next_hops clear y.red_next_hops and y.blue_next_hops
y.order_proxy = y y.order_proxy = y
SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE) SPF_No_Traverse_Root(x, x.localroot, FORWARD)
SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE) SPF_No_Traverse_Root(x, x.localroot, REVERSE)
// red and blue next-hops are stored to x.localroot as different // red and blue next-hops are stored to x.localroot as different
// paths are found via the SPF and reverse-SPF. // paths are found via the SPF and reverse-SPF.
// Similarly any nodes whose local-root is x will have their // Similarly any nodes whose local-root is x will have their
// red_next_hops and blue_next_hops already set. // red_next_hops and blue_next_hops already set.
// Handle nodes in the same block that aren't the local-root // Handle nodes in the same block that aren't the local-root
foreach node y foreach node y
if (y.IN_MRT_ISLAND and (y is not x) and if (y.IN_MRT_ISLAND and (y is not x) and
(y.localroot is x.localroot) and (y.block_id is x.block_id) )
((y is x.localroot) or (x is y.localroot) or if y.higher
(y.block_id is x.block_id))) y.red_next_hops = x.localroot.red_next_hops
if y.higher else if y.lower
y.red_next_hops = x.localroot.red_next_hops y.blue_next_hops = x.localroot.blue_next_hops
else if y.lower else
y.blue_next_hops = x.localroot.blue_next_hops y.blue_next_hops = x.localroot.red_next_hops
else y.red_next_hops = x.localroot.blue_next_hops
y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_next_hops
// Inherit next-hops and order_proxies to other components // Inherit next-hops and order_proxies to other components
if x is not root if x is not root
root.blue_next_hops = x.localroot.blue_next_hops root.blue_next_hops = x.localroot.blue_next_hops
root.red_next_hops = x.localroot.red_next_hops root.red_next_hops = x.localroot.red_next_hops
root.order_proxy = x.localroot root.order_proxy = x.localroot
foreach node y foreach node y
if (y is not root) and (y is not x) and y.IN_MRT_ISLAND if (y is not root) and (y is not x) and y.IN_MRT_ISLAND
SetEdge(y) SetEdge(y)
max_block_id = 0 max_block_id = 0
Assign_Block_ID(root, max_block_id) Assign_Block_ID(root, max_block_id)
Compute_MRT_NextHops(x, root) Compute_MRT_NextHops(x, root)
Figure 22 Figure 23
5.7. Identify MRT alternates 5.8. 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
next hop or to use the MRT-Red next-hops. The algorithm is given in next hop or to use the MRT-Red next-hops. The algorithm is given in
Figure 23 and discussed afterwards. Figure 24 and discussed afterwards.
Select_Alternates_Internal(S, D, F, primary_intf, Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order) D_lower, D_higher, D_topo_order)
//When D==F, we can do only link protection //When D==F, we can do only link protection
if ((D is F) or (D.order_proxy is F)) if ((D is F) or (D.order_proxy is F))
if an MRT doesn't use primary_intf if an MRT doesn't use primary_intf
indicate alternate is not node-protecting indicate alternate is not node-protecting
return that MRT color return that MRT color
else // parallel links are cut-links else // parallel links are cut-links
skipping to change at page 34, line 42 skipping to change at page 36, line 44
return USE_BLUE return USE_BLUE
if (F.lower and F.higher) if (F.lower and F.higher)
if D_lower if D_lower
return USE_RED return USE_RED
else if D_higher else if D_higher
return USE_BLUE return USE_BLUE
else else
if primary_intf.OUTGOING and primary_intf.INCOMING if primary_intf.OUTGOING and primary_intf.INCOMING
return AVOID_LINK_ON_BLUE return AVOID_LINK_ON_BLUE
if primary_intf.OUTGOING is true if primary_intf.OUTGOING
return USE_BLUE return USE_BLUE
if primary_intf.INCOMING is true if primary_intf.INCOMING
return USE_RED return USE_RED
if D_higher if D_higher
if F.higher if F.higher
if F.topo_order < D_topo_order if F.topo_order < D_topo_order
return USE_RED return USE_RED
else else
return USE_BLUE return USE_BLUE
else if F.lower else if F.lower
return USE_BLUE return USE_BLUE
else else
// F and S are neighbors so either F << S or F >> S // F and S are neighbors so either F << S or F >> S
else if D_lower else if D_lower
if F.higher if F.higher
return USE_RED return USE_RED
else if F.lower else if F.lower
if F.topo_order < D_topo_order if F.topo_order < D_topo_order
return USE_RED return USE_RED
else else
return USE_BLUE return USE_BLUE
else else
// F and S are neighbors so either F << S or F >> S // F and S are neighbors so either F << S or F >> S
else // D and S not ordered else // D and S not ordered
if F.lower if F.lower
return USE_RED return USE_RED
else if F.higher else if F.higher
return USE_BLUE return USE_BLUE
else else
// F and S are neighbors so either F << S or F >> S // F and S are neighbors so either F << S or F >> S
Select_Alternates(S, D, F, primary_intf) Select_Alternates(S, D, F, primary_intf)
if D.order_proxy is not D if D.order_proxy is not D
D_lower = D.order_proxy.lower D_lower = D.order_proxy.lower
D_higher = D.order_proxy.higher D_higher = D.order_proxy.higher
D_topo_order = D.order_proxy.topo_order D_topo_order = D.order_proxy.topo_order
else else
D_lower = D.lower D_lower = D.lower
D_higher = D.higher D_higher = D.higher
D_topo_order = D.topo_order D_topo_order = D.topo_order
return Select_Alternates_Internal(S, D, F, primary_intf, return Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order) D_lower, D_higher, D_topo_order)
Figure 23 Figure 24
If either D>>S>>F or D<<S<<F holds true, the situation is simple: in If either D>>S>>F or D<<S<<F holds true, the situation is simple: in
the first case we should choose the increasing Blue next-hop, in the the first case we should choose the increasing Blue next-hop, in the
second case, the decreasing Red next-hop is the right choice. second case, the decreasing Red next-hop is the right choice.
However, when both D and F are greater than S the situation is not so However, when both D and F are greater than S the situation is not so
simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii) simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii)
F and D are not ordered. In the first case, we should choose the F and D are not ordered. In the first case, we should choose the
path towards D along the Blue tree. In contrast, in case (ii) the path towards D along the Blue tree. In contrast, in case (ii) the
Red path towards the root and then to D would be the solution. Red path towards the root and then to D would be the solution.
skipping to change at page 36, line 47 skipping to change at page 38, line 50
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 Finally, there is the case where D is also F. In this case, only
link protection is possible. The MRT that doesn't use the indicated 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 25 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
than H, so we should select the decreasing path towards the root. than H, so we should select the decreasing path towards the root.
If, however, the destination were instead J, we must find that If, however, the destination were instead J, we must find that
H.topo_order>J.topo_order, so we must choose the increasing Blue H.topo_order>J.topo_order, so we must choose the increasing Blue
next-hop to J, which is I. In the case, when instead the destination next-hop to J, which is I. In the case, when instead the destination
is C, we find that we need to first decrease to avoid using H, so the is C, we find that we need to first decrease to avoid using H, so the
Blue, first decreasing then increasing, path is selected. Blue, first decreasing then increasing, path is selected.
[E]<-[D]<-[H]<-[J] [E]<-[D]<-[H]<-[J]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[R] [C] [G]->[I] [R] [C] [G]->[I]
skipping to change at page 37, line 19 skipping to change at page 39, line 21
Blue, first decreasing then increasing, path is selected. Blue, first decreasing then increasing, path is selected.
[E]<-[D]<-[H]<-[J] [E]<-[D]<-[H]<-[J]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[R] [C] [G]->[I] [R] [C] [G]->[I]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[A]->[B]->[F]---| [A]->[B]->[F]---|
(a) (a)ADAG rooted at R for
a 2-connected graph a 2-connected graph
Figure 24 Figure 25
5.8. Finding FRR Next-Hops for Proxy-Nodes 5.9. Finding FRR Next-Hops for Proxy-Nodes
As discussed in Section 10.2 of As discussed in Section 10.2 of
[I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT-
Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy-
nodes. An example case is for a router that is not part of that nodes. An example case is for a router that is not part of that
local MRT Island, when there is only partial MRT support in the local MRT Island, when there is only partial MRT support in the
domain. domain.
A first incorrect and naive approach to handling proxy-nodes, which A first incorrect and naive approach to handling proxy-nodes, which
cannot be transited, is to simply add these proxy-nodes to the graph cannot be transited, is to simply add these proxy-nodes to the graph
skipping to change at page 39, line 6 skipping to change at page 41, line 6
4 A<<S<<B Red to A Blue to B 4 A<<S<<B Red to A Blue to B
5 A<<S Red to A Blue to R S not ordered w/ B 5 A<<S Red to A Blue to R S not ordered w/ B
6 S<<B Red to R Blue to B S not ordered w/ A 6 S<<B Red to R Blue to B S not ordered w/ A
7 Otherwise Red to R Blue to R S not ordered w/ A+B 7 Otherwise Red to R Blue to R S not ordered w/ A+B
These rules are realized in the following pseudocode where P is the These rules are realized in the following pseudocode where P is the
proxy-node, X and Y are the nodes that P is attached to, and S is the proxy-node, X and Y are the nodes that P is attached to, and S is the
computing router: computing router:
Select_Proxy_Node_NHs(P, S, X, Y) Select_Proxy_Node_NHs(P, S, X, Y)
if (X.order_proxy.topo_order < Y.order_proxy.topo_order) if (X.order_proxy.topo_order < Y.order_proxy.topo_order)
//This fits even if X.order_proxy=S.local_root //This fits even if X.order_proxy=S.local_root
A=X.order_proxy A=X.order_proxy
B=Y.order_proxy B=Y.order_proxy
else else
A=Y.order_proxy A=Y.order_proxy
B=X.order_proxy B=X.order_proxy
if (S==A.local_root) if (S==A.local_root)
P.blue_next_hops = A.blue_next_hops P.blue_next_hops = A.blue_next_hops
P.red_next_hops = B.red_next_hops P.red_next_hops = B.red_next_hops
return return
if (A.higher) if (A.higher)
P.blue_next_hops = A.blue_next_hops P.blue_next_hops = A.blue_next_hops
P.red_next_hops = R.red_next_hops P.red_next_hops = R.red_next_hops
return return
if (B.lower) if (B.lower)
P.blue_next_hops = R.blue_next_hops P.blue_next_hops = R.blue_next_hops
P.red_next_hops = B.red_next_hops P.red_next_hops = B.red_next_hops
return return
if (A.lower && B.higher) if (A.lower && B.higher)
P.blue_next_hops = A.red_next_hops P.blue_next_hops = A.red_next_hops
P.red_next_hops = B.blue_next_hops P.red_next_hops = B.blue_next_hops
return return
if (A.lower) if (A.lower)
P.blue_next_hops = R.red_next_hops
P.red_next_hops = B.blue_next_hops
return
if (B.higher)
P.blue_next_hops = A.red_next_hops
P.red_next_hops = R.blue_next_hops
return
P.blue_next_hops = R.red_next_hops P.blue_next_hops = R.red_next_hops
P.red_next_hops = B.blue_next_hops
return
if (B.higher)
P.blue_next_hops = A.red_next_hops
P.red_next_hops = R.blue_next_hops P.red_next_hops = R.blue_next_hops
return return
P.blue_next_hops = R.red_next_hops
P.red_next_hops = R.blue_next_hops
return
After finding the the red and the blue 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, as long as 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
skipping to change at page 40, line 19 skipping to change at page 42, line 19
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 26
6. MRT Lowpoint Algorithm: Next-hop conformance 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.7 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 >> X, 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].
skipping to change at page 41, line 23 skipping to change at page 43, line 23
they did not provide significant differences in the path lenghts for they did not provide significant differences in the path lenghts for
the alternatives. This section does not focus on that analysis or the alternatives. This section does not focus on that analysis or
the decision to use the MRT Lowpoint algorithm as the default MRT the decision to use the MRT Lowpoint algorithm as the default MRT
algorithm; it has the lowest computational and storage requirements algorithm; it has the lowest computational and storage requirements
and gave comparable results. and gave comparable results.
Since this document defines the MRT Lowpoint algorithm for use in Since this document defines the MRT Lowpoint algorithm for use in
fast-reroute applications, it is useful to compare MRT and Remote LFA fast-reroute applications, it is useful to compare MRT and Remote LFA
[I-D.ietf-rtgwg-remote-lfa]. This section compares MRT and remote [I-D.ietf-rtgwg-remote-lfa]. This section compares MRT and remote
LFA for IP Fast Reroute in 19 service provider network topologies, LFA for IP Fast Reroute in 19 service provider network topologies,
focusing on coverage and alternate path length. Figure 26 shows the focusing on coverage and alternate path length. Figure 27 shows the
node-protecting coverage provided by local LFA (LLFA), remote LFA node-protecting coverage provided by local LFA (LLFA), remote LFA
(RLFA), and MRT against different failure scenarios in these (RLFA), and MRT against different failure scenarios in these
topologies. The coverage values are calculated as the percentage of topologies. The coverage values are calculated as the percentage of
source-destination pairs protected by the given IPFRR method relative source-destination pairs protected by the given IPFRR method relative
to those protectable by optimal routing, against the same failure to those protectable by optimal routing, against the same failure
modes. More details on alternate selection policies used for this modes. More details on alternate selection policies used for this
analysis are described later in this section. analysis are described later in this section.
+------------+-----------------------------+ +------------+-----------------------------+
| Topology | percentage of failure | | Topology | percentage of failure |
skipping to change at page 42, line 33 skipping to change at page 44, line 33
| T212 | 59 | 63 | 100 | | T212 | 59 | 63 | 100 |
| T213 | 84 | 84 | 100 | | T213 | 84 | 84 | 100 |
| T214 | 68 | 78 | 100 | | T214 | 68 | 78 | 100 |
| T215 | 84 | 88 | 100 | | T215 | 84 | 88 | 100 |
| T216 | 43 | 59 | 100 | | T216 | 43 | 59 | 100 |
| T217 | 78 | 88 | 100 | | T217 | 78 | 88 | 100 |
| T218 | 72 | 75 | 100 | | T218 | 72 | 75 | 100 |
| T219 | 78 | 84 | 100 | | T219 | 78 | 84 | 100 |
+------------+---------+---------+---------+ +------------+---------+---------+---------+
Figure 26 Figure 27
For the topologies analyzed here, LLFA is able to provide node- For the topologies analyzed here, LLFA is able to provide node-
protecting coverage ranging from 37% to 95% of the source-destination 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 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 addition to LLFA is generally able to increase the node-protecting
coverage. The percentage of node-protecting coverage with RLFA is coverage. The percentage of node-protecting coverage with RLFA is
provided in the column labeled NP_RLFA, ranges from 59% to 98% for provided in the column labeled NP_RLFA, ranges from 59% to 98% for
these topologies. The node-protecting coverage provided by MRT is these topologies. The node-protecting coverage provided by MRT is
100% since MRT is able to provide protection for any source- 100% since MRT is able to provide protection for any source-
destination pair for which a path still exists after the failure. destination pair for which a path still exists after the failure.
We would also like to measure the quality of the alternate paths We would also like to measure the quality of the alternate paths
produced by these different IPFRR methods. An obvious approach is to produced by these different IPFRR methods. An obvious approach is to
take an average of the alternate path costs over all source- take an average of the alternate path costs over all source-
destination pairs and failure modes. However, this presents a destination pairs and failure modes. However, this presents a
problem, which we will illustrate by presenting an example of results problem, which we will illustrate by presenting an example of results
for one topology using this approach ( Figure 27). In this table, for one topology using this approach ( Figure 28). In this table,
the average relative path length is the alternate path length for the the average relative path length is the alternate path length for the
IPFRR method divided by the optimal alternate path length, averaged IPFRR method divided by the optimal alternate path length, averaged
over all source-destination pairs and failure modes. The first three over all source-destination pairs and failure modes. The first three
columns of data in the table give the path length calculated from the 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 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 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 NP_RLFA alternates are on average 78 and 66 times longer than the
path lengths for optimal alternates. The metric-based path lengths path lengths for optimal alternates. The metric-based path lengths
for MRT alternates are on average 14 times longer than for optimal for MRT alternates are on average 14 times longer than for optimal
alternates. alternates.
skipping to change at page 43, line 23 skipping to change at page 45, line 23
+--------+------------------------------------------------+ +--------+------------------------------------------------+
| | average relative alternate path length | | | average relative alternate path length |
| |-----------------------+------------------------+ | |-----------------------+------------------------+
|Topology| IGP metric | hopcount | |Topology| IGP metric | hopcount |
| |-----------------------+------------------------+ | |-----------------------+------------------------+
| |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT |
+--------+--------+--------+-----+--------+--------+------+ +--------+--------+--------+-----+--------+--------+------+
| T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 |
+--------+--------+--------+-----+--------+--------+------+ +--------+--------+--------+-----+--------+--------+------+
Figure 27 Figure 28
The network topology represented by T208 uses values of 10, 100, and The network topology represented by T208 uses values of 10, 100, and
1000 as IGP costs, so small deviations from the optimal alternate 1000 as IGP costs, so small deviations from the optimal alternate
path can result in large differences in relative path length. LLFA, 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 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 be chosen independent of the cost of the link. This can easily
result in an alternate using a link with cost 1000, which introduces result in an alternate using a link with cost 1000, which introduces
noise into the path length measurement. In the case of T208, the noise into the path length measurement. In the case of T208, the
adverse effects of using metric-based path lengths is obvious. adverse effects of using metric-based path lengths is obvious.
However, we have observed that the metric-based path length However, we have observed that the metric-based path length
introduces noise into alternate path length measurements in several introduces noise into alternate path length measurements in several
other topologies as well. For this reason, we have opted to measure other topologies as well. For this reason, we have opted to measure
the alternate path length using hopcount. While IGP metrics may be the alternate path length using hopcount. While IGP metrics may be
adjusted by the network operator for a number of reasons (e.g. adjusted by the network operator for a number of reasons (e.g.
traffic engineering), the hopcount is a fairly stable measurement of traffic engineering), the hopcount is a fairly stable measurement of
path length. As shown in the last three columns of Figure 27, the path length. As shown in the last three columns of Figure 28, the
hopcount-based alternate path lengths for topology T208 are fairly hopcount-based alternate path lengths for topology T208 are fairly
well-behaved. well-behaved.
Figure 28, Figure 29, Figure 30, and Figure 31 present the hopcount- Figure 29, Figure 30, Figure 31, and Figure 32 present the hopcount-
based path length results for the 19 topologies examined. The based path length results for the 19 topologies examined. The
topologies in the four tables are grouped based on the size of the topologies in the four tables are grouped based on the size of the
topologies, as measured by the number of nodes, with Figure 28 having topologies, as measured by the number of nodes, with Figure 29 having
the smallest topologies and Figure 31 having the largest topologies. the smallest topologies and Figure 32 having the largest topologies.
Instead of trying to represent the path lengths of a large set of Instead of trying to represent the path lengths of a large set of
alternates with a single number, we have chosen to present a alternates with a single number, we have chosen to present a
histogram of the path lengths for each IPFRR method and alternate histogram of the path lengths for each IPFRR method and alternate
selection policy studied. The first eight colums of data represent selection policy studied. The first eight colums of data represent
the percentage of failure scenarios protected by an alternate N hops the percentage of failure scenarios protected by an alternate N hops
longer than the primary path, with the first column representing an 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 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 through the eighth column respresenting an alternate 14 or 15 hops
longer than the primary path. The last column in the table gives the longer than the primary path. The last column in the table gives the
percentage of failure scenarios for which there is no alternate less percentage of failure scenarios for which there is no alternate less
skipping to change at page 45, line 50 skipping to change at page 47, line 50
| MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T205(avg primary hops=3.4) | | | | | | | | | | | T205(avg primary hops=3.4) | | | | | | | | | |
| OPTIMAL | 92| 8| | | | | | | | | OPTIMAL | 92| 8| | | | | | | |
| NP_LLFA | 89| 3| | | | | | | 8| | NP_LLFA | 89| 3| | | | | | | 8|
| NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7|
| NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | |
| MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 28 Figure 29
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 46, line 50 skipping to change at page 48, line 50
| MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T210(avg primary hops=2.5) | | | | | | | | | | | T210(avg primary hops=2.5) | | | | | | | | | |
| OPTIMAL | 95| 4| 1| | | | | | | | OPTIMAL | 95| 4| 1| | | | | | |
| NP_LLFA | 94| 1| | | | | | | 5| | NP_LLFA | 94| 1| | | | | | | 5|
| NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2|
| NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | |
| MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 29 Figure 30
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 47, line 50 skipping to change at page 49, line 50
| MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T215(avg primary hops=4.8) | | | | | | | | | | | T215(avg primary hops=4.8) | | | | | | | | | |
| OPTIMAL | 73| 27| | | | | | | | | OPTIMAL | 73| 27| | | | | | | |
| NP_LLFA | 73| 11| | | | | | | 16| | NP_LLFA | 73| 11| | | | | | | 16|
| NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12|
| NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | |
| MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 30 Figure 31
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 48, line 43 skipping to change at page 50, line 43
| MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T219(avg primary hops=7.7) | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | |
| OPTIMAL | 77| 15| 5| 1| 1| | | | | | OPTIMAL | 77| 15| 5| 1| 1| | | | |
| NP_LLFA | 72| 5| | | | | | | 22| | NP_LLFA | 72| 5| | | | | | | 22|
| NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16|
| NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| | 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| | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 31 Figure 32
In the preceding analysis, the following procedure for selecting an In the preceding analysis, the following procedure for selecting an
RLFA was used. Nodes were ordered with respect to distance from the 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 source and checked for membership in Q and P-space. The first node
to satisfy this condition was selected as the RLFA. More to satisfy this condition was selected as the RLFA. More
sophisticated methods to select node-protecting RLFAs is an area of sophisticated methods to select node-protecting RLFAs is an area of
active research. active research.
The analysis presented above uses the MRT Lowpoint Algorithm defined The analysis presented above uses the MRT Lowpoint Algorithm defined
in this specification with a common GADAG root. The particular in this specification with a common GADAG root. The particular
skipping to change at page 49, line 24 skipping to change at page 51, line 24
chosen based on the GADAG Root Selection Priority advertised by each chosen based on the GADAG Root Selection Priority advertised by each
router, the values of which would be determined off-line. router, the values of which would be determined off-line.
In order to measure how sensitive the MRT alternate path lengths are In order to measure how sensitive the MRT alternate path lengths are
to the choice of common GADAG root, we performed the same analysis to the choice of common GADAG root, we performed the same analysis
using different choices of GADAG root. All of the nodes in the using different choices of GADAG root. All of the nodes in the
network were ordered with respect to the node centrality as computed network were ordered with respect to the node centrality as computed
above. Nodes were chosen at the 0th, 25th, and 50th percentile with above. Nodes were chosen at the 0th, 25th, and 50th percentile with
respect to the centrality ordering, with 0th percentile being the respect to the centrality ordering, with 0th percentile being the
most central node. The distribution of alternate path lengths for most central node. The distribution of alternate path lengths for
those three choices of GADAG root are shown in Figure 32 for a subset those three choices of GADAG root are shown in Figure 33 for a subset
of the 19 topologies (chosen arbitrarily). The third row for each of the 19 topologies (chosen arbitrarily). The third row for each
topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the
results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth
rows show the alternate path length distibution for the 25th and 50th rows show the alternate path length distibution for the 25th and 50th
percentile choice for GADAG root. One can see some impact on the percentile choice for GADAG root. One can see some impact on the
path length distribution with the less central choice of GADAG root path length distribution with the less central choice of GADAG root
resulting in longer path lenghths. resulting in longer path lenghths.
We also looked at the impact of MRT algorithm variant on the We also looked at the impact of MRT algorithm variant on the
alternate path lengths. The first two rows for each topology present alternate path lengths. The first two rows for each topology present
skipping to change at page 50, line 50 skipping to change at page 52, line 50
| MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| 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 33
8. Implementation Status 8. Implementation Status
[RFC Editor: please remove this section prior to publication.] [RFC Editor: please remove this section prior to publication.]
Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on
implementation status. implementation status.
9. Algorithm Work to Be Done 9. Algorithm Work to Be Done
skipping to change at page 51, line 39 skipping to change at page 53, line 39
12. Security Considerations 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.
13. References 13. References
13.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., Bowers, C., Enyedi, G., Csaszar, Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., Konstantynowicz, M., and R. White, "An A., Tantsura, J., and R. White, "An Architecture for IP/
Architecture for IP/LDP Fast-Reroute Using Maximally LDP Fast-Reroute Using Maximally Redundant Trees", draft-
Redundant Trees", draft-rtgwg-mrt-frr-architecture-04 ietf-rtgwg-mrt-frr-architecture-05 (work in progress),
(work in progress), July 2014. January 2015.
[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.
13.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/collection Thesis, February 2011, <http://www.omikk.bme.hu/collection
s/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.farkas-isis-pcr]
Atlas, A., Tiruveedhula, K., Tantsura, J., and IJ. Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., and P.
Wijnands, "LDP Extensions to Support Maximally Redundant Ashwood-Smith, "IS-IS Path Computation and Reservation",
Trees", draft-atlas-mpls-ldp-mrt-01 (work in progress), draft-farkas-isis-pcr-01 (work in progress), December
July 2014. 2014.
[I-D.atlas-ospf-mrt] [I-D.ietf-isis-mrt]
Atlas, A., Hegde, S., Bowers, C., and J. Tantsura, "OSPF Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
Extensions to Support Maximally Redundant Trees", draft- Tantsura, "Intermediate System to Intermediate System (IS-
atlas-ospf-mrt-02 (work in progress), July 2014. IS) Extensions for Maximally Redundant Trees (MRT)",
draft-ietf-isis-mrt-00 (work in progress), February 2015.
[I-D.ietf-mpls-ldp-mrt]
Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and
I. Wijnands, "LDP Extensions to Support Maximally
Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in
progress), January 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-00 (work in progress), January 2015.
[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. Sarkar, "Operational management of Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draft-ietf-rtgwg-lfa- Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-07 (work in progress), January 2015. manageability-08 (work in progress), March 2015.
[I-D.ietf-rtgwg-remote-lfa] [I-D.ietf-rtgwg-remote-lfa]
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate Fast Re-Route", draft- So, "Remote Loop-Free Alternate (LFA) Fast Re-Route
ietf-rtgwg-remote-lfa-10 (work in progress), January 2015. (FRR)", draft-ietf-rtgwg-remote-lfa-11 (work in progress),
January 2015.
[I-D.li-isis-mrt]
Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
Tantsura, "Intermediate System to Intermediate System (IS-
IS) Extensions for Maximally Redundant Trees(MRT)", draft-
li-isis-mrt-01 (work in progress), July 2014.
[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, of IEEE INFOCOM , 2011,
skipping to change at page 53, line 29 skipping to change at page 55, line 34
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
Symposium on Computers and Comunications (ISCC) , 2009, Symposium on Computers and Comunications (ISCC) , 2009,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/ <http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>. distMaxRedTree.pdf>.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137, McPherson, "OSPF Stub Router Advertisement", RFC 3137,
June 2001. June 2001.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120, February 2008.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast
Reroute: Loop-Free Alternates", RFC 5286, September 2008. Reroute: Loop-Free Alternates", RFC 5286, September 2008.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework", RFC
5714, January 2010. 5714, January 2010.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., [RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B.,
Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free
Alternate (LFA) Applicability in Service Provider (SP) Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, June 2012. Networks", RFC 6571, June 2012.
skipping to change at page 54, line 35 skipping to change at page 56, line 48
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)
if min_node.IN_GADAG is true if min_node.IN_GADAG
found_in_gadag = true found_in_gadag = true
else else
foreach interface intf of min_node foreach interface intf of min_node
if ((intf.OUTGOING or intf.UNDIRECTED) and if ((intf.OUTGOING or intf.UNDIRECTED) and
((intf.remote_node.localroot is block_root) or ((intf.remote_node.localroot is block_root) or
(intf.remote_node is block_root)) and (intf.remote_node is block_root)) and
(intf.remote_node is not TEMP_UNUSABLE) and (intf.remote_node is not TEMP_UNUSABLE) and
(intf is not TEMP_UNUSABLE)) (intf is not TEMP_UNUSABLE))
path_metric = min_node.spf_metric + intf.metric path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric intf.remote_node.spf_metric = path_metric
intf.remote_node.spf_prev_intf = intf intf.remote_node.spf_prev_intf = intf
insert_or_update(spf_heap, intf.remote_node) insert_or_update(spf_heap, intf.remote_node)
return min_node return min_node
SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root, SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root,
method) method)
Mark all interfaces between cand_intf.remote_node Mark all interfaces between cand_intf.remote_node
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 33: Modified SPF for GADAG computation Figure 34: 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 y<- path should be y->x...q->z but if y >> z, then the path should be y<-
x...q<-z. In Section 5.4, the same problem was handled by finding 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 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 56, line 48 skipping to change at page 59, 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 34: Algorithm to assign links of an ear direction Figure 35: 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 the algorithm is to find the shortest cycles and ears. An
ear is started by going to a neighbor x of an IN_GADAG node y. The ear is started by going to a neighbor x of an IN_GADAG node y. The
path from x to an IN_GADAG node is minimal, since it is computed via path from x to an IN_GADAG node is minimal, since it is computed via
SPF. Since a shortest path is made of shortest paths, to find the SPF. Since a shortest path is made of shortest paths, to find the
shortest ears requires reaching from the set of IN_GADAG nodes to the shortest ears requires reaching from the set of IN_GADAG nodes to the
closest node that isn't IN_GADAG. Therefore, an ordered tree is closest node that isn't IN_GADAG. Therefore, an ordered tree is
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
was seen in Section 5.6. After any ear gets computed, we traverse was seen in Section 5.7. After any ear gets computed, we traverse
the newly added nodes to the GADAG and insert interfaces whose far the newly added nodes to the GADAG and insert interfaces whose far
end is not yet on the GADAG to the ordered tree for later processing. 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
insert(intf,ordered_intfs_tree) insert(intf,ordered_intfs_tree)
check_if_block_has_ear(x,block_id) check_if_block_has_ear(x,block_id)
block_has_ear = false block_has_ear = false
for all interfaces of x for all interfaces of x
if (intf.remote_node.block_id == block_id) && if ( (intf.remote_node.block_id == block_id) &&
(intf.remote_node.IN_GADAG is true) intf.remote_node.IN_GADAG )
block_has_ear = true block_has_ear = true
return block_has_ear return block_has_ear
Construct_GADAG_via_SPF(topology, root) Construct_GADAG_via_SPF(topology, root)
Compute_Localroot (root,root) Compute_Localroot (root,root)
Assign_Block_ID(root,0) Assign_Block_ID(root,0)
root.IN_GADAG = true root.IN_GADAG = true
add_eligible_interfaces_of_node(ordered_intfs_tree,root) add_eligible_interfaces_of_node(ordered_intfs_tree,root)
while ordered_intfs_tree is not empty while ordered_intfs_tree is not empty
cand_intf = remove_lowest(ordered_intfs_tree) cand_intf = remove_lowest(ordered_intfs_tree)
if cand_intf.remote_node.IN_GADAG is false if cand_intf.remote_node.IN_GADAG is false
if L(cand_intf.remote_node) == D(cand_intf.remote_node) if L(cand_intf.remote_node) == D(cand_intf.remote_node)
// Special case for cut-links // Special case for cut-links
cand_intf.UNDIRECTED = false cand_intf.UNDIRECTED = false
cand_intf.remote_intf.UNDIRECTED = false cand_intf.remote_intf.UNDIRECTED = false
cand_intf.OUTGOING = true cand_intf.OUTGOING = true
cand_intf.INCOMING = true cand_intf.INCOMING = true
cand_intf.remote_intf.OUTGOING = true cand_intf.remote_intf.OUTGOING = true
cand_intf.remote_intf.INCOMING = true cand_intf.remote_intf.INCOMING = true
cand_intf.remote_node.IN_GADAG = true cand_intf.remote_node.IN_GADAG = true
add_eligible_interfaces_of_node( add_eligible_interfaces_of_node(
ordered_intfs_tree,cand_intf.remote_node) ordered_intfs_tree,cand_intf.remote_node)
else
if (cand_intf.remote_node.local_root ==
cand_intf.local_node) &&
check_if_block_has_ear
(cand_intf.local_node,
cand_intf.remote_node.block_id))
/* Skip the interface since the block root
already has an incoming interface in the
block */
else else
ear_end = SPF_for_Ear(cand_intf.local_node, if (cand_intf.remote_node.local_root ==
cand_intf.remote_node, cand_intf.local_node) &&
cand_intf.remote_node.localroot, check_if_block_has_ear
SPF method) (cand_intf.local_node,
y = ear_end.spf_prev_hop cand_intf.remote_node.block_id))
while y.local_node is not cand_intf.local_node /* Skip the interface since the block root
add_eligible_interfaces_of_node( already has an incoming interface in the
ordered_intfs_tree, block */
y.local_node) else
y = y.local_node.spf_prev_intf ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.remote_node,
cand_intf.remote_node.localroot,
SPF method)
y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node(
ordered_intfs_tree,
y.local_node)
y = y.local_node.spf_prev_intf
Figure 35: SPF-based GADAG algorithm Figure 36: 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
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
skipping to change at page 59, line 14 skipping to change at page 62, 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 36 The entire algorithm is shown below in Figure 37
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 59, line 44 skipping to change at page 62, line 44
If x was set as TEMP_UNUSABLE, clear it If x was set as TEMP_UNUSABLE, clear it
cur = end_ear cur = end_ear
while (cur != y) while (cur != y)
intf = cur.spf_prev_hop intf = cur.spf_prev_hop
prev = intf.local_node prev = intf.local_node
intf.UNDIRECTED = false intf.UNDIRECTED = false
intf.remote_intf.UNDIRECTED = false intf.remote_intf.UNDIRECTED = false
intf.OUTGOING = true intf.OUTGOING = true
intf.remote_intf.INCOMING = true intf.remote_intf.INCOMING = true
push prev onto stack push prev onto stack
cur = prev cur = prev
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.remote_intf.INCOMING = true xy_intf.remote_intf.INCOMING = true
return return
Construct_GADAG_via_hybrid(topology,root) Construct_GADAG_via_hybrid(topology,root)
Compute_Localroot (root,root) Compute_Localroot (root,root)
Assign_Block_ID(root,0) Assign_Block_ID(root,0)
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 36: Hybrid GADAG algorithm Figure 37: Hybrid GADAG algorithm
Authors' Addresses Authors' Addresses
Gabor Sandor Enyedi (editor) Gabor Sandor Enyedi (editor)
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. 130 change blocks. 
374 lines changed or deleted 473 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/