draft-ietf-rtgwg-mrt-frr-algorithm-09.txt   rfc7811.txt 
Routing Area Working Group G. Enyedi Internet Engineering Task Force (IETF) G. Enyedi
Internet-Draft A. Csaszar Request for Comments: 7811 A. Csaszar
Intended status: Standards Track Ericsson Category: Standards Track Ericsson
Expires: August 19, 2016 A. Atlas ISSN: 2070-1721 A. Atlas
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
February 16, 2016 June 2016
An Algorithm for Computing Maximally Redundant Trees for IP/LDP Fast- An Algorithm for Computing IP/LDP Fast Reroute
Reroute Using Maximally Redundant Trees (MRT-FRR)
draft-ietf-rtgwg-mrt-frr-algorithm-09
Abstract Abstract
A solution for IP and LDP Fast-Reroute using Maximally Redundant This document supports the solution put forth in "An Architecture for
Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)"
document defines the associated MRT Lowpoint algorithm that is used (RFC 7812) by defining the associated MRT Lowpoint algorithm that is
in the Default MRT profile to compute both the necessary Maximally used in the Default MRT Profile to compute both the necessary
Redundant Trees with their associated next-hops and the alternates to Maximally Redundant Trees with their associated next hops and the
select for MRT-FRR. alternates to select for MRT-FRR.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This is an Internet Standards Track document.
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months This document is a product of the Internet Engineering Task Force
and may be updated, replaced, or obsoleted by other documents at any (IETF). It represents the consensus of the IETF community. It has
time. It is inappropriate to use Internet-Drafts as reference received public review and has been approved for publication by the
material or to cite them other than as "work in progress." Internet Engineering Steering Group (IESG). Further information on
Internet Standards is available in Section 2 of RFC 7841.
This Internet-Draft will expire on August 19, 2016. Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc7811.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 20 skipping to change at page 2, line 28
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5 3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6 4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7 4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
4.2. Finding an Ear and the Correct Direction . . . . . . . . 8 4.2. Finding an Ear and the Correct Direction . . . . . . . . 8
4.3. Low-Point Values and Their Uses . . . . . . . . . . . . . 11 4.3. Lowpoint Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14 4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
4.5. Determining Local-Root and Assigning Block-ID . . . . . . 16 4.5. Determining Localroot and Assigning Block-ID . . . . . . 16
5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18 5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18
5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22
5.5. Constructing the GADAG using lowpoint inheritance . . . . 23 5.5. Constructing the GADAG Using Lowpoint Inheritance . . . . 23
5.6. Augmenting the GADAG by directing all links . . . . . . . 25 5.6. Augmenting the GADAG by Directing All Links . . . . . . . 25
5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 29 5.7. Compute MRT Next Hops . . . . . . . . . . . . . . . . . . 29
5.7.1. MRT next-hops to all nodes ordered with respect to 5.7.1. MRT Next Hops to All Nodes Ordered with Respect to
the computing node . . . . . . . . . . . . . . . . . 29 the Computing Node . . . . . . . . . . . . . . . . . 29
5.7.2. MRT next-hops to all nodes not ordered with respect 5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect
to the computing node . . . . . . . . . . . . . . . . 30 to the Computing Node . . . . . . . . . . . . . . . . 30
5.7.3. Computing Redundant Tree next-hops in a 2-connected 5.7.3. Computing Redundant Tree Next Hops in a 2-Connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
5.7.4. Generalizing for a graph that isn't 2-connected . . . 33 5.7.4. Generalizing for a Graph That Isn't 2-Connected . . . 33
5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 34 5.7.5. Complete Algorithm to Compute MRT Next Hops . . . . . 34
5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 36 5.8. Identify MRT Alternates . . . . . . . . . . . . . . . . . 36
5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 43 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44
5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 43 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 45
5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 44 5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free . . 45
5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 46 5.9.3. Computing MRT Next Hops for Proxy-Nodes . . . . . . . 47
5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 52 5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 60
7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 60 6. MRT Lowpoint Algorithm: Next-Hop Conformance . . . . . . . . 61
7.1. Computing MRT next-hops on broadcast networks . . . . . . 61 7. Broadcast Interfaces . . . . . . . . . . . . . . . . . . . . 61
7.2. Using MRT next-hops as alternates in the event of 7.1. Computing MRT Next Hops on Broadcast Networks . . . . . . 62
failures on broadcast networks . . . . . . . . . . . . . 62 7.2. Using MRT Next Hops as Alternates in the Event of
8. Evaluation of Alternative Methods for Constructing GADAGs . . 63 Failures on Broadcast Networks . . . . . . . . . . . . . 63
9. Implementation Status . . . . . . . . . . . . . . . . . . . . 64 8. Evaluation of Alternative Methods for Constructing GADAGs . . 64
10. Operational Considerations . . . . . . . . . . . . . . . . . 65 9. Operational Considerations . . . . . . . . . . . . . . . . . 66
10.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 65 9.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 67
10.2. Destination-rooted GADAGs . . . . . . . . . . . . . . . 65 9.2. Destination-Rooted GADAGs . . . . . . . . . . . . . . . . 67
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 66 10. Security Considerations . . . . . . . . . . . . . . . . . . . 67
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 66 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 68
13. Security Considerations . . . . . . . . . . . . . . . . . . . 66 11.1. Normative References . . . . . . . . . . . . . . . . . . 68
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 66 11.2. Informative References . . . . . . . . . . . . . . . . . 68
14.1. Normative References . . . . . . . . . . . . . . . . . . 66 Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 70
14.2. Informative References . . . . . . . . . . . . . . . . . 66 Appendix B. Constructing a GADAG Using SPFs . . . . . . . . . . 110
Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 67 Appendix C. Constructing a GADAG Using a Hybrid Method . . . . . 115
Appendix B. Constructing a GADAG using SPFs . . . . . . . . . . 108 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 117
Appendix C. Constructing a GADAG using a hybrid method . . . . . 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 118
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 115
1. Introduction 1. Introduction
MRT Fast-Reroute requires that packets can be forwarded not only on MRT Fast Reroute requires that packets can be forwarded not only on
the shortest-path tree, but also on two Maximally Redundant Trees the shortest-path tree, but also on two Maximally Redundant Trees
(MRTs), referred to as the MRT-Blue and the MRT-Red. A router which (MRTs), referred to as the MRT-Blue and the MRT-Red. A router that
experiences a local failure must also have pre-determined which experiences a local failure must also have predetermined which
alternate to use. This document defines how to compute these three alternate to use. This document defines how to compute these three
things for use in MRT-FRR and describes the algorithm design things for use in MRT-FRR and describes the algorithm design
decisions and rationale. The algorithm is based on those presented decisions and rationale. The algorithm is based on those presented
in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint
algorithm is required for implementation when the Default MRT profile algorithm is required for implementation when the Default MRT Profile
is implemented. is implemented.
The MRT Lowpoint Algorithm defined in this document, when used for
MRT Fast-Reroute as described in [RFC7812], guarantees 100% recovery
for single failures when the network is 2-connected. This guaranteed
coverage does not depend on the link metrics, which an operator may
be using to traffic-engineer the IP network. Thus, the link metrics
and general network topology are largely decoupled from the
guaranteed coverage.
Just as packets routed on a hop-by-hop basis require that each router Just as packets routed on a hop-by-hop basis require that each router
compute a shortest-path tree which is consistent, it is necessary for compute a shortest-path tree that is consistent, it is necessary for
each router to compute the MRT-Blue next-hops and MRT-Red next-hops each router to compute the MRT-Blue next hops and MRT-Red next hops
in a consistent fashion. This document defines the MRT Lowpoint in a consistent fashion. This document defines the MRT Lowpoint
algorithm to be used as a standard in the default MRT profile for algorithm to be used as a standard in the Default MRT Profile for
MRT-FRR. MRT-FRR.
As now, a router's FIB will contain primary next-hops for the current A router's Forwarding Information Base (FIB) will continue to contain
shortest-path tree for forwarding traffic. In addition, a router's primary next hops for the current shortest-path tree for forwarding
FIB will contain primary next-hops for the MRT-Blue for forwarding traffic. In addition, a router's FIB will contain primary next hops
received traffic on the MRT-Blue and primary next-hops for the MRT- for the MRT-Blue for forwarding received traffic on the MRT-Blue and
Red for forwarding received traffic on the MRT-Red. primary next hops for the MRT-Red for forwarding received traffic on
the MRT-Red.
What alternate next-hops a point-of-local-repair (PLR) selects need What alternate next hops a Point of Local Repair (PLR) selects need
not be consistent - but loops must be prevented. To reduce not be consistent -- but loops must be prevented. To reduce
congestion, it is possible for multiple alternate next-hops to be congestion, it is possible for multiple alternate next hops to be
selected; in the context of MRT alternates, each of those alternate selected; in the context of MRT alternates, each of those alternate
next-hops would be equal-cost paths. next hops would be equal-cost paths.
This document defines an algorithm for selecting an appropriate MRT This document defines an algorithm for selecting an appropriate MRT
alternate for consideration. Other alternates, e.g. LFAs that are alternate for consideration. Other alternates, e.g., Loop-Free
downstream paths, may be preferred when available. See the Alternates (LFAs) that are downstream paths, may be preferred when
Operational Considerations section of available. See the "Operational Considerations" section of [RFC7812]
[I-D.ietf-rtgwg-mrt-frr-architecture] for a more detailed discussion for a more detailed discussion of combining MRT alternates with those
of combining MRT alternates with those produced by other FRR produced by other FRR technologies.
technologies.
[E]---[D]---| [E]<--[D]<--| [E]-->[D] [E]---[D]---| [E]<--[D]<--| [E]-->[D]---|
| | | | ^ | | | | | | ^ | | |
| | | V | | V | | | V | | V V
[R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C]
| | | ^ ^ | | | | | ^ ^ ^ | |
| | | | | V | | | | | | | V |
[A]---[B]---| [A]-->[B] [A]---[B]<--| [A]---[B]---| [A]-->[B]---| [A]<--[B]<--|
(a) (b) (c) (a) (b) (c)
a 2-connected graph MRT-Blue towards R MRT-Red towards R A 2-connected graph MRT-Blue towards R MRT-Red towards R
Figure 1 Figure 1
The MRT Lowpoint algorithm can handle arbitrary network topologies The MRT Lowpoint algorithm can handle arbitrary network topologies
where the whole network graph is not 2-connected, as in Figure 2, as where the whole network graph is not 2-connected, as in Figure 2, as
well as the easier case where the network graph is 2-connected well as the easier case where the network graph is 2-connected
(Figure 1). Each MRT is a spanning tree. The pair of MRTs provide (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide
two paths from every node X to the root of the MRTs. Those paths two paths from every node X to the root of the MRTs. Those paths
share the minimum number of nodes and the minimum number of links. share the minimum number of nodes and the minimum number of links.
Each such shared node is a cut-vertex. Any shared links are cut- Each such shared node is a cut-vertex. Any shared links are cut-
links. links.
[E]---[D]---| |---[J] [E]---[D]---| |---[J]
| | | | | | | | | |
| | | | | | | | | |
[R] [F] [C]---[G] | [R] [F] [C]---[G] |
| | | | | | | | | |
| | | | | | | | | |
[A]---[B]---| |---[H] [A]---[B]---| |---[H]
(a) a graph that isn't 2-connected (a) a graph that is not 2-connected
[E]<--[D]<--| [J] [E]-->[D]---| |---[J] [E]<--[D]<--| [J] [E]-->[D]---| |---[J]
| ^ | | | | | ^ | ^ | | | | | ^
V | | | V V V | V | | | V V V |
[R] [F] [C]<--[G] | [R] [F] [C]<--[G] | [R] [F] [C]<--[G] | [R] [F] [C]<--[G] |
^ ^ ^ | ^ | | | ^ ^ ^ | ^ | | |
| | | V | V | | | | | V | V | |
[A]-->[B]---| |---[H] [A]<--[B]<--| [H] [A]-->[B]---| |---[H] [A]<--[B]<--| [H]
(b) MRT-Blue towards R (c) MRT-Red towards R (b) MRT-Blue towards R (c) MRT-Red towards R
Figure 2 Figure 2: A Network That Is Not 2-Connected
2. Requirements Language 2. Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
3. Terminology and Definitions 3. Terminology and Definitions
Please see the Terminology section of Please see the Terminology section of [RFC7812] for a complete list
[I-D.ietf-rtgwg-mrt-frr-architecture] for a complete list of of terminology relevant to this document. The list below does not
terminology relevant to this draft. The list below does not repeat repeat terminology introduced in that RFC.
terminology introduced in that draft.
spanning tree: A tree containing links that connects all nodes in spanning tree: A tree that contains links and that connects all
the network graph. nodes in the network graph.
back-edge: In the context of a spanning tree computed via a depth- back-edge: In the context of a spanning tree computed via a depth-
first search, a back-edge is a link that connects a descendant of first search, a back-edge is a link that connects a descendant of
a node x with an ancestor of x. a node x with an ancestor of x.
partial ADAG: A subset of an ADAG that doesn't yet contain all the partial ADAG: A subset of an Almost Directed Acyclic Graph (ADAG)
nodes in the block. A partial ADAG is created during the MRT that doesn't yet contain all the nodes in the block. A partial
algorithm and then expanded until all nodes in the block are ADAG is created during the MRT Lowpoint algorithm and then
included and it is an ADAG. expanded until all nodes in the block are included and it becomes
an ADAG.
DFS: Depth-First Search DFS: Depth-First Search
DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS- DFS ancestor: A node n is a DFS ancestor of x if n is on the DFS-
tree path from the DFS root to x. tree path from the DFS root to x.
DFS descendant: A node n is a DFS descendant of x if x is on the DFS descendant: A node n is a DFS descendant of x if x is on the
DFS-tree path from the DFS root to n. DFS-tree path from the DFS root to n.
ear: A path along not-yet-included-in-the-GADAG nodes that starts ear: A path along nodes that are not yet included in the Generalized
at a node that is already-included-in-the-GADAG and that ends at a ADAG (GADAG) that starts at a node that is already included in the
node that is already-included-in-the-GADAG. The starting and GADAG and that ends at a node that is already included in the
ending nodes may be the same node if it is a cut-vertex. GADAG. The starting and ending nodes may be the same node if it
is a cut-vertex.
X >> Y or Y << X: Indicates the relationship between X and Y in a X>>Y or Y<<X: Indicates the relationship between X and Y in a
partial order, such as found in a GADAG. X >> Y means that X is partial order, such as found in a GADAG. X>>Y means that X is
higher in the partial order than Y. Y << X means that Y is lower higher in the partial order than Y. Y<<X means that Y is lower in
in the partial order than X. the partial order than X.
X > Y or Y < X: Indicates the relationship between X and Y in the X>Y or Y<X: Indicates the relationship between X and Y in the total
total order, such as found via a topological sort. X > Y means order, such as found via a topological sort. X>Y means that X is
that X is higher in the total order than Y. Y < X means that Y is higher in the total order than Y. Y<X means that Y is lower in
lower in the total order than X. the total order than X.
X ?? Y: Indicates that X is unordered with respect to Y in the X ?? Y: Indicates that X is unordered with respect to Y in the
partial order. partial order.
UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING UNDIRECTED: In the GADAG, each link is marked as OUTGOING, INCOMING,
or both. Until the directionality of the link is determined, the or both. Until the directionality of the link is determined, the
link is marked as UNDIRECTED to indicate that its direction hasn't link is marked as UNDIRECTED to indicate that its direction hasn't
been determined. been determined.
OUTGOING: A link marked as OUTGOING has direction in the GADAG from OUTGOING: A link marked as OUTGOING has direction in the GADAG from
the interface's router to the remote end. the interface's router to the remote end.
INCOMING: A link marked as INCOMING has direction in the GADAG from INCOMING: A link marked as INCOMING has direction in the GADAG from
the remote end to the interface's router. the remote end to the interface's router.
4. Algorithm Key Concepts 4. Algorithm Key Concepts
There are five key concepts that are critical for understanding the There are five key concepts that are critical for understanding the
MRT Lowpoint algorithm. The first is the idea of partially ordering MRT Lowpoint algorithm. The first is the idea of partially ordering
the nodes in a network graph with regard to each other and to the the nodes in a network graph with regard to each other and to the
GADAG root. The second is the idea of finding an ear of nodes and GADAG root. The second is the idea of finding an ear of nodes and
adding them in the correct direction. The third is the idea of a adding them in the correct direction. The third is the idea of a
Low-Point value and how it can be used to identify cut-vertices and Lowpoint value and how it can be used to identify cut-vertices and to
to find a second path towards the root. The fourth is the idea that find a second path towards the root. The fourth is the idea that a
a non-2-connected graph is made up of blocks, where a block is a non-2-connected graph is made up of blocks, where a block is a
2-connected cluster, a cut-link or an isolated node. The fifth is 2-connected cluster, a cut-link or an isolated node. The fifth is
the idea of a local-root for each node; this is used to compute ADAGs the idea of a localroot for each node; this is used to compute ADAGs
in each block. in each block.
4.1. Partial Ordering for Disjoint Paths 4.1. Partial Ordering for Disjoint Paths
Given any two nodes X and Y in a graph, a particular total order Given any two nodes X and Y in a graph, a particular total order
means that either X < Y or X > Y in that total order. An example means that either X<Y or X>Y in that total order. An example would
would be a graph where the nodes are ranked based upon their unique be a graph where the nodes are ranked based upon their unique IP
IP loopback addresses. In a partial order, there may be some nodes loopback addresses. In a partial order, there may be some nodes for
for which it can't be determined whether X << Y or X >> Y. A partial which it can't be determined whether X<<Y or X>>Y. A partial order
order can be captured in a directed graph, as shown in Figure 3. In can be captured in a directed graph, as shown in Figure 3. In a
a graphical representation, a link directed from X to Y indicates graphical representation, a link directed from X to Y indicates that
that X is a neighbor of Y in the network graph and X << Y. X is a neighbor of Y in the network graph and X<<Y.
[A]<---[R] [E] R << A << B << C << D << E [A]<---[R] [E] R << A << B << C << D << E
| ^ R << A << B << F << G << H << D << E | ^ R << A << B << F << G << H << D << E
| | | |
V | Unspecified Relationships: V | Unspecified Relationships:
[B]--->[C]--->[D] C and F [B]--->[C]--->[D] C and F
| ^ C and G | ^ C and G
| | C and H | | C and H
V | V |
[F]--->[G]--->[H] [F]--->[G]--->[H]
Figure 3: Directed Graph showing a Partial Order Figure 3: Directed Graph Showing a Partial Order
To compute MRTs, the root of the MRTs is at both the very bottom and To compute MRTs, the root of the MRTs is at both the very bottom and
the very top of the partial ordering. This means that from any node the very top of the partial ordering. This means that from any node
X, one can pick nodes higher in the order until the root is reached. X, one can pick nodes higher in the order until the root is reached.
Similarly, from any node X, one can pick nodes lower in the order Similarly, from any node X, one can pick nodes lower in the order
until the root is reached. For instance, in Figure 4, from G the until the root is reached. For instance, in Figure 4, from G the
higher nodes picked can be traced by following the directed links and higher nodes picked can be traced by following the directed links and
are H, D, E and R. Similarly, from G the lower nodes picked can be are H, D, E, and R. Similarly, from G the lower nodes picked can be
traced by reversing the directed links and are F, B, A, and R. A traced by reversing the directed links and are F, B, A, and R. A
graph that represents this modified partial order is no longer a DAG; graph that represents this modified partial order is no longer a DAG;
it is termed an Almost DAG (ADAG) because if the links directed to it is termed an Almost DAG (ADAG) because if the links directed to
the root were removed, it would be a DAG. the root were removed, it would be a DAG.
[A]<---[R]<---[E] R << A << B << C << R [A]<---[R]<---[E] R << A << B << C << R
| ^ ^ R << A << B << C << D << E << R | ^ ^ R << A << B << C << D << E << R
| | | R << A << B << F << G << H << D << E << R | | | R << A << B << F << G << H << D << E << R
V | | V | |
[B]--->[C]--->[D] Unspecified Relationships: [B]--->[C]--->[D] Unspecified Relationships:
| ^ C and F | ^ C and F
| | C and G | | C and G
V | C and H V | C and H
[F]--->[G]--->[H] [F]--->[G]--->[H]
Figure 4: ADAG showing a Partial Order with R lowest and highest Figure 4: ADAG Showing a Partial Order with R Lowest and Highest
Most importantly, if a node Y >> X, then Y can only appear on the Most importantly, if a node Y>>X, then Y can only appear on the
increasing path from X to the root and never on the decreasing path. increasing path from X to the root and never on the decreasing path.
Similarly, if a node Z << X, then Z can only appear on the decreasing Similarly, if a node Z<<X, then Z can only appear on the decreasing
path from X to the root and never on the inceasing path. path from X to the root and never on the increasing path.
When following the increasing paths, it is possible to pick multiple When following the increasing paths, it is possible to pick multiple
higher nodes and still have the certainty that those paths will be higher nodes and still have the certainty that those paths will be
disjoint from the decreasing paths. E.g. in the previous example disjoint from the decreasing paths. For example, in the previous
node B has multiple possibilities to forward packets along an example, node B has multiple possibilities to forward packets along
increasing path: it can either forward packets to C or F. an increasing path: it can either forward packets to C or F.
4.2. Finding an Ear and the Correct Direction 4.2. Finding an Ear and the Correct Direction
For simplicity, the basic idea of creating a GADAG by adding ears is For simplicity, the basic idea of creating a GADAG by adding ears is
described assuming that the network graph is a single 2-connected described assuming that the network graph is a single 2-connected
cluster so that an ADAG is sufficient. Generalizing to multiple cluster so that an ADAG is sufficient. Generalizing to multiple
blocks is done by considering the block-roots instead of the GADAG blocks is done by considering the block-roots instead of the GADAG
root - and the actual algorithm is given in Section 5.5. root -- and the actual algorithm is given in Section 5.5.
In order to understand the basic idea of finding an ADAG, first In order to understand the basic idea of finding an ADAG, first
suppose that we have already a partial ADAG, which doesn't contain suppose that we have already a partial ADAG, which doesn't contain
all the nodes in the block yet, and we want to extend it to cover all all the nodes in the block yet, and we want to extend it to cover all
the nodes. Suppose that we find a path from a node X to Y such that the nodes. Suppose that we find a path from a node X to Y such that
X and Y are already contained by our partial ADAG, but all the X and Y are already contained by our partial ADAG, but all the
remaining nodes along the path are not added to the ADAG yet. We remaining nodes along the path are not added to the ADAG yet. We
refer to such a path as an ear. refer to such a path as an "ear".
Recall that our ADAG is closely related to a partial order. More Recall that our ADAG is closely related to a partial order. More
precisely, if we remove root R, the remaining DAG describes a partial precisely, if we remove root R, the remaining DAG describes a partial
order of the nodes. If we suppose that neither X nor Y is the root, order of the nodes. If we suppose that neither X nor Y is the root,
we may be able to compare them. If one of them is definitely lesser we may be able to compare them. If one of them is definitely lesser
with respect to our partial order (say X<<Y), we can add the new path with respect to our partial order (say X<<Y), we can add the new path
to the ADAG in a direction from X to Y. As an example consider to the ADAG in a direction from X to Y. As an example, consider
Figure 5. Figure 5.
E---D---| E<--D---| E<--D<--| E---D---| E<--D---| E<--D<--|
| | | | ^ | | ^ | | | | | ^ | | ^ |
| | | V | | V | | | | | V | | V | |
R F C R F C R F C R F C R F C R F C
| | | | ^ | | ^ ^ | | | | ^ | | ^ ^
| | | V | | V | | | | | V | | V | |
A---B---| A-->B---| A-->B---| A---B---| A-->B---| A-->B---|
(a) (b) (c) (a) (b) (c)
(a) A 2-connected graph (a) A 2-connected graph
(b) Partial ADAG (C is not included) (b) Partial ADAG (C is not included)
(c) Resulting ADAG after adding path (or ear) B-C-D (c) Resulting ADAG after adding path (or ear) B-C-D
Figure 5 Figure 5
In this partial ADAG, node C is not yet included. However, we can In this partial ADAG, node C is not yet included. However, we can
find path B-C-D, where both endpoints are contained by this partial find path B-C-D, where both endpoints are contained by this partial
ADAG (we say those nodes are "ready" in the following text), and the ADAG (we say those nodes are "ready" in the following text), and the
remaining node (node C) is not contained yet. If we remove R, the remaining node (node C) is not contained yet. If we remove R, the
remaining DAG defines a partial order, and with respect to this remaining DAG defines a partial order, and with respect to this
partial order we can say that B<<D, so we can add the path to the partial order, we can say that B<<D; so, we can add the path to the
ADAG in the direction from B to D (arcs B->C and C->D are added). If ADAG in the direction from B to D (arcs B->C and C->D are added). If
B >> D, we would add the same path in reverse direction. B>>D, we would add the same path in reverse direction.
If in the partial order where an ear's two ends are X and Y, X << Y, If, in the partial order where an ear's two ends are X and Y, X<<Y,
then there must already be a directed path from X to Y in the ADAG. then there must already be a directed path from X to Y in the ADAG.
The ear must be added in a direction such that it doesn't create a The ear must be added in a direction such that it doesn't create a
cycle; therefore the ear must go from X to Y. cycle; therefore, the ear must go from X to Y.
In the case, when X and Y are not ordered with each other, we can In the case when X and Y are not ordered with each other, we can
select either direction for the ear. We have no restriction since select either direction for the ear. We have no restriction since
neither of the directions can result in a cycle. In the corner case neither of the directions can result in a cycle. In the corner case
when one of the endpoints of an ear, say X, is the root (recall that when one of the endpoints of an ear, say X, is the root (recall that
the two endpoints must be different), we could use both directions the two endpoints must be different), we could use both directions
again for the ear because the root can be considered both as smaller again for the ear because the root can be considered both as smaller
and as greater than Y. However, we strictly pick that direction in and as greater than Y. However, we strictly pick that direction in
which the root is lower than Y. The logic for this decision is which the root is lower than Y. The logic for this decision is
explained in Section 5.7 explained in Section 5.7
A partial ADAG is started by finding a cycle from the root R back to A partial ADAG is started by finding a cycle from the root R back to
itself. This can be done by selecting a non-ready neighbor N of R itself. This can be done by selecting a non-ready neighbor N of R
and then finding a path from N to R that doesn't use any links and then finding a path from N to R that doesn't use any links
between R and N. The direction of the cycle can be assigned either between R and N. The direction of the cycle can be assigned either
way since it is starting the ordering. way since it is starting the ordering.
Once a partial ADAG is already present, it will always have a node Once a partial ADAG is already present, it will always have a node
that is not the root R in it. As a brief proof that a partial ADAG that is not the root R in it. The following is a brief proof that a
can always have ears added to it: just select a non-ready neighbor N partial ADAG can always have ears added to it: just select a non-
of a ready node Q, such that Q is not the root R, find a path from N ready neighbor N of a ready node Q, such that Q is not the root R,
to the root R in the graph with Q removed. This path is an ear where find a path from N to the root R in the graph with Q removed. This
the first node of the ear is Q, the next is N, then the path until path is an ear where the first node of the ear is Q, the next is N,
the first ready node the path reached (that ready node is the other then the path until the first ready node the path reached (that ready
endpoint of the path). Since the graph is 2-connected, there must be node is the other endpoint of the path). Since the graph is
a path from N to R without Q. 2-connected, there must be a path from N to R without Q.
It is always possible to select a non-ready neighbor N of a ready It is always possible to select a non-ready neighbor N of a ready
node Q so that Q is not the root R. Because the network is node Q so that Q is not the root R. Because the network is
2-connected, N must be connected to two different nodes and only one 2-connected, N must be connected to two different nodes and only one
can be R. Because the initial cycle has already been added to the can be R. Because the initial cycle has already been added to the
ADAG, there are ready nodes that are not R. Since the graph is ADAG, there are ready nodes that are not R. Since the graph is
2-connected, while there are non-ready nodes, there must be a non- 2-connected, while there are non-ready nodes, there must be a non-
ready neighbor N of a ready node that is not R. ready neighbor N of a ready node that is not R.
Generic_Find_Ears_ADAG(root) Generic_Find_Ears_ADAG(root)
Create an empty ADAG. Add root to the ADAG. Create an empty ADAG. Add root to the ADAG.
Mark root as IN_GADAG. Mark root as IN_GADAG.
Select an arbitrary cycle containing root. Select an arbitrary cycle containing root.
Add the arbitrary cycle to the ADAG. Add the arbitrary cycle to the ADAG.
Mark cycle's nodes as IN_GADAG. Mark cycle's nodes as IN_GADAG.
Add cycle's non-root nodes to process_list. Add cycle's non-root nodes to process_list.
while there exists connected nodes in graph that are not IN_GADAG While there exist connected nodes in graph that are not IN_GADAG
Select a new ear. Let its endpoints be X and Y. Select a new ear. Let its endpoints be X and Y.
if Y is root or (Y << X) If Y is root or (Y<<X)
add the ear towards X to the ADAG Add the ear towards X to the ADAG
else // (a) X is root or (b)X << Y or (c) X, Y not ordered Else // (a) X is root, or (b) X<<Y, or (c) X, Y not ordered
Add the ear towards Y to the ADAG Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to find ears and their direction in Figure 6: Generic Algorithm to Find Ears and Their Direction in
2-connected graph 2-Connected Graph
The algorithm in Figure 6 merely requires that a cycle or ear be The algorithm in Figure 6 merely requires that a cycle or ear be
selected without specifying how. Regardless of the method for selected without specifying how. Regardless of the method for
selecting the path, we will get an ADAG. The method used for finding selecting the path, we will get an ADAG. The method used for finding
and selecting the ears is important; shorter ears result in shorter and selecting the ears is important; shorter ears result in shorter
paths along the MRTs. The MRT Lowpoint algorithm uses the Low-Point paths along the MRTs. The MRT Lowpoint algorithm uses the Lowpoint
Inheritance method for constructing an ADAG (and ultimately a GADAG). Inheritance method for constructing an ADAG (and ultimately a GADAG).
This method is defined in Section 5.5. Other methods for This method is defined in Section 5.5. Other methods for
constructing GADAGs are described in Appendix B and Appendix C. An constructing GADAGs are described in Appendices B and C. An
evaluation of these different methods is given in Section 8 evaluation of these different methods is given in Section 8.
As an example, consider Figure 5 again. First, we select the As an example, consider Figure 5 again. First, we select the
shortest cycle containing R, which can be R-A-B-F-D-E (uniform link shortest cycle containing R, which can be R-A-B-F-D-E (uniform link
costs were assumed), so we get to the situation depicted in Figure 5 costs were assumed), so we get to the situation depicted in
(b). Finally, we find a node next to a ready node; that must be node Figure 5(b). Finally, we find a node next to a ready node; that must
C and assume we reached it from ready node B. We search a path from be node C and assume we reached it from ready node B. We search a
C to R without B in the original graph. The first ready node along path from C to R without B in the original graph. The first ready
this is node D, so the open ear is B-C-D. Since B<<D, we add arc node along this is node D, so the open ear is B-C-D. Since B<<D, we
B->C and C->D to the ADAG. Since all the nodes are ready, we stop at add arc B->C and C->D to the ADAG. Since all the nodes are ready, we
this point. stop at this point.
4.3. Low-Point Values and Their Uses 4.3. Lowpoint Values and Their Uses
A basic way of computing a spanning tree on a network graph is to run A basic way of computing a spanning tree on a network graph is to run
a depth-first-search, such as given in Figure 7. This tree has the a DFS, such as given in Figure 7. This tree has the important
important property that if there is a link (x, n), then either n is a property that if there is a link (x, n), then either n is a DFS
DFS ancestor of x or n is a DFS descendant of x. In other words, ancestor of x or n is a DFS descendant of x. In other words, either
either n is on the path from the root to x or x is on the path from n is on the path from the root to x or x is on the path from the root
the root to n. to n.
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 gadag_root) Run_DFS(node gadag_root)
dfs_number = 0 dfs_number = 0
DFS_Visit(gadag_root, NONE) DFS_Visit(gadag_root, NONE)
Figure 7: Basic Depth-First Search algorithm Figure 7: Basic DFS 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 neighbors 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 neighboring x. What is interesting,
though, is what is the earliest attachment point from x and x's though, is the earliest attachment point from x and x's descendants.
descendants. This is what is determined by computing the Low-Point This is what is determined by computing the Lowpoint value.
value.
In order to compute the low point value, the network is traversed In order to compute the low point value, the network is traversed
using DFS and the vertices are numbered based on the DFS walk. Let using DFS and the vertices are numbered based on the DFS walk. Let
this number be represented as DFS(x). All the edges that lead to this number be represented as DFS(x). All the edges that lead to
already visited nodes during DFS walk are back-edges. The back-edges already-visited nodes during DFS walk are back-edges. The back-edges
are important because they give information about reachability of a are important because they give information about reachability of a
node via another path. node via another path.
The low point number is calculated by finding: The low point number is calculated by finding:
Low(x) = Minimum of ( (DFS(x), Low(x) = Minimum of ( (DFS(x),
Lowest DFS(n, x->n is a back-edge), Lowest DFS(n, x->n is a back-edge),
Lowest Low(n, x->n is tree edge in DFS walk) ). Lowest Low(n, x->n is tree edge in DFS walk) ).
A detailed algorithm for computing the low-point value is given in A detailed algorithm for computing the lowpoint value is given in
Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to Figure 8. Figure 9 illustrates how the Lowpoint algorithm applies to
a example graph. an example graph.
global_variable: dfs_number global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x) Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number D(x) = dfs_number
L(x) = D(x) L(x) = D(x)
dfs_number += 1 dfs_number += 1
x.dfs_parent = parent x.dfs_parent = parent
x.dfs_parent_intf = p_to_x.remote_intf x.dfs_parent_intf = p_to_x.remote_intf
x.lowpoint_parent = NONE x.lowpoint_parent = NONE
skipping to change at page 12, line 36 skipping to change at page 12, line 41
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 gadag_root) Run_Lowpoint(node gadag_root)
dfs_number = 0 dfs_number = 0
Lowpoint_Visit(gadag_root, NONE, NONE) Lowpoint_Visit(gadag_root, NONE, NONE)
Figure 8: Computing Low-Point value Figure 8: Computing Lowpoint Value
[E]---| [J]-------[I] [P]---[O] [E]---| [J]-------[I] [P]---[O]
| | | | | | | | | | | |
| | | | | | | | | | | |
[R] [D]---[C]--[F] [H]---[K] [N] [R] [D]---[C]--[F] [H]---[K] [N]
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]--------[B] [G]---| [L]---[M] [A]--------[B] [G]---| [L]---[M]
(a) a non-2-connected graph (a) a non-2-connected graph
skipping to change at page 13, line 39 skipping to change at page 13, line 39
(5,0) | (10,3) (9,3) (16,11) (15,11) (5,0) | (10,3) (9,3) (16,11) (15,11)
| | | | | | | | | | | |
| | | | | | | | | | | |
[R] [D]---[C]---[F] [H]----[K] [N] [R] [D]---[C]---[F] [H]----[K] [N]
(0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11) (0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]---------[B] [G]----| [L]------[M] [A]---------[B] [G]----| [L]------[M]
(1,0) (2,0) (7,3) (12,11) (13,11) (1,0) (2,0) (7,3) (12,11) (13,11)
(c) with low-point values assigned (D(x), L(x)) (c) with lowpoint values assigned (D(x), L(x))
Figure 9: Example lowpoint value computation Figure 9: Example Lowpoint Value Computation
From the low-point value and lowpoint parent, there are three very From the lowpoint value and lowpoint parent, there are three very
useful things which motivate our computation. useful things that motivate our computation.
First, if there is a child c of x such that L(c) >= D(x), then there First, if there is a child c of x such that L(c) >= D(x), then there
are no paths in the network graph that go from c or its descendants are no paths in the network graph that go from c or its descendants
to an ancestor of x - and therefore x is a cut-vertex. In Figure 9, to an ancestor of x; therefore, x is a cut-vertex. In Figure 9, this
this can be seen by looking at the DFS children of C. C has two can be seen by looking at the DFS children of C. C has two children,
children - D and F and L(F) = 3 = D(C) so it is clear that C is a D and F and L(F) = 3 = D(C); so, it is clear that C is a cut-vertex
cut-vertex and F is in a block where C is the block's root. L(D) = 0 and F is in a block where C is the block's root. L(D) = 0<3 = D(C),
< 3 = D(C) so D has a path to the ancestors of C; in this case, D can so D has a path to the ancestors of C; in this case, D can go via E
go via E to reach R. Comparing the low-point values of all a node's to reach R. Comparing the lowpoint values of all a node's DFS-
DFS-children with the node's DFS-value is very useful because it children with the node's DFS-value is very useful because it allows
allows identification of the cut-vertices and thus the blocks. identification of the cut-vertices and thus the blocks.
Second, by repeatedly following the path given by lowpoint_parent, Second, by repeatedly following the path given by lowpoint_parent,
there is a path from x back to an ancestor of x that does not use the there is a path from x back to an ancestor of x that does not use the
link [x, x.dfs_parent] in either direction. The full path need not link [x, x.dfs_parent] in either direction. The full path need not
be taken, but this gives a way of finding an initial cycle and then be taken, but this gives a way of finding an initial cycle and then
ears. ears.
Third, as seen in Figure 9, even if L(x) < D(x), there may be a block Third, as seen in Figure 9, even if L(x)<D(x), there may be a block
that contains both the root and a DFS-child of a node while other that contains both the root and a DFS-child of a node while other
DFS-children might be in different blocks. In this example, C's DFS-children might be in different blocks. In this example, C's
child D is in the same block as R while F is not. It is important to child D is in the same block as R while F is not. It is important to
realize that the root of a block may also be the root of another realize that the root of a block may also be the root of another
block. block.
4.4. Blocks in a Graph 4.4. Blocks in a Graph
A key idea for the MRT Lowpoint algorithm is that any non-2-connected A key idea for the MRT Lowpoint algorithm is that any non-2-connected
graph is made up by blocks (e.g. 2-connected clusters, cut-links, graph is made up by blocks (e.g., 2-connected clusters, cut-links,
and/or isolated nodes). To compute GADAGs and thus MRTs, computation and/or isolated nodes). To compute GADAGs and thus MRTs, computation
is done in each block to compute ADAGs or Redundant Trees and then is done in each block to compute ADAGs or Redundant Trees and then
those ADAGs or Redundant Trees are combined into a GADAG or MRT. those ADAGs or Redundant Trees are combined into a GADAG or MRT.
[E]---| [J]-------[I] [P]---[O] [E]---| [J]-------[I] [P]---[O]
| | | | | | | | | | | |
| | | | | | | | | | | |
[R] [D]---[C]--[F] [H]---[K] [N] [R] [D]---[C]--[F] [H]---[K] [N]
| | | | | | | | | | | |
| | | | | | | | | | | |
[A]--------[B] [G]---| [L]---[M] [A]--------[B] [G]---| [L]---[M]
(a) A graph with four blocks that are: (a) A graph with four blocks:
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]
skipping to change at page 15, line 42 skipping to change at page 15, line 42
| V | | | V | V | | | V
[A]<-------[B] [G]<--| [L]<--[M] [A]<-------[B] [G]<--| [L]<--[M]
(c) MRT-Red for destination R (c) MRT-Red for destination R
Figure 10 Figure 10
Consider the example depicted in Figure 10 (a). In this figure, a Consider the example depicted in Figure 10 (a). In this figure, a
special graph is presented, showing us all the ways 2-connected special graph is presented, showing us all the ways 2-connected
clusters can be connected. It has four blocks: block 1 contains R, clusters can be connected. It has four blocks: block 1 contains R,
A, B, C, D, E, block 2 contains C, F, G, H, I, J, block 3 contains K, A, B, C, D, E; block 2 contains C, F, G, H, I, J; block 3 contains K,
L, M, N, O, P, and block 4 is a cut-link containing H and K. As can L, M, N, O, P; and block 4 is a cut-link containing H and K. As can
be observed, the first two blocks have one common node (node C) and be observed, the first two blocks have one common node (node C) and
blocks 2 and 3 do not have any common node, but they are connected blocks 2 and 3 do not have any common node, but they are connected
through a cut-link that is block 4. No two blocks can have more than through a cut-link that is block 4. No two blocks can have more than
one common node, since two blocks with at least two common nodes one common node, since two blocks with at least two common nodes
would qualify as a single 2-connected cluster. would qualify as a single 2-connected cluster.
Moreover, observe that if we want to get from one block to another, Moreover, observe that if we want to get from one block to another,
we must use a cut-vertex (the cut-vertices in this graph are C, H, we must use a cut-vertex (the cut-vertices in this graph are C, H,
K), regardless of the path selected, so we can say that all the paths K), regardless of the path selected, so we can say that all the paths
from block 3 along the MRTs rooted at R will cross K first. This from block 3 along the MRTs rooted at R will cross K first. This
skipping to change at page 16, line 22 skipping to change at page 16, line 22
root, and finally, we need the last pair of RTs in block 1 with R as root, and finally, we need the last pair of RTs in block 1 with R as
a root. When all the trees are selected, we can simply combine them; a root. When all the trees are selected, we can simply combine them;
when a block is a cut-link (as in block 4), that cut-link is added in when a block is a cut-link (as in block 4), that cut-link is added in
the same direction to both of the trees. The resulting trees are the same direction to both of the trees. The resulting trees are
depicted in Figure 10 (b) and (c). depicted in Figure 10 (b) and (c).
Similarly, to create a GADAG it is sufficient to compute ADAGs in Similarly, to create a GADAG it is sufficient to compute ADAGs in
each block and connect them. each block and connect them.
It is necessary, therefore, to identify the cut-vertices, the blocks It is necessary, therefore, to identify the cut-vertices, the blocks
and identify the appropriate local-root to use for each block. and identify the appropriate localroot to use for each block.
4.5. Determining Local-Root and Assigning Block-ID 4.5. Determining Localroot and Assigning Block-ID
Each node in a network graph has a local-root, which is the cut- Each node in a network graph has a localroot, which is the cut-vertex
vertex (or root) in the same block that is closest to the root. The (or root) in the same block that is closest to the root. The
local-root is used to determine whether two nodes share a common localroot is used to determine whether two nodes share a common
block. block.
Compute_Localroot(node x, node localroot) Compute_Localroot(node x, node localroot)
x.localroot = localroot x.localroot = localroot
for each DFS child 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(gadag_root, gadag_root) Compute_Localroot(gadag_root, gadag_root)
Figure 11: A method for computing local-roots Figure 11: A Method for Computing Localroots
There are two different ways of computing the local-root for each There are two different ways of computing the localroot 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 GADAG construction methods illustrates the concept; it is used by the GADAG construction methods
given in Appendix B and Appendix C. The MRT Lowpoint algorithm given in Appendices B and C. The MRT Lowpoint algorithm computes the
computes the local-root for a block as part of computing the GADAG localroot for a block as part of computing the GADAG using lowpoint
using lowpoint inheritance; the essence of this computation is given inheritance; the essence of this computation is given in Figure 12.
in Figure 12. Both methods for computing the local-root produce the Both methods for computing the localroot produce the same results.
same results.
Get the current node, s. Get the current node, s.
Compute an ear(either through lowpoint inheritance Compute an ear (either through lowpoint inheritance
or by following dfs parents) from s to a ready node e. or by following dfs parents) from s to a ready node e.
(Thus, s is not e, if there is such ear.) (Thus, s is not e, if there is such ear.)
if s is e if s is e
for each node x in the ear that is not s for each node x in the ear that is not s
x.localroot = s x.localroot = s
else else
for each node x in the ear that is not s or e for each node x in the ear that is not s or e
x.localroot = e.localroot x.localroot = e.localroot
Figure 12: Ear-based method for computing local-roots Figure 12: Ear-Based Method for Computing Localroots
Once the local-roots are known, two nodes X and Y are in a common Once the localroots are known, two nodes X and Y are in a common
block if and only if one of the following three conditions apply. block if and only if one of the following three conditions apply.
o Y's local-root is X's local-root : They are in the same block and o Y's localroot is X's localroot : They are in the same block and
neither is the cut-vertex closest to the root. neither is the cut-vertex closest to the root.
o Y's local-root is X: X is the cut-vertex closest to the root for o Y's localroot is X: X is the cut-vertex closest to the root for
Y's block Y's block
o Y is X's local-root: Y is the cut-vertex closest to the root for o Y is X's localroot: Y is the cut-vertex closest to the root for
X's block X's block
Once we have computed the local-root for each node in the network Once we have computed the localroot for each node in the network
graph, we can assign for each node, a block id that represents the graph, we can assign for each node, a Block-ID that represents the
block in which the node is present. This computation is shown in block in which the node is present. This computation is shown in
Figure 13. Figure 13.
global_var: max_block_id global_var: max_block_id
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(gadag_root, max_block_id) Assign_Block_ID(gadag_root, max_block_id)
Figure 13: Assigning block id to identify blocks Figure 13: Assigning Block-ID to Identify Blocks
5. MRT Lowpoint Algorithm Specification 5. MRT Lowpoint Algorithm Specification
The MRT Lowpoint algorithm computes one GADAG that is then used by a The MRT Lowpoint algorithm computes one GADAG that is then used by a
router to determine its MRT-Blue and MRT-Red next-hops to all router to determine its MRT-Blue and MRT-Red next hops to all
destinations. Finally, based upon that information, alternates are destinations. Finally, based upon that information, alternates are
selected for each next-hop to each destination. The different parts selected for each next hop to each destination. The different parts
of this algorithm are described below. of this algorithm are described below.
o Order the interfaces in the network graph. [See Section 5.1] o Order the interfaces in the network graph. See Section 5.1.
o Compute the local MRT Island for the particular MRT Profile. [See o Compute the local MRT Island for the particular MRT Profile. See
Section 5.2] Section 5.2.
o Select the root to use for the GADAG. [See Section 5.3] o Select the root to use for the GADAG. See Section 5.3.
o Initialize all interfaces to UNDIRECTED. [See Section 5.4] o Initialize all interfaces to UNDIRECTED. See Section 5.4.
o Compute the DFS value,e.g. D(x), and lowpoint value, L(x). [See o Compute the DFS value, e.g., D(x), and lowpoint value, L(x). See
Figure 8] Figure 8.
o Construct the GADAG. [See Section 5.5] o Construct the GADAG. See Section 5.5.
o Assign directions to all interfaces that are still UNDIRECTED. o Assign directions to all interfaces that are still UNDIRECTED.
[See Section 5.6] See Section 5.6.
o From the computing router x, compute the next-hops for the MRT- o From the computing router x, compute the next hops for the MRT-
Blue and MRT-Red. [See Section 5.7] Blue and MRT-Red. See Section 5.7.
o Identify alternates for each next-hop to each destination by o 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 MRT-Blue and the MRT-Red the
computing router x should select. [See Section 5.8] computing router x should select. See Section 5.8.
A Python implementation of this algorithm is given in Appendix A. A Python implementation of this algorithm is given in Appendix A.
5.1. Interface Ordering 5.1. Interface Ordering
To ensure consistency in computation, all routers MUST order To ensure consistency in computation, all routers MUST order
interfaces identically down to the set of links with the same metric interfaces identically down to the set of links with the same metric
to the same neighboring node. This is necessary for the DFS in to the same neighboring node. This is necessary for the DFS in
Lowpoint_Visit in Section 4.3, where the selection order of the Lowpoint_Visit in Section 4.3, where the selection order of the
interfaces to explore results in different trees. Consistent interfaces to explore results in different trees. Consistent
skipping to change at page 19, line 21 skipping to change at page 19, line 21
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
// Same metric to same node, so the order doesn't matter for // Same metric to same node, so the order doesn't matter for
// interoperability. // interoperability.
return A_EQUAL_TO_B return A_EQUAL_TO_B
Figure 14: Rules for ranking multiple interfaces. Order is from low Figure 14: Rules for Ranking Multiple Interfaces (Order Is from Low
to high. to High)
In Figure 14, if two interfaces on a router connect to the same In Figure 14, if two interfaces on a router connect to the same
remote router with the same metric, the Interface_Compare function remote router with the same metric, the Interface_Compare function
returns A_EQUAL_TO_B. This is because the order in which those returns A_EQUAL_TO_B. This is because the order in which those
interfaces are initially explored does not affect the final GADAG interfaces are initially explored does not affect the final GADAG
produced by the algorithm described here. While only one of the produced by the algorithm described here. While only one of the
links will be added to the GADAG in the initial traversal, the other links will be added to the GADAG in the initial traversal, the other
parallel links will be added to the GADAG with the same direction parallel links will be added to the GADAG with the same direction
assigned during the procedure for assigning direction to UNDIRECTED assigned during the procedure for assigning direction to UNDIRECTED
links described in Section 5.6. An implementation is free to apply links described in Section 5.6. An implementation is free to apply
some additional criteria to break ties in interface ordering in this some additional criteria to break ties in interface ordering in this
situation, but that criteria is not specified here since it will not situation, but those criteria are not specified here since they will
affect the final GADAG produced by the algorithm. not 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 and applications is specified in Figure 15. The metric and IGPs and applications is specified in Figure 15. The metric and
mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is
normative. The metric and mrt_node_id values for ISIS-PCR in this normative. The metric and mrt_node_id values for IS-IS Path Control
table should be considered informational. The normative values are and Reservation (PCR) in this table should be considered
specified in [IEEE8021Qca] . informational. The normative values are specified in [IEEE8021Qca].
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id | metric of | | IGP/flooding | mrt_node_id | metric of |
| protocol | of neighbor | interface | | protocol | of neighbor | interface |
| and | on interface | | | and | on interface | |
| application | | | | application | | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| OSPFv2 for | 4 octet Neighbor | 2 octet Metric field | | OSPFv2 for | 4-octet Neighbor | 2-octet Metric field |
| IP/LDP FRR | Router ID in | for corresponding | | IP/LDP FRR | Router ID in | for corresponding |
| | Link ID field for | point-to-point link | | | Link ID field for | point-to-point link |
| | corresponding | in Router-LSA | | | corresponding | in Router-LSA |
| | point-to-point link | | | | point-to-point link | |
| | in Router-LSA | | | | in Router-LSA | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| OSPFv3 for | 4 octet Neighbor | 2 octet Metric field | | OSPFv3 for | 4-octet Neighbor | 2-octet Metric field |
| IP/LDP FRR | Router ID field | for corresponding | | IP/LDP FRR | Router ID field | for corresponding |
| | for corresponding | point-to-point link | | | for corresponding | point-to-point link |
| | point-to-point link | in Router-LSA | | | point-to-point link | in Router-LSA |
| | in Router-LSA | | | | in Router-LSA | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| IS-IS for | 7 octet neighbor | 3 octet metric field | | IS-IS for | 7-octet neighbor | 3-octet metric field |
| IP/LDP FRR | system ID and | in Extended IS | | IP/LDP FRR | system ID and | in Extended IS |
| | pseudonode number | Reachability TLV #22 | | | pseudonode number | Reachability TLV (type 22) |
| | in Extended IS | or Multi-Topology | | | in Extended IS | or Multi-Topology |
| | Reachability TLV #22 | IS Neighbor TLV #222 | | | Reachability TLV (type| IS Neighbor TLV (type 222) |
| | or Multi-Topology | | | | 22) or Multi-Topology | |
| | IS Neighbor TLV #222 | | | | IS Neighbor TLV (type | |
| | 222) | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
| ISIS-PCR for | 8 octet Bridge ID | 3 octet SPB-LINK-METRIC in | | IS-IS PCR for| 8-octet Bridge ID | 3-octet SPB-LINK-METRIC in |
| protection | created from 2 octet | SPB-Metric sub-TLV (type 29)| | protection | created from 2-octet | SPB-Metric sub-TLV (type 29)|
| of traffic | Bridge Priority in | in Extended IS Reachability | | of traffic | Bridge Priority in | in Extended IS Reachability |
| in bridged | SPB Instance sub-TLV | TLV #22 or Multi-Topology | | in bridged | Shortest Path Bridging| TLV (type 22) or |
| |SPB Instance sub-TLV | Multi-Topology |
| networks | (type 1) carried in | Intermediate Systems | | networks | (type 1) carried in | Intermediate Systems |
| | MT-Capability TLV | TLV #222. In the case | | | MT-Capability TLV | TLV (type 222). In the case|
| | #144 and 6 octet | of asymmetric link metrics, | | | (type 144) and 6-octet| of asymmetric link metrics, |
| | neighbor system ID in | the larger link metric | | | neighbor system ID in | the larger link metric |
| | Extended IS | is used for both link | | | Extended IS | is used for both link |
| | Reachability TLV #22 | directions. | | | Reachability TLV (type| directions. |
| | or Multi-Topology | (informational) | | | 22) or Multi-Topology | (informational) |
| | Intermediate Systems | | | | Intermediate Systems | |
| | TLV #222 | | | | TLV (type 222) | |
| | (informational) | | | | (informational) | |
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
Figure 15: value of interface.neighbor.mrt_node_id and Figure 15: Value of interface.neighbor.mrt_node_id and
interface.metric to be used for ranking interfaces, for different interface.metric to Be Used for Ranking Interfaces, for Different
flooding protocols and applications Flooding Protocols and Applications
The metrics are unsigned integers and MUST be compared as unsigned The metrics are unsigned integers and MUST be compared as unsigned
integers. The results of mrt_node_id comparisons MUST be the same as integers. The results of mrt_node_id comparisons MUST be the same as
would be obtained by converting the mrt_node_ids to unsigned integers would be obtained by converting the mrt_node_ids to unsigned integers
using network byte order and performing the comparison as unsigned using network byte order and performing the comparison as unsigned
integers. In the case of IS-IS for IP/LDP FRR with point-to-point integers. In the case of IS-IS for IP/LDP FRR with point-to-point
links, the pseudonode number (the 7th octet) is zero. Broadcast links, the pseudonode number (the 7th octet) is zero. Broadcast
interfaces will be discussed in Section 7. interfaces will be discussed in Section 7.
5.2. MRT Island Identification 5.2. MRT Island Identification
The local MRT Island for a particular MRT profile can be determined The local MRT Island for a particular MRT profile can be determined
by starting from the computing router in the network graph and doing by starting from the computing router in the network graph and doing
a breadth-first-search (BFS). The BFS explores only links that are a breadth-first-search (BFS). The BFS explores only links that are
in the same area/level, are not IGP-excluded, and are not MRT- in the same area/level, are not IGP-excluded, and are not MRT-
ineligible. The BFS explores only nodes that are are not IGP- ineligible. The BFS explores only nodes that support the particular
excluded, and that support the particular MRT profile. See section 7 MRT profile. See Section 7 of [RFC7812] for more-precise definitions
of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions
of these criteria. of these criteria.
MRT_Island_Identification(topology, computing_rtr, profile_id, area) MRT_Island_Identification(topology, computing_rtr, profile_id, area)
for all routers in topology for all routers in topology
rtr.IN_MRT_ISLAND = FALSE rtr.IN_MRT_ISLAND = FALSE
computing_rtr.IN_MRT_ISLAND = TRUE computing_rtr.IN_MRT_ISLAND = TRUE
explore_list = { computing_rtr } explore_list = { computing_rtr }
while (explore_list is not empty) while (explore_list is not empty)
next_rtr = remove_head(explore_list) next_rtr = remove_head(explore_list)
for each intf in next_rtr for each intf in next_rtr
if (not intf.MRT-ineligible if (not intf.IN_MRT_ISLAND
and not intf.MRT-ineligible
and not intf.remote_intf.MRT-ineligible and not intf.remote_intf.MRT-ineligible
and not intf.IGP-excluded and (intf in area) and not intf.IGP-excluded and (intf in area)
and (intf.remote_node supports profile_id) ) and (intf.remote_node supports profile_id) )
intf.IN_MRT_ISLAND = TRUE intf.IN_MRT_ISLAND = TRUE
intf.remote_node.IN_MRT_ISLAND = TRUE intf.remote_intf.IN_MRT_ISLAND = TRUE
if (not intf.remote_node.IN_MRT_ISLAND)) if (not intf.remote_node.IN_MRT_ISLAND))
intf.remote_node.IN_MRT_ISLAND = TRUE intf.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, intf.remote_node) add_to_tail(explore_list, intf.remote_node)
Figure 16: MRT Island Identification Figure 16: MRT Island Identification
5.3. GADAG Root Selection 5.3. GADAG Root Selection
In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG In Section 8.3 of [RFC7812], the GADAG Root Selection Policy is
Root Selection Policy is described for the MRT default profile. This described for the Default MRT Profile. This selection policy allows
selection policy allows routers to consistently select a common GADAG routers to consistently select a common GADAG Root inside the local
Root inside the local MRT Island, based on advertised priority MRT Island, based on advertised priority values. The MRT Lowpoint
values. The MRT Lowpoint algorithm simply requires that all routers algorithm simply requires that all routers in the MRT Island MUST
in the MRT Island MUST select the same GADAG Root; the mechanism can select the same GADAG Root; the mechanism can vary based upon the MRT
vary based upon the MRT profile description. Before beginning profile description. Before beginning computation, the network graph
computation, the network graph is reduced to contain only the set of is reduced to contain only the set of routers that support the
routers that support the specific MRT profile whose MRTs are being specific MRT profile whose MRTs are being computed.
computed.
As noted in Section 7, pseudonodes MUST NOT be considered for GADAG As noted in Section 7, pseudonodes MUST NOT be considered for GADAG
root selection. root selection.
It is expected that an operator will designate a set of routers as It is expected that an operator will designate a set of routers as
good choices for selection as GADAG root by setting the GADAG Root good choices for selection as GADAG root by setting the GADAG Root
Selection Priority for that set of routers to lower (more preferred) Selection Priority for that set of routers to lower (more preferred)
numerical values. For guidance on setting the GADAG Root Selection numerical values. For guidance on setting the GADAG Root Selection
Priority values, refer to Section 10.1. Priority values, refer to Section 9.1.
5.4. Initialization 5.4. Initialization
Before running the algorithm, there is the standard type of Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFS-values, initialization to be done, such as clearing any computed DFS-values,
lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed lowpoint-values, DFS parents, lowpoint-parents, any MRT-computed next
next-hops, and flags associated with algorithm. hops, and flags associated with algorithm.
It is assumed that a regular SPF computation has been run so that the It is assumed that a regular SPF computation has been run so that the
primary next-hops from the computing router to each destination are primary next hops from the computing router to each destination are
known. This is required for determining alternates at the last step. known. This is required for determining alternates at the last step.
Initially, all interfaces MUST be initialized to UNDIRECTED. Whether Initially, all interfaces MUST be initialized to UNDIRECTED. Whether
they are OUTGOING, INCOMING or both is determined when the GADAG is they are OUTGOING, INCOMING, or both is determined when the GADAG is
constructed and augmented. constructed and augmented.
It is possible that some links and nodes will be marked using It is possible that some links and nodes will be marked using
standard IGP mechanisms to discourage or prevent transit traffic. standard IGP mechanisms to discourage or prevent transit traffic.
Section 7.3.1 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes how Section 7.3.1 of [RFC7812] describes how those links and nodes are
those links and nodes are excluded from MRT Island formation. excluded from MRT Island formation.
MRT-FRR also has the ability to advertise links MRT-Ineligible, as MRT-FRR also has the ability to advertise links MRT-Ineligible, as
described in Section 7.3.2 of [I-D.ietf-rtgwg-mrt-frr-architecture]. described in Section 7.3.2 of [RFC7812]. These links are excluded
These links are excluded from the MRT Island and the GADAG. from the MRT Island and the GADAG. Computation of MRT next hops will
Computation of MRT next-hops will therefore not use any MRT- therefore not use any MRT-ineligible links. The MRT Lowpoint
ineligible links. The MRT algorithm does still need to consider MRT- algorithm does still need to consider MRT-ineligible links when
ineligible links when computing FRR alternates, because an MRT- computing FRR alternates, because an MRT-ineligible link can still be
ineligible link can still be the shortest-path next-hop to reach a the shortest-path next hop to reach a destination.
destination.
When a broadcast interface is advertised as MRT-ineligible, then the When a broadcast interface is advertised as MRT-ineligible, then the
pseudo-node representing the entire broadcast network MUST NOT be pseudonode representing the entire broadcast network MUST NOT be
included in the MRT Island. This is equivalent to excluding all of included in the MRT Island. This is equivalent to excluding all of
the broadcast interfaces on that broadcast network from the MRT the broadcast interfaces on that broadcast network from the MRT
Island. Island.
5.5. Constructing the GADAG using lowpoint inheritance 5.5. Constructing the GADAG Using Lowpoint Inheritance
As discussed in Section 4.2, it is necessary to find ears from a node As discussed in Section 4.2, it is necessary to find ears from a node
x that is already in the GADAG (known as IN_GADAG). Two different x that is already in the GADAG (known as IN_GADAG). Two different
methods are used to find ears in the algorithm. The first is by methods are used to find ears in the algorithm. The first is by
going to a not IN_GADAG DFS-child and then following the chain of going to a DFS-child that is not IN_GADAG and then following the
low-point parents until an IN_GADAG node is found. The second is by chain of lowpoint parents until an IN_GADAG node is found. The
going to a not IN_GADAG neighbor and then following the chain of DFS second is by going to a neighbor that is not IN_GADAG and then
parents until an IN_GADAG node is found. As an ear is found, the following the chain of DFS parents until an IN_GADAG node is found.
associated interfaces are marked based on the direction taken. The As an ear is found, the associated interfaces are marked based on the
nodes in the ear are marked as IN_GADAG. In the algorithm, first the direction taken. The nodes in the ear are marked as IN_GADAG. In
ears via DFS-children are found and then the ears via DFS-neighbors the algorithm, first the ears via DFS-children are found and then the
are found. ears via DFS-neighbors are found.
By adding both types of ears when an IN_GADAG node is processed, all By adding both types of ears when an IN_GADAG node is processed, all
ears that connect to that node are found. The order in which the ears that connect to that node are found. The order in which the
IN_GADAG nodes is processed is, of course, key to the algorithm. The IN_GADAG nodes are processed is, of course, key to the algorithm.
order is a stack of ears so the most recent ear is found at the top The order is a stack of ears so the most recent ear is found at the
of the stack. Of course, the stack stores nodes and not ears, so an top of the stack. Of course, the stack stores nodes and not ears, so
ordered list of nodes, from the first node in the ear to the last an ordered list of nodes, from the first node in the ear to the last
node in the ear, is created as the ear is explored and then that list node in the ear, is created as the ear is explored and then that list
is pushed onto the stack. is pushed onto the stack.
Each ear represents a partial order (see Figure 4) and processing the Each ear represents a partial order (see Figure 4) and processing the
nodes in order along each ear ensures that all ears connecting to a nodes in order along each ear ensures that all ears connecting to a
node are found before a node higher in the partial order has its ears node are found before a node higher in the partial order has its ears
explored. This means that the direction of the links in the ear is explored. This means that the direction of the links in the ear is
always from the node x being processed towards the other end of the always from the node x being processed towards the other end of the
ear. Additionally, by using a stack of ears, this means that any ear. Additionally, by using a stack of ears, this means that any
unprocessed nodes in previous ears can only be ordered higher than unprocessed nodes in previous ears can only be ordered higher than
nodes in the ears below it on the stack. nodes in the ears below it on the stack.
In this algorithm that depends upon Low-Point inheritance, it is In this algorithm that depends upon Lowpoint inheritance, it is
necessary that every node have a low-point parent that is not itself. necessary that every node has a lowpoint parent that is not itself.
If a node is a cut-vertex, that may not yet be the case. Therefore, If a node is a cut-vertex, that may not yet be the case. Therefore,
any nodes without a low-point parent will have their low-point parent any nodes without a lowpoint parent will have their lowpoint parent
set to their DFS parent and their low-point value set to the DFS- set to their DFS parent and their lowpoint value set to the DFS-value
value of their parent. This assignment also properly allows an ear of their parent. This assignment also properly allows an ear between
between two cut-vertices. two cut-vertices.
Finally, the algorithm simultaneously computes each node's local- Finally, the algorithm simultaneously computes each node's localroot,
root, as described in Figure 12. This is further elaborated as as described in Figure 12. This is further elaborated as follows.
follows. The local-root can be inherited from the node at the end of The localroot can be inherited from the node at the end of the ear
the ear unless the end of the ear is x itself, in which case the unless the end of the ear is x itself, in which case the localroot
local-root for all the nodes in the ear would be x. This is because for all the nodes in the ear would be x. This is because whenever
whenever the first cycle is found in a block, or an ear involving a the first cycle is found in a block, or an ear involving a bridge is
bridge is computed, the cut-vertex closest to the root would be x computed, the cut-vertex closest to the root would be x itself. In
itself. In all other scenarios, the properties of lowpoint/dfs all other scenarios, the properties of lowpoint/dfs parents ensure
parents ensure that the end of the ear will be in the same block, and that the end of the ear will be in the same block, and thus
thus inheriting its local-root would be the correct local-root for inheriting its localroot would be the correct localroot for all newly
all newly added nodes. added nodes.
The pseudo-code for the GADAG algorithm (assuming that the adjustment The pseudocode for the GADAG algorithm (assuming that the adjustment
of lowpoint for cut-vertices has been made) is shown in Figure 17. of lowpoint for cut-vertices has been made) is shown in Figure 17.
Construct_Ear(x, Stack, intf, ear_type) Construct_Ear(x, Stack, intf, ear_type)
ear_list = empty ear_list = empty
cur_node = intf.remote_node cur_node = intf.remote_node
cur_intf = intf cur_intf = intf
not_done = true not_done = true
while not_done while not_done
cur_intf.UNDIRECTED = false cur_intf.UNDIRECTED = false
skipping to change at page 24, line 41 skipping to change at page 24, line 41
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 x.IS_CUT_VERTEX = true
localroot = x localroot = x
else else
// Inherit local-root from the end of the ear // Inherit localroot 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, gadag_root) Construct_GADAG_via_Lowpoint(topology, gadag_root)
gadag_root.IN_GADAG = true gadag_root.IN_GADAG = true
gadag_root.localroot = None gadag_root.localroot = None
Initialize Stack to empty Initialize Stack to empty
skipping to change at page 25, line 18 skipping to change at page 25, line 18
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 ordered_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, gadag_root) Construct_GADAG_via_Lowpoint(topology, gadag_root)
Figure 17: Low-point Inheritance GADAG algorithm Figure 17: Lowpoint 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 method used to construct it, at this The GADAG, regardless of the method used to construct it, at this
point could be used to find MRTs, but the topology does not include point could be used to find MRTs, but the topology does not include
all links in the network graph. That has two impacts. First, there all links in the network graph. That has two impacts. First, there
might be shorter paths that respect the GADAG partial ordering and so might be shorter paths that respect the GADAG partial ordering and so
the alternate paths would not be as short as possible. Second, there the alternate paths would not be as short as possible. Second, there
may be additional paths between a router x and the root that are not may be additional paths between a router x and the root that are not
included in the GADAG. Including those provides potentially more included in the GADAG. Including those provides potentially more
bandwidth to traffic flowing on the alternates and may reduce bandwidth to traffic flowing on the alternates and may reduce
congestion compared to just using the GADAG as currently constructed. congestion compared to just using the GADAG as currently constructed.
The goal is thus to assign direction to every remaining link marked The goal is thus to assign direction to every remaining link marked
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
MRTs are computed. MRTs are computed.
To do this, we need to establish a total order that respects the To do this, we need to establish a total order that respects the
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. When adding undirected links to the GADAG, links connecting done. When adding undirected links to the GADAG, links connecting
the block root to other nodes in that block need special handling the block root to other nodes in that block need special handling
because the topological order will not always give the right answer because the topological order will not always give the right answer
for those links. There are three cases to consider. If the for those links. There are three cases to consider. If the
undirected link in question has another parallel link between the undirected link in question has another parallel link between the
same two nodes that is already directed, then the direction of the same two nodes that is already directed, then the direction of the
undirected link can be inherited from the previously directed link. undirected link can be inherited from the previously directed link.
In the case of parallel cut links, we set all of the parallel links In the case of parallel cut links, we set all of the parallel links
to both INCOMING and OUTGOING. Otherwise, the undirected link in to both INCOMING and OUTGOING. Otherwise, the undirected link in
question is set to OUTGOING from the block root node. A cut-link can 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 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 and OUTGOING in the GADAG. The exact details of this whole process
are captured in Figure 18 are captured in Figure 18.
Add_Undirected_Block_Root_Links(topo, gadag_root) Add_Undirected_Block_Root_Links(topo, gadag_root)
foreach node x in topo foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_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 not x if (i.remote_node.localroot is not x
or i.PROCESSED ) or i.PROCESSED )
continue continue
Initialize bundle_list to empty Initialize bundle_list to empty
bundle.UNDIRECTED = true bundle.UNDIRECTED = true
skipping to change at page 28, line 42 skipping to change at page 28, line 42
i.remote_intf.OUTGOING = true i.remote_intf.OUTGOING = true
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, gadag_root) Add_Undirected_Links(topo, gadag_root)
Add_Undirected_Block_Root_Links(topo, gadag_root) Add_Undirected_Block_Root_Links(topo, gadag_root)
Run_Topological_Sort_GADAG(topo, gadag_root) Run_Topological_Sort_GADAG(topo, gadag_root)
Set_Other_Undirected_Links_Based_On_Topo_Order(topo) Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
Add_Undirected_Links(topo, gadag_root) 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
As was discussed in Section 4.1, once a ADAG is found, it is As was discussed in Section 4.1, once an ADAG is found, it is
straightforward to find the next-hops from any node X to the ADAG straightforward to find the next hops from any node X to the ADAG
root. However, in this algorithm, we will reuse the common GADAG and root. However, in this algorithm, we will reuse the common GADAG and
find not only the one pair of MRTs rooted at the GADAG root with it, find not only the one pair of MRTs rooted at the GADAG root with it,
but find a pair rooted at each node. This is useful since it is but find a pair rooted at each node. This is useful since it is
significantly faster to compute. significantly faster to compute.
The method for computing differently rooted MRTs from the common The method for computing differently rooted MRTs from the common
GADAG is based on two ideas. First, if two nodes X and Y are ordered GADAG is based on two ideas. First, if two nodes X and Y are ordered
with respect to each other in the partial order, then an SPF along with respect to each other in the partial order, then an SPF along
OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a
decreasing-SPF) can be used to find the increasing and decreasing decreasing-SPF) can be used to find the increasing and decreasing
paths. Second, if two nodes X and Y aren't ordered with respect to paths. Second, if two nodes X and Y aren't ordered with respect to
each other in the partial order, then intermediary nodes can be used each other in the partial order, then intermediary nodes can be used
to create the paths by increasing/decreasing to the intermediary and to create the paths by increasing/decreasing to the intermediary and
then decreasing/increasing to reach Y. then decreasing/increasing to reach Y.
As usual, the two basic ideas will be discussed assuming the network As usual, the two basic ideas will be discussed assuming the network
is two-connected. The generalization to multiple blocks is discussed is 2-connected. The generalization to multiple blocks is discussed
in Section 5.7.4. The full algorithm is given in Section 5.7.5. in Section 5.7.4. The full algorithm is given in Section 5.7.5.
5.7.1. MRT next-hops to all nodes ordered with respect to the computing 5.7.1. MRT Next Hops to All Nodes Ordered with Respect to the Computing
node Node
To find two node-disjoint paths from the computing router X to any Finding two node-disjoint paths from the computing router X to any
node Y, depends upon whether Y >> X or Y << X. As shown in node Y depends upon whether Y>>X or Y<<X. As shown in Figure 19, if
Figure 19, if Y >> X, then there is an increasing path that goes from Y>>X, then there is an increasing path that goes from X to Y without
X to Y without crossing R; this contains nodes in the interval [X,Y]. crossing R; this contains nodes in the interval [X,Y]. There is also
There is also a decreasing path that decreases towards R and then a decreasing path that decreases towards R and then decreases from R
decreases from R to Y; this contains nodes in the interval to Y; this contains nodes in the interval [X,R-small] or [R-great,Y].
[X,R-small] or [R-great,Y]. The two paths cannot have common nodes The two paths cannot have common nodes other than X and Y.
other than X and Y.
[Y]<---(Cloud 2)<--- [X] [Y]<---(Cloud 2)<--- [X]
| ^ | ^
| | | |
V | V |
(Cloud 3)--->[R]--->(Cloud 1) (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 2->Y MRT-Blue path: X->Cloud 2->Y
MRT-Red path: X->Cloud 1->R->Cloud 3->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y
Figure 19: Y >> X Figure 19: Y>>X
Similar logic applies if Y << X, as shown in Figure 20. In this Similar logic applies if Y<<X, as shown in Figure 20. In this case,
case, the increasing path from X increases to R and then increases the increasing path from X increases to R and then increases from R
from R to Y to use nodes in the intervals [X,R-great] and [R-small, to Y to use nodes in the intervals [X,R-great] and [R-small, Y]. The
Y]. The decreasing path from X reaches Y without crossing R and uses decreasing path from X reaches Y without crossing R and uses nodes in
nodes in the interval [Y,X]. the interval [Y,X].
[X]<---(Cloud 2)<--- [Y] [X]<---(Cloud 2)<--- [Y]
| ^ | ^
| | | |
V | V |
(Cloud 3)--->[R]--->(Cloud 1) (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Blue path: X->Cloud 3->R->Cloud 1->Y
MRT-Red path: X->Cloud 2->Y MRT-Red path: X->Cloud 2->Y
Figure 20: Y << X Figure 20: Y<<X
5.7.2. MRT next-hops to all nodes not ordered with respect to the 5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect to the
computing node Computing Node
When X and Y are not ordered, the first path should increase until we When X and Y are not ordered, the first path should increase until we
get to a node G, where G >> Y. At G, we need to decrease to Y. The get to a node G, where G>>Y. At G, we need to decrease to Y. The
other path should be just the opposite: we must decrease until we get other path should be just the opposite: we must decrease until we get
to a node H, where H << Y, and then increase. Since R is smaller and to a node H, where H<<Y, and then increase. Since R is smaller and
greater than Y, such G and H must exist. It is also easy to see that greater than Y, such G and H must exist. It is also easy to see that
these two paths must be node disjoint: the first path contains nodes these two paths must be node disjoint: the first path contains nodes
in interval [X,G] and [Y,G], while the second path contains nodes in in interval [X,G] and [Y,G], while the second path contains nodes in
interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is
necessary to decrease and then increase for the MRT-Blue and increase necessary to decrease and then increase for the MRT-Blue and increase
and then decrease for the MRT-Red; if one simply increased for one and then decrease for the MRT-Red; if one simply increased for one
and decreased for the other, then both paths would go through the and decreased for the other, then both paths would go through the
root R. root R.
(Cloud 6)<---[Y]<---(Cloud 5)<------------| (Cloud 6)<---[Y]<---(Cloud 5)<------------|
skipping to change at page 31, line 20 skipping to change at page 31, line 20
^ | ^ |
| | | |
| | | |
(Cloud 3)<---[X]<---(Cloud 2)<-----------| (Cloud 3)<---[X]<---(Cloud 2)<-----------|
MRT-Blue path: decrease to H and increase to Y MRT-Blue path: decrease to H and increase to Y
X->Cloud 2->H->Cloud 5->Y X->Cloud 2->H->Cloud 5->Y
MRT-Red path: increase to G and decrease to Y MRT-Red path: increase to G and decrease to Y
X->Cloud 3->G->Cloud 6->Y X->Cloud 3->G->Cloud 6->Y
Figure 21: X and Y unordered Figure 21: X and Y Unordered
This gives disjoint paths as long as G and H are not the same node. This gives disjoint paths as long as G and H are not the same node.
Since G >> Y and H << Y, if G and H could be the same node, that Since G>>Y and H<<Y, if G and H could be the same node, that would
would have to be the root R. This is not possible because there is have to be the root R. This is not possible because there is only
only one incoming interface to the root R which is created when the one incoming interface to the root R that is created when the initial
initial cycle is found. Recall from Figure 6 that whenever an ear cycle is found. Recall from Figure 6 that whenever an ear was found
was found to have an end that was the root R, the ear was directed to have an end that was the root R, the ear was directed from R so
from R so that the associated interface on R is outgoing and not that the associated interface on R is outgoing and not incoming.
incoming. Therefore, there must be exactly one node M which is the Therefore, there must be exactly one node M that is the largest one
largest one before R, so the MRT-Red path will never reach R; it will before R, so the MRT-Red path will never reach R; it will turn at M
turn at M and decrease to Y. and decrease to Y.
5.7.3. Computing Redundant Tree next-hops in a 2-connected Graph 5.7.3. Computing Redundant Tree Next Hops in a 2-Connected Graph
The basic ideas for computing RT next-hops in a 2-connected graph The basic ideas for computing RT next hops in a 2-connected graph
were given in Section 5.7.1 and Section 5.7.2. Given these two were given in Sections 5.7.1 and 5.7.2. Given these two ideas, how
ideas, how can we find the trees? can we find the trees?
If some node X only wants to find the next-hops (which is usually the If some node X only wants to find the next hops (which is usually the
case for IP networks), it is enough to find which nodes are greater case for IP networks), it is enough to find which nodes are greater
and less than X, and which are not ordered; this can be done by and less than X, and which are not ordered; this can be done by
running an increasing-SPF and a decreasing-SPF rooted at X and not running an increasing-SPF and a decreasing-SPF rooted at X and not
exploring any links from the ADAG root. exploring any links from the ADAG root.
In principle, an traversal method other than SPF could be used to In principle, a traversal method other than SPF could be used to
traverse the GADAG in the process of determining blue and red next- traverse the GADAG in the process of determining blue and red next
hops that result in maximally redundant trees. This will be the case hops that result in maximally redundant trees. This will be the case
as long as one traversal uses the links in the direction specified by as long as one traversal uses the links in the direction specified by
the GADAG and the other traversal uses the links in the direction the GADAG and the other traversal uses the links in the direction
opposite of that specified by the GADAG. However, a different opposite of that specified by the GADAG. However, a different
traversal algorithm will generally result in different blue and red traversal algorithm will generally result in different blue and red
next-hops. Therefore, the algorithm specified here requires the use next hops. Therefore, the algorithm specified here requires the use
of SPF to traverse the GADAG to generate MRT blue and red next-hops, of SPF to traverse the GADAG to generate MRT blue and red next hops,
as described below. as described below.
An increasing-SPF rooted at X and not exploring links from the root An increasing-SPF rooted at X and not exploring links from the root
will find the increasing next-hops to all Y >> X. Those increasing will find the increasing next hops to all Y>>X. Those increasing
next-hops are X's next-hops on the MRT-Blue to reach Y. A next hops are X's next hops on the MRT-Blue to reach Y. A
decreasing-SPF rooted at X and not exploring links from the root will decreasing-SPF rooted at X and not exploring links from the root will
find the decreasing next-hops to all Z << X. Those decreasing next- find the decreasing next hops to all Z<<X. Those decreasing next
hops are X's next-hops on the MRT-Red to reach Z. Since the root R hops are X's next hops on the MRT-Red to reach Z. Since the root R
is both greater than and less than X, after this increasing-SPF and is both greater than and less than X, after this increasing-SPF and
decreasing-SPF, X's next-hops on the MRT-Blue and on the MRT-Red to decreasing-SPF, X's next hops on the MRT-Blue and on the MRT-Red to
reach R are known. For every node Y >> X, X's next-hops on the MRT- reach R are known. For every node Y>>X, X's next hops on the MRT-Red
Red to reach Y are set to those on the MRT-Red to reach R. For every to reach Y are set to those on the MRT-Red to reach R. For every
node Z << X, X's next-hops on the MRT-Blue to reach Z are set to node Z<<X, X's next hops on the MRT-Blue to reach Z are set to those
those on the MRT-Blue to reach R. on the MRT-Blue to reach R.
For those nodes which were not reached by either the increasing-SPF For those nodes that were not reached by either the increasing-SPF or
or the decreasing-SPF, we can determine the next-hops as well. The the decreasing-SPF, we can determine the next hops as well. The
increasing MRT-Blue next-hop for a node which is not ordered with increasing MRT-Blue next hop for a node that is not ordered with
respect to X is the next-hop along the decreasing MRT-Red towards R, respect to X is the next hop along the decreasing MRT-Red towards R,
and the decreasing MRT-Red next-hop is the next-hop along the and the decreasing MRT-Red next hop is the next hop along the
increasing MRT-Blue towards R. Naturally, since R is ordered with increasing MRT-Blue towards R. Naturally, since R is ordered with
respect to all the nodes, there will always be an increasing and a respect to all the nodes, there will always be an increasing and a
decreasing path towards it. This algorithm does not provide the decreasing path towards it. This algorithm does not provide the
complete specific path taken but just the appropriate next-hops to complete specific path taken but just the appropriate next hops to
use. The identities of G and H are not determined by the computing use. The identities of G and H are not determined by the computing
node X. node X.
The final case to consider is when the GADAG root R computes its own The final case to consider is when the GADAG root R computes its own
next-hops. Since the GADAG root R is << all other nodes, running an next hops. Since the GADAG root R is << all other nodes, running an
increasing-SPF rooted at R will reach all other nodes; the MRT-Blue increasing-SPF rooted at R will reach all other nodes; the MRT-Blue
next-hops are those found with this increasing-SPF. Similarly, since next hops are those found with this increasing-SPF. Similarly, since
the GADAG root R is >> all other nodes, running a decreasing-SPF the GADAG root R is >> all other nodes, running a decreasing-SPF
rooted at R will reach all other nodes; the MRT-Red next-hops are rooted at R will reach all other nodes; the MRT-Red next hops are
those found with this decreasing-SPF. those found with this decreasing-SPF.
E---D---| E<--D<--| E---D---| E<--D<--|
| | | | ^ | | | | | ^ |
| | | V | | | | | V | |
R F C R F C R F C R F C
| | | | ^ ^ | | | | ^ ^
| | | V | | | | | V | |
A---B---| A-->B---| A---B---| A-->B---|
(a) (b) (a) (b)
A 2-connected graph A spanning ADAG rooted at R A 2-connected graph A spanning ADAG rooted at R
Figure 22 Figure 22
As an example consider the situation depicted in Figure 22. Node C As an example, consider the situation depicted in Figure 22. Node C
runs an increasing-SPF and a decreasing-SPF on the ADAG. The runs an increasing-SPF and a decreasing-SPF on the ADAG. The
increasing-SPF reaches D, E and R and the decreasing-SPF reaches B, A increasing-SPF reaches D, E, and R; the decreasing-SPF reaches B, A,
and R. E>>C. So towards E the MRT-Blue next-hop is D, since E was and R. E>>C. So, towards E the MRT-Blue next hop is D, since E was
reached on the increasing path through D. And the MRT-Red next-hop reached on the increasing path through D. The MRT-Red next hop
towards E is B, since R was reached on the decreasing path through B. towards E is B, since R was reached on the decreasing path through B.
Since E>>D, D will similarly compute its MRT-Blue next-hop to be E, Since E>>D, D will similarly compute its MRT-Blue next hop to be E,
ensuring that a packet on MRT-Blue will use path C-D-E. B, A and R ensuring that a packet on MRT-Blue will use path C-D-E. B, A, and R
will similarly compute the MRT-Red next-hops towards E (which is will similarly compute the MRT-Red next hops towards E (which is
ordered less than B, A and R), ensuring that a packet on MRT-Red will ordered less than B, A and R), ensuring that a packet on MRT-Red will
use path C-B-A-R-E. use path C-B-A-R-E.
C can determine the next-hops towards F as well. Since F is not C can determine the next hops towards F as well. Since F is not
ordered with respect to C, the MRT-Blue next-hop is the decreasing ordered with respect to C, the MRT-Blue next hop is the decreasing
one towards R (which is B) and the MRT-Red next-hop is the increasing one towards R (which is B) and the MRT-Red next hop is the increasing
one towards R (which is D). Since F>>B, for its MRT-Blue next-hop one towards R (which is D). Since F>>B, for its MRT-Blue next hop
towards F, B will use the real increasing next-hop towards F. So a towards F, B will use the real increasing next hop towards F. So a
packet forwarded to B on MRT-Blue will get to F on path C-B-F. packet forwarded to B on MRT-Blue will get to F on path C-B-F.
Similarly, D will use the real decreasing next-hop towards F as its Similarly, D will use the real decreasing next hop towards F as its
MRT-Red next-hop, a packet on MRT-Red will use path C-D-F. MRT-Red next hop, a packet on MRT-Red will use path C-D-F.
5.7.4. Generalizing for a graph that isn't 2-connected 5.7.4. Generalizing for a Graph That Isn't 2-Connected
If a graph isn't 2-connected, then the basic approach given in If a graph isn't 2-connected, then the basic approach given in
Section 5.7.3 needs some extensions to determine the appropriate MRT Section 5.7.3 needs some extensions to determine the appropriate MRT
next-hops to use for destinations outside the computing router X's next hops to use for destinations outside the computing router X's
blocks. In order to find a pair of maximally redundant trees in that blocks. In order to find a pair of maximally redundant trees in that
graph we need to find a pair of RTs in each of the blocks (the root graph, we need to find a pair of RTs in each of the blocks (the root
of these trees will be discussed later), and combine them. of these trees will be discussed later) and combine them.
When computing the MRT next-hops from a router X, there are three When computing the MRT next hops from a router X, there are three
basic differences: basic differences:
1. Only nodes in a common block with X should be explored in the 1. Only nodes in a common block with X should be explored in the
increasing-SPF and decreasing-SPF. increasing-SPF and decreasing-SPF.
2. Instead of using the GADAG root, X's local-root should be used. 2. Instead of using the GADAG root, X's localroot should be used.
This has the following implications: This has the following implications:
A. The links from X's local-root should not be explored. A. The links from X's localroot should not be explored.
B. If a node is explored in the outgoing SPF so Y >> X, then X's B. If a node is explored in the outgoing SPF so Y>>X, then X's
MRT-Red next-hops to reach Y uses X's MRT-Red next-hops to MRT-Red next hops to reach Y uses X's MRT-Red next hops to
reach X's local-root and if Z << X, then X's MRT-Blue next- reach X's localroot and if Z<<X, then X's MRT-Blue next hops
hops to reach Z uses X's MRT-Blue next-hops to reach X's to reach Z uses X's MRT-Blue next hops to reach X's
local-root. localroot.
C. If a node W in a common block with X was not reached in the C. If a node W in a common block with X was not reached in the
increasing-SPF or decreasing-SPF, then W is unordered with increasing-SPF or decreasing-SPF, then W is unordered with
respect to X. X's MRT-Blue next-hops to W are X's decreasing respect to X. X's MRT-Blue next hops to W are X's decreasing
(aka MRT-Red) next-hops to X's local-root. X's MRT-Red next- (aka MRT-Red) next hops to X's localroot. X's MRT-Red next
hops to W are X's increasing (aka MRT-Blue) next-hops to X's hops to W are X's increasing (aka MRT-Blue) next hops to X's
local-root. localroot.
3. For nodes in different blocks, the next-hops must be inherited 3. For nodes in different blocks, the next hops must be inherited
via the relevant cut-vertex. via the relevant cut-vertex.
These are all captured in the detailed algorithm given in These are all captured in the detailed algorithm given in
Section 5.7.5. Section 5.7.5.
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
skipping to change at page 34, line 52 skipping to change at page 35, line 29
SPF_No_Traverse_Block_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 == intf.remote_node.spf_metric else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root if min_node is spf_root
skipping to change at page 35, line 36 skipping to change at page 36, line 13
y.order_proxy = y.localroot.order_proxy y.order_proxy = y.localroot.order_proxy
Compute_MRT_NextHops(x, gadag_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_Block_Root(x, x.localroot, FORWARD) SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD)
SPF_No_Traverse_Block_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 node whose localroot is x will have its
// 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 localroot
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 gadag_root) and (x.localroot is not gadag_root) if (x is not gadag_root) and (x.localroot is not gadag_root)
gadag_root.blue_next_hops = x.localroot.blue_next_hops gadag_root.blue_next_hops = x.localroot.blue_next_hops
gadag_root.red_next_hops = x.localroot.red_next_hops gadag_root.red_next_hops = x.localroot.red_next_hops
gadag_root.order_proxy = x.localroot gadag_root.order_proxy = x.localroot
foreach node y foreach node y
if (y is not gadag_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(gadag_root, max_block_id) Assign_Block_ID(gadag_root, max_block_id)
Compute_MRT_NextHops(x, gadag_root) Compute_MRT_NextHops(x, gadag_root)
Figure 23 Figure 23: Complete Algorithm to Compute MRT Next Hops
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 MRT
MRTs avoids the primary next-hop node F. This computation depends avoids the primary next-hop node F. This computation depends upon
upon data set in Compute_MRT_NextHops such as each node y's 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 or MRT-Red next-hops as the alternate next-hop(s) for the MRT-Blue or MRT-Red next hops as the alternate next hop(s) for
that primary next hop. The algorithm is given in Figure 24 and that primary next hop. The algorithm is given in Figure 24 and
discussed afterwards. discussed afterwards.
Select_Alternates_Internal(D, F, primary_intf, Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order): D_lower, D_higher, D_topo_order):
if D_higher and D_lower if D_higher and D_lower
if F.HIGHER and F.LOWER if F.HIGHER and F.LOWER
if F.topo_order < D_topo_order if F.topo_order < D_topo_order
return USE_RED return USE_RED
else else
skipping to change at page 38, line 18 skipping to change at page 38, line 43
if (D is F) or (D.order_proxy is F) if (D is F) or (D.order_proxy is F)
return PRIM_NH_IS_D_OR_OP_FOR_D return PRIM_NH_IS_D_OR_OP_FOR_D
D_lower = D.order_proxy.LOWER D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf, return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order) D_lower, D_higher, D_topo_order)
Figure 24: Select_Alternates() and Select_Alternates_Internal() Figure 24: Select_Alternates() and Select_Alternates_Internal()
It is useful to first handle the case where where F is also D, or F It is useful to first handle the case where F is also D, or F is the
is the order proxy for D. In this case, only link protection is order proxy for D. In this case, only link protection is possible.
possible. The MRT that doesn't use the failed primary next-hop is The MRT that doesn't use the failed primary next hop is used. If
used. If both MRTs use the primary next-hop, then the primary next- both MRTs use the primary next hop, then the primary next hop must be
hop must be a cut-link, so either MRT could be used but the set of a cut-link, so either MRT could be used but the set of MRT next hops
MRT next-hops must be pruned to avoid the failed primary next-hop must be pruned to avoid the failed primary next-hop interface. To
interface. To indicate this case, Select_Alternates returns indicate this case, Select_Alternates returns
PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudo-code to handle the three PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three
sub-cases above is not provided. sub-cases above is not provided.
The logic behind Select_Alternates_Internal is described in The logic behind Select_Alternates_Internal() is described in
Figure 25. As an example, consider the first case described in the 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 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 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 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 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.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 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, or it is on neither an increasing nor a
decreasing path from S to D. In either case, it is safe to take an 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, 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 the increasing path is the blue path, so it is safe to use the blue
path to avoid F. path to avoid F.
If instead F.topo_order>D.topo_order, then either F is ordered lower If instead F.topo_order<D.topo_order, then either F is ordered lower
than D, or F is unordered with respect to D. Therefore, F is either than D, or F is unordered with respect to D. Therefore, F is either
on an increasing path from S to D, or it is on neither an increasing 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 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 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 is R, the decreasing path is the red path, so it is safe to use the
red path to avoid F. red path to avoid F.
If F>>S or F<<S (but not both), then D is the block root. We then If F>>S or F<<S (but not both), then D is the block root. We then
know that the blue path from S to D is the increasing path to R, and know that the blue path from S to D is the increasing path to R, and
the red path is the decreasing path to R. When F>>S, we deduce that the red path is the decreasing path to R. When F>>S, we deduce that
skipping to change at page 39, line 32 skipping to change at page 40, line 24
| D is | Red path: | | | S to R | | | D is | Red path: | | | S to R | |
| R, | Decreasing +------+-----------------+------------+------------+ | R, | Decreasing +------+-----------------+------------+------------+
| | path to R. | F<<S | additional | F on a | Use Blue | | | path to R. | F<<S | additional | F on a | Use Blue |
| | | only | criteria | decreasing | to avoid | | | | only | criteria | decreasing | to avoid |
| | | | not needed | path from | F | | | | | not needed | path from | F |
| or | | | | S to R | | | or | | | | S to R | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F>>S | topo(F)>topo(D) | F on a | Use Blue | | | | F>>S | topo(F)>topo(D) | F on a | Use Blue |
| S is | Blue path: | and | implies that | decreasing | to avoid | | S is | Blue path: | and | implies that | decreasing | to avoid |
| R | Increasing | F<<S,| F>>D or F??D | path from | F | | R | Increasing | F<<S,| F>>D or F??D | path from | F |
| | path to D. | F is | | S to D or | | | | path to D. | | | S to D or | |
| | Red path: | R | | neither | | | | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+ | | Decreasing | +-----------------+------------+------------+
| | path to D. | | topo(F)<topo(D) | F on an | Use Red | | | path to D. | | topo(F)<topo(D) | F on an | Use Red |
| | | | implies that | increasing | to avoid | | | | | implies that | increasing | to avoid |
| | | | F<<D or F??D | path from | F | | | | | F<<D or F??D | path from | F |
| | | | | S to D or | | | | | | | S to D or | |
| | | | | neither | | | | | | | neither | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F??S | Can only occur | F is on | Use Red | | | | F??S | Can only occur | F is on | Use Red |
| | | | when link | neither | or Blue | | | | | when link | neither | or Blue |
| | | | between | increasing | to avoid | | | | | between | increasing | to avoid |
skipping to change at page 41, line 28 skipping to change at page 43, line 5
| | S to first | | not needed | path from | F | | | S to first | | not needed | path from | F |
| | node K<<D, | | | S to K. | | | | node K<<D, | | | S to K. | |
| | then incr. +------+-----------------+------------+------------+ | | then incr. +------+-----------------+------------+------------+
| | to D. | F>>S | additional | F on an | Use Blue | | | to D. | F>>S | additional | F on an | Use Blue |
| | Red path: | only | criteria | increasing | to avoid | | | Red path: | only | criteria | increasing | to avoid |
| | Incr. from | | not needed | path from | F | | | Incr. from | | not needed | path from | F |
| | S to first | | | S to L | | | | S to first | | | S to L | |
| | node L>>D, | | | | | | | node L>>D, | | | | |
| | then decr. | | | | | | | then decr. | | | | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F??S | F<-->S link is | | | | | | F??S | topo(F)>topo(D) | F on decr. | Use Blue |
| | | | MRT_INELIGIBLE | | |
| | | +-----------------+------------+------------+
| | | | topo(F)>topo(D) | F on decr. | Use Blue |
| | | | implies that | path from | to avoid | | | | | implies that | path from | to avoid |
| | | | F>>D or F??D | L to D or | F | | | | | F>>D or F??D | L to D or | F |
| | | | | neither | | | | | | | neither | |
| | | +-----------------+------------+------------+ | | | +-----------------+------------+------------+
| | | | topo(F)<topo(D) | F on incr. | Use Red | | | | | topo(F)<topo(D) | F on incr. | Use Red |
| | | | implies that | path from | to avoid | | | | | implies that | path from | to avoid |
| | | | F<<D or F??D | K to D or | F | | | | | F<<D or F??D | K to D or | F |
| | | | | neither | | | | | | | neither | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F>>S | GADAG link | F on an | Use Blue | | | | F>>S | GADAG link | F on an | Use Blue |
skipping to change at page 42, line 15 skipping to change at page 43, line 37
| | | | | from F, in which case | | | | | | from F, in which case |
| | | | | Red or Blue avoids F | | | | | | Red or Blue avoids F |
| | | +-----------------+-------------------------+ | | | +-----------------+-------------------------+
| | | | S-F link not | Relies on special | | | | | S-F link not | Relies on special |
| | | | in GADAG, | construction of GADAG | | | | | in GADAG, | construction of GADAG |
| | | | only when | to demonstrate that | | | | | only when | to demonstrate that |
| | | | S-F link is | using Red avoids F | | | | | S-F link is | using Red avoids F |
| | | | MRT_INELIGIBLE | (see text) | | | | | MRT_INELIGIBLE | (see text) |
+------+------------+------+-----------------+-------------------------+ +------+------------+------+-----------------+-------------------------+
Figure 25: determining MRT next-hops and alternates based on the Determining MRT next hops and alternates based on the partial order
partial order and topological sort relationships between the and topological sort relationships between the source(S),
source(S), destination(D), primary next-hop(F), and block root(R). destination(D), primary next hop(F), and block root(R). topo(N)
topo(N) indicates the topological sort value of node N. X??Y indicates the topological sort value of node N. X??Y indicates that
indicates that node X is unordered with respect to node Y. It is node X is unordered with respect to node Y. It is assumed that the
assumed that the case where F is D, or where F is the order proxy for case where F is D, or where F is the order proxy for D, has already
D, has already been handled. been handled.
Figure 25: Determining MRT Next Hops and Alternates
The last case in Figure 25 requires additional explanation. The fact The last case in Figure 25 requires additional explanation. The fact
that the red path from S to D in this case avoids F relies on a that the red path from S to D in this case avoids F relies on a
special property of the GADAGs that we have constructed in this special property of the GADAGs that we have constructed in this
algorithm, a property not shared by all GADAGs in general. When D is algorithm, a property not shared by all GADAGs in general. When D is
unordered with respect to S, and F is the localroot for S, it can unordered with respect to S, and F is the localroot for S, it can
occur that the link between S and F is not in the GADAG only when occur that the link between S and F is not in the GADAG only when
that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S
doesn't have enough information based on the computed order doesn't have enough information based on the computed order
relationships to determine if the red path or blue path will hit F relationships to determine if the red path or blue path will hit F
(which is also the localroot) before hitting K or L, and making it (which is also the localroot) before hitting K or L, and making it
safely to D. However, the GADAGs that we construct using the safely to D. However, the GADAGs that we construct using the
algorithm in this document are not arbitrary GADAGs. They have the algorithm in this document are not arbitrary GADAGs. They have the
additional property that incoming links to a localroot come from only additional property that incoming links to a localroot come from only
one other node in the same block. This is a result of the method of one other node in the same block. This is a result of the method of
construction. This additional property guarantees that the red path construction. This additional property guarantees that the red path
from S to D will never pass through the localroot of S. (That would from S to D will never pass through the localroot of S. (That would
require the localroot to play the role of L, the first node in the require the localroot to play the role of L, the first node in the
path ordered higher than D, which would in turn require the localroot path ordered higher than D, which would in turn require the localroot
to have two incoming links in the GADAG, which cannot happen.) to have two incoming links in the GADAG, which cannot happen.)
Therefore it is safe to use the red path to avoid F with these Therefore, it is safe to use the red path to avoid F with these
specially constructed GADAGs. specially constructed GADAGs.
As an example of how Select_Alternates_Internal() operates, consider As an example of how Select_Alternates_Internal() operates, consider
the ADAG depicted in Figure 26 and first suppose that G is the the ADAG depicted in Figure 26 and first suppose that G is the
source, D is the destination and H is the failed next-hop. Since source, D is the destination, and H is the failed next hop. Since
D>>G, we need to compare H.topo_order and D.topo_order. Since D>>G, we need to compare H.topo_order and D.topo_order. Since
D.topo_order>H.topo_order, D must be either higher than H or D.topo_order>H.topo_order, D must be either higher than H or
unordered with respect to H, so we should select the decreasing path unordered with respect to H, so we should select the decreasing path
towards the root. If, however, the destination were instead J, we towards the root. If, however, the destination were instead J, we
must find that H.topo_order>J.topo_order, so we must choose the must find that 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 increasing Blue 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 the destination is C, we find that we need to first decrease to avoid
using H, so the Blue, first decreasing then increasing, path is using H, so the Blue, first decreasing then increasing, path is
selected. selected.
[E]<-[D]<-[H]<-[J] [E]<-[D]<-[H]<-[J]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[R] [C] [G]->[I] [R] [C] [G]->[I]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[A]->[B]->[F]---| [A]->[B]->[F]---|
(a)ADAG rooted at R for
a 2-connected graph
Figure 26 Figure 26: ADAG Rooted at R for a 2-Connected Graph
5.9. Named Proxy-Nodes 5.9. Named Proxy-Nodes
As discussed in Section 11.2 of As discussed in Section 11.2 of [RFC7812], it is necessary to find
[I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- MRT-Blue and MRT-Red next hops and MRT-FRR alternates for named
Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy- proxy-nodes. An example use case is for a router that is not part of
nodes. An example use case is for a router that is not part of that 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.
5.9.1. Determining Proxy-Node Attachment Routers 5.9.1. Determining Proxy-Node Attachment Routers
Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses Section 11.2 of [RFC7812] discusses general considerations for
general considerations for determining the two proxy-node attachment determining the two proxy-node attachment routers for a given proxy-
routers for a given proxy-node, corresponding to a prefix. A router node, corresponding to a prefix. A router in the MRT Island that
in the MRT Island that advertises the prefix is a candidate for being advertises the prefix is a candidate for being a proxy-node
a proxy-node attachment router, with the associated named-proxy-cost attachment router, with the associated named-proxy-cost equal to the
equal to the advertised cost to the prefix. advertised cost to the prefix.
An Island Border Router (IBR) is a router in the MRT Island that is An Island Border Router (IBR) is a router in the MRT Island that is
connected to an Island Neighbor(IN), which is a router not in the MRT connected to an Island Neighbor (IN), which is a router not in the
Island but in the same area/level. An (IBR,IN) pair is a candidate MRT Island but in the same area/level. An (IBR,IN) pair is a
for being a proxy-node attachment router, if the shortest path from candidate for being a proxy-node attachment router, if the shortest
the IN to the prefix does not enter the MRT Island. A method for path from the IN to the prefix does not enter the MRT Island. A
identifying such loop-free Island Neighbors(LFINs) is given below. method for identifying such Loop-Free Island Neighbors (LFINs) is
The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) given below. The named-proxy-cost assigned to each (IBR, IN) pair is
+ D_opt(IN, prefix). cost(IBR, IN) + D_opt(IN, prefix).
From the set of prefix-advertising routers and the set of IBRs with From the set of prefix-advertising routers and the set of IBRs with
at least one LFIN, the two routers with the lowest named-proxy-cost at least one LFIN, the two routers with the lowest named-proxy-cost
are selected. Ties are broken based upon the lowest Router ID. For are selected. Ties are broken based upon the lowest Router ID. For
ease of discussion, the two selected routers will be referred to as ease of discussion, the two selected routers will be referred to as
proxy-node attachment routers. proxy-node attachment routers.
5.9.2. Computing if an Island Neighbor (IN) is loop-free 5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free
As discussed above, the Island Neighbor needs to be loop-free with As discussed above, the IN needs to be loop-free with respect to the
respect to the whole MRT Island for the destination. This can be whole MRT Island for the destination. This can be accomplished by
accomplished by running the usual SPF algorithm while keeping track running the usual SPF algorithm while keeping track of which shortest
of which shortest paths have passed through the MRT island. Pseudo- paths have passed through the MRT island. Pseudocode for this is
code for this is shown in Figure 27. The Island_Marking_SPF() is run shown in Figure 27. The Island_Marking_SPF() is run for each IN that
for each IN that needs to be evaluated for the loop-free condition, needs to be evaluated for the loop-free condition, with the IN as the
with the IN as the spf_root. Whether or not an IN is loop-free with spf_root. Whether or not an IN is loop-free with respect to the MRT
respect to the MRT island can then be determined by evaluating island can then be determined by evaluating node.PATH_HITS_ISLAND for
node.PATH_HITS_ISLAND for each destination of interest. each destination of interest.
Island_Marking_SPF(spf_root) Island_Marking_SPF(spf_root)
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
and PATH_HITS_ISLAND to false and PATH_HITS_ISLAND to false
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)
foreach interface intf of min_node foreach interface intf of min_node
skipping to change at page 45, line 39 skipping to change at page 46, line 39
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)
if intf.remote_node.IN_MRT_ISLAND if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true intf.remote_node.PATH_HITS_ISLAND = true
else else
intf.remote_node.PATH_HITS_ISLAND = intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND min_node.PATH_HITS_ISLAND
Figure 27: Island_Marking_SPF for determining if an Island Neighbor Figure 27: Island_Marking_SPF() for Determining If an Island Neighbor
is loop-free Is Loop-Free
It is also possible that a given prefix is originated by a It is also possible that a given prefix is originated by a
combination of non-island routers and island routers. The results of combination of non-island routers and island routers. The results of
the Island_Marking_SPF computation can be used to determine if the the Island_Marking_SPF() computation can be used to determine if the
shortest path from an IN to reach that prefix hits the MRT island. shortest path from an IN to reach that prefix hits the MRT Island.
The shortest path for the IN to reach prefix P is determined by the The shortest path for the IN to reach prefix P is determined by the
total cost to reach prefix P, which is the sum of the cost for the IN total cost to reach prefix P, which is the sum of the cost for the IN
to reach a prefix-advertising node and the cost with which that node to reach a prefix-advertising node and the cost with which that node
advertises the prefix. The path with the minimum total cost to advertises the prefix. The path with the minimum total cost to
prefix P is chosen. If the prefix-advertising node for that minimum prefix P is chosen. If the prefix-advertising node for that minimum
total cost path has PATH_HITS_ISLAND set to True, then the IN is not total cost path has PATH_HITS_ISLAND set to True, then the IN is not
loop-free with respect to the MRT Island for reaching prefix P. If loop-free with respect to the MRT Island for reaching prefix P. If
there multiple minimum total cost paths to reach prefix P, then all there are multiple minimum total cost paths to reach prefix P, then
of the prefix-advertising routers involved in the minimum total cost all of the prefix-advertising routers involved in the minimum total
paths MUST have PATH_HITS_ISLAND set to False for the IN to be cost paths MUST have PATH_HITS_ISLAND set to False for the IN to be
considered loop-free to reach P. considered loop-free to reach P.
Note that there are other computations that could be used to Note that there are other computations that could be used to
determine if paths from a given IN _might_ pass through the MRT determine if paths from a given IN _might_ pass through the MRT
Island for a given prefix or destination. For example, a previous Island for a given prefix or destination. For example, a previous
version of this draft specified running the SPF algorithm on modified draft version of this document specified running the SPF algorithm on
topology which treats the MRT island as a single node (with intra- modified topology that treats the MRT Island as a single node (with
island links set to zero cost) in order to provide input to intra-island links set to zero cost) in order to provide input to
computations to determine if the path from IN to non-island computations to determine if the path from IN to non-island
destination hits the MRT island in this modified topology. This destination hits the MRT Island in this modified topology. This
computation is enough to guarantee that a path will not hit the MRT computation is enough to guarantee that a path will not hit the MRT
island in the original topology. However, it is possible that a path Island in the original topology. However, it is possible that a path
which is disqualified for hitting the MRT island in the modified that is disqualified for hitting the MRT Island in the modified
topology will not actually hit the MRT Island in the original topology will not actually hit the MRT Island in the original
topology. The algorithm described in Island_Marking_SPF() above does topology. The algorithm described in Island_Marking_SPF() above does
not modify the original topology, and will only disqualify a path if not modify the original topology, and will only disqualify a path if
the actual path does in fact hit the MRT island. the actual path does in fact hit the MRT Island.
Since all routers need to come to the same conclusion about which Since all routers need to come to the same conclusion about which
routers qualify as LFINs, this specification requires that all routers qualify as LFINs, this specification requires that all
routers computing LFINs MUST use an algorithm whose result is routers computing LFINs MUST use an algorithm whose result is
identical to that of the Island_Marking_SPF() in Figure 27. identical to that of the Island_Marking_SPF() in Figure 27.
5.9.3. Computing MRT Next-Hops for Proxy-Nodes 5.9.3. Computing MRT Next Hops for Proxy-Nodes
Determining the MRT next-hops for a proxy-node in the degenerate case Determining the MRT next hops for a proxy-node in the degenerate case
where the proxy-node is attached to only one node in the GADAG is where the proxy-node is attached to only one node in the GADAG is
trivial, as all needed information can be derived from that proxy trivial, as all needed information can be derived from that proxy-
node attachment router. If there are multiple interfaces connecting node attachment router. If there are multiple interfaces connecting
the proxy node to the single proxy node attachment router, then some the proxy-node to the single proxy-node attachment router, then some
can be assigned to MRT-Red and others to MRT_Blue. can be assigned to MRT-Red and others to MRT_Blue.
Now, consider the proxy-node P that is attached to two proxy-node Now, consider the proxy-node P that is attached to two proxy-node
attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S) attachment routers. The pseudocode for Select_Proxy_Node_NHs(P,S) in
in Figure 28 specifies how a computing-router S MUST compute the MRT Figure 28 specifies how a computing-router S MUST compute the MRT red
red and blue next-hops to reach proxy-node P. The proxy-node and blue next hops to reach proxy-node P. The proxy-node attachment
attachment router with the lower value of mrt_node_id (as defined in router with the lower value of mrt_node_id (as defined in Figure 15)
Figure 15) is assigned to X, and the other proxy-node attachment is assigned to X, and the other proxy-node attachment router is
router is assigned to Y. We will be using the relative order of X,Y, assigned to Y. We will be using the relative order of X,Y, and S in
and S in the partial order defined by the GADAG to determine the MRT the partial order defined by the GADAG to determine the MRT red and
red and blue next-hops to reach P, so we also define A and B as the blue next hops to reach P, so we also define A and B as the order
order proxies for X and Y, respectively, with respect to S. The proxies for X and Y, respectively, with respect to S. The order
order proxies for all nodes with respect to S were already computed proxies for all nodes with respect to S were already computed in
in Compute_MRT_NextHops(). Compute_MRT_NextHops().
def Select_Proxy_Node_NHs(P,S): def Select_Proxy_Node_NHs(P,S):
if P.pnar1.node.node_id < P.pnar2.node.node_id: if P.pnar1.node.node_id < P.pnar2.node.node_id:
X = P.pnar1.node X = P.pnar1.node
Y = P.pnar2.node Y = P.pnar2.node
else: else:
X = P.pnar2.node X = P.pnar2.node
Y = P.pnar1.node Y = P.pnar1.node
P.pnar_X = X P.pnar_X = X
P.pnar_Y = Y P.pnar_Y = Y
skipping to change at page 49, line 43 skipping to change at page 51, line 4
Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return return
else: else:
// case 4.3.3 // case 4.3.3
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
// case 4.3.3.1 // case 4.3.3.1
Copy_List_Items(P.blue_next_hops, X.blue_next_hops) Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return return
else: else:
// case 4.3.3.2 // case 4.3.3.2
Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return return
assert(False) assert(False)
Figure 28: Select_Proxy_Node_NHs() Figure 28: Select_Proxy_Node_NHs()
It is useful to understand up front that the blue next-hops to reach It is useful to understand up front that the blue next hops to reach
proxy-node P produced by Select_Proxy_Node_NHs() will always be the proxy-node P produced by Select_Proxy_Node_NHs() will always be the
next-hops that reach proxy-node attachment router X, while the red next hops that reach proxy-node attachment router X, while the red
next-hops to reach proxy-node P will always be the next-hops that next hops to reach proxy-node P will always be the next hops that
reach proxy-node attachment router Y. This is different from the red reach proxy-node attachment router Y. This is different from the red
and blue next-hops produced by Compute_MRT_NextHops() where, for and blue next hops produced by Compute_MRT_NextHops() where, for
example, blue next-hops to a destination that is ordered with respect example, blue next hops to a destination that is ordered with respect
to the source will always correspond to an INCREASING next-hop on the to the source will always correspond to an INCREASING next hop on the
GADAG. The exact choice of which next-hops chosen by GADAG. The exact choice of which next hops chosen by
Select_Proxy_Node_NHs() as the blue next-hops to reach P (which will Select_Proxy_Node_NHs() as the blue next hops to reach P (which will
necessarily go through X on its way to P) does depend on the GADAG, necessarily go through X on its way to P) does depend on the GADAG,
but the relationship is more complex than was the case with but the relationship is more complex than was the case with
Compute_MRT_NextHops(). Compute_MRT_NextHops().
There are twenty-one different relative order relationships between There are 21 different relative order relationships between A, B, and
A, B and S that Select_Proxy_Node_NHs() uses to determine red and S that Select_Proxy_Node_NHs() uses to determine red and blue next
blue next-hops to P. This document does not attempt to provide an hops to P. This document does not attempt to provide an exhaustive
exhaustive description of each case considered in description of each case considered in Select_Proxy_Node_NHs().
Select_Proxy_Node_NHs(). Instead we provide a high level overview of Instead, we provide a high-level overview of the different cases, and
the different cases, and we consider a few cases in detail to give an we consider a few cases in detail to give an example of the reasoning
example of the reasoning that can be used to understand each case. that can be used to understand each case.
At the highest level, Select_Proxy_Node_NHs() distinguishes between At the highest level, Select_Proxy_Node_NHs() distinguishes between
four different cases depending on whether or not A or B is the four different cases depending on whether or not A or B is the
localroot for S. For example, for case 4.0, neither A nor B is the localroot for S. For example, for case 4.0, neither A nor B is the
localroot for S. Case 4.05 addresses the case where S is the localroot for S. Case 4.05 addresses the case where S is the
localroot for either A or B, while cases 4.1, 4.2, and 4.3 address localroot for either A or B, while cases 4.1, 4.2, and 4.3 address
the cases where A is ordered lower than S, A is ordered higher than the cases where A is ordered lower than S, A is ordered higher than
S, or A is unordered with respect to S on the GADAG. In general, S, or A is unordered with respect to S on the GADAG. In general,
each of these cases is then further subdivided into whether or not B each of these cases is then further subdivided into whether or not B
is ordered lower than S, B is ordered higher than S, or B is is ordered lower than S, B is ordered higher than S, or B is
unordered with respect to S. In some cases we also need a further unordered with respect to S. In some cases, we also need a further
level of discrimination, where we use the topological sort order of A level of discrimination, where we use the topological sort order of A
with respect to B. with respect to B.
As a detailed example, let's consider case 4.1 and all of its sub- As a detailed example, let's consider case 4.1 and all of its sub-
cases, and explain why the red and blue next-hops to reach P are cases, and explain why the red and blue next hops to reach P are
chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither
A nor B is the localroot for S, S is not the localroot for A or B, A nor B is the localroot for S, S is not the localroot for A or B,
and A is ordered lower than S on the GADAG. In this situation, we and A is ordered lower than S on the GADAG. In this situation, we
know that the red path to reach X (as computed in know that the red path to reach X (as computed in
Compute_MRT_NextHops()) will follow DECREASING next-hops towards A, Compute_MRT_NextHops()) will follow DECREASING next hops towards A,
while the blue path to reach X will follow INCREASING next-hops to while the blue path to reach X will follow INCREASING next hops to
the localroot, and then INCREASING next-hops to A. the localroot, and then INCREASING next hops to A.
Now consider sub-case 4.1.1 where B is ordered higher than S. In Now consider sub-case 4.1.1 where B is ordered higher than S. In
this situation, we know that the blue path to reach Y will follow this situation, we know that the blue path to reach Y will follow
INCREASING next-hops towards B, while the red next-hops to reach Y INCREASING next hops towards B, while the red next hops to reach Y
will follow DECREASING next-hops to the localroot, and then will follow DECREASING next hops to the localroot, and then
DECREASING next-hops to B. So to reach X and Y by two disjoint DECREASING next hops to B. So, to reach X and Y by two disjoint
paths, we can choose the red next-hops to X and the blue next-hops to paths, we can choose the red next hops to X and the blue next hops to
Y. We have chosen the convention that blue next-hops to P are those Y. We have chosen the convention that blue next hops to P are those
that pass through X, and red next-hops to P are those that pass that pass through X, and red next hops to P are those that pass
through Y, so we can see that case 4.1.1 produces the desired result. through Y, so we can see that case 4.1.1 produces the desired result.
Choosing blue to X and red to Y does not produce disjoint paths Choosing blue to X and red to Y does not produce disjoint paths
because the paths intersect at least at the localroot. because the paths intersect at least at the localroot.
Now consider sub-case 4.1.2 where B is ordered lower than S. In this Now consider sub-case 4.1.2 where B is ordered lower than S. In this
situation, we know that the red path to reach Y will follow situation, we know that the red path to reach Y will follow
DECREASING next-hops towards B, while the BLUE next-hops to reach Y DECREASING next hops towards B, while the BLUE next hops to reach Y
will follow INCREASING next-hops to the localroot, and then will follow INCREASING next hops to the localroot, and then
INCREASING next-hops to A. The choice here is more difficult than in INCREASING next hops to A. The choice here is more difficult than in
4.1.1 because A and B are both on the DECREASING path from S towards 4.1.1 because A and B are both on the DECREASING path from S towards
the localroot. We want to use the direct DECREASING(red) path to the the localroot. We want to use the direct DECREASING(red) path to the
one that is nearer to S on the GADAG. We get this extra information one that is nearer to S on the GADAG. We get this extra information
by comparing the topological sort order of A and B. If by comparing the topological sort order of A and B. If
A.topo_order<B.topo_order, then we use red to Y and blue to X, since A.topo_order<B.topo_order, then we use red to Y and blue to X, since
the red path to Y will DECREASE to B without hitting A, and the blue the red path to Y will DECREASE to B without hitting A, and the blue
path to X will INCREASE to A without hitting B. Instead, if path to X will INCREASE to A without hitting B. Instead, if
A.topo_order>B.topo_order, then we use red to X and blue to Y. A.topo_order>B.topo_order, then we use red to X and blue to Y.
Note that when A is unordered with respect to B, the result of Note that when A is unordered with respect to B, the result of
comparing A.topo_order with B.topo_order could be greater than or comparing A.topo_order with B.topo_order could be greater than or
less than. In this case, the result doesn't matter because either less than. In this case, the result doesn't matter because either
choice (red to Y and blue to X or red to X and blue to Y) would work. choice (red to Y and blue to X or red to X and blue to Y) would work.
What is required is that all nodes in the network give the same What is required is that all nodes in the network give the same
result when comparing A.topo_order with B.topo_order. This is result when comparing A.topo_order with B.topo_order. This is
guarantee by having all nodes run the same algorithm guaranteed by having all nodes run the same algorithm
(Run_Topological_Sort_GADAG()) to compute the topological sort order. (Run_Topological_Sort_GADAG()) to compute the topological sort order.
Finally we consider case 4.1.3, where B is unordered with respect to Finally, we consider case 4.1.3, where B is unordered with respect to
S. In this case, the blue path to reach Y will follow the DECREASING S. In this case, the blue path to reach Y will follow the DECREASING
next-hops towards the localroot until it reaches some node (K) which next hops towards the localroot until it reaches some node (K) which
is ordered less than B, after which it will take INCREASING next-hops is ordered less than B, after which it will take INCREASING next hops
to B. The red path to reach Y will follow the INCREASING next-hops to B. The red path to reach Y will follow the INCREASING next hops
towards the localroot until it reaches some node (L) which is ordered towards the localroot until it reaches some node (L) which is ordered
greater than B, after which it will take DECREASING next-hops to B. greater than B, after which it will take DECREASING next hops to B.
Both K and A are reached by DECREASING from S, but we don't have Both K and A are reached by DECREASING from S, but we don't have
information about whether or not that DECREASING path will hit K or A information about whether or not that DECREASING path will hit K or A
first. Instead, we do know that the INCREASING path from S will hit first. Instead, we do know that the INCREASING path from S will hit
L before reaching A. Therefore, we use the red path to reach Y and L before reaching A. Therefore, we use the red path to reach Y and
the red path to reach X. the red path to reach X.
Similar reasoning can be applied to understand the other seventeen Similar reasoning can be applied to understand the other 17 cases
cases used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3 deserve
deserve special attention because the correctness of the solution for special attention because the correctness of the solution for these
these two cases relies on a special property of the GADAGs that we two cases relies on a special property of the GADAGs that we have
have constructed in this algorithm, a property not shared by all constructed in this algorithm, a property not shared by all GADAGs in
GADAGs in general. Focusing on case 2.3, we consider the case where general. Focusing on case 2.3, we consider the case where A is the
A is the localroot for S, while B is not, and B is unordered with localroot for S, while B is not, and B is unordered with respect to
respect to S. The red path to X DECREASES from S to the localroot A, S. The red path to X DECREASES from S to the localroot A, while the
while the blue path to X INCREASES from S to the localroot A. The blue path to X INCREASES from S to the localroot A. The blue path to
blue path to Y DECREASES towards the localroot A until it reaches Y DECREASES towards the localroot A until it reaches some node (K)
some node (K) which is ordered less than B, after which the path which is ordered less than B, after which the path INCREASES to B.
INCREASES to B. The red path to Y INCREASES towards the localroot A The red path to Y INCREASES towards the localroot A until it reaches
until it reaches some node (L) which is ordered greater than B, after some node (L) which is ordered greater than B, after which the path
which the path DECREASES to B. It can be shown that for an arbitrary DECREASES to B. It can be shown that for an arbitrary GADAG, with
GADAG, with only the ordering relationships computed so far, we don't only the ordering relationships computed so far, we don't have enough
have enough information to choose a pair of paths to reach X and Y information to choose a pair of paths to reach X and Y that are
that are guaranteed to be disjoint. In some topologies, A will play guaranteed to be disjoint. In some topologies, A will play the role
the role of K, the first node ordered less than B on the blue path to of K, the first node ordered less than B on the blue path to Y. In
Y. In other topologies, A will play the role of L, the first node other topologies, A will play the role of L, the first node ordered
ordered greater than B on the red path to Y. The basic problem is greater than B on the red path to Y. The basic problem is that we
that we cannot distinguish between these two cases based on the cannot distinguish between these two cases based on the ordering
ordering relationships. relationships.
As discussed Section 5.8, the GADAGs that we construct using the As discussed Section 5.8, the GADAGs that we construct using the
algorithm in this document are not arbitrary GADAGs. They have the algorithm in this document are not arbitrary GADAGs. They have the
additional property that incoming links to a localroot come from only additional property that incoming links to a localroot come from only
one other node in the same block. This is a result of the method of one other node in the same block. This is a result of the method of
construction. This additional property guarantees that localroot A construction. This additional property guarantees that localroot A
will never play the role of L in the red path to Y, since L must have will never play the role of L in the red path to Y, since L must have
at least two incoming links from different nodes in the same block in at least two incoming links from different nodes in the same block in
the GADAG. This in turn allows Select_Proxy_Node_NHs() to choose the the GADAG. This, in turn, allows Select_Proxy_Node_NHs() to choose
red path to Y and the red path to X as the disjoint MRT paths to the red path to Y and the red path to X as the disjoint MRT paths to
reach P. reach P.
5.9.4. Computing MRT Alternates for Proxy-Nodes 5.9.4. Computing MRT Alternates for Proxy-Nodes
After finding the red and the blue next-hops for a given proxy-node After finding the red and the blue next hops for a given proxy-node
P, it is necessary to know which one of these to use in the case of P, it is necessary to know which one of these to use in the case of
failure. This can be done by Select_Alternates_Proxy_Node(), as failure. This can be done by Select_Alternates_Proxy_Node(), as
shown in the pseudo-code in Figure 29. shown in the pseudocode in Figure 29.
def Select_Alternates_Proxy_Node(P,F,primary_intf): def Select_Alternates_Proxy_Node(P,F,primary_intf):
S = primary_intf.local_node S = primary_intf.local_node
X = P.pnar_X X = P.pnar_X
Y = P.pnar_Y Y = P.pnar_Y
A = X.order_proxy A = X.order_proxy
B = Y.order_proxy B = Y.order_proxy
if F is A and F is B: if F is A and F is B:
return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y' return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'
if F is A: if F is A:
skipping to change at page 58, line 21 skipping to change at page 59, line 34
Select_Alternates(Y,F,primary_intf) to determine which of the two MRT Select_Alternates(Y,F,primary_intf) to determine which of the two MRT
paths to X and which of the two MRT paths to Y is safe to use in the paths to X and which of the two MRT paths to Y is safe to use in the
event of the failure of F. In general, we will find that if it is event of the failure of F. In general, we will find that if it is
safe to use a particular path to X or Y when F fails, and safe to use a particular path to X or Y when F fails, and
Select_Proxy_Node_NHs() used that path when constructing the red or Select_Proxy_Node_NHs() used that path when constructing the red or
blue path to reach P, then it will also be safe to use that path to blue path to reach P, then it will also be safe to use that path to
reach P when F fails. This rule has one exception which is covered reach P when F fails. This rule has one exception which is covered
below. First, we give a concrete example of how below. First, we give a concrete example of how
Select_Alternates_Proxy_Node() works in the common case. Select_Alternates_Proxy_Node() works in the common case.
The twenty one ordering relationships used in Select_Proxy_Node_NHs() The 21 ordering relationships used in Select_Proxy_Node_NHs() are
are repeated in Select_Alternates_Proxy_Node(). We focus on case repeated in Select_Alternates_Proxy_Node(). We focus on case 4.1.1
4.1.1 to give give a detailed example of the reasoning used in to give a detailed example of the reasoning used in
Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we
determined for case 4.1.1 that the red next-hops to X and the blue determined for case 4.1.1 that the red next hops to X and the blue
next-hops to Y allow us to reach X and Y by disjoint paths, and are next hops to Y allow us to reach X and Y by disjoint paths, and are
thus the blue and red next-hops to reach P. Therefore, if we run thus the blue and red next hops to reach P. Therefore, if
Select_Alternates(X, F, primary_intf) and we find that it is safe to Select_Alternates(X, F, primary_intf) is run and we find that it is
USE_RED to reach X, then we also conclude that it is safe to use the safe to USE_RED to reach X, then we also conclude that it is safe to
MRT path through X to reach P (the blue path to P) when F fails. use the MRT path through X to reach P (the blue path to P) when F
Similarly, if run Select_Alternates(X, F, primary_intf) and we find fails. Similarly, if we run Select_Alternates(Y, F, primary_intf)
that it is safe to USE_BLUE to reach Y, then we also conclude that it and we find that it is safe to USE_BLUE to reach Y, then we also
is safe to use the MRT path through Y to reach P (the red path to P) conclude that it is safe to use the MRT path through Y to reach P
when F fails. If both of the paths that were used in (the red path to P) when F fails. If both of the paths that were
Select_Proxy_Node_NHs() to construct the blue and red paths to P are used in Select_Proxy_Node_NHs() to construct the blue and red paths
found to be safe to use to use to reach X and Y, t then we conclude to P are found to be safe to use to use to reach X and Y, t then we
that we can use either the red or the blue path to P. conclude that we can use either the red or the blue path to P.
This simple reasoning gives the correct answer in most of the cases. This simple reasoning gives the correct answer in most of the cases.
However, additional logic is needed when either A or B (but not both However, additional logic is needed when either A or B (but not both
A and B) is unordered with respect to S. This applies to cases A and B) is unordered with respect to S. This applies to cases
4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more 4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more
detail, A is ordered less than S, but B is unordered with respect to detail, A is ordered less than S, but B is unordered with respect to
S. In the discussion of case 4.1.3 above, we saw that S. In the discussion of case 4.1.3 above, we saw that
Select_Proxy_Node_NHs() chose the red path to reach Y and the red Select_Proxy_Node_NHs() chose the red path to reach Y and the red
path to reach X. We also saw that the red path to reach Y will path to reach X. We also saw that the red path to reach Y will
follow the INCREASING next-hops towards the localroot until it follow the INCREASING next hops towards the localroot until it
reaches some node (L) which is ordered greater than B, after which it reaches some node (L) which is ordered greater than B, after which it
will take DECREASING next-hops to B. The problem is that the red will take DECREASING next hops to B. The problem is that the red
path to reach P (the one that goes through Y) won't necessarily be path to reach P (the one that goes through Y) won't necessarily be
the same as the red path to reach Y. This is because the next-hop the same as the red path to reach Y. This is because the next hop
that node L computes for its red next-hop to reach P may be different that node L computes for its red next hop to reach P may be different
from the next-hop it computes for its red next-hop to reach Y. This from the next hop it computes for its red next hop to reach Y. This
is because B is ordered lower than L, so L applies case 4.1.2 of is because B is ordered lower than L, so L applies case 4.1.2 of
Select_Proxy_Node_NHs() in order to determine its next-hops to reach Select_Proxy_Node_NHs() in order to determine its next hops to reach
P. If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose P. If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose
DECREASING next-hops directly to B, which is the same result that L DECREASING next hops directly to B, which is the same result that L
computes in Compute_MRT_NextHops() to reach Y. However, if computes in Compute_MRT_NextHops() to reach Y. However, if
A.topo_order>B.topo_order (case 4.1.2.2), then L will choose A.topo_order>B.topo_order (case 4.1.2.2), then L will choose
INCREASING next-hops to reach B, which is different from what L INCREASING next hops to reach B, which is different from what L
computes in Compute_MRT_NextHops() to reach Y. So testing the safety computes in Compute_MRT_NextHops() to reach Y. So, testing the
of the path for S to reach Y on failure of F as a surrogate for the safety of the path for S to reach Y on failure of F as a surrogate
safety of using the red path to reach P is not reliable in this case. for the safety of using the red path to reach P is not reliable in
It is possible construct topologies where the red path to P hits F this case. It is possible construct topologies where the red path to
even though the red path to Y does not hit F. P hits F even though the red path to Y does not hit F.
Fortunately there is enough information in the order relationships Fortunately, there is enough information in the order relationships
that we have already computed to still figure out which alternate to that we have already computed to still figure out which alternate to
choose in these four cases. The basic idea is to always choose the choose in these four cases. The basic idea is to always choose the
path involving the ordered node, unless that path would hit F. path involving the ordered node, unless that path would hit F.
Returning to case 4.1.3, we see that since A is ordered lower than S, Returning to case 4.1.3, we see that since A is ordered lower than S,
the only way for S to hit F using a simple DECREASING path to A is the only way for S to hit F using a simple DECREASING path to A is
for F to lie between A and S on the GADAG. This scenario is covered for F to lie between A and S on the GADAG. This scenario is covered
by requiring that F be lower than S (but not also higher than S) and by requiring that F be lower than S (but not also higher than S) and
that F.topo_order>A.topo_order in case 4.1.3.1. that F.topo_order>A.topo_order in case 4.1.3.1.
We just need to confirm that it is safe to use the path involving B We just need to confirm that it is safe to use the path involving B
in this scenario. In case 4.1.3.1, either F is between A and S on in this scenario. In case 4.1.3.1, either F is between A and S on
the GADAG, or F is unordered with respect to A and lies on the the GADAG, or F is unordered with respect to A and lies on the
DECREASING path from S to the localroot. When F is between A and S DECREASING path from S to the localroot. When F is between A and S
on the GADAG, then the path through B chosen to avoid A in on the GADAG, then the path through B chosen to avoid A in
Select_Proxy_Node_NHs() will also avoid F. When F is unordered with Select_Proxy_Node_NHs() will also avoid F. When F is unordered with
respect to A and lies on the DECREASING path from S to the localroot, respect to A and lies on the DECREASING path from S to the localroot,
then we consider two cases. Either F.topo_order<B.topo_order or then we consider two cases. Either F.topo_order<B.topo_order or
F.topo_order>B.topo_order. In the first case, since F.topo_order>B.topo_order. In the first case, since
F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be
the case that A.topo_order<B.topo_order. Therefore, L will choose the case that A.topo_order<B.topo_order. Therefore, L will choose
DECREASING next-hops directly to B (case 4.1.2.1), which cannot hit F DECREASING next hops directly to B (case 4.1.2.1), which cannot hit F
since F.topo_order<B.topo_order. In the second case, where since F.topo_order<B.topo_order. In the second case, where
F.topo_order>B.topo_order, the only way for the path involving B to F.topo_order>B.topo_order, the only way for the path involving B to
hit F is if it DECREASES from L to B through F , ie. it must be that hit F is if it DECREASES from L to B through F, i.e., it must be that
L>>F>>B. However, since S>>F, this would imply that S>>B. However, L>>F>>B. However, since S>>F, this would imply that S>>B. However,
we know that S is unordered with respect to B, so the second case we know that S is unordered with respect to B, so the second case
cannot occur. So we have demonstrated that the red path to P (which cannot occur. So we have demonstrated that the red path to P (which
goes via B and Y) is safe to use under the conditions of 4.1.3.1. goes via B and Y) is safe to use under the conditions of 4.1.3.1.
Similar reasoning can be applied to the other three special cases Similar reasoning can be applied to the other three special cases
where either A or B is unordered with respect to S. where either A or B is unordered with respect to S.
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 includes
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.
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. Broadcast interfaces 7. Broadcast Interfaces
When broadcast interfaces are used to connect nodes, the broadcast When broadcast interfaces are used to connect nodes, the broadcast
network MUST be represented as a pseudonode, where each real node network MUST be represented as a pseudonode, where each real node
connects to the pseudonode. The interface metric in the direction connects to the pseudonode. The interface metric in the direction
from real node to pseudonode is the non-zero interface metric, while from real node to pseudonode is the non-zero interface metric, while
the interface metric in the direction from the pseudonode to the real the interface metric in the direction from the pseudonode to the real
node is set to zero. This is consistent with the way that broadcast node is set to zero. This is consistent with the way that broadcast
interfaces are represented as pseudonodes in IS-IS and OSPF. interfaces are represented as pseudonodes in IS-IS and OSPF.
Pseudonodes MUST be treated as equivalent to real nodes in the Pseudonodes MUST be treated as equivalent to real nodes in the
network graph used in the MRT algorithm with a few exceptions network graph used in the MRT Lowpoint algorithm with a few
detailed below. exceptions detailed below.
The pseudonodes MUST be included in the computation of the GADAG. The pseudonodes MUST be included in the computation of the GADAG.
The neighbors of the pseudonode need to know the mrt_node_id of the The neighbors of the pseudonode need to know the mrt_node_id of the
pseudonode in order to consistently order interfaces, which is needed pseudonode in order to consistently order interfaces, which is needed
to compute the GADAG. The mrt_node_id for IS-IS is the 7 octet to compute the GADAG. The mrt_node_id for IS-IS is the 7-octet
neighbor system ID and pseudonode number in TLV #22 or TLV#222. The neighbor system ID and pseudonode number in TLV 22 or TLV 222. The
mrt_node_id for OSPFv2 is the 4 octet interface address of the mrt_node_id for OSPFv2 is the 4-octet interface address of the
Designated Router found in the Link ID field for the link type 2 Designated Router found in the Link ID field for the link type 2
(transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is (transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is
the 4 octet interface address of the Designated Router found in the the 4 octet interface address of the Designated Router found in the
Neighbor Interface ID field for the link type 2 (transit network) in Neighbor Interface ID field for the link type 2 (transit network) in
the Router-LSA. pseudonodes MUST NOT be considered as candidates for the Router-LSA. Note that this is different from the Neighbor Router
GADAG root selection. Note that this is different from the Neighbor ID field used for the mrt_node_id for point-to-point links in OSPFv3
Router ID field used for the mrt_node_id for point-to-point links in Router-LSAs given in Figure 15.
OSPFv3 Router-LSAs given in Figure 15.
Pseudonodes MUST NOT be considered as candidates for selection as Pseudonodes MUST NOT be considered candidates for selection as GADAG
GADAG root. This rule is intended to result in a more stable root. This rule is intended to result in a more stable network-wide
network- wide selection of GADAG root by removing the possibility selection of GADAG root by removing the possibility that the change
that the change of Designated Router or Designated Intermediate of Designated Router or Designated Intermediate System on a broadcast
System on a broadcast network can result in a change of GADAG root. network can result in a change of GADAG root.
7.1. Computing MRT next-hops on broadcast networks 7.1. Computing MRT Next Hops on Broadcast Networks
The pseudonode does not correspond to an real node, so it is not The pseudonode does not correspond to a real node, so it is not
actually involved in forwarding. A real node on a broadcast network actually involved in forwarding. A real node on a broadcast network
cannot simply forward traffic to the broadcast network. It must cannot simply forward traffic to the broadcast network. It must
specify another real node on the broadcast network as the next-hop. specify another real node on the broadcast network as the next hop.
On a network graph where a broadcast network is represented by a On a network graph where a broadcast network is represented by a
pseudonode, this means that if a real node determines that the next- pseudonode, this means that if a real node determines that the next
hop to reach a given destination is a pseudonode, it must also hop to reach a given destination is a pseudonode, it must also
determine the next-next-hop for that destination in the network determine the next-next-hop for that destination in the network
graph, which corresponds to a real node attached to the broadcast graph, which corresponds to a real node attached to the broadcast
network. network.
It is interesting to note that this issue is not unique to the MRT It is interesting to note that this issue is not unique to the MRT
algorithm, but is also encountered in normal SPF computations for algorithm, but is also encountered in normal SPF computations for
IGPs. Section 16.1.1 of [RFC2328] describes how this is done for IGPs. Section 16.1.1 of [RFC2328] describes how this is done for
OSPF. As OSPF runs Dijkstra's algorithm, whenever a shorter path is OSPF. When OSPF runs its shortest-path tree calculation, it deals
found reach a real destination node, and the shorter path is one hop with pseudonodes in the following manner. Whenever the calculating
from the computing routing, and that one hop is a pseudonode, then router finds a shorter path to reach a real destination node and the
the next-hop for that destination is taken from the interface IP shorter path to the destination is a single pseudonode hop, then the
address in the Router-LSA correspond to the link to the real next hop for that destination is taken from the interface IP address
destination node in the Router-LSA correspond to the link to the real destination
node.
For IS-IS, in the example pseudo-code implementation of Dijkstra's For IS-IS, in the example pseudocode implementation of Dijkstra's
algorithm in Annex C of [ISO10589-Second-Edition] whenever the algorithm in Annex C of [ISO10589-Second-Edition], whenever the
algorithm encounters an adjacency from a real node to a pseudonode, algorithm encounters an adjacency from a real node to a pseudonode,
it gets converted to a set of adjacencies from the real node to the it gets converted to a set of adjacencies from the real node to the
neighbors of the pseudonode. In this way, the computed next-hops neighbors of the pseudonode. In this way, the computed next hops
point all the way to the real node, and not the pseudonode. point all the way to the real node, and not the pseudonode.
We could avoid the problem of determining next-hops across We could avoid the problem of determining next hops across
pseudonodes in MRT by converting the pseudonode representation of pseudonodes in MRT by converting the pseudonode representation of
broadcast networks to a full mesh of links between real nodes on the broadcast networks to a full mesh of links between real nodes on the
same network. However, if we make that conversion before computing same network. However, if we make that conversion before computing
the GADAG, we lose information about which links actually correspond the GADAG, we lose information about which links actually correspond
to a single physical interface into the broadcast network. This to a single physical interface into the broadcast network. This
could result computing red and blue next-hops that use the same could result computing red and blue next hops that use the same
broadcast interface, in which case neither the red nor the blue next- broadcast interface, in which case neither the red nor the blue next
hop would be usable as an alternate on failure of the broadcast hop would be usable as an alternate on failure of the broadcast
interface. interface.
Instead, we take the following approach, which maintains the property Instead, we take the following approach, which maintains the property
that either the red and blue next-hop will avoid the broadcast that either the red and blue next hop will avoid the broadcast
network, if topologically allowed. We run the MRT algorithm treating network, if topologically allowed. We run the MRT Lowpoint algorithm
the pseudonodes as equivalent to real nodes in the network graph, treating the pseudonodes as equivalent to real nodes in the network
with the exceptions noted above. In addition to running the MRT graph, with the exceptions noted above. In addition to running the
algorithm from the point of view of itself, a computing router MRT Lowpoint algorithm from the point of view of itself, a computing
connected to a pseudonode MUST also run the MRT algorithm from the router connected to a pseudonode MUST also run the MRT Lowpoint
point of view of each of its pseudonode neighbors. For example, if a algorithm from the point of view of each of its pseudonode neighbors.
computing router S determines that its MRT red next-hop to reach a For example, if a computing router S determines that its MRT red next
destination D is a pseudonode P, S looks at its MRT algorithm hop to reach a destination D is a pseudonode P, S looks at its MRT
computation from P's point of view to determine P's red next-hop to Lowpoint algorithm computation from P's point of view to determine
reach D, say interface 1 on node X. S now knows that its real red P's red next hop to reach D, say interface 1 on node X. S now knows
next-hop to reach D is interface 1 on node X on the broadcast network that its real red next hop to reach D is interface 1 on node X on the
represented by P, and can install the corresponding entry in its FIB. broadcast network represented by P, and it can install the
corresponding entry in its FIB.
7.2. Using MRT next-hops as alternates in the event of failures on 7.2. Using MRT Next Hops as Alternates in the Event of Failures on
broadcast networks Broadcast Networks
In the previous section, we specified how to compute MRT next-hops In the previous section, we specified how to compute MRT next hops
when broadcast networks are involved. In this section, we discuss when broadcast networks are involved. In this section, we discuss
how a PLR can use those MRT next-hops in the event of failures how a PLR can use those MRT next hops in the event of failures
involving broadcast networks. involving broadcast networks.
A PLR attached to a broadcast network running only OSPF or IS-IS with A PLR attached to a broadcast network running only OSPF or IS-IS with
large Hello intervals has limited ability to quickly detect failures large Hello intervals has limited ability to quickly detect failures
on a broadcast network. The only failure mode that can be quickly on a broadcast network. The only failure mode that can be quickly
detected is the failure of the physical interface connecting the PLR detected is the failure of the physical interface connecting the PLR
to the broadcast network. For the failure of the interface to the broadcast network. For the failure of the interface
connecting the PLR to the broadcast network, the alternate that connecting the PLR to the broadcast network, the alternate that
avoids the broadcast network can be computed by using the broadcast avoids the broadcast network can be computed by using the broadcast
network pseudonode as F, the primary next-hop node, in network pseudonode as F, the primary next-hop node, in
skipping to change at page 63, line 4 skipping to change at page 64, line 16
broadcast network. This is the best that we can hope to do if broadcast network. This is the best that we can hope to do if
failure of the broadcast interface is the only failure mode that the failure of the broadcast interface is the only failure mode that the
PLR can respond to. PLR can respond to.
We can improve on this if the PLR also has the ability to quickly We can improve on this if the PLR also has the ability to quickly
detect a lack of connectivity across the broadcast network to a given detect a lack of connectivity across the broadcast network to a given
IP-layer node. This can be accomplished by running BFD between all IP-layer node. This can be accomplished by running BFD between all
pairs of IGP neighbors on the broadcast network. Note that in the pairs of IGP neighbors on the broadcast network. Note that in the
case of OSPF, this would require establishing BFD sessions between case of OSPF, this would require establishing BFD sessions between
all pairs of neighbors in the 2-WAY state. When the PLR can quickly all pairs of neighbors in the 2-WAY state. When the PLR can quickly
detect the failure of a particular next-hop across a broadcast detect the failure of a particular next hop across a broadcast
network, then the PLR can be more selective in its choice of network, the PLR can be more selective in its choice of alternates.
alternates. For example, when the PLR observes that connectivity to For example, when the PLR observes that connectivity to an IP-layer
an IP-layer node on a broadcast network has failed, the PLR may node on a broadcast network has failed, the PLR may choose to still
choose to still use the broadcast network to reach other IP-layer use the broadcast network to reach other IP-layer nodes that are
nodes which are still reachable. Or if the PLR observes that still reachable. Or, if the PLR observes that connectivity has
connectivity has failed to several IP-layer nodes on the same failed to several IP-layer nodes on the same broadcast network, it
broadcast network, it may choose to treat the entire broadcast may choose to treat the entire broadcast network as failed. The
network as failed. The choice of MRT alternates by a PLR for a choice of MRT alternates by a PLR for a particular set of failure
particular set of failure conditions is a local decision, since it conditions is a local decision, since it does not require
does not require coordination with other nodes. coordination with other nodes.
8. Evaluation of Alternative Methods for Constructing GADAGs 8. Evaluation of Alternative Methods for Constructing GADAGs
This document specifies the MRT Lowpoint algorithm. One component of This document specifies the MRT Lowpoint algorithm. One component of
the algorithm involves constructing a common GADAG based on the the algorithm involves constructing a common GADAG based on the
network topology. The MRT Lowpoint algorithm computes the GADAG network topology. The MRT Lowpoint algorithm computes the GADAG
using the method described in Section 5.5. This method aims to using the method described in Section 5.5. This method aims to
minimize the amount of computation required to compute the GADAG. In minimize the amount of computation required to compute the GADAG. In
the process of developing the MRT Lowpoint algorithm, two alternative the process of developing the MRT Lowpoint algorithm, two alternative
methods for constructing GADAGs were also considered. These methods for constructing GADAGs were also considered. These
alternative methods are described in Appendix B and Appendix C. In alternative methods are described in Appendices B and C. In general,
general, these other two methods require more computation to compute these other two methods require more computation to compute the
the GADAG. The analysis below was performed to determine if the GADAG. The analysis below was performed to determine if the
alternative GADAG construction methods produce shorter MRT alternate alternative GADAG construction methods produce shorter MRT alternate
paths in real network topologies, and if so, to what extent. paths in real network topologies, and if so, to what extent.
Figure 30 compares results obtained using the three different methods Figure 30 compares results obtained using the three different methods
for constructing GADAGs on five different service provider network for constructing GADAGs on five different service provider network
topologies. MRT_LOWPOINT indicates the method specified in topologies. MRT_LOWPOINT indicates the method specified in
Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods Section 5.5, while MRT_SPF and MRT_HYBRID indicate the methods
specified in Appendix B and Appendix C, respectively. The columns on specified in Appendices B and C, respectively. The columns on the
the right present the distribution of alternate path lengths for each right present the distribution of alternate path lengths for each
GADAG construction method. Each MRT computation was performed using GADAG construction method. Each MRT computation was performed using
a same GADAG root chosen based on centrality. a same GADAG root chosen based on centrality.
For three of the topologies analyzed (T201, T206, and T211), the use For three of the topologies analyzed (T201, T206, and T211), the use
of MRT_SPF or MRT_HYBRID methods does not appear to provide a of MRT_SPF or MRT_HYBRID methods does not appear to provide a
significantly shorter alternate path lengths compared to the significantly shorter alternate path lengths compared to the
MRT_LOWPOINT method. However, for two of the topologies (T216 and MRT_LOWPOINT method. However, for two of the topologies (T216 and
T219), the use of the MRT_SPF method resulted in noticeably shorter T219), the use of the MRT_SPF method resulted in noticeably shorter
alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID alternate path lengths than the use of the MRT_LOWPOINT or MRT_HYBRID
methods. methods.
It was decided to use the MRT_LOWPOINT method to construct the GADAG It was decided to use the MRT_LOWPOINT method to construct the GADAG
in the algorithm specified in this draft, in order to initially offer in the algorithm specified in this document, in order to initially
an algorithm with lower computational requirements. These results offer an algorithm with lower computational requirements. These
indicate that in the future it may be useful to evaluate and results indicate that in the future it may be useful to evaluate and
potentially specify other MRT algorithm variants that use different potentially specify other MRT Lowpoint algorithm variants that use
GADAG construction methods. different GADAG construction methods.
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| Topology name | percentage of failure scenarios | | Topology name | percentage of failure scenarios |
| | protected by an alternate N hops | | | protected by an alternate N hops |
| GADAG construction | longer than the primary path | | GADAG construction | longer than the primary path |
| method +------------------------------------+ | method +------------------------------------+
| | | | | | | | | | no | | | | | | | | | | | 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 64, line 42 skipping to change at page 66, line 40
| MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2| | MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2|
| MRT_SPF | 35| 32| 19| 9| 3| 1| | | | | MRT_SPF | 35| 32| 19| 9| 3| 1| | | |
| MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1| | MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T219(avg primary hops=7.7) | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | |
| MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3| | MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3|
| MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| | | MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| |
| MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10| | MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 30 Figure 30: The Length of Alternate Paths for Various GADAG
Construction Methods
9. Implementation Status
[RFC Editor: please remove this section prior to publication.]
Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on
implementation status.
10. Operational Considerations 9. Operational Considerations
This sections discusses operational considerations related to the the This section discusses operational considerations related to the MRT
MRT Lowpoint algorithm and other potential MRT algorithm variants. Lowpoint algorithm and other potential MRT algorithm variants. For a
For a discussion of operational considerations related to MRT-FRR in discussion of operational considerations related to MRT-FRR in
general, see the Operational Considerations section of general, see the "Operational Considerations" section of [RFC7812].
[I-D.ietf-rtgwg-mrt-frr-architecture].
10.1. GADAG Root Selection 9.1. GADAG Root Selection
The Default MRT Profile uses the GADAG Root Selection Priority The Default MRT Profile uses the GADAG Root Selection Priority
advertised by routers as the primary criterion for selecting the advertised by routers as the primary criterion for selecting the
GADAG root. It is RECOMMENDED that an operator designate a set of GADAG root. It is RECOMMENDED that an operator designate a set of
routers as good choices for selection as GADAG root by setting the routers as good choices for selection as GADAG root by setting the
GADAG Root Selection Priority for that set of routers to lower (more GADAG Root Selection Priority for that set of routers to lower (more
preferred) numerical values. Criteria for making this designation preferred) numerical values. Criteria for making this designation
are discussed below. are discussed below.
Analysis has shown that the centrality of a router can have a Analysis has shown that the centrality of a router can have a
significant impact on the lengths of the alternate paths computed. significant impact on the lengths of the alternate paths computed.
Therefore, it is RECOMMENDED that off-line analysis that considers Therefore, it is RECOMMENDED that off-line analysis that considers
the centrality of a router be used to help determine how good a the centrality of a router be used to help determine how good a
choice a particular router is for the role of GADAG root. choice a particular router is for the role of GADAG root.
If the router currently selected as GADAG root becomes unreachable in If the router currently selected as GADAG root becomes unreachable in
the IGP topology, then a new GADAG root will be selected. Changing the IGP topology, then a new GADAG root will be selected. Changing
the GADAG root can change the overall structure of the GADAG as well the GADAG root can change the overall structure of the GADAG as well
the paths of the red and blue MRT trees built using that GADAG. In the paths of the red and MRT-Blue trees built using that GADAG. In
order to minimize change in the associated red and blue MRT order to minimize change in the associated red and MRT-Blue
forwarding entries that can result from changing the GADAG root, it forwarding entries that can result from changing the GADAG root, it
is RECOMMENDED that operators prioritize for selection as GADAG root is RECOMMENDED that operators prioritize for selection as GADAG root
those routers that are expected to consistently remain part of the those routers that are expected to consistently remain part of the
IGP topology. IGP topology.
10.2. Destination-rooted GADAGs 9.2. Destination-Rooted GADAGs
The MRT Lowpoint algorithm constructs a single GADAG rooted at a The MRT Lowpoint algorithm constructs a single GADAG rooted at a
single node selected as the GADAG root. It is also possible to single node selected as the GADAG root. It is also possible to
construct a different GADAG for each destination, with the GADAG construct a different GADAG for each destination, with the GADAG
rooted at the destination. A router can compute the MRT-Red and MRT- rooted at the destination. A router can compute the MRT-Red and MRT-
Blue next-hops for that destination based on the GADAG rooted at that Blue next hops for that destination based on the GADAG rooted at that
destination. Building a different GADAG for each destination is destination. Building a different GADAG for each destination is
computationally more expensive, but it may give somewhat shorter computationally more expensive, but it may give somewhat shorter
alternate paths. Using destination-rooted GADAGs would require a new alternate paths. Using destination-rooted GADAGs would require a new
MRT profile to be created with a new MRT algorithm specification, MRT profile to be created with a new MRT algorithm specification,
since all routers in the MRT Island would need to use destination- since all routers in the MRT Island would need to use destination-
rooted GADAGs. rooted GADAGs.
11. Acknowledgements 10. Security Considerations
The authors would like to thank Shraddha Hegde, Eric Wu, Janos
Farkas, Stewart Bryant, and Alvaro Retana for their suggestions and
review. We would also like to thank Anil Kumar SN for his assistance
in clarifying the algorithm description and pseudo-code.
12. IANA Considerations
This document includes no request to IANA.
13. Security Considerations
The algorithm described in this document does not introduce new The algorithm described in this document does not introduce new
security concerns beyond those already discussed in the document security concerns beyond those already discussed in the document
describing the MRT FRR architecture describing the MRT FRR architecture [RFC7812].
[I-D.ietf-rtgwg-mrt-frr-architecture].
14. References
14.1. Normative References 11. References
[I-D.ietf-rtgwg-mrt-frr-architecture] 11.1. Normative References
Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., and R. White, "An Architecture for IP/
LDP Fast-Reroute Using Maximally Redundant Trees", draft-
ietf-rtgwg-mrt-frr-architecture-07 (work in progress),
October 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
14.2. Informative References [RFC7812] Atlas, A., Bowers, C., and G. Enyedi, "An Architecture for
IP/LDP Fast Reroute Using Maximally Redundant Trees
(MRT-FRR)", RFC 7812, DOI 10.17487/RFC7812, June 2016,
<http://www.rfc-editor.org/info/rfc7812>.
11.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,
s/phd/Villamosmernoki_es_Informatikai_Kar/2011/ <https://repozitorium.omikk.bme.hu/bitstream/
Enyedi_Gabor/ertekezes.pdf>. handle/10890/1040/ertekezes.pdf>.
[IEEE8021Qca] [IEEE8021Qca]
IEEE 802.1, "IEEE 802.1Qca Bridges and Bridged Networks - IEEE, "IEEE Standard for Local and metropolitan area
Amendment: Path Control and Reservation - Draft 2.1", networks - Bridges and Bridged Networks - Amendment 24:
(work in progress), June 24, 2015, Path Control and Reservation", IEEE 802.1Qca-2015,
<http://www.ieee802.org/1/pages/802.1ca.html>. DOI 10.1109/IEEESTD.2016.7434544, 2016,
<https://standards.ieee.org/findstds/
standard/802.1Qca-2015.html>.
[ISO10589-Second-Edition] [ISO10589-Second-Edition]
International Organization for Standardization, International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain "Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in routeing information exchange protocol for use in
conjunction with the protocol for providing the conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)", ISO/ connectionless-mode Network Service (ISO 8473)", ISO/
IEC 10589:2002, Second Edition, Nov. 2002. IEC 10589:2002, Second Edition, November 2002.
[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 DOI
10.1145/368996.369025, November 1962,
<http://dl.acm.org/citation.cfm?doid=368996.369025>. <http://dl.acm.org/citation.cfm?doid=368996.369025>.
[MRTLinear] [MRTLinear]
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE Maximally Redundant Trees in Strictly Linear Time", IEEE
Symposium on Computers and Comunications (ISCC) , 2009, Symposium on Computers and Communications (ISCC), 2009,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/ <http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>. distMaxRedTree.pdf>.
[RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
DOI 10.17487/RFC2328, April 1998, DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2328>. <http://www.rfc-editor.org/info/rfc2328>.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120,
DOI 10.17487/RFC5120, February 2008,
<http://www.rfc-editor.org/info/rfc5120>.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>.
Appendix A. Python Implementation of MRT Lowpoint Algorithm Appendix A. Python Implementation of MRT Lowpoint Algorithm
Below is Python code implementing the MRT Lowpoint algorithm Below is Python code implementing the MRT Lowpoint algorithm
specified in this document. In order to avoid the page breaks in the specified in this document. The code is also posted on GitHub
.txt version of the draft, one can cut and paste the Python code from <https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-
the .xml version. The code is also posted on Github. algorithm/blob/python_code_RFC7811/src/mrt_lowpoint_draft_text.py>.
While this Python code is believed to correctly implement the pseudo- While this Python code is believed to correctly implement the
code description of the algorithm, in the event of a difference, the pseudocode description of the algorithm, in the event of a
pseudo-code description should be considered normative. difference, the pseudocode description should be considered
normative.
<CODE BEGINS> <CODE BEGINS>
# This program has been tested to run on Python 2.6 and 2.7 # 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). # (specifically Python 2.6.6 and 2.7.8 were tested).
# The program has known incompatibilities with Python 3.X. # The program has known incompatibilities with Python 3.X.
# When executed, this program will generate a text file describing # When executed, this program will generate a text file describing
# an example topology. It then reads that text file back in as input # an example topology. It then reads that text file back in as input
# to create the example topology, and runs the MRT algorithm.This # to create the example topology, and runs the MRT Lowpoint algorithm.
# was done to simplify the inclusion of the program as a single text # This was done to simplify the inclusion of the program as a single
# file that can be extracted from the IETF draft. # text file that can be extracted from the RFC.
# The output of the program is four text files containing a description # 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 # of the GADAG, the blue and MRT-Reds for all destinations, and the
# MRT alternates for all failures. # MRT alternates for all failures.
import random import random
import os.path import os.path
import heapq import heapq
# simple Class definitions allow structure-like dot notation for # simple Class definitions allow structure-like dot notation for
# variables and a convenient place to initialize those variables. # variables and a convenient place to initialize those variables.
class Topology: class Topology:
def __init__(self): def __init__(self):
skipping to change at page 72, line 27 skipping to change at page 74, line 36
nodeb_intf.remote_node = nodea nodeb_intf.remote_node = nodea
nodea_intf.local_node = nodea nodea_intf.local_node = nodea
nodeb_intf.local_node = nodeb nodeb_intf.local_node = nodeb
nodea_intf.link_data = len(nodea.intf_list) nodea_intf.link_data = len(nodea.intf_list)
nodeb_intf.link_data = len(nodeb.intf_list) nodeb_intf.link_data = len(nodeb.intf_list)
nodea.intf_list.append(nodea_intf) nodea.intf_list.append(nodea_intf)
nodeb.intf_list.append(nodeb_intf) nodeb.intf_list.append(nodeb_intf)
return topo return topo
def MRT_Island_Identification(topo, computing_rtr, profile_id, area): def MRT_Island_Identification(topo, computing_rtr, profile_id, area):
if profile_id in computing_rtr.profile_id_list: if profile_id in computing_rtr.profile_id_list:
computing_rtr.IN_MRT_ISLAND = True computing_rtr.IN_MRT_ISLAND = True
explore_list = [computing_rtr] explore_list = [computing_rtr]
else: else:
return return
while explore_list != []: while explore_list != []:
next_rtr = explore_list.pop() next_rtr = explore_list.pop()
for intf in next_rtr.intf_list: for intf in next_rtr.intf_list:
if ( (not intf.MRT_INELIGIBLE) if ( (not intf.IN_MRT_ISLAND)
and (not intf.remote_intf.MRT_INELIGIBLE) and (not intf.MRT_INELIGIBLE)
and (not intf.IGP_EXCLUDED) and intf.area == area and (not intf.remote_intf.MRT_INELIGIBLE)
and (profile_id in intf.remote_node.profile_id_list)): and (not intf.IGP_EXCLUDED) and intf.area == area
and (profile_id in intf.remote_node.profile_id_list)):
intf.IN_MRT_ISLAND = True intf.IN_MRT_ISLAND = True
intf.remote_intf.IN_MRT_ISLAND = True intf.remote_intf.IN_MRT_ISLAND = True
if (not intf.remote_node.IN_MRT_ISLAND): if (not intf.remote_node.IN_MRT_ISLAND):
intf.remote_node.IN_MRT_ISLAND = True
intf.remote_INTF.IN_MRT_ISLAND = True
explore_list.append(intf.remote_node) explore_list.append(intf.remote_node)
def Compute_Island_Node_List_For_Test_GR(topo, test_gr): def Compute_Island_Node_List_For_Test_GR(topo, test_gr):
Reset_Computed_Node_and_Intf_Values(topo) Reset_Computed_Node_and_Intf_Values(topo)
topo.test_gr = topo.node_dict[test_gr] topo.test_gr = topo.node_dict[test_gr]
MRT_Island_Identification(topo, topo.test_gr, 0, 0) MRT_Island_Identification(topo, topo.test_gr, 0, 0)
for node in topo.node_list: for node in topo.node_list:
if node.IN_MRT_ISLAND: if node.IN_MRT_ISLAND:
topo.island_node_list_for_test_gr.append(node) topo.island_node_list_for_test_gr.append(node)
skipping to change at page 78, line 42 skipping to change at page 81, line 5
Copy_List_Items(y.red_next_hops, y.next_hops) Copy_List_Items(y.red_next_hops, y.next_hops)
if direction == 'NORMAL_SPF': if direction == 'NORMAL_SPF':
y.primary_spf_metric = y.spf_metric y.primary_spf_metric = y.spf_metric
Copy_List_Items(y.primary_next_hops, y.next_hops) Copy_List_Items(y.primary_next_hops, y.next_hops)
if direction == 'MRT_ISLAND_SPF': if direction == 'MRT_ISLAND_SPF':
Copy_List_Items(y.mrt_island_next_hops, y.next_hops) Copy_List_Items(y.mrt_island_next_hops, y.next_hops)
if direction == 'COLLAPSED_SPF': if direction == 'COLLAPSED_SPF':
y.collapsed_metric = y.spf_metric y.collapsed_metric = y.spf_metric
Copy_List_Items(y.collapsed_next_hops, y.next_hops) Copy_List_Items(y.collapsed_next_hops, y.next_hops)
# Note that the Python heapq fucntion allows for duplicate items, # Note that the Python heapq function allows for duplicate items,
# so we use the 'spf_visited' property to only consider a node # so we use the 'spf_visited' property to only consider a node
# as min_node the first time it gets removed from the heap. # as min_node the first time it gets removed from the heap.
def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction):
spf_heap = [] spf_heap = []
for y in topo.island_node_list: for y in topo.island_node_list:
y.spf_metric = 2147483647 # 2^31-1 y.spf_metric = 2147483647 # 2^31-1
y.next_hops = [] y.next_hops = []
y.spf_visited = False y.spf_visited = False
spf_root.spf_metric = 0 spf_root.spf_metric = 0
heapq.heappush(spf_heap, heapq.heappush(spf_heap,
skipping to change at page 81, line 14 skipping to change at page 83, line 25
x.localroot.red_next_hops) x.localroot.red_next_hops)
elif y.LOWER == True: elif y.LOWER == True:
Copy_List_Items(y.blue_next_hops, Copy_List_Items(y.blue_next_hops,
x.localroot.blue_next_hops) x.localroot.blue_next_hops)
else: else:
Copy_List_Items(y.blue_next_hops, Copy_List_Items(y.blue_next_hops,
x.localroot.red_next_hops) x.localroot.red_next_hops)
Copy_List_Items(y.red_next_hops, Copy_List_Items(y.red_next_hops,
x.localroot.blue_next_hops) x.localroot.blue_next_hops)
# Inherit x's MRT next-hops to reach the GADAG root # Inherit x's MRT next hops to reach the GADAG root
# from x's MRT next-hops to reach its local root, # from x's MRT next hops to reach its local root,
# but first check if x is the gadag_root (in which case # 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 # x does not have a local root) or if x's local root
# is the gadag root (in which case we already have the # is the gadag root (in which case we already have the
# x's MRT next-hops to reach the gadag root) # 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: if x is not topo.gadag_root and x.localroot is not topo.gadag_root:
Copy_List_Items(topo.gadag_root.blue_next_hops, Copy_List_Items(topo.gadag_root.blue_next_hops,
x.localroot.blue_next_hops) x.localroot.blue_next_hops)
Copy_List_Items(topo.gadag_root.red_next_hops, Copy_List_Items(topo.gadag_root.red_next_hops,
x.localroot.red_next_hops) x.localroot.red_next_hops)
topo.gadag_root.order_proxy = x.localroot topo.gadag_root.order_proxy = x.localroot
# Inherit next-hops and order_proxies to other blocks # Inherit next hops and order_proxies to other blocks
for y in topo.island_node_list: for y in topo.island_node_list:
if (y is not topo.gadag_root and y is not x ): if (y is not topo.gadag_root and y is not x ):
Set_Edge(y) Set_Edge(y)
def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list: for y in topo.island_node_list:
if y is x: if y is x:
continue continue
x.blue_next_hops_dict[y.node_id] = [] x.blue_next_hops_dict[y.node_id] = []
x.red_next_hops_dict[y.node_id] = [] x.red_next_hops_dict[y.node_id] = []
skipping to change at page 84, line 40 skipping to change at page 87, line 4
continue continue
for failed_intf in D.primary_next_hops: for failed_intf in D.primary_next_hops:
alt = Alternate() alt = Alternate()
alt.failed_intf = failed_intf alt.failed_intf = failed_intf
cand_alt_list = [] cand_alt_list = []
F = failed_intf.remote_node F = failed_intf.remote_node
#We need to test if F is in the island, as opposed #We need to test if F is in the island, as opposed
#to just testing if failed_intf is in island_intf_list, #to just testing if failed_intf is in island_intf_list,
#because failed_intf could be marked as MRT_INELIGIBLE. #because failed_intf could be marked as MRT_INELIGIBLE.
if F in topo.island_node_list: if F in topo.island_node_list:
alt.info = Select_Alternates(D, F, failed_intf) alt.info = Select_Alternates(D, F, failed_intf)
else: else:
#The primary next-hop is not in the MRT Island. #The primary next hop is not in the MRT Island.
#Either red or blue will avoid the primary next-hop, #Either red or blue will avoid the primary next hop,
#because the primary next-hop is not even in the #because the primary next hop is not even in the
#GADAG. #GADAG.
alt.info = 'USE_RED_OR_BLUE' alt.info = 'USE_RED_OR_BLUE'
if (alt.info == 'USE_RED_OR_BLUE'): if (alt.info == 'USE_RED_OR_BLUE'):
alt.red_or_blue = random.choice(['USE_RED','USE_BLUE']) alt.red_or_blue = random.choice(['USE_RED','USE_BLUE'])
if (alt.info == 'USE_BLUE' if (alt.info == 'USE_BLUE'
or alt.red_or_blue == 'USE_BLUE'): or alt.red_or_blue == 'USE_BLUE'):
Copy_List_Items(alt.nh_list, D.blue_next_hops) Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE' alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION' alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'): if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'):
Copy_List_Items(alt.nh_list, D.red_next_hops) Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED' alt.fec = 'RED'
alt.prot = 'NODE_PROTECTION' alt.prot = 'NODE_PROTECTION'
if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'): if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'):
alt.fec = 'NO_ALTERNATE' alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION' alt.prot = 'NO_PROTECTION'
skipping to change at page 96, line 31 skipping to change at page 98, line 46
Copy_List_Items(P.blue_next_hops, X.red_next_hops) Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops) Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return return
assert(False) assert(False)
def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S): def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S):
for prefix in topo.named_proxy_dict: for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix] P = topo.named_proxy_dict[prefix]
if P.pnar2 == None: if P.pnar2 == None:
if S is P.pnar1.node: if S is P.pnar1.node:
# set the MRT next-hops for the PNAR to # set the MRT next hops for the PNAR to
# reach the LFIN and change FEC to green # reach the LFIN and change FEC to green
Copy_List_Items(P.blue_next_hops, Copy_List_Items(P.blue_next_hops,
P.pnar1.nh_intf_list) P.pnar1.nh_intf_list)
S.blue_to_green_nh_dict[P.node_id] = True S.blue_to_green_nh_dict[P.node_id] = True
Copy_List_Items(P.red_next_hops, Copy_List_Items(P.red_next_hops,
P.pnar1.nh_intf_list) P.pnar1.nh_intf_list)
S.red_to_green_nh_dict[P.node_id] = True S.red_to_green_nh_dict[P.node_id] = True
else: else:
# inherit MRT NHs for P from pnar1 # inherit MRT NHs for P from pnar1
Copy_List_Items(P.blue_next_hops, Copy_List_Items(P.blue_next_hops,
P.pnar1.node.blue_next_hops) P.pnar1.node.blue_next_hops)
Copy_List_Items(P.red_next_hops, Copy_List_Items(P.red_next_hops,
P.pnar1.node.red_next_hops) P.pnar1.node.red_next_hops)
else: else:
Select_Proxy_Node_NHs(P,S) Select_Proxy_Node_NHs(P,S)
# set the MRT next-hops for the PNAR to reach the LFIN # set the MRT next hops for the PNAR to reach the LFIN
# and change FEC to green rely on the red or blue # and change FEC to green rely on the red or blue
# next-hops being empty to figure out which one needs # next hops being empty to figure out which one needs
# to point to the LFIN. # to point to the LFIN.
if S is P.pnar1.node: if S is P.pnar1.node:
this_pnar = P.pnar1 this_pnar = P.pnar1
elif S is P.pnar2.node: elif S is P.pnar2.node:
this_pnar = P.pnar2 this_pnar = P.pnar2
else: else:
continue continue
if P.blue_next_hops == []: if P.blue_next_hops == []:
Copy_List_Items(P.blue_next_hops, Copy_List_Items(P.blue_next_hops,
this_pnar.nh_intf_list) this_pnar.nh_intf_list)
S.blue_to_green_nh_dict[P.node_id] = True S.blue_to_green_nh_dict[P.node_id] = True
if P.red_next_hops == []: if P.red_next_hops == []:
skipping to change at page 104, line 4 skipping to change at page 106, line 20
(intf.remote_node is (intf.remote_node is
failed_intf.remote_node)): failed_intf.remote_node)):
if intf.metric < min_metric: if intf.metric < min_metric:
cand_alt_list = [intf] cand_alt_list = [intf]
min_metric = intf.metric min_metric = intf.metric
elif intf.metric == min_metric: elif intf.metric == min_metric:
cand_alt_list.append(intf) cand_alt_list.append(intf)
if cand_alt_list != [None]: if cand_alt_list != [None]:
alt.fec = 'GREEN' alt.fec = 'GREEN'
alt.prot = 'PARALLEL_CUTLINK' alt.prot = 'PARALLEL_CUTLINK'
else: else:
alt.fec = 'NO_ALTERNATE' alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION' alt.prot = 'NO_PROTECTION'
Copy_List_Items(alt.nh_list, cand_alt_list) Copy_List_Items(alt.nh_list, cand_alt_list)
else: else:
# set Z as the node to inherit blue next-hops from # set Z as the node to inherit blue next hops from
if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D': if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D':
Z = P.pnar1.node Z = P.pnar1.node
else: else:
Z = P Z = P
if failed_intf in Z.red_next_hops: if failed_intf in Z.red_next_hops:
Copy_List_Items(alt.nh_list, Z.blue_next_hops) Copy_List_Items(alt.nh_list, Z.blue_next_hops)
alt.fec = 'BLUE' alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION' alt.prot = 'LINK_PROTECTION'
else: else:
assert(failed_intf in Z.blue_next_hops) assert(failed_intf in Z.blue_next_hops)
skipping to change at page 108, line 20 skipping to change at page 110, line 40
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root) Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_MRT_for_All_Sources(topo) Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base) Write_Output_To_Files(topo, res_file_base)
Generate_Basic_Topology_and_Run_MRT() Generate_Basic_Topology_and_Run_MRT()
Generate_Complex_Topology_and_Run_MRT() Generate_Complex_Topology_and_Run_MRT()
<CODE ENDS> <CODE ENDS>
Appendix B. Constructing a GADAG using SPFs Appendix B. Constructing a GADAG Using SPFs
The basic idea in this method for constructing a GADAG is to use The basic idea in this method for constructing a GADAG is to use
slightly-modified SPF computations to find ears. In every block, an slightly modified SPF computations to find ears. In every block, an
SPF computation is first done to find a cycle from the local root and SPF computation is first done to find a cycle from the local root and
then SPF computations in that block find ears until there are no more then SPF computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops is the path of interfaces indicated by following the previous hops
from the mininized IN_GADAG node back to the SPF root. from the minimized IN_GADAG node back to the SPF root.
To do this, first all cut-vertices must be identified and local-roots To do this, first all cut-vertices must be identified and localroots
assigned as specified in Figure 12. assigned as specified in Figure 12.
The slight modifications to the SPF are as follows. The root of the The slight modifications to the SPF are as follows. The root of the
block is referred to as the block-root; it is either the GADAG root block is referred to as the block-root; it is either the GADAG root
or a cut-vertex. or a cut-vertex.
a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All
links between y and x are marked as TEMP_UNUSABLE. They should links between y and x are marked as TEMP_UNUSABLE. They should
not be used during the SPF computation. not be used during the SPF computation.
b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It b. If y is not the block-root, then it is marked TEMP_UNUSABLE. It
should not be used during the SPF computation. This prevents should not be used during the SPF computation. This prevents
ears from starting and ending at the same node and avoids cycles; ears from starting and ending at the same node and avoids cycles;
the exception is because cycles to/from the block-root are the exception is because cycles to/from the block-root are
acceptable and expected. acceptable and expected.
c. Do not explore links to nodes whose local-root is not the block- c. Do not explore links to nodes whose localroot is not the block-
root. This keeps the SPF confined to the particular block. root. This keeps the SPF confined to the particular block.
d. Terminate when the first IN_GADAG node z is minimized. d. Terminate when the first IN_GADAG node z is minimized.
e. Respect the existing directions (e.g. INCOMING, OUTGOING, e. Respect the existing directions (e.g., INCOMING, OUTGOING,
UNDIRECTED) already specified for each interface. UNDIRECTED) already specified for each interface.
Mod_SPF(spf_root, block_root) Mod_SPF(spf_root, block_root)
Initialize spf_heap to empty Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity Initialize nodes' spf_metric to infinity
spf_root.spf_metric = 0 spf_root.spf_metric = 0
insert(spf_heap, spf_root) insert(spf_heap, spf_root)
found_in_gadag = false found_in_gadag = false
while (spf_heap is not empty) and (found_in_gadag is false) while (spf_heap is not empty) and (found_in_gadag is false)
min_node = remove_lowest(spf_heap) min_node = remove_lowest(spf_heap)
skipping to change at page 110, line 4 skipping to change at page 112, line 23
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 31: Modified SPF for GADAG construction Figure 31: Modified SPF for GADAG Construction
Assume that an ear is found by going from y to x and then running an Assume that an ear is found by going from y to x and then running an
SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is SPF that terminates by minimizing z (e.g., y<->x...q<->z). Now it is
necessary to determine the direction of the ear; if y << z, then the necessary to determine the direction of the ear; if y<<z, then the
path should be y->x...q->z but if y >> z, then the path should be y<- path should be y->x...q->z; but if y>>z, then the path should be
x...q<-z. In Section 5.5, the same problem was handled by finding y<-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 GADAG construction nodes higher in the partial order. In this GADAG construction
method, using that approach could mean that new ears aren't added in method, using that approach could mean that new ears aren't added in
order of their total cost since all ears connected to a node would order of their total cost since all ears connected to a node would
need to be found before additional nodes could be found. need to be found before additional nodes could be found.
The alternative is to track the order relationship of each node with The alternative is to track the order relationship of each node with
respect to every other node. This can be accomplished by maintaining respect to every other node. This can be accomplished by maintaining
two sets of nodes at each node. The first set, Higher_Nodes, two sets of nodes at each node. The first set, Higher_Nodes,
contains all nodes that are known to be ordered above the node. The contains all nodes that are known to be ordered above the node. The
skipping to change at page 111, line 48 skipping to change at page 113, line 48
add i.local_node to x.Higher_Nodes add i.local_node to x.Higher_Nodes
else else
foreach node x where x.localroot is block_root foreach node x where x.localroot is block_root
if end_b is in x.Lower_Nodes if end_b is in x.Lower_Nodes
foreach interface i in ear_list foreach interface i in ear_list
add i.local_node to x.Lower_Nodes add i.local_node to x.Lower_Nodes
if end_a is in x.Higher_Nodes if end_a is in x.Higher_Nodes
foreach interface i in ear_list foreach interface i in ear_list
add i.remote_node to x.Higher_Nodes add i.remote_node to x.Higher_Nodes
Figure 32: Algorithm to assign links of an ear direction Figure 32: Algorithm to Assign Links of an Ear Direction
A goal of this GADAG construction method is to find the shortest A goal of this GADAG construction method is to find the shortest
cycles and ears. An ear is started by going to a neighbor x of an cycles and ears. An 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, IN_GADAG node y. The path from x to an IN_GADAG node is minimal,
since it is computed via SPF. Since a shortest path is made of since it is computed via SPF. Since a shortest path is made of
shortest paths, to find the shortest ears requires reaching from the shortest paths, to find the shortest ears requires reaching from the
set of IN_GADAG nodes to the closest node that isn't IN_GADAG. set of IN_GADAG nodes to the closest node that isn't IN_GADAG.
Therefore, an ordered tree is maintained of interfaces that could be Therefore, an ordered tree is maintained of interfaces that could be
explored from the IN_GADAG nodes. The interfaces are ordered by explored from the IN_GADAG nodes. The interfaces are ordered by
their characteristics of metric, local loopback address, remote their characteristics of metric, local loopback address, remote
loopback address, and ifindex, based on the Interface_Compare loopback address, and ifindex, based on the Interface_Compare
function defined in Figure 14. function defined in Figure 14.
This GADAG construction method ignores interfaces picked from the This GADAG construction method ignores interfaces picked from the
ordered list that belong to the block root if the block in which the ordered list that belong to the block root if the block in which the
interface is present already has an ear that has been computed. This interface is present already has an ear that has been computed. This
is necessary since we allow at most one incoming interface to a block is necessary since we allow at most one incoming interface to a block
root in each block. This requirement stems from the way next-hops root in each block. This requirement stems from the way next hops
are computed as was seen in Section 5.7. After any ear gets are computed as was seen in Section 5.7. After any ear gets
computed, we traverse the newly added nodes to the GADAG and insert computed, we traverse the newly added nodes to the GADAG and insert
interfaces whose far end is not yet on the GADAG to the ordered tree interfaces whose far end is not yet on the GADAG to the ordered tree
for later processing. 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 two 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)
skipping to change at page 113, line 32 skipping to change at page 115, line 32
ear_end = SPF_for_Ear(cand_intf.local_node, ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.remote_node, cand_intf.remote_node,
cand_intf.remote_node.localroot, cand_intf.remote_node.localroot,
SPF method) SPF method)
y = ear_end.spf_prev_hop y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node( add_eligible_interfaces_of_node(
ordered_intfs_tree, y.local_node) ordered_intfs_tree, y.local_node)
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
Figure 33: SPF-based method for GADAG construction Figure 33: SPF-Based Method for GADAG Construction
Appendix C. Constructing a GADAG using a hybrid method Appendix C. Constructing a GADAG Using a Hybrid Method
The idea of this method is to combine the salient features of the The idea of this method is to combine the salient features of the
lowpoint inheritance and SPF methods. To this end, we process nodes lowpoint inheritance and SPF methods. To this end, we process nodes
as they get added to the GADAG just like in the lowpoint inheritance as they get added to the GADAG just like in the lowpoint inheritance
by maintaining a stack of nodes. This ensures that we do not need to by maintaining a stack of nodes. This ensures that we do not need to
maintain lower and higher sets at each node to ascertain ear maintain lower and higher sets at each node to ascertain ear
directions since the ears will always be directed from the node being directions since the ears will always be directed from the node being
processed towards the end of the ear. To compute the ear however, we processed towards the end of the ear. To compute the ear however, we
resort to an SPF to have the possibility of better ears (path resort to an SPF to have the possibility of better ears (path
lentghs) thus giving more flexibility than the restricted use of lengths) thus giving more flexibility than the restricted use of
lowpoint/dfs parents. lowpoint/dfs parents.
Regarding ears involving a block root, unlike the SPF method which Regarding ears involving a block root, unlike the SPF method, which
ignored interfaces of the block root after the first ear, in the ignored interfaces of the block root after the first ear, in the
hybrid method we would have to process all interfaces of the block hybrid method we would have to process all interfaces of the block
root before moving on to other nodes in the block since the direction root before moving on to other nodes in the block since the direction
of an ear is pre-determined. Thus, whenever the block already has an of an ear is predetermined. 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 34 The entire algorithm is shown below in Figure 34.
find_spf_stack_ear(stack, x, y, xy_intf, block_root) find_spf_stack_ear(stack, x, y, xy_intf, block_root)
if L(y) == D(y) if L(y) == D(y)
// Special case for cut-links // Special case for cut-links
xy_intf.UNDIRECTED = false xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true xy_intf.OUTGOING = true
xy_intf.INCOMING = true xy_intf.INCOMING = true
xy_intf.remote_intf.OUTGOING = true xy_intf.remote_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true xy_intf.remote_intf.INCOMING = true
skipping to change at page 115, line 16 skipping to change at page 117, line 18
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 34: Hybrid GADAG construction method Figure 34: Hybrid GADAG Construction Method
Acknowledgements
The authors would like to thank Shraddha Hegde, Eric Wu, Janos
Farkas, Stewart Bryant, Alvaro Retana, and Deccan (Shaofu Peng) for
their suggestions and review. We would also like to thank Anil Kumar
SN for his assistance in clarifying the algorithm description and
pseudocode.
Authors' Addresses Authors' Addresses
Gabor Sandor Enyedi Gabor Sandor Enyedi
Ericsson Ericsson
Konyves Kalman krt 11 Konyves Kalman krt 11
Budapest 1097 Budapest 1097
Hungary Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com Email: Gabor.Sandor.Enyedi@ericsson.com
skipping to change at page 115, line 40 skipping to change at page 118, line 27
Konyves Kalman krt 11 Konyves Kalman krt 11
Budapest 1097 Budapest 1097
Hungary Hungary
Email: Andras.Csaszar@ericsson.com Email: Andras.Csaszar@ericsson.com
Alia Atlas Alia Atlas
Juniper Networks Juniper Networks
10 Technology Park Drive 10 Technology Park Drive
Westford, MA 01886 Westford, MA 01886
USA United States
Email: akatlas@juniper.net Email: akatlas@juniper.net
Chris Bowers Chris Bowers
Juniper Networks Juniper Networks
1194 N. Mathilda Ave. 1194 N. Mathilda Ave.
Sunnyvale, CA 94089 Sunnyvale, CA 94089
USA United States
Email: cbowers@juniper.net Email: cbowers@juniper.net
Abishek Gopalan Abishek Gopalan
University of Arizona University of Arizona
1230 E Speedway Blvd. 1230 E Speedway Blvd.
Tucson, AZ 85721 Tucson, AZ 85721
USA United States
Email: abishek@ece.arizona.edu Email: abishek@ece.arizona.edu
 End of changes. 343 change blocks. 
860 lines changed or deleted 840 lines changed or added

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