< draft-enyedi-rtgwg-mrt-frr-algorithm-00.txt   draft-enyedi-rtgwg-mrt-frr-algorithm-01.txt >
Routing Area Working Group A. Atlas Routing Area Working Group A. Atlas
Internet-Draft Juniper Networks Internet-Draft Juniper Networks
Intended status: Informational G. Enyedi Intended status: Informational G. Enyedi
Expires: April 26, 2012 A. Csaszar Expires: September 13, 2012 A. Csaszar
Ericsson Ericsson
October 24, 2011 March 12, 2012
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-
Reroute Reroute
draft-enyedi-rtgwg-mrt-frr-algorithm-00 draft-enyedi-rtgwg-mrt-frr-algorithm-01
Abstract Abstract
A complete solution for IP and LDP Fast-Reroute using Maximally A complete solution for IP and LDP Fast-Reroute using Maximally
Redundant Trees is presented in Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr-
[I-D.atlas-rtgwg-mrt-frr-architecture]. This document describes an architecture]. This document describes an algorithm that can be used
algorithm that can be used to compute the necessary Maximally to compute the necessary Maximally Redundant Trees and the associated
Redundant Trees and the associated next-hops. next-hops.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 26, 2012. This Internet-Draft will expire on September 13, 2012.
Copyright Notice Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology and Definitions . . . . . . . . . . . . . . . . . 4
3. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . . 6
3.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 6
3.2. Finding an Ear and the Correct Direction . . . . . . . . . 8
3.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 10
3.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
3.5. Determining Local-Root . . . . . . . . . . . . . . . . . . 15
4. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . . 16
4.1. Root Selection . . . . . . . . . . . . . . . . . . . . . . 18
4.2. Initialization . . . . . . . . . . . . . . . . . . . . . . 18
4.3. Option 1: Computing GADAG using lowpoint inheritance . . . 18
4.4. Option 2: Computing GADAG using SPFs . . . . . . . . . . . 21
4.5. Augmenting the GADAG by directing all links . . . . . . . 27
4.6. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29
4.6.1. MRT next-hops to all nodes partially ordered with
respect to the computing node . . . . . . . . . . . . 30
4.6.2. MRT next-hops to all nodes not partially ordered
with respect to the computing node . . . . . . . . . . 30
4.6.3. Computing Redundant Tree next-hops in a
2-connected Graph . . . . . . . . . . . . . . . . . . 31
4.6.4. Generalizing for graph that isn't 2-connected . . . . 33
4.6.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 34
4.7. Identify MRT alternates . . . . . . . . . . . . . . . . . 36
5. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42
5.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . . 43
6. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 44
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 44
8. Security Considerations . . . . . . . . . . . . . . . . . . . 44
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 44
9.1. Normative References . . . . . . . . . . . . . . . . . . . 44
9.2. Informative References . . . . . . . . . . . . . . . . . . 44
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 46
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 Blue MRT and the Red MRT. A router which (MRTs), referred to as the Blue MRT and the Red MRT. 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 describes how to compute these three alternate to use. This document describes how to compute these three
things and the algorithm design decisions and rationale. The things and the algorithm design decisions and rationale. The
algorithms are based on those presented in [MRTLinear] and expanded algorithms are based on those presented in [MRTLinear] and expanded
in [EnyediThesis]. in [EnyediThesis].
skipping to change at page 3, line 43 skipping to change at page 4, line 27
[A]---[B]---| |---[H] [A]---[B]---| |---[H]
(a) a graph that isn't 2-connected (a) a graph that isn't 2-connected
[E]<--[D]<--| |---[J] [E]-->[D] [J] [E]<--[D]<--| |---[J] [E]-->[D] [J]
| ^ | | ^ | | | ^ | | ^ | |
V | | V | V | V | | V | V |
[R] [F] [C]<--[G] | [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | [R] [F] [C]<--[G] |
^ | ^ | | ^ | ^ | ^ | | ^ |
| | | V | | V | | | V | | V
[A]-->[B] [H] [A]---[B]<--| |---[H] [A]-->[B] [H] [A]<--[B]<--| |---[H]
(b) Blue MRT towards R (c) Red MRT towards R (b) Blue MRT towards R (c) Red MRT towards R
Figure 2 Figure 2
2. Terminology and Definitions 2. Terminology and Definitions
Redundant Trees (RT): A pair of trees where the path from any node Redundant Trees (RT): A pair of trees where the path from any node X
X to the root R along the first tree is node-disjoint with the to the root R on the first tree is node-disjoint with the path
path from the same node X to the root along the second tree. from the same node X to the root along the second tree. These can
These can be computed in 2-connected graphs. be computed in 2-connected graphs.
Maximally Redundant Trees (MRT): A pair of trees where the path Maximally Redundant Trees (MRT): A pair of trees where the path
from any node X to the root R along the first tree and the path from any node X to the root R along the first tree and the path
from the same node X to the root along the second tree share the from the same node X to the root along the second tree share the
minimum number of nodes and the minimum number of links. Each minimum number of nodes and the minimum number of links. Each
such shared node is a cut-vertex. Any shared links are cut-links. such shared node is a cut-vertex. Any shared links are cut-links.
Any RT is an MRT but many MRTs are not RTs. Any RT is an MRT but many MRTs are not RTs.
network graph: A graph that reflects the network topology where all network graph: A graph that reflects the network topology where all
links connect exactly two nodes and broadcast links have been links connect exactly two nodes and broadcast links have been
skipping to change at page 4, line 42 skipping to change at page 5, line 24
that requires two nodes to be removed before the network is that requires two nodes to be removed before the network is
partitioned. partitioned.
spanning tree: A tree containing links that connects all nodes in spanning tree: A tree containing links that connects all nodes in
the network graph. the network graph.
back-edge: In the context of a spanning tree computed via a depth- back-edge: In the context of a spanning tree computed via a depth-
first search, a back-edge is a link that connects a descendant of first search, a back-edge is a link that connects a descendant of
a node x with an ancestor of x. a node x with an ancestor of x.
DAG: Directed Acyclic Graph - a graph where all links are directed
and there are no cycles in it.
ADAG: Almost Directed Acyclic Graph - a graph that, if all links
incoming to the root were removed, would be a DAG.
2-connected cluster: A maximal set of nodes that are 2-connected. 2-connected cluster: A maximal set of nodes that are 2-connected.
In a network graph with at least one cut-vertex, there will be In a network graph with at least one cut-vertex, there will be
multiple 2-connected clusters. multiple 2-connected clusters.
block: Either a 2-connected cluster, a cut-edge, or an isolated block: Either a 2-connected cluster, a cut-edge, or an isolated
vertex. vertex.
GADAG: Generalized ADAG - a graph that is the combination of the DAG: Directed Acyclic Graph - a digraph containing no directed
ADAGs of all blocks. cycle.
ADAG: Almost Directed Acyclic Graph - a digraph that can be
transformed into a DAG whith removing a single node (the root
node).
GADAG: Generalized ADAG - a digraph, which has only ADAGs as all of
its blocks. The root of such a block is the node closest to the
global root (e.g. with uniform link costs).
DFS: Depth-First Search DFS: Depth-First Search
DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS-
tree path from the DFS root to x. tree path from the DFS root to x.
DFS descendant: A node n is a DFS descendant of x if x is on the DFS descendant: A node n is a DFS descendant of x if x is on the
DFS-tree path from the DFS root to n. DFS-tree path from the DFS root to n.
ear: A path along not-yet-included-in-the-GADAG nodes that starts ear: A path along not-yet-included-in-the-GADAG nodes that starts
skipping to change at page 5, line 34 skipping to change at page 6, line 20
X >> Y or Y << X: Indicates the relationship between X and Y in a X >> Y or Y << X: Indicates the relationship between X and Y in a
partial order, such as found in a GADAG. X >> Y means that X is partial order, such as found in a GADAG. X >> Y means that X is
higher in the partial order than Y. Y << X means that Y is lower higher in the partial order than Y. Y << X means that Y is lower
in the partial order than X. in the partial order than X.
X > Y or Y < X: Indicates the relationship between X and Y in the X > Y or Y < X: Indicates the relationship between X and Y in the
total order, such as found via a topological sort. X > Y means total order, such as found via a topological sort. X > Y means
that X is higher in the total order than Y. Y < X means that Y is that X is higher in the total order than Y. Y < X means that Y is
lower in the total order than X. lower in the total order than X.
proxy-node: A node added to the network graph to represent a multi-
homed prefix or routers outside the local MRT-fast-reroute-
supporting island of routers. The key property of proxy-nodes is
that traffic cannot transit them.
3. Algorithm Key Concepts 3. Algorithm Key Concepts
There are five key concepts that are critical for understanding the There are five key concepts that are critical for understanding the
algorithms for computing MRTs. The first is the idea of partially algorithms for computing MRTs. The first is the idea of partially
ordering the nodes in a network graph with regard to each other and ordering the nodes in a network graph with regard to each other and
to the GADAG root. The second is the idea of finding an ear of nodes to the GADAG root. The second is the idea of finding an ear of nodes
and adding them in the correct direction. The third is the idea of a and adding them in the correct direction. The third is the idea of a
Low-Point value and how it can be used to identify cut-vertices and Low-Point value and how it can be used to identify cut-vertices and
to find a second path towards the root. The fourth is the idea that to find a second path towards the root. The fourth is the idea that
a non-2-connected graph is made up of blocks, where a block is a a non-2-connected graph is made up of blocks, where a block is a
skipping to change at page 7, line 37 skipping to change at page 8, line 29
X and Y are already contained by our partial ADAG, but all the X and Y are already contained by our partial ADAG, but all the
remaining nodes along the path are not added to the ADAG yet. We remaining nodes along the path are not added to the ADAG yet. We
refer to such a path as an ear. refer to such a path as an ear.
Recall that our ADAG is closely related to a partial order, more Recall that our ADAG is closely related to a partial order, more
precisely, if we remove root R, the remaining DAG describes a partial precisely, if we remove root R, the remaining DAG describes a partial
order of the nodes. If we suppose that neither X nor Y is the root, order of the nodes. If we suppose that neither X nor Y is the root,
we may be able to compare them. If one of them is definitely lesser we may be able to compare them. If one of them is definitely lesser
with respect to our partial order (say X<<Y), we can add the new path with respect to our partial order (say X<<Y), we can add the new path
to the ADAG in a direction from X to Y. As an example consider to the ADAG in a direction from X to Y. As an example consider
Figure 5 Figure 5.
E---D---| E<--D---| E<--D<--| E---D---| E<--D---| E<--D<--|
| | | | ^ | | ^ | | | | | ^ | | ^ |
| | | V | | V | | | | | V | | V | |
R F C R F C R F C R F C R F C R F C
| | | | ^ | | ^ ^ | | | | ^ | | ^ ^
| | | V | | V | | | | | V | | V | |
A---B---| A-->B---| A-->B---| A---B---| A-->B---| A-->B---|
(a) (b) (c) (a) (b) (c)
skipping to change at page 8, line 42 skipping to change at page 9, line 21
ADAG. The ear must be added in a direction such that it doesn't ADAG. The ear must be added in a direction such that it doesn't
create a cycle; therefore the ear must go from X to Y. create a 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 greater than Y. The logic for this decision is which the root is lower than Y. The logic for this decision is
explained in Section 4.6 explained in Section 4.6
A partial ADAG is started by finding a cycle from the root R back to A partial ADAG is started by finding a cycle from the root R back to
itself. This can be done by selecting a non-ready neighbor N of R itself. This can be done by selecting a non-ready neighbor N of R
and then finding a path from N to R that doesn't use any links and then finding a path from N to R that doesn't use any links
between R and N. The direction of the cycle can be assigned either between R and N. The direction of the cycle can be assigned either
way since it is starting the ordering. way since it is starting the ordering.
Once a partial ADAG is already present, we can always add ears to it: Once a partial ADAG is already present, we can always add ears to it:
just select a non-ready neighbor N of a ready node Q, such that Q is just select a non-ready neighbor N of a ready node Q, such that Q is
not the root, find a path from N to the root in the graph with Q not the root, find a path from N to the root in the graph with Q
removed. This path is an ear where the first node of the ear is Q, removed. This path is an ear where the first node of the ear is Q,
the next is N, then the path until the first ready node the path the next is N, then the path until the first ready node the path
reached (that second ready node is the other endpoint of the path). reached (that second ready node is the other endpoint of the path).
Since the graph is 2-connected, there must be a path from N to R Since the graph is 2-connected, there must be a path from N to R
without Q. without Q.
It is always possible to select a non-ready neighbor N of a ready It is always possible to select a non-ready neighbor N of a ready
node Q so that Q is not the root R. Because the network is node Q so that Q is not the root R. Because the network is
skipping to change at page 9, line 30 skipping to change at page 10, line 14
Generic_Find_Ears_ADAG(root) Generic_Find_Ears_ADAG(root)
Create an empty ADAG. Add root to the ADAG. Create an empty ADAG. Add root to the ADAG.
Mark root as IN_GADAG. Mark root as IN_GADAG.
Select the shortest cycle containing root. Select the shortest cycle containing root.
Add the shortest cycle to the ADAG. Add the shortest cycle to the ADAG.
Mark cycle's nodes as IN_GADAG. Mark cycle's nodes as IN_GADAG.
Add cycle's non-root nodes to process_list. Add cycle's non-root nodes to process_list.
while there exists connected nodes in graph that are not IN_GADAG while there exists connected nodes in graph that are not IN_GADAG
Select a new ear. Let its endpoints be X and Y. Select a new ear. Let its endpoints be X and Y.
if (X is root) or (Y<<X) if Y is root or (Y << X)
add the ear towards X to the ADAG add the ear towards X to the ADAG
else // (a) Y is root or (b) Y>>X or (c)X, Y not ordered else // (a) X is root or (b)X << Y or (c) X, Y not ordered
Add the ear towards Y to the ADAG Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to find ears and their direction in Figure 6: Generic Algorithm to find ears and their direction in
2-connected graph 2-connected graph
Algorithm Figure 6 merely requires that a cycle or ear be selected 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. There are two options being considered. The Low-Point MRTs. There are two options being considered. The Low-Point
skipping to change at page 19, line 24 skipping to change at page 20, line 24
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_Ear(x, Stack, intf, type) Construct_Ear(x, Stack, intf, 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
while cur_node.IN_GADAG is false 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
cur_node.IN_GADAG = true
add_to_list_end(ear_list, cur_node)
if type is CHILD if cur_node.IN_GADAG is false
cur_intf = cur_node.lowpoint_parent_intf cur_node.IN_GADAG = true
else type must be NEIGHBOR add_to_list_end(ear_list, cur_node)
cur_intf = cur_node.dfs_parent_intf if type is CHILD
cur_node = cur_intf.remote_node cur_intf = cur_node.lowpoint_parent_intf
else type must be NEIGHBOR
cur_intf = cur_node.dfs_parent_intf
cur_node = cur_intf.remote_node
else
not_done = false
if (type is CHILD) and (cur_node is x) if (type is CHILD) and (cur_node is x)
localroot = x localroot = x
else else
localroot = x.localroot localroot = x.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
push(Stack, y) push(Stack, y)
Construct_GADAG_via_Lowpoint(topology, root)
Figure 14: Low-point Inheritance GADAG algorithm Figure 14: Low-point Inheritance GADAG algorithm
4.4. Option 2: Computing GADAG using SPFs 4.4. Option 2: Computing GADAG using SPFs
The basic idea in this option is to use slightly-modified SPF The basic idea in this option is to use slightly-modified SPF
computations to find ADAGs in each block. In each block, an SPF computations to find ADAGs in each block. In each block, an SPF
computation is first done to find a cycle from the local root and computation is first done to find a cycle from the local root and
then SPF computations find ears until there are no more interfaces to then SPF computations find ears until there are no more interfaces to
be explored. The used result from the SPF computation is the path of be explored. The used result from the SPF computation is the path of
interfaces indicated by following the previous hops from the interfaces indicated by following the previous hops from the
skipping to change at page 21, line 18 skipping to change at page 22, line 18
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 is true
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) and ((intf.remote_node.localroot is block_root) or
(intf.remote_node is not TEMP_UNUSABLE)) (intf.remote_node is block_root)) and
(intf.remote_node is not TEMP_UNUSABLE) and
(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(spf_root, block_root, ear_list, cut_vertex_list) SPF_for_Ear(spf_root, block_root, ear_list, cut_vertex_list)
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(cut_vertex_list, y) add_to_list_start(ear_list, y)
if y.local_node is a cut-vertex if y.local_node is a cut-vertex
add_to_list_end(cut_vertex_list, y.local_node) add_to_list_end(cut_vertex_list, y.local_node)
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
Figure 15: Modified SPF for GADAG computation Figure 15: Modified SPF for GADAG computation
In Figure 15, while the path is determined, any non-end node in the In Figure 15, while the path is determined, any non-end node in the
path that is a cut-vertex is added to the list of cut-vertices. This path that is a cut-vertex is added to the list of cut-vertices. This
ensures that there is a path from the GADAG root to that cut-vertex ensures that there is a path from the GADAG root to that cut-vertex
before adding it to the list of nodes. All such cut-vertices will be before adding it to the list of nodes. All such cut-vertices will be
skipping to change at page 23, line 12 skipping to change at page 24, line 12
second set, Lower_Nodes, contains all nodes that are known to be second set, Lower_Nodes, contains all nodes that are known to be
ordered below the node. This is the approach used in this algorithm. ordered below the node. This is the approach used in this algorithm.
Set_Ear_Direction(ear_list, end_a, end_b, block_root) Set_Ear_Direction(ear_list, end_a, end_b, block_root)
// Default of A_TO_B for the following cases: // Default of A_TO_B for the following cases:
// (a) end_a and end_b are the same (root) // (a) end_a and end_b are the same (root)
// or (b) end_a is in end_b's Lower Nodes // or (b) end_a is in end_b's Lower Nodes
// or (c) end_a and end_b were unordered with respect to each // or (c) end_a and end_b were unordered with respect to each
// other // other
direction = A_TO_B direction = A_TO_B
if (end_a is block_root) and (end_a is not end_b) if (end_b is block_root) and (end_a is not end_b)
direction = B_TO_A direction = B_TO_A
else if end_a is in end_b.Higher_Nodes else if end_a is in end_b.Higher_Nodes
direction = B_TO_A direction = B_TO_A
if direction is B_TO_A if direction is B_TO_A
foreach interface i in ear_list foreach interface i in ear_list
i.UNDIRECTED = false i.UNDIRECTED = false
i.INCOMING = true i.INCOMING = true
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
i.remote_intf.OUTGOING = true i.remote_intf.OUTGOING = true
else else
skipping to change at page 25, line 15 skipping to change at page 26, line 15
Construct_GADAG_via_SPF(topology, root) Construct_GADAG_via_SPF(topology, root)
Compute_Localroot(root, root) Compute_Localroot(root, root)
if root has multiple DFS-children if root has multiple DFS-children
mark root as a cut-vertex mark root as a cut-vertex
Initialize cut_vertex_list to empty Initialize cut_vertex_list to empty
Initialize ordered_intfs_tree to empty Initialize ordered_intfs_tree to empty
add_to_list_end(cut_vertex_list, root) add_to_list_end(cut_vertex_list, root)
while cut_vertex_list is not empty while cut_vertex_list is not empty
v = remove_start_item_from_list(cut_vertex_list) v = remove_start_item_from_list(cut_vertex_list)
foreach interface intf of v foreach interface intf of v
if intf.remote_node is a cut-vertex if L(intf.remote_node) == D(intf.remote_node)
// Special case for cut-edges // Special case for cut-edges
intf.UNDIRECTED = false intf.UNDIRECTED = false
intf.remote_intf.UNDIRECTED = false intf.remote_intf.UNDIRECTED = false
intf.OUTGOING = true intf.OUTGOING = true
intf.INCOMING = true intf.INCOMING = true
intf.remote_intf.OUTGOING = true intf.remote_intf.OUTGOING = true
intf.remote_intf.INCOMING = true intf.remote_intf.INCOMING = true
if intf.remote_node.IN_GADAG == false
if intf.remote_node is a cut-vertex
add_to_list_end(cut_vertex_list, intf.remote_node)
intf.remote_node.IN_GADAG = true
else if intf.remote_node.localroot is v else if intf.remote_node.localroot is v
insert(ordered_intfs_tree, intf) insert(ordered_intfs_tree, intf)
v.IN_GADAG = true v.IN_GADAG = true
while ordered_intfs_trees is not empty while ordered_intfs_trees 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
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 v if cand_intf.local_node is not v
Mark cand_intf.local_node as TEMP_UNUSABLE Mark cand_intf.local_node as TEMP_UNUSABLE
skipping to change at page 26, line 30 skipping to change at page 27, line 39
To convert a GADAG to a DAG, it is necessary to remove all links that To convert a GADAG to a DAG, it is necessary to remove all links that
point to a root of block from within that block. That provides the point to a root of block from within that block. That provides the
necessary conversion to a DAG and then a topological sort can be necessary conversion to a DAG and then a topological sort can be
done. Finally, all UNDIRECTED links are assigned a direction based done. Finally, all UNDIRECTED links are assigned a direction based
upon the partial ordering. Any UNDIRECTED links that connect to a upon the partial ordering. Any UNDIRECTED links that connect to a
root of a block from within that block are assigned a direction root of a block from within that block are assigned a direction
INCOMING to that root. The exact details of this whole process are INCOMING to that root. The exact details of this whole process are
captured in Figure 18 captured 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.INCOMING = true i.OUTGOING = true
i.remote_intf.OUTGOING = true i.remote_intf.INCOMING = true
i.UNDIRECTED = false i.UNDIRECTED = false
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
if i.INCOMING if i.INCOMING
if mark_or_clear is mark if mark_or_clear is mark
i.TEMP_UNUSABLE = true if i.OUTGOING // a cut-edge
i.remote_intf.TEMP_UNUSABLE = true i.STORE_INCOMING = true
i.INCOMING = false
i.remote_intf.STORE_OUTGOING = true
i.remote_intf.OUTGOING = false
i.TEMP_UNUSABLE = true
i.remote_intf.TEMP_UNUSABLE = true
else
i.TEMP_UNUSABLE = false
i.remote_intf.TEMP_UNUSABLE = false
if i.STORE_INCOMING and (mark_or_clear is clear)
i.INCOMING = true
i.STORE_INCOMING = false
i.remote_intf.OUTGOING = true
i.remote_intf.STORE_OUTGOING = false
Run_Topological_Sort(topo, root) Run_Topological_Sort_GADAG(topo, root)
foreach node x Set_Block_Root_Incoming_Links(topo, root, MARK)
set x.unvisited to the count of x's incoming interfaces foreach node x
that aren't marked TEMP_UNUSABLE set x.unvisited to the count of x's incoming interfaces
Initialize working_list to empty that aren't marked TEMP_UNUSABLE
Initialize topo_order_list to empty Initialize working_list to empty
add_to_list_end(working_list, root) Initialize topo_order_list to empty
while working_list is not empty add_to_list_end(working_list, root)
y = remove_start_item_from_list(working_list) while working_list is not empty
add_to_list_end(topo_order_list, y) y = remove_start_item_from_list(working_list)
foreach interface i of y add_to_list_end(topo_order_list, y)
if (i.OUTGOING) and (not i.TEMP_UNUSABLE) foreach interface i of y
i.remote_node.unvisited -= 1 if (i.OUTGOING) and (not i.TEMP_UNUSABLE)
if i.remote_node.unvisited is 0 i.remote_node.unvisited -= 1
add_to_list_end(working_list, i.remote_node) if i.remote_node.unvisited is 0
next_topo_order = 1 add_to_list_end(working_list, i.remote_node)
while topo_order_list is not empty next_topo_order = 1
y = remove_start_item_from_list(topo_order_list) while topo_order_list is not empty
y.topo_order = next_topo_order y = remove_start_item_from_list(topo_order_list)
next_topo_order += 1 y.topo_order = next_topo_order
next_topo_order += 1
Set_Block_Root_Incoming_Links(topo, root, CLEAR)
Add_Undirected_Links(topo, root) Add_Undirected_Links(topo, root)
Set_Block_Root_Incoming_Links(topo, root, MARK) Run_Topological_Sort_GADAG(topo, root)
Run_Topological_Sort(topo, root) foreach node x in topo
Set_Block_Root_Incoming_Links(topo, root, CLEAR) foreach interface i of x
foreach node x in topo if i.UNDIRECTED
foreach interface i of x if x.topo_order < i.remote_node.topo_order
if i.UNDIRECTED i.OUTGOING = true
if x.topo_order < i.remote_node.topo_order i.UNDIRECTED = false
i.OUTGOING = true i.remote_intf.INCOMING = true
i.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
i.remote_intf.INCOMING = true
i.remote_intf.UNDIRECTED = false
else
i.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, root) else
i.INCOMING = true
i.UNDIRECTED = false
i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, root)
Figure 18: Assigning direction to UNDIRECTED links Figure 18: Assigning direction to UNDIRECTED links
Proxy-nodes are used to represent multi-homed prefixes and routers
that do not support MRT Fast-Reroute. Until now, the network graph
has not included proxy-nodes because the computation for a GADAG
assumes that the nodes can be transited.
To handle destinations that can only be reached via proxy-nodes, each
proxy-node should be added into the network graph after
Add_Directed_Links() has beeen run once. A proxy-node P is connected
to two routers, X and Y, which have been found to offer the best
cost. If X.topo_order < Y.topo_order, then the proxy-node P is added
along with a link X->P and a link P->Y. Once all the proxy-nodes have
been added in this fashion, Run_Topological_Sort_GADAG() should be
rerun so that the topological order includes the proxy-nodes as well.
This is needed for determining which MRT can offer alternates, as is
explained in Section 4.7.
4.6. Compute MRT next-hops 4.6. Compute MRT next-hops
As was discussed in Section 3.1, once a ADAG is found, it is As was discussed in Section 3.1, once a ADAG is found, it is
straightforward to find the next-hops from any node X to the ADAG straightforward to find the next-hops from any node X to the ADAG
root. However, in this algorithm, we want to reuse the common GADAG root. However, in this algorithm, we want to reuse the common GADAG
and find not only one pair of redundant trees with it, but a pair and find not only one pair of redundant trees with it, but a pair
rooted at each node. This is ideal, since it is faster and it rooted at each node. This is ideal, since it is faster and it
results packet forwarding easier to trace and/or debug. The method results packet forwarding easier to trace and/or debug. The method
for doing that is based on two basic ideas. First, if two nodes X for doing that is based on two basic ideas. First, if two nodes X
and Y are ordered with respect to each other in the partial order, and Y are ordered with respect to each other in the partial order,
skipping to change at page 29, line 42 skipping to change at page 31, line 34
Blue MRT path: decrease to H and increase to Y Blue MRT path: decrease to H and increase to Y
X->Cloud 2->H->Cloud 5->Y X->Cloud 2->H->Cloud 5->Y
Red MRT path: increase to G and decrease to Y Red MRT path: increase to G and decrease to Y
X->Cloud 3->G->Cloud 6->Y X->Cloud 3->G->Cloud 6->Y
Figure 21: 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 out-going interface from the root R which is created when only one incoming interface to the root R which is created when the
the initial cycle is found. Recall from Figure 6 that whenever an initial cycle is found. Recall from Figure 6 that whenever an ear
ear was found to have an end that was the root R, the ear was was found to have an end that was the root R, the ear was directed
directed towards R so that the associated interface on R is incoming from R so that the associated interface on R is outgoing and not
and not outgoing. Therefore, there must be exactly one node M which incoming. Therefore, there must be exactly one node M which is the
is the smallest one after R, so the Blue MRT path will never reach R; largest one before R, so the Red MRT path will never reach R; it will
it will turn at M and increase to Y. turn at M and decrease to Y.
4.6.3. Computing Redundant Tree next-hops in a 2-connected Graph 4.6.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 4.6.1 and Section 4.6.2. Given these two were given in Section 4.6.1 and Section 4.6.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
skipping to change at page 32, line 35 skipping to change at page 34, line 21
4.6.5. Complete Algorithm to Compute MRT Next-Hops 4.6.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 23. In addition to computing the Blue router X is given in Figure 23. In addition to computing the Blue
MRT next-hops and Red MRT next-hops used by X to reach each node Y, MRT next-hops and Red MRT 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 Blue MRT or the Red MRT can provide an in deciding whether the Blue MRT or the Red MRT can provide an
acceptable alternate for a particular primary next-hop. acceptable alternate for a particular primary next-hop.
global_var: max_block_id
Assign_Block_ID(x, cur_block_id)
x.block_id = cur_block_id
foreach DFS child c of x
if (c.local_root is x)
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else
Assign_Block_ID(c, cur_block_id)
In_Common_Block(x, y) In_Common_Block(x, y)
if ((x.localroot is y.localroot) or (x is y.localroot) or if ((x.localroot is y.localroot) or (x is y.localroot) or
(y is x.localroot)) (y is x.localroot))
return true return true
return false return false
Store_Results(y, direction, spf_root) Store_Results(y, direction, spf_root, store_nhs)
if direction is FORWARD if direction is FORWARD
y.higher = true y.higher = true
y.blue_next_hops = y.next_hops if store_nhs
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) SPF_No_Traverse_Root(spf_root, block_root, direction, store_nhs)
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_Results(min_node, direction, spf_root, store_nhs)
if min_node is not block_root if ((min_node is spf_root) or
((min_node is not block_root) and
(min_node is not a proxy_node)))
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) and
In_Common_Block(spf_root, intf.remote_node)) In_Common_Block(spf_root, intf.remote_node))
if direction is FORWARD if direction is FORWARD
path_metric = min_node.spf_metric + intf.metric path_metric = min_node.spf_metric + intf.metric
else else
path_metric = min_node.spf_metric + path_metric = min_node.spf_metric +
intf.remote_intf.metric intf.remote_intf.metric
if path_metric < intf.remote_node.spf_metric if path_metric < intf.remote_node.spf_metric
skipping to change at page 33, line 44 skipping to change at page 35, line 45
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) SPF_No_Traverse_Root(x, x.localroot, FORWARD, TRUE)
SPF_No_Traverse_Root(x, x.localroot, REVERSE) SPF_No_Traverse_Root(x, x.localroot, REVERSE, TRUE)
// 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 is not x) and (y.localroot is x.localroot) if ((y is not x) and (y.localroot is x.localroot) and
((y is x.localroot) or (y.block_id is x.block_id))
if y.higher if y.higher
y.red_next_hops = x.localroot.red_next_hops y.red_next_hops = x.localroot.red_next_hops
else if y.lower else if y.lower
y.blue_next_hops = x.localroot.blue_next_hops y.blue_next_hops = x.localroot.blue_next_hops
else else
y.blue_next_hops = x.localroot.red_next_hops y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_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) if (y is not root) and (y is not x)
SetEdge(y) SetEdge(y)
Copute_RT_NextHops(x, root) max_block_id = 0
Assign_Block_ID(root, max_block_id)
Compute_MRT_NextHops(x, root)
Figure 23 Figure 23
4.7. Identify MRT alternates 4.7. Identify MRT alternates
At this point, a computing router S knows its Blue MRT next-hops and At this point, we have that a computing router S knows its Blue MRT
Red MRT next-hops for each destination. The primary next-hops along next-hops and Red MRT next-hops for each destination. However, we
the SPT are also known. It remains to determine for each primary usually needed to find out which one among these two should be used
next-hop to a destination D, which of the MRTs avoids the primary in order to avoid a potentially failed node. Usually, the node needs
next-hop node F. This computation depends upon data set in only to avoid the default next-hop (which has just failed), which is
Compute_MRT_NextHops such as each node y's y.blue_next_hops, a neighbor. However, there is a much complex use case for multicast
y.red_next_hops, y.order_proxy, y.higher, y.lower and topo_orders. forwarding, when an alternate area border router must be avoided.
Recall that any router knows only which are the nodes greater and Thus, first we provide a simple algorithm for finding the correct
lesser than itself, but it cannot decide the relation between any two trees to avoid a given neighbor, and later this algorithm is modified
given nodes easily; that is why we need topological ordering. for a node far away.
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) to determine whether to use the Blue MRT Select_Alternates(S, D, F) to determine whether to use the Blue MRT
next-hops as the alternate next-hop(s) for that primary next-hop or next-hops as the alternate next-hops for that primary next-hop or to
to use the Red MRT next-hops. The algorithm is given in Figure 24 use the Red MRT next-hops. The algorithm is given in Figure 24 and
and discussed afterwards. discussed afterwards. Note that we suppose that each link was
already added to the GADAG in some direction, thus S and F must be
ordered, and there must be a block of the GADAG, which contains both
S and F. Moreover, we also suppose that if there are parallel links
between S and F, and only one of them fails, the connection with F is
not lost, and IPFRR is not activated (instead this event is handled
by some other protection). Finally, if F is the primary next-hop
along a shortest path towards D, D (or D.order_proxy) must be in the
same block. If this final assumption were not true, we would have to
put an extra condition into the algorithm for checking if F and
D.order_proxy are not in the same block, and if they were in
different blocks, both trees could be used.
Select_Alternates(S, D, F) Select_Alternates_For_NH(S, D, F)
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
if D_higher ///When D==F, we can do only link protection
if F.higher if ((D == F) or (D.order_proxy == F))
if F.topo_order < D_topo_order if (D_lower)
return USE_RED return USE_BLUE
else else
return USE_BLUE return USE_RED
else if F.lower
return USE_BLUE
else
// F and S are neighbors so either F << S or F >> S
else if D_lower
if F.higher
return USE_RED
else if F.lower
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
else
// F and S are neighbors so either F << S or F >> S
else // D and S not ordered
if F.lower
return USE_BLUE
else if F.upper
return USE_RED
else
// F and S are neighbors so either F << S or F >> S
Figure 24 //There are three corner cases when S, F or D is the local root
if (S == F.local_root && S == D.local_root)
if (F.topo_order < D.topo_order)
return USE_RED
else
return USE_BLUE
If either D>>S>>F or D<<S<<F holds true, the situation is simple: in if (F == S.local_root && F == D.local_root)
the first case we should choose the increasing Blue next-hop, in the if (D_lower)
second case, the decreasing Red next-hop is the right choice. return USE_RED
else
return USE_BLUE
However, when both D and F are greater than S the situation is not so if (D == S.local_root && D == F.local_root)
simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii) if (F.lower)
F and D are not ordered. In the first case, we should choose the return USE_BLUE
path towards D along the Blue tree. In contrast, in case (ii) the else
Red path towards the root and then to D would be the solution. return USE_RED
Finally, in case (iii) both paths would be acceptable. However,
observe that if e.g. F.topo_order>D.topo_order, either case (i) or
case (iii) holds true, which means that selecting the Blue next-hop
is safe. Similarly, if F.topo_order<D.topo_order, we should select
the Red next-hop. The situation is almost the same if both F and D
are less than S.
Recall that we have added each link to the GADAG in some direction, //This is the main part. Recall that S and F must be ordered
so that is imposible that S and F are not ordered. But it is if (D_lower)
possible that S and D are not ordered, so we need to deal with this if (F.lower && F.topo_order > D_topo_order)
case as well. If F<<S, we can use the Red next-hop, because that return USE_BLUE
path is first increasing until a node definitely greater than D is else
reached, than decreasing; this path must avoid using F. Similarly, if return USE_RED
F>>S, we should use the Blue next-hop. else if (D_higher)
if (F.higher && F.topo_order < D_topo_order)
return USE_RED
else
return USE_BLUE
else //S and D are not ordered
if (F.lower)
return USE_RED
else
return USE_BLUE
As an example consider the ADAG depicted in Figure 25 and first Figure 24
The algorithm first handles some corner cases, when either of S, D
and F is the local root. When D is in a different block, the cut-
vertex leading to D's block is used instead as D's order-proxy. If
that is not true, there must be a block, which contains all the three
of them. If S>>D.order_proxy, we can use the red path (decreasing
path), unless F is in interval [D.order_proxy,S] - that is checked in
the second if branch. Similarly, when S<<D.order_proxy, we can use
the blue path unless F can be in interval [S,D.order_proxy]. When S
and D.order_proxy are not ordered, and F<<S, we know that the first
increasing than decreasing (red) path must not contain F. Trivially,
when F>>S, we need to use the blue path.
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 check if H can be in
D.topo_order. Since D.topo_order>H.topo_order D must be not smaller interval [G,D]. Since H>>G and D.topo_order>H.topo_order, this may
than H, so we should select the decreasing path towards the root. be possible (actually, in this example that is not only possible but
If, however, the destination were instead J, we must find that true), so we select the decreasing path towards the root (red path).
H.topo_order>J.topo_order, so we must choose the increasing Blue Observe, that we are not sure that H is really in [G,D], but we are
next-hop to J, which is I. In the case, when instead the destination sure that it is not in interval [R, G] and not in interval [R, D] (R
is C, we find that we need first decrease to avoid using H, so the is the smallest and the greatest node), so the decreasing path will
Blue, first decreasing then increasing, path is selected. always be usable. If, however, the destination was instead J, we
would find that H.topo_order>J.topo_order, so we can be sure that H
is not in [G, J], so using the increasing (blue) path is safe.
[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)
a 2-connected graph a 2-connected graph
Figure 25 Figure 25
For ADAGs, the previous algorithm can easily be extended to compute
the right next-hops for a failed node F. One needs only to find out
what to do, when S is ordered with neither F nor D. In that
situation, the first part of the path (the decreasing part for the
blue path or the increasing part of the red path) is ordered with S,
so that do not contain F. Thus, we can use the blue path if F>D and
the red path if F<D, since the second part of these paths are not
containing F. This extended algorithm is described below (the
differing part is at the end); keep in mind that this algorithm is
applicable only for ADAGs, so the initial part for finding
D.order_proxy is excluded.
Select_Alternates_For_ADAG(S, D, F)
//When D==F, we can do only link protection
if (D == F)
if Blue next-hops do not include primary next-hop
return USE_BLUE
else if Red next-hops do not include primary next-hop
return USE_RED
else if Blue next-hops minus primary next-hop is not empty
return USE_BLUE_MINUS_LINK
else if Red next-hops minus primary next-hop is not empty
return USE_BLUE_MINUS_LINK
//There are three corner cases when S, F or D is the local root
if (S == F.local_root && S == D.local_root)
if (F.topo_order < D.topo_order)
return USE_RED
else
return USE_BLUE
if (F == S.local_root && F == D.local_root)
if (D.lower)
return USE_RED
else
return USE_BLUE
if (D == S.local_root && D == F.local_root)
if (F.lower)
return USE_BLUE
else
return USE_RED
//This is the main part. Recall that S and D must be ordered
if (D.lower)
if (F.lower && F.topo_order > D_topo_order)
return USE_BLUE
else
return USE_RED
else if (D.higher)
if (F.higher && F.topo_order < D_topo_order)
return USE_RED
else
return USE_BLUE
else //S and D are not ordered
if (F.lower)
return USE_RED
else
return USE_BLUE
else //THIS IS DIFFERENT: S is not ordered with both F and D
if (F.topo_order > D_topo_order)
return USE_BLUE
else
return USE_RED
Figure 26
Select_Alternates_For_ADAG is valid, only when S, F, and D are in the
same block; if this is not the case, we do not even have order
between the nodes. Therefore, if we have a GADAG, where S and F are
not in the same block, we need to convert it into an ADAG.
The transformation is straightforward. Suppose that there is a node
X along the path from S to D. We need to split that into two nodes,
let them be X1 and X2, and add an X1->X2 arc between them. For that
block where X was not the local root, all the arcs going into X must
be added to X1 and all the arcs going out from X must be added to X2.
Moreover, for all the blocks, where X was the local root, do the
opposite, i.e. add arcs going out from X to X1, and those going into
X should be added to X2. It can be seen that the blue and the red
paths will be the same after the transformation, except that where
previously they both crossed X, the red now crosses X1 and the blue
now crosses X2. It is straightforward to see that in this way the
blocks separated by X are opened up into a single block. Naturally,
if the blue or the red path could avoid using a given node F in the
resulting ADAG, path with the same color will avoid F in the original
GADAG. Below is the pseudo code of the generalized algorithm.
Convert_GADAG_to_ADAG(GADAG, ADAG)
ADAG = GADAG
for_each local_root X in GADAG
remove X from ADAG
add X1 to ADAG
add X2 to ADAG
add X1->X2 to ADAG
for_each arc Y->X in GADAG {
if (Y.local_root != X)
add Y->X1 to ADAG
else
add Y->X2 to ADAG
}
for_each arc X->Y in GADAG {
if (Y.local_root != X)
add X2->Y to ADAG
else
add X1->Y to ADAG
}
Select_Alternates_For_GADAG(S, D, F)
if (ADAG == NULL) //Need this once, not once for each F and D
Convert_GADAG_to_ADAG(GADAG, ADAG)
// Now determine the orderings via an SPF and rSPF on ADAG
SPF_No_Traverse_Root(S, S.localroot, FORWARD, FALSE)
SPF_No_Traverse_Root(S, S.localroot, REVERSE, FALSE)
return Select_Alternates_For_ADAG(S, D, F)
Figure 27
As an example consider the GADAG depicted in Figure 28. In that
GADAG, three cut-vertices can be found: C, H and K; we need to split
them all. First, split C, now we have C1 and C2 and a C1->C2 arc
between them. We have arcs B->C and J->C going into C. Since B does
not have C as local root, we add B->C1 to ADAG. However,
J.local_root is C, so J->C2 is added. Similarly we add C2->D and
C1->F. The resulting ADAG is depicted in Figure 29. Now that the
GADAG is converted to an ADAG, it is straightforward to use
Select_Alternates_For_ADAG for this ADAG.
[E]<--| [J]<------[I] [P]<--[O]
| | | ^ | ^
V | V | V |
[R] [D]<--[C]->[F] [H]<--[K] [N]
| ^ | [ ]-->[ ] ^
| | | ^ | |
V | V | V |
[A]------->[B] [G]---| [L]-->[M]
A GADAG with multiple blocks
Figure 28
[E]<--| [J]<-----------[I] [P]<--[O]
| | | ^ | ^
V | V | V |
[R] [D]<----[C2] [H2]<--[K2] [N]
| ^ ^ ^ ^
| | | | |
| [C1]----->[F] [H1]-->[K1] |
| ^ | ^ | |
V | V | V |
[A]---------->[B] [G]----| [L]-->[M]
The ADAG after conversion
Figure 29
5. Algorithm Alternatives and Evaluation 5. Algorithm Alternatives and Evaluation
This description of the algorithm assumes a particular approach that This description of the algorithm assumes a particular approach that
is believed to be a reasonable compromise between complexity and is believed to be a reasonable compromise between complexity and
computation. There are two options given for constructing the GADAG computation. There are two options given for constructing the GADAG
as both are reasonable and promising. as both are reasonable and promising.
SPF-based GADAG Compute the common GADAG using Option 2 of SPF-based SPF-based GADAG Compute the common GADAG using Option 2 of SPF-based
inheritance. This considers metrics when constructing the GADAG, inheritance. This considers metrics when constructing the GADAG,
which is important for path length and operational control. It which is important for path length and operational control. It
skipping to change at page 38, line 14 skipping to change at page 44, line 4
o SPF-based GADAG o SPF-based GADAG
o Low-Point Inheritance GADAG o Low-Point Inheritance GADAG
o Destination-Rooted SPF-based GADAG o Destination-Rooted SPF-based GADAG
o Destination-Rooted Low-Point Inheritance GADAG o Destination-Rooted Low-Point Inheritance GADAG
o Not-Via to Next-Next Hop[I-D.ietf-rtgwg-ipfrr-notvia-addresses] o Not-Via to Next-Next Hop[I-D.ietf-rtgwg-ipfrr-notvia-addresses]
o Loop-Free Alternates[RFC5286] o Loop-Free Alternates[RFC5286]
o Remote LFAs[I-D.shand-remote-lfa] o Remote LFAs[I-D.shand-remote-lfa]
6. IANA Considerations 6. Algorithm Work to Be Done
Broadcast Interfaces: The algorithm assumes that broadcast
interfaces are already represented as pseudo-nodes in the network
graph. The exact rules for extending the set of next-hops and
ensuring that the neighboring node is avoided need to be fully
specified.
Local SRLG Protection: The algorithmic extensions to handle local
SRLGs, where each member of the SRLG shares a common router end,
need to be fully specified.
General SRLG Protection: Creating MRTs that consider general SRLGs
is still a challenging open research problem.
7. IANA Considerations
This doument includes no request to IANA. This doument includes no request to IANA.
7. Security Considerations 8. Security Considerations
This architecture is not currently believed to introduce new security This architecture is not currently believed to introduce new security
concerns. concerns.
8. References 9. References
8.1. Normative References 9.1. Normative References
[I-D.atlas-rtgwg-mrt-frr-architecture] [I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Konstantynowicz, M., Envedi, G., Csaszar, A., Atlas, A., Kebler, R., Konstantynowicz, M., Csaszar, A.,
White, R., and M. Shand, "An Architecture for IP/LDP Fast- White, R., and M. Shand, "An Architecture for IP/LDP Fast-
Reroute Using Maximally Redundant Trees", Reroute Using Maximally Redundant Trees",
draft-atlas-rtgwg-mrt-frr-architecture-00 (work in draft-ietf-rtgwg-mrt-frr-architecture-00 (work in
progress), July 2011. progress), January 2012.
8.2. Informative References 9.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, Thesis, February 2011, <http://www.omikk.bme.hu/
<http://timon.tmit.bme.hu/theses/thesis_book.pdf>. collections/phd/Villamosmernoki_es_Informatikai_Kar/2011/
Enyedi_Gabor/ertekezes.pdf>.
[I-D.ietf-rtgwg-ipfrr-notvia-addresses] [I-D.ietf-rtgwg-ipfrr-notvia-addresses]
Shand, M., Bryant, S., and S. Previdi, "IP Fast Reroute Bryant, S., Previdi, S., and M. Shand, "IP Fast Reroute
Using Not-via Addresses", Using Not-via Addresses",
draft-ietf-rtgwg-ipfrr-notvia-addresses-07 (work in draft-ietf-rtgwg-ipfrr-notvia-addresses-08 (work in
progress), April 2011. progress), December 2011.
[I-D.ietf-rtgwg-lfa-applicability] [I-D.ietf-rtgwg-lfa-applicability]
Filsfils, C., Francois, P., Shand, M., Decraene, B., Filsfils, C. and P. Francois, "LFA applicability in SP
Uttaro, J., Leymann, N., and M. Horneffer, "LFA networks", draft-ietf-rtgwg-lfa-applicability-06 (work in
applicability in SP networks", progress), January 2012.
draft-ietf-rtgwg-lfa-applicability-03 (work in progress),
August 2011.
[I-D.shand-remote-lfa] [I-D.shand-remote-lfa]
Bryant, S., Filsfils, C., Shand, M., and N. So, "Remote Bryant, S., Filsfils, C., Shand, M., and N. So, "Remote
LFA FRR", draft-shand-remote-lfa-00 (work in progress), LFA FRR", draft-shand-remote-lfa-00 (work in progress),
October 2011. October 2011.
[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>.
 End of changes. 67 change blocks. 
211 lines changed or deleted 498 lines changed or added

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