draft-ietf-rtgwg-mrt-frr-algorithm-06.txt   draft-ietf-rtgwg-mrt-frr-algorithm-07.txt 
Routing Area Working Group G. Enyedi, Ed. Routing Area Working Group G. Enyedi
Internet-Draft A. Csaszar Internet-Draft A. Csaszar
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: April 17, 2016 A. Atlas, Ed. Expires: June 23, 2016 A. Atlas
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
October 15, 2015 December 21, 2015
Algorithms for computing Maximally Redundant Trees for IP/LDP Fast- Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-
Reroute Reroute
draft-ietf-rtgwg-mrt-frr-algorithm-06 draft-ietf-rtgwg-mrt-frr-algorithm-07
Abstract Abstract
A complete solution for IP and LDP Fast-Reroute using Maximally A solution for IP and LDP Fast-Reroute using Maximally Redundant
Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This
architecture]. This document defines the associated MRT Lowpoint document defines the associated MRT Lowpoint algorithm that is used
algorithm that is used in the default MRT profile to compute both the in the default MRT profile to compute both the necessary Maximally
necessary Maximally Redundant Trees with their associated next-hops Redundant Trees with their associated next-hops and the alternates to
and the alternates to select for MRT-FRR. select for MRT-FRR.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 17, 2016. This Internet-Draft will expire on June 23, 2016.
Copyright Notice Copyright Notice
Copyright (c) 2015 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 41 skipping to change at page 2, line 41
5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30
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 . . . . . . . . . . . . . . . . . 30 the computing node . . . . . . . . . . . . . . . . . 30
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 . . . . . . . . . . . . . . . . 31 to the computing node . . . . . . . . . . . . . . . . 31
5.7.3. Computing Redundant Tree next-hops in a 2-connected 5.7.3. Computing Redundant Tree next-hops in a 2-connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 32 Graph . . . . . . . . . . . . . . . . . . . . . . . . 32
5.7.4. Generalizing for a graph that isn't 2-connected . . . 34 5.7.4. Generalizing for a graph that isn't 2-connected . . . 34
5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35 5.7.5. Complete Algorithm to Compute MRT Next-Hops . . . . . 35
5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37 5.8. Identify MRT alternates . . . . . . . . . . . . . . . . . 37
5.9. Finding MRT Next-Hops for Proxy-Nodes . . . . . . . . . . 44 5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 58 5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 44
7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 58 5.9.2. Computing if an Island Neighbor (IN) is loop-free . . 45
7.1. Computing MRT next-hops on broadcast networks . . . . . . 59 5.9.3. Computing MRT Next-Hops for Proxy-Nodes . . . . . . . 47
5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 61
7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 61
7.1. Computing MRT next-hops on broadcast networks . . . . . . 62
7.2. Using MRT next-hops as alternates in the event of 7.2. Using MRT next-hops as alternates in the event of
failures on broadcast networks . . . . . . . . . . . . . 60 failures on broadcast networks . . . . . . . . . . . . . 63
8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 61 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 64
9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 102 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 104
9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 102 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 105
10. Implementation Status . . . . . . . . . . . . . . . . . . . . 112 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 115
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 112 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 115
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 112 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 115
13. Security Considerations . . . . . . . . . . . . . . . . . . . 112 13. Security Considerations . . . . . . . . . . . . . . . . . . . 115
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 112 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 115
14.1. Normative References . . . . . . . . . . . . . . . . . . 112 14.1. Normative References . . . . . . . . . . . . . . . . . . 115
14.2. Informative References . . . . . . . . . . . . . . . . . 112 14.2. Informative References . . . . . . . . . . . . . . . . . 115
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 115 Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 117
Appendix B. Option 3: Computing GADAG using a hybrid method . . 120 Appendix B. Option 3: Computing GADAG using a hybrid method . . 122
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 122 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 124
1. Introduction 1. Introduction
MRT Fast-Reroute requires that packets can be forwarded not only on MRT Fast-Reroute requires that packets can be forwarded not only on
the shortest-path tree, but also on two Maximally Redundant Trees the shortest-path tree, but also on two Maximally Redundant Trees
(MRTs), referred to as the MRT-Blue and the MRT-Red. A router which (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which
experiences a local failure must also have pre-determined which experiences a local failure must also have pre-determined which
alternate to use. This document defines how to compute these three alternate to use. This document defines how to compute these three
things for use in MRT-FRR and describes the algorithm design things for use in MRT-FRR and describes the algorithm design
decisions and rationale. The algorithm is based on those presented decisions and rationale. The algorithm is based on those presented
skipping to change at page 3, line 47 skipping to change at page 3, line 51
Red for forwarding received traffic on the MRT-Red. Red for forwarding received traffic on the MRT-Red.
What alternate next-hops a point-of-local-repair (PLR) selects need What alternate next-hops a point-of-local-repair (PLR) selects need
not be consistent - but loops must be prevented. To reduce not be consistent - but loops must be prevented. To reduce
congestion, it is possible for multiple alternate next-hops to be congestion, it is possible for multiple alternate next-hops to be
selected; in the context of MRT alternates, each of those alternate selected; in the context of MRT alternates, each of those alternate
next-hops would be equal-cost paths. next-hops would be equal-cost paths.
This document defines an algorithm for selecting an appropriate MRT This document defines an algorithm for selecting an appropriate MRT
alternate for consideration. Other alternates, e.g. LFAs that are alternate for consideration. Other alternates, e.g. LFAs that are
downstream paths, may be prefered when available and that policy- downstream paths, may be preferred when available and that policy-
based alternate selection process[I-D.ietf-rtgwg-lfa-manageability] based alternate selection process [I-D.ietf-rtgwg-lfa-manageability]
is not captured in this document. is not captured in this document.
[E]---[D]---| [E]<--[D]<--| [E]-->[D] [E]---[D]---| [E]<--[D]<--| [E]-->[D]
| | | | ^ | | | | | | ^ | |
| | | V | | V | | | V | | V
[R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C] [R] [F] [C]
| | | ^ ^ | | | | | ^ ^ | |
| | | | | V | | | | | | V |
[A]---[B]---| [A]-->[B] [A]---[B]<--| [A]---[B]---| [A]-->[B] [A]---[B]<--|
skipping to change at page 5, line 9 skipping to change at page 5, line 9
[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
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
network graph: A graph that reflects the network topology where all network graph: A graph that reflects the network topology where all
links connect exactly two nodes and broadcast links have been links connect exactly two nodes and broadcast links have been
transformed into a pseudonode representation (e.g. in OSPF, transformed into a pseudonode representation (e.g. in OSPF,
viewing a Network LSA as representing a pseudonode). viewing a Network LSA as representing a pseudonode).
Redundant Trees (RT): A pair of trees where the path from any node X Redundant Trees (RT): A pair of trees where the path from any node X
to the root R on the first tree is node-disjoint with the path to the root R on the first tree is node-disjoint with the path
skipping to change at page 43, line 45 skipping to change at page 43, line 45
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 to Select_Alternates_Internal() operates, As an example of how Select_Alternates_Internal() operates, consider
consider the ADAG depicted in Figure 26 and first suppose that G is the ADAG depicted in Figure 26 and first suppose that G is the
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.
skipping to change at page 44, line 23 skipping to change at page 44, line 23
[R] [C] [G]->[I] [R] [C] [G]->[I]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[A]->[B]->[F]---| [A]->[B]->[F]---|
(a)ADAG rooted at R for (a)ADAG rooted at R for
a 2-connected graph a 2-connected graph
Figure 26 Figure 26
5.9. Finding MRT Next-Hops for Proxy-Nodes 5.9. Named Proxy-Nodes
As discussed in Section 11.2 of As discussed in Section 11.2 of
[I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT- [I-D.ietf-rtgwg-mrt-frr-architecture], it is necessary to find MRT-
Blue and MRT-Red next-hops and MRT-FRR alternates for a named proxy- Blue and MRT-Red next-hops and MRT-FRR alternates for named proxy-
nodes. An example use case is for a router that is not part of that nodes. An example use case is for a router that is not part of that
local MRT Island, when there is only partial MRT support in the local MRT Island, when there is only partial MRT support in the
domain. domain.
The proxy-node is connected to at most two nodes in the GADAG. 5.9.1. Determining Proxy-Node Attachment Routers
Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the
proxy-node attachment routers MUST be determined. The degenerate Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] discusses
case where the proxy-node is attached to only one node in the GADAG general considerations for determining the two proxy-node attachment
is trivial as all needed information can be derived from that proxy routers for a given proxy-node, corresponding to a prefix. A router
in the MRT Island that advertises the prefix is a candidate for being
a proxy-node attachment router, with the associated named-proxy-cost
equal to the advertised cost to the prefix.
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
Island but in the same area/level. An (IBR,IN) pair is a candidate
for being a proxy-node attachment router, if the shortest path from
the IN to the prefix does not enter the MRT Island. A method for
identifying such loop-free Island Neighbors(LFINs) is given below.
The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN)
+ D_opt(IN, prefix).
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
are selected. Ties are broken based upon the lowest Router ID. For
ease of discussion, the two selected routers will be referred to as
proxy-node attachment routers.
5.9.2. Computing if an Island Neighbor (IN) is loop-free
As discussed above, the Island Neighbor needs to be loop-free with
respect to the whole MRT Island for the destination. This can be
accomplished by running the usual SPF algorithm while keeping track
of which shortest paths have passed through the MRT island. Pseudo-
code for this is shown in Figure 27. The Island_Marking_SPF() is run
for each IN that needs to be evaluated for the loop-free condition,
with the IN as the spf_root. Whether or not an IN is loop-free with
respect to the MRT island can then be determined by evaluating
node.PATH_HITS_ISLAND for each destination of interest.
Island_Marking_SPF(spf_root)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
and PATH_HITS_ISLAND to false
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
foreach interface intf of min_node
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
Figure 27: Island_Marking_SPF for determining if an Island Neighbor
is loop-free
It is also possible that a given prefix is originated by a
combination of non-island routers and island routers. The results of
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.
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
to reach a prefix-advertising node and the cost with which that node
advertises the prefix. The path with the minimum total cost to
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
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
of the prefix-advertising routers involved in the minimum total cost
paths MUST have PATH_HITS_ISLAND set to False for the IN to be
considered loop-free to reach P.
Note that there are other computations that could be used to
determine if paths from a given IN _might_ pass through the MRT
Island for a given prefix or destination. For example, a previous
version of this draft specified running the SPF algorithm on modified
topology which treats the MRT island as a single node (with intra-
island links set to zero cost) in order to provide input to
computations to determine if the path from IN to non-island
destination hits the MRT island in this modified topology. This
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
which is disqualified for hitting the MRT island in the modified
topology will not actually hit the MRT Island in the original
topology. The algorithm described in Island_Marking_SPF() above does
not modify the original topology, and will only disqualify a path if
the actual path does in fact hit the MRT island.
Since all routers need to come to the same conclusion about which
routers qualify as LFINs, this specification requires that all
routers computing LFINs MUST use an algorithm whose result is
identical to that of the Island_Marking_SPF() in Figure 27.
5.9.3. Computing MRT Next-Hops for Proxy-Nodes
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
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
canbe 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 pseudo-code for Select_Proxy_Node_NHs(P,S)
in Figure 27 specifies how a computing-router S MUST compute the MRT in Figure 28 specifies how a computing-router S MUST compute the MRT
red and blue next-hops to reach proxy-node P. The proxy-node red and blue next-hops to reach proxy-node P. The proxy-node
attachment router with the lower value of mrt_node_id (as defined in attachment router with the lower value of mrt_node_id (as defined in
Figure 15) is assigned to X, and the other proxy-node attachment Figure 15) is assigned to X, and the other proxy-node attachment
router is assigned to Y. We will be using the relative order of X,Y, router is assigned to Y. We will be using the relative order of X,Y,
and S in the partial order defined by the GADAG to determine the MRT and S in the partial order defined by the GADAG to determine the MRT
red and blue next-hops to reach P, so we also define A and B as the red and blue next-hops to reach P, so we also define A and B as the
order proxies for X and Y, respectively, with respect to S. The order proxies for X and Y, respectively, with respect to S. The
order proxies for all nodes with respect to S were already computed order proxies for all nodes with respect to S were already computed
in Compute_MRT_NextHops(). in Compute_MRT_NextHops().
skipping to change at page 45, line 20 skipping to change at page 48, line 18
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
A = X.order_proxy A = X.order_proxy
B = Y.order_proxy B = Y.order_proxy
if (A is S.localroot if (A is S.localroot
and B is S.localroot): and B is S.localroot):
#print("1.0") // case 1.0
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
if (A is S.localroot if (A is S.localroot
and B is not S.localroot): and B is not S.localroot):
#print("2.0") // case 2.0
if B.LOWER: if B.LOWER:
#print("2.1") // case 2.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
if B.HIGHER: if B.HIGHER:
#print("2.2") // case 2.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
else: else:
#print("2.3") // case 2.3
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.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return return
if (A is not S.localroot if (A is not S.localroot
and B is S.localroot): and B is S.localroot):
#print("3.0") // case 3.0
if A.LOWER: if A.LOWER:
#print("3.1") // case 3.1
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
if A.HIGHER: if A.HIGHER:
#print("3.2") // case 3.2
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:
#print("3.3") // case 3.3
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.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return return
if (A is not S.localroot if (A is not S.localroot
and B is not S.localroot): and B is not S.localroot):
#print("4.0") // case 4.0
if (S is A.localroot or S is B.localroot): if (S is A.localroot or S is B.localroot):
#print("4.05") // case 4.05
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.05.1") // case 4.05.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:
#print("4.05.2") // case 4.05.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
if A.LOWER: if A.LOWER:
#print("4.1") // case 4.1
if B.HIGHER: if B.HIGHER:
#print("4.1.1") // case 4.1.1
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
if B.LOWER: if B.LOWER:
#print("4.1.2") // case 4.1.2
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.1.2.1") // case 4.1.2.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:
#print("4.1.2.2") // case 4.1.2.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
else: else:
#print("4.1.3") // case 4.1.3
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.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return return
if A.HIGHER: if A.HIGHER:
// case 4.2
#print("4.2")
if B.HIGHER: if B.HIGHER:
#print("4.2.1") // case 4.2.1
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.2.1.1") // case 4.2.1.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:
#print("4.2.1.2") // case 4.2.1.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
if B.LOWER: if B.LOWER:
#print("4.2.2") // case 4.2.2
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:
#print("4.2.3") // case 4.2.3
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:
#print("4.3") // case 4.3
if B.LOWER: if B.LOWER:
#print("4.3.1") // case 4.3.1
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.red_next_hops) Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return return
if B.HIGHER: if B.HIGHER:
#print("4.3.2") // case 4.3.2
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:
#print("4.3.3") // case 4.3.3
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("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:
#print("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 27: 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
skipping to change at page 50, line 39 skipping to change at page 53, line 35
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 the
red path to Y and the red path to X as the disjoint MRT paths to 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
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 28. shown in the pseudo-code 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 51, line 33 skipping to change at page 54, line 32
if (alt_to_X == 'USE_RED_OR_BLUE' if (alt_to_X == 'USE_RED_OR_BLUE'
and alt_to_Y == 'USE_RED_OR_BLUE'): and alt_to_Y == 'USE_RED_OR_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED_OR_BLUE': if alt_to_X == 'USE_RED_OR_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED_OR_BLUE': if alt_to_Y == 'USE_RED_OR_BLUE':
return 'USE_RED' return 'USE_RED'
if (A is S.localroot if (A is S.localroot
and B is S.localroot): and B is S.localroot):
#print("1.0") // case 1.0
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if (A is S.localroot if (A is S.localroot
and B is not S.localroot): and B is not S.localroot):
#print("2.0") // case 2.0
if B.LOWER: if B.LOWER:
#print("2.1") // case 2.1
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if B.HIGHER: if B.HIGHER:
#print("2.2")
// case 2.2
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("2.3") // case 2.3
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if (A is not S.localroot if (A is not S.localroot
and B is S.localroot): and B is S.localroot):
#print("3.0") // case 3.0
if A.LOWER: if A.LOWER:
#print("3.1") // case 3.1
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if A.HIGHER: if A.HIGHER:
#print("3.2") // case 3.2
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("3.3") // case 3.3
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if (A is not S.localroot if (A is not S.localroot
and B is not S.localroot): and B is not S.localroot):
#print("4.0") // case 4.0
if (S is A.localroot or S is B.localroot): if (S is A.localroot or S is B.localroot):
#print("4.05") // case 4.05
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.05.1") // case 4.05.1
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'): if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.05.2") // case 4.05.2
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if A.LOWER: if A.LOWER:
#print("4.1") // case 4.1
if B.HIGHER: if B.HIGHER:
#print("4.1.1") // case 4.1.1
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'): if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if B.LOWER: if B.LOWER:
#print("4.1.2") // case 4.1.2
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.1.2.1") // case 4.1.2.1
if (alt_to_X == 'USE_BLUE' if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'): and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.1.2.2") // case 4.1.2.2
if (alt_to_X == 'USE_RED' if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'): and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.1.3") // case 4.1.3
if (F.LOWER and not F.HIGHER if (F.LOWER and not F.HIGHER
and F.topo_order > A.topo_order): and F.topo_order > A.topo_order):
#print("4.1.3.1") // case 4.1.3.1
return 'USE_RED' return 'USE_RED'
else: else:
#print("4.1.3.2") // case 4.1.3.2
return 'USE_BLUE' return 'USE_BLUE'
if A.HIGHER: if A.HIGHER:
#print("4.2") // case 4.2
if B.HIGHER: if B.HIGHER:
#print("4.2.1") // case 4.2.1
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.2.1.1") // case 4.2.1.1
if (alt_to_X == 'USE_BLUE' if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'): and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.2.1.2") // case 4.2.1.2
if (alt_to_X == 'USE_RED' if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'): and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
if B.LOWER: if B.LOWER:
#print("4.2.2") // case 4.2.2
if (alt_to_X == 'USE_BLUE' if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'): and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.2.3") // case 4.2.3
if (F.HIGHER and not F.LOWER if (F.HIGHER and not F.LOWER
and F.topo_order < A.topo_order): and F.topo_order < A.topo_order):
return 'USE_RED' return 'USE_RED'
else: else:
return 'USE_BLUE' return 'USE_BLUE'
else: else:
#print("4.3") // case 4.3
if B.LOWER: if B.LOWER:
#print("4.3.1") // case 4.3.1
if (F.LOWER and not F.HIGHER if (F.LOWER and not F.HIGHER
and F.topo_order > B.topo_order): and F.topo_order > B.topo_order):
return 'USE_BLUE' return 'USE_BLUE'
else: else:
return 'USE_RED' return 'USE_RED'
if B.HIGHER: if B.HIGHER:
#print("4.3.2") // case 4.3.2
if (F.HIGHER and not F.LOWER if (F.HIGHER and not F.LOWER
and F.topo_order < B.topo_order): and F.topo_order < B.topo_order):
return 'USE_BLUE' return 'USE_BLUE'
else: else:
return 'USE_RED' return 'USE_RED'
else: else:
#print("4.3.3") // case 4.3.3
if A.topo_order < B.topo_order: if A.topo_order < B.topo_order:
#print("4.3.3.1") // case 4.3.3.1
if (alt_to_X == 'USE_BLUE' if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'): and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE': if alt_to_X == 'USE_BLUE':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_RED': if alt_to_Y == 'USE_RED':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
else: else:
#print("4.3.3.2") // case 4.3.3.2
if (alt_to_X == 'USE_RED' if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'): and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED': if alt_to_X == 'USE_RED':
return 'USE_BLUE' return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE': if alt_to_Y == 'USE_BLUE':
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
assert(False) assert(False)
Figure 29: Select_Alternates_Proxy_Node()
Figure 28: Select_Alternates_Proxy_Node()
Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it Select_Alternates_Proxy_Node(P,F,primary_intf) determines whether it
is safe to use the blue path to P (which goes through X), the red is safe to use the blue path to P (which goes through X), the red
path to P (which goes through Y), or either, when the primary_intf to path to P (which goes through Y), or either, when the primary_intf to
node F (and possibly node F) fails. The basic approach is to run node F (and possibly node F) fails. The basic approach is to run
Select_Alternates(X,F,primary_intf) and Select_Alternates(X,F,primary_intf) and
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
skipping to change at page 59, line 26 skipping to change at page 62, line 26
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 [RFC2327] 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. As OSPF runs Dijkstra's algorithm, whenever a shorter path is
found reach a real destination node, and the shorter path is one hop found reach a real destination node, and the shorter path is one hop
from the computing routing, and that one hop is a pseudonode, then from the computing routing, and that one hop is a pseudonode, then
the next-hop for that destination is taken from the interface IP the next-hop for that destination is taken from the interface IP
address in the Router-LSA correspond to the link to the real address in the Router-LSA correspond to the link to the real
destination node destination node
For IS-IS, in the example pseudo-code implementation of Dijkstra's For IS-IS, in the example pseudo-code 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,
skipping to change at page 61, line 23 skipping to change at page 64, line 23
particular set of failure conditions is a local decision, since it particular set of failure conditions is a local decision, since it
does not require coordination with other nodes. does not require coordination with other nodes.
8. Python Implementation of MRT Lowpoint Algorithm 8. 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. In order to avoid the page breaks in the
.txt version of the draft, one can cut and paste the Python code from .txt version of the draft, one can cut and paste the Python code from
the .xml version. The code is also posted on Github. the .xml version. The code is also posted on Github.
While this Python code is believed to correctly implement the pseudo-
code description of the algorithm, in the event of a difference, the
pseudo-code 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 algorithm.This
# was done to simplify the inclusion of the program as a single text # was done to simplify the inclusion of the program as a single text
# file that can be extracted from the IETF draft. # file that can be extracted from the IETF draft.
skipping to change at page 65, line 51 skipping to change at page 69, line 7
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.MRT_INELIGIBLE)
and (not intf.remote_intf.MRT_INELIGIBLE) and (not intf.remote_intf.MRT_INELIGIBLE)
and (not intf.IGP_EXCLUDED) and intf.area == area ): and (not intf.IGP_EXCLUDED) and intf.area == area
and (profile_id in intf.remote_node.profile_id_list)):
if (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_node.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)
def Set_Island_Intf_and_Node_Lists(topo): def Set_Island_Intf_and_Node_Lists(topo):
skipping to change at page 76, line 45 skipping to change at page 79, line 49
return 'USE_BLUE' return 'USE_BLUE'
if F.topo_order < D_topo_order: if F.topo_order < D_topo_order:
return 'USE_RED' return 'USE_RED'
assert(False) assert(False)
assert(primary_intf.MRT_INELIGIBLE assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE) or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
else: # D is unordered wrt S else: # D is unordered wrt S
if F.HIGHER and F.LOWER: if F.HIGHER and F.LOWER:
if primary_intf.OUTGOING and primary_intf.INCOMING: if primary_intf.OUTGOING and primary_intf.INCOMING:
# This can happen when the primary next hop goes # This can happen when F and D are in different blocks
# to a node in a different block and D is
# unordered wrt S.
return 'USE_RED_OR_BLUE' return 'USE_RED_OR_BLUE'
if primary_intf.OUTGOING: if primary_intf.OUTGOING:
return 'USE_BLUE' return 'USE_BLUE'
if primary_intf.INCOMING: if primary_intf.INCOMING:
return 'USE_RED' return 'USE_RED'
#This can occur when primary_intf is MRT_INELIGIBLE. #This can occur when primary_intf is MRT_INELIGIBLE.
#This appears to be a case where the special #This appears to be a case where the special
#construction of the GADAG allows us to choose red, #construction of the GADAG allows us to choose red,
#whereas with an arbitrary GADAG, neither red nor blue #whereas with an arbitrary GADAG, neither red nor blue
#is guaranteed to work. #is guaranteed to work.
assert(primary_intf.MRT_INELIGIBLE assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE) or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED' return 'USE_RED'
if F.LOWER: if F.LOWER:
return 'USE_RED' return 'USE_RED'
skipping to change at page 79, line 7 skipping to change at page 82, line 10
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)
# Use Is_Remote_Node_In_NH_List() is used, as opposed # Is_Remote_Node_In_NH_List() is used, as opposed
# to just checking if failed_intf is in D.red_next_hops, # to just checking if failed_intf is in D.red_next_hops,
# because failed_intf could be marked as MRT_INELIGIBLE. # because failed_intf could be marked as MRT_INELIGIBLE.
elif Is_Remote_Node_In_NH_List(F, D.red_next_hops): elif Is_Remote_Node_In_NH_List(F, D.red_next_hops):
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 = 'LINK_PROTECTION' alt.prot = 'LINK_PROTECTION'
else: elif Is_Remote_Node_In_NH_List(F, D.blue_next_hops):
if not Is_Remote_Node_In_NH_List(F, D.blue_next_hops):
print("WEIRD behavior")
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 = 'LINK_PROTECTION' alt.prot = 'LINK_PROTECTION'
else:
alt.fec = random.choice(['RED','BLUE'])
alt.prot = 'LINK_PROTECTION'
# working version but has issue with MRT_INELIGIBLE link being
# primary_NH
# elif failed_intf in D.red_next_hops:
# Copy_List_Items(alt.nh_list, D.blue_next_hops)
# alt.fec = 'BLUE'
# alt.prot = 'LINK_PROTECTION'
# else:
# Copy_List_Items(alt.nh_list, D.red_next_hops)
# alt.fec = 'RED'
# alt.prot = 'LINK_PROTECTION'
D.alt_list.append(alt) D.alt_list.append(alt)
def Write_GADAG_To_File(topo, file_prefix): def Write_GADAG_To_File(topo, file_prefix):
gadag_edge_list = [] gadag_edge_list = []
for node in topo.node_list: for node in topo.node_list:
for intf in node.intf_list: for intf in node.intf_list:
if intf.SIMULATION_OUTGOING: if intf.SIMULATION_OUTGOING:
local_node = "%04d" % (intf.local_node.node_id) local_node = "%04d" % (intf.local_node.node_id)
remote_node = "%04d" % (intf.remote_node.node_id) remote_node = "%04d" % (intf.remote_node.node_id)
intf_data = "%03d" % (intf.link_data) intf_data = "%03d" % (intf.link_data)
skipping to change at page 102, line 33 skipping to change at page 105, line 25
they did not provide significant differences in the path lenghts for they did not provide significant differences in the path lenghts for
the alternatives. This section does not focus on that analysis or the alternatives. This section does not focus on that analysis or
the decision to use the MRT Lowpoint algorithm as the default MRT the decision to use the MRT Lowpoint algorithm as the default MRT
algorithm; it has the lowest computational and storage requirements algorithm; it has the lowest computational and storage requirements
and gave comparable results. and gave comparable results.
Since this document defines the MRT Lowpoint algorithm for use in Since this document defines the MRT Lowpoint algorithm for use in
fast-reroute applications, it is useful to compare MRT and Remote LFA fast-reroute applications, it is useful to compare MRT and Remote LFA
[RFC7490]. This section compares MRT and remote LFA for IP Fast [RFC7490]. This section compares MRT and remote LFA for IP Fast
Reroute in 19 service provider network topologies, focusing on Reroute in 19 service provider network topologies, focusing on
coverage and alternate path length. Figure 29 shows the node- coverage and alternate path length. Figure 30 shows the node-
protecting coverage provided by local LFA (LLFA), remote LFA (RLFA), protecting coverage provided by local LFA (LLFA), remote LFA (RLFA),
and MRT against different failure scenarios in these topologies. The and MRT against different failure scenarios in these topologies. The
coverage values are calculated as the percentage of source- coverage values are calculated as the percentage of source-
destination pairs protected by the given IPFRR method relative to destination pairs protected by the given IPFRR method relative to
those protectable by optimal routing, against the same failure modes. those protectable by optimal routing, against the same failure modes.
More details on alternate selection policies used for this analysis More details on alternate selection policies used for this analysis
are described later in this section. are described later in this section.
+------------+-----------------------------+ +------------+-----------------------------+
| Topology | percentage of failure | | Topology | percentage of failure |
skipping to change at page 103, line 33 skipping to change at page 106, line 33
| T212 | 59 | 63 | 100 | | T212 | 59 | 63 | 100 |
| T213 | 84 | 84 | 100 | | T213 | 84 | 84 | 100 |
| T214 | 68 | 78 | 100 | | T214 | 68 | 78 | 100 |
| T215 | 84 | 88 | 100 | | T215 | 84 | 88 | 100 |
| T216 | 43 | 59 | 100 | | T216 | 43 | 59 | 100 |
| T217 | 78 | 88 | 100 | | T217 | 78 | 88 | 100 |
| T218 | 72 | 75 | 100 | | T218 | 72 | 75 | 100 |
| T219 | 78 | 84 | 100 | | T219 | 78 | 84 | 100 |
+------------+---------+---------+---------+ +------------+---------+---------+---------+
Figure 29 Figure 30
For the topologies analyzed here, LLFA is able to provide node- For the topologies analyzed here, LLFA is able to provide node-
protecting coverage ranging from 37% to 95% of the source-destination protecting coverage ranging from 37% to 95% of the source-destination
pairs, as seen in the column labeled NP_LLFA. The use of RLFA in pairs, as seen in the column labeled NP_LLFA. The use of RLFA in
addition to LLFA is generally able to increase the node-protecting addition to LLFA is generally able to increase the node-protecting
coverage. The percentage of node-protecting coverage with RLFA is coverage. The percentage of node-protecting coverage with RLFA is
provided in the column labeled NP_RLFA, ranges from 59% to 98% for provided in the column labeled NP_RLFA, ranges from 59% to 98% for
these topologies. The node-protecting coverage provided by MRT is these topologies. The node-protecting coverage provided by MRT is
100% since MRT is able to provide protection for any source- 100% since MRT is able to provide protection for any source-
destination pair for which a path still exists after the failure. destination pair for which a path still exists after the failure.
We would also like to measure the quality of the alternate paths We would also like to measure the quality of the alternate paths
produced by these different IPFRR methods. An obvious approach is to produced by these different IPFRR methods. An obvious approach is to
take an average of the alternate path costs over all source- take an average of the alternate path costs over all source-
destination pairs and failure modes. However, this presents a destination pairs and failure modes. However, this presents a
problem, which we will illustrate by presenting an example of results problem, which we will illustrate by presenting an example of results
for one topology using this approach ( Figure 30). In this table, for one topology using this approach ( Figure 31). In this table,
the average relative path length is the alternate path length for the the average relative path length is the alternate path length for the
IPFRR method divided by the optimal alternate path length, averaged IPFRR method divided by the optimal alternate path length, averaged
over all source-destination pairs and failure modes. The first three over all source-destination pairs and failure modes. The first three
columns of data in the table give the path length calculated from the columns of data in the table give the path length calculated from the
sum of IGP metrics of the links in the path. The results for sum of IGP metrics of the links in the path. The results for
topology T208 show that the metric-based path lengths for NP_LLFA and topology T208 show that the metric-based path lengths for NP_LLFA and
NP_RLFA alternates are on average 78 and 66 times longer than the NP_RLFA alternates are on average 78 and 66 times longer than the
path lengths for optimal alternates. The metric-based path lengths path lengths for optimal alternates. The metric-based path lengths
for MRT alternates are on average 14 times longer than for optimal for MRT alternates are on average 14 times longer than for optimal
alternates. alternates.
skipping to change at page 104, line 23 skipping to change at page 107, line 23
+--------+------------------------------------------------+ +--------+------------------------------------------------+
| | average relative alternate path length | | | average relative alternate path length |
| |-----------------------+------------------------+ | |-----------------------+------------------------+
|Topology| IGP metric | hopcount | |Topology| IGP metric | hopcount |
| |-----------------------+------------------------+ | |-----------------------+------------------------+
| |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT | | |NP_LLFA |NP_RLFA | MRT |NP_LLFA |NP_RLFA | MRT |
+--------+--------+--------+-----+--------+--------+------+ +--------+--------+--------+-----+--------+--------+------+
| T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 | | T208 | 78.2 | 66.0 | 13.6| 0.99 | 1.01 | 1.32 |
+--------+--------+--------+-----+--------+--------+------+ +--------+--------+--------+-----+--------+--------+------+
Figure 30 Figure 31
The network topology represented by T208 uses values of 10, 100, and The network topology represented by T208 uses values of 10, 100, and
1000 as IGP costs, so small deviations from the optimal alternate 1000 as IGP costs, so small deviations from the optimal alternate
path can result in large differences in relative path length. LLFA, path can result in large differences in relative path length. LLFA,
RLFA, and MRT all allow for at least one hop in the alterate path to RLFA, and MRT all allow for at least one hop in the alterate path to
be chosen independent of the cost of the link. This can easily be chosen independent of the cost of the link. This can easily
result in an alternate using a link with cost 1000, which introduces result in an alternate using a link with cost 1000, which introduces
noise into the path length measurement. In the case of T208, the noise into the path length measurement. In the case of T208, the
adverse effects of using metric-based path lengths is obvious. adverse effects of using metric-based path lengths is obvious.
However, we have observed that the metric-based path length However, we have observed that the metric-based path length
introduces noise into alternate path length measurements in several introduces noise into alternate path length measurements in several
other topologies as well. For this reason, we have opted to measure other topologies as well. For this reason, we have opted to measure
the alternate path length using hopcount. While IGP metrics may be the alternate path length using hopcount. While IGP metrics may be
adjusted by the network operator for a number of reasons (e.g. adjusted by the network operator for a number of reasons (e.g.
traffic engineering), the hopcount is a fairly stable measurement of traffic engineering), the hopcount is a fairly stable measurement of
path length. As shown in the last three columns of Figure 30, the path length. As shown in the last three columns of Figure 31, the
hopcount-based alternate path lengths for topology T208 are fairly hopcount-based alternate path lengths for topology T208 are fairly
well-behaved. well-behaved.
Figure 31, Figure 32, Figure 33, and Figure 34 present the hopcount- Figure 32, Figure 33, Figure 34, and Figure 35 present the hopcount-
based path length results for the 19 topologies examined. The based path length results for the 19 topologies examined. The
topologies in the four tables are grouped based on the size of the topologies in the four tables are grouped based on the size of the
topologies, as measured by the number of nodes, with Figure 31 having topologies, as measured by the number of nodes, with Figure 32 having
the smallest topologies and Figure 34 having the largest topologies. the smallest topologies and Figure 35 having the largest topologies.
Instead of trying to represent the path lengths of a large set of Instead of trying to represent the path lengths of a large set of
alternates with a single number, we have chosen to present a alternates with a single number, we have chosen to present a
histogram of the path lengths for each IPFRR method and alternate histogram of the path lengths for each IPFRR method and alternate
selection policy studied. The first eight colums of data represent selection policy studied. The first eight colums of data represent
the percentage of failure scenarios protected by an alternate N hops the percentage of failure scenarios protected by an alternate N hops
longer than the primary path, with the first column representing an longer than the primary path, with the first column representing an
alternate 0 or 1 hops longer than the primary path, all the way up alternate 0 or 1 hops longer than the primary path, all the way up
through the eighth column respresenting an alternate 14 or 15 hops through the eighth column respresenting an alternate 14 or 15 hops
longer than the primary path. The last column in the table gives the longer than the primary path. The last column in the table gives the
percentage of failure scenarios for which there is no alternate less percentage of failure scenarios for which there is no alternate less
skipping to change at page 106, line 50 skipping to change at page 109, line 50
| MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | | | MRT_LOWPOINT_ONLY | 58| 27| 11| 3| 1| | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T205(avg primary hops=3.4) | | | | | | | | | | | T205(avg primary hops=3.4) | | | | | | | | | |
| OPTIMAL | 92| 8| | | | | | | | | OPTIMAL | 92| 8| | | | | | | |
| NP_LLFA | 89| 3| | | | | | | 8| | NP_LLFA | 89| 3| | | | | | | 8|
| NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7| | NP_LLFA_THEN_NP_RLFA | 90| 4| | | | | | | 7|
| NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 91| 9| | | | | | | |
| MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | | | MRT_LOWPOINT_ONLY | 62| 33| 5| 1| | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 31 Figure 32
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 107, line 50 skipping to change at page 110, line 50
| MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | | | MRT_LOWPOINT_ONLY | 63| 29| 8| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T210(avg primary hops=2.5) | | | | | | | | | | | T210(avg primary hops=2.5) | | | | | | | | | |
| OPTIMAL | 95| 4| 1| | | | | | | | OPTIMAL | 95| 4| 1| | | | | | |
| NP_LLFA | 94| 1| | | | | | | 5| | NP_LLFA | 94| 1| | | | | | | 5|
| NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2| | NP_LLFA_THEN_NP_RLFA | 94| 3| 1| | | | | | 2|
| NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | | | NP_LLFA_THEN_MRT_LOWPOINT | 95| 4| 1| | | | | | |
| MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | | | MRT_LOWPOINT_ONLY | 91| 6| 2| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 32 Figure 33
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 108, line 50 skipping to change at page 111, line 50
| MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3| | MRT_LOWPOINT_ONLY | 30| 20| 18| 12| 8| 4| 3| 2| 3|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T215(avg primary hops=4.8) | | | | | | | | | | | T215(avg primary hops=4.8) | | | | | | | | | |
| OPTIMAL | 73| 27| | | | | | | | | OPTIMAL | 73| 27| | | | | | | |
| NP_LLFA | 73| 11| | | | | | | 16| | NP_LLFA | 73| 11| | | | | | | 16|
| NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12| | NP_LLFA_THEN_NP_RLFA | 73| 13| 2| | | | | | 12|
| NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | | | NP_LLFA_THEN_MRT_LOWPOINT | 74| 19| 3| 2| 1| 1| 1| | |
| MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | | | MRT_LOWPOINT_ONLY | 32| 31| 16| 12| 4| 3| 1| | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 33 Figure 34
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 109, line 43 skipping to change at page 112, line 43
| MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | | | MRT_LOWPOINT_ONLY | 37| 29| 21| 10| 3| 1| | | |
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T219(avg primary hops=7.7) | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | |
| OPTIMAL | 77| 15| 5| 1| 1| | | | | | OPTIMAL | 77| 15| 5| 1| 1| | | | |
| NP_LLFA | 72| 5| | | | | | | 22| | NP_LLFA | 72| 5| | | | | | | 22|
| NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16| | NP_LLFA_THEN_NP_RLFA | 73| 8| 2| | | | | | 16|
| NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4| | NP_LLFA_THEN_MRT_LOWPOINT | 74| 8| 3| 3| 2| 2| 2| 2| 4|
| MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10| | MRT_LOWPOINT_ONLY | 19| 14| 15| 12| 10| 8| 7| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 34 Figure 35
In the preceding analysis, the following procedure for selecting an In the preceding analysis, the following procedure for selecting an
RLFA was used. Nodes were ordered with respect to distance from the RLFA was used. Nodes were ordered with respect to distance from the
source and checked for membership in Q and P-space. The first node source and checked for membership in Q and P-space. The first node
to satisfy this condition was selected as the RLFA. More to satisfy this condition was selected as the RLFA. More
sophisticated methods to select node-protecting RLFAs is an area of sophisticated methods to select node-protecting RLFAs is an area of
active research. active research.
The analysis presented above uses the MRT Lowpoint Algorithm defined The analysis presented above uses the MRT Lowpoint Algorithm defined
in this specification with a common GADAG root. The particular in this specification with a common GADAG root. The particular
skipping to change at page 110, line 24 skipping to change at page 113, line 24
chosen based on the GADAG Root Selection Priority advertised by each chosen based on the GADAG Root Selection Priority advertised by each
router, the values of which would be determined off-line. router, the values of which would be determined off-line.
In order to measure how sensitive the MRT alternate path lengths are In order to measure how sensitive the MRT alternate path lengths are
to the choice of common GADAG root, we performed the same analysis to the choice of common GADAG root, we performed the same analysis
using different choices of GADAG root. All of the nodes in the using different choices of GADAG root. All of the nodes in the
network were ordered with respect to the node centrality as computed network were ordered with respect to the node centrality as computed
above. Nodes were chosen at the 0th, 25th, and 50th percentile with above. Nodes were chosen at the 0th, 25th, and 50th percentile with
respect to the centrality ordering, with 0th percentile being the respect to the centrality ordering, with 0th percentile being the
most central node. The distribution of alternate path lengths for most central node. The distribution of alternate path lengths for
those three choices of GADAG root are shown in Figure 35 for a subset those three choices of GADAG root are shown in Figure 36 for a subset
of the 19 topologies (chosen arbitrarily). The third row for each of the 19 topologies (chosen arbitrarily). The third row for each
topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the topology (labeled MRT_LOWPOINT ( 0 percentile) ) reproduces the
results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth results presented above for MRT_LOWPOINT_ONLY. The fourth and fifth
rows show the alternate path length distibution for the 25th and 50th rows show the alternate path length distibution for the 25th and 50th
percentile choice for GADAG root. One can see some impact on the percentile choice for GADAG root. One can see some impact on the
path length distribution with the less central choice of GADAG root path length distribution with the less central choice of GADAG root
resulting in longer path lenghths. resulting in longer path lenghths.
We also looked at the impact of MRT algorithm variant on the We also looked at the impact of MRT algorithm variant on the
alternate path lengths. The first two rows for each topology present alternate path lengths. The first two rows for each topology present
skipping to change at page 111, line 50 skipping to change at page 114, line 50
| MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10| | MRT_LOWPOINT (50 percentile) | 19| 14| 13| 10| 8| 6| 5| 5| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
| T219(avg primary hops=7.7) | | | | | | | | | | | T219(avg primary hops=7.7) | | | | | | | | | |
| MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3| | MRT_HYBRID ( 0 percentile) | 20| 16| 13| 10| 7| 5| 5| 5| 3|
| MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| | | MRT_SPF ( 0 percentile) | 31| 23| 19| 12| 7| 4| 2| 1| |
| MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10| | MRT_LOWPOINT ( 0 percentile) | 19| 14| 15| 12| 10| 8| 7| 6| 10|
| MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7| | MRT_LOWPOINT (25 percentile) | 19| 14| 15| 13| 12| 10| 6| 5| 7|
| MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10| | MRT_LOWPOINT (50 percentile) | 19| 14| 14| 12| 11| 8| 6| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
Figure 35 Figure 36
10. Implementation Status 10. Implementation Status
[RFC Editor: please remove this section prior to publication.] [RFC Editor: please remove this section prior to publication.]
Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on Please see [I-D.ietf-rtgwg-mrt-frr-architecture] for details on
implementation status. implementation status.
11. Acknowledgements 11. Acknowledgements
The authors would like to thank Shraddha Hegde for her suggestions The authors would like to thank Shraddha Hegde, Eric Wu, and Janos
and review. We would also like to thank Anil Kumar SN for his Farkas for their suggestions and review. We would also like to thank
assistance in clarifying the algorithm description and pseudo-code. Anil Kumar SN for his assistance in clarifying the algorithm
description and pseudo-code.
12. IANA Considerations 12. IANA Considerations
This document includes no request to IANA. This document includes no request to IANA.
13. Security Considerations 13. Security Considerations
This architecture is not currently believed to introduce new security The algorithm described in this document does not introduce new
concerns. security concerns beyond those already discussed in the document
describing the MRT FRR architecture
[I-D.ietf-rtgwg-mrt-frr-architecture].
14. References 14. References
14.1. Normative References 14.1. Normative References
[I-D.ietf-rtgwg-mrt-frr-architecture] [I-D.ietf-rtgwg-mrt-frr-architecture]
Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar, Atlas, A., Kebler, R., Bowers, C., Envedi, G., Csaszar,
A., Tantsura, J., and R. White, "An Architecture for IP/ A., Tantsura, J., and R. White, "An Architecture for IP/
LDP Fast-Reroute Using Maximally Redundant Trees", draft- LDP Fast-Reroute Using Maximally Redundant Trees", draft-
ietf-rtgwg-mrt-frr-architecture-05 (work in progress), ietf-rtgwg-mrt-frr-architecture-07 (work in progress),
January 2015. 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 14.2. Informative References
[EnyediThesis] [EnyediThesis]
Enyedi, G., "Novel Algorithms for IP Fast Reroute", Enyedi, G., "Novel Algorithms for IP Fast Reroute",
Department of Telecommunications and Media Informatics, Department of Telecommunications and Media Informatics,
Budapest University of Technology and Economics Ph.D. Budapest University of Technology and Economics Ph.D.
Thesis, February 2011, <http://www.omikk.bme.hu/collection Thesis, February 2011, <http://www.omikk.bme.hu/collection
s/phd/Villamosmernoki_es_Informatikai_Kar/2011/ s/phd/Villamosmernoki_es_Informatikai_Kar/2011/
Enyedi_Gabor/ertekezes.pdf>. Enyedi_Gabor/ertekezes.pdf>.
[I-D.ietf-isis-mrt] [I-D.ietf-isis-mrt]
Li, Z., Wu, N., Zhao, Q., Atlas, A., Bowers, C., and J. Li, Z., Wu, N., <>, Q., Atlas, A., Bowers, C., and J.
Tantsura, "Intermediate System to Intermediate System (IS- Tantsura, "Intermediate System to Intermediate System (IS-
IS) Extensions for Maximally Redundant Trees (MRT)", IS) Extensions for Maximally Redundant Trees (MRT)",
draft-ietf-isis-mrt-00 (work in progress), February 2015. draft-ietf-isis-mrt-01 (work in progress), October 2015.
[I-D.ietf-isis-pcr] [I-D.ietf-isis-pcr]
Farkas, J., Bragg, N., Unbehagen, P., Parsons, G., Farkas, J., Bragg, N., Unbehagen, P., Parsons, G.,
Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation Ashwood-Smith, P., and C. Bowers, "IS-IS Path Computation
and Reservation", draft-ietf-isis-pcr-00 (work in and Reservation", draft-ietf-isis-pcr-04 (work in
progress), April 2015. progress), December 2015.
[I-D.ietf-mpls-ldp-mrt]
Atlas, A., Tiruveedhula, K., Bowers, C., Tantsura, J., and
I. Wijnands, "LDP Extensions to Support Maximally
Redundant Trees", draft-ietf-mpls-ldp-mrt-00 (work in
progress), January 2015.
[I-D.ietf-ospf-mrt] [I-D.ietf-ospf-mrt]
Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li, Atlas, A., Hegde, S., Bowers, C., Tantsura, J., and Z. Li,
"OSPF Extensions to Support Maximally Redundant Trees", "OSPF Extensions to Support Maximally Redundant Trees",
draft-ietf-ospf-mrt-00 (work in progress), January 2015. draft-ietf-ospf-mrt-01 (work in progress), October 2015.
[I-D.ietf-rtgwg-ipfrr-notvia-addresses]
Bryant, S., Previdi, S., and M. Shand, "A Framework for IP
and MPLS Fast Reroute Using Not-via Addresses", draft-
ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress),
May 2013.
[I-D.ietf-rtgwg-lfa-manageability] [I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational management of Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draft-ietf-rtgwg-lfa- Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-11 (work in progress), June 2015. manageability-11 (work in progress), June 2015.
[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, Nov. 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 , Nov 1962,
<http://dl.acm.org/citation.cfm?doid=368996.369025>. <http://dl.acm.org/citation.cfm?doid=368996.369025>.
[LFARevisited]
Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP
Fast ReRoute: Loop Free Alternates Revisited", Proceedings
of IEEE INFOCOM , 2011,
<http://opti.tmit.bme.hu/~tapolcai/papers/
retvari2011lfa_infocom.pdf>.
[LightweightNotVia]
Enyedi, G., Retvari, G., Szilagyi, P., and A. Csaszar, "IP
Fast ReRoute: Lightweight Not-Via without Additional
Addresses", Proceedings of IEEE INFOCOM , 2009,
<http://mycite.omikk.bme.hu/doc/71691.pdf>.
[MRTLinear] [MRTLinear]
Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Enyedi, G., Retvari, G., and A. Csaszar, "On Finding
Maximally Redundant Trees in Strictly Linear Time", IEEE Maximally Redundant Trees in Strictly Linear Time", IEEE
Symposium on Computers and Comunications (ISCC) , 2009, Symposium on Computers and Comunications (ISCC) , 2009,
<http://opti.tmit.bme.hu/~enyedi/ipfrr/ <http://opti.tmit.bme.hu/~enyedi/ipfrr/
distMaxRedTree.pdf>. distMaxRedTree.pdf>.
[RFC2327] Handley, M. and V. Jacobson, "SDP: Session Description [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328,
Protocol", RFC 2327, DOI 10.17487/RFC2327, April 1998, DOI 10.17487/RFC2328, April 1998,
<http://www.rfc-editor.org/info/rfc2327>. <http://www.rfc-editor.org/info/rfc2328>.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137,
DOI 10.17487/RFC3137, June 2001,
<http://www.rfc-editor.org/info/rfc3137>.
[RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi [RFC5120] Przygienda, T., Shen, N., and N. Sheth, "M-ISIS: Multi
Topology (MT) Routing in Intermediate System to Topology (MT) Routing in Intermediate System to
Intermediate Systems (IS-ISs)", RFC 5120, Intermediate Systems (IS-ISs)", RFC 5120,
DOI 10.17487/RFC5120, February 2008, DOI 10.17487/RFC5120, February 2008,
<http://www.rfc-editor.org/info/rfc5120>. <http://www.rfc-editor.org/info/rfc5120>.
[RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
IP Fast Reroute: Loop-Free Alternates", RFC 5286,
DOI 10.17487/RFC5286, September 2008,
<http://www.rfc-editor.org/info/rfc5286>.
[RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
RFC 5714, DOI 10.17487/RFC5714, January 2010,
<http://www.rfc-editor.org/info/rfc5714>.
[RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene,
B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free
Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, DOI 10.17487/RFC6571, June 2012,
<http://www.rfc-editor.org/info/rfc6571>.
[RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N. [RFC7490] Bryant, S., Filsfils, C., Previdi, S., Shand, M., and N.
So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)", So, "Remote Loop-Free Alternate (LFA) Fast Reroute (FRR)",
RFC 7490, DOI 10.17487/RFC7490, April 2015, RFC 7490, DOI 10.17487/RFC7490, April 2015,
<http://www.rfc-editor.org/info/rfc7490>. <http://www.rfc-editor.org/info/rfc7490>.
Appendix A. Option 2: Computing GADAG using SPFs Appendix A. Option 2: Computing GADAG using SPFs
The basic idea in this option is to use slightly-modified SPF The basic idea in this option is to use slightly-modified SPF
computations to find ears. In every block, an SPF computation is computations to find ears. In every block, an SPF computation is
first done to find a cycle from the local root and then SPF first done to find a cycle from the local root and then SPF
skipping to change at page 116, line 40 skipping to change at page 119, line 4
and cand_intf.local_node as TEMP_UNUSABLE and cand_intf.local_node as TEMP_UNUSABLE
if cand_intf.local_node is not block_root if cand_intf.local_node is not block_root
Mark cand_intf.local_node as TEMP_UNUSABLE Mark cand_intf.local_node as TEMP_UNUSABLE
Initialize ear_list to empty Initialize ear_list to empty
end_ear = Mod_SPF(spf_root, block_root) end_ear = Mod_SPF(spf_root, block_root)
y = end_ear.spf_prev_hop y = end_ear.spf_prev_hop
while y.local_node is not spf_root while y.local_node is not spf_root
add_to_list_start(ear_list, y) add_to_list_start(ear_list, y)
y.local_node.IN_GADAG = true y.local_node.IN_GADAG = true
y = y.local_node.spf_prev_intf y = y.local_node.spf_prev_intf
if(method is not hybrid) if(method is not hybrid)
Set_Ear_Direction(ear_list, cand_intf.local_node, Set_Ear_Direction(ear_list, cand_intf.local_node,
end_ear,block_root) end_ear,block_root)
Clear TEMP_UNUSABLE from all interfaces between Clear TEMP_UNUSABLE from all interfaces between
cand_intf.remote_node and cand_intf.local_node cand_intf.remote_node and cand_intf.local_node
Clear TEMP_UNUSABLE from cand_intf.local_node Clear TEMP_UNUSABLE from cand_intf.local_node
return end_ear return end_ear
Figure 36: Modified SPF for GADAG computation Figure 37: Modified SPF for GADAG computation
Assume that an ear is found by going from y to x and then running an Assume that an ear is found by going from y to x and then running an
SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is SPF that terminates by minimizing z (e.g. y<->x...q<->z). Now it is
necessary to determine the direction of the ear; if y << z, then the necessary to determine the direction of the ear; if y << z, then the
path should be y->x...q->z but if y >> z, then the path should be y<- path should be y->x...q->z but if y >> z, then the path should be y<-
x...q<-z. In Section 5.5, the same problem was handled by finding x...q<-z. In Section 5.5, the same problem was handled by finding
all ears that started at a node before looking at ears starting at all ears that started at a node before looking at ears starting at
nodes higher in the partial order. In this algorithm, using that nodes higher in the partial order. In this algorithm, using that
approach could mean that new ears aren't added in order of their approach could mean that new ears aren't added in order of their
total cost since all ears connected to a node would need to be found total cost since all ears connected to a node would need to be found
skipping to change at page 118, line 48 skipping to change at page 120, 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 37: Algorithm to assign links of an ear direction Figure 38: Algorithm to assign links of an ear direction
A goal of the algorithm is to find the shortest cycles and ears. An A goal of the algorithm is to find the shortest cycles and ears. An
ear is started by going to a neighbor x of an IN_GADAG node y. The ear is started by going to a neighbor x of an IN_GADAG node y. The
path from x to an IN_GADAG node is minimal, since it is computed via path from x to an IN_GADAG node is minimal, since it is computed via
SPF. Since a shortest path is made of shortest paths, to find the SPF. Since a shortest path is made of shortest paths, to find the
shortest ears requires reaching from the set of IN_GADAG nodes to the shortest ears requires reaching from the set of IN_GADAG nodes to the
closest node that isn't IN_GADAG. Therefore, an ordered tree is closest node that isn't IN_GADAG. Therefore, an ordered tree is
maintained of interfaces that could be explored from the IN_GADAG maintained of interfaces that could be explored from the IN_GADAG
nodes. The interfaces are ordered by their characteristics of nodes. The interfaces are ordered by their characteristics of
metric, local loopback address, remote loopback address, and ifindex, metric, local loopback address, remote loopback address, and ifindex,
skipping to change at page 120, line 30 skipping to change at page 122, line 30
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 38: SPF-based GADAG algorithm Figure 39: SPF-based GADAG algorithm
Appendix B. Option 3: Computing GADAG using a hybrid method Appendix B. Option 3: Computing GADAG using a hybrid method
In this option, the idea is to combine the salient features of the In this option, the idea is to combine the salient features of the
lowpoint inheritance and SPF methods. To this end, we process nodes lowpoint inheritance and SPF methods. To this end, we process nodes
as they get added to the GADAG just like in the lowpoint inheritance as they get added to the GADAG just like in the lowpoint inheritance
by maintaining a stack of nodes. This ensures that we do not need to by maintaining a stack of nodes. This ensures that we do not need to
maintain lower and higher sets at each node to ascertain ear maintain lower and higher sets at each node to ascertain ear
directions since the ears will always be directed from the node being directions since the ears will always be directed from the node being
processed towards the end of the ear. To compute the ear however, we processed towards the end of the ear. To compute the ear however, we
skipping to change at page 121, line 12 skipping to change at page 123, line 12
of an ear is pre-determined. Thus, whenever the block already has an of an ear is pre-determined. Thus, whenever the block already has an
ear computed, and we are processing an interface of the block root, ear computed, and we are processing an interface of the block root,
we mark the block root as unusable before the SPF run that computes we mark the block root as unusable before the SPF run that computes
the ear. This ensures that the SPF terminates at some node other the ear. This ensures that the SPF terminates at some node other
than the block-root. This in turn guarantees that the block-root has than the block-root. This in turn guarantees that the block-root has
only one incoming interface in each block, which is necessary for only one incoming interface in each block, which is necessary for
correctly computing the next-hops on the GADAG. correctly computing the next-hops on the GADAG.
As in the SPF gadag, bridge ears are handled as a special case. As in the SPF gadag, bridge ears are handled as a special case.
The entire algorithm is shown below in Figure 39 The entire algorithm is shown below in Figure 40
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 122, line 14 skipping to change at page 124, line 14
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 39: Hybrid GADAG algorithm Figure 40: Hybrid GADAG algorithm
Authors' Addresses Authors' Addresses
Gabor Sandor Enyedi (editor) 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
Andras Csaszar Andras Csaszar
Ericsson Ericsson
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 (editor) Alia Atlas
Juniper Networks Juniper Networks
10 Technology Park Drive 10 Technology Park Drive
Westford, MA 01886 Westford, MA 01886
USA USA
Email: akatlas@juniper.net Email: akatlas@juniper.net
Chris Bowers Chris Bowers
Juniper Networks Juniper Networks
1194 N. Mathilda Ave. 1194 N. Mathilda Ave.
 End of changes. 131 change blocks. 
225 lines changed or deleted 290 lines changed or added

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