draft-ietf-rtgwg-mrt-frr-algorithm-05.txt   draft-ietf-rtgwg-mrt-frr-algorithm-06.txt 
Routing Area Working Group G. Enyedi, Ed. Routing Area Working Group G. Enyedi, Ed.
Internet-Draft A. Csaszar Internet-Draft A. Csaszar
Intended status: Standards Track Ericsson Intended status: Standards Track Ericsson
Expires: January 3, 2016 A. Atlas, Ed. Expires: April 17, 2016 A. Atlas, Ed.
C. Bowers C. Bowers
Juniper Networks Juniper Networks
A. Gopalan A. Gopalan
University of Arizona University of Arizona
July 2, 2015 October 15, 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-05 draft-ietf-rtgwg-mrt-frr-algorithm-06
Abstract Abstract
A complete solution for IP and LDP Fast-Reroute using Maximally A complete solution for IP and LDP Fast-Reroute using Maximally
Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr- Redundant Trees is presented in [I-D.ietf-rtgwg-mrt-frr-
architecture]. This document defines the associated MRT Lowpoint architecture]. This document defines the associated MRT Lowpoint
algorithm that is used in the default MRT profile to compute both the algorithm that is used in the default MRT profile to compute both the
necessary Maximally Redundant Trees with their associated next-hops necessary Maximally Redundant Trees with their associated next-hops
and the alternates to select for MRT-FRR. and the alternates to select for MRT-FRR.
skipping to change at page 1, line 41 skipping to change at page 1, line 41
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 3, 2016. This Internet-Draft will expire on April 17, 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 32 skipping to change at page 2, line 32
4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17 4.5. Determining Local-Root and Assigning Block-ID . . . . . . 17
5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19 5. Algorithm Sections . . . . . . . . . . . . . . . . . . . . . 19
5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19 5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 19
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22 5.2. MRT Island Identification . . . . . . . . . . . . . . . . 22
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23 5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 23
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23 5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 23
5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint
inheritance . . . . . . . . . . . . . . . . . . . . . . . 24 inheritance . . . . . . . . . . . . . . . . . . . . . . . 24
5.6. Augmenting the GADAG by directing all links . . . . . . . 26 5.6. Augmenting the GADAG by directing all links . . . . . . . 26
5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30 5.7. Compute MRT next-hops . . . . . . . . . . . . . . . . . . 30
5.7.1. MRT next-hops to all nodes partially ordered with 5.7.1. MRT next-hops to all nodes ordered with respect to
respect to the computing node . . . . . . . . . . . . 30 the computing node . . . . . . . . . . . . . . . . . 30
5.7.2. MRT next-hops to all nodes not partially ordered with 5.7.2. MRT next-hops to all nodes not ordered with respect
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 FRR Next-Hops for Proxy-Nodes . . . . . . . . . . 42 5.9. Finding MRT Next-Hops for Proxy-Nodes . . . . . . . . . . 44
6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 45 6. MRT Lowpoint Algorithm: Next-hop conformance . . . . . . . . 58
7. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 45 7. Broadcast interfaces . . . . . . . . . . . . . . . . . . . . 58
8. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 66 7.1. Computing MRT next-hops on broadcast networks . . . . . . 59
8.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 66 7.2. Using MRT next-hops as alternates in the event of
9. Implementation Status . . . . . . . . . . . . . . . . . . . . 76 failures on broadcast networks . . . . . . . . . . . . . 60
10. Algorithm Work to Be Done . . . . . . . . . . . . . . . . . . 76 8. Python Implementation of MRT Lowpoint Algorithm . . . . . . . 61
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 76 9. Algorithm Alternatives and Evaluation . . . . . . . . . . . . 102
12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 76 9.1. Algorithm Evaluation . . . . . . . . . . . . . . . . . . 102
13. Security Considerations . . . . . . . . . . . . . . . . . . . 76 10. Implementation Status . . . . . . . . . . . . . . . . . . . . 112
14. References . . . . . . . . . . . . . . . . . . . . . . . . . 76 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 112
14.1. Normative References . . . . . . . . . . . . . . . . . . 76 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 112
14.2. Informative References . . . . . . . . . . . . . . . . . 77 13. Security Considerations . . . . . . . . . . . . . . . . . . . 112
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 79 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 112
Appendix B. Option 3: Computing GADAG using a hybrid method . . 84 14.1. Normative References . . . . . . . . . . . . . . . . . . 112
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 86 14.2. Informative References . . . . . . . . . . . . . . . . . 112
Appendix A. Option 2: Computing GADAG using SPFs . . . . . . . . 115
Appendix B. Option 3: Computing GADAG using a hybrid method . . 120
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 122
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 5, line 15 skipping to change at page 5, line 15
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 pseudo-node representation (e.g. in OSPF, transformed into a pseudonode representation (e.g. in OSPF,
viewing a Network LSA as representing a pseudo-noe). 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
from the same node X to the root along the second tree. These can from the same node X to the root along the second tree. These can
be computed in 2-connected graphs. be computed in 2-connected graphs.
Maximally Redundant Trees (MRT): A pair of trees where the path Maximally Redundant Trees (MRT): A pair of trees where the path
from any node X to the root R along the first tree and the path from any node X to the root R along the first tree and the path
from the same node X to the root along the second tree share the from the same node X to the root along the second tree share the
minimum number of nodes and the minimum number of links. Each minimum number of nodes and the minimum number of links. Each
skipping to change at page 22, line 9 skipping to change at page 22, line 9
+--------------+-----------------------+-----------------------------+ +--------------+-----------------------+-----------------------------+
Figure 15: value of interface.neighbor.mrt_node_id and Figure 15: value of interface.neighbor.mrt_node_id and
interface.metric to be used for ranking interfaces, for different interface.metric to be used for ranking interfaces, for different
flooding protocols and applications flooding protocols and applications
The metrics are unsigned integers and MUST be compared as unsigned The metrics are unsigned integers and MUST be compared as unsigned
integers. The results of mrt_node_id comparisons MUST be the same as integers. The results of mrt_node_id comparisons MUST be the same as
would be obtained by converting the mrt_node_ids to unsigned integers would be obtained by converting the mrt_node_ids to unsigned integers
using network byte order and performing the comparison as unsigned using network byte order and performing the comparison as unsigned
integers. Also note that these values are only specified in the case integers. In the case of IS-IS for IP/LDP FRR with point-to-point
of point-to-point links. Therefore, in the case of IS-IS for IP/LDP links, the pseudonode number (the 7th octet) is zero. Broadcast
FRR, the pseudonode number (the 7th octet) will always be zero. interfaces will be discussed in Section 7.
In the case of IS-IS for IP/LDP FRR, this specification allows for In the case of IS-IS for IP/LDP FRR, this specification allows for
the use of Multi-Topology routing. [RFC5120] requires that the use of Multi-Topology routing. [RFC5120] requires that
information related to the standard/default topology (MT-ID = 0) be information related to the standard/default topology (MT-ID = 0) be
carried in the Extended IS Reachability TLV #22, while it requires carried in the Extended IS Reachability TLV #22, while it requires
that the Multi-Topology IS Neighbor TLV #222 only be used to carry that the Multi-Topology IS Neighbor TLV #222 only be used to carry
topology information related to non-default topologies (with non-zero topology information related to non-default topologies (with non-zero
MT-IDs). [RFC5120] enforces this by requiring an implementation to MT-IDs). [RFC5120] enforces this by requiring an implementation to
ignore TLV#222 with MT-ID = 0. The current document also requires ignore TLV#222 with MT-ID = 0. The current document also requires
that TLV#222 with MT-ID = 0 MUST be ignored. that TLV#222 with MT-ID = 0 MUST be ignored.
skipping to change at page 22, line 41 skipping to change at page 22, line 41
of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions
of these criteria. of these criteria.
MRT_Island_Identification(topology, computing_rtr, profile_id, area) MRT_Island_Identification(topology, computing_rtr, profile_id, area)
for all routers in topology for all routers in topology
rtr.IN_MRT_ISLAND = FALSE rtr.IN_MRT_ISLAND = FALSE
computing_rtr.IN_MRT_ISLAND = TRUE computing_rtr.IN_MRT_ISLAND = TRUE
explore_list = { computing_rtr } explore_list = { computing_rtr }
while (explore_list is not empty) while (explore_list is not empty)
next_rtr = remove_head(explore_list) next_rtr = remove_head(explore_list)
for each interface in next_rtr for each intf in next_rtr
if interface is (not MRT-ineligible and not IGP-excluded if (not intf.MRT-ineligible
and in area) and not intf.remote_intf.MRT-ineligible
if ((interface.remote_node supports profile_id) and and not intf.IGP-excluded and (intf in area)
(interface.remote_node.IN_MRT_ISLAND is FALSE)) and (intf.remote_node supports profile_id) )
interface.remote_node.IN_MRT_ISLAND = TRUE intf.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, interface.remote_node) intf.remote_node.IN_MRT_ISLAND = TRUE
if (not intf.remote_node.IN_MRT_ISLAND))
intf.remote_node.IN_MRT_ISLAND = TRUE
add_to_tail(explore_list, intf.remote_node)
Figure 16: MRT Island Identification Figure 16: MRT Island Identification
5.3. GADAG Root Selection 5.3. GADAG Root Selection
In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG
Root Selection Policy is described for the MRT default profile. In Root Selection Policy is described for the MRT default profile. In
[I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for [I-D.ietf-ospf-mrt] and [I-D.ietf-isis-mrt], a mechanism is given for
routers to advertise the GADAG Root Selection Priority and routers to advertise the GADAG Root Selection Priority and
consistently select a GADAG Root inside the local MRT Island. The consistently select a GADAG Root inside the local MRT Island. The
MRT Lowpoint algorithm simply requires that all routers in the MRT MRT Lowpoint algorithm simply requires that all routers in the MRT
Island MUST select the same GADAG Root; the mechanism can vary based Island MUST select the same GADAG Root; the mechanism can vary based
upon the MRT profile description. Before beginning computation, the upon the MRT profile description. Before beginning computation, the
network graph is reduced to contain only the set of routers that network graph is reduced to contain only the set of routers that
support the specific MRT profile whose MRTs are being computed. support the specific MRT profile whose MRTs are being computed.
As noted in Section 7, pseudonodes MUST NOT be considered for GADAG
root selection.
Analysis has shown that the centrality of a router can have a Analysis has shown that the centrality of a router can have a
significant impact on the lengths of the alternate paths computed. significant impact on the lengths of the alternate paths computed.
Therefore, it is RECOMMENDED that off-line analysis that considers Therefore, it is RECOMMENDED that off-line analysis that considers
the centrality of a router be used to help determine how good a the centrality of a router be used to help determine how good a
choice a particular router is for the role of GADAG root. choice a particular router is for the role of GADAG root.
5.4. Initialization 5.4. Initialization
Before running the algorithm, there is the standard type of Before running the algorithm, there is the standard type of
initialization to be done, such as clearing any computed DFS-values, initialization to be done, such as clearing any computed DFS-values,
skipping to change at page 23, line 46 skipping to change at page 23, line 49
they are OUTGOING, INCOMING or both is determined when the GADAG is they are OUTGOING, INCOMING or both is determined when the GADAG is
constructed and augmented. constructed and augmented.
It is possible that some links and nodes will be marked as unusable It is possible that some links and nodes will be marked as unusable
using standard IGP mechanisms (see section 7 of using standard IGP mechanisms (see section 7 of
[I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability [I-D.ietf-rtgwg-mrt-frr-architecture]). Due to FRR manageability
considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be considerations [I-D.ietf-rtgwg-lfa-manageability], it may also be
desirable to administratively configure some interfaces as ineligible desirable to administratively configure some interfaces as ineligible
to carry MRT FRR traffic. This constraint MUST be consistently to carry MRT FRR traffic. This constraint MUST be consistently
flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the flooded via the IGP [I-D.ietf-ospf-mrt] [I-D.ietf-isis-mrt] by the
owner of the interface, so that links are clearly known to be MRT- owner of the interface, so that links are known to be MRT-ineligible
ineligible and not explored or used in the MRT algorithm. In the and not explored or used in the MRT algorithm. When a either
algorithm description, it is assumed that such links and nodes will interface on a link is advertised as MRT-ineligible, the link MUST
not be explored or used, and no more discussion is given of this NOT be included in the MRT Island, and will thus be excluded from the
restriction. GADAG. Computation of MRT next-hops will therefore not use any MRT-
ineligible links. The MRT algorithm does still need to consider MRT-
ineligible links when computing FRR alternates, because an MRT-
ineligible link can still be the shortest-path next-hop to reach a
destination.
When a broadcast interface is advertised as MRT-ineligible, then the
pseudo-node representing the entire broadcast network MUST NOT be
included in the MRT Island. This is equivalent to excluding all of
the broadcast interfaces on that broadcast network from the MRT
Island.
5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance 5.5. MRT Lowpoint Algorithm: Computing GADAG using lowpoint inheritance
As discussed in Section 4.2, it is necessary to find ears from a node As discussed in Section 4.2, it is necessary to find ears from a node
x that is already in the GADAG (known as IN_GADAG). Two different x that is already in the GADAG (known as IN_GADAG). Two different
methods are used to find ears in the algorithm. The first is by methods are used to find ears in the algorithm. The first is by
going to a not IN_GADAG DFS-child and then following the chain of going to a not IN_GADAG DFS-child and then following the chain of
low-point parents until an IN_GADAG node is found. The second is by low-point parents until an IN_GADAG node is found. The second is by
going to a not IN_GADAG neighbor and then following the chain of DFS going to a not IN_GADAG neighbor and then following the chain of DFS
parents until an IN_GADAG node is found. As an ear is found, the parents until an IN_GADAG node is found. As an ear is found, the
skipping to change at page 27, line 13 skipping to change at page 27, line 25
undirected link in question has another parallel link between the undirected link in question has another parallel link between the
same two nodes that is already directed, then the direction of the same two nodes that is already directed, then the direction of the
undirected link can be inherited from the previously directed link. undirected link can be inherited from the previously directed link.
In the case of parallel cut links, we set all of the parallel links In the case of parallel cut links, we set all of the parallel links
to both INCOMING and OUTGOING. Otherwise, the undirected link in to both INCOMING and OUTGOING. Otherwise, the undirected link in
question is set to OUTGOING from the block root node. A cut-link can question is set to OUTGOING from the block root node. A cut-link can
then be identified by the fact that it will be directed both INCOMING then be identified by the fact that it will be directed both INCOMING
and OUTGOING in the GADAG. The exact details of this whole process and OUTGOING in the GADAG. The exact details of this whole process
are captured in Figure 18 are captured in Figure 18
Add_Undirected_Block_Root_Links(topo, gadag_root): Add_Undirected_Block_Root_Links(topo, gadag_root)
foreach node x in topo foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x foreach interface i of x
if (i.remote_node.localroot is not x if (i.remote_node.localroot is not x
or i.PROCESSED ) or i.PROCESSED )
continue continue
Initialize bundle_list to empty Initialize bundle_list to empty
bundle.UNDIRECTED = true bundle.UNDIRECTED = true
bundle.OUTGOING = false bundle.OUTGOING = false
bundle.INCOMING = false bundle.INCOMING = false
skipping to change at page 28, line 22 skipping to change at page 28, line 33
i3.remote_intf.INCOMING = true i3.remote_intf.INCOMING = true
else if bundle.INCOMING else if bundle.INCOMING
foreach interface i3 in bundle_list foreach interface i3 in bundle_list
i3.UNDIRECTED = false i3.UNDIRECTED = false
i3.remote_intf.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false
i3.PROCESSED = true i3.PROCESSED = true
i3.remote_intf.PROCESSED = true i3.remote_intf.PROCESSED = true
i3.INCOMING = true i3.INCOMING = true
i3.remote_intf.OUTGOING = true i3.remote_intf.OUTGOING = true
Modify_Block_Root_Incoming_Links(topo, gadag_root): Modify_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x foreach interface i of x
if i.remote_node.localroot is x if i.remote_node.localroot is x
if i.INCOMING: if i.INCOMING:
i.INCOMING = false i.INCOMING = false
i.INCOMING_STORED = true i.INCOMING_STORED = true
i.remote_intf.OUTGOING = false i.remote_intf.OUTGOING = false
i.remote_intf.OUTGOING_STORED = true i.remote_intf.OUTGOING_STORED = true
Revert_Block_Root_Incoming_Links(topo, gadag_root): Revert_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo foreach node x in topo
if x.IS_CUT_VERTEX or x is gadag_root if x.IS_CUT_VERTEX or x is gadag_root
foreach interface i of x foreach interface i of x
if i.remote_node.localroot is x if i.remote_node.localroot is x
if i.INCOMING_STORED: if i.INCOMING_STORED
i.INCOMING = true i.INCOMING = true
i.remote_intf.OUTGOING = true i.remote_intf.OUTGOING = true
i.INCOMING_STORED = false i.INCOMING_STORED = false
i.remote_intf.OUTGOING_STORED = false i.remote_intf.OUTGOING_STORED = false
Run_Topological_Sort_GADAG(topo, gadag_root): Run_Topological_Sort_GADAG(topo, gadag_root)
Modify_Block_Root_Incoming_Links(topo, gadag_root) Modify_Block_Root_Incoming_Links(topo, gadag_root)
foreach node x in topo: foreach node x in topo
node.unvisited = 0 node.unvisited = 0
foreach interface i of x: foreach interface i of x
if (i.INCOMING): if (i.INCOMING)
node.unvisited += 1 node.unvisited += 1
Initialize working_list to empty Initialize working_list to empty
Initialize topo_order_list to empty Initialize topo_order_list to empty
add_to_list_end(working_list, gadag_root) add_to_list_end(working_list, gadag_root)
while working_list is not empty while working_list is not empty
y = remove_start_item_from_list(working_list) y = remove_start_item_from_list(working_list)
add_to_list_end(topo_order_list, y) add_to_list_end(topo_order_list, y)
foreach ordered_interface i of y foreach ordered_interface i of y
if intf.OUTGOING if intf.OUTGOING
i.remote_node.unvisited -= 1 i.remote_node.unvisited -= 1
if i.remote_node.unvisited is 0 if i.remote_node.unvisited is 0
add_to_list_end(working_list, i.remote_node) add_to_list_end(working_list, i.remote_node)
next_topo_order = 1 next_topo_order = 1
while topo_order_list is not empty while topo_order_list is not empty
y = remove_start_item_from_list(topo_order_list) y = remove_start_item_from_list(topo_order_list)
y.topo_order = next_topo_order y.topo_order = next_topo_order
next_topo_order += 1 next_topo_order += 1
Revert_Block_Root_Incoming_Links(topo, gadag_root) Revert_Block_Root_Incoming_Links(topo, gadag_root)
def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): def Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
foreach node x in topo foreach node x in topo
foreach interface i of x foreach interface i of x
if i.UNDIRECTED: if i.UNDIRECTED:
if x.topo_order < i.remote_node.topo_order if x.topo_order < i.remote_node.topo_order
i.OUTGOING = true i.OUTGOING = true
i.UNDIRECTED = false i.UNDIRECTED = false
i.remote_intf.INCOMING = true i.remote_intf.INCOMING = true
i.remote_intf.UNDIRECTED = false i.remote_intf.UNDIRECTED = false
else else
i.INCOMING = true i.INCOMING = true
skipping to change at page 30, line 28 skipping to change at page 30, line 38
decreasing-SPF) can be used to find the increasing and decreasing decreasing-SPF) can be used to find the increasing and decreasing
paths. Second, if two nodes X and Y aren't ordered with respect to paths. Second, if two nodes X and Y aren't ordered with respect to
each other in the partial order, then intermediary nodes can be used each other in the partial order, then intermediary nodes can be used
to create the paths by increasing/decreasing to the intermediary and to create the paths by increasing/decreasing to the intermediary and
then decreasing/increasing to reach Y. then decreasing/increasing to reach Y.
As usual, the two basic ideas will be discussed assuming the network As usual, the two basic ideas will be discussed assuming the network
is two-connected. The generalization to multiple blocks is discussed is two-connected. The generalization to multiple blocks is discussed
in Section 5.7.4. The full algorithm is given in Section 5.7.5. in Section 5.7.4. The full algorithm is given in Section 5.7.5.
5.7.1. MRT next-hops to all nodes partially ordered with respect to the 5.7.1. MRT next-hops to all nodes ordered with respect to the computing
computing node node
To find two node-disjoint paths from the computing router X to any To find two node-disjoint paths from the computing router X to any
node Y, depends upon whether Y >> X or Y << X. As shown in node Y, depends upon whether Y >> X or Y << X. As shown in
Figure 19, if Y >> X, then there is an increasing path that goes from Figure 19, if Y >> X, then there is an increasing path that goes from
X to Y without crossing R; this contains nodes in the interval [X,Y]. X to Y without crossing R; this contains nodes in the interval [X,Y].
There is also a decreasing path that decreases towards R and then There is also a decreasing path that decreases towards R and then
decreases from R to Y; this contains nodes in the interval decreases from R to Y; this contains nodes in the interval
[X,R-small] or [R-great,Y]. The two paths cannot have common nodes [X,R-small] or [R-great,Y]. The two paths cannot have common nodes
other than X and Y. other than X and Y.
skipping to change at page 31, line 22 skipping to change at page 31, line 33
| ^ | ^
| | | |
V | V |
(Cloud 3)--->[R]--->(Cloud 1) (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Blue path: X->Cloud 3->R->Cloud 1->Y
MRT-Red path: X->Cloud 2->Y MRT-Red path: X->Cloud 2->Y
Figure 20: Y << X Figure 20: Y << X
5.7.2. MRT next-hops to all nodes not partially ordered with respect to 5.7.2. MRT next-hops to all nodes not ordered with respect to the
the computing node computing node
When X and Y are not ordered, the first path should increase until we When X and Y are not ordered, the first path should increase until we
get to a node G, where G >> Y. At G, we need to decrease to Y. The get to a node G, where G >> Y. At G, we need to decrease to Y. The
other path should be just the opposite: we must decrease until we get other path should be just the opposite: we must decrease until we get
to a node H, where H << Y, and then increase. Since R is smaller and to a node H, where H << Y, and then increase. Since R is smaller and
greater than Y, such G and H must exist. It is also easy to see that greater than Y, such G and H must exist. It is also easy to see that
these two paths must be node disjoint: the first path contains nodes these two paths must be node disjoint: the first path contains nodes
in interval [X,G] and [Y,G], while the second path contains nodes in in interval [X,G] and [Y,G], while the second path contains nodes in
interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is interval [H,X] and [H,Y]. This is illustrated in Figure 21. It is
necessary to decrease and then increase for the MRT-Blue and increase necessary to decrease and then increase for the MRT-Blue and increase
skipping to change at page 33, line 32 skipping to change at page 33, line 32
increasing MRT-Blue next-hop for a node which is not ordered with increasing MRT-Blue next-hop for a node which is not ordered with
respect to X is the next-hop along the decreasing MRT-Red towards R, respect to X is the next-hop along the decreasing MRT-Red towards R,
and the decreasing MRT-Red next-hop is the next-hop along the and the decreasing MRT-Red next-hop is the next-hop along the
increasing MRT-Blue towards R. Naturally, since R is ordered with increasing MRT-Blue towards R. Naturally, since R is ordered with
respect to all the nodes, there will always be an increasing and a respect to all the nodes, there will always be an increasing and a
decreasing path towards it. This algorithm does not provide the decreasing path towards it. This algorithm does not provide the
complete specific path taken but just the appropriate next-hops to complete specific path taken but just the appropriate next-hops to
use. The identities of G and H are not determined by the computing use. The identities of G and H are not determined by the computing
node X. node X.
The final case to considered is when the root R computes its own The final case to consider is when the GADAG root R computes its own
next-hops. Since the root R is << all other nodes, running an next-hops. Since the GADAG root R is << all other nodes, running an
increasing-SPF rooted at R will reach all other nodes; the MRT-Blue increasing-SPF rooted at R will reach all other nodes; the MRT-Blue
next-hops are those found with this increasing-SPF. Similarly, since next-hops are those found with this increasing-SPF. Similarly, since
the root R is >> all other nodes, running a decreasing-SPF rooted at the GADAG root R is >> all other nodes, running a decreasing-SPF
R will reach all other nodes; the MRT-Red next-hops are those found rooted at R will reach all other nodes; the MRT-Red next-hops are
with this decreasing-SPF. those found with this decreasing-SPF.
E---D---| E<--D<--| E---D---| E<--D<--|
| | | | ^ | | | | | ^ |
| | | V | | | | | V | |
R F C R F C R F C R F C
| | | | ^ ^ | | | | ^ ^
| | | V | | | | | V | |
A---B---| A-->B---| A---B---| A-->B---|
(a) (b) (a) (b)
skipping to change at page 36, line 14 skipping to change at page 36, line 14
((direction is REVERSE) and intf.INCOMING) ) ((direction is REVERSE) and intf.INCOMING) )
and In_Common_Block(spf_root, intf.remote_node) ) and In_Common_Block(spf_root, intf.remote_node) )
path_metric = min_node.spf_metric + intf.metric path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric intf.remote_node.spf_metric = path_metric
if min_node is spf_root if min_node is spf_root
intf.remote_node.next_hops = make_list(intf) intf.remote_node.next_hops = make_list(intf)
else else
intf.remote_node.next_hops = min_node.next_hops intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node) insert_or_update(spf_heap, intf.remote_node)
else if path_metric is intf.remote_node.spf_metric else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf) add_to_list(intf.remote_node.next_hops, intf)
else else
add_list_to_list(intf.remote_node.next_hops, add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops) min_node.next_hops)
SetEdge(y) SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty if y.blue_next_hops is empty and y.red_next_hops is empty
SetEdge(y.localroot) SetEdge(y.localroot)
y.blue_next_hops = y.localroot.blue_next_hops y.blue_next_hops = y.localroot.blue_next_hops
skipping to change at page 37, line 6 skipping to change at page 37, line 6
(y.block_id is x.block_id) ) (y.block_id is x.block_id) )
if y.higher if y.higher
y.red_next_hops = x.localroot.red_next_hops y.red_next_hops = x.localroot.red_next_hops
else if y.lower else if y.lower
y.blue_next_hops = x.localroot.blue_next_hops y.blue_next_hops = x.localroot.blue_next_hops
else else
y.blue_next_hops = x.localroot.red_next_hops y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_next_hops y.red_next_hops = x.localroot.blue_next_hops
// Inherit next-hops and order_proxies to other components // Inherit next-hops and order_proxies to other components
if x is not gadag_root if (x is not gadag_root) and (x.localroot is not gadag_root)
gadag_root.blue_next_hops = x.localroot.blue_next_hops gadag_root.blue_next_hops = x.localroot.blue_next_hops
gadag_root.red_next_hops = x.localroot.red_next_hops gadag_root.red_next_hops = x.localroot.red_next_hops
gadag_root.order_proxy = x.localroot gadag_root.order_proxy = x.localroot
foreach node y foreach node y
if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND
SetEdge(y) SetEdge(y)
max_block_id = 0 max_block_id = 0
Assign_Block_ID(gadag_root, max_block_id) Assign_Block_ID(gadag_root, max_block_id)
Compute_MRT_NextHops(x, gadag_root) Compute_MRT_NextHops(x, gadag_root)
skipping to change at page 37, line 52 skipping to change at page 37, line 52
if D_higher and D_lower if D_higher and D_lower
if F.HIGHER and F.LOWER if F.HIGHER and F.LOWER
if F.topo_order < D_topo_order if F.topo_order < D_topo_order
return USE_RED return USE_RED
else else
return USE_BLUE return USE_BLUE
if F.HIGHER if F.HIGHER
return USE_RED return USE_RED
if F.LOWER if F.LOWER
return USE_BLUE return USE_BLUE
//F unordered wrt S
return USE_RED_OR_BLUE
else if D_higher else if D_higher
if F.HIGHER and F.LOWER if F.HIGHER and F.LOWER
return USE_BLUE return USE_BLUE
if F.LOWER if F.LOWER
return USE_BLUE return USE_BLUE
if F.HIGHER if F.HIGHER
if (F.topo_order > D_topo_order) if (F.topo_order > D_topo_order)
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
//F unordered wrt S
return USE_RED_OR_BLUE
else if D_lower else if D_lower
if F.HIGHER and F.LOWER if F.HIGHER and F.LOWER
return USE_RED return USE_RED
if F.HIGHER if F.HIGHER
return USE_RED return USE_RED
if F.LOWER if F.LOWER
if F.topo_order > D_topo_order if F.topo_order > D_topo_order
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
//F unordered wrt S
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 case should not occur 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
//primary_intf not in GADAG
return USE_RED
if F.LOWER if F.LOWER
return USE_RED return USE_RED
if F.HIGHER if F.HIGHER
return USE_BLUE return USE_BLUE
//F unordered wrt S
if F.topo_order > D_topo_order:
return USE_BLUE
else:
return USE_RED
Select_Alternates(D, F, primary_intf) Select_Alternates(D, F, primary_intf)
if not In_Common_Block(F, S)
return PRIM_NH_IN_DIFFERENT_BLOCK
if (D is F) or (D.order_proxy is F) if (D is F) or (D.order_proxy is F)
return PRIM_NH_IS_D_OR_OP_FOR_D return PRIM_NH_IS_D_OR_OP_FOR_D
D_lower = D.order_proxy.LOWER D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf, return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order) D_lower, D_higher, D_topo_order)
Figure 24 Figure 24: Select_Alternates() and Select_Alternates_Internal()
It is useful to first handle the case where where F is also D, or F It is useful to first handle the case where where F is also D, or F
is the order proxy for D. In this case, only link protection is is the order proxy for D. In this case, only link protection is
possible. The MRT that doesn't use the failed primary next-hop is possible. The MRT that doesn't use the failed primary next-hop is
used. If both MRTs use the primary next-hop, then the primary next- used. If both MRTs use the primary next-hop, then the primary next-
hop must be a cut-link, so either MRT could be used but the set of hop must be a cut-link, so either MRT could be used but the set of
MRT next-hops must be pruned to avoid the failed primary next-hop MRT next-hops must be pruned to avoid the failed primary next-hop
interface. To indicate this case, Select_Alternates returns interface. To indicate this case, Select_Alternates returns
PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode to handle the three PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudo-code to handle the three
sub-cases above is not provided. sub-cases above is not provided.
The logic behind Select_Alternates_Internal is described in The logic behind Select_Alternates_Internal is described in
Figure 25. As an example, consider the first case described in the Figure 25. As an example, consider the first case described in the
table, where the D>>S and D<<S. If this is true, then either S or D table, where the D>>S and D<<S. If this is true, then either S or D
must be the block root, R. If F>>S and F<<S, then S is the block must be the block root, R. If F>>S and F<<S, then S is the block
root. So the blue path from S to D is the increasing path to D, and root. So the blue path from S to D is the increasing path to D, and
the red path S to D is the decreasing path to D. If the the red path S to D is the decreasing path to D. If the
F.topo_order<D.topo_order, then either F is ordered higher than D or F.topo_order<D.topo_order, then either F is ordered higher than D or
F is unordered with respect to D. Therefore, F is either on a F is unordered with respect to D. Therefore, F is either on a
skipping to change at page 40, line 13 skipping to change at page 40, line 31
| D<<S,| path to R. | | not needed | path from | F | | D<<S,| path to R. | | not needed | path from | F |
| D is | Red path: | | | S to R | | | D is | Red path: | | | S to R | |
| R, | Decreasing +------+-----------------+------------+------------+ | R, | Decreasing +------+-----------------+------------+------------+
| | path to R. | F<<S | additional | F on a | Use Blue | | | path to R. | F<<S | additional | F on a | Use Blue |
| | | only | criteria | decreasing | to avoid | | | | only | criteria | decreasing | to avoid |
| | | | not needed | path from | F | | | | | not needed | path from | F |
| or | | | | S to R | | | or | | | | S to R | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F>>S | topo(F)>topo(D) | F on a | Use Blue | | | | F>>S | topo(F)>topo(D) | F on a | Use Blue |
| S is | Blue path: | and | implies that | decreasing | to avoid | | S is | Blue path: | and | implies that | decreasing | to avoid |
| R | Increasing | F<<S | F>>D or F??D | path from | F | | R | Increasing | F<<S,| F>>D or F??D | path from | F |
| | path to D. | | | S to D or | | | | path to D. | F is | | S to D or | |
| | Red path: | | | neither | | | | Red path: | R | | neither | |
| | Decreasing | +-----------------+------------+------------+ | | Decreasing | +-----------------+------------+------------+
| | path to D. | | topo(F)<topo(D) | F on an | Use Red | | | path to D. | | topo(F)<topo(D) | F on an | Use Red |
| | | | implies that | increasing | to avoid | | | | | implies that | increasing | to avoid |
| | | | F<<D or F??D | path from | F | | | | | F<<D or F??D | path from | F |
| | | | | S to D or | | | | | | | S to D or | |
| | | | | neither | | | | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F??S | Can only occur | F is on | Use Red |
| | | | when link | neither | or Blue |
| | | | between | increasing | to avoid |
| | | | F and S | nor decr. | F |
| | | | is marked | path from | |
| | | | MRT_INELIGIBLE | S to D or R| |
+------+------------+------+-----------------+------------+------------+ +------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F<<S | additional | F on | Use Blue | | D>>S | Blue path: | F<<S | additional | F on | Use Blue |
| only | Increasing | only | criteria | decreasing | to avoid | | only | Increasing | only | criteria | decreasing | to avoid |
| | shortest | | not needed | path from | F | | | shortest | | not needed | path from | F |
| | path from | | | S to R | | | | path from | | | S to R | |
| | S to D. +------+-----------------+------------+------------+ | | S to D. +------+-----------------+------------+------------+
| | Red path: | F>>S | topo(F)>topo(D) | F on | Use Blue | | | Red path: | F>>S | topo(F)>topo(D) | F on | Use Blue |
| | Decreasing | only | implies that | decreasing | to avoid | | | Decreasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F | | | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | | | | path from | | | R to D | |
skipping to change at page 40, line 47 skipping to change at page 41, line 24
| | R to D. | | F<<D or F??D | path from | F | | | R to D. | | F<<D or F??D | path from | F |
| | | | | S to D | | | | | | | S to D | |
| | | | | or | | | | | | | or | |
| | | | | neither | | | | | | | neither | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Red | Use Blue | | | | F>>S | additional | F on Red | Use Blue |
| | | and | criteria | | to avoid | | | | and | criteria | | to avoid |
| | | F<<S,| not needed | | F | | | | F<<S,| not needed | | F |
| | | F is | | | | | | | F is | | | |
| | | R | | | | | | | R | | | |
| | +------+-----------------+------------+------------+
| | | F??S | Can only occur | F is on | Use Red |
| | | | when link | neither | or Blue |
| | | | between | increasing | to avoid |
| | | | F and S | nor decr. | F |
| | | | is marked | path from | |
| | | | MRT_INELIGIBLE | S to D or R| |
+------+------------+------+-----------------+------------+------------+ +------+------------+------+-----------------+------------+------------+
| D<<S | Blue path: | F>>S | additional | F on | Use Red | | D<<S | Blue path: | F>>S | additional | F on | Use Red |
| only | Increasing | only | criteria | increasing | to avoid | | only | Increasing | only | criteria | increasing | to avoid |
| | shortest | | not needed | path from | F | | | shortest | | not needed | path from | F |
| | path from | | | S to R | | | | path from | | | S to R | |
| | S to R, +------+-----------------+------------+------------+ | | S to R, +------+-----------------+------------+------------+
| | then | F<<S | topo(F)>topo(D) | F on | Use Blue | | | then | F<<S | topo(F)>topo(D) | F on | Use Blue |
| | increasing | only | implies that | decreasing | to avoid | | | increasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F | | | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | | | | path from | | | R to D | |
skipping to change at page 41, line 24 skipping to change at page 42, line 8
| | S to D. | | F<<D or F??D | path from | F | | | S to D. | | F<<D or F??D | path from | F |
| | | | | S to D | | | | | | | S to D | |
| | | | | or | | | | | | | or | |
| | | | | neither | | | | | | | neither | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Blue | Use Red | | | | F>>S | additional | F on Blue | Use Red |
| | | and | criteria | | to avoid | | | | and | criteria | | to avoid |
| | | F<<S,| not | | F | | | | F<<S,| not | | F |
| | | F is | needed | | | | | | F is | needed | | |
| | | R | | | | | | | R | | | |
| | +------+-----------------+------------+------------+
| | | F??S | Can only occur | F is on | Use Red |
| | | | when link | neither | or Blue |
| | | | between | increasing | to avoid |
| | | | F and S | nor decr. | F |
| | | | is marked | path from | |
| | | | MRT_INELIGIBLE | S to D or R| |
+------+------------+------+-----------------+------------+------------+ +------+------------+------+-----------------+------------+------------+
| D??S | Blue path: | F<<S | additional | F on a | Use Red | | D??S | Blue path: | F<<S | additional | F on a | Use Red |
| | Decr. from | only | criteria | decreasing | to avoid | | | Decr. from | only | criteria | decreasing | to avoid |
| | S to first | | not needed | path from | F | | | S to first | | not needed | path from | F |
| | node H>>D, | | | S to H. | | | | node K<<D, | | | S to K. | |
| | then incr. +------+-----------------+------------+------------+ | | then incr. +------+-----------------+------------+------------+
| | to D. | F>>S | additional | F on an | Use Blue | | | to D. | F>>S | additional | F on an | Use Blue |
| | Red path: | only | criteria | increasing | to avoid | | | Red path: | only | criteria | increasing | to avoid |
| | Incr. from | | not needed | path from | F | | | Incr. from | | not needed | path from | F |
| | S to first | | | S to G | | | | S to first | | | S to L | |
| | node G<<D, | | | | | | | node L>>D, | | | | |
| | then decr. | | | | | | | then decr. | | | | |
| | +------+-----------------+------------+------------+ | | +------+-----------------+------------+------------+
| | | F??S | F<-->S link is | | |
| | | | MRT_INELIGIBLE | | |
| | | +-----------------+------------+------------+
| | | | topo(F)>topo(D) | F on decr. | Use Blue |
| | | | implies that | path from | to avoid |
| | | | F>>D or F??D | L to D or | F |
| | | | | neither | |
| | | +-----------------+------------+------------+
| | | | topo(F)<topo(D) | F on incr. | Use Red |
| | | | implies that | path from | to avoid |
| | | | F<<D or F??D | K to D or | F |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | GADAG link | F on an | Use Blue | | | | F>>S | GADAG link | F on an | Use Blue |
| | | and | direction | incr. path | to avoid | | | | and | direction | incr. path | to avoid |
| | | F<<S,| S->F | from S | F | | | | F<<S,| S->F | from S | F |
| | | F is +-----------------+------------+------------+ | | | F is +-----------------+------------+------------+
| | | R | GADAG link | F on a | Use Red | | | | R | GADAG link | F on a | Use Red |
| | | | direction | decr. path | to avoid | | | | | direction | decr. path | to avoid |
| | | | S<-F | from S | F | | | | | S<-F | from S | F |
| | | +-----------------+------------+------------+ | | | +-----------------+------------+------------+
| | | | GADAG link | Implies F is the order | | | | | GADAG link | Either F is the order |
| | | | direction | proxy for D, which has | | | | | direction | proxy for D (case |
| | | | S<-->F | already been handled. | | | | | S<-->F | already handled) or D |
+------+------------+------+-----------------+------------+------------+ | | | | | is in a different block |
| | | | | from F, in which case |
| | | | | Red or Blue avoids F |
| | | +-----------------+-------------------------+
| | | | S-F link not | Relies on special |
| | | | in GADAG, | construction of GADAG |
| | | | only when | to demonstrate that |
| | | | S-F link is | using Red avoids F |
| | | | MRT_INELIGIBLE | (see text) |
+------+------------+------+-----------------+-------------------------+
Figure 25: determining MRT next-hops and alternates based on the Figure 25: determining MRT next-hops and alternates based on the
partial order and topological sort relationships between the partial order and topological sort relationships between the
source(S), destination(D), primary next-hop(F), and block root(R). source(S), destination(D), primary next-hop(F), and block root(R).
topo(N) indicates the topological sort value of node N. X??Y topo(N) indicates the topological sort value of node N. X??Y
indicates that node X is unordered with respect to node Y. It is indicates that node X is unordered with respect to node Y. It is
assumed that the case where F is D, or where F is the order proxy for assumed that the case where F is D, or where F is the order proxy for
D, has already been handled. D, has already been handled.
As an example, consider the ADAG depicted in Figure 26 and first The last case in Figure 25 requires additional explanation. The fact
suppose that G is the source, D is the destination and H is the that the red path from S to D in this case avoids F relies on a
failed next-hop. Since D>>G, we need to compare H.topo_order and special property of the GADAGs that we have constructed in this
D.topo_order. Since D.topo_order>H.topo_order, D must be not smaller algorithm, a property not shared by all GADAGs in general. When D is
than H, so we should select the decreasing path towards the root. unordered with respect to S, and F is the localroot for S, it can
If, however, the destination were instead J, we must find that occur that the link between S and F is not in the GADAG only when
H.topo_order>J.topo_order, so we must choose the increasing Blue that link has been marked MRT_INELIGIBLE. For an arbitrary GADAG, S
next-hop to J, which is I. In the case, when instead the destination doesn't have enough information based on the computed order
is C, we find that we need to first decrease to avoid using H, so the relationships to determine if the red path or blue path will hit F
Blue, first decreasing then increasing, path is selected. (which is also the localroot) before hitting K or L, and making it
safely to D. However, the GADAGs that we construct using the
algorithm in this document are not arbitrary GADAGs. They have the
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
construction. This additional property guarantees that the red path
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
path ordered higher than D, which would in turn require the localroot
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
specially constructed GADAGs.
As an example of how to Select_Alternates_Internal() operates,
consider the ADAG depicted in Figure 26 and first suppose that G is
the source, D is the destination and H is the failed next-hop. Since
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
unordered with respect to H, so we should select the decreasing path
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
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
using H, so the Blue, first decreasing then increasing, path is
selected.
[E]<-[D]<-[H]<-[J] [E]<-[D]<-[H]<-[J]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[R] [C] [G]->[I] [R] [C] [G]->[I]
| ^ ^ ^ | ^ ^ ^
V | | | V | | |
[A]->[B]->[F]---| [A]->[B]->[F]---|
(a)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 FRR Next-Hops for Proxy-Nodes 5.9. Finding MRT Next-Hops for Proxy-Nodes
As discussed in Section 10.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 a named proxy-
nodes. An example 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.
A first incorrect and naive approach to handling proxy-nodes, which The proxy-node is connected to at most two nodes in the GADAG.
cannot be transited, is to simply add these proxy-nodes to the graph Section 11.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the
of the network and connect it to the routers through which the new proxy-node attachment routers MUST be determined. The degenerate
proxy-node can be reached. Unfortunately, this can introduce some case where the proxy-node is attached to only one node in the GADAG
new ordering between the border routers connected to the new node is trivial as all needed information can be derived from that proxy
which could result in routing MRT paths through the proxy-node. node attachment router. If there are multiple interfaces connecting
Thus, this naive approach would need to recompute GADAGs and redo the proxy node to the single proxy node attachment router, then some
SPTs for each proxy-node. canbe assigned to MRT-Red and others to MRT_Blue.
Instead of adding the proxy-node to the original network graph, each Now, consider the proxy-node P that is attached to two proxy-node
individual proxy-node can be individually added to the GADAG. The attachment routers. The pseudo-code for Select_Proxy_Node_NHs(P,S)
proxy-node is connected to at most two nodes in the GADAG. in Figure 27 specifies how a computing-router S MUST compute the MRT
Section 10.2 of [I-D.ietf-rtgwg-mrt-frr-architecture] defines how the red and blue next-hops to reach proxy-node P. The proxy-node
proxy-node attachments MUST be determined. The degenerate case where attachment router with the lower value of mrt_node_id (as defined in
the proxy-node is attached to only one node in the GADAG is trivial Figure 15) is assigned to X, and the other proxy-node attachment
as all needed information can be derived from that attachment node; router is assigned to Y. We will be using the relative order of X,Y,
if there are different interfaces, then some can be assigned to MRT- and S in the partial order defined by the GADAG to determine the MRT
Red and others to MRT_Blue. 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 all nodes with respect to S were already computed
in Compute_MRT_NextHops().
Now, consider the proxy-node that is attached to exactly two nodes in def Select_Proxy_Node_NHs(P,S):
the GADAG. Let the order_proxies of these nodes be A and B. Let the if P.pnar1.node.node_id < P.pnar2.node.node_id:
current node, where next-hop is just being calculated, be S. If one X = P.pnar1.node
of these two nodes A and B is the local root of S, let A=S.local_root Y = P.pnar2.node
and the other one be B. Otherwise, let A.topo_order < B.topo_order. else:
X = P.pnar2.node
Y = P.pnar1.node
P.pnar_X = X
P.pnar_Y = Y
A = X.order_proxy
B = Y.order_proxy
if (A is S.localroot
and B is S.localroot):
#print("1.0")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is S.localroot
and B is not S.localroot):
#print("2.0")
if B.LOWER:
#print("2.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if B.HIGHER:
#print("2.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("2.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is not S.localroot
and B is S.localroot):
#print("3.0")
if A.LOWER:
#print("3.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if A.HIGHER:
#print("3.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("3.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is not S.localroot
and B is not S.localroot):
#print("4.0")
if (S is A.localroot or S is B.localroot):
#print("4.05")
if A.topo_order < B.topo_order:
#print("4.05.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.05.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if A.LOWER:
#print("4.1")
if B.HIGHER:
#print("4.1.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if B.LOWER:
#print("4.1.2")
if A.topo_order < B.topo_order:
#print("4.1.2.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.1.2.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.1.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if A.HIGHER:
A valid GADAG was constructed. Instead doing an increasing-SPF and a #print("4.2")
decreasing-SPF to find ordering for the proxy-nodes, the following if B.HIGHER:
simple rules, providing the same result, can be used independently #print("4.2.1")
for each different proxy-node. For the following rules, let if A.topo_order < B.topo_order:
X=A.local_root, and if A is the local root, let that be strictly #print("4.2.1.1")
lower than any other node. Always take the first rule that matches. Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.2.1.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if B.LOWER:
#print("4.2.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.2.3")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.3")
if B.LOWER:
#print("4.3.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if B.HIGHER:
#print("4.3.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.3.3")
if A.topo_order < B.topo_order:
#print("4.3.3.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.3.3.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
assert(False)
Figure 27: Select_Proxy_Node_NHs()
Rule Condition Blue NH Red NH Notes It is useful to understand up front that the blue next-hops to reach
1 S=X Blue to A Red to B proxy-node P produced by Select_Proxy_Node_NHs() will always be the
2 S<<A Blue to A Red to R next-hops that reach proxy-node attachment router X, while the red
3 S>>B Blue to R Red to B next-hops to reach proxy-node P will always be the next-hops that
4 A<<S<<B Red to A Blue to B reach proxy-node attachment router Y. This is different from the red
5 A<<S Red to A Blue to R S not ordered w/ B and blue next-hops produced by Compute_MRT_NextHops() where, for
6 S<<B Red to R Blue to B S not ordered w/ A example, blue next-hops to a destination that is ordered with respect
7 Otherwise Red to R Blue to R S not ordered w/ A+B to the source will always correspond to an INCREASING next-hop on the
GADAG. The exact choice of which next-hops chosen by
Select_Proxy_Node_NHs() as the blue next-hops to reach P (which will
necessarily go through X on its way to P) does depend on the GADAG,
but the relationship is more complex than was the case with
Compute_MRT_NextHops().
These rules are realized in the following pseudocode where P is the There are twenty-one different relative order relationships between
proxy-node, X and Y are the nodes that P is attached to, and S is the A, B and S that Select_Proxy_Node_NHs() uses to determine red and
computing router: blue next-hops to P. This document does not attempt to provide an
exhaustive description of each case considered in
Select_Proxy_Node_NHs(). Instead we provide a high level overview of
the different cases, and we consider a few cases in detail to give an
example of the reasoning that can be used to understand each case.
Select_Proxy_Node_NHs(P, S, X, Y) At the highest level, Select_Proxy_Node_NHs() distinguishes between
if (X.order_proxy.topo_order < Y.order_proxy.topo_order) four different cases depending on whether or not A or B is the
//This fits even if X.order_proxy=S.local_root localroot for S. For example, for case 4.0, neither A nor B is the
A=X.order_proxy localroot for S. Case 4.05 addresses the case where S is the
B=Y.order_proxy localroot for either A or B, while cases 4.1, 4.2, and 4.3 address
else the cases where A is ordered lower than S, A is ordered higher than
A=Y.order_proxy S, or A is unordered with respect to S on the GADAG. In general,
B=X.order_proxy each of these cases is then further subdivided into whether or not B
is ordered lower than S, B is ordered higher than S, or B is
unordered with respect to S. In some cases we also need a further
level of discrimination, where we use the topological sort order of A
with respect to B.
if (S==A.local_root) As a detailed example, let's consider case 4.1 and all of its sub-
P.blue_next_hops = A.blue_next_hops cases, and explain why the red and blue next-hops to reach P are
P.red_next_hops = B.red_next_hops chosen as they are in Select_Proxy_Node_NHs(). In case 4.1, neither
return A nor B is the localroot for S, S is not the localroot for A or B,
if (A.higher) and A is ordered lower than S on the GADAG. In this situation, we
P.blue_next_hops = A.blue_next_hops know that the red path to reach X (as computed in
P.red_next_hops = R.red_next_hops Compute_MRT_NextHops()) will follow DECREASING next-hops towards A,
return while the blue path to reach X will follow INCREASING next-hops to
if (B.lower) the localroot, and then INCREASING next-hops to A.
P.blue_next_hops = R.blue_next_hops
P.red_next_hops = B.red_next_hops
return
if (A.lower && B.higher)
P.blue_next_hops = A.red_next_hops
P.red_next_hops = B.blue_next_hops
return
if (A.lower)
P.blue_next_hops = R.red_next_hops
P.red_next_hops = B.blue_next_hops
return
if (B.higher)
P.blue_next_hops = A.red_next_hops
P.red_next_hops = R.blue_next_hops
return
P.blue_next_hops = R.red_next_hops
P.red_next_hops = R.blue_next_hops
return
After finding the the red and the blue next-hops, it is necessary to Now consider sub-case 4.1.1 where B is ordered higher than S. In
know which one of these to use in the case of failure. This can be this situation, we know that the blue path to reach Y will follow
done by Select_Alternates_Inner(). In order to use INCREASING next-hops towards B, while the red next-hops to reach Y
Select_Alternates_Internal(), we need to know if P is greater, less will follow DECREASING next-hops to the localroot, and then
or unordered with S, and P.topo_order. P.lower = B.lower, P.higher = DECREASING next-hops to B. So to reach X and Y by two disjoint
A.higher, and any value is OK for P.topo_order, as long as paths, we can choose the red next-hops to X and the blue next-hops to
A.topo_order<=P.topo_order<=B.topo_order and P.topo_order is not Y. We have chosen the convention that blue next-hops to P are those
equal to the topo_order of the failed node. So for simplicity let that pass through X, and red next-hops to P are those that pass
P.topo_order=A.topo_order when the next-hop is not A, and through Y, so we can see that case 4.1.1 produces the desired result.
P.topo_order=B.topo_order otherwise. This gives the following Choosing blue to X and red to Y does not produce disjoint paths
pseudo-code: because the paths intersect at least at the localroot.
Select_Alternates_Proxy_Node(S, P, F, primary_intf) Now consider sub-case 4.1.2 where B is ordered lower than S. In this
if (F is not P.neighbor_A) situation, we know that the red path to reach Y will follow
return Select_Alternates_Internal(S, P, F, primary_intf, DECREASING next-hops towards B, while the BLUE next-hops to reach Y
P.neighbor_B.lower, will follow INCREASING next-hops to the localroot, and then
P.neighbor_A.higher, INCREASING next-hops to A. The choice here is more difficult than in
P.neighbor_A.topo_order) 4.1.1 because A and B are both on the DECREASING path from S towards
else the localroot. We want to use the direct DECREASING(red) path to the
return Select_Alternates_Internal(S, P, F, primary_intf, one that is nearer to S on the GADAG. We get this extra information
P.neighbor_B.lower, by comparing the topological sort order of A and B. If
P.neighbor_A.higher, A.topo_order<B.topo_order, then we use red to Y and blue to X, since
P.neighbor_B.topo_order) the red path to Y will DECREASE to B without hitting A, and the blue
path to X will INCREASE to A without hitting B. Instead, if
A.topo_order>B.topo_order, then we use red to X and blue to Y.
Figure 27 Note that when A is unordered with respect to B, the result of
comparing A.topo_order with B.topo_order could be greater than or
less than. In this case, the result doesn't matter because either
choice (red to Y and blue to X or red to X and blue to Y) would work.
What is required is that all nodes in the network give the same
result when comparing A.topo_order with B.topo_order. This is
guarantee by having all nodes run the same algorithm
(Run_Topological_Sort_GADAG()) to compute the topological sort order.
Finally we consider case 4.1.3, where B is unordered with respect to
S. In this case, the blue path to reach Y will follow the DECREASING
next-hops towards the localroot until it reaches some node (K) which
is ordered less than B, after which it will take INCREASING next-hops
to B. The red path to reach Y will follow the INCREASING next-hops
towards the localroot until it reaches some node (L) which is ordered
greater than B, after which it will take DECREASING next-hops to B.
Both K and A are reached by DECREASING from S, but we don't have
information about whether or not that DECREASING path will hit K or A
first. Instead, we do know that the INCREASING path from S will hit
L before reaching A. Therefore, we use the red path to reach Y and
the red path to reach X.
Similar reasoning can be applied to understand the other seventeen
cases used in Select_Proxy_Node_NHs(). However, cases 2.3 and 3.3
deserve special attention because the correctness of the solution for
these two cases relies on a special property of the GADAGs that we
have constructed in this algorithm, a property not shared by all
GADAGs in general. Focusing on case 2.3, we consider the case where
A is the localroot for S, while B is not, and B is unordered with
respect to S. The red path to X DECREASES from S to the localroot A,
while the blue path to X INCREASES from S to the localroot A. The
blue path to Y DECREASES towards the localroot A until it reaches
some node (K) which is ordered less than B, after which the path
INCREASES to B. The red path to Y INCREASES towards the localroot A
until it reaches some node (L) which is ordered greater than B, after
which the path DECREASES to B. It can be shown that for an arbitrary
GADAG, with only the ordering relationships computed so far, we don't
have enough information to choose a pair of paths to reach X and Y
that are guaranteed to be disjoint. In some topologies, A will play
the role of K, the first node ordered less than B on the blue path to
Y. In other topologies, A will play the role of L, the first node
ordered greater than B on the red path to Y. The basic problem is
that we cannot distinguish between these two cases based on the
ordering relationships.
As discussed Section 5.8, the GADAGs that we construct using the
algorithm in this document are not arbitrary GADAGs. They have the
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
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
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
red path to Y and the red path to X as the disjoint MRT paths to
reach P.
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
failure. This can be done by Select_Alternates_Proxy_Node(), as
shown in the pseudo-code in Figure 28.
def Select_Alternates_Proxy_Node(P,F,primary_intf):
S = primary_intf.local_node
X = P.pnar_X
Y = P.pnar_Y
A = X.order_proxy
B = Y.order_proxy
if F is A and F is B:
return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'
if F is A:
return 'USE_RED'
if F is B:
return 'USE_BLUE'
if not In_Common_Block(A, B):
if In_Common_Block(F, A):
return 'USE_RED'
elif In_Common_Block(F, B):
return 'USE_BLUE'
else:
return 'USE_RED_OR_BLUE'
if (not In_Common_Block(F, A)
and not In_Common_Block(F, A) ):
return 'USE_RED_OR_BLUE'
alt_to_X = Select_Alternates(X, F, primary_intf)
alt_to_Y = Select_Alternates(Y, F, primary_intf)
if (alt_to_X == 'USE_RED_OR_BLUE'
and alt_to_Y == 'USE_RED_OR_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED_OR_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED_OR_BLUE':
return 'USE_RED'
if (A is S.localroot
and B is S.localroot):
#print("1.0")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is S.localroot
and B is not S.localroot):
#print("2.0")
if B.LOWER:
#print("2.1")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if B.HIGHER:
#print("2.2")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
else:
#print("2.3")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is not S.localroot
and B is S.localroot):
#print("3.0")
if A.LOWER:
#print("3.1")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if A.HIGHER:
#print("3.2")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("3.3")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is not S.localroot
and B is not S.localroot):
#print("4.0")
if (S is A.localroot or S is B.localroot):
#print("4.05")
if A.topo_order < B.topo_order:
#print("4.05.1")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.05.2")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if A.LOWER:
#print("4.1")
if B.HIGHER:
#print("4.1.1")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if B.LOWER:
#print("4.1.2")
if A.topo_order < B.topo_order:
#print("4.1.2.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.1.2.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
else:
#print("4.1.3")
if (F.LOWER and not F.HIGHER
and F.topo_order > A.topo_order):
#print("4.1.3.1")
return 'USE_RED'
else:
#print("4.1.3.2")
return 'USE_BLUE'
if A.HIGHER:
#print("4.2")
if B.HIGHER:
#print("4.2.1")
if A.topo_order < B.topo_order:
#print("4.2.1.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.2.1.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if B.LOWER:
#print("4.2.2")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.2.3")
if (F.HIGHER and not F.LOWER
and F.topo_order < A.topo_order):
return 'USE_RED'
else:
return 'USE_BLUE'
else:
#print("4.3")
if B.LOWER:
#print("4.3.1")
if (F.LOWER and not F.HIGHER
and F.topo_order > B.topo_order):
return 'USE_BLUE'
else:
return 'USE_RED'
if B.HIGHER:
#print("4.3.2")
if (F.HIGHER and not F.LOWER
and F.topo_order < B.topo_order):
return 'USE_BLUE'
else:
return 'USE_RED'
else:
#print("4.3.3")
if A.topo_order < B.topo_order:
#print("4.3.3.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.3.3.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
assert(False)
Figure 28: Select_Alternates_Proxy_Node()
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
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
Select_Alternates(X,F,primary_intf) and
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
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
Select_Proxy_Node_NHs() used that path when constructing the red or
blue path to reach P, then it will also be safe to use that path to
reach P when F fails. This rule has one exception which is covered
below. First, we give a concrete example of how
Select_Alternates_Proxy_Node() works in the common case.
The twenty one ordering relationships used in Select_Proxy_Node_NHs()
are repeated in Select_Alternates_Proxy_Node(). We focus on case
4.1.1 to give give a detailed example of the reasoning used in
Select_Alternates_Proxy_Node(). In Select_Proxy_Node_NHs(), we
determined for case 4.1.1 that the red next-hops to X and the blue
next-hops to Y allow us to reach X and Y by disjoint paths, and are
thus the blue and red next-hops to reach P. Therefore, if we run
Select_Alternates(X, F, primary_intf) and we find that it is safe to
USE_RED to reach X, then we also conclude that it is safe to use the
MRT path through X to reach P (the blue path to P) when F fails.
Similarly, if run Select_Alternates(X, F, primary_intf) and we find
that it is safe to USE_BLUE to reach Y, then we also conclude that it
is safe to use the MRT path through Y to reach P (the red path to P)
when F fails. If both of the paths that were used in
Select_Proxy_Node_NHs() to construct the blue and red paths to P are
found to be safe to use to use to reach X and Y, t then we conclude
that we can use either the red or the blue path to P.
This simple reasoning gives the correct answer in most of the cases.
However, additional logic is needed when either A or B (but not both
A and B) is unordered with respect to S. This applies to cases
4.1.3, 4.2.3, 4.3.1, and 4.3.2. Looking at case 4.1.3 in more
detail, A is ordered less than S, but B is unordered with respect to
S. In the discussion of case 4.1.3 above, we saw that
Select_Proxy_Node_NHs() chose the red path to reach Y and the red
path to reach X. We also saw that the red path to reach Y will
follow the INCREASING next-hops towards the localroot until it
reaches some node (L) which is ordered greater than B, after which it
will take DECREASING next-hops to B. The problem is that the red
path to reach P (the one that goes through Y) won't necessarily be
the same as the red path to reach Y. This is because the next-hop
that node L computes for its red next-hop to reach P may be different
from the next-hop it computes for its red next-hop to reach Y. This
is because B is ordered lower than L, so L applies case 4.1.2 of
Select_Proxy_Node_NHs() in order to determine its next-hops to reach
P. If A.topo_order<B.topo_order (case 4.1.2.1), then L will choose
DECREASING next-hops directly to B, which is the same result that L
computes in Compute_MRT_NextHops() to reach Y. However, if
A.topo_order>B.topo_order (case 4.1.2.2), then L will choose
INCREASING next-hops to reach B, which is different from what L
computes in Compute_MRT_NextHops() to reach Y. So testing the safety
of the path for S to reach Y on failure of F as a surrogate for the
safety of using the red path to reach P is not reliable in this case.
It is possible construct topologies where the red path to P hits F
even though the red path to Y does not hit F.
Fortunately there is enough information in the order relationships
that we have already computed to still figure out which alternate to
choose in these four cases. The basic idea is to always choose the
path involving the ordered node, unless that path would hit F.
Returning to case 4.1.3, we see that since A is ordered lower than S,
the only way for S to hit F using a simple DECREASING path to A is
for F to lie between A and S on the GADAG. This scenario is covered
by requiring that F be lower than S (but not also higher than S) and
that F.topo_order>A.topo_order in case 4.1.3.1.
We just need to confirm that it is safe to use the path involving B
in this scenario. In case 4.1.3.1, either F is between A and S on
the GADAG, or F is unordered with respect to A and lies on the
DECREASING path from S to the localroot. When F is between A and S
on the GADAG, then the path through B chosen to avoid A in
Select_Proxy_Node_NHs() will also avoid F. When F is unordered with
respect to A and lies on the DECREASING path from S to the localroot,
then we consider two cases. Either F.topo_order<B.topo_order or
F.topo_order>B.topo_order. In the first case, since
F.topo_order<B.topo_order and F.topo_order>A.topo_order, it must be
the case that A.topo_order<B.topo_order. Therefore, L will choose
DECREASING next-hops directly to B (case 4.1.2.1), which cannot hit F
since F.topo_order<B.topo_order. In the second case, where
F.topo_order>B.topo_order, the only way for the path involving B to
hit F is if it DECREASES from L to B through F , ie. it must be that
L>>F>>B. However, since S>>F, this would imply that S>>B. However,
we know that S is unordered with respect to B, so the second case
cannot occur. So we have demonstrated that the red path to P (which
goes via B and Y) is safe to use under the conditions of 4.1.3.1.
Similar reasoning can be applied to the other three special cases
where either A or B is unordered with respect to S.
6. MRT Lowpoint Algorithm: Next-hop conformance 6. MRT Lowpoint Algorithm: Next-hop conformance
This specification defines the MRT Lowpoint Algorithm, which include This specification defines the MRT Lowpoint Algorithm, which include
the construction of a common GADAG and the computation of MRT-Red and the construction of a common GADAG and the computation of MRT-Red and
MRT-Blue next-hops to each node in the graph. An implementation MAY MRT-Blue next-hops to each node in the graph. An implementation MAY
select any subset of next-hops for MRT-Red and MRT-Blue that respect select any subset of next-hops for MRT-Red and MRT-Blue that respect
the available nodes that are described in Section 5.7 for each of the the available nodes that are described in Section 5.7 for each of the
MRT-Red and MRT-Blue and the selected next-hops are further along in MRT-Red and MRT-Blue and the selected next-hops are further along in
the interval of allowed nodes towards the destination. the interval of allowed nodes towards the destination.
skipping to change at page 45, line 41 skipping to change at page 58, line 25
For example, the MRT-Blue next-hops used when the destination Y >> X, For example, the MRT-Blue next-hops used when the destination Y >> X,
the computing router, MUST be one or more nodes, T, whose topo_order the computing router, MUST be one or more nodes, T, whose topo_order
is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y is in the interval [X.topo_order, Y.topo_order] and where Y >> T or Y
is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in is T. Similarly, the MRT-Red next-hops MUST be have a topo_order in
the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, the interval [R-small.topo_order, X.topo_order] or [Y.topo_order,
R-big.topo_order]. R-big.topo_order].
Implementations SHOULD implement the Select_Alternates() function to Implementations SHOULD implement the Select_Alternates() function to
pick an MRT-FRR alternate. pick an MRT-FRR alternate.
7. Python Implementation of MRT Lowpoint Algorithm 7. Broadcast interfaces
When broadcast interfaces are used to connect nodes, the broadcast
network MUST be represented as a pseudonode, where each real node
connects to the pseudonode. The interface metric in the direction
from real node to pseudonode is the non-zero interface metric, while
the interface metric in the direction from the pseudonode to the real
node is set to zero. This is consistent with the way that broadcast
interfaces are represented as pseudonodes in IS-IS and OSPF.
Pseudonodes MUST be treated as equivalent to real nodes in the
network graph used in the MRT algorithm with a few exceptions
detailed below.
The pseudonodes MUST be included in the computation of the GADAG.
The neighbors of the pseudonode need to know the mrt_node_id of the
pseudonode in order to consistently order interfaces, which is needed
to compute the GADAG. The mrt_node_id for IS-IS is the 7 octet
neighbor system ID and pseudonode number in TLV #22 or TLV#222. The
mrt_node_id for OSPFv2 is the 4 octet interface address of the
Designated Router found in the Link ID field for the link type 2
(transit network) in the Router-LSA. The mrt_node_id for OSPFv3 is
the 4 octet interface address of the Designated Router found in the
Neighbor Interface ID field for the link type 2 (transit network) in
the Router-LSA. pseudonodes MUST NOT be considered as candidates for
GADAG root selection. Note that this is different from the Neighbor
Router ID field used for the mrt_node_id for point-to-point links in
OSPFv3 Router-LSAs given in Figure 15.
Pseudonodes MUST NOT be considered as candidates for selection as
GADAG root. This rule is intended to result in a more stable
network- wide selection of GADAG root by removing the possibility
that the change of Designated Router or Designated Intermediate
System on a broadcast network can result in a change of GADAG root.
7.1. Computing MRT next-hops on broadcast networks
The pseudonode does not correspond to an real node, so it is not
actually involved in forwarding. A real node on a broadcast network
cannot simply forward traffic to the broadcast network. It must
specify another real node on the broadcast network as the next-hop.
On a network graph where a broadcast network is represented by a
pseudonode, this means that if a real node determines that the next-
hop to reach a given destination is a pseudonode, it must also
determine the next-next-hop for that destination in the network
graph, which corresponds to a real node attached to the broadcast
network.
It is interesting to note that this issue is not unique to the MRT
algorithm, but is also encountered in normal SPF computations for
IGPs. Section 16.1.1 of [RFC2327] describes how this is done for
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
from the computing routing, and that one hop is a pseudonode, then
the next-hop for that destination is taken from the interface IP
address in the Router-LSA correspond to the link to the real
destination node
For IS-IS, in the example pseudo-code implementation of Dijkstra's
algorithm in Annex C of [ISO10589-Second-Edition] whenever the
algorithm encounters an adjacency from a real node to a pseudonode,
it gets converted to a set of adjacencies from the real node to the
neighbors of the pseudonode. In this way, the computed next-hops
point all the way to the real node, and not the pseudonode.
We could avoid the problem of determining next-hops across
pseudonodes in MRT by converting the pseudonode representation of
broadcast networks to a full mesh of links between real nodes on the
same network. However, if we make that conversion before computing
the GADAG, we lose information about which links actually correspond
to a single physical interface into the broadcast network. This
could result computing red and blue next-hops that use the same
broadcast interface, in which case neither the red nor the blue next-
hop would be usable as an alternate on failure of the broadcast
interface.
Instead, we take the following approach, which maintains the property
that either the red and blue next-hop will avoid the broadcast
network, if topologically allowed. We run the MRT algorithm treating
the pseudonodes as equivalent to real nodes in the network graph,
with the exceptions noted above. In addition to running the MRT
algorithm from the point of view of itself, a computing router
connected to a pseudonode MUST also run the MRT algorithm from the
point of view of each of its pseudonode neighbors. For example, if a
computing router S determines that its MRT red next-hop to reach a
destination D is a pseudonode P, S looks at its MRT algorithm
computation from P's point of view to determine P's red next-hop to
reach D, say interface 1 on node X. S now knows that its real red
next-hop to reach D is interface 1 on node X on the broadcast network
represented by P, and can install the corresponding entry in its FIB.
7.2. Using MRT next-hops as alternates in the event of failures on
broadcast networks
In the previous section, we specified how to compute MRT next-hops
when broadcast networks are involved. In this section, we discuss
how a PLR can use those MRT next-hops in the event of failures
involving broadcast networks.
A PLR attached to a broadcast network running only OSPF or IS-IS with
large Hello intervals has limited ability to quickly detect failures
on a broadcast network. The only failure mode that can be quickly
detected is the failure of the physical interface connecting the PLR
to the broadcast network. For the failure of the interface
connecting the PLR to the broadcast network, the alternate that
avoids the broadcast network can be computed by using the broadcast
network pseudonode as F, the primary next-hop node, in
Select_Alternates(). This will choose an alternate path that avoids
the broadcast network. However, the alternate path will not
necessarily avoid all of the real nodes connected to the broadcast
network. This is because we have used the pseudonode to represent
the broadcast network. And we have enforced the node-protecting
property of MRT on the pseudonode to provide protection against
failure of the broadcast network, not the real next-hop nodes on the
broadcast network. This is the best that we can hope to do if
failure of the broadcast interface is the only failure mode that the
PLR can respond to.
We can improve on this if the PLR also has the ability to quickly
detect a lack of connectivity across the broadcast network to a given
IP-layer node. This can be accomplished by running BFD between all
pairs of IGP neighbors on the broadcast network. Note that in the
case of OSPF, this would require establishing BFD sessions between
all pairs of neighbors in the 2-WAY state. When the PLR can quickly
detect the failure of a particular next-hop across a broadcast
network, then the PLR can be more selective in its choice of
alternates. For example, when the PLR observes that connectivity to
an IP-layer node on a broadcast network has failed, the PLR may
choose to still use the broadcast network to reach other IP-layer
nodes which are still reachable. Or if the PLR observes that
connectivity has failed to several IP-layer nodes on the same
broadcast network, it may choose to treat the entire broadcast
network as failed. The choice of MRT alternates by a PLR for a
particular set of failure conditions is a local decision, since it
does not require coordination with other nodes.
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.
<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
# an example topology. It then reads that text file back in as input
# to create the example topology, and runs the MRT algorithm.This
# was done to simplify the inclusion of the program as a single text
# file that can be extracted from the IETF draft.
# When executed, this program will generate a text file describing # The output of the program is four text files containing a description
# an example topology. It then reads that text file back in as input # of the GADAG, the blue and red MRTs for all destinations, and the
# to create the example topology, and runs the MRT algorithm.This # MRT alternates for all failures.
# was done to simplify the inclusion of the program as a single text
# file that can be extracted from the IETF draft.
# The output of the program is four text files containing a description import random
# of the GADAG, the blue and red MRTs for all destinations, and the import os.path
# MRT alternates for all failures. import heapq
import heapq # simple Class definitions allow structure-like dot notation for
# variables and a convenient place to initialize those variables.
class Topology:
def __init__(self):
self.gadag_root = None
self.node_list = []
self.node_dict = {}
self.test_gr = None
self.island_node_list_for_test_gr = []
self.stored_named_proxy_dict = {}
self.init_new_computing_router()
def init_new_computing_router(self):
self.island_node_list = []
self.named_proxy_dict = {}
# simple Class definitions allow structure-like dot notation for class Node:
# variables and a convenient place to initialize those variables. def __init__(self):
class Topology: self.node_id = None
pass self.intf_list = []
self.profile_id_list = [0]
self.GR_sel_priority = 128
self.blue_next_hops_dict = {}
self.red_next_hops_dict = {}
self.blue_to_green_nh_dict = {}
self.red_to_green_nh_dict = {}
self.prefix_cost_dict = {}
self.pnh_dict = {}
self.alt_dict = {}
self.init_new_computing_router()
def init_new_computing_router(self):
self.island_intf_list = []
self.IN_MRT_ISLAND = False
self.IN_GADAG = False
self.dfs_number = None
self.dfs_parent = None
self.dfs_parent_intf = None
self.dfs_child_list = []
self.lowpoint_number = None
self.lowpoint_parent = None
self.lowpoint_parent_intf = None
self.localroot = None
self.block_id = None
self.IS_CUT_VERTEX = False
self.blue_next_hops = []
self.red_next_hops = []
self.primary_next_hops = []
self.alt_list = []
class Node: class Interface:
pass def __init__(self):
self.metric = None
self.area = None
self.MRT_INELIGIBLE = False
self.IGP_EXCLUDED = False
self.SIMULATION_OUTGOING = False
self.init_new_computing_router()
def init_new_computing_router(self):
self.UNDIRECTED = True
self.INCOMING = False
self.OUTGOING = False
self.INCOMING_STORED = False
self.OUTGOING_STORED = False
self.IN_MRT_ISLAND = False
self.PROCESSED = False
class Interface: class Bundle:
pass def __init__(self):
self.UNDIRECTED = True
self.OUTGOING = False
self.INCOMING = False
class Bundle: class Alternate:
pass def __init__(self):
self.failed_intf = None
self.red_or_blue = None
self.nh_list = []
self.fec = 'NO_ALTERNATE'
self.prot = 'NO_PROTECTION'
self.info = 'NONE'
class Alternate: class Proxy_Node_Attachment_Router:
def __init__(self): def __init__(self):
self.failed_intf = None self.prefix = None
self.nh_list = [] self.node = None
self.fec = 'NO_ALTERNATE' self.named_proxy_cost = None
self.prot = 'NO_PROTECTION' self.min_lfin = None
self.info = 'NONE' self.nh_intf_list = []
def Interface_Compare(intf_a, intf_b): class Named_Proxy_Node:
if intf_a.metric < intf_b.metric: def __init__(self):
return -1 self.node_id = None #this is the prefix_id
if intf_b.metric < intf_a.metric: self.node_prefix_cost_list = []
return 1 self.lfin_list = []
if intf_a.remote_node.node_id < intf_b.remote_node.node_id: self.pnar1 = None
return -1 self.pnar2 = None
if intf_b.remote_node.node_id < intf_a.remote_node.node_id: self.pnar_X = None
return 1 self.pnar_Y = None
return 0 self.blue_next_hops = []
self.red_next_hops = []
self.primary_next_hops = []
self.blue_next_hops_dict = {}
self.red_next_hops_dict = {}
self.pnh_dict = {}
self.alt_dict = {}
def Sort_Interfaces(topo): def Interface_Compare(intf_a, intf_b):
for node in topo.island_node_list:
node.island_intf_list.sort(Interface_Compare)
def Initialize_Node(node): if intf_a.metric < intf_b.metric:
node.intf_list = [] return -1
node.island_intf_list = [] if intf_b.metric < intf_a.metric:
node.profile_id_list = [0] return 1
node.GR_sel_priority = 128 if intf_a.remote_node.node_id < intf_b.remote_node.node_id:
node.IN_MRT_ISLAND = False return -1
node.IN_GADAG = False if intf_b.remote_node.node_id < intf_a.remote_node.node_id:
node.dfs_number = None return 1
node.dfs_parent = None return 0
node.dfs_parent_intf = None
node.dfs_child_list = []
node.lowpoint_number = None
node.lowpoint_parent = None
node.lowpoint_parent_intf = None
node.localroot = None
node.block_id = None
node.IS_CUT_VERTEX = False
node.blue_next_hops_dict = {}
node.red_next_hops_dict = {}
node.pnh_dict = {}
node.alt_dict = {}
def Initialize_Intf(intf): def Sort_Interfaces(topo):
intf.metric = None for node in topo.island_node_list:
intf.area = None node.island_intf_list.sort(Interface_Compare)
intf.MRT_INELIGIBLE = False
intf.IGP_EXCLUDED = False
intf.UNDIRECTED = True
intf.INCOMING = False
intf.OUTGOING = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
intf.PROCESSED = False
intf.IN_MRT_ISLAND = False
def Reset_Computed_Node_and_Intf_Values(topo): def Reset_Computed_Node_and_Intf_Values(topo):
for node in topo.node_list: topo.init_new_computing_router()
node.IN_MRT_ISLAND = False for node in topo.node_list:
node.IN_GADAG = False node.init_new_computing_router()
node.dfs_number = None for intf in node.intf_list:
node.dfs_parent = None intf.init_new_computing_router()
node.dfs_parent_intf = None
node.dfs_child_list = []
node.lowpoint_number = None
node.lowpoint_parent = None
node.lowpoint_parent_intf = None
node.localroot = None
node.block_id = None
node.IS_CUT_VERTEX = False
for intf in node.intf_list:
intf.UNDIRECTED = True
intf.INCOMING = False
intf.OUTGOING = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
intf.IN_MRT_ISLAND = False
# This function takes a file with links represented by 2-digit # This function takes a file with links represented by 2-digit
# numbers in the format: # numbers in the format:
# 01,05,10 # 01,05,10
# 05,02,30 # 05,02,30
# 02,01,15 # 02,01,15
# which represents a triangle topology with nodes 01, 05, and 02 # which represents a triangle topology with nodes 01, 05, and 02
# and symmetric metrics of 10, 30, and 15. # and symmetric metrics of 10, 30, and 15.
# Inclusion of a fourth column makes the metrics for the link # Inclusion of a fourth column makes the metrics for the link
# asymmetric. An entry of: # asymmetric. An entry of:
# 02,07,10,15 # 02,07,10,15
# creates a link from node 02 to 07 with metrics 10 and 15. # creates a link from node 02 to 07 with metrics 10 and 15.
def Create_Topology_From_File(filename): def Create_Topology_From_File(filename):
topo = Topology() topo = Topology()
topo.gadag_root = None node_id_set= set()
topo.node_list = [] cols_list = []
topo.node_dict = {} # on first pass just create nodes
topo.island_node_list = [] with open(filename + '.csv') as topo_file:
topo.prefix_list = [] # possibly no longer needed for line in topo_file:
node_id_set= set() line = line.rstrip('\r\n')
cols_list = [] cols=line.split(',')
# on first pass just create nodes cols_list.append(cols)
with open(filename) as topo_file: nodea_node_id = int(cols[0])
for line in topo_file: nodeb_node_id = int(cols[1])
line = line.rstrip('\r\n') if (nodea_node_id > 999 or nodeb_node_id > 999):
cols=line.split(',') print("node_id must be between 0 and 999.")
cols_list.append(cols) print("exiting.")
nodea_node_id = int(cols[0]) exit()
nodeb_node_id = int(cols[1]) node_id_set.add(nodea_node_id)
if (nodea_node_id > 999 or nodeb_node_id > 999): node_id_set.add(nodeb_node_id)
print("node_id must be between 0 and 999.") for node_id in node_id_set:
print("exiting.") node = Node()
exit() node.node_id = node_id
node_id_set.add(nodea_node_id) topo.node_list.append(node)
node_id_set.add(nodeb_node_id) topo.node_dict[node_id] = node
for node_id in node_id_set: # on second pass create interfaces
node = Node() for cols in cols_list:
node.node_id = node_id nodea_node_id = int(cols[0])
Initialize_Node(node) nodeb_node_id = int(cols[1])
topo.node_list.append(node) metric = int(cols[2])
topo.node_dict[node_id] = node reverse_metric = int(cols[2])
# on second pass create interfaces if len(cols) > 3:
for cols in cols_list: reverse_metric=int(cols[3])
nodea_node_id = int(cols[0]) nodea = topo.node_dict[nodea_node_id]
nodeb_node_id = int(cols[1]) nodeb = topo.node_dict[nodeb_node_id]
metric = int(cols[2]) nodea_intf = Interface()
reverse_metric = int(cols[2]) nodea_intf.metric = metric
if len(cols) > 3: nodea_intf.area = 0
reverse_metric=int(cols[3]) nodeb_intf = Interface()
nodea = topo.node_dict[nodea_node_id] nodeb_intf.metric = reverse_metric
nodeb = topo.node_dict[nodeb_node_id] nodeb_intf.area = 0
nodea_intf = Interface() nodea_intf.remote_intf = nodeb_intf
Initialize_Intf(nodea_intf) nodeb_intf.remote_intf = nodea_intf
nodea_intf.metric = metric nodea_intf.remote_node = nodeb
nodea_intf.area = 0 nodeb_intf.remote_node = nodea
nodeb_intf = Interface() nodea_intf.local_node = nodea
Initialize_Intf(nodeb_intf) nodeb_intf.local_node = nodeb
nodeb_intf.metric = reverse_metric nodea_intf.link_data = len(nodea.intf_list)
nodeb_intf.area = 0 nodeb_intf.link_data = len(nodeb.intf_list)
nodea_intf.remote_intf = nodeb_intf nodea.intf_list.append(nodea_intf)
nodeb_intf.remote_intf = nodea_intf nodeb.intf_list.append(nodeb_intf)
nodea_intf.remote_node = nodeb return topo
nodeb_intf.remote_node = nodea
nodea_intf.local_node = nodea
nodeb_intf.local_node = nodeb
nodea_intf.link_data = len(nodea.intf_list)
nodeb_intf.link_data = len(nodeb.intf_list)
nodea.intf_list.append(nodea_intf)
nodeb.intf_list.append(nodeb_intf)
return topo
def MRT_Island_Identification(topo, computing_rtr, profile_id, area): def MRT_Island_Identification(topo, computing_rtr, profile_id, area):
if profile_id in computing_rtr.profile_id_list: if profile_id in computing_rtr.profile_id_list:
computing_rtr.IN_MRT_ISLAND = True computing_rtr.IN_MRT_ISLAND = True
explore_list = [computing_rtr] explore_list = [computing_rtr]
else: else:
return return
while explore_list != []: while explore_list != []:
next_rtr = explore_list.pop() next_rtr = explore_list.pop()
for intf in next_rtr.intf_list: for intf in next_rtr.intf_list:
if ( not intf.MRT_INELIGIBLE and not intf.IGP_EXCLUDED if ( (not intf.MRT_INELIGIBLE)
and intf.area == area ): and (not intf.remote_intf.MRT_INELIGIBLE)
and (not intf.IGP_EXCLUDED) and intf.area == area ):
if (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
if (not intf.remote_node.IN_MRT_ISLAND): intf.remote_intf.IN_MRT_ISLAND = True
intf.remote_node.IN_MRT_ISLAND = True if (not intf.remote_node.IN_MRT_ISLAND):
explore_list.append(intf.remote_node) intf.remote_node.IN_MRT_ISLAND = True
explore_list.append(intf.remote_node)
def Set_Island_Intf_and_Node_Lists(topo): def Compute_Island_Node_List_For_Test_GR(topo, test_gr):
topo.island_node_list = [] Reset_Computed_Node_and_Intf_Values(topo)
for node in topo.node_list: topo.test_gr = topo.node_dict[test_gr]
node.island_intf_list = [] MRT_Island_Identification(topo, topo.test_gr, 0, 0)
if node.IN_MRT_ISLAND: for node in topo.node_list:
topo.island_node_list.append(node) if node.IN_MRT_ISLAND:
for intf in node.intf_list: topo.island_node_list_for_test_gr.append(node)
if intf.IN_MRT_ISLAND:
node.island_intf_list.append(intf)
global_dfs_number = None def Set_Island_Intf_and_Node_Lists(topo):
for node in topo.node_list:
if node.IN_MRT_ISLAND:
topo.island_node_list.append(node)
for intf in node.intf_list:
if intf.IN_MRT_ISLAND:
node.island_intf_list.append(intf)
def Lowpoint_Visit(x, parent, intf_p_to_x): global_dfs_number = None
global global_dfs_number
x.dfs_number = global_dfs_number
x.lowpoint_number = x.dfs_number
global_dfs_number += 1
x.dfs_parent = parent
if intf_p_to_x == None:
x.dfs_parent_intf = None
else:
x.dfs_parent_intf = intf_p_to_x.remote_intf
x.lowpoint_parent = None
if parent != None:
parent.dfs_child_list.append(x)
for intf in x.island_intf_list:
if intf.remote_node.dfs_number == None:
Lowpoint_Visit(intf.remote_node, x, intf)
if intf.remote_node.lowpoint_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.lowpoint_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else:
if intf.remote_node is not parent:
if intf.remote_node.dfs_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.dfs_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
def Run_Lowpoint(topo): def Lowpoint_Visit(x, parent, intf_p_to_x):
global global_dfs_number global global_dfs_number
global_dfs_number = 0 x.dfs_number = global_dfs_number
Lowpoint_Visit(topo.gadag_root, None, None) x.lowpoint_number = x.dfs_number
global_dfs_number += 1
x.dfs_parent = parent
if intf_p_to_x == None:
x.dfs_parent_intf = None
else:
x.dfs_parent_intf = intf_p_to_x.remote_intf
x.lowpoint_parent = None
if parent != None:
parent.dfs_child_list.append(x)
for intf in x.island_intf_list:
if intf.remote_node.dfs_number == None:
Lowpoint_Visit(intf.remote_node, x, intf)
if intf.remote_node.lowpoint_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.lowpoint_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else:
if intf.remote_node is not parent:
if intf.remote_node.dfs_number < x.lowpoint_number:
# addresses these cases. x.lowpoint_number = intf.remote_node.dfs_number
max_block_id = None x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
def Assign_Block_ID(x, cur_block_id): def Run_Lowpoint(topo):
global max_block_id global global_dfs_number
x.block_id = cur_block_id global_dfs_number = 0
for c in x.dfs_child_list: Lowpoint_Visit(topo.gadag_root, None, None)
if (c.localroot is x):
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else:
Assign_Block_ID(c, cur_block_id)
def Run_Assign_Block_ID(topo): max_block_id = None
global max_block_id
max_block_id = 0
Assign_Block_ID(topo.gadag_root, max_block_id)
def Construct_Ear(x, stack, intf, ear_type): def Assign_Block_ID(x, cur_block_id):
ear_list = [] global max_block_id
cur_intf = intf x.block_id = cur_block_id
not_done = True for c in x.dfs_child_list:
if (c.localroot is x):
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else:
Assign_Block_ID(c, cur_block_id)
while not_done: def Run_Assign_Block_ID(topo):
cur_intf.UNDIRECTED = False global max_block_id
cur_intf.OUTGOING = True max_block_id = 0
cur_intf.remote_intf.UNDIRECTED = False Assign_Block_ID(topo.gadag_root, max_block_id)
cur_intf.remote_intf.INCOMING = True
if cur_intf.remote_node.IN_GADAG == False:
cur_intf.remote_node.IN_GADAG = True
ear_list.append(cur_intf.remote_node)
if ear_type == 'CHILD':
cur_intf = cur_intf.remote_node.lowpoint_parent_intf
else:
assert ear_type == 'NEIGHBOR'
cur_intf = cur_intf.remote_node.dfs_parent_intf
else:
not_done = False
if ear_type == 'CHILD' and cur_intf.remote_node is x: def Construct_Ear(x, stack, intf, ear_type):
# x is a cut-vertex and the local root for the block ear_list = []
# in which the ear is computed cur_intf = intf
x.IS_CUT_VERTEX = True not_done = True
localroot = x while not_done:
cur_intf.UNDIRECTED = False
cur_intf.OUTGOING = True
cur_intf.remote_intf.UNDIRECTED = False
cur_intf.remote_intf.INCOMING = True
if cur_intf.remote_node.IN_GADAG == False:
cur_intf.remote_node.IN_GADAG = True
ear_list.append(cur_intf.remote_node)
if ear_type == 'CHILD':
cur_intf = cur_intf.remote_node.lowpoint_parent_intf
else:
assert ear_type == 'NEIGHBOR'
cur_intf = cur_intf.remote_node.dfs_parent_intf
else:
not_done = False
else: if ear_type == 'CHILD' and cur_intf.remote_node is x:
# inherit local root from the end of the ear # x is a cut-vertex and the local root for the block
localroot = cur_intf.remote_node.localroot # in which the ear is computed
x.IS_CUT_VERTEX = True
localroot = x
else:
# inherit local root from the end of the ear
localroot = cur_intf.remote_node.localroot
while ear_list != []: while ear_list != []:
y = ear_list.pop() y = ear_list.pop()
y.localroot = localroot y.localroot = localroot
stack.append(y) stack.append(y)
def Construct_GADAG_via_Lowpoint(topo): def Construct_GADAG_via_Lowpoint(topo):
gadag_root = topo.gadag_root gadag_root = topo.gadag_root
gadag_root.IN_GADAG = True gadag_root.IN_GADAG = True
gadag_root.localroot = None gadag_root.localroot = None
stack = [] stack = []
stack.append(gadag_root) stack.append(gadag_root)
while stack != []:
x = stack.pop()
for intf in x.island_intf_list:
if ( intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is x ):
Construct_Ear(x, stack, intf, 'CHILD' )
for intf in x.island_intf_list:
if (intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is not x):
Construct_Ear(x, stack, intf, 'NEIGHBOR')
while stack != []: def Assign_Remaining_Lowpoint_Parents(topo):
x = stack.pop() for node in topo.island_node_list:
for intf in x.island_intf_list: if ( node is not topo.gadag_root
if ( intf.remote_node.IN_GADAG == False and node.lowpoint_parent == None ):
and intf.remote_node.dfs_parent is x ): node.lowpoint_parent = node.dfs_parent
Construct_Ear(x, stack, intf, 'CHILD' ) node.lowpoint_parent_intf = node.dfs_parent_intf
for intf in x.island_intf_list: node.lowpoint_number = node.dfs_parent.dfs_number
if (intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is not x):
Construct_Ear(x, stack, intf, 'NEIGHBOR')
def Assign_Remaining_Lowpoint_Parents(topo): def Add_Undirected_Block_Root_Links(topo):
for node in topo.island_node_list: for node in topo.island_node_list:
if ( node is not topo.gadag_root if node.IS_CUT_VERTEX or node is topo.gadag_root:
and node.lowpoint_parent == None ): for intf in node.island_intf_list:
node.lowpoint_parent = node.dfs_parent if ( intf.remote_node.localroot is not node
node.lowpoint_parent_intf = node.dfs_parent_intf or intf.PROCESSED ):
node.lowpoint_number = node.dfs_parent.dfs_number continue
bundle_list = []
bundle = Bundle()
for intf2 in node.island_intf_list:
if intf2.remote_node is intf.remote_node:
def Add_Undirected_Block_Root_Links(topo): bundle_list.append(intf2)
for node in topo.island_node_list: if not intf2.UNDIRECTED:
if node.IS_CUT_VERTEX or node is topo.gadag_root: bundle.UNDIRECTED = False
for intf in node.island_intf_list: if intf2.INCOMING:
if ( intf.remote_node.localroot is not node bundle.INCOMING = True
or intf.PROCESSED ): if intf2.OUTGOING:
continue bundle.OUTGOING = True
bundle_list = [] if bundle.UNDIRECTED:
bundle = Bundle() for intf3 in bundle_list:
bundle.UNDIRECTED = True intf3.UNDIRECTED = False
bundle.OUTGOING = False intf3.remote_intf.UNDIRECTED = False
bundle.INCOMING = False intf3.PROCESSED = True
for intf2 in node.island_intf_list: intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
else:
if (bundle.OUTGOING and bundle.INCOMING):
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.INCOMING = True
intf3.remote_intf.INCOMING = True
intf3.remote_intf.OUTGOING = True
elif bundle.OUTGOING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
elif bundle.INCOMING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.INCOMING = True
intf3.remote_intf.OUTGOING = True
if intf2.remote_node is intf.remote_node: def Modify_Block_Root_Incoming_Links(topo):
bundle_list.append(intf2) for node in topo.island_node_list:
if not intf2.UNDIRECTED: if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
bundle.UNDIRECTED = False for intf in node.island_intf_list:
if intf2.INCOMING: if intf.remote_node.localroot is node:
bundle.INCOMING = True
if intf2.OUTGOING:
bundle.OUTGOING = True
if bundle.UNDIRECTED:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
else:
if (bundle.OUTGOING and bundle.INCOMING):
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.INCOMING = True
intf3.remote_intf.INCOMING = True
intf3.remote_intf.OUTGOING = True
elif bundle.OUTGOING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
elif bundle.INCOMING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.INCOMING = True
intf3.remote_intf.OUTGOING = True
def Modify_Block_Root_Incoming_Links(topo): if intf.INCOMING:
for node in topo.island_node_list: intf.INCOMING = False
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): intf.INCOMING_STORED = True
for intf in node.island_intf_list: intf.remote_intf.OUTGOING = False
intf.remote_intf.OUTGOING_STORED = True
if intf.remote_node.localroot is node: def Revert_Block_Root_Incoming_Links(topo):
if intf.INCOMING: for node in topo.island_node_list:
intf.INCOMING = False if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
intf.INCOMING_STORED = True for intf in node.island_intf_list:
intf.remote_intf.OUTGOING = False if intf.remote_node.localroot is node:
intf.remote_intf.OUTGOING_STORED = True if intf.INCOMING_STORED:
intf.INCOMING = True
intf.remote_intf.OUTGOING = True
intf.INCOMING_STORED = False
intf.remote_intf.OUTGOING_STORED = False
def Revert_Block_Root_Incoming_Links(topo): def Run_Topological_Sort_GADAG(topo):
for node in topo.island_node_list: Modify_Block_Root_Incoming_Links(topo)
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ): for node in topo.island_node_list:
for intf in node.island_intf_list: node.unvisited = 0
if intf.remote_node.localroot is node: for intf in node.island_intf_list:
if intf.INCOMING_STORED: if (intf.INCOMING == True):
intf.INCOMING = True node.unvisited += 1
intf.remote_intf.OUTGOING = True working_list = []
intf.INCOMING_STORED = False topo_order_list = []
intf.remote_intf.OUTGOING_STORED = False working_list.append(topo.gadag_root)
while working_list != []:
y = working_list.pop(0)
topo_order_list.append(y)
for intf in y.island_intf_list:
if ( intf.OUTGOING == True):
intf.remote_node.unvisited -= 1
if intf.remote_node.unvisited == 0:
working_list.append(intf.remote_node)
next_topo_order = 1
while topo_order_list != []:
y = topo_order_list.pop(0)
y.topo_order = next_topo_order
next_topo_order += 1
Revert_Block_Root_Incoming_Links(topo)
def Run_Topological_Sort_GADAG(topo): def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):
Modify_Block_Root_Incoming_Links(topo) for node in topo.island_node_list:
for node in topo.island_node_list: for intf in node.island_intf_list:
node.unvisited = 0 if intf.UNDIRECTED:
for intf in node.island_intf_list: if node.topo_order < intf.remote_node.topo_order:
if (intf.INCOMING == True): intf.OUTGOING = True
node.unvisited += 1 intf.UNDIRECTED = False
working_list = [] intf.remote_intf.INCOMING = True
topo_order_list = [] intf.remote_intf.UNDIRECTED = False
working_list.append(topo.gadag_root) else:
while working_list != []: intf.INCOMING = True
y = working_list.pop(0) intf.UNDIRECTED = False
topo_order_list.append(y) intf.remote_intf.OUTGOING = True
for intf in y.island_intf_list: intf.remote_intf.UNDIRECTED = False
if ( intf.OUTGOING == True):
intf.remote_node.unvisited -= 1
if intf.remote_node.unvisited == 0:
working_list.append(intf.remote_node)
next_topo_order = 1
while topo_order_list != []:
y = topo_order_list.pop(0)
y.topo_order = next_topo_order
next_topo_order += 1
Revert_Block_Root_Incoming_Links(topo)
def Set_Other_Undirected_Links_Based_On_Topo_Order(topo): def Initialize_Temporary_Interface_Flags(topo):
for node in topo.island_node_list: for node in topo.island_node_list:
for intf in node.island_intf_list: for intf in node.island_intf_list:
if intf.UNDIRECTED: intf.PROCESSED = False
if node.topo_order < intf.remote_node.topo_order: intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
intf.OUTGOING = True def Add_Undirected_Links(topo):
intf.UNDIRECTED = False Initialize_Temporary_Interface_Flags(topo)
intf.remote_intf.INCOMING = True Add_Undirected_Block_Root_Links(topo)
intf.remote_intf.UNDIRECTED = False Run_Topological_Sort_GADAG(topo)
else: Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
intf.INCOMING = True
intf.UNDIRECTED = False
intf.remote_intf.OUTGOING = True
intf.remote_intf.UNDIRECTED = False
def Initialize_Temporary_Interface_Flags(topo): def In_Common_Block(x,y):
for node in topo.island_node_list: if ( (x.block_id == y.block_id)
for intf in node.island_intf_list: or ( x is y.localroot) or (y is x.localroot) ):
intf.PROCESSED = False return True
intf.INCOMING_STORED = False return False
intf.OUTGOING_STORED = False
def Add_Undirected_Links(topo): def Copy_List_Items(target_list, source_list):
Initialize_Temporary_Interface_Flags(topo) del target_list[:] # Python idiom to remove all elements of a list
Add_Undirected_Block_Root_Links(topo) for element in source_list:
Run_Topological_Sort_GADAG(topo) target_list.append(element)
Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
def In_Common_Block(x,y): def Add_Item_To_List_If_New(target_list, item):
if ( (x.block_id == y.block_id) if item not in target_list:
or ( x is y.localroot) or (y is x.localroot) ): target_list.append(item)
return True
return False
def Copy_List_Items(target_list, source_list): def Store_Results(y, direction):
del target_list[:] # Python idiom to remove all elements of a list if direction == 'INCREASING':
for element in source_list: y.HIGHER = True
target_list.append(element) Copy_List_Items(y.blue_next_hops, y.next_hops)
if direction == 'DECREASING':
y.LOWER = True
Copy_List_Items(y.red_next_hops, y.next_hops)
if direction == 'NORMAL_SPF':
y.primary_spf_metric = y.spf_metric
Copy_List_Items(y.primary_next_hops, y.next_hops)
if direction == 'MRT_ISLAND_SPF':
def Add_Item_To_List_If_New(target_list, item): Copy_List_Items(y.mrt_island_next_hops, y.next_hops)
if item not in target_list: if direction == 'COLLAPSED_SPF':
target_list.append(item) y.collapsed_metric = y.spf_metric
Copy_List_Items(y.collapsed_next_hops, y.next_hops)
def Store_Results(y, direction): # Note that the Python heapq fucntion allows for duplicate items,
if direction == 'INCREASING': # so we use the 'spf_visited' property to only consider a node
y.HIGHER = True # as min_node the first time it gets removed from the heap.
Copy_List_Items(y.blue_next_hops, y.next_hops) def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction):
if direction == 'DECREASING': spf_heap = []
y.LOWER = True for y in topo.island_node_list:
Copy_List_Items(y.red_next_hops, y.next_hops) y.spf_metric = 2147483647 # 2^31-1
if direction == 'NORMAL_SPF': y.next_hops = []
y.primary_spf_metric = y.spf_metric y.spf_visited = False
Copy_List_Items(y.primary_next_hops, y.next_hops) spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric, spf_root.node_id, spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, direction)
if ( (min_node is spf_root) or (min_node is not block_root) ):
for intf in min_node.island_intf_list:
if ( ( (direction == 'INCREASING' and intf.OUTGOING )
or (direction == 'DECREASING' and intf.INCOMING ) )
and In_Common_Block(spf_root, intf.remote_node) ) :
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
if direction == 'MRT_ISLAND_SPF': def Normal_SPF(topo, spf_root):
Copy_List_Items(y.mrt_island_next_hops, y.next_hops) spf_heap = []
if direction == 'COLLAPSED_SPF': for y in topo.node_list:
y.collapsed_metric = y.spf_metric y.spf_metric = 2147483647 # 2^31-1 as max metric
Copy_List_Items(y.collapsed_next_hops, y.next_hops) y.next_hops = []
y.primary_spf_metric = 2147483647
y.primary_next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric,spf_root.node_id,spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, 'NORMAL_SPF')
for intf in min_node.intf_list:
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
# Note that the Python heapq fucntion allows for duplicate items, def Set_Edge(y):
# so we use the 'spf_visited' property to only consider a node if (y.blue_next_hops == [] and y.red_next_hops == []):
# as min_node the first time it gets removed from the heap. Set_Edge(y.localroot)
def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction): Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops)
spf_heap = [] Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops)
for y in topo.island_node_list: y.order_proxy = y.localroot.order_proxy
y.spf_metric = 2147483647 # 2^31-1
y.next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric, spf_root.node_id, spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, direction)
if ( (min_node is spf_root) or (min_node is not block_root) ):
for intf in min_node.island_intf_list:
if ( ( (direction == 'INCREASING' and intf.OUTGOING )
or (direction == 'DECREASING' and intf.INCOMING ) )
and In_Common_Block(spf_root, intf.remote_node) ) :
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New( def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x):
intf.remote_node.next_hops,nh_intf) for y in topo.island_node_list:
y.HIGHER = False
y.LOWER = False
y.red_next_hops = []
y.blue_next_hops = []
y.order_proxy = y
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING')
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING')
for y in topo.island_node_list:
if ( y is not x and (y.block_id == x.block_id) ):
assert (not ( y is x.localroot or x is y.localroot) )
assert(not (y.HIGHER and y.LOWER) )
if y.HIGHER == True:
Copy_List_Items(y.red_next_hops,
x.localroot.red_next_hops)
elif y.LOWER == True:
Copy_List_Items(y.blue_next_hops,
x.localroot.blue_next_hops)
else:
Copy_List_Items(y.blue_next_hops,
x.localroot.red_next_hops)
Copy_List_Items(y.red_next_hops,
x.localroot.blue_next_hops)
def Normal_SPF(topo, spf_root): # Inherit x's MRT next-hops to reach the GADAG root
spf_heap = [] # from x's MRT next-hops to reach its local root,
for y in topo.node_list: # but first check if x is the gadag_root (in which case
y.spf_metric = 2147483647 # 2^31-1 as max metric # x does not have a local root) or if x's local root
y.next_hops = [] # is the gadag root (in which case we already have the
y.primary_spf_metric = 2147483647 # x's MRT next-hops to reach the gadag root)
y.primary_next_hops = [] if x is not topo.gadag_root and x.localroot is not topo.gadag_root:
y.spf_visited = False Copy_List_Items(topo.gadag_root.blue_next_hops,
spf_root.spf_metric = 0 x.localroot.blue_next_hops)
heapq.heappush(spf_heap, Copy_List_Items(topo.gadag_root.red_next_hops,
(spf_root.spf_metric,spf_root.node_id,spf_root) ) x.localroot.red_next_hops)
while spf_heap != []: topo.gadag_root.order_proxy = x.localroot
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, 'NORMAL_SPF')
for intf in min_node.intf_list:
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
def Set_Edge(y): # Inherit next-hops and order_proxies to other blocks
if (y.blue_next_hops == [] and y.red_next_hops == []): for y in topo.island_node_list:
Set_Edge(y.localroot) if (y is not topo.gadag_root and y is not x ):
Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops) Set_Edge(y)
Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops)
y.order_proxy = y.localroot.order_proxy
def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x): def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list: for y in topo.island_node_list:
y.HIGHER = False if y is x:
y.LOWER = False continue
y.red_next_hops = [] x.blue_next_hops_dict[y.node_id] = []
y.blue_next_hops = [] x.red_next_hops_dict[y.node_id] = []
y.order_proxy = y Copy_List_Items(x.blue_next_hops_dict[y.node_id],
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING') y.blue_next_hops)
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING') Copy_List_Items(x.red_next_hops_dict[y.node_id],
for y in topo.island_node_list: y.red_next_hops)
if ( y is not x and (y.block_id == x.block_id) ):
assert (not ( y is x.localroot or x is y.localroot) )
assert(not (y.HIGHER and y.LOWER) )
if y.HIGHER == True:
Copy_List_Items(y.red_next_hops,
x.localroot.red_next_hops)
elif y.LOWER == True:
Copy_List_Items(y.blue_next_hops,
x.localroot.blue_next_hops)
else:
Copy_List_Items(y.blue_next_hops,
x.localroot.red_next_hops)
Copy_List_Items(y.red_next_hops,
x.localroot.blue_next_hops)
# Inherit x's MRT next-hops to reach the GADAG root def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x):
# from x's MRT next-hops to reach its local root, for y in topo.island_node_list:
# but first check if x is the gadag_root (in which case x.pnh_dict[y.node_id] = []
# x does not have a local root) or if x's local root Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
# is the gadag root (in which case we already have the x.alt_dict[y.node_id] = []
# x's MRT next-hops to reach the gadag root) Copy_List_Items(x.alt_dict[y.node_id], y.alt_list)
if x is not topo.gadag_root and x.localroot is not topo.gadag_root:
Copy_List_Items(topo.gadag_root.blue_next_hops,
x.localroot.blue_next_hops)
Copy_List_Items(topo.gadag_root.red_next_hops,
x.localroot.red_next_hops)
topo.gadag_root.order_proxy = x.localroot
# Inherit next-hops and order_proxies to other blocks def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x):
for y in topo.island_node_list: for y in topo.node_list:
if (y is not topo.gadag_root and y is not x ): x.pnh_dict[y.node_id] = []
Set_Edge(y) Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x): def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for y in topo.island_node_list: for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.blue_next_hops_dict[P.node_id] = []
x.red_next_hops_dict[P.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[P.node_id],
P.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[P.node_id],
P.red_next_hops)
if y is x: def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x):
continue for prefix in topo.named_proxy_dict:
x.blue_next_hops_dict[y.node_id] = [] P = topo.named_proxy_dict[prefix]
x.red_next_hops_dict[y.node_id] = [] x.alt_dict[P.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[y.node_id], Copy_List_Items(x.alt_dict[P.node_id],
y.blue_next_hops) P.alt_list)
Copy_List_Items(x.red_next_hops_dict[y.node_id],
y.red_next_hops)
def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x): def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for y in topo.island_node_list: for prefix in topo.named_proxy_dict:
x.pnh_dict[y.node_id] = [] P = topo.named_proxy_dict[prefix]
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) x.pnh_dict[P.node_id] = []
x.alt_dict[y.node_id] = [] Copy_List_Items(x.pnh_dict[P.node_id],
Copy_List_Items(x.alt_dict[y.node_id], y.alt_list) P.primary_next_hops)
def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): def Select_Alternates_Internal(D, F, primary_intf,
for prefix in topo.named_proxy_dict: D_lower, D_higher, D_topo_order):
P = topo.named_proxy_dict[prefix] if D_higher and D_lower:
x.blue_next_hops_dict[P.node_id] = [] if F.HIGHER and F.LOWER:
x.red_next_hops_dict[P.node_id] = [] if F.topo_order > D_topo_order:
Copy_List_Items(x.blue_next_hops_dict[P.node_id], return 'USE_BLUE'
P.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[P.node_id],
P.red_next_hops)
if P.convert_blue_to_green:
x.blue_to_green_nh_dict[P.node_id] = True
if P.convert_red_to_green:
x.red_to_green_nh_dict[P.node_id] = True
def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x): else:
for prefix in topo.named_proxy_dict: return 'USE_RED'
P = topo.named_proxy_dict[prefix] if F.HIGHER:
x.alt_dict[P.node_id] = [] return 'USE_RED'
Copy_List_Items(x.alt_dict[P.node_id], if F.LOWER:
P.alt_list) return 'USE_BLUE'
assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED_OR_BLUE'
if D_higher:
if F.HIGHER and F.LOWER:
return 'USE_BLUE'
if F.LOWER:
return 'USE_BLUE'
if F.HIGHER:
if (F.topo_order > D_topo_order):
return 'USE_BLUE'
if (F.topo_order < D_topo_order):
return 'USE_RED'
assert(False)
assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED_OR_BLUE'
if D_lower:
if F.HIGHER and F.LOWER:
return 'USE_RED'
if F.HIGHER:
return 'USE_RED'
if F.LOWER:
if F.topo_order > D_topo_order:
return 'USE_BLUE'
if F.topo_order < D_topo_order:
return 'USE_RED'
assert(False)
assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED_OR_BLUE'
else: # D is unordered wrt S
if F.HIGHER and F.LOWER:
if primary_intf.OUTGOING and primary_intf.INCOMING:
# This can happen when the primary next hop goes
# to a node in a different block and D is
# unordered wrt S.
return 'USE_RED_OR_BLUE'
if primary_intf.OUTGOING:
return 'USE_BLUE'
if primary_intf.INCOMING:
return 'USE_RED'
def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x): #This can occur when primary_intf is MRT_INELIGIBLE.
for y in topo.node_list: #This appears to be a case where the special
x.pnh_dict[y.node_id] = [] #construction of the GADAG allows us to choose red,
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops) #whereas with an arbitrary GADAG, neither red nor blue
#is guaranteed to work.
assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE)
return 'USE_RED'
if F.LOWER:
return 'USE_RED'
if F.HIGHER:
return 'USE_BLUE'
assert(primary_intf.MRT_INELIGIBLE
or primary_intf.remote_intf.MRT_INELIGIBLE)
if F.topo_order > D_topo_order:
return 'USE_BLUE'
else:
return 'USE_RED'
def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x): def Select_Alternates(D, F, primary_intf):
for prefix in topo.named_proxy_dict: S = primary_intf.local_node
P = topo.named_proxy_dict[prefix] if not In_Common_Block(F, S):
x.pnh_dict[P.node_id] = [] return 'PRIM_NH_IN_DIFFERENT_BLOCK'
Copy_List_Items(x.pnh_dict[P.node_id], if (D is F) or (D.order_proxy is F):
P.primary_next_hops) return 'PRIM_NH_IS_D_OR_OP_FOR_D'
D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order)
def Select_Alternates_Internal(D, F, primary_intf, def Is_Remote_Node_In_NH_List(node, intf_list):
D_lower, D_higher, D_topo_order): for intf in intf_list:
if node is intf.remote_node:
return True
return False
if D_higher and D_lower: def Select_Alts_For_One_Src_To_Island_Dests(topo,x):
if F.HIGHER and F.LOWER: Normal_SPF(topo, x)
if F.topo_order > D_topo_order: for D in topo.island_node_list:
return 'USE_BLUE' D.alt_list = []
else: if D is x:
return 'USE_RED' continue
if F.HIGHER: for failed_intf in D.primary_next_hops:
return 'USE_RED' alt = Alternate()
if F.LOWER: alt.failed_intf = failed_intf
return 'USE_BLUE' cand_alt_list = []
assert(False) F = failed_intf.remote_node
if D_higher: #We need to test if F is in the island, as opposed
if F.HIGHER and F.LOWER: #to just testing if failed_intf is in island_intf_list,
return 'USE_BLUE' #because failed_intf could be marked as MRT_INELIGIBLE.
if F.LOWER: if F in topo.island_node_list:
return 'USE_BLUE' alt.info = Select_Alternates(D, F, failed_intf)
if F.HIGHER: else:
if (F.topo_order > D_topo_order): #The primary next-hop is not in the MRT Island.
return 'USE_BLUE' #Either red or blue will avoid the primary next-hop,
if (F.topo_order < D_topo_order): #because the primary next-hop is not even in the
return 'USE_RED' #GADAG.
assert(False) alt.info = 'USE_RED_OR_BLUE'
assert(False)
if D_lower:
if F.HIGHER and F.LOWER:
return 'USE_RED'
if F.HIGHER:
return 'USE_RED'
if F.LOWER:
if F.topo_order > D_topo_order:
return 'USE_BLUE'
if F.topo_order < D_topo_order:
return 'USE_RED'
assert(False)
assert(False)
else: # D is unordered wrt S
if F.HIGHER and F.LOWER:
if primary_intf.OUTGOING and primary_intf.INCOMING:
assert(False)
if primary_intf.OUTGOING:
# this case isn't hit it topo-9e
return 'USE_BLUE'
if primary_intf.INCOMING:
return 'USE_RED'
assert(False)
if F.LOWER: if (alt.info == 'USE_RED_OR_BLUE'):
return 'USE_RED' alt.red_or_blue = random.choice(['USE_RED','USE_BLUE'])
if F.HIGHER: if (alt.info == 'USE_BLUE'
return 'USE_BLUE' or alt.red_or_blue == 'USE_BLUE'):
assert(False) Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_RED' or alt.red_or_blue == 'USE_RED'):
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'PRIM_NH_IN_DIFFERENT_BLOCK'):
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'):
if failed_intf.OUTGOING and failed_intf.INCOMING:
# cut-link: if there are parallel cut links, use
# the link(s) with lowest metric that are not
# primary intf or None
cand_alt_list = [None]
min_metric = 2147483647
for intf in x.island_intf_list:
if ( intf is not failed_intf and
(intf.remote_node is
failed_intf.remote_node)):
if intf.metric < min_metric:
cand_alt_list = [intf]
min_metric = intf.metric
elif intf.metric == min_metric:
cand_alt_list.append(intf)
if cand_alt_list != [None]:
alt.fec = 'GREEN'
alt.prot = 'PARALLEL_CUTLINK'
else:
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
Copy_List_Items(alt.nh_list, cand_alt_list)
def Select_Alternates(D, F, primary_intf): # Use Is_Remote_Node_In_NH_List() is used, as opposed
if (D is F) or (D.order_proxy is F): # to just checking if failed_intf is in D.red_next_hops,
return 'PRIM_NH_IS_D_OR_OP_FOR_D' # because failed_intf could be marked as MRT_INELIGIBLE.
D_lower = D.order_proxy.LOWER elif Is_Remote_Node_In_NH_List(F, D.red_next_hops):
D_higher = D.order_proxy.HIGHER Copy_List_Items(alt.nh_list, D.blue_next_hops)
D_topo_order = D.order_proxy.topo_order alt.fec = 'BLUE'
return Select_Alternates_Internal(D, F, primary_intf, alt.prot = 'LINK_PROTECTION'
D_lower, D_higher, D_topo_order) else:
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)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
def Select_Alts_For_One_Src_To_Island_Dests(topo,x): # working version but has issue with MRT_INELIGIBLE link being
Normal_SPF(topo, x) # primary_NH
for D in topo.island_node_list: # elif failed_intf in D.red_next_hops:
D.alt_list = [] # Copy_List_Items(alt.nh_list, D.blue_next_hops)
if D is x: # alt.fec = 'BLUE'
continue # alt.prot = 'LINK_PROTECTION'
for primary_intf in D.primary_next_hops: # else:
alt = Alternate() # Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.failed_intf = primary_intf # alt.fec = 'RED'
if primary_intf in x.island_intf_list: # alt.prot = 'LINK_PROTECTION'
alt.info = Select_Alternates(D, D.alt_list.append(alt)
primary_intf.remote_node, primary_intf)
else:
alt.info = 'PRIM_NH_NOT_IN_ISLAND'
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_BLUE'):
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'USE_RED'):
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'NODE_PROTECTION'
if (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'):
if primary_intf.OUTGOING and primary_intf.INCOMING:
# cut-link: if there are parallel cut links, use
# the link(s) with lowest metric that are not
# primary intf or None
cand_alt_list = [None]
min_metric = 2147483647
for intf in x.island_intf_list:
if ( intf is not primary_intf and def Write_GADAG_To_File(topo, file_prefix):
(intf.remote_node is gadag_edge_list = []
primary_intf.remote_node)): for node in topo.node_list:
if intf.metric < min_metric: for intf in node.intf_list:
cand_alt_list = [intf] if intf.SIMULATION_OUTGOING:
min_metric = intf.metric local_node = "%04d" % (intf.local_node.node_id)
elif intf.metric == min_metric: remote_node = "%04d" % (intf.remote_node.node_id)
cand_alt_list.append(intf) intf_data = "%03d" % (intf.link_data)
if cand_alt_list != [None]: edge_string=(local_node+','+remote_node+','+
alt.fec = 'GREEN' intf_data+'\n')
alt.prot = 'PARALLEL_CUTLINK' gadag_edge_list.append(edge_string)
else: gadag_edge_list.sort();
alt.fec = 'NO_ALTERNATE' filename = file_prefix + '_gadag.csv'
alt.prot = 'NO_PROTECTION' with open(filename, 'w') as gadag_file:
Copy_List_Items(alt.nh_list, cand_alt_list) gadag_file.write('local_node,'\
elif primary_intf in D.red_next_hops: 'remote_node,local_intf_link_data\n')
Copy_List_Items(alt.nh_list, D.blue_next_hops) for edge_string in gadag_edge_list:
alt.fec = 'BLUE' gadag_file.write(edge_string);
alt.prot = 'LINK_PROTECTION'
else:
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
D.alt_list.append(alt)
def Write_GADAG_To_File(topo, file_prefix): def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix):
gadag_edge_list = [] edge_list = []
for node in topo.island_node_list: for node in topo.island_node_list_for_test_gr:
for intf in node.island_intf_list: if color == 'blue':
if intf.OUTGOING: node_next_hops_dict = node.blue_next_hops_dict
local_node = "%04d" % (intf.local_node.node_id) elif color == 'red':
remote_node = "%04d" % (intf.remote_node.node_id) node_next_hops_dict = node.red_next_hops_dict
intf_data = "%03d" % (intf.link_data) for dest_node_id in node_next_hops_dict:
edge_string=(local_node+','+remote_node+','+ for intf in node_next_hops_dict[dest_node_id]:
intf_data+'\n') gadag_root = "%04d" % (topo.gadag_root.node_id)
gadag_edge_list.append(edge_string) dest_node = "%04d" % (dest_node_id)
gadag_edge_list.sort(); local_node = "%04d" % (intf.local_node.node_id)
filename = file_prefix + '_gadag.csv' remote_node = "%04d" % (intf.remote_node.node_id)
with open(filename, 'w') as gadag_file: intf_data = "%03d" % (intf.link_data)
gadag_file.write('local_node,'\ edge_string=(gadag_root+','+dest_node+','+local_node+
'remote_node,local_intf_link_data\n') ','+remote_node+','+intf_data+'\n')
for edge_string in gadag_edge_list: edge_list.append(edge_string)
gadag_file.write(edge_string); edge_list.sort()
filename = file_prefix + '_' + color + '_to_all.csv'
with open(filename, 'w') as mrt_file:
mrt_file.write('gadag_root,dest,'\
'local_node,remote_node,link_data\n')
for edge_string in edge_list:
mrt_file.write(edge_string);
def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix): def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix):
edge_list = [] Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix)
for node in topo.island_node_list: Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix)
if color == 'blue':
node_next_hops_dict = node.blue_next_hops_dict def Write_Alternates_For_All_Dests_To_File(topo, file_prefix):
elif color == 'red': edge_list = []
node_next_hops_dict = node.red_next_hops_dict for x in topo.island_node_list_for_test_gr:
for dest_node_id in node_next_hops_dict: for dest_node_id in x.alt_dict:
for intf in node_next_hops_dict[dest_node_id]: alt_list = x.alt_dict[dest_node_id]
gadag_root = "%04d" % (topo.gadag_root.node_id) for alt in alt_list:
dest_node = "%04d" % (dest_node_id) for alt_intf in alt.nh_list:
local_node = "%04d" % (intf.local_node.node_id) gadag_root = "%04d" % (topo.gadag_root.node_id)
remote_node = "%04d" % (intf.remote_node.node_id) dest_node = "%04d" % (dest_node_id)
intf_data = "%03d" % (intf.link_data) prim_local_node = \
edge_string=(gadag_root+','+dest_node+','+local_node+ "%04d" % (alt.failed_intf.local_node.node_id)
','+remote_node+','+intf_data+'\n') prim_remote_node = \
edge_list.append(edge_string) "%04d" % (alt.failed_intf.remote_node.node_id)
edge_list.sort() prim_intf_data = \
filename = file_prefix + '_' + color + '_to_all.csv' "%03d" % (alt.failed_intf.link_data)
with open(filename, 'w') as mrt_file: if alt_intf == None:
mrt_file.write('gadag_root,dest,'\ alt_local_node = "None"
'local_node,remote_node,link_data\n') alt_remote_node = "None"
for edge_string in edge_list: alt_intf_data = "None"
mrt_file.write(edge_string);
def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix): else:
Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix) alt_local_node = \
Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix) "%04d" % (alt_intf.local_node.node_id)
alt_remote_node = \
"%04d" % (alt_intf.remote_node.node_id)
alt_intf_data = \
"%03d" % (alt_intf.link_data)
edge_string = (gadag_root+','+dest_node+','+
prim_local_node+','+prim_remote_node+','+
prim_intf_data+','+alt_local_node+','+
alt_remote_node+','+alt_intf_data+','+
alt.fec +'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_alts_to_all.csv'
with open(filename, 'w') as alt_file:
alt_file.write('gadag_root,dest,'\
'prim_nh.local_node,prim_nh.remote_node,'\
'prim_nh.link_data,alt_nh.local_node,'\
'alt_nh.remote_node,alt_nh.link_data,'\
'alt_nh.fec\n')
for edge_string in edge_list:
alt_file.write(edge_string);
def Write_Alternates_For_All_Dests_To_File(topo, file_prefix): def Raise_GADAG_Root_Selection_Priority(topo,node_id):
edge_list = [] node = topo.node_dict[node_id]
for x in topo.island_node_list: node.GR_sel_priority = 255
for dest_node_id in x.alt_dict:
alt_list = x.alt_dict[dest_node_id]
for alt in alt_list:
for alt_intf in alt.nh_list:
gadag_root = "%04d" % (topo.gadag_root.node_id)
dest_node = "%04d" % (dest_node_id)
prim_local_node = \
"%04d" % (alt.failed_intf.local_node.node_id)
prim_remote_node = \
"%04d" % (alt.failed_intf.remote_node.node_id)
prim_intf_data = \
"%03d" % (alt.failed_intf.link_data)
if alt_intf == None:
alt_local_node = "None"
alt_remote_node = "None"
alt_intf_data = "None"
else:
alt_local_node = \
"%04d" % (alt_intf.local_node.node_id)
alt_remote_node = \
"%04d" % (alt_intf.remote_node.node_id)
alt_intf_data = \
"%03d" % (alt_intf.link_data)
edge_string = (gadag_root+','+dest_node+','+
prim_local_node+','+prim_remote_node+','+
prim_intf_data+','+alt_local_node+','+
alt_remote_node+','+alt_intf_data+','+
alt.fec +'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_alts_to_all.csv'
with open(filename, 'w') as alt_file:
alt_file.write('gadag_root,dest,'\
'prim_nh.local_node,prim_nh.remote_node,'\
'prim_nh.link_data,alt_nh.local_node,'\
'alt_nh.remote_node,alt_nh.link_data,'\
'alt_nh.fec\n')
for edge_string in edge_list:
alt_file.write(edge_string);
def Raise_GADAG_Root_Selection_Priority(topo,node_id): def Lower_GADAG_Root_Selection_Priority(topo,node_id):
node = topo.node_dict[node_id] node = topo.node_dict[node_id]
node.GR_sel_priority = 255 node.GR_sel_priority = 128
def Lower_GADAG_Root_Selection_Priority(topo,node_id): def GADAG_Root_Compare(node_a, node_b):
node = topo.node_dict[node_id] if (node_a.GR_sel_priority > node_b.GR_sel_priority):
node.GR_sel_priority = 128 return 1
elif (node_a.GR_sel_priority < node_b.GR_sel_priority):
return -1
else:
if node_a.node_id > node_b.node_id:
return 1
elif node_a.node_id < node_b.node_id:
return -1
def GADAG_Root_Compare(node_a, node_b): def Set_GADAG_Root(topo,computing_router):
if (node_a.GR_sel_priority > node_b.GR_sel_priority): gadag_root_list = []
return 1 for node in topo.island_node_list:
elif (node_a.GR_sel_priority < node_b.GR_sel_priority): gadag_root_list.append(node)
return -1 gadag_root_list.sort(GADAG_Root_Compare)
else: topo.gadag_root = gadag_root_list.pop()
if node_a.node_id > node_b.node_id:
return 1
elif node_a.node_id < node_b.node_id:
return -1
def Set_GADAG_Root(topo,computing_router): def Add_Prefix_Advertisements_From_File(topo, filename):
gadag_root_list = [] prefix_filename = filename + '.prefix'
for node in topo.island_node_list: cols_list = []
gadag_root_list.append(node) if not os.path.exists(prefix_filename):
gadag_root_list.sort(GADAG_Root_Compare) return
topo.gadag_root = gadag_root_list.pop() with open(prefix_filename) as prefix_file:
for line in prefix_file:
line = line.rstrip('\r\n')
cols=line.split(',')
cols_list.append(cols)
prefix_id = int(cols[0])
if prefix_id < 2000 or prefix_id >2999:
print('skipping the following line of prefix file')
print('prefix id should be between 2000 and 2999')
print(line)
continue
prefix_node_id = int(cols[1])
prefix_cost = int(cols[2])
advertising_node = topo.node_dict[prefix_node_id]
advertising_node.prefix_cost_dict[prefix_id] = prefix_cost
def Run_MRT_for_One_Source(topo, src): def Add_Prefixes_for_Non_Island_Nodes(topo):
Reset_Computed_Node_and_Intf_Values(topo) for node in topo.node_list:
MRT_Island_Identification(topo, src, 0, 0) if node.IN_MRT_ISLAND:
Set_Island_Intf_and_Node_Lists(topo) continue
Set_GADAG_Root(topo,src) prefix_id = node.node_id + 1000
Sort_Interfaces(topo) node.prefix_cost_dict[prefix_id] = 0
Run_Lowpoint(topo)
Assign_Remaining_Lowpoint_Parents(topo)
Construct_GADAG_via_Lowpoint(topo)
Run_Assign_Block_ID(topo)
Add_Undirected_Links(topo)
Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src)
Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src)
Select_Alts_For_One_Src_To_Island_Dests(topo,src)
Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src)
def Run_Prim_SPF_for_One_Source(topo,src): def Add_Profile_IDs_from_File(topo, filename):
Normal_SPF(topo, src) profile_filename = filename + '.profile'
Store_Primary_NHs_For_One_Source_To_Nodes(topo,src) for node in topo.node_list:
node.profile_id_list = []
cols_list = []
if os.path.exists(profile_filename):
with open(profile_filename) as profile_file:
for line in profile_file:
line = line.rstrip('\r\n')
cols=line.split(',')
cols_list.append(cols)
node_id = int(cols[0])
profile_id = int(cols[1])
this_node = topo.node_dict[node_id]
this_node.profile_id_list.append(profile_id)
else:
for node in topo.node_list:
node.profile_id_list = [0]
def Run_MRT_for_All_Sources(topo): def Island_Marking_SPF(topo,spf_root):
for src in topo.node_list: spf_root.isl_marking_spf_dict = {}
if 0 in src.profile_id_list: for y in topo.node_list:
# src runs MRT if it has profile_id=0 y.spf_metric = 2147483647 # 2^31-1 as max metric
Run_MRT_for_One_Source(topo,src) y.PATH_HITS_ISLAND = False
else: y.next_hops = []
# still run SPF for nodes not running MRT y.spf_visited = False
Run_Prim_SPF_for_One_Source(topo,src) spf_root.spf_metric = 0
spf_heap = []
heapq.heappush(spf_heap,
(spf_root.spf_metric,spf_root.node_id,spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
spf_root.isl_marking_spf_dict[min_node.node_id] = \
(min_node.spf_metric, min_node.PATH_HITS_ISLAND)
for intf in min_node.intf_list:
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
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
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
if (intf.remote_node.IN_MRT_ISLAND):
intf.remote_node.PATH_HITS_ISLAND = True
else:
def Write_Output_To_Files(topo,file_prefix): if (intf.remote_node.PATH_HITS_ISLAND
Write_GADAG_To_File(topo,file_prefix) or min_node.PATH_HITS_ISLAND):
Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix) intf.remote_node.PATH_HITS_ISLAND = True
Write_Alternates_For_All_Dests_To_File(topo,file_prefix)
def Create_Example_Topology_Input_File(filename): def Create_Basic_Named_Proxy_Nodes(topo):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10], for node in topo.node_list:
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10], for prefix in node.prefix_cost_dict:
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10], prefix_cost = node.prefix_cost_dict[prefix]
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10], if prefix in topo.named_proxy_dict:
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10], P = topo.named_proxy_dict[prefix]
[78,79,10],[79,77,10]] P.node_prefix_cost_list.append((node,prefix_cost))
with open(filename, 'w') as topo_file: else:
for item in data: P = Named_Proxy_Node()
if len(item) > 3: topo.named_proxy_dict[prefix] = P
line = (str(item[0])+','+str(item[1])+','+ P.node_id = prefix
str(item[2])+','+str(item[3])+'\n') P.node_prefix_cost_list = [(node,prefix_cost)]
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Generate_Example_Topology_and_Run_MRT(): def Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo):
Create_Example_Topology_Input_File('example_topo_input_file.csv') topo.island_nbr_set = set()
topo = Create_Topology_From_File('example_topo_input_file.csv') topo.island_border_set = set()
res_file_base = 'example_topo' for node in topo.node_list:
Raise_GADAG_Root_Selection_Priority(topo,3) if node.IN_MRT_ISLAND:
Run_MRT_for_All_Sources(topo) continue
Write_Output_To_Files(topo, res_file_base) for intf in node.intf_list:
if intf.remote_node.IN_MRT_ISLAND:
topo.island_nbr_set.add(node)
topo.island_border_set.add(intf.remote_node)
Generate_Example_Topology_and_Run_MRT() for island_nbr in topo.island_nbr_set:
Island_Marking_SPF(topo,island_nbr)
<CODE ENDS> for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
P.lfin_list = []
for island_nbr in topo.island_nbr_set:
min_isl_nbr_to_pref_cost = 2147483647
for (adv_node, prefix_cost) in P.node_prefix_cost_list:
(adv_node_cost, path_hits_island) = \
island_nbr.isl_marking_spf_dict[adv_node.node_id]
isl_nbr_to_pref_cost = adv_node_cost + prefix_cost
if isl_nbr_to_pref_cost < min_isl_nbr_to_pref_cost:
min_isl_nbr_to_pref_cost = isl_nbr_to_pref_cost
min_path_hits_island = path_hits_island
elif isl_nbr_to_pref_cost == min_isl_nbr_to_pref_cost:
if min_path_hits_island or path_hits_island:
min_path_hits_island = True
if not min_path_hits_island:
8. Algorithm Alternatives and Evaluation P.lfin_list.append( (island_nbr,
min_isl_nbr_to_pref_cost) )
def Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo):
for ibr in topo.island_border_set:
ibr.prefix_lfin_dict = {}
ibr.min_intf_metric_dict = {}
ibr.min_intf_list_dict = {}
ibr.min_intf_list_dict[None] = None
for intf in ibr.intf_list:
if not intf.remote_node in topo.island_nbr_set:
continue
if not intf.remote_node in ibr.min_intf_metric_dict:
ibr.min_intf_metric_dict[intf.remote_node] = \
intf.metric
ibr.min_intf_list_dict[intf.remote_node] = [intf]
else:
if (intf.metric
< ibr.min_intf_metric_dict[intf.remote_node]):
ibr.min_intf_metric_dict[intf.remote_node] = \
intf.metric
ibr.min_intf_list_dict[intf.remote_node] = [intf]
elif (intf.metric
< ibr.min_intf_metric_dict[intf.remote_node]):
ibr.min_intf_list_dict[intf.remote_node].\
append(intf)
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
for ibr in topo.island_border_set:
min_ibr_lfin_pref_cost = 2147483647
min_lfin = None
for (lfin, lfin_to_pref_cost) in P.lfin_list:
if not lfin in ibr.min_intf_metric_dict:
continue
ibr_lfin_pref_cost = \
ibr.min_intf_metric_dict[lfin] + lfin_to_pref_cost
if ibr_lfin_pref_cost < min_ibr_lfin_pref_cost:
min_ibr_lfin_pref_cost = ibr_lfin_pref_cost
min_lfin = lfin
ibr.prefix_lfin_dict[prefix] = (min_lfin,
min_ibr_lfin_pref_cost,
ibr.min_intf_list_dict[min_lfin])
def Proxy_Node_Att_Router_Compare(pnar_a, pnar_b):
if pnar_a.named_proxy_cost < pnar_b.named_proxy_cost:
return -1
if pnar_b.named_proxy_cost < pnar_a.named_proxy_cost:
return 1
if pnar_a.node.node_id < pnar_b.node.node_id:
return -1
if pnar_b.node.node_id < pnar_a.node.node_id:
return 1
if pnar_a.min_lfin == None:
return -1
if pnar_b.min_lfin == None:
return 1
def Choose_Proxy_Node_Attachment_Routers(topo):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
pnar_candidate_list = []
for (node, prefix_cost) in P.node_prefix_cost_list:
if not node.IN_MRT_ISLAND:
continue
pnar = Proxy_Node_Attachment_Router()
pnar.prefix = prefix
pnar.named_proxy_cost = prefix_cost
pnar.node = node
pnar_candidate_list.append(pnar)
for ibr in topo.island_border_set:
(min_lfin, prefix_cost, min_intf_list) = \
ibr.prefix_lfin_dict[prefix]
if min_lfin == None:
continue
pnar = Proxy_Node_Attachment_Router()
pnar.named_proxy_cost = prefix_cost
pnar.node = ibr
pnar.min_lfin = min_lfin
pnar.nh_intf_list = min_intf_list
pnar_candidate_list.append(pnar)
pnar_candidate_list.sort(cmp=Proxy_Node_Att_Router_Compare)
#pop first element from list
first_pnar = pnar_candidate_list.pop(0)
second_pnar = None
for next_pnar in pnar_candidate_list:
if next_pnar.node is first_pnar.node:
continue
second_pnar = next_pnar
break
P.pnar1 = first_pnar
P.pnar2 = second_pnar
def Attach_Named_Proxy_Nodes(topo):
Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo)
Compute_Island_Border_Router_LFIN_Pairs_For_Each_Prefix(topo)
Choose_Proxy_Node_Attachment_Routers(topo)
def Select_Proxy_Node_NHs(P,S):
if P.pnar1.node.node_id < P.pnar2.node.node_id:
X = P.pnar1.node
Y = P.pnar2.node
else:
X = P.pnar2.node
Y = P.pnar1.node
P.pnar_X = X
P.pnar_Y = Y
A = X.order_proxy
B = Y.order_proxy
if (A is S.localroot
and B is S.localroot):
#print("1.0")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is S.localroot
and B is not S.localroot):
#print("2.0")
if B.LOWER:
#print("2.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if B.HIGHER:
#print("2.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("2.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is not S.localroot
and B is S.localroot):
#print("3.0")
if A.LOWER:
#print("3.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if A.HIGHER:
#print("3.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("3.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if (A is not S.localroot
and B is not S.localroot):
#print("4.0")
if (S is A.localroot or S is B.localroot):
#print("4.05")
if A.topo_order < B.topo_order:
#print("4.05.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.05.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if A.LOWER:
#print("4.1")
if B.HIGHER:
#print("4.1.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if B.LOWER:
#print("4.1.2")
if A.topo_order < B.topo_order:
#print("4.1.2.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.1.2.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.1.3")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if A.HIGHER:
#print("4.2")
if B.HIGHER:
#print("4.2.1")
if A.topo_order < B.topo_order:
#print("4.2.1.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.2.1.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
if B.LOWER:
#print("4.2.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.2.3")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.3")
if B.LOWER:
#print("4.3.1")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
if B.HIGHER:
#print("4.3.2")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
else:
#print("4.3.3")
if A.topo_order < B.topo_order:
#print("4.3.3.1")
Copy_List_Items(P.blue_next_hops, X.blue_next_hops)
Copy_List_Items(P.red_next_hops, Y.red_next_hops)
return
else:
#print("4.3.3.2")
Copy_List_Items(P.blue_next_hops, X.red_next_hops)
Copy_List_Items(P.red_next_hops, Y.blue_next_hops)
return
assert(False)
def Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,S):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
if P.pnar2 == None:
if S is P.pnar1.node:
# set the MRT next-hops for the PNAR to
# reach the LFIN and change FEC to green
Copy_List_Items(P.blue_next_hops,
P.pnar1.nh_intf_list)
S.blue_to_green_nh_dict[P.node_id] = True
Copy_List_Items(P.red_next_hops,
P.pnar1.nh_intf_list)
S.red_to_green_nh_dict[P.node_id] = True
else:
# inherit MRT NHs for P from pnar1
Copy_List_Items(P.blue_next_hops,
P.pnar1.node.blue_next_hops)
Copy_List_Items(P.red_next_hops,
P.pnar1.node.red_next_hops)
else:
Select_Proxy_Node_NHs(P,S)
# set the MRT next-hops for the PNAR to reach the LFIN
# and change FEC to green rely on the red or blue
# next-hops being empty to figure out which one needs
# to point to the LFIN.
if S is P.pnar1.node:
this_pnar = P.pnar1
elif S is P.pnar2.node:
this_pnar = P.pnar2
else:
continue
if P.blue_next_hops == []:
Copy_List_Items(P.blue_next_hops,
this_pnar.nh_intf_list)
S.blue_to_green_nh_dict[P.node_id] = True
if P.red_next_hops == []:
Copy_List_Items(P.red_next_hops,
this_pnar.nh_intf_list)
S.red_to_green_nh_dict[P.node_id] = True
def Select_Alternates_Proxy_Node(P,F,primary_intf):
S = primary_intf.local_node
X = P.pnar_X
Y = P.pnar_Y
A = X.order_proxy
B = Y.order_proxy
if F is A and F is B:
return 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'
if F is A:
return 'USE_RED'
if F is B:
return 'USE_BLUE'
if not In_Common_Block(A, B):
if In_Common_Block(F, A):
return 'USE_RED'
elif In_Common_Block(F, B):
return 'USE_BLUE'
else:
return 'USE_RED_OR_BLUE'
if (not In_Common_Block(F, A)
and not In_Common_Block(F, A) ):
return 'USE_RED_OR_BLUE'
alt_to_X = Select_Alternates(X, F, primary_intf)
alt_to_Y = Select_Alternates(Y, F, primary_intf)
if (alt_to_X == 'USE_RED_OR_BLUE'
and alt_to_Y == 'USE_RED_OR_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED_OR_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED_OR_BLUE':
return 'USE_RED'
if (A is S.localroot
and B is S.localroot):
#print("1.0")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is S.localroot
and B is not S.localroot):
#print("2.0")
if B.LOWER:
#print("2.1")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if B.HIGHER:
#print("2.2")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
else:
#print("2.3")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is not S.localroot
and B is S.localroot):
#print("3.0")
if A.LOWER:
#print("3.1")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if A.HIGHER:
#print("3.2")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("3.3")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
if (A is not S.localroot
and B is not S.localroot):
#print("4.0")
if (S is A.localroot or S is B.localroot):
#print("4.05")
if A.topo_order < B.topo_order:
#print("4.05.1")
if (alt_to_X == 'USE_BLUE' and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.05.2")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if A.LOWER:
#print("4.1")
if B.HIGHER:
#print("4.1.1")
if (alt_to_X == 'USE_RED' and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if B.LOWER:
#print("4.1.2")
if A.topo_order < B.topo_order:
#print("4.1.2.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.1.2.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
else:
#print("4.1.3")
if (F.LOWER and not F.HIGHER
and F.topo_order > A.topo_order):
#print("4.1.3.1")
return 'USE_RED'
else:
#print("4.1.3.2")
return 'USE_BLUE'
if A.HIGHER:
#print("4.2")
if B.HIGHER:
#print("4.2.1")
if A.topo_order < B.topo_order:
#print("4.2.1.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.2.1.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
if B.LOWER:
#print("4.2.2")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.2.3")
if (F.HIGHER and not F.LOWER
and F.topo_order < A.topo_order):
return 'USE_RED'
else:
return 'USE_BLUE'
else:
#print("4.3")
if B.LOWER:
#print("4.3.1")
if (F.LOWER and not F.HIGHER
and F.topo_order > B.topo_order):
return 'USE_BLUE'
else:
return 'USE_RED'
if B.HIGHER:
#print("4.3.2")
if (F.HIGHER and not F.LOWER
and F.topo_order < B.topo_order):
return 'USE_BLUE'
else:
return 'USE_RED'
else:
#print("4.3.3")
if A.topo_order < B.topo_order:
#print("4.3.3.1")
if (alt_to_X == 'USE_BLUE'
and alt_to_Y == 'USE_RED'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_BLUE':
return 'USE_BLUE'
if alt_to_Y == 'USE_RED':
return 'USE_RED'
assert(False)
else:
#print("4.3.3.2")
if (alt_to_X == 'USE_RED'
and alt_to_Y == 'USE_BLUE'):
return 'USE_RED_OR_BLUE'
if alt_to_X == 'USE_RED':
return 'USE_BLUE'
if alt_to_Y == 'USE_BLUE':
return 'USE_RED'
assert(False)
assert(False)
def Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
min_total_pref_cost = 2147483647
for (adv_node, prefix_cost) in P.node_prefix_cost_list:
total_pref_cost = (adv_node.primary_spf_metric
+ prefix_cost)
if total_pref_cost < min_total_pref_cost:
min_total_pref_cost = total_pref_cost
Copy_List_Items(P.primary_next_hops,
adv_node.primary_next_hops)
elif total_pref_cost == min_total_pref_cost:
for nh_intf in adv_node.primary_next_hops:
Add_Item_To_List_If_New(P.primary_next_hops,
nh_intf)
def Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
P.alt_list = []
for failed_intf in P.primary_next_hops:
alt = Alternate()
alt.failed_intf = failed_intf
if failed_intf not in src.island_intf_list:
alt.info = 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND'
elif P.pnar1 is None:
alt.info = 'NO_PNARs_EXIST_FOR_THIS_PREFIX'
elif src is P.pnar1.node:
alt.info = 'SRC_IS_PNAR'
elif P.pnar2 is not None and src is P.pnar2.node:
alt.info = 'SRC_IS_PNAR'
elif P.pnar2 is None:
#inherit alternates from the only pnar.
alt.info = Select_Alternates(P.pnar1.node,
failed_intf.remote_node, failed_intf)
elif failed_intf in src.island_intf_list:
alt.info = Select_Alternates_Proxy_Node(P,
failed_intf.remote_node, failed_intf)
if alt.info == 'USE_RED_OR_BLUE':
alt.red_or_blue = \
random.choice(['USE_RED','USE_BLUE'])
if (alt.info == 'USE_BLUE'
or alt.red_or_blue == 'USE_BLUE'):
Copy_List_Items(alt.nh_list, P.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'NODE_PROTECTION'
elif (alt.info == 'USE_RED'
or alt.red_or_blue == 'USE_RED'):
Copy_List_Items(alt.nh_list, P.red_next_hops)
alt.fec = 'RED'
alt.prot = 'NODE_PROTECTION'
elif (alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D'
or alt.info == 'PRIM_NH_IS_OP_FOR_BOTH_X_AND_Y'):
if failed_intf.OUTGOING and failed_intf.INCOMING:
# cut-link: if there are parallel cut links, use
# the link(s) with lowest metric that are not
# primary intf or None
cand_alt_list = [None]
min_metric = 2147483647
for intf in src.island_intf_list:
if ( intf is not failed_intf and
(intf.remote_node is
failed_intf.remote_node)):
if intf.metric < min_metric:
cand_alt_list = [intf]
min_metric = intf.metric
elif intf.metric == min_metric:
cand_alt_list.append(intf)
if cand_alt_list != [None]:
alt.fec = 'GREEN'
alt.prot = 'PARALLEL_CUTLINK'
else:
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
Copy_List_Items(alt.nh_list, cand_alt_list)
else:
# set Z as the node to inherit blue next-hops from
if alt.info == 'PRIM_NH_IS_D_OR_OP_FOR_D':
Z = P.pnar1.node
else:
Z = P
if failed_intf in Z.red_next_hops:
Copy_List_Items(alt.nh_list, Z.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION'
else:
assert(failed_intf in Z.blue_next_hops)
Copy_List_Items(alt.nh_list, Z.red_next_hops)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
elif alt.info == 'PRIM_NH_FOR_PROXY_NODE_NOT_IN_ISLAND':
if (P.pnar2 == None and src is P.pnar1.node):
#MRT Island is singly connected to non-island dest
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
elif P.node_id in src.blue_to_green_nh_dict:
# blue to P goes to failed LFIN so use red to P
Copy_List_Items(alt.nh_list, P.red_next_hops)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
elif P.node_id in src.red_to_green_nh_dict:
# red to P goes to failed LFIN so use blue to P
Copy_List_Items(alt.nh_list, P.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION'
else:
Copy_List_Items(alt.nh_list, P.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION'
elif alt.info == 'TEMP_NO_ALTERNATE':
alt.fec = 'NO_ALTERNATE'
alt.prot = 'NO_PROTECTION'
P.alt_list.append(alt)
def Run_Basic_MRT_for_One_Source(topo, src):
MRT_Island_Identification(topo, src, 0, 0)
Set_Island_Intf_and_Node_Lists(topo)
Set_GADAG_Root(topo,src)
Sort_Interfaces(topo)
Run_Lowpoint(topo)
Assign_Remaining_Lowpoint_Parents(topo)
Construct_GADAG_via_Lowpoint(topo)
Run_Assign_Block_ID(topo)
Add_Undirected_Links(topo)
Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src)
Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src)
Select_Alts_For_One_Src_To_Island_Dests(topo,src)
Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src)
def Store_GADAG_and_Named_Proxies_Once(topo):
for node in topo.node_list:
for intf in node.intf_list:
if intf.OUTGOING:
intf.SIMULATION_OUTGOING = True
else:
intf.SIMULATION_OUTGOING = False
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
topo.stored_named_proxy_dict[prefix] = P
def Run_Basic_MRT_for_All_Sources(topo):
for src in topo.node_list:
Reset_Computed_Node_and_Intf_Values(topo)
Run_Basic_MRT_for_One_Source(topo,src)
if src is topo.gadag_root:
Store_GADAG_and_Named_Proxies_Once(topo)
def Run_MRT_for_One_Source(topo, src):
MRT_Island_Identification(topo, src, 0, 0)
Set_Island_Intf_and_Node_Lists(topo)
Set_GADAG_Root(topo,src)
Sort_Interfaces(topo)
Run_Lowpoint(topo)
Assign_Remaining_Lowpoint_Parents(topo)
Construct_GADAG_via_Lowpoint(topo)
Run_Assign_Block_ID(topo)
Add_Undirected_Links(topo)
Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,src)
Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,src)
Select_Alts_For_One_Src_To_Island_Dests(topo,src)
Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,src)
Create_Basic_Named_Proxy_Nodes(topo)
Attach_Named_Proxy_Nodes(topo)
Compute_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Select_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,src)
def Run_Prim_SPF_for_One_Source(topo,src):
Normal_SPF(topo, src)
Store_Primary_NHs_For_One_Source_To_Nodes(topo,src)
Create_Basic_Named_Proxy_Nodes(topo)
Compute_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,src)
def Run_MRT_for_All_Sources(topo):
for src in topo.node_list:
Reset_Computed_Node_and_Intf_Values(topo)
if src in topo.island_node_list_for_test_gr:
# src runs MRT if it is in same MRT island as test_gr
Run_MRT_for_One_Source(topo,src)
if src is topo.gadag_root:
Store_GADAG_and_Named_Proxies_Once(topo)
else:
# src still runs SPF if not in MRT island
Run_Prim_SPF_for_One_Source(topo,src)
def Write_Output_To_Files(topo,file_prefix):
Write_GADAG_To_File(topo,file_prefix)
Write_Both_MRTs_For_All_Dests_To_File(topo,file_prefix)
Write_Alternates_For_All_Dests_To_File(topo,file_prefix)
def Create_Basic_Topology_Input_File(filename):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10],
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10],
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10],
[78,79,10],[79,77,10]]
with open(filename + '.csv', 'w') as topo_file:
for item in data:
if len(item) > 3:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+','+str(item[3])+'\n')
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Create_Complex_Topology_Input_File(filename):
data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
[06,07,10],[06,07,10],[06,07,15],[07,01,10],[07,51,10],
[51,52,10],[52,53,10],[53,03,10],[01,55,10],[55,06,10],
[04,12,10],[12,13,10],[13,14,10],[14,15,10],[15,16,10],
[16,17,10],[17,04,10],[05,76,10],[76,77,10],[77,78,10],
[78,79,10],[79,77,10]]
with open(filename + '.csv', 'w') as topo_file:
for item in data:
if len(item) > 3:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+','+str(item[3])+'\n')
else:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
data = [[01,0],[02,0],[03,0],[04,0],[05,0],
[06,0],[07,0],
[51,0],[55,0],
[12,0],[13,0],[14,0],[15,0],
[16,0],[17,0],[76,0],[77,0],
[78,0],[79,0]]
with open(filename + '.profile', 'w') as topo_file:
for item in data:
line = (str(item[0])+','+str(item[1])+'\n')
topo_file.write(line)
data = [[2001,05,100],[2001,07,120],[2001,03,130],
[2002,13,100],[2002,15,110],
[2003,52,100],[2003,78,100]]
with open(filename + '.prefix', 'w') as topo_file:
for item in data:
line = (str(item[0])+','+str(item[1])+','+
str(item[2])+'\n')
topo_file.write(line)
def Generate_Basic_Topology_and_Run_MRT():
this_gadag_root = 3
Create_Basic_Topology_Input_File('basic_topo_input')
topo = Create_Topology_From_File('basic_topo_input')
res_file_base = 'basic_topo'
Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_Basic_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
def Generate_Complex_Topology_and_Run_MRT():
this_gadag_root = 3
Create_Complex_Topology_Input_File('complex_topo_input')
topo = Create_Topology_From_File('complex_topo_input')
Add_Profile_IDs_from_File(topo,'complex_topo_input')
Add_Prefix_Advertisements_From_File(topo,'complex_topo_input')
Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
Add_Prefixes_for_Non_Island_Nodes(topo)
res_file_base = 'complex_topo'
Raise_GADAG_Root_Selection_Priority(topo,this_gadag_root)
Run_MRT_for_All_Sources(topo)
Write_Output_To_Files(topo, res_file_base)
Generate_Basic_Topology_and_Run_MRT()
Generate_Complex_Topology_and_Run_MRT()
<CODE ENDS>
9. Algorithm Alternatives and Evaluation
This specification defines the MRT Lowpoint Algorithm, which is one This specification defines the MRT Lowpoint Algorithm, which is one
option among several possible MRT algorithms. Other alternatives are option among several possible MRT algorithms. Other alternatives are
described in the appendices. described in the appendices.
In addition, it is possible to calculate Destination-Rooted GADAG, In addition, it is possible to calculate Destination-Rooted GADAG,
where for each destination, a GADAG rooted at that destination is where for each destination, a GADAG rooted at that destination is
computed. Then a router can compute the blue MRT and red MRT next- computed. Then a router can compute the blue MRT and red MRT next-
hops to that destination. Building GADAGs per destination is hops to that destination. Building GADAGs per destination is
computationally more expensive, but may give somewhat shorter computationally more expensive, but may give somewhat shorter
alternate paths. It may be useful for live-live multicast along alternate paths. It may be useful for live-live multicast along
MRTs. MRTs.
8.1. Algorithm Evaluation 9.1. Algorithm Evaluation
The MRT Lowpoint algorithm is the lowest computation of the MRT The MRT Lowpoint algorithm is the lowest computation of the MRT
algorithms. Two other MRT algorithms are provided in Appendix A and algorithms. Two other MRT algorithms are provided in Appendix A and
Appendix B. When analyzed on service provider network topologies, Appendix B. When analyzed on service provider network topologies,
they did not provide significant differences in the path lenghts for they did not provide significant differences in the path lenghts for
the alternatives. This section does not focus on that analysis or the alternatives. This section does not focus on that analysis or
the decision to use the MRT Lowpoint algorithm as the default MRT the decision to use the MRT Lowpoint algorithm as the default MRT
algorithm; it has the lowest computational and storage requirements algorithm; it has the lowest computational and storage requirements
and gave comparable results. and gave comparable results.
Since this document defines the MRT Lowpoint algorithm for use in Since this document defines the MRT Lowpoint algorithm for use in
fast-reroute applications, it is useful to compare MRT and Remote LFA fast-reroute applications, it is useful to compare MRT and Remote LFA
[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 28 shows the node- coverage and alternate path length. Figure 29 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 67, line 37 skipping to change at page 103, 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 28 Figure 29
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 29). In this table, for one topology using this approach ( Figure 30). 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 68, line 28 skipping to change at page 104, 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 29 Figure 30
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 29, the path length. As shown in the last three columns of Figure 30, 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 30, Figure 31, Figure 32, and Figure 33 present the hopcount- Figure 31, Figure 32, Figure 33, and Figure 34 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 30 having topologies, as measured by the number of nodes, with Figure 31 having
the smallest topologies and Figure 33 having the largest topologies. the smallest topologies and Figure 34 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 70, line 50 skipping to change at page 106, 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 30 Figure 31
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
| | percentage of failure scenarios | | | percentage of failure scenarios |
| Topology name | protected by an alternate N hops | | Topology name | protected by an alternate N hops |
| and | longer than the primary path | | and | longer than the primary path |
| alternate selection +------------------------------------+ | alternate selection +------------------------------------+
| policy evaluated | | | | | | | | | no | | policy evaluated | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt| | | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16| | |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+ +------------------------------+---+---+---+---+---+---+---+---+----+
skipping to change at page 71, line 50 skipping to change at page 107, 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 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 72, line 50 skipping to change at page 108, 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 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 73, line 43 skipping to change at page 109, 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 33 Figure 34
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 74, line 24 skipping to change at page 110, 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 34 for a subset those three choices of GADAG root are shown in Figure 35 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 75, line 50 skipping to change at page 111, 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 34 Figure 35
9. 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.
10. Algorithm Work to Be Done
Broadcast Interfaces: The algorithm assumes that broadcast
interfaces are already represented as pseudo-nodes in the network
graph. Given maximal redundancy, one of the MRT will try to avoid
both the pseudo-node and the next hop. The exact rules need to be
fully specified.
11. Acknowledgements 11. Acknowledgements
The authors would like to thank Shraddha Hegde for her suggestions The authors would like to thank Shraddha Hegde for her suggestions
and review. We would also like to thank Anil Kumar SN for his and review. We would also like to thank Anil Kumar SN for his
assistance in clarifying the algorithm description and pseudocode. 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 This architecture is not currently believed to introduce new security
concerns. concerns.
skipping to change at page 76, line 47 skipping to change at page 112, line 39
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-05 (work in progress),
January 2015. January 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<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>.
skipping to change at page 78, line 5 skipping to change at page 113, line 40
and MPLS Fast Reroute Using Not-via Addresses", draft- and MPLS Fast Reroute Using Not-via Addresses", draft-
ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress), ietf-rtgwg-ipfrr-notvia-addresses-11 (work in progress),
May 2013. May 2013.
[I-D.ietf-rtgwg-lfa-manageability] [I-D.ietf-rtgwg-lfa-manageability]
Litkowski, S., Decraene, B., Filsfils, C., Raza, K., Litkowski, S., Decraene, B., Filsfils, C., Raza, K.,
Horneffer, M., and P. Sarkar, "Operational management of Horneffer, M., and P. Sarkar, "Operational management of
Loop Free Alternates", draft-ietf-rtgwg-lfa- Loop Free Alternates", draft-ietf-rtgwg-lfa-
manageability-11 (work in progress), June 2015. manageability-11 (work in progress), June 2015.
[ISO10589-Second-Edition]
International Organization for Standardization,
"Intermediate system to Intermediate system intra-domain
routeing information exchange protocol for use in
conjunction with the protocol for providing the
connectionless-mode Network Service (ISO 8473)", ISO/
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] [LFARevisited]
Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP Retvari, G., Tapolcai, J., Enyedi, G., and A. Csaszar, "IP
Fast ReRoute: Loop Free Alternates Revisited", Proceedings Fast ReRoute: Loop Free Alternates Revisited", Proceedings
of IEEE INFOCOM , 2011, of IEEE INFOCOM , 2011,
<http://opti.tmit.bme.hu/~tapolcai/papers/ <http://opti.tmit.bme.hu/~tapolcai/papers/
skipping to change at page 78, line 30 skipping to change at page 114, line 25
Addresses", Proceedings of IEEE INFOCOM , 2009, Addresses", Proceedings of IEEE INFOCOM , 2009,
<http://mycite.omikk.bme.hu/doc/71691.pdf>. <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
Protocol", RFC 2327, DOI 10.17487/RFC2327, April 1998,
<http://www.rfc-editor.org/info/rfc2327>.
[RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D. [RFC3137] Retana, A., Nguyen, L., White, R., Zinin, A., and D.
McPherson, "OSPF Stub Router Advertisement", RFC 3137, McPherson, "OSPF Stub Router Advertisement", RFC 3137,
June 2001. 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, February 2008. Intermediate Systems (IS-ISs)", RFC 5120,
DOI 10.17487/RFC5120, February 2008,
<http://www.rfc-editor.org/info/rfc5120>.
[RFC5286] Atlas, A. and A. Zinin, "Basic Specification for IP Fast [RFC5286] Atlas, A., Ed. and A. Zinin, Ed., "Basic Specification for
Reroute: Loop-Free Alternates", RFC 5286, September 2008. 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 [RFC5714] Shand, M. and S. Bryant, "IP Fast Reroute Framework",
5714, January 2010. RFC 5714, DOI 10.17487/RFC5714, January 2010,
<http://www.rfc-editor.org/info/rfc5714>.
[RFC6571] Filsfils, C., Francois, P., Shand, M., Decraene, B., [RFC6571] Filsfils, C., Ed., Francois, P., Ed., Shand, M., Decraene,
Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free B., Uttaro, J., Leymann, N., and M. Horneffer, "Loop-Free
Alternate (LFA) Applicability in Service Provider (SP) Alternate (LFA) Applicability in Service Provider (SP)
Networks", RFC 6571, June 2012. Networks", RFC 6571, 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, April 2015. RFC 7490, DOI 10.17487/RFC7490, April 2015,
<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
computations in that block find ears until there are no more computations in that block find ears until there are no more
interfaces to be explored. The used result from the SPF computation interfaces to be explored. The used result from the SPF computation
is the path of interfaces indicated by following the previous hops is the path of interfaces indicated by following the previous hops
from the mininized IN_GADAG node back to the SPF root. from the mininized IN_GADAG node back to the SPF root.
skipping to change at page 80, line 37 skipping to change at page 116, line 48
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 35: Modified SPF for GADAG computation Figure 36: 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 82, line 48 skipping to change at page 118, 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 36: Algorithm to assign links of an ear direction Figure 37: 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 84, line 30 skipping to change at page 120, 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 37: SPF-based GADAG algorithm Figure 38: 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 85, line 12 skipping to change at page 121, 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 38 The entire algorithm is shown below in Figure 39
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)