draft-ietf-rtgwg-mrt-frr-algorithm-03.txt   draft-ietf-rtgwg-mrt-frr-algorithm-04.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: September 10, 2015 A. Atlas, Ed. Expires: January 3, 2016 A. Atlas, Ed.
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
March 9, 2015 July 2, 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-03 draft-ietf-rtgwg-mrt-frr-algorithm-04
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 September 10, 2015. This Internet-Draft will expire on January 3, 2016.
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 31 skipping to change at page 2, line 31
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. Interface Ordering . . . . . . . . . . . . . . . . . . . 19 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23
5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
inheritance . . . . . . . . . . . . . . . . . . . . . . . 24 inheritance . . . . . . . . . . . . . . . . . . . . . . . 24
5.6. Augmenting the GADAG by directing all links . . . . . . . 26 5.6. Augmenting the GADAG by directing all links . . . . . . . 26
5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 28 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30
5.7.1. MRT next-hops to all nodes partially ordered with 5.7.1. MRT next-hops to all nodes partially ordered with
respect to the computing node . . . . . . . . . . . . 29
5.7.2. MRT next-hops to all nodes not partially ordered with
respect to the computing node . . . . . . . . . . . . 30 respect to the computing node . . . . . . . . . . . . 30
5.7.2. MRT next-hops to all nodes not partially ordered with
respect to the computing node . . . . . . . . . . . . 31
5.7.3. Computing Redundant Tree next-hops in a 2-connected 5.7.3. Computing Redundant Tree next-hops in a 2-connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 Graph . . . . . . . . . . . . . . . . . . . . . . . . 32
5.7.4. Generalizing for a graph that isn't 2-connected . . . 32 5.7.4. Generalizing for a graph that isn't 2-connected . . . 34
5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 33 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35
5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 35 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37
5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 39 5.9. Finding FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 42
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 42 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 45
7. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 42 7. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 45
7.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 43 8. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 66
8. Implementation Status . . . . . . . . . . . . . . . . . . . . 53 8.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 66
9. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 53 9. Implementation Status . . . . . . . . . . . . . . . . . . . . 76
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 53 10. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 76
11. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 53 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 76
12. Security Considerations . . . . . . . . . . . . . . . . . . . 53 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 76
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 53 13. Security Considerations . . . . . . . . . . . . . . . . . . . 76
13.1. Normative References . . . . . . . . . . . . . . . . . . 53 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 76
13.2. Informative References . . . . . . . . . . . . . . . . . 53 14.1. Normative References . . . . . . . . . . . . . . . . . . 76
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 56 14.2. Informative References . . . . . . . . . . . . . . . . . 76
Appendix B. Option 3: Computing GADAG using a hybrid method . . 61 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 78
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 63 Appendix B. Option 3: Computing GADAG using a hybrid method . . 83
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 85
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 7, line 25 skipping to change at page 7, line 25
proxy-node: A node added to the network graph to represent a multi- proxy-node: A node added to the network graph to represent a multi-
homed prefix or routers outside the local MRT-fast-reroute- homed prefix or routers outside the local MRT-fast-reroute-
supporting island of routers. The key property of proxy-nodes is supporting island of routers. The key property of proxy-nodes is
that traffic cannot transit them. that traffic cannot transit them.
UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING
or both. Until the directionality of the link is determined, the or both. Until the directionality of the link is determined, the
link is marked as UNDIRECTED to indicate that its direction hasn't link is marked as UNDIRECTED to indicate that its direction hasn't
been determined. been determined.
OUTGOING: In the GADAG, each link is marked as OUTGOING, INCOMING OUTGOING: A link marked as OUTGOING has direction in the GADAG from
or both. A link marked as OUTGOING has direction from the the interface's router to the remote end.
interface's router to the remote end.
INCOMING: In the GADAG, each link is marked as OUTGOING, INCOMING INCOMING: A link marked as INCOMING has direction in the GADAG from
or both. A link marked as INCOMING has direction from the remote the remote end to the interface's router.
end to the interface's router.
4. Algorithm Key Concepts 4. Algorithm Key Concepts
There are five key concepts that are critical for understanding the There are five key concepts that are critical for understanding the
MRT Lowpoint algorithm and other algorithms for computing MRTs. The MRT Lowpoint algorithm and other algorithms for computing MRTs. The
first is the idea of partially ordering the nodes in a network graph first is the idea of partially ordering the nodes in a network graph
with regard to each other and to the GADAG root. The second is the with regard to each other and to the GADAG root. The second is the
idea of finding an ear of nodes and adding them in the correct idea of finding an ear of nodes and adding them in the correct
direction. The third is the idea of a Low-Point value and how it can direction. The third is the idea of a Low-Point value and how it can
be used to identify cut-vertices and to find a second path towards be used to identify cut-vertices and to find a second path towards
skipping to change at page 12, line 15 skipping to change at page 12, line 15
global_variable: dfs_number global_variable: dfs_number
DFS_Visit(node x, node parent) DFS_Visit(node x, node parent)
D(x) = dfs_number D(x) = dfs_number
dfs_number += 1 dfs_number += 1
x.dfs_parent = parent x.dfs_parent = parent
for each link (x, w) for each link (x, w)
if D(w) is not set if D(w) is not set
DFS_Visit(w, x) DFS_Visit(w, x)
Run_DFS(node root) Run_DFS(node gadag_root)
dfs_number = 0 dfs_number = 0
DFS_Visit(root, NONE) DFS_Visit(gadag_root, NONE)
Figure 7: Basic Depth-First Search algorithm Figure 7: Basic Depth-First Search algorithm
Given a node x, one can compute the minimal DFS number of the Given a node x, one can compute the minimal DFS number of the
neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the
earliest attachment point neighbouring x. What is interesting, earliest attachment point neighbouring x. What is interesting,
though, is what is the earliest attachment point from x and x's though, is what is the earliest attachment point from x and x's
descendants. This is what is determined by computing the Low-Point descendants. This is what is determined by computing the Low-Point
value. value.
skipping to change at page 13, line 14 skipping to change at page 13, line 14
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.remote_intf 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 ordered_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)
L(x) = D(intf.remote_node) L(x) = D(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
Run_Lowpoint(node root) Run_Lowpoint(node gadag_root)
dfs_number = 0 dfs_number = 0
Lowpoint_Visit(root, NONE, NONE) Lowpoint_Visit(gadag_root, NONE, NONE)
Figure 8: Computing Low-Point value Figure 8: Computing Low-Point value
[E]---| [J]-------[I] [P]---[O] [E]---| [J]-------[I] [P]---[O]
| | | | | | | | | | | |
| | | | | | | | | | | |
[R] [D]---[C]--[F] [H]---[K] [N] [R] [D]---[C]--[F] [H]---[K] [N]
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]--------[B] [G]---| [L]---[M] [A]--------[B] [G]---| [L]---[M]
skipping to change at page 16, line 15 skipping to change at page 16, line 15
[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:
three 2-connected clusters three 2-connected clusters
and one cut-link 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 for destination R (b) MRT-Blue for destination R
skipping to change at page 17, line 40 skipping to change at page 17, line 40
Compute_Localroot(node x, node localroot) Compute_Localroot(node x, node localroot)
x.localroot = localroot x.localroot = localroot
for each DFS child node c of x 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(gadag_root, gadag_root)
Figure 11: A method for computing local-roots Figure 11: A method for computing local-roots
There are two different ways of computing the local-root for each There are two different ways of computing the local-root for each
node. The stand-alone method is given in Figure 11 and better node. The stand-alone method is given in Figure 11 and better
illustrates the concept; it is used by the MRT algorithms given in illustrates the concept; it is used by the 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. Both methods for computing the local-root produce the in Figure 12. Both methods for computing the local-root produce the
skipping to change at page 18, line 47 skipping to change at page 18, line 47
Assign_Block_ID(x, cur_block_id) Assign_Block_ID(x, cur_block_id)
x.block_id = cur_block_id x.block_id = cur_block_id
foreach DFS child c of x foreach DFS child c of x
if (c.local_root is x) if (c.local_root is x)
max_block_id += 1 max_block_id += 1
Assign_Block_ID(c, max_block_id) Assign_Block_ID(c, max_block_id)
else else
Assign_Block_ID(c, cur_block_id) Assign_Block_ID(c, cur_block_id)
max_block_id = 0 max_block_id = 0
Assign_Block_ID(root, max_block_id) Assign_Block_ID(gadag_root, max_block_id)
Figure 13: Assigning block id to identify blocks Figure 13: Assigning block id to identify blocks
5. Algorithm Sections 5. 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
skipping to change at page 19, line 40 skipping to change at page 19, line 40
Blue and MRT-Red. [See Section 5.7.] 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.8.] computing router x should select. [See Section 5.8.]
5.1. Interface Ordering 5.1. Interface Ordering
To ensure consistency in computation, all routers MUST order To ensure consistency in computation, all routers MUST order
interfaces identically down to the set of links with the same metric interfaces identically down to the set of links with the same metric
to the same neighboring node. This is necessary for the DFS, where to the same neighboring node. This is necessary for the DFS in
the selection order of the interfaces to explore results in different Lowpoint_Visit in Section 4.3, where the selection order of the
trees, and for computing the GADAG, where the selection order of the interfaces to explore results in different trees. Consistent
interfaces to use to form ears can result in different GADAGs. The interface ordering is also necessary for computing the GADAG, where
required ordering between two interfaces from the same router x is the selection order of the interfaces to use to form ears can result
given in Figure 14. in different GADAGs. It is also necessary for the topological sort
described in Section 5.8, where different topological sort orderings
can result in undirected links being added to the GADAG in different
directions.
The required ordering between two interfaces from the same router x
is 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.mrt_node_id < b.neighbor.mrt_node_id if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
return A_LESS_THAN_B return A_LESS_THAN_B
if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
return B_LESS_THAN_A return B_LESS_THAN_A
skipping to change at page 20, line 38 skipping to change at page 20, line 38
assigned during the procedure for assigning direction to UNDIRECTED assigned during the procedure for assigning direction to UNDIRECTED
links described in Section 5.6. An implementation is free to apply links described in Section 5.6. An implementation is free to apply
some additional criteria to break ties in interface ordering in this some additional criteria to break ties in interface ordering in this
situation, but that criteria is not specified here since it will not situation, but that criteria is not specified here since it will not
affect the final GADAG produced by the algorithm. affect the final GADAG produced by the algorithm.
The Interface_Compare function in Figure 14 relies on the The Interface_Compare function in Figure 14 relies on the
interface.metric and the interface.neighbor.mrt_node_id values to interface.metric and the interface.neighbor.mrt_node_id values to
order interfaces. The exact source of these values for different order interfaces. The exact source of these values for different
IGPs (or flooding protocol in the case of ISIS-PCR IGPs (or flooding protocol in the case of ISIS-PCR
[I-D.farkas-isis-pcr]) and applications is specified in Figure 15. [I-D.ietf-isis-pcr]) and applications is specified in Figure 15. The
The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided
provided here is normative. The metric and mrt_node_id values for here is normative. The metric and mrt_node_id values for ISIS-PCR
ISIS-PCR should be considered informational. should be considered informational.
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id | metric of | | IGP/flooding | mrt_node_id | metric of |
| protocol | of neighbor | interface | | protocol | of neighbor | interface |
| and | on interface | | | and | on interface | |
| application | | | | application | | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | | OSPFv2 for | 4 octet Neighbor | 2 octet Metric field |
| IP/LDP FRR | Router ID in | for corresponding | | IP/LDP FRR | Router ID in | for corresponding |
| | Link ID field for | point-to-point link | | | Link ID field for | point-to-point link |
skipping to change at page 25, line 38 skipping to change at page 25, line 38
cur_node = cur_node.lowpoint_parent cur_node = cur_node.lowpoint_parent
else // ear_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 (ear_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
x.IS_CUT_VERTEX = true
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, gadag_root)
root.IN_GADAG = true gadag_root.IN_GADAG = true
root.localroot = None gadag_root.localroot = None
Initialize Stack to empty Initialize Stack to empty
push root onto Stack push gadag_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 ordered_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 ordered_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, gadag_root)
Figure 17: Low-point Inheritance GADAG algorithm Figure 17: Low-point Inheritance GADAG algorithm
5.6. Augmenting the GADAG by directing all links 5.6. Augmenting the GADAG by directing all links
The GADAG, regardless of the algorithm used to construct it, at this The GADAG, regardless of the 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.
The goal is thus to assign direction to every remaining link marked The goal is thus to assign direction to every remaining link marked
as UNDIRECTED to improve the paths and number of paths found when the as UNDIRECTED to improve the paths and number of paths found when the
skipping to change at page 26, line 46 skipping to change at page 26, line 47
partial order described by the GADAG. This can be done using Kahn's partial order described by the GADAG. This can be done using Kahn's
topological sort[Kahn_1962_topo_sort] which essentially assigns a topological sort[Kahn_1962_topo_sort] which essentially assigns a
number to a node x only after all nodes before it (e.g. with a link number to a node x only after all nodes before it (e.g. with a link
incoming to x) have had their numbers assigned. The only issue with incoming to x) have had their numbers assigned. The only issue with
the topological sort is that it works on DAGs and not ADAGs or the topological sort is that it works on DAGs and not ADAGs or
GADAGs. GADAGs.
To convert a GADAG to a DAG, it is necessary to remove all links that To convert a GADAG to a DAG, it is necessary to remove all links that
point to a root of block from within that block. That provides the point to a root of block from within that block. That provides the
necessary conversion to a DAG and then a topological sort can be necessary conversion to a DAG and then a topological sort can be
done. Finally, all UNDIRECTED links are assigned a direction based done. When adding undirected links to the GADAG, links connecting
upon the total ordering. Any UNDIRECTED links that connect to a root the block root to other nodes in that block need special handling
of a block from within that block are assigned a direction INCOMING because the topological order will not always give the right answer
to that root. The exact details of this whole process are captured for those links. There are three cases to consider. If the
in Figure 18 undirected link in question has another parallel link between the
Set_Block_Root_Incoming_Links(topo, root, mark_or_clear) same two nodes that is already directed, then the direction of the
undirected link can be inherited from the previously directed link.
In the case of parallel cut links, we set all of the parallel links
to both INCOMING and OUTGOING. Otherwise, the undirected link in
question is set to OUTGOING from the block root node. A cut-link can
then be identified by the fact that it will be directed both INCOMING
and OUTGOING in the GADAG. The exact details of this whole process
are captured in Figure 18
Add_Undirected_Block_Root_Links(topo, gadag_root):
foreach node x in topo foreach node x in topo
if node x is a cut-vertex or root if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x foreach interface i of x
if (i.remote_node.localroot is x) if (i.remote_node.localroot is not x
if i.UNDIRECTED or i.PROCESSED )
i.OUTGOING = true continue
i.remote_intf.INCOMING = true Initialize bundle_list to empty
i.UNDIRECTED = false bundle.UNDIRECTED = true
i.remote_intf.UNDIRECTED = false bundle.OUTGOING = false
if i.INCOMING bundle.INCOMING = false
if mark_or_clear is MARK foreach interface i2 in x
if i.OUTGOING // a cut-link if i2.remote_node is i.remote_node
i.STORE_INCOMING = true add_to_list_end(bundle_list, i2)
i.INCOMING = false if not i2.UNDIRECTED:
i.remote_intf.STORE_OUTGOING = true bundle.UNDIRECTED = false
i.remote_intf.OUTGOING = false if i2.INCOMING:
i.TEMP_UNUSABLE = true bundle.INCOMING = true
i.remote_intf.TEMP_UNUSABLE = true if i2.OUTGOING:
else bundle.OUTGOING = true
i.TEMP_UNUSABLE = false if bundle.UNDIRECTED
i.remote_intf.TEMP_UNUSABLE = false foreach interface i3 in bundle_list
if i.STORE_INCOMING and (mark_or_clear is CLEAR) i3.UNDIRECTED = false
i.INCOMING = true i3.remote_intf.UNDIRECTED = false
i.STORE_INCOMING = false i3.PROCESSED = true
i.remote_intf.OUTGOING = true i3.remote_intf.PROCESSED = true
i.remote_intf.STORE_OUTGOING = false i3.OUTGOING = true
i3.remote_intf.INCOMING = true
else
if (bundle.OUTGOING and bundle.INCOMING)
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.INCOMING = true
i3.remote_intf.INCOMING = true
i3.remote_intf.OUTGOING = true
Run_Topological_Sort_GADAG(topo, root) else if bundle.OUTGOING
Set_Block_Root_Incoming_Links(topo, root, MARK) foreach interface i3 in bundle_list
foreach node x i3.UNDIRECTED = false
set x.unvisited to the count of x's incoming interfaces i3.remote_intf.UNDIRECTED = false
that aren't marked TEMP_UNUSABLE i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.OUTGOING = true
i3.remote_intf.INCOMING = true
else if bundle.INCOMING
foreach interface i3 in bundle_list
i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true
i3.remote_intf.PROCESSED = true
i3.INCOMING = true
i3.remote_intf.OUTGOING = true
Modify_Block_Root_Incoming_Links(topo, gadag_root):
foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING:
i.INCOMING = false
i.INCOMING_STORED = true
i.remote_intf.OUTGOING = false
i.remote_intf.OUTGOING_STORED = true
Revert_Block_Root_Incoming_Links(topo, gadag_root):
foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x
if i.remote_node.localroot is x
if i.INCOMING_STORED:
i.INCOMING = true
i.remote_intf.OUTGOING = true
i.INCOMING_STORED = false
i.remote_intf.OUTGOING_STORED = false
Run_Topological_Sort_GADAG(topo, gadag_root):
Modify_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo:
node.unvisited = 0
foreach interface i of x:
if (i.INCOMING):
node.unvisited += 1
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, gadag_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 ordered_interface i of y
if (i.OUTGOING) and (not i.TEMP_UNUSABLE) if intf.OUTGOING
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) Revert_Block_Root_Incoming_Links(topo, gadag_root)
Add_Undirected_Links(topo, root) def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):
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, gadag_root)
Add_Undirected_Block_Root_Links(topo, gadag_root)
Run_Topological_Sort_GADAG(topo, gadag_root)
Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
Add_Undirected_Links(topo, gadag_root)
Figure 18: 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.9. selected is given in Section 5.9.
5.7. Compute MRT next-hops 5.7. Compute MRT next-hops
skipping to change at page 33, line 47 skipping to change at page 35, line 28
5.7.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 23. 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.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) Store_Results(y, direction)
if direction is FORWARD if direction is FORWARD
y.higher = true y.higher = true
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 y.red_next_hops = y.next_hops
SPF_No_Traverse_Root(spf_root, block_root, direction) SPF_No_Traverse_Block_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) 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) ) ((direction is REVERSE) and intf.INCOMING) )
and 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.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, gadag_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_Block_Root(x, x.localroot, FORWARD)
SPF_No_Traverse_Root(x, x.localroot, REVERSE) SPF_No_Traverse_Block_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.block_id is x.block_id) ) (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 gadag_root
root.blue_next_hops = x.localroot.blue_next_hops gadag_root.blue_next_hops = x.localroot.blue_next_hops
root.red_next_hops = x.localroot.red_next_hops gadag_root.red_next_hops = x.localroot.red_next_hops
root.order_proxy = x.localroot gadag_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 gadag_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(gadag_root, max_block_id)
Compute_MRT_NextHops(x, root) Compute_MRT_NextHops(x, gadag_root)
Figure 23 Figure 23
5.8. 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 or MRT-Red next-hops as the alternate next-hop(s) for
next hop or to use the MRT-Red next-hops. The algorithm is given in that primary next hop. The algorithm is given in Figure 24 and
Figure 24 and discussed afterwards. discussed afterwards.
Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order)
//When D==F, we can do only link protection
if ((D is F) or (D.order_proxy is F))
if an MRT doesn't use primary_intf
indicate alternate is not node-protecting
return that MRT color
else // parallel links are cut-links
return AVOID_LINK_ON_BLUE
if (D_lower and D_higher and F.lower and F.higher)
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
if (D_lower and D_higher) Select_Alternates_Internal(D, F, primary_intf,
if F.higher D_lower, D_higher, D_topo_order):
return USE_RED if D_higher and D_lower
else if F.HIGHER and F.LOWER
return USE_BLUE if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
if F.HIGHER
return USE_RED
if F.LOWER
return USE_BLUE
else if D_higher
if F.HIGHER and F.LOWER
return USE_BLUE
if F.LOWER
return USE_BLUE
if F.HIGHER
if (F.topo_order > D_topo_order)
return USE_BLUE
if (F.topo_order < D_topo_order)
return USE_RED
else if D_lower
if F.HIGHER and F.LOWER
return USE_RED
if F.HIGHER
return USE_RED
if F.LOWER
if F.topo_order > D_topo_order
return USE_BLUE
if F.topo_order < D_topo_order
return USE_RED
else //D is unordered wrt S
if F.HIGHER and F.LOWER
if primary_intf.OUTGOING and primary_intf.INCOMING
// this case should not occur
if primary_intf.OUTGOING
return USE_BLUE
if primary_intf.INCOMING
return USE_RED
if F.LOWER
return USE_RED
if F.HIGHER
return USE_BLUE
if (F.lower and F.higher) Select_Alternates(D, F, primary_intf)
if D_lower if (D is F) or (D.order_proxy is F)
return USE_RED return PRIM_NH_IS_D_OR_OP_FOR_D
else if D_higher D_lower = D.order_proxy.LOWER
return USE_BLUE D_higher = D.order_proxy.HIGHER
else D_topo_order = D.order_proxy.topo_order
if primary_intf.OUTGOING and primary_intf.INCOMING return Select_Alternates_Internal(D, F, primary_intf,
return AVOID_LINK_ON_BLUE D_lower, D_higher, D_topo_order)
if primary_intf.OUTGOING
return USE_BLUE
if primary_intf.INCOMING
return USE_RED
if D_higher Figure 24
if F.higher
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
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_RED
else if F.higher
return USE_BLUE
else
// F and S are neighbors so either F << S or F >> S
Select_Alternates(S, D, F, primary_intf) It is useful to first handle the case where where F is also D, or F
if D.order_proxy is not D is the order proxy for D. In this case, only link protection is
D_lower = D.order_proxy.lower possible. The MRT that doesn't use the failed primary next-hop is
D_higher = D.order_proxy.higher used. If both MRTs use the primary next-hop, then the primary next-
D_topo_order = D.order_proxy.topo_order hop must be a cut-link, so either MRT could be used but the set of
else MRT next-hops must be pruned to avoid the failed primary next-hop
D_lower = D.lower interface. To indicate this case, Select_Alternates returns
D_higher = D.higher PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three
D_topo_order = D.topo_order sub-cases above is not provided.
return Select_Alternates_Internal(S, D, F, primary_intf,
D_lower, D_higher, D_topo_order)
Figure 24 The logic behind Select_Alternates_Internal is described in
Figure 25. As an example, consider the first case described in the
table, where the D>>S and D<<S. If this is true, then either S or D
must be the block root, R. If F>>S and F<<S, then S is the block
root. So the blue path from S to D is the increasing path to D, and
the red path S to D is the decreasing path to D. If the
F.topo_order<D.topo_order, then either F is ordered higher than D or
F is unordered with respect to D. Therefore, F is either on a
decreasing path from S to D, or it is on neither an increasing nor a
decreasing path from S to D. In either case, it is safe to take an
increasing path from S to D to avoid F. We know that when S is R,
the increasing path is the blue path, so it is safe to use the blue
path to avoid F.
If either D>>S>>F or D<<S<<F holds true, the situation is simple: in If instead F.topo_order>D.topo_order, then either F is ordered lower
the first case we should choose the increasing Blue next-hop, in the than D, or F is unordered with respect to D. Therefore, F is either
second case, the decreasing Red next-hop is the right choice. on an increasing path from S to D, or it is on neither an increasing
nor a decreasing path from S to D. In either case, it is safe to
take a decreasing path from S to D to avoid F. We know that when S
is R, the decreasing path is the red path, so it is safe to use the
red path to avoid F.
However, when both D and F are greater than S the situation is not so If F>>S or F<<S (but not both), then D is the block root. We then
simple, there can be three possibilities: (i) F>>D (ii) F<<D or (iii) know that the blue path from S to D is the increasing path to R, and
F and D are not ordered. In the first case, we should choose the the red path is the decreasing path to R. When F>>S, we deduce that
path towards D along the Blue tree. In contrast, in case (ii) the F is on an increasing path from S to R. So in order to avoid F, we
Red path towards the root and then to D would be the solution. use a decreasing path from S to R, which is the red path. Instead,
Finally, in case (iii) both paths would be acceptable. However, when F<<S, we deduce that F is on a decreasing path from S to R. So
observe that if e.g. F.topo_order>D.topo_order, either case (i) or in order to avoid F, we use an increasing path from S to R, which is
case (iii) holds true, which means that selecting the Blue next-hop the blue path.
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, All possible cases are systematically described in the same manner in
so it is impossible that S and F are not ordered. But it is possible the rest of the table.
that S and D are not ordered, so we need to deal with this case as
well. If F<<S, we can use the Red next-hop, because that path is
first increasing until a node definitely greater than D is reached,
then decreasing; this path must avoid using F. Similarly, if F>>S,
we should use the Blue next-hop.
Additionally, the cases where either F or D is ordered both higher +------+------------+------+------------------------------+------------+
and lower must be considered; this can happen when one is a block- | D | MRT blue | F | additional | F | Alternate |
root or its order_proxy is. If D is both higher and lower than S, | wrt | and red | wrt | criteria | wrt | |
then the MRT to use is the one that avoids F so if F is higher, then | S | path | S | | MRT | |
the MRT-Red should be used and if F is lower, then the MRT-Blue | | properties | | | (deduced) | |
should be used; F and S must be ordered because they are neighbors. +------+------------+------+-----------------+------------+------------+
If F is both higher and lower, then if D is lower, using the MRT-Red | D>>S | Blue path: | F>>S | additional | F on an | Use Red |
to decrease reaches D and if D is higher, using the Blue MRT to | and | Increasing | only | criteria | increasing | to avoid |
increase reaches D; if D is unordered compared to S, then the | D<<S,| path to R. | | not needed | path from | F |
situation is a bit more complicated. | D is | Red path: | | | S to R | |
| R, | Decreasing +------+-----------------+------------+------------+
| | path to R. | F<<S | additional | F on a | Use Blue |
| | | only | criteria | decreasing | to avoid |
| | | | not needed | path from | F |
| or | | | | S to R | |
| | +------+-----------------+------------+------------+
| | | F>>S | topo(F)>topo(D) | F on a | Use Blue |
| S is | Blue path: | and | implies that | decreasing | to avoid |
| R | Increasing | F<<S | F>>D or F??D | path from | F |
| | path to D. | | | S to D or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | path to D. | | topo(F)<topo(D) | F on an | Use Red |
| | | | implies that | increasing | to avoid |
| | | | F<<D or F??D | path from | F |
| | | | | S to D or | |
| | | | | neither | |
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F<<S | additional | F on | Use Blue |
| only | Increasing | only | criteria | decreasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to D. +------+-----------------+------------+------------+
| | Red path: | F>>S | topo(F)>topo(D) | F on | Use Blue |
| | Decreasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | S to R, | | | or | |
| | then | | | neither | |
| | decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | R to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Red | Use Blue |
| | | and | criteria | | to avoid |
| | | F<<S,| not needed | | F |
| | | F is | | | |
| | | R | | | |
+------+------------+------+-----------------+------------+------------+
| D<<S | Blue path: | F>>S | additional | F on | Use Red |
| only | Increasing | only | criteria | increasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to R, +------+-----------------+------------+------------+
| | then | F<<S | topo(F)>topo(D) | F on | Use Blue |
| | increasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | R to D. | | | or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | S to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Blue | Use Red |
| | | and | criteria | | to avoid |
| | | F<<S,| not | | F |
| | | F is | needed | | |
| | | R | | | |
+------+------------+------+-----------------+------------+------------+
| D??S | Blue path: | F<<S | additional | F on a | Use Red |
| | Decr. from | only | criteria | decreasing | to avoid |
| | S to first | | not needed | path from | F |
| | node H>>D, | | | S to H. | |
| | then incr. +------+-----------------+------------+------------+
| | to D. | F>>S | additional | F on an | Use Blue |
| | Red path: | only | criteria | increasing | to avoid |
| | Incr. from | | not needed | path from | F |
| | S to first | | | S to G | |
| | node G<<D, | | | | |
| | then decr. | | | | |
| | +------+-----------------+------------+------------+
| | | F>>S | GADAG link | F on an | Use Blue |
| | | and | direction | incr. path | to avoid |
| | | F<<S,| S->F | from S | F |
| | | F is +-----------------+------------+------------+
| | | R | GADAG link | F on a | Use Red |
| | | | direction | decr. path | to avoid |
| | | | S<-F | from S | F |
| | | +-----------------+------------+------------+
| | | | GADAG link | Implies F is the order |
| | | | direction | proxy for D, which has |
| | | | S<-->F | already been handled. |
+------+------------+------+-----------------+------------+------------+
In the case where F<<S<<F and D and S are unordered, the direction of Figure 25: determining MRT next-hops and alternates based on the
the link in the GADAG between S and F should be examined. If the partial order and topological sort relationships between the
link is directed S -> F, then use the MRT-Blue (decrease to avoid
that link and then increase). If the link is directed S <- F, then
use the MRT-Red (increase to avoid that link and then decrease). If
the link is S <--> F, then the link must be a cut-link and there is
no node-protecting alternate. If there are multiple links between S
and F, then they can protect against each other; of course, in this
situation, they are probably already ECMP.
Finally, there is the case where D is also F. In this case, only source(S), destination(D), primary next-hop(F), and block root(R).
link protection is possible. The MRT that doesn't use the indicated topo(N) indicates the topological sort value of node N. X??Y
primary next-hop is used. If both MRTs use the primary next-hop, indicates that node X is unordered with respect to node Y. It is
then the primary next-hop must be a cut-link so either MRT could be assumed that the case where F is D, or where F is the order proxy for
used but the set of MRT next-hops must be pruned to avoid that D, has already been handled.
primary next-hop. To indicate this case, Select_Alternates returns
AVOID_LINK_ON_BLUE.
As an example, consider the ADAG depicted in Figure 25 and first As an example, consider the ADAG depicted in Figure 26 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.
skipping to change at page 39, line 24 skipping to change at page 42, line 33
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[R] [C] [G]->[I] [R] [C] [G]->[I]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[A]->[B]->[F]---| [A]->[B]->[F]---|
(a)ADAG rooted at R for (a)ADAG rooted at R for
a 2-connected graph a 2-connected graph
Figure 25 Figure 26
5.9. 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.
skipping to change at page 41, line 6 skipping to change at page 44, 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 42, line 19 skipping to change at page 45, 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 26 Figure 27
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.7 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.
skipping to change at page 42, line 41 skipping to change at page 45, line 41
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].
Implementations SHOULD implement the Select_Alternates() function to Implementations SHOULD implement the Select_Alternates() function to
pick an MRT-FRR alternate. pick an MRT-FRR alternate.
7. Algorithm Alternatives and Evaluation 7. Python Implementation of MRT Lowpoint Algorithm
Below is Python code implementing the MRT Lowpoint algorithm
specified in this document. In order to avoid the page breaks in the
.txt version of the draft, one can cut and paste the Python code from
the .xml version. The code is also posted on Github.
<CODE BEGINS>
# This program has been tested to run on Python 2.6 and 2.7
# (specifically Python 2.6.6 and 2.7.8 were tested).
# The program has known incompatibilities with Python 3.X.
# When executed, this program will generate a text file describing
# an example topology. It then reads that text file back in as input
# to create the example topology, and runs the MRT algorithm.This
# was done to simplify the inclusion of the program as a single text
# file that can be extracted from the IETF draft.
# The output of the program is four text files containing a description
# of the GADAG, the blue and red MRTs for all destinations, and the
# MRT alternates for all failures.
import heapq
# simple Class definitions allow structure-like dot notation for
# variables and a convenient place to initialize those variables.
class Topology:
pass
class Node:
pass
class Interface:
pass
class Bundle:
pass
class Alternate:
def __init__(self):
self.failed_intf = None
self.nh_list = []
self.fec = 'NO_ALTERNATE'
self.prot = 'NO_PROTECTION'
self.info = 'NONE'
def Interface_Compare(intf_a, intf_b):
if intf_a.metric < intf_b.metric:
return -1
if intf_b.metric < intf_a.metric:
return 1
if intf_a.remote_node.node_id < intf_b.remote_node.node_id:
return -1
if intf_b.remote_node.node_id < intf_a.remote_node.node_id:
return 1
return 0
def Sort_Interfaces(topo):
for node in topo.island_node_list:
node.island_intf_list.sort(Interface_Compare)
def Initialize_Node(node):
node.intf_list = []
node.island_intf_list = []
node.profile_id_list = [0]
node.GR_sel_priority = 128
node.IN_MRT_ISLAND = False
node.IN_GADAG = False
node.dfs_number = None
node.dfs_parent = None
node.dfs_parent_intf = None
node.dfs_child_list = []
node.lowpoint_number = None
node.lowpoint_parent = None
node.lowpoint_parent_intf = None
node.localroot = None
node.block_id = None
node.IS_CUT_VERTEX = False
node.blue_next_hops_dict = {}
node.red_next_hops_dict = {}
node.pnh_dict = {}
node.alt_dict = {}
def Initialize_Intf(intf):
intf.metric = None
intf.area = None
intf.MRT_INELIGIBLE = False
intf.IGP_EXCLUDED = False
intf.UNDIRECTED = True
intf.INCOMING = False
intf.OUTGOING = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
intf.PROCESSED = False
intf.IN_MRT_ISLAND = False
def Reset_Computed_Node_and_Intf_Values(topo):
for node in topo.node_list:
node.IN_MRT_ISLAND = False
node.IN_GADAG = False
node.dfs_number = None
node.dfs_parent = None
node.dfs_parent_intf = None
node.dfs_child_list = []
node.lowpoint_number = None
node.lowpoint_parent = None
node.lowpoint_parent_intf = None
node.localroot = None
node.block_id = None
node.IS_CUT_VERTEX = False
for intf in node.intf_list:
intf.UNDIRECTED = True
intf.INCOMING = False
intf.OUTGOING = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
intf.IN_MRT_ISLAND = False
# This function takes a file with links represented by 2-digit
# numbers in the format:
# 01,05,10
# 05,02,30
# 02,01,15
# which represents a triangle topology with nodes 01, 05, and 02
# and symmetric metrics of 10, 30, and 15.
# Inclusion of a fourth column makes the metrics for the link
# asymmetric. An entry of:
# 02,07,10,15
# creates a link from node 02 to 07 with metrics 10 and 15.
def Create_Topology_From_File(filename):
topo = Topology()
topo.gadag_root = None
topo.node_list = []
topo.node_dict = {}
topo.island_node_list = []
topo.prefix_list = [] # possibly no longer needed
node_id_set= set()
cols_list = []
# on first pass just create nodes
with open(filename) as topo_file:
for line in topo_file:
line = line.rstrip('\r\n')
cols=line.split(',')
cols_list.append(cols)
nodea_node_id = int(cols[0])
nodeb_node_id = int(cols[1])
if (nodea_node_id > 999 or nodeb_node_id > 999):
print("node_id must be between 0 and 999.")
print("exiting.")
exit()
node_id_set.add(nodea_node_id)
node_id_set.add(nodeb_node_id)
for node_id in node_id_set:
node = Node()
node.node_id = node_id
Initialize_Node(node)
topo.node_list.append(node)
topo.node_dict[node_id] = node
# on second pass create interfaces
for cols in cols_list:
nodea_node_id = int(cols[0])
nodeb_node_id = int(cols[1])
metric = int(cols[2])
reverse_metric = int(cols[2])
if len(cols) > 3:
reverse_metric=int(cols[3])
nodea = topo.node_dict[nodea_node_id]
nodeb = topo.node_dict[nodeb_node_id]
nodea_intf = Interface()
Initialize_Intf(nodea_intf)
nodea_intf.metric = metric
nodea_intf.area = 0
nodeb_intf = Interface()
Initialize_Intf(nodeb_intf)
nodeb_intf.metric = reverse_metric
nodeb_intf.area = 0
nodea_intf.remote_intf = nodeb_intf
nodeb_intf.remote_intf = nodea_intf
nodea_intf.remote_node = nodeb
nodeb_intf.remote_node = nodea
nodea_intf.local_node = nodea
nodeb_intf.local_node = nodeb
nodea_intf.link_data = len(nodea.intf_list)
nodeb_intf.link_data = len(nodeb.intf_list)
nodea.intf_list.append(nodea_intf)
nodeb.intf_list.append(nodeb_intf)
return topo
def MRT_Island_Identification(topo, computing_rtr, profile_id, area):
if profile_id in computing_rtr.profile_id_list:
computing_rtr.IN_MRT_ISLAND = True
explore_list = [computing_rtr]
else:
return
while explore_list != []:
next_rtr = explore_list.pop()
for intf in next_rtr.intf_list:
if ( not intf.MRT_INELIGIBLE and not intf.IGP_EXCLUDED
and intf.area == area ):
if (profile_id in intf.remote_node.profile_id_list):
intf.IN_MRT_ISLAND = True
if (not intf.remote_node.IN_MRT_ISLAND):
intf.remote_node.IN_MRT_ISLAND = True
explore_list.append(intf.remote_node)
def Set_Island_Intf_and_Node_Lists(topo):
topo.island_node_list = []
for node in topo.node_list:
node.island_intf_list = []
if node.IN_MRT_ISLAND:
topo.island_node_list.append(node)
for intf in node.intf_list:
if intf.IN_MRT_ISLAND:
node.island_intf_list.append(intf)
global_dfs_number = None
def Lowpoint_Visit(x, parent, intf_p_to_x):
global global_dfs_number
x.dfs_number = global_dfs_number
x.lowpoint_number = x.dfs_number
global_dfs_number += 1
x.dfs_parent = parent
if intf_p_to_x == None:
x.dfs_parent_intf = None
else:
x.dfs_parent_intf = intf_p_to_x.remote_intf
x.lowpoint_parent = None
if parent != None:
parent.dfs_child_list.append(x)
for intf in x.island_intf_list:
if intf.remote_node.dfs_number == None:
Lowpoint_Visit(intf.remote_node, x, intf)
if intf.remote_node.lowpoint_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.lowpoint_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else:
if intf.remote_node is not parent:
if intf.remote_node.dfs_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.dfs_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
def Run_Lowpoint(topo):
global global_dfs_number
global_dfs_number = 0
Lowpoint_Visit(topo.gadag_root, None, None)
# addresses these cases.
max_block_id = None
def Assign_Block_ID(x, cur_block_id):
global max_block_id
x.block_id = cur_block_id
for c in x.dfs_child_list:
if (c.localroot is x):
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else:
Assign_Block_ID(c, cur_block_id)
def Run_Assign_Block_ID(topo):
global max_block_id
max_block_id = 0
Assign_Block_ID(topo.gadag_root, max_block_id)
def Construct_Ear(x, stack, intf, ear_type):
ear_list = []
cur_intf = intf
not_done = True
while not_done:
cur_intf.UNDIRECTED = False
cur_intf.OUTGOING = True
cur_intf.remote_intf.UNDIRECTED = False
cur_intf.remote_intf.INCOMING = True
if cur_intf.remote_node.IN_GADAG == False:
cur_intf.remote_node.IN_GADAG = True
ear_list.append(cur_intf.remote_node)
if ear_type == 'CHILD':
cur_intf = cur_intf.remote_node.lowpoint_parent_intf
else:
assert ear_type == 'NEIGHBOR'
cur_intf = cur_intf.remote_node.dfs_parent_intf
else:
not_done = False
if ear_type == 'CHILD' and cur_intf.remote_node is x:
# x is a cut-vertex and the local root for the block
# in which the ear is computed
x.IS_CUT_VERTEX = True
localroot = x
else:
# inherit local root from the end of the ear
localroot = cur_intf.remote_node.localroot
while ear_list != []:
y = ear_list.pop()
y.localroot = localroot
stack.append(y)
def Construct_GADAG_via_Lowpoint(topo):
gadag_root = topo.gadag_root
gadag_root.IN_GADAG = True
gadag_root.localroot = None
stack = []
stack.append(gadag_root)
while stack != []:
x = stack.pop()
for intf in x.island_intf_list:
if ( intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is x ):
Construct_Ear(x, stack, intf, 'CHILD' )
for intf in x.island_intf_list:
if (intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is not x):
Construct_Ear(x, stack, intf, 'NEIGHBOR')
def Assign_Remaining_Lowpoint_Parents(topo):
for node in topo.island_node_list:
if ( node is not topo.gadag_root
and node.lowpoint_parent == None ):
node.lowpoint_parent = node.dfs_parent
node.lowpoint_parent_intf = node.dfs_parent_intf
node.lowpoint_number = node.dfs_parent.dfs_number
def Add_Undirected_Block_Root_Links(topo):
for node in topo.island_node_list:
if node.IS_CUT_VERTEX or node is topo.gadag_root:
for intf in node.island_intf_list:
if ( intf.remote_node.localroot is not node
or intf.PROCESSED ):
continue
bundle_list = []
bundle = Bundle()
bundle.UNDIRECTED = True
bundle.OUTGOING = False
bundle.INCOMING = False
for intf2 in node.island_intf_list:
if intf2.remote_node is intf.remote_node:
bundle_list.append(intf2)
if not intf2.UNDIRECTED:
bundle.UNDIRECTED = False
if intf2.INCOMING:
bundle.INCOMING = True
if intf2.OUTGOING:
bundle.OUTGOING = True
if bundle.UNDIRECTED:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
else:
if (bundle.OUTGOING and bundle.INCOMING):
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.INCOMING = True
intf3.remote_intf.INCOMING = True
intf3.remote_intf.OUTGOING = True
elif bundle.OUTGOING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
elif bundle.INCOMING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.INCOMING = True
intf3.remote_intf.OUTGOING = True
def Modify_Block_Root_Incoming_Links(topo):
for node in topo.island_node_list:
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
for intf in node.island_intf_list:
if intf.remote_node.localroot is node:
if intf.INCOMING:
intf.INCOMING = False
intf.INCOMING_STORED = True
intf.remote_intf.OUTGOING = False
intf.remote_intf.OUTGOING_STORED = True
def Revert_Block_Root_Incoming_Links(topo):
for node in topo.island_node_list:
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
for intf in node.island_intf_list:
if intf.remote_node.localroot is node:
if intf.INCOMING_STORED:
intf.INCOMING = True
intf.remote_intf.OUTGOING = True
intf.INCOMING_STORED = False
intf.remote_intf.OUTGOING_STORED = False
def Run_Topological_Sort_GADAG(topo):
Modify_Block_Root_Incoming_Links(topo)
for node in topo.island_node_list:
node.unvisited = 0
for intf in node.island_intf_list:
if (intf.INCOMING == True):
node.unvisited += 1
working_list = []
topo_order_list = []
working_list.append(topo.gadag_root)
while working_list != []:
y = working_list.pop(0)
topo_order_list.append(y)
for intf in y.island_intf_list:
if ( intf.OUTGOING == True):
intf.remote_node.unvisited -= 1
if intf.remote_node.unvisited == 0:
working_list.append(intf.remote_node)
next_topo_order = 1
while topo_order_list != []:
y = topo_order_list.pop(0)
y.topo_order = next_topo_order
next_topo_order += 1
Revert_Block_Root_Incoming_Links(topo)
def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):
for node in topo.island_node_list:
for intf in node.island_intf_list:
if intf.UNDIRECTED:
if node.topo_order < intf.remote_node.topo_order:
intf.OUTGOING = True
intf.UNDIRECTED = False
intf.remote_intf.INCOMING = True
intf.remote_intf.UNDIRECTED = False
else:
intf.INCOMING = True
intf.UNDIRECTED = False
intf.remote_intf.OUTGOING = True
intf.remote_intf.UNDIRECTED = False
def Initialize_Temporary_Interface_Flags(topo):
for node in topo.island_node_list:
for intf in node.island_intf_list:
intf.PROCESSED = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
def Add_Undirected_Links(topo):
Initialize_Temporary_Interface_Flags(topo)
Add_Undirected_Block_Root_Links(topo)
Run_Topological_Sort_GADAG(topo)
Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
def In_Common_Block(x,y):
if ( (x.block_id == y.block_id)
or ( x is y.localroot) or (y is x.localroot) ):
return True
return False
def Copy_List_Items(target_list, source_list):
del target_list[:] # Python idiom to remove all elements of a list
for element in source_list:
target_list.append(element)
def Add_Item_To_List_If_New(target_list, item):
if item not in target_list:
target_list.append(item)
def Store_Results(y, direction):
if direction == 'INCREASING':
y.HIGHER = True
Copy_List_Items(y.blue_next_hops, y.next_hops)
if direction == 'DECREASING':
y.LOWER = True
Copy_List_Items(y.red_next_hops, y.next_hops)
if direction == 'NORMAL_SPF':
y.primary_spf_metric = y.spf_metric
Copy_List_Items(y.primary_next_hops, y.next_hops)
if direction == 'MRT_ISLAND_SPF':
Copy_List_Items(y.mrt_island_next_hops, y.next_hops)
if direction == 'COLLAPSED_SPF':
y.collapsed_metric = y.spf_metric
Copy_List_Items(y.collapsed_next_hops, y.next_hops)
# Note that the Python heapq fucntion allows for duplicate items,
# so we use the 'spf_visited' property to only consider a node
# as min_node the first time it gets removed from the heap.
def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction):
spf_heap = []
for y in topo.island_node_list:
y.spf_metric = 2147483647 # 2^31-1
y.next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric, spf_root.node_id, spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, direction)
if ( (min_node is spf_root) or (min_node is not block_root) ):
for intf in min_node.island_intf_list:
if ( ( (direction == 'INCREASING' and intf.OUTGOING )
or (direction == 'DECREASING' and intf.INCOMING ) )
and In_Common_Block(spf_root, intf.remote_node) ) :
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
def Normal_SPF(topo, spf_root):
spf_heap = []
for y in topo.node_list:
y.spf_metric = 2147483647 # 2^31-1 as max metric
y.next_hops = []
y.primary_spf_metric = 2147483647
y.primary_next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric,spf_root.node_id,spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, 'NORMAL_SPF')
for intf in min_node.intf_list:
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
def Set_Edge(y):
if (y.blue_next_hops == [] and y.red_next_hops == []):
Set_Edge(y.localroot)
Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops)
Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops)
y.order_proxy = y.localroot.order_proxy
def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
y.HIGHER = False
y.LOWER = False
y.red_next_hops = []
y.blue_next_hops = []
y.order_proxy = y
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING')
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING')
for y in topo.island_node_list:
if ( y is not x and (y.block_id == x.block_id) ):
assert (not ( y is x.localroot or x is y.localroot) )
assert(not (y.HIGHER and y.LOWER) )
if y.HIGHER == True:
Copy_List_Items(y.red_next_hops,
x.localroot.red_next_hops)
elif y.LOWER == True:
Copy_List_Items(y.blue_next_hops,
x.localroot.blue_next_hops)
else:
Copy_List_Items(y.blue_next_hops,
x.localroot.red_next_hops)
Copy_List_Items(y.red_next_hops,
x.localroot.blue_next_hops)
# Inherit x's MRT next-hops to reach the GADAG root
# from x's MRT next-hops to reach its local root,
# but first check if x is the gadag_root (in which case
# x does not have a local root) or if x's local root
# is the gadag root (in which case we already have the
# x's MRT next-hops to reach the gadag root)
if x is not topo.gadag_root and x.localroot is not topo.gadag_root:
Copy_List_Items(topo.gadag_root.blue_next_hops,
x.localroot.blue_next_hops)
Copy_List_Items(topo.gadag_root.red_next_hops,
x.localroot.red_next_hops)
topo.gadag_root.order_proxy = x.localroot
# Inherit next-hops and order_proxies to other blocks
for y in topo.island_node_list:
if (y is not topo.gadag_root and y is not x ):
Set_Edge(y)
def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
if y is x:
continue
x.blue_next_hops_dict[y.node_id] = []
x.red_next_hops_dict[y.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[y.node_id],
y.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[y.node_id],
y.red_next_hops)
def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
x.pnh_dict[y.node_id] = []
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
x.alt_dict[y.node_id] = []
Copy_List_Items(x.alt_dict[y.node_id], y.alt_list)
def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.blue_next_hops_dict[P.node_id] = []
x.red_next_hops_dict[P.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[P.node_id],
P.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[P.node_id],
P.red_next_hops)
if P.convert_blue_to_green:
x.blue_to_green_nh_dict[P.node_id] = True
if P.convert_red_to_green:
x.red_to_green_nh_dict[P.node_id] = True
def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.alt_dict[P.node_id] = []
Copy_List_Items(x.alt_dict[P.node_id],
P.alt_list)
def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x):
for y in topo.node_list:
x.pnh_dict[y.node_id] = []
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.pnh_dict[P.node_id] = []
Copy_List_Items(x.pnh_dict[P.node_id],
P.primary_next_hops)
def Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order):
if D_higher and D_lower:
if F.HIGHER and F.LOWER:
if F.topo_order > D_topo_order:
return 'USE_BLUE'
else:
return 'USE_RED'
if F.HIGHER:
return 'USE_RED'
if F.LOWER:
return 'USE_BLUE'
assert(False)
if D_higher:
if F.HIGHER and F.LOWER:
return 'USE_BLUE'
if F.LOWER:
return 'USE_BLUE'
if F.HIGHER:
if (F.topo_order > D_topo_order):
return 'USE_BLUE'
if (F.topo_order < D_topo_order):
return 'USE_RED'
assert(False)
assert(False)
if D_lower:
if F.HIGHER and F.LOWER:
return 'USE_RED'
if F.HIGHER:
return 'USE_RED'
if F.LOWER:
if F.topo_order > D_topo_order:
return 'USE_BLUE'
if F.topo_order < D_topo_order:
return 'USE_RED'
assert(False)
assert(False)
else: # D is unordered wrt S
if F.HIGHER and F.LOWER:
if primary_intf.OUTGOING and primary_intf.INCOMING:
assert(False)
if primary_intf.OUTGOING:
# this case isn't hit it topo-9e
return 'USE_BLUE'
if primary_intf.INCOMING:
return 'USE_RED'
assert(False)
if F.LOWER:
return 'USE_RED'
if F.HIGHER:
return 'USE_BLUE'
assert(False)
def Select_Alternates(D, F, primary_intf):
if (D is F) or (D.order_proxy is F):
return 'PRIM_NH_IS_D_OR_OP_FOR_D'
D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order)
def Select_Alts_For_One_Src_To_Island_Dests(topo,x):
Normal_SPF(topo, x)
for D in topo.island_node_list:
D.alt_list = []
if D is x:
continue
for primary_intf in D.primary_next_hops:
alt = Alternate()
alt.failed_intf = primary_intf
if primary_intf in x.island_intf_list:
alt.info = Select_Alternates(D,
primary_intf.remote_node, primary_intf)
else:
alt.info = 'PRIM_NH_NOT_IN_ISLAND'
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_BLUE'):
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_RED'):
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'):
if primary_intf.OUTGOING and primary_intf.INCOMING:
# cut-link: if there are parallel cut links, use
# the link(s) with lowest metric that are not
# primary intf or None
cand_alt_list = [None]
min_metric = 2147483647
for intf in x.island_intf_list:
if ( intf is not primary_intf and
(intf.remote_node is
primary_intf.remote_node)):
if intf.metric < min_metric:
cand_alt_list = [intf]
min_metric = intf.metric
elif intf.metric == min_metric:
cand_alt_list.append(intf)
if cand_alt_list != [None]:
alt.fec = 'GREEN'
alt.prot = 'PARALLEL_CUTLINK'
else:
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
Copy_List_Items(alt.nh_list, cand_alt_list)
elif primary_intf in D.red_next_hops:
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION'
else:
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
D.alt_list.append(alt)
def Write_GADAG_To_File(topo, file_prefix):
gadag_edge_list = []
for node in topo.island_node_list:
for intf in node.island_intf_list:
if intf.OUTGOING:
local_node = "%04d" % (intf.local_node.node_id)
remote_node = "%04d" % (intf.remote_node.node_id)
intf_data = "%03d" % (intf.link_data)
edge_string=(local_node+','+remote_node+','+
intf_data+'\n')
gadag_edge_list.append(edge_string)
gadag_edge_list.sort();
filename = file_prefix + '_gadag.csv'
with open(filename, 'w') as gadag_file:
gadag_file.write('local_node,'\
'remote_node,local_intf_link_data\n')
for edge_string in gadag_edge_list:
gadag_file.write(edge_string);
def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix):
edge_list = []
for node in topo.island_node_list:
if color == 'blue':
node_next_hops_dict = node.blue_next_hops_dict
elif color == 'red':
node_next_hops_dict = node.red_next_hops_dict
for dest_node_id in node_next_hops_dict:
for intf in node_next_hops_dict[dest_node_id]:
gadag_root = "%04d" % (topo.gadag_root.node_id)
dest_node = "%04d" % (dest_node_id)
local_node = "%04d" % (intf.local_node.node_id)
remote_node = "%04d" % (intf.remote_node.node_id)
intf_data = "%03d" % (intf.link_data)
edge_string=(gadag_root+','+dest_node+','+local_node+
','+remote_node+','+intf_data+'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_' + color + '_to_all.csv'
with open(filename, 'w') as mrt_file:
mrt_file.write('gadag_root,dest,'\
'local_node,remote_node,link_data\n')
for edge_string in edge_list:
mrt_file.write(edge_string);
def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix):
Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix)
Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix)
def Write_Alternates_For_All_Dests_To_File(topo, file_prefix):
edge_list = []
for x in topo.island_node_list:
for dest_node_id in x.alt_dict:
alt_list = x.alt_dict[dest_node_id]
for alt in alt_list:
for alt_intf in alt.nh_list:
gadag_root = "%04d" % (topo.gadag_root.node_id)
dest_node = "%04d" % (dest_node_id)
prim_local_node = \
"%04d" % (alt.failed_intf.local_node.node_id)
prim_remote_node = \
"%04d" % (alt.failed_intf.remote_node.node_id)
prim_intf_data = \
"%03d" % (alt.failed_intf.link_data)
if alt_intf == None:
alt_local_node = "None"
alt_remote_node = "None"
alt_intf_data = "None"
else:
alt_local_node = \
"%04d" % (alt_intf.local_node.node_id)
alt_remote_node = \
"%04d" % (alt_intf.remote_node.node_id)
alt_intf_data = \
"%03d" % (alt_intf.link_data)
edge_string = (gadag_root+','+dest_node+','+
prim_local_node+','+prim_remote_node+','+
prim_intf_data+','+alt_local_node+','+
alt_remote_node+','+alt_intf_data+','+
alt.fec +'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_alts_to_all.csv'
with open(filename, 'w') as alt_file:
alt_file.write('gadag_root,dest,'\
'prim_nh.local_node,prim_nh.remote_node,'\
'prim_nh.link_data,alt_nh.local_node,'\
'alt_nh.remote_node,alt_nh.link_data,'\
'alt_nh.fec\n')
for edge_string in edge_list:
alt_file.write(edge_string);
def Raise_GADAG_Root_Selection_Priority(topo,node_id):
node = topo.node_dict[node_id]
node.GR_sel_priority = 255
def Lower_GADAG_Root_Selection_Priority(topo,node_id):
node = topo.node_dict[node_id]
node.GR_sel_priority = 128
def GADAG_Root_Compare(node_a, node_b):
if (node_a.GR_sel_priority > node_b.GR_sel_priority):
return 1
elif (node_a.GR_sel_priority < node_b.GR_sel_priority):
return -1
else:
if node_a.node_id > node_b.node_id:
return 1
elif node_a.node_id < node_b.node_id:
return -1
def Set_GADAG_Root(topo,computing_router):
gadag_root_list = []
for node in topo.island_node_list:
gadag_root_list.append(node)
gadag_root_list.sort(GADAG_Root_Compare)
topo.gadag_root = gadag_root_list.pop()
def Run_MRT_for_One_Source(topo, src):
Reset_Computed_Node_and_Intf_Values(topo)
MRT_Island_Identification(topo, src, 0, 0)
Set_Island_Intf_and_Node_Lists(topo)
Set_GADAG_Root(topo,src)
Sort_Interfaces(topo)
Run_Lowpoint(topo)
Assign_Remaining_Lowpoint_Parents(topo)
Construct_GADAG_via_Lowpoint(topo)
Run_Assign_Block_ID(topo)
Add_Undirected_Links(topo)
Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src)
Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src)
Select_Alts_For_One_Src_To_Island_Dests(topo,src)
Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src)
def Run_Prim_SPF_for_One_Source(topo,src):
Normal_SPF(topo, src)
Store_Primary_NHs_For_One_Source_To_Nodes(topo,src)
def Run_MRT_for_All_Sources(topo):
for src in topo.node_list:
if 0 in src.profile_id_list:
# src runs MRT if it has profile_id=0
Run_MRT_for_One_Source(topo,src)
else:
# still run SPF for nodes not running MRT
Run_Prim_SPF_for_One_Source(topo,src)
def Write_Output_To_Files(topo,file_prefix):
Write_GADAG_To_File(topo,file_prefix)
Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix)
Write_Alternates_For_All_Dests_To_File(topo,file_prefix)
def Create_Example_Topology_Input_File(filename):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10],
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10],
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10],
[78,79,10],[79,77,10]]
with open(filename, 'w') as topo_file:
for item in data:
if len(item) > 3:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+','+str(item[3])+'\n')
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Generate_Example_Topology_and_Run_MRT():
Create_Example_Topology_Input_File('example_topo_input_file.csv')
topo = Create_Topology_From_File('example_topo_input_file.csv')
res_file_base = 'example_topo'
Raise_GADAG_Root_Selection_Priority(topo,3)
Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
Generate_Example_Topology_and_Run_MRT()
<CODE ENDS>
8. Algorithm Alternatives and Evaluation
This specification defines the MRT Lowpoint Algorithm, which is one This specification defines the MRT Lowpoint Algorithm, which is one
option among several possible MRT algorithms. Other alternatives are option among several possible MRT algorithms. Other alternatives are
described in the appendices. described in the appendices.
In addition, it is possible to calculate Destination-Rooted GADAG, In addition, it is possible to calculate Destination-Rooted GADAG,
where for each destination, a GADAG rooted at that destination is where for each destination, a GADAG rooted at that destination is
computed. Then a router can compute the blue MRT and red MRT next- computed. Then a router can compute the blue MRT and red MRT next-
hops to that destination. Building GADAGs per destination is hops to that destination. Building GADAGs per destination is
computationally more expensive, but may give somewhat shorter computationally more expensive, but may give somewhat shorter
alternate paths. It may be useful for live-live multicast along alternate paths. It may be useful for live-live multicast along
MRTs. MRTs.
7.1. Algorithm Evaluation 8.1. Algorithm Evaluation
The MRT Lowpoint algorithm is the lowest computation of the MRT The MRT Lowpoint algorithm is the lowest computation of the MRT
algorithms. Two other MRT algorithms are provided in Appendix A and algorithms. Two other MRT algorithms are provided in Appendix A and
Appendix B. When analyzed on service provider network topologies, Appendix B. When analyzed on service provider network topologies,
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 [RFC7490]. This section compares MRT and remote LFA for IP Fast
LFA for IP Fast Reroute in 19 service provider network topologies, Reroute in 19 service provider network topologies, focusing on
focusing on coverage and alternate path length. Figure 27 shows the coverage and alternate path length. Figure 28 shows the node-
node-protecting coverage provided by local LFA (LLFA), remote LFA protecting coverage provided by local LFA (LLFA), remote LFA (RLFA),
(RLFA), and MRT against different failure scenarios in these and MRT against different failure scenarios in these topologies. The
topologies. The coverage values are calculated as the percentage of coverage values are calculated as the percentage of source-
source-destination pairs protected by the given IPFRR method relative destination pairs protected by the given IPFRR method relative to
to those protectable by optimal routing, against the same failure those protectable by optimal routing, against the same failure modes.
modes. More details on alternate selection policies used for this More details on alternate selection policies used for this analysis
analysis are described later in this section. are described later in this section.
+------------+-----------------------------+ +------------+-----------------------------+
| Topology | percentage of failure | | Topology | percentage of failure |
| | scenarios covered by | | | scenarios covered by |
| | IPFRR method | | | IPFRR method |
| |-----------------------------+ | |-----------------------------+
| | NP_LLFA | NP_RLFA | MRT | | | NP_LLFA | NP_RLFA | MRT |
+------------+---------+---------+---------+ +------------+---------+---------+---------+
| T201 | 37 | 90 | 100 | | T201 | 37 | 90 | 100 |
| T202 | 73 | 83 | 100 | | T202 | 73 | 83 | 100 |
skipping to change at page 44, line 33 skipping to change at page 67, line 37
| 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 27 Figure 28
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 28). In this table, for one topology using this approach ( Figure 29). 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 45, line 23 skipping to change at page 68, line 28
+--------+------------------------------------------------+ +--------+------------------------------------------------+
| | 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 28 Figure 29
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 28, the path length. As shown in the last three columns of Figure 29, 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 29, Figure 30, Figure 31, and Figure 32 present the hopcount- Figure 30, Figure 31, Figure 32, and Figure 33 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 29 having topologies, as measured by the number of nodes, with Figure 30 having
the smallest topologies and Figure 32 having the largest topologies. the smallest topologies and Figure 33 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 47, line 50 skipping to change at page 70, 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 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 48, line 50 skipping to change at page 71, 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 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 49, line 50 skipping to change at page 72, 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 31 Figure 32
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | 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 50, line 43 skipping to change at page 73, 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 32 Figure 33
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 51, line 24 skipping to change at page 74, 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 33 for a subset those three choices of GADAG root are shown in Figure 34 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 52, line 50 skipping to change at page 75, 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 33 Figure 34
8. Implementation Status 9. 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 10. Algorithm Work to Be Done
Broadcast Interfaces: The algorithm assumes that broadcast Broadcast Interfaces: The algorithm assumes that broadcast
interfaces are already represented as pseudo-nodes in the network interfaces are already represented as pseudo-nodes in the network
graph. Given maximal redundancy, one of the MRT will try to avoid graph. Given maximal redundancy, one of the MRT will try to avoid
both the pseudo-node and the next hop. The exact rules need to be both the pseudo-node and the next hop. The exact rules need to be
fully specified. fully specified.
10. Acknowledgements 11. Acknowledgements
The authors would like to thank Shraddha Hegde for her suggestions The authors would like to thank Shraddha Hegde for her suggestions
and review. and review.
11. IANA Considerations 12. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
12. Security Considerations 13. 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 14. References
13.1. Normative References 14.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-architecture] [I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., and R. White, "An Architecture for IP/ A., Tantsura, J., and R. White, "An Architecture for IP/
LDP Fast-Reroute Using Maximally Redundant Trees", draft- LDP Fast-Reroute Using Maximally Redundant Trees", draft-
ietf-rtgwg-mrt-frr-architecture-05 (work in progress), ietf-rtgwg-mrt-frr-architecture-05 (work in progress),
January 2015. 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 14.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.farkas-isis-pcr]
Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., and P.
Ashwood-Smith, "IS-IS Path Computation and Reservation",
draft-farkas-isis-pcr-01 (work in progress), December
2014.
[I-D.ietf-isis-mrt] [I-D.ietf-isis-mrt]
Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J.
Tantsura, "Intermediate System to Intermediate System (IS- Tantsura, "Intermediate System to Intermediate System (IS-
IS) Extensions for Maximally Redundant Trees (MRT)", IS) Extensions for Maximally Redundant Trees (MRT)",
draft-ietf-isis-mrt-00 (work in progress), February 2015. draft-ietf-isis-mrt-00 (work in progress), February 2015.
[I-D.ietf-isis-pcr]
Farkas, J., Bragg, N., Unbehagen, P., Parsons, G.,
Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation
and Reservation", draft-ietf-isis-pcr-00 (work in
progress), April 2015.
[I-D.ietf-mpls-ldp-mrt] [I-D.ietf-mpls-ldp-mrt]
Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and
I. Wijnands, "LDP Extensions to Support Maximally I. Wijnands, "LDP Extensions to Support Maximally
Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in
progress), January 2015. progress), January 2015.
[I-D.ietf-ospf-mrt] [I-D.ietf-ospf-mrt]
Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
"OSPF Extensions to Support Maximally Redundant Trees", "OSPF Extensions to Support Maximally Redundant Trees",
draft-ietf-ospf-mrt-00 (work in progress), January 2015. draft-ietf-ospf-mrt-00 (work in progress), January 2015.
skipping to change at page 54, line 46 skipping to change at page 77, line 46
[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-08 (work in progress), March 2015. manageability-11 (work in progress), June 2015.
[I-D.ietf-rtgwg-remote-lfa]
Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Re-Route
(FRR)", draft-ietf-rtgwg-remote-lfa-11 (work in progress),
January 2015.
[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 56, line 5 skipping to change at page 78, line 44
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.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, April 2015.
Appendix A. Option 2: Computing GADAG using SPFs Appendix A. Option 2: Computing GADAG using SPFs
The basic idea in this option is to use slightly-modified SPF The basic idea in this option is to use slightly-modified SPF
computations to find ears. In every block, an SPF computation is computations to find ears. In every block, an SPF computation is
first done to find a cycle from the local root and then SPF first done to find a cycle from the local root and then SPF
computations in that block find ears until there are no more computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops is the path of interfaces indicated by following the previous hops
from the mininized IN_GADAG node back to the SPF root. from the mininized IN_GADAG node back to the SPF root.
skipping to change at page 57, line 9 skipping to change at page 80, line 4
min_node = remove_lowest(spf_heap) min_node = remove_lowest(spf_heap)
if min_node.IN_GADAG 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 34: Modified SPF for GADAG computation Figure 35: 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.5, the same problem was handled by finding x...q<-z. In Section 5.5, the same problem was handled by finding
all ears that started at a node before looking at ears starting at all ears that started at a node before looking at ears starting at
nodes higher in the partial order. In this algorithm, using that nodes higher in the partial order. In this 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
skipping to change at page 59, line 48 skipping to change at page 81, line 50
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 35: Algorithm to assign links of an ear direction Figure 36: 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,
skipping to change at page 60, line 27 skipping to change at page 82, line 31
was seen in Section 5.7. 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 ) 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
if (cand_intf.remote_node.local_root == ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.local_node) && cand_intf.remote_node,
check_if_block_has_ear cand_intf.remote_node.localroot,
(cand_intf.local_node, SPF method)
cand_intf.remote_node.block_id)) y = ear_end.spf_prev_hop
/* Skip the interface since the block root while y.local_node is not cand_intf.local_node
already has an incoming interface in the add_eligible_interfaces_of_node(
block */ ordered_intfs_tree, 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 36: SPF-based GADAG algorithm Figure 37: 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 62, line 14 skipping to change at page 84, line 15
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 37 The entire algorithm is shown below in Figure 38
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 62, line 44 skipping to change at page 84, line 45
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 37: Hybrid GADAG algorithm Figure 38: 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. 105 change blocks. 
458 lines changed or deleted 1598 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/