RFC 7811
An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)
RFC 7811: An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR) 💖
Okay bestie, this is RFC 7811 🦋 an IETF Standards Track doc, dated June 2016 and filed under ISSN 2070-1721. It was written by G. Enyedi and A. Csaszar from Ericsson, A. Atlas and C. Bowers from Juniper Networks, and A. Gopalan from the University of Arizona. Its header doesn't list anything it obsoletes or updates, so it stands on its own 💅
Abstract 🌸
This doc backs up the solution in "An Architecture for IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)" (RFC 7812) by defining the MRT Lowpoint algorithm 🧚 It's the one used in the Default MRT Profile to compute the Maximally Redundant Trees, their next hops, and the alternates you pick for MRT-FRR. Main character energy, literally ✨
Status of This Memo 📜
This is an Internet Standards Track document ✨
This doc is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It went through public review and got approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check Section 2 of RFC 7841.
Info about the current status of this doc, any errata, and how to send feedback lives at http://www.rfc-editor.org/info/rfc7811.
Copyright Notice 💅
Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved.
This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) as in effect on the date of publication. Please read these carefully, bestie, because they explain your rights and restrictions for this doc 📖 Any Code Components pulled out of this doc must include Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions, and they come without warranty as described in the Simplified BSD License 🔒
Table of Contents 🧚
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Language . . . . . . . . . . . . . . . . . . . . 5
3. Terminology and Definitions . . . . . . . . . . . . . . . . . 5
4. Algorithm Key Concepts . . . . . . . . . . . . . . . . . . . 6
4.1. Partial Ordering for Disjoint Paths . . . . . . . . . . . 7
4.2. Finding an Ear and the Correct Direction . . . . . . . . 8
4.3. Lowpoint Values and Their Uses . . . . . . . . . . . . . 11
4.4. Blocks in a Graph . . . . . . . . . . . . . . . . . . . . 14
4.5. Determining Localroot and Assigning Block-ID . . . . . . 16
5. MRT Lowpoint Algorithm Specification . . . . . . . . . . . . 18
5.1. Interface Ordering . . . . . . . . . . . . . . . . . . . 18
5.2. MRT Island Identification . . . . . . . . . . . . . . . . 21
5.3. GADAG Root Selection . . . . . . . . . . . . . . . . . . 21
5.4. Initialization . . . . . . . . . . . . . . . . . . . . . 22
5.5. Constructing the GADAG Using Lowpoint Inheritance . . . . 23
5.6. Augmenting the GADAG by Directing All Links . . . . . . . 25
5.7. Compute MRT Next Hops . . . . . . . . . . . . . . . . . . 29
5.7.1. MRT Next Hops to All Nodes Ordered with Respect to
the Computing Node . . . . . . . . . . . . . . . . . 29
5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect
to the Computing Node . . . . . . . . . . . . . . . . 30
5.7.3. Computing Redundant Tree Next Hops in a 2-Connected
Graph . . . . . . . . . . . . . . . . . . . . . . . . 31
5.7.4. Generalizing for a Graph That Isn't 2-Connected . . . 33
5.7.5. Complete Algorithm to Compute MRT Next Hops . . . . . 34
5.8. Identify MRT Alternates . . . . . . . . . . . . . . . . . 36
5.9. Named Proxy-Nodes . . . . . . . . . . . . . . . . . . . . 44
5.9.1. Determining Proxy-Node Attachment Routers . . . . . . 45
5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free . . 45
5.9.3. Computing MRT Next Hops for Proxy-Nodes . . . . . . . 47
5.9.4. Computing MRT Alternates for Proxy-Nodes . . . . . . 53
6. MRT Lowpoint Algorithm: Next-Hop Conformance . . . . . . . . 61
7. Broadcast Interfaces . . . . . . . . . . . . . . . . . . . . 61
7.1. Computing MRT Next Hops on Broadcast Networks . . . . . . 62
7.2. Using MRT Next Hops as Alternates in the Event of
Failures on Broadcast Networks . . . . . . . . . . . . . 63
8. Evaluation of Alternative Methods for Constructing GADAGs . . 64
9. Operational Considerations . . . . . . . . . . . . . . . . . 66
9.1. GADAG Root Selection . . . . . . . . . . . . . . . . . . 67
9.2. Destination-Rooted GADAGs . . . . . . . . . . . . . . . . 67
10. Security Considerations . . . . . . . . . . . . . . . . . . . 67
11. References . . . . . . . . . . . . . . . . . . . . . . . . . 68
11.1. Normative References . . . . . . . . . . . . . . . . . . 68
11.2. Informative References . . . . . . . . . . . . . . . . . 68
Appendix A. Python Implementation of MRT Lowpoint Algorithm . . 70
Appendix B. Constructing a GADAG Using SPFs . . . . . . . . . . 110
Appendix C. Constructing a GADAG Using a Hybrid Method . . . . . 115
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 117
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 1181. Introduction ✨
MRT Fast Reroute needs packets to be forwardable not only on the shortest-path tree, but also on two Maximally Redundant Trees (MRTs), called the MRT-Blue and the MRT-Red 🔥 A router that hits a local failure also has to have already decided which alternate to use. This doc defines how to compute all three of those things for MRT-FRR, and it explains the design decisions and reasoning behind the algorithm. The algorithm is built on the ideas in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint algorithm is required for implementation when the Default MRT Profile is implemented 💖
The MRT Lowpoint Algorithm defined here, when used for MRT Fast-Reroute as described in [RFC7812], guarantees 100% recovery for single failures when the network is 2-connected 😭 This guaranteed coverage doesn't depend on the link metrics, which an operator may be using to traffic-engineer the IP network. So the link metrics and the general network topology are mostly decoupled from the guaranteed coverage. It's giving independence 🦋
Just as packets routed hop by hop need each router to compute a consistent shortest-path tree, each router also needs to compute the MRT-Blue next hops and MRT-Red next hops in a consistent way 🌈 This doc defines the MRT Lowpoint algorithm to be used as a standard in the Default MRT Profile for MRT-FRR 👑
A router's Forwarding Information Base (FIB) keeps primary next hops for the current shortest-path tree so it can forward traffic. On top of that, the FIB holds primary next hops for the MRT-Blue, used to forward traffic received on the MRT-Blue, and primary next hops for the MRT-Red, used to forward traffic received on the MRT-Red 🧚
What alternate next hops a Point of Local Repair (PLR) picks doesn't need to be consistent, but loops must be prevented 🙈 To reduce congestion, multiple alternate next hops can be selected. In the context of MRT alternates, each of those alternate next hops would be equal-cost paths 🍓
This doc defines an algorithm for selecting an appropriate MRT alternate to consider. Other alternates, e.g., Loop-Free Alternates (LFAs) that are downstream paths, may be preferred when they're available. For a more detailed take on combining MRT alternates with the ones produced by other FRR technologies, see the "Operational Considerations" section of [RFC7812] 💅
[E]---[D]---| [E]<--[D]<--| [E]-->[D]---|
| | | | ^ | | |
| | | V | | V V
[R] [F] [C] [R] [F] [C] [R] [F] [C]
| | | ^ ^ ^ | |
| | | | | | V |
[A]---[B]---| [A]-->[B]---| [A]<--[B]<--|
(a) (b) (c)
A 2-connected graph MRT-Blue towards R MRT-Red towards R
Figure 1The MRT Lowpoint algorithm can handle arbitrary network topologies where the whole network graph isn't 2-connected, like in Figure 2, and it also handles the easier case where the network graph is 2-connected (Figure 1) 🎀 Each MRT is a spanning tree. The pair of MRTs gives two paths from every node X to the root of the MRTs. Those paths share the minimum number of nodes and the minimum number of links. Each shared node is a cut-vertex, and any shared links are cut-links 🫶
[E]---[D]---| |---[J]
| | | | |
| | | | |
[R] [F] [C]---[G] |
| | | | |
| | | | |
[A]---[B]---| |---[H]
(a) a graph that is not 2-connected
[E]<--[D]<--| [J] [E]-->[D]---| |---[J]
| ^ | | | | | ^
V | | | V V V |
[R] [F] [C]<--[G] | [R] [F] [C]<--[G] |
^ ^ ^ | ^ | | |
| | | V | V | |
[A]-->[B]---| |---[H] [A]<--[B]<--| [H]
(b) MRT-Blue towards R (c) MRT-Red towards R
Figure 2: A Network That Is Not 2-Connected2. Requirements Language 🫶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] 💜
3. Terminology and Definitions ✨
okay so, the full glossary lives in the Terminology section of [RFC7812] 💅 This part only covers the extra terms that show up in this doc, so you don't have to re-read the same stuff 🧚
spanning tree 🌳: a tree made of links that connects every node in the network graph. no node left on read 🫶
back-edge 🔙: when you're working with a spanning tree built by a depth-first search, a back-edge is a link that connects a descendant of some node x with one of x's ancestors. it's giving loop vibes 🌀
partial ADAG 🧩: a piece of an Almost Directed Acyclic Graph (ADAG) that doesn't have all the nodes in its block yet. it gets built during the MRT Lowpoint algorithm and keeps growing until every node in the block is in, and then it's a full ADAG. glow-up arc 🦋
DFS 🔍: short for Depth-First Search
DFS ancestor 👑: a node n is a DFS ancestor of x if n sits on the DFS-tree path from the DFS root down to x
DFS descendant 🌸: a node n is a DFS descendant of x if x sits on the DFS-tree path from the DFS root down to n. so it's just the reverse of an ancestor, bestie 🙈
ear 🎀: a path through nodes that aren't in the Generalized ADAG (GADAG) yet. it starts at a node that's already in the GADAG and ends at a node that's already in the GADAG too. the start and end can be the very same node, but only if that node is a cut-vertex 💀
X>>Y or Y<<X 💜: this shows how X and Y relate in a partial order (the kind you'd find in a GADAG). X>>Y means X is higher in the partial order than Y, and Y<<X means Y is lower than X. same vibe, two ways to say it 🫶
X>Y or Y<X 🌈: this shows how X and Y relate in the total order (the kind you get from a topological sort). X>Y means X is higher in the total order than Y, and Y<X means Y is lower than X ✨
X ?? Y ❓: means X is unordered with respect to Y in the partial order. they're just not comparable, no drama 🤷♀️
UNDIRECTED 🌫️: in the GADAG, every link gets marked as OUTGOING, INCOMING, or both. until the link's direction has been figured out, it stays marked as UNDIRECTED, which just means "we don't know which way it goes yet" 🙈
OUTGOING ➡️: a link marked OUTGOING points in the GADAG from the interface's router out to the remote end ✨
INCOMING ⬅️: a link marked INCOMING points in the GADAG from the remote end back in to the interface's router 💖
4. Algorithm Key Concepts
okay bestie, there are five key concepts you need in your back pocket to get the MRT Lowpoint algorithm 🧠✨ concept one is partially ordering the nodes in a network graph, both relative to each other and relative to the GADAG root. concept two is finding an ear of nodes and adding them in the right direction 🛣️ concept three is the Lowpoint value, and how it helps you spot cut-vertices and find a second path toward the root 🔎 concept four is that a graph which isn't 2-connected is made of blocks, where a block is either a 2-connected cluster, a cut-link, or an isolated node 🧱 and concept five is the localroot for each node, which gets used to compute the ADAGs inside each block 👑
4.1. Partial Ordering for Disjoint Paths
so, given any two nodes X and Y in a graph, a total order means you can always say either X<Y or X>Y. a good example is a graph where the nodes get ranked by their unique IP loopback addresses 🌸 in a partial order though, there are some nodes where you just can't tell whether X<<Y or X>>Y. you can capture a partial order in a directed graph, like in Figure 3 👇 in that kind of graphical picture, a link pointing from X to Y means X is a neighbor of Y in the network graph and X<<Y 💜
[A]<---[R] [E] R << A << B << C << D << E
| ^ R << A << B << F << G << H << D << E
| |
V | Unspecified Relationships:
[B]--->[C]--->[D] C and F
| ^ C and G
| | C and H
V |
[F]--->[G]--->[H]Figure 3: Directed Graph Showing a Partial Order
now, to compute MRTs, the root of the MRTs sits at both the very bottom and the very top of the partial ordering 🔝⬇️ that means from any node X, you can keep picking higher nodes until you reach the root, and you can also keep picking lower nodes until you reach the root. for example, in Figure 4, starting at G, the higher nodes you can pick (by following the directed links) are H, D, E, and R. and starting at G, the lower nodes you can pick (by reversing the directed links) are F, B, A, and R 🦋 a graph like this isn't a DAG anymore, since the links pointing at the root break the no-cycles rule. that's why it's called an Almost DAG (ADAG), because if you removed those links to the root, it would be a DAG again 🫶
[A]<---[R]<---[E] R << A << B << C << R
| ^ ^ R << A << B << C << D << E << R
| | | R << A << B << F << G << H << D << E << R
V | |
[B]--->[C]--->[D] Unspecified Relationships:
| ^ C and F
| | C and G
V | C and H
[F]--->[G]--->[H]Figure 4: ADAG Showing a Partial Order with R Lowest and Highest
here's the most important bit 🚨 if a node Y>>X, then Y can only show up on the increasing path from X to the root, and it can never show up on the decreasing path. flip it around and if a node Z<<X, then Z can only show up on the decreasing path from X to the root, and never on the increasing path 💅
when you're following the increasing paths, you can pick several higher nodes and still be certain those paths stay disjoint from the decreasing paths ✨ like in the example above, node B has more than one option for forwarding packets along an increasing path: it can forward them to C or to F 🎀
4.2. Finding an Ear and the Correct Direction ✨
okay bestie, to keep things simple, the basic idea of building a GADAG by adding ears assumes the network graph is a single 2-connected cluster, so an ADAG is enough 🦋. Generalizing to multiple blocks works by using the block-roots instead of the GADAG root, and the actual algorithm is in Section 5.5 💅.
okay so, to get the basic idea of finding an ADAG, first imagine we already have a partial ADAG that doesn't have all the nodes in the block yet, and we want to extend it to cover everything 🌸. Now we find a path from a node X to Y where X and Y are already in our partial ADAG, but all the nodes in between aren't added yet. We call that path an "ear" 🎀.
Recall that our ADAG is closely related to a partial order. More precisely, if we remove root R, the remaining DAG describes a partial order of the nodes 💜. If neither X nor Y is the root, we may be able to compare them. If one of them is definitely lesser with respect to our partial order (say X<<Y), we can add the new path to the ADAG in a direction from X to Y ✨. As an example, check out Figure 5 👑.
E---D---| E<--D---| E<--D<--|
| | | | ^ | | ^ |
| | | V | | V | |
R F C R F C R F C
| | | | ^ | | ^ ^
| | | V | | V | |
A---B---| A-->B---| A-->B---|
(a) (b) (c)
(a) A 2-connected graph
(b) Partial ADAG (C is not included)
(c) Resulting ADAG after adding path (or ear) B-C-D
Figure 5In this partial ADAG, node C isn't included yet 🙈. But we can find the path B-C-D, where both endpoints are already in this partial ADAG (we say those nodes are "ready" in the following text), and the remaining node (node C) isn't in there yet 🧚. If we remove R, the remaining DAG defines a partial order, and with respect to that partial order, we can say that B<<D. So we can add the path to the ADAG in the direction from B to D (arcs B->C and C->D are added) 🍓. If B>>D, we would add the same path in reverse direction 🔄.
If, in the partial order where an ear's two ends are X and Y, X<<Y, then there must already be a directed path from X to Y in the ADAG. The ear must be added in a direction that doesn't create a cycle, so the ear must go from X to Y 🚫🔁.
If X and Y aren't ordered with each other, we can pick either direction for the ear. We have no restriction, since neither direction can result in a cycle 🙌. In the corner case where one of the endpoints of an ear, say X, is the root (recall that the two endpoints must be different), we could use both directions again for the ear, because the root can be considered both smaller and greater than Y. However, we strictly pick the direction in which the root is lower than Y. The logic for this decision is explained in Section 5.7 💖.
A partial ADAG is started by finding a cycle from the root R back to itself. This can be done by selecting a non-ready neighbor N of R and then finding a path from N to R that doesn't use any links between R and N. The direction of the cycle can be assigned either way, since it's starting the ordering 🌈.
Once a partial ADAG is already present, it will always have a node in it that isn't the root R. Here's a brief proof that a partial ADAG can always have ears added to it: just select a non-ready neighbor N of a ready node Q, such that Q isn't the root R, then find a path from N to the root R in the graph with Q removed. This path is an ear where the first node of the ear is Q, the next is N, and then the path continues until the first ready node it reaches (that ready node is the other endpoint of the path). Since the graph is 2-connected, there must be a path from N to R without Q 🫶.
It's always possible to select a non-ready neighbor N of a ready node Q so that Q isn't the root R. Because the network is 2-connected, N must be connected to two different nodes, and only one of them can be R. Because the initial cycle has already been added to the ADAG, there are ready nodes that aren't R. Since the graph is 2-connected, while there are non-ready nodes, there must be a non-ready neighbor N of a ready node that isn't R 🥹.
Generic_Find_Ears_ADAG(root)
Create an empty ADAG. Add root to the ADAG.
Mark root as IN_GADAG.
Select an arbitrary cycle containing root.
Add the arbitrary cycle to the ADAG.
Mark cycle's nodes as IN_GADAG.
Add cycle's non-root nodes to process_list.
While there exist connected nodes in graph that are not IN_GADAG
Select a new ear. Let its endpoints be X and Y.
If Y is root or (Y<<X)
Add the ear towards X to the ADAG
Else // (a) X is root, or (b) X<<Y, or (c) X, Y not ordered
Add the ear towards Y to the ADAG
Figure 6: Generic Algorithm to Find Ears and Their Direction in
2-Connected GraphThe algorithm in Figure 6 only requires that a cycle or ear be selected, without saying how 🧠. No matter how you select the path, you'll end up with an ADAG 💅. The way you find and select the ears does matter, though: shorter ears result in shorter paths along the MRTs 📏. The MRT Lowpoint algorithm uses the Lowpoint Inheritance method for constructing an ADAG (and ultimately a GADAG). That method is defined in Section 5.5. Other methods for constructing GADAGs are described in Appendices B and C, and an evaluation of these different methods is given in Section 8 📚.
As an example, look at Figure 5 again. First, we select the shortest cycle containing R, which can be R-A-B-F-D-E (uniform link costs were assumed), so we end up in the situation shown in Figure 5(b) 🔁. Finally, we find a node next to a ready node. That must be node C, and let's assume we reached it from ready node B. We search for a path from C to R without B in the original graph. The first ready node along this path is node D, so the open ear is B-C-D. Since B<<D, we add arc B->C and C->D to the ADAG. Since all the nodes are ready now, we stop right here 🎉✨
4.3. Lowpoint Values and Their Uses ✨
okay so a basic way to build a spanning tree on a network graph is to run a DFS, like in Figure 7 🌳. This tree has the iconic property that if there is a link (x, n), then either n is a DFS ancestor of x or n is a DFS descendant of x. Basically, either n is on the path from the root to x, or x is on the path from the root to n 💅.
global_variable: dfs_number
DFS_Visit(node x, node parent)
D(x) = dfs_number
dfs_number += 1
x.dfs_parent = parent
for each link (x, w)
if D(w) is not set
DFS_Visit(w, x)
Run_DFS(node gadag_root)
dfs_number = 0
DFS_Visit(gadag_root, NONE)
Figure 7: Basic DFS AlgorithmGiven a node x, you can compute the minimal DFS number of the neighbors of x, i.e., min( D(w) if (x,w) is a link). This gives the earliest attachment point neighboring x. But what's actually interesting is the earliest attachment point from x and x's descendants 👀. That's what the Lowpoint value figures out 🎀.
To compute the lowpoint value, the network gets traversed using DFS, and the vertices get numbered based on that DFS walk. We'll call this number DFS(x). Every edge that leads to an already-visited node during the DFS walk is a back-edge 🔙. Back-edges are a big deal because they tell you about reachability of a node via another path 🧚.
The low point number is calculated by finding:
Low(x) = Minimum of ( (DFS(x),
Lowest DFS(n, x->n is a back-edge),
Lowest Low(n, x->n is tree edge in DFS walk) ).A detailed algorithm for computing the lowpoint value is in Figure 8, and Figure 9 shows how the Lowpoint algorithm works on an example graph 🌈.
global_variable: dfs_number
Lowpoint_Visit(node x, node parent, interface p_to_x)
D(x) = dfs_number
L(x) = D(x)
dfs_number += 1
x.dfs_parent = parent
x.dfs_parent_intf = p_to_x.remote_intf
x.lowpoint_parent = NONE
for each ordered_interface intf of x
if D(intf.remote_node) is not set
Lowpoint_Visit(intf.remote_node, x, intf)
if L(intf.remote_node) < L(x)
L(x) = L(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else if intf.remote_node is not parent
if D(intf.remote_node) < L(x)
L(x) = D(intf.remote_node)
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
Run_Lowpoint(node gadag_root)
dfs_number = 0
Lowpoint_Visit(gadag_root, NONE, NONE)
Figure 8: Computing Lowpoint Value [E]---| [J]-------[I] [P]---[O]
| | | | | |
| | | | | |
[R] [D]---[C]--[F] [H]---[K] [N]
| | | | | |
| | | | | |
[A]--------[B] [G]---| [L]---[M]
(a) a non-2-connected graph
[E]----| [J]---------[I] [P]------[O]
(5, ) | (10, ) (9, ) (16, ) (15, )
| | | | | |
| | | | | |
[R] [D]---[C]---[F] [H]----[K] [N]
(0, ) (4, ) (3, ) (6, ) (8, ) (11, ) (14, )
| | | | | |
| | | | | |
[A]---------[B] [G]----| [L]------[M]
(1, ) (2, ) (7, ) (12, ) (13, )
(b) with DFS values assigned (D(x), L(x))
[E]----| [J]---------[I] [P]------[O]
(5,0) | (10,3) (9,3) (16,11) (15,11)
| | | | | |
| | | | | |
[R] [D]---[C]---[F] [H]----[K] [N]
(0,0) (4,0) (3,0) (6,3) (8,3) (11,11) (14,11)
| | | | | |
| | | | | |
[A]---------[B] [G]----| [L]------[M]
(1,0) (2,0) (7,3) (12,11) (13,11)
(c) with lowpoint values assigned (D(x), L(x))
Figure 9: Example Lowpoint Value ComputationFrom the lowpoint value and lowpoint parent, we get three super useful things that motivate the whole computation 🫶.
First, if there is a child c of x such that L(c) >= D(x), then there are no paths in the network graph that go from c or its descendants to an ancestor of x. That means x is a cut-vertex 🚧. In Figure 9, you can see this by looking at the DFS children of C. C has two children, D and F, and L(F) = 3 = D(C), so it's clear that C is a cut-vertex and F is in a block where C is the block's root. Meanwhile L(D) = 0<3 = D(C), so D has a path to the ancestors of C. In this case, D can go via E to reach R. Comparing the lowpoint values of all a node's DFS-children with the node's DFS-value is so useful because it lets you spot the cut-vertices, and therefore the blocks 🧩.
Second, by repeatedly following the path given by lowpoint_parent, there is a path from x back to an ancestor of x that does not use the link [x, x.dfs_parent] in either direction. You don't have to take the full path, but this gives a way of finding an initial cycle and then ears 🔁.
Third, as seen in Figure 9, even if L(x)<D(x), there may be a block that contains both the root and a DFS-child of a node, while other DFS-children might be in different blocks. In this example, C's child D is in the same block as R, while F is not. It's important to realize that the root of a block may also be the root of another block 👑.
4.4. Blocks in a Graph 🧱
A key idea for the MRT Lowpoint algorithm is that any non-2-connected graph is made up by blocks (e.g., 2-connected clusters, cut-links, and/or isolated nodes). To compute GADAGs and thus MRTs, computation is done in each block to compute ADAGs or Redundant Trees, and then those ADAGs or Redundant Trees are combined into a GADAG or MRT 💖.
[E]---| [J]-------[I] [P]---[O]
| | | | | |
| | | | | |
[R] [D]---[C]--[F] [H]---[K] [N]
| | | | | |
| | | | | |
[A]--------[B] [G]---| [L]---[M]
(a) A graph with four blocks:
three 2-connected clusters
and one cut-link
[E]<--| [J]<------[I] [P]<--[O]
| | | ^ | ^
V | V | V |
[R] [D]<--[C] [F] [H]<---[K] [N]
^ | ^ ^
| V | |
[A]------->[B] [G]---| [L]-->[M]
(b) MRT-Blue for destination R
[E]---| [J]-------->[I] [P]-->[O]
| | |
V V V
[R] [D]-->[C]<---[F] [H]<---[K] [N]
^ | ^ | ^ |
| V | | | V
[A]<-------[B] [G]<--| [L]<--[M]
(c) MRT-Red for destination R
Figure 10Let's look at the example in Figure 10 (a), because it's a special graph that shows every way 2-connected clusters can be connected 🕸️. It has four blocks. Block 1 contains R, A, B, C, D, E. Block 2 contains C, F, G, H, I, J. Block 3 contains K, L, M, N, O, P. Block 4 is a cut-link containing H and K. The first two blocks have one common node (node C), and blocks 2 and 3 don't have any common node, but they're connected through a cut-link, which is block 4. No two blocks can have more than one common node, since two blocks with at least two common nodes would count as a single 2-connected cluster 🙈.
Also, if we want to get from one block to another, we have to go through a cut-vertex (the cut-vertices in this graph are C, H, K), no matter which path we pick 🚦. So all the paths from block 3 along the MRTs rooted at R will cross K first. This means that if we want a pair of MRTs rooted at R, we need to build a pair of RTs in block 3 with K as a root. Similarly, we need another pair of RTs in block 2 with C as a root, and finally the last pair of RTs in block 1 with R as a root 🎀. Once all the trees are selected, we can just combine them. When a block is a cut-link (like block 4), that cut-link gets added in the same direction to both of the trees. The resulting trees are shown in Figure 10 (b) and (c) 🦋.
Similarly, to create a GADAG, it's enough to compute ADAGs in each block and connect them 💜.
So it's necessary to identify the cut-vertices, the blocks, and the appropriate localroot to use for each block 💅✨
4.5. Determining Localroot and Assigning Block-ID 🦋
okay so every node in the network graph has a localroot 💖. It's the cut-vertex (or root) in the same block that's closest to the root 🌸. The localroot is how we figure out whether two nodes share a common block 🫶
Compute_Localroot(node x, node localroot)
x.localroot = localroot
for each DFS child node c of x
if L(c) < D(x) //x is not a cut-vertex
Compute_Localroot(c, x.localroot)
else
mark x as cut-vertex
Compute_Localroot(c, x)
Compute_Localroot(gadag_root, gadag_root)Figure 11: A Method for Computing Localroots
there are two different ways to compute the localroot for each node 💅. The stand-alone method is in Figure 11 and honestly it's the best way to get the concept. It's what the GADAG construction methods in Appendices B and C use. The MRT Lowpoint algorithm, on the other hand, computes the localroot for a block as part of building the GADAG with lowpoint inheritance. The essence of that is in Figure 12. Both methods give the same results, so no drama 😌
Get the current node, s.
Compute an ear (either through lowpoint inheritance
or by following dfs parents) from s to a ready node e.
(Thus, s is not e, if there is such ear.)
if s is e
for each node x in the ear that is not s
x.localroot = s
else
for each node x in the ear that is not s or e
x.localroot = e.localrootFigure 12: Ear-Based Method for Computing Localroots
once the localroots are known, two nodes X and Y are in a common block if and only if one of these three conditions applies 👑
- Y's localroot is X's localroot : They are in the same block and neither is the cut-vertex closest to the root.
- Y's localroot is X: X is the cut-vertex closest to the root for Y's block.
- Y is X's localroot: Y is the cut-vertex closest to the root for X's block.
and once we've got the localroot for every node, we can give each node a Block-ID that represents the block it lives in 🌈 Here's how that works in Figure 13 ✨
global_var: max_block_id
Assign_Block_ID(x, cur_block_id)
x.block_id = cur_block_id
foreach DFS child c of x
if (c.local_root is x)
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else
Assign_Block_ID(c, cur_block_id)
max_block_id = 0
Assign_Block_ID(gadag_root, max_block_id)Figure 13: Assigning Block-ID to Identify Blocks
5. MRT Lowpoint Algorithm Specification 💖
the MRT Lowpoint algorithm builds one GADAG, and then a router uses that GADAG to work out its MRT-Blue and MRT-Red next hops to every destination 🦋 From there, alternates get picked for each next hop to each destination. Here are the steps, in order 🎀
- Order the interfaces in the network graph. See Section 5.1.
- Compute the local MRT Island for the particular MRT Profile. See Section 5.2.
- Select the root to use for the GADAG. See Section 5.3.
- Initialize all interfaces to UNDIRECTED. See Section 5.4.
- Compute the DFS value, e.g., D(x), and lowpoint value, L(x). See Figure 8.
- Construct the GADAG. See Section 5.5.
- Assign directions to all interfaces that are still UNDIRECTED. See Section 5.6.
- From the computing router x, compute the next hops for the MRT-Blue and MRT-Red. See Section 5.7.
- Identify alternates for each next hop to each destination by determining which one of the MRT-Blue and the MRT-Red the computing router x should select. See Section 5.8.
A Python implementation of this algorithm is in Appendix A 🐍
5.1. Interface Ordering ✨
so to keep the computation consistent, all routers MUST order interfaces identically, all the way down to the set of links with the same metric to the same neighboring node 🫶 This matters for the DFS in Lowpoint_Visit in Section 4.3, because the order you pick interfaces to explore changes the trees you get. It also matters for building the GADAG, since the order you pick interfaces to form ears can change the GADAG. And it matters for the topological sort in Section 5.8, because different sort orders can push undirected links into the GADAG in different directions 😭
the required ordering between two interfaces from the same router x is in Figure 14 💅
Interface_Compare(interface a, interface b)
if a.metric < b.metric
return A_LESS_THAN_B
if b.metric < a.metric
return B_LESS_THAN_A
if a.neighbor.mrt_node_id < b.neighbor.mrt_node_id
return A_LESS_THAN_B
if b.neighbor.mrt_node_id < a.neighbor.mrt_node_id
return B_LESS_THAN_A
// Same metric to same node, so the order doesn't matter for
// interoperability.
return A_EQUAL_TO_B
Figure 14: Rules for Ranking Multiple Interfaces (Order Is from Low to High)if two interfaces on a router connect to the same remote router with the same metric, Interface_Compare returns A_EQUAL_TO_B 🙈 That's because the order you explore those interfaces in doesn't change the final GADAG. Only one of the links gets added during the initial traversal, but the other parallel links end up in the GADAG with the same direction, thanks to the procedure for assigning direction to UNDIRECTED links in Section 5.6. An implementation is free to add extra criteria to break ties here, but those criteria aren't specified in this document, since they won't change the final GADAG either 🌸
the Interface_Compare function in Figure 14 relies on interface.metric and interface.neighbor.mrt_node_id to order interfaces. The exact source of those values for each IGP and application is in Figure 15. The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS given here are normative. The ones for IS-IS Path Control and Reservation (PCR) in this table should be considered informational. The normative values are specified in [IEEE8021Qca] 📚
+--------------+-----------------------+-----------------------------+
| IGP/flooding | mrt_node_id | metric of |
| protocol | of neighbor | interface |
| and | on interface | |
| application | | |
+--------------+-----------------------+-----------------------------+
| OSPFv2 for | 4-octet Neighbor | 2-octet Metric field |
| IP/LDP FRR | Router ID in | for corresponding |
| | Link ID field for | point-to-point link |
| | corresponding | in Router-LSA |
| | point-to-point link | |
| | in Router-LSA | |
+--------------+-----------------------+-----------------------------+
| OSPFv3 for | 4-octet Neighbor | 2-octet Metric field |
| IP/LDP FRR | Router ID field | for corresponding |
| | for corresponding | point-to-point link |
| | point-to-point link | in Router-LSA |
| | in Router-LSA | |
+--------------+-----------------------+-----------------------------+
| IS-IS for | 7-octet neighbor | 3-octet metric field |
| IP/LDP FRR | system ID and | in Extended IS |
| | pseudonode number | Reachability TLV (type 22) |
| | in Extended IS | or Multi-Topology |
| | Reachability TLV (type| IS Neighbor TLV (type 222) |
| | 22) or Multi-Topology | |
| | IS Neighbor TLV (type | |
| | 222) | |
+--------------+-----------------------+-----------------------------+
| IS-IS PCR for| 8-octet Bridge ID | 3-octet SPB-LINK-METRIC in |
| protection | created from 2-octet | SPB-Metric sub-TLV (type 29)|
| of traffic | Bridge Priority in | in Extended IS Reachability |
| in bridged | Shortest Path Bridging| TLV (type 22) or |
| |SPB Instance sub-TLV | Multi-Topology |
| networks | (type 1) carried in | Intermediate Systems |
| | MT-Capability TLV | TLV (type 222). In the case|
| | (type 144) and 6-octet| of asymmetric link metrics, |
| | neighbor system ID in | the larger link metric |
| | Extended IS | is used for both link |
| | Reachability TLV (type| directions. |
| | 22) or Multi-Topology | (informational) |
| | Intermediate Systems | |
| | TLV (type 222) | |
| | (informational) | |
+--------------+-----------------------+-----------------------------+
Figure 15: Value of interface.neighbor.mrt_node_id and
interface.metric to Be Used for Ranking Interfaces, for Different
Flooding Protocols and Applicationsthe metrics are unsigned integers, and they MUST be compared as unsigned integers 🔢 Also, the results of mrt_node_id comparisons MUST be the same as what you'd get by converting the mrt_node_ids to unsigned integers using network byte order and then comparing them as unsigned integers. Just a heads up for IS-IS for IP/LDP FRR with point-to-point links: the pseudonode number (the 7th octet) is zero 🧚 Broadcast interfaces get their own discussion in Section 7 🎀
5.2. MRT Island Identification
Okay so, the local MRT Island for a particular MRT profile can be figured out by starting at the computing router in the network graph and running a breadth-first-search (BFS) 🦋. The BFS only explores links that are in the same area/level, are not IGP-excluded, and are not MRT-ineligible ✨. It also only explores nodes that support that specific MRT profile 💅. For the more-precise definitions of all this, check out Section 7 of [RFC7812] 🤓.
MRT_Island_Identification(topology, computing_rtr, profile_id, area)
for all routers in topology
rtr.IN_MRT_ISLAND = FALSE
computing_rtr.IN_MRT_ISLAND = TRUE
explore_list = { computing_rtr }
while (explore_list is not empty)
next_rtr = remove_head(explore_list)
for each intf in next_rtr
if (not intf.IN_MRT_ISLAND
and not intf.MRT-ineligible
and not intf.remote_intf.MRT-ineligible
and not intf.IGP-excluded and (intf in area)
and (intf.remote_node supports profile_id) )
intf.IN_MRT_ISLAND = TRUE
intf.remote_intf.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
5.3. GADAG Root Selection
In Section 8.3 of [RFC7812], the GADAG Root Selection Policy gets described for the Default MRT Profile 👑. This selection policy lets routers consistently pick a common GADAG Root inside the local MRT Island, based on advertised priority values 🫶. The MRT Lowpoint algorithm basically just needs every router in the MRT Island to MUST select the same GADAG Root 🔥, and how they do that can change depending on the MRT profile description. Before computation even starts, the network graph gets trimmed down to only the routers that support the specific MRT profile whose MRTs are being computed 🧚.
Also, pseudonodes MUST NOT be considered for GADAG root selection 🙈. (As noted in Section 7, of course.)
It's expected that an operator will pick out a set of routers as good GADAG root choices by setting the GADAG Root Selection Priority for those routers to lower numerical values, since lower means more preferred 🌸. For guidance on setting those GADAG Root Selection Priority values, go look at Section 9.1 💜.
5.4. Initialization
Before running the algorithm, there's the usual kind of setup to do 🧹, like clearing out any computed DFS-values, lowpoint-values, DFS parents, lowpoint-parents, any MRT-computed next hops, and the flags tied to the algorithm 🍓.
It's assumed that a regular SPF computation has already run, so the primary next hops from the computing router to each destination are known. This is required for figuring out alternates at the last step 🔍.
Initially, every interface MUST be initialized to UNDIRECTED 🦋. Whether each one ends up OUTGOING, INCOMING, or both gets decided when the GADAG is constructed and augmented ✨.
Some links and nodes might already be marked, using standard IGP mechanisms, to discourage or prevent transit traffic. Section 7.3.1 of [RFC7812] explains how those links and nodes get excluded from MRT Island formation 🚧.
MRT-FRR can also advertise links as MRT-Ineligible, which is described in Section 7.3.2 of [RFC7812] 💀. These links get excluded from the MRT Island and the GADAG, so computing MRT next hops won't use any MRT-ineligible links. But the MRT Lowpoint algorithm still has 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, the pseudonode representing the entire broadcast network MUST NOT be included in the MRT Island. That's basically the same as excluding all of the broadcast interfaces on that broadcast network from the MRT Island. Don't skip this one, bestie 🚨.
5.5. Constructing the GADAG Using Lowpoint Inheritance
Okay, so as we talked about in Section 4.2, we need to find ears from a node x that's already in the GADAG (known as IN_GADAG) 🌈. There are two methods for finding ears here. The first one goes to a DFS-child that isn't IN_GADAG, then follows the chain of lowpoint parents until it hits an IN_GADAG node. The second one goes to a neighbor that isn't IN_GADAG, then follows the chain of DFS parents until it hits an IN_GADAG node 🌸. Every time an ear gets found, its interfaces get marked based on the direction taken, and the nodes in the ear get marked IN_GADAG ✨. In the algorithm, the ears via DFS-children get found first, and then the ears via DFS-neighbors 💅.
If you process an IN_GADAG node, adding both types of ears means you find all the ears connecting to that node 🫶. The order you process the IN_GADAG nodes in is, obviously, key to the whole algorithm 🔑. That order is a stack of ears, so the most recent ear sits at the top. Since the stack actually stores nodes and not ears, an ordered list of nodes (from the first node in the ear to the last) gets built while the ear is explored, and then that list gets pushed onto the stack 🥞.
Each ear represents a partial order (see Figure 4), and processing the nodes in order along each ear makes sure all the ears connecting to a node are found before a node higher in the partial order has its ears explored 👑. So the direction of the links in an ear always goes from the node x being processed toward the other end of the ear. And because it's a stack of ears, any unprocessed nodes in previous ears can only be ordered higher than the nodes in the ears below them on the stack 🦋.
This algorithm relies on Lowpoint inheritance, so every node needs a lowpoint parent that isn't itself 🧠. A cut-vertex might not have that yet, though. So any node without a lowpoint parent gets its lowpoint parent set to its DFS parent, and its lowpoint value set to the DFS-value of that parent. This assignment also properly allows an ear between two cut-vertices 🎀.
Finally, the algorithm computes each node's localroot at the same time, as described in Figure 12 🧚. Here's the extra detail: the localroot can be inherited from the node at the end of the ear, unless the end of the ear is x itself. In that case, the localroot for all the nodes in the ear would be x. The reason is that whenever the first cycle is found in a block, or an ear involving a bridge is computed, the cut-vertex closest to the root would be x itself 💖. In every other scenario, the properties of lowpoint/dfs parents make sure the end of the ear is in the same block, so inheriting its localroot is the correct localroot for all the newly added nodes 🌈.
The pseudocode for the GADAG algorithm (assuming the lowpoint adjustment for cut-vertices has been made) is in Figure 17 below 💅.
Construct_Ear(x, Stack, intf, ear_type)
ear_list = empty
cur_node = intf.remote_node
cur_intf = intf
not_done = true
while not_done
cur_intf.UNDIRECTED = false
cur_intf.OUTGOING = true
cur_intf.remote_intf.UNDIRECTED = false
cur_intf.remote_intf.INCOMING = true
if cur_node.IN_GADAG is false
cur_node.IN_GADAG = true
add_to_list_end(ear_list, cur_node)
if ear_type is CHILD
cur_intf = cur_node.lowpoint_parent_intf
cur_node = cur_node.lowpoint_parent
else // ear_type must be NEIGHBOR
cur_intf = cur_node.dfs_parent_intf
cur_node = cur_node.dfs_parent
else
not_done = false
if (ear_type is CHILD) and (cur_node is x)
// x is a cut-vertex and the local root for
// the block in which the ear is computed
x.IS_CUT_VERTEX = true
localroot = x
else
// Inherit localroot from the end of the ear
localroot = cur_node.localroot
while ear_list is not empty
y = remove_end_item_from_list(ear_list)
y.localroot = localroot
push(Stack, y)
Construct_GADAG_via_Lowpoint(topology, gadag_root)
gadag_root.IN_GADAG = true
gadag_root.localroot = None
Initialize Stack to empty
push gadag_root onto Stack
while (Stack is not empty)
x = pop(Stack)
foreach ordered_interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is x))
Construct_Ear(x, Stack, intf, CHILD)
foreach ordered_interface intf of x
if ((intf.remote_node.IN_GADAG == false) and
(intf.remote_node.dfs_parent is not x))
Construct_Ear(x, Stack, intf, NEIGHBOR)
Construct_GADAG_via_Lowpoint(topology, gadag_root)Figure 17: Lowpoint Inheritance GADAG Algorithm
5.6. Augmenting the GADAG by Directing All Links
The GADAG, regardless of the method used to construct it, at this point could be used to find MRTs, but the topology does not include all links in the network graph. That has two impacts. First, there might be shorter paths that respect the GADAG partial ordering and so the alternate paths would not be as short as possible. Second, there may be additional paths between a router x and the root that are not included in the GADAG. Including those provides potentially more bandwidth to traffic flowing on the alternates and may reduce congestion compared to just using the GADAG as currently constructed.
The goal is thus to assign direction to every remaining link marked as UNDIRECTED to improve the paths and number of paths found when the MRTs are computed.
To do this, we need to establish a total order that respects the partial order described by the GADAG. This can be done using Kahn's topological sort [Kahn_1962_topo_sort], which essentially assigns a number to a node x only after all nodes before it (e.g., with a link incoming to x) have had their numbers assigned. The only issue with the topological sort is that it works on DAGs and not ADAGs or GADAGs.
To convert a GADAG to a DAG, it is necessary to remove all links that point to a root of block from within that block. That provides the necessary conversion to a DAG and then a topological sort can be done. When adding undirected links to the GADAG, links connecting the block root to other nodes in that block need special handling because the topological order will not always give the right answer for those links. There are three cases to consider. If the undirected link in question has another parallel link between the same two nodes that is already directed, then the direction of the undirected link can be inherited from the previously directed link. In the case of parallel cut links, we set all of the parallel links to both INCOMING and OUTGOING. Otherwise, the undirected link in question is set to OUTGOING from the block root node. A cut-link can then be identified by the fact that it will be directed both INCOMING and OUTGOING in the GADAG. The exact details of this whole process are captured in Figure 18.
Add_Undirected_Block_Root_Links(topo, gadag_root) foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if (i.remote_node.localroot is not x or i.PROCESSED ) continue Initialize bundle_list to empty bundle.UNDIRECTED = true bundle.OUTGOING = false bundle.INCOMING = false foreach interface i2 in x if i2.remote_node is i.remote_node add_to_list_end(bundle_list, i2) if not i2.UNDIRECTED: bundle.UNDIRECTED = false if i2.INCOMING: bundle.INCOMING = true if i2.OUTGOING: bundle.OUTGOING = true if bundle.UNDIRECTED foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.remote_intf.INCOMING = true else if (bundle.OUTGOING and bundle.INCOMING) foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.INCOMING = true i3.remote_intf.INCOMING = true i3.remote_intf.OUTGOING = true
else if bundle.OUTGOING foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.OUTGOING = true i3.remote_intf.INCOMING = true else if bundle.INCOMING foreach interface i3 in bundle_list i3.UNDIRECTED = false i3.remote_intf.UNDIRECTED = false i3.PROCESSED = true i3.remote_intf.PROCESSED = true i3.INCOMING = true i3.remote_intf.OUTGOING = true
Modify_Block_Root_Incoming_Links(topo, gadag_root) foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if i.remote_node.localroot is x if i.INCOMING: i.INCOMING = false i.INCOMING_STORED = true i.remote_intf.OUTGOING = false i.remote_intf.OUTGOING_STORED = true
Revert_Block_Root_Incoming_Links(topo, gadag_root) foreach node x in topo if x.IS_CUT_VERTEX or x is gadag_root foreach interface i of x if i.remote_node.localroot is x if i.INCOMING_STORED i.INCOMING = true i.remote_intf.OUTGOING = true i.INCOMING_STORED = false i.remote_intf.OUTGOING_STORED = false
Run_Topological_Sort_GADAG(topo, gadag_root) Modify_Block_Root_Incoming_Links(topo, gadag_root) foreach node x in topo node.unvisited = 0 foreach interface i of x if (i.INCOMING) node.unvisited += 1 Initialize working_list to empty Initialize topo_order_list to empty add_to_list_end(working_list, gadag_root) while working_list is not empty y = remove_start_item_from_list(working_list) add_to_list_end(topo_order_list, y) foreach ordered_interface i of y if intf.OUTGOING i.remote_node.unvisited -= 1 if i.remote_node.unvisited is 0 add_to_list_end(working_list, i.remote_node) next_topo_order = 1 while topo_order_list is not empty y = remove_start_item_from_list(topo_order_list) y.topo_order = next_topo_order next_topo_order += 1 Revert_Block_Root_Incoming_Links(topo, gadag_root)
def Set_Other_Undirected_Links_Based_On_Topo_Order(topo) foreach node x in topo foreach interface i of x if i.UNDIRECTED: if x.topo_order < i.remote_node.topo_order i.OUTGOING = true i.UNDIRECTED = false i.remote_intf.INCOMING = true i.remote_intf.UNDIRECTED = false else i.INCOMING = true i.UNDIRECTED = false i.remote_intf.OUTGOING = true i.remote_intf.UNDIRECTED = false
Add_Undirected_Links(topo, gadag_root) Add_Undirected_Block_Root_Links(topo, gadag_root) Run_Topological_Sort_GADAG(topo, gadag_root) Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
Add_Undirected_Links(topo, gadag_root)
Figure 18: Assigning Direction to UNDIRECTED Links
Proxy-nodes do not need to be added to the network graph. They cannot be transited and do not affect the MRTs that are computed. The details of how the MRT-Blue and MRT-Red next hops are computed for proxy-nodes and how the appropriate alternate next hops are selected is given in Section 5.9.
5.7. Compute MRT Next Hops
As was discussed in Section 4.1, once an ADAG is found, it is straightforward to find the next hops from any node X to the ADAG root. However, in this algorithm, we will reuse the common GADAG and find not only the one pair of MRTs rooted at the GADAG root with it, but find a pair rooted at each node. This is useful since it is significantly faster to compute.
The method for computing differently rooted MRTs from the common GADAG is based on two ideas. First, if two nodes X and Y are ordered with respect to each other in the partial order, then an SPF along OUTGOING links (an increasing-SPF) and an SPF along INCOMING links (a 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 each other in the partial order, then intermediary nodes can be used to create the paths by increasing/decreasing to the intermediary and then decreasing/increasing to reach Y.
As usual, the two basic ideas will be discussed assuming the network is 2-connected. The generalization to multiple blocks is discussed in Section 5.7.4. The full algorithm is given in Section 5.7.5.
5.7.1. MRT Next Hops to All Nodes Ordered with Respect to the Computing Node
Finding two node-disjoint paths from the computing router X to any node Y depends upon whether Y>>X or Y<<X. As shown in 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]. There is also a decreasing path that decreases towards R and then 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 other than X and Y.
[Y]<---(Cloud 2)<--- [X]
| ^ |
V | (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 2->Y MRT-Red path: X->Cloud 1->R->Cloud 3->Y
Figure 19: Y>>X
Similar logic applies if Y<<X, as shown in Figure 20. In this case, the increasing path from X increases to R and then increases from R to Y to use nodes in the intervals [X,R-great] and [R-small, Y]. The decreasing path from X reaches Y without crossing R and uses nodes in the interval [Y,X].
[X]<---(Cloud 2)<--- [Y]
| ^ |
V | (Cloud 3)--->[R]--->(Cloud 1)
MRT-Blue path: X->Cloud 3->R->Cloud 1->Y MRT-Red path: X->Cloud 2->Y
Figure 20: Y<<X
5.7.2. MRT Next Hops to All Nodes Not Ordered with Respect to the Computing Node 💅
okay so when X and Y are not ordered, the first path should climb up until we hit a node G where G>>Y. At G we need to come back down to Y. The other path is basically the mirror image: we go down until we reach a node H where H<<Y, and then we climb back up. Since R is both smaller and greater than Y, both G and H have to exist ✨
It's also pretty easy to see that these two paths have to be node disjoint 🦋. The first path only touches nodes in the intervals [X,G] and [Y,G], while the second path only touches nodes in [H,X] and [H,Y]. Check out Figure 21 to see it all laid out:
(Cloud 6)<---[Y]<---(Cloud 5)<------------|
| |
| |
V |
[G]--->(Cloud 4)--->[R]--->(Cloud 1)--->[H]
^ |
| |
| |
(Cloud 3)<---[X]<---(Cloud 2)<-----------|
MRT-Blue path: decrease to H and increase to Y
X->Cloud 2->H->Cloud 5->Y
MRT-Red path: increase to G and decrease to Y
X->Cloud 3->G->Cloud 6->Y
Figure 21: X and Y UnorderedThe MRT-Blue path has to decrease and then increase, and the MRT-Red path has to increase and then decrease. If one of them just went up and the other just went down, then both paths would run through the root R, and that's a no-go 🙅♀️.
This gives disjoint paths as long as G and H are not the same node. Since G>>Y and H<<Y, if G and H could be the same node, that node would have to be the root R. But that can't happen, because there's only one incoming interface to the root R, and it's created when the initial cycle is found. Remember from Figure 6 that whenever an ear had an end at the root R, the ear was directed away from R, so the matching interface on R is outgoing and not incoming. So there has to be exactly one node M that is the largest one before R. That means the MRT-Red path never reaches R. It turns at M and decreases to Y 👑.
5.7.3. Computing Redundant Tree Next Hops in a 2-Connected Graph 🎀
The basic ideas for computing RT next hops in a 2-connected graph were covered in Sections 5.7.1 and 5.7.2. So now the big question is: how do we actually find the trees? 🤔
If some node X only wants its next hops (which is usually the case for IP networks), it's enough to figure out which nodes are greater than X, which are less than X, and which are not ordered. You can do that by running an increasing-SPF and a decreasing-SPF rooted at X, and by not exploring any links from the ADAG root.
In principle, a traversal method other than SPF could be used to walk the GADAG while figuring out the blue and red next hops that give maximally redundant trees. That works as long as one traversal uses the links in the direction the GADAG specifies, and the other traversal uses the links in the opposite direction. The catch is that a different traversal algorithm will generally give different blue and red next hops. So the algorithm in this document requires SPF to traverse the GADAG when generating the MRT blue and red next hops, as described below 🧚.
An increasing-SPF rooted at X that doesn't explore links from the root will find the increasing next hops to all Y>>X. Those are X's next hops on the MRT-Blue to reach Y. A decreasing-SPF rooted at X that doesn't explore links from the root will find the decreasing next hops to all Z<<X. Those are X's next hops on the MRT-Red to reach Z. The root R is both greater than and less than X, so after running both SPFs, X knows its MRT-Blue and MRT-Red next hops to reach R. Then, for every node Y>>X, X's MRT-Red next hops to reach Y get set to the MRT-Red next hops to reach R. And for every node Z<<X, X's MRT-Blue next hops to reach Z get set to the MRT-Blue next hops to reach R. Iconic, honestly 💖.
What about the nodes that neither the increasing-SPF nor the decreasing-SPF reached? We can work those out too 🌸. The increasing MRT-Blue next hop for a node that isn't ordered with respect to X is the next hop along the decreasing MRT-Red path towards R. And the decreasing MRT-Red next hop is the next hop along the increasing MRT-Blue path towards R. Since R is ordered with respect to every node, there's always an increasing path and a decreasing path towards it. This algorithm doesn't give you the full specific path taken, just the right next hops to use. Also, the computing node X doesn't determine the identities of G and H.
The last case is when the GADAG root R computes its own next hops. Since R is smaller than every other node, an increasing-SPF rooted at R reaches all the other nodes, and the MRT-Blue next hops are the ones found by that increasing-SPF. Similarly, since R is greater than every other node, a decreasing-SPF rooted at R reaches all the other nodes, and the MRT-Red next hops are the ones found by that decreasing-SPF 🌈.
Here's an example to make it click. Take a look at Figure 22:
E---D---| E<--D<--|
| | | | ^ |
| | | V | |
R F C R F C
| | | | ^ ^
| | | V | |
A---B---| A-->B---|
(a) (b)
A 2-connected graph A spanning ADAG rooted at R
Figure 22Node C runs an increasing-SPF and a decreasing-SPF on the ADAG. The increasing-SPF reaches D, E, and R, and the decreasing-SPF reaches B, A, and R. Since E>>C, towards E the MRT-Blue next hop is D, because E was reached on the increasing path through D. The MRT-Red next hop towards E is B, because R was reached on the decreasing path through B. Then, since E>>D, D works out its MRT-Blue next hop to be E, so a packet on MRT-Blue takes the path C-D-E. B, A, and R work out the MRT-Red next hops towards E (which is ordered less than B, A, and R), so a packet on MRT-Red takes the path C-B-A-R-E. ✨
C can figure out the next hops towards F too. F isn't ordered with respect to C, so the MRT-Blue next hop is the decreasing one towards R (which is B), and the MRT-Red next hop is the increasing one towards R (which is D). Since F>>B, B uses the real increasing next hop towards F as its MRT-Blue next hop towards F. So a packet forwarded to B on MRT-Blue gets to F along C-B-F. In the same way, D uses the real decreasing next hop towards F as its MRT-Red next hop, so a packet on MRT-Red takes C-D-F. 🫶
5.7.4. Generalizing for a Graph That Isn't 2-Connected 🍓
If a graph isn't 2-connected, the basic approach from Section 5.7.3 needs a few extensions so we can pick the right MRT next hops for destinations outside the computing router X's blocks. To find a pair of maximally redundant trees in that kind of graph, we need to find a pair of RTs in each of the blocks (the root of these trees gets covered later) and then combine them 💜.
When computing the MRT next hops from a router X, there are three basic differences:
- Only nodes in a common block with X should be explored in the increasing-SPF and decreasing-SPF.
- Instead of using the GADAG root, X's localroot should be used. This has the following implications:
- A. The links from X's localroot should not be explored.
- B. If a node is explored in the outgoing SPF so Y>>X, then X's MRT-Red next hops to reach Y use X's MRT-Red next hops to reach X's localroot. And if Z<<X, then X's MRT-Blue next hops to reach Z use X's MRT-Blue next hops to reach X's localroot.
- C. If a node W in a common block with X was not reached in the increasing-SPF or decreasing-SPF, then W is unordered with respect to X. X's MRT-Blue next hops to W are X's decreasing (aka MRT-Red) next hops to X's localroot. X's MRT-Red next hops to W are X's increasing (aka MRT-Blue) next hops to X's localroot.
- For nodes in different blocks, the next hops must be inherited via the relevant cut-vertex.
All of these are captured in the detailed algorithm given in Section 5.7.5. Bestie, you're doing amazing 🎀💅
5.7.5. Complete Algorithm to Compute MRT Next Hops ✨
okay so bestie, this is where everything comes together 🫶 The full algorithm for working out MRT Next Hops for a particular router X is in Figure 23 💅 Besides figuring out the MRT-Blue next hops and MRT-Red next hops that X uses to reach each node Y, it also stores an order_proxy. That's the proper cut-vertex you use to reach Y when Y is outside the block, and it gets used later to decide whether MRT-Blue or MRT-Red can be an acceptable alternate for a given primary next hop 🦋
In_Common_Block(x, y)
if ( (x.block_id is y.block_id)
or (x is y.localroot) or (y is x.localroot) )
return true
return false
Store_Results(y, direction)
if direction is FORWARD
y.higher = true
y.blue_next_hops = y.next_hops
if direction is REVERSE
y.lower = true
y.red_next_hops = y.next_hops
SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
Store_Results(min_node, direction)
if ((min_node is spf_root) or (min_node is not block_root))
foreach interface intf of min_node
if ( ( ((direction is FORWARD) and intf.OUTGOING) or
((direction is REVERSE) 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 = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
SetEdge(y)
if y.blue_next_hops is empty and y.red_next_hops is empty
SetEdge(y.localroot)
y.blue_next_hops = y.localroot.blue_next_hops
y.red_next_hops = y.localroot.red_next_hops
y.order_proxy = y.localroot.order_proxy
Compute_MRT_NextHops(x, gadag_root)
foreach node y
y.higher = y.lower = false
clear y.red_next_hops and y.blue_next_hops
y.order_proxy = y
SPF_No_Traverse_Block_Root(x, x.localroot, FORWARD)
SPF_No_Traverse_Block_Root(x, x.localroot, REVERSE)
// red and blue next hops are stored to x.localroot as different
// paths are found via the SPF and reverse-SPF.
// Similarly, any node whose localroot is x will have its
// red_next_hops and blue_next_hops already set.
// Handle nodes in the same block that aren't the localroot
foreach node y
if (y.IN_MRT_ISLAND and (y is not x) and
(y.block_id is x.block_id) )
if y.higher
y.red_next_hops = x.localroot.red_next_hops
else if y.lower
y.blue_next_hops = x.localroot.blue_next_hops
else
y.blue_next_hops = x.localroot.red_next_hops
y.red_next_hops = x.localroot.blue_next_hops
// Inherit next hops and order_proxies to other components
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.red_next_hops = x.localroot.red_next_hops
gadag_root.order_proxy = x.localroot
foreach node y
if (y is not gadag_root) and (y is not x) and y.IN_MRT_ISLAND
SetEdge(y)
max_block_id = 0
Assign_Block_ID(gadag_root, max_block_id)
Compute_MRT_NextHops(x, gadag_root)
Figure 23: Complete Algorithm to Compute MRT Next Hops5.8. Identify MRT Alternates 🎀
okay so at this point, a computing router S knows its MRT-Blue next hops and MRT-Red next hops for each destination in the MRT Island 💖 It also knows the primary next hops along the SPT. What's left is figuring out, for each primary next hop to a destination D, which MRT avoids the primary next-hop node F. This depends on data that Compute_MRT_NextHops already set, like each node y's y.blue_next_hops, y.red_next_hops, y.order_proxy, y.higher, y.lower, and topo_orders. Here's the tea: any router only knows which nodes are greater or lesser than itself, but it can't easily tell how two random nodes relate to each other. That's exactly why we need topological ordering 🧚
For each primary next-hop node F to each destination D, S can call Select_Alternates(S, D, F, primary_intf) to decide whether to use the MRT-Blue or MRT-Red next hops as the alternate next hop(s) for that primary next hop. The algorithm is in Figure 24 and we'll talk through it after 💅
Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order):
if D_higher and D_lower
if F.HIGHER and F.LOWER
if F.topo_order < D_topo_order
return USE_RED
else
return USE_BLUE
if F.HIGHER
return USE_RED
if F.LOWER
return USE_BLUE
//F unordered wrt S
return USE_RED_OR_BLUE
else if D_higher
if F.HIGHER and F.LOWER
return USE_BLUE
if F.LOWER
return USE_BLUE
if F.HIGHER
if (F.topo_order > D_topo_order)
return USE_BLUE
if (F.topo_order < D_topo_order)
return USE_RED
//F unordered wrt S
return USE_RED_OR_BLUE
else if D_lower
if F.HIGHER and F.LOWER
return USE_RED
if F.HIGHER
return USE_RED
if F.LOWER
if F.topo_order > D_topo_order
return USE_BLUE
if F.topo_order < D_topo_order
return USE_RED
//F unordered wrt S
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
return USE_RED_OR_BLUE
if primary_intf.OUTGOING
return USE_BLUE
if primary_intf.INCOMING
return USE_RED
//primary_intf not in GADAG
return USE_RED
if F.LOWER
return USE_RED
if F.HIGHER
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)
if not In_Common_Block(F, S)
return PRIM_NH_IN_DIFFERENT_BLOCK
if (D is F) or (D.order_proxy is F)
return PRIM_NH_IS_D_OR_OP_FOR_D
D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order)
Figure 24: Select_Alternates() and Select_Alternates_Internal()It's useful to handle the case where F is also D, or F is the order proxy for D, first 🦋 In that case only link protection is possible. The MRT that doesn't use the failed primary next hop gets used. If both MRTs use the primary next hop, then that primary next hop has to be a cut-link. So either MRT could work, but the set of MRT next hops needs pruning to avoid the failed primary next-hop interface. To flag this case, Select_Alternates returns PRIM_NH_IS_D_OR_OP_FOR_D. Explicit pseudocode for the three sub-cases above isn't provided 🙈
The logic behind Select_Alternates_Internal() is in Figure 25. Let's use the first case in the table as an example: D>>S and D<<S. If that's true, then either S or D has to be the block root, R. If F>>S and F<<S, then S is the block root. So the blue path from S to D is the increasing path to D, and the red path from S to D is the decreasing path to D. Now if F.topo_order>D.topo_order, then either F is ordered higher than D or F is unordered with respect to D. That means F is either on a decreasing path from S to D, or it's on neither an increasing nor a decreasing path from S to D. Either way, it's safe to take an increasing path from S to D to dodge F. We know that when S is R, the increasing path is the blue path, so using blue avoids F 🌈
Now if instead F.topo_order<D.topo_order, then either F is ordered lower than D or F is unordered with respect to D. So F is either on an increasing path from S to D, or it's on neither kind of path. Either way, it's safe to take a decreasing path from S to D to avoid F. We know that when S is R, the decreasing path is the red path, so using red avoids F ✨
If F>>S or F<<S (but not both), then D is the block root. In that case the blue path from S to D is the increasing path to R, and the red path is the decreasing path to R. When F>>S, we can deduce that F is on an increasing path from S to R. So to avoid F, we take a decreasing path from S to R, which is the red path. On the flip side, when F<<S, we deduce that F is on a decreasing path from S to R. So to avoid F, we take an increasing path from S to R, which is the blue path 💜
All the other possible cases are handled the same way in the rest of the table 🍓
+------+------------+------+------------------------------+------------+
| D | MRT blue | F | additional | F | Alternate |
| wrt | and red | wrt | criteria | wrt | |
| S | path | S | | MRT | |
| | properties | | | (deduced) | |okay bestie, the table is the main event here 💅 it's giving decision tree, and every row is a little "use this color to avoid F" moment 🦋
+------+------------+------+-----------------+------------+------------+
| D>>S | Blue path: | F>>S | additional | F on an | Use Red |
| and | Increasing | only | criteria | increasing | to avoid |
| D<<S,| path to R. | | not needed | path from | F |
| D is | Red path: | | | S to R | |
| R, | Decreasing +------+-----------------+------------+------------+
| | path to R. | F<<S | additional | F on a | Use Blue |
| | | only | criteria | decreasing | to avoid |
| | | | not needed | path from | F |
| or | | | | S to R | |
| | +------+-----------------+------------+------------+
| | | F>>S | topo(F)>topo(D) | F on a | Use Blue |
| S is | Blue path: | and | implies that | decreasing | to avoid |
| R | Increasing | F<<S,| F>>D or F??D | path from | F |
| | path to D. | | | S to D or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | path to D. | | topo(F)<topo(D) | F on an | Use Red |
| | | | implies that | increasing | to avoid |
| | | | F<<D or F??D | path from | F |
| | | | | S to D or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | 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 |
| only | Increasing | only | criteria | decreasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to D. +------+-----------------+------------+------------+
| | Red path: | F>>S | topo(F)>topo(D) | F on | Use Blue |
| | Decreasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | S to R, | | | or | |
| | then | | | neither | |
| | decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | R to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Red | Use Blue |
| | | and | criteria | | to avoid |
| | | F<<S,| not needed | | F |
| | | F is | | | |
| | | R | | | |
| | +------+-----------------+------------+------------+
| | | 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 |
| only | Increasing | only | criteria | increasing | to avoid |
| | shortest | | not needed | path from | F |
| | path from | | | S to R | |
| | S to R, +------+-----------------+------------+------------+
| | then | F<<S | topo(F)>topo(D) | F on | Use Blue |
| | increasing | only | implies that | decreasing | to avoid |
| | shortest | | F>>D or F??D | path from | F |
| | path from | | | R to D | |
| | R to D. | | | or | |
| | Red path: | | | neither | |
| | Decreasing | +-----------------+------------+------------+
| | shortest | | topo(F)<topo(D) | F on | Use Red |
| | path from | | implies that | increasing | to avoid |
| | S to D. | | F<<D or F??D | path from | F |
| | | | | S to D | |
| | | | | or | |
| | | | | neither | |
| | +------+-----------------+------------+------------+
| | | F>>S | additional | F on Blue | Use Red |
| | | and | criteria | | to avoid |
| | | F<<S,| not | | F |
| | | F is | needed | | |
| | | R | | | |
| | +------+-----------------+------------+------------+
| | | 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 | |
| | | | | S to D or R| |
+------+------------+------+-----------------+------------+------------+
| D??S | Blue path: | F<<S | additional | F on a | Use Red |
| | Decr. from | only | criteria | decreasing | to avoid |
| | S to first | | not needed | path from | F |
| | node K<<D, | | | S to K. | |
| | then incr. +------+-----------------+------------+------------+
| | to D. | F>>S | additional | F on an | Use Blue |
| | Red path: | only | criteria | increasing | to avoid |
| | Incr. from | | not needed | path from | F |
| | S to first | | | S to L | |
| | node L>>D, | | | | |
| | then decr. | | | | |
| | +------+-----------------+------------+------------+
| | | F??S | 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 |
| | | and | direction | incr. path | to avoid |
| | | F<<S,| S->F | from S | F |
| | | F is +-----------------+------------+------------+
| | | R | GADAG link | F on a | Use Red |
| | | | direction | decr. path | to avoid |
| | | | S<-F | from S | F |
| | | +-----------------+------------+------------+
| | | | GADAG link | Either F is the order |
| | | | direction | proxy for D (case |
| | | | 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) |
+------+------------+------+-----------------+-------------------------++------+------------+------+-----------------+-------------------------+
Determining MRT next hops and alternates based on the partial order
and topological sort relationships between the source(S),
destination(D), primary next hop(F), and block root(R). 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 assumed that the
case where F is D, or where F is the order proxy for D, has already
been handled.
Figure 25: Determining MRT Next Hops and Alternatesokay so the last case in Figure 25 needs a little extra explaining, bestie 🧠 the red path from S to D avoiding F only works because of a special property of the GADAGs we build in this algorithm. Not every GADAG has it, so it's giving "not all graphs are created equal" 💅
When D is unordered with respect to S and F is the localroot for S, the link between S and F can only be missing from the GADAG if that link was marked MRT_INELIGIBLE. For an arbitrary GADAG, S doesn't have enough order info to tell whether the red or blue path will hit F (which is also the localroot) before hitting K or L and safely making it to D. 😬
BUT the GADAGs from this document's algorithm are not arbitrary. Incoming links to a localroot come from only one other node in the same block, because of how they're constructed 🫶 That means the red path from S to D will never pass through the localroot of S. (Why? That would make the localroot play the role of L, the first node ordered higher than D, which would mean it has two incoming links in the GADAG, and that literally cannot happen 💀) So using the red path to dodge F is safe with these specially built GADAGs ✨
Let's do an example of how Select_Alternates_Internal() operates 🦋 Check out the ADAG in Figure 26. Say 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 is either higher than H or unordered with respect to H, so we should select the decreasing path towards the root.
If the destination were J instead, we find H.topo_order>J.topo_order, so we must choose the increasing Blue next hop to J, which is I. And when the destination is C, we first need to decrease to avoid using H, so the Blue path goes first decreasing, then increasing, and that's the one that gets selected 🌸
[E]<-[D]<-[H]<-[J]
| ^ ^ ^
V | | |
[R] [C] [G]->[I]
| ^ ^ ^
V | | |
[A]->[B]->[F]---|
Figure 26: ADAG Rooted at R for a 2-Connected Graph5.9. Named Proxy-Nodes ✨
As discussed in Section 11.2 of [RFC7812], it's necessary to find MRT-Blue and MRT-Red next hops and MRT-FRR alternates for named proxy-nodes 🧚 An example use case is a router that is not part of that local MRT Island, when there's only partial MRT support in the domain.
5.9.1. Determining Proxy-Node Attachment Routers 🍓
Section 11.2 of [RFC7812] talks about general considerations for figuring out the two proxy-node attachment routers for a given proxy-node, which corresponds to a prefix. Any router in the MRT Island that advertises the prefix is a candidate for being a proxy-node attachment router, with the associated named-proxy-cost equal to the advertised cost to the prefix.
An Island Border Router (IBR) is a router in the MRT Island that's connected to an Island Neighbor (IN), which is a router not in the MRT Island but in the same area/level. An (IBR,IN) pair is a candidate for being a proxy-node attachment router if the shortest path from the IN to the prefix does not enter the MRT Island. There's a method for identifying these Loop-Free Island Neighbors (LFINs) below. The named-proxy-cost assigned to each (IBR, IN) pair is cost(IBR, IN) + D_opt(IN, prefix).
From the set of prefix-advertising routers and the set of IBRs with at least one LFIN, the two routers with the lowest named-proxy-cost are selected. Ties get broken by the lowest Router ID 🏆 For ease of discussion, those two selected routers are called proxy-node attachment routers.
5.9.2. Computing If an Island Neighbor (IN) Is Loop-Free 🔍
okay so the IN needs to be loop-free with respect to the whole MRT Island for the destination 🫧 This can be done by running the usual SPF algorithm while keeping track of which shortest paths have passed through the MRT island. Here's the pseudocode, shown in Figure 27. Island_Marking_SPF() gets run for each IN that needs checking for the loop-free condition, with the IN as the spf_root. Then you can tell whether or not an IN is loop-free with respect to the MRT island by evaluating node.PATH_HITS_ISLAND for each destination of interest.
Island_Marking_SPF(spf_root)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity and next_hops to empty
and PATH_HITS_ISLAND to false
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
while (spf_heap is not empty)
min_node = remove_lowest(spf_heap)
foreach interface intf of min_node
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
if min_node is spf_root
intf.remote_node.next_hops = make_list(intf)
else
intf.remote_node.next_hops = min_node.next_hops
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
insert_or_update(spf_heap, intf.remote_node)
else if path_metric == intf.remote_node.spf_metric
if min_node is spf_root
add_to_list(intf.remote_node.next_hops, intf)
else
add_list_to_list(intf.remote_node.next_hops,
min_node.next_hops)
if intf.remote_node.IN_MRT_ISLAND
intf.remote_node.PATH_HITS_ISLAND = true
else
intf.remote_node.PATH_HITS_ISLAND =
min_node.PATH_HITS_ISLAND
Figure 27: Island_Marking_SPF() for Determining If an Island Neighbor
Is Loop-FreeIt's also possible that a given prefix is originated by a mix of non-island routers and island routers 💜 The results of the Island_Marking_SPF() computation can be used to tell if the shortest path from an IN to reach that prefix hits the MRT Island. The shortest path for the IN to reach prefix P is determined by the total cost to reach prefix P, which is the sum of the cost for the IN to reach a prefix-advertising node plus the cost with which that node advertises the prefix. The path with the minimum total cost to prefix P gets chosen. If the prefix-advertising node for that minimum total cost path has PATH_HITS_ISLAND set to True, then the IN is not loop-free with respect to the MRT Island for reaching prefix P. If there are multiple minimum total cost paths to reach prefix P, then all of the prefix-advertising routers involved in those paths MUST have PATH_HITS_ISLAND set to False for the IN to be considered loop-free to reach P.
Note that there are other computations that could tell if paths from a given IN might pass through the MRT Island for a given prefix or destination 👀 For example, an earlier draft of this document said to run the SPF algorithm on a modified topology that treats the MRT Island as a single node (with intra-island links set to zero cost), to feed the computations that decide whether the path from an IN to a non-island destination hits the MRT Island in that modified topology. That computation is enough to guarantee that a path won't hit the MRT Island in the original topology. However, a path that gets disqualified for hitting the MRT Island in the modified topology might not actually hit the MRT Island in the original topology. The algorithm described in Island_Marking_SPF() above does not modify the original topology, and it only disqualifies a path if the actual path really does hit the MRT Island 💅
Since all routers need to come to the same conclusion about which routers qualify as LFINs, this specification requires that all routers computing LFINs MUST use an algorithm whose result is identical to that of the Island_Marking_SPF() in Figure 27 🫶
5.9.3. Computing MRT Next Hops for Proxy-Nodes 🦋
Figuring out the MRT next hops for a proxy-node in the degenerate case, where the proxy-node is attached to only one node in the GADAG, is trivial 🥰 All the needed info can be derived from that one proxy-node attachment router. If there are multiple interfaces connecting the proxy-node to that single proxy-node attachment router, some can be assigned to MRT-Red and others to MRT_Blue.
Now, consider the proxy-node P that's attached to two proxy-node attachment routers. The pseudocode for Select_Proxy_Node_NHs(P,S) in Figure 28 specifies how a computing-router S MUST compute the MRT red and blue next hops to reach proxy-node P. The proxy-node attachment router with the lower value of mrt_node_id (as defined in Figure 15) gets assigned to X, and the other one gets assigned to Y. We'll be using the relative order of X, Y, and S in the partial order defined by the GADAG to determine the MRT red and blue next hops to reach P, so we also define A and B as the 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() ✨
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):
// case 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):
// case 2.0
if B.LOWER:
// case 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:
// case 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:
// case 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):
// case 3.0
if A.LOWER:
// case 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:
// case 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:
// case 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):
// case 4.0
if (S is A.localroot or S is B.localroot):
// case 4.05
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 4.1
if B.HIGHER:
// case 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:
// case 4.1.2
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 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:
// case 4.2
if B.HIGHER:
// case 4.2.1
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 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:
// case 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:
// case 4.3
if B.LOWER:
// case 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:
// case 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:
// case 4.3.3
if A.topo_order < B.topo_order:
// case 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:
// case 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 28: Select_Proxy_Node_NHs()
okay so it is so useful to know this up front bestie 💖 the blue next hops to reach proxy-node P that Select_Proxy_Node_NHs() spits out will always be the next hops that reach proxy-node attachment router X 🦋, and the red next hops to reach P will always be the ones that reach attachment router Y ✨. this is different from the red and blue next hops from Compute_MRT_NextHops(), where for example blue next hops to a destination that's ordered with respect to the source always correspond to an INCREASING next hop on the GADAG 🌈. the exact choice of which next hops count as blue to P (which will necessarily go through X on the way to P) does depend on the GADAG, but the relationship is way more complex than it was in Compute_MRT_NextHops() 💀
there are 21 different relative order relationships between A, B, and S that Select_Proxy_Node_NHs() uses to pick red and blue next hops to P 😭 we are not going to write out every single case here, that would be a whole mood 🙈 instead we get a high-level overview of the different cases, and then we walk through a few of them in detail so you can see the reasoning behind each one 🧚
at the highest level, Select_Proxy_Node_NHs() splits into four different cases depending on whether or not A or B is the localroot for S 👑 case 4.0 is where neither A nor B is the localroot for S. case 4.05 covers the situation where S is the localroot for either A or B, and cases 4.1, 4.2, and 4.3 cover when A is ordered lower than S, when A is ordered higher than S, or when A is unordered with respect to S on the GADAG 🍓 then each of those gets split again based on whether B is ordered lower than S, ordered higher than S, or unordered with respect to S. and sometimes we need one more layer of sorting, where we check the topological sort order of A against B 🫶
let's do case 4.1 and all of its sub-cases, because this is where it gets juicy 🔥 in case 4.1, neither A nor B is the localroot for S, S is not the localroot for A or B, and A is ordered lower than S on the GADAG. so here's the vibe: the red path to reach X (as computed in Compute_MRT_NextHops()) follows DECREASING next hops towards A 🌸, while the blue path to reach X follows INCREASING next hops up to the localroot, and then INCREASING next hops to A 🦋
now check out sub-case 4.1.1, where B is ordered higher than S 💜 here the blue path to reach Y follows INCREASING next hops towards B, while the red next hops to reach Y follow DECREASING next hops to the localroot, and then DECREASING next hops to B. so if we want X and Y reached by two disjoint paths, we pick red next hops to X and blue next hops to Y 👑 remember the convention that blue next hops to P are the ones going through X, and red next hops to P are the ones going through Y, so yep, case 4.1.1 gives us exactly what we want ✨ choosing blue to X and red to Y would NOT give disjoint paths, because the two paths would intersect at least at the localroot 💀
next up is sub-case 4.1.2, where B is ordered lower than S 🎀 this time the red path to reach Y follows DECREASING next hops towards B, and the BLUE next hops to reach Y follow INCREASING next hops up to the localroot, and then INCREASING next hops to A 😭 this one is trickier than 4.1.1, because A and B are both on the DECREASING path from S towards the localroot 🙈 we want to use the direct DECREASING (red) path to whichever one is nearer to S on the GADAG. we figure that out by comparing the topological sort order of A and B 🧚 if A.topo_order<B.topo_order, then we use red to Y and blue to X, since 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 💖 otherwise, if A.topo_order>B.topo_order, we use red to X and blue to Y 🦋
now, when A is unordered with respect to B, the result of comparing A.topo_order with B.topo_order could come out either greater than or less than 💅 but honestly it doesn't matter in that case, because either choice (red to Y and blue to X, or red to X and blue to Y) would work just fine 🌈 what is required is that every node in the network gets the same answer when it compares A.topo_order with B.topo_order. and that's guaranteed, because every node runs the same algorithm (Run_Topological_Sort_GADAG()) to compute the topological sort order 🫶
last one in this walkthrough is case 4.1.3, where B is unordered with respect to S 🌸 here the blue path to reach Y follows DECREASING next hops towards the localroot until it hits some node (K) that is ordered less than B, and after that it takes INCREASING next hops to B ✨ the red path to reach Y follows INCREASING next hops towards the localroot until it hits some node (L) that is ordered greater than B, and after that it takes DECREASING next hops to B 🔥
both K and A are reached by DECREASING from S, but we don't actually know whether that DECREASING path hits K or A first 😭 what we do know is that the INCREASING path from S will hit L before it reaches A 👑 so we use the red path to reach Y and the red path to reach X 💖
Okay so the same kind of reasoning works for the other 17 cases in Select_Proxy_Node_NHs() 🧠✨ but ngl, cases 2.3 and 3.3 need extra attention 👀. Their correctness depends on a special property of the GADAGs we build in this algorithm, and not every GADAG has that property 🦋.
Let's zoom into case 2.3 💅. A is the localroot for S, but B isn't, and B is unordered relative to S. The red path to X DECREASES from S down to the localroot A, while the blue path to X INCREASES from S up to A. The blue path to Y DECREASES toward A until it hits some node (K) that's ordered less than B, and then it INCREASES up to B. The red path to Y INCREASES toward A until it reaches some node (L) that's ordered greater than B, and then it DECREASES down to B.
Here's the tea ☕: for an arbitrary GADAG, using only the ordering relationships computed so far, we don't have enough info to pick a pair of paths to X and Y that are guaranteed to be disjoint 😭. In some topologies, A plays the role of K, the first node ordered less than B on the blue path to Y. In other topologies, A plays the role of L, the first node ordered greater than B on the red path to Y. The basic problem is that the ordering relationships alone can't tell these two situations apart 🙃.
The GADAGs built with the algorithm in this document are NOT arbitrary, and that's the saving grace 🌈. They have the extra property that incoming links to a localroot come from only one other node in the same block. This is just a result of how they're constructed 🏗️.
Remember Section 5.8: this extra property means localroot A will never play the role of L on the red path to Y, because L must have at least two incoming links from different nodes in the same block in the GADAG. That's what lets Select_Proxy_Node_NHs() choose the red path to Y and the red path to X as the disjoint MRT paths to reach P 👑💖.
5.9.4. Computing MRT Alternates for Proxy-Nodes ✨
Once we've got the red and blue next hops for a given proxy-node P, we need to know which one to fall back on if something fails 🚨. That's the job of Select_Alternates_Proxy_Node(), shown in the pseudocode in Figure 29 🎀.
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):
// case 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):
// case 2.0
if B.LOWER:
// case 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:
// case 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:
// case 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):
// case 3.0
if A.LOWER:
// case 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:
// case 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:
// case 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):
// case 4.0
if (S is A.localroot or S is B.localroot):
// case 4.05
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 4.1
if B.HIGHER:
// case 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:
// case 4.1.2
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 4.1.3
if (F.LOWER and not F.HIGHER
and F.topo_order > A.topo_order):
// case 4.1.3.1
return 'USE_RED'
else:
// case 4.1.3.2
return 'USE_BLUE'
if A.HIGHER:
// case 4.2
if B.HIGHER:
// case 4.2.1
if A.topo_order < B.topo_order:
// case 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:
// case 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:
// case 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:
// case 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:
// case 4.3
if B.LOWER:
// case 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:
// case 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:
// case 4.3.3
if A.topo_order < B.topo_order:
// case 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:
// case 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 29: Select_Alternates_Proxy_Node() 🦋
Okay so this is where the proxy-node stuff gets spicy 🌶️ Select_Alternates_Proxy_Node(P,F,primary_intf) decides whether it's safe to use the blue path to P (the one through X), the red path to P (the one through Y), or either one, when the primary_intf to node F fails (and possibly node F itself 💀). The plan is to run Select_Alternates(X,F,primary_intf) and Select_Alternates(Y,F,primary_intf) to see which MRT path to X and which MRT path to Y is safe if F goes down. Then the big idea: if a path to X or Y is safe when F fails, and Select_Proxy_Node_NHs() used that exact path to build the red or blue path to P, then the path to P is safe too when F fails 🦋. There's one exception, and we'll get to it. First, a concrete example of how this works in the common case 🎀
The 21 ordering relationships from Select_Proxy_Node_NHs() get repeated in Select_Alternates_Proxy_Node(). We're focusing on case 4.1.1 for the detailed reasoning ✨ In Select_Proxy_Node_NHs(), we figured out that for case 4.1.1, the red next hops to X and the blue next hops to Y let us reach X and Y by disjoint paths, so they become the blue and red next hops to reach P 💅 So if Select_Alternates(X, F, primary_intf) says it's safe to USE_RED to reach X, we can also conclude that the MRT path through X (the blue path to P) is safe to use when F fails. Same deal the other way: if Select_Alternates(Y, F, primary_intf) says it's safe to USE_BLUE to reach Y, then the MRT path through Y (the red path to P) is safe when F fails. If both paths that Select_Proxy_Node_NHs() used for the blue and red paths to P are safe to reach X and Y, then we can use either the red or the blue path to P 🫶
This simple reasoning gets the right answer in most cases. However, extra logic is needed when either A or B (but not both A and B) is unordered with respect to S. This shows up in cases 4.1.3, 4.2.3, 4.3.1, and 4.3.2 😭 Let's look at case 4.1.3 more closely. A is ordered less than S, but B is unordered with respect to S. Back in case 4.1.3, Select_Proxy_Node_NHs() chose the red path to reach Y and the red path to reach X. The red path to reach Y follows the INCREASING next hops toward the localroot until it reaches some node (L) that is ordered greater than B, and after that it takes DECREASING next hops to B. The problem is that the red path to reach P (the one through Y) isn't necessarily the same as the red path to reach Y. That's because the next hop L computes for its red next hop to reach P can be different from the one it computes for its red next hop to reach Y. B is ordered lower than L, so L applies case 4.1.2 of Select_Proxy_Node_NHs() to pick its next hops to reach P. If A.topo_order<B.topo_order (case 4.1.2.1), then L chooses DECREASING next hops directly to B, which matches what L computes in Compute_MRT_NextHops() to reach Y. But if A.topo_order>B.topo_order (case 4.1.2.2), then L chooses INCREASING next hops to reach B, which is different from what L computes in Compute_MRT_NextHops() to reach Y. So using the safety of S's path to Y on failure of F as a stand-in for the safety of the red path to P is not reliable in this case. It's possible to build topologies where the red path to P hits F even though the red path to Y does not 🙈
Good news though: the order relationships we've already computed are enough to figure out which alternate to pick in these four cases 🧚 The basic idea is to always choose the path involving the ordered node, unless that path would hit F. Back to case 4.1.3: 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 sit 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 still need to confirm that it's 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, the path through B that was 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, we look at two sub-cases: either F.topo_order<B.topo_order or F.topo_order>B.topo_order. In the first sub-case, since F.topo_order<B.topo_order and F.topo_order>A.topo_order, it has to be that A.topo_order<B.topo_order. So L chooses DECREASING next hops directly to B (case 4.1.2.1), which can't hit F since F.topo_order<B.topo_order. In the second sub-case, where F.topo_order>B.topo_order, the only way the path involving B can hit F is if it DECREASES from L to B through F, meaning it must be that L>>F>>B. But since S>>F, this would imply S>>B. We know S is unordered with respect to B, so this second sub-case can't happen 💅 That means 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 works for the other three special cases where either A or B is unordered with respect to S.
6. MRT Lowpoint Algorithm: Next-Hop Conformance 🎀
This specification defines the MRT Lowpoint algorithm, which includes building a common GADAG and computing MRT-Red and 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 the available nodes described in Section 5.7 for each of MRT-Red and MRT-Blue, and whose selected next hops are further along in the interval of allowed nodes toward the destination 🦋
For example, the MRT-Blue next hops used when the destination is Y >> X, with X being 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 T. Similarly, the MRT-Red next hops MUST have a topo_order in the interval [R-small.topo_order, X.topo_order] or [Y.topo_order, R-big.topo_order] 🌸
Implementations SHOULD implement the Select_Alternates() function to pick an MRT-FRR alternate 💖
7. Broadcast Interfaces 🌈
When broadcast interfaces are used to connect nodes, the broadcast network MUST be represented as a pseudonode, with each real node connecting to the pseudonode. The interface metric in the direction from a real node to the 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 how 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 Lowpoint 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 so they can 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. 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 candidates for selection as GADAG root. This rule is meant to keep the network-wide choice of GADAG root more stable, by removing the possibility that a change of Designated Router or Designated Intermediate System on a broadcast network could change the GADAG root 🫶
7.1. Computing MRT Next Hops on Broadcast Networks 🌊
Okay so the pseudonode isn't a real node, which means it's not actually involved in forwarding 🫠 A real node on a broadcast network can't just forward traffic to the broadcast network, bestie. It MUST name another real node on that network as the next hop. In a network graph, a broadcast network shows up as a pseudonode, so if a real node finds out its next hop to some destination is a pseudonode, it also has to work out the next-next-hop for that destination. That next-next-hop is a real node attached to the broadcast network. Main character energy, but make it routing 💅
This problem isn't unique to MRT. It shows up in regular SPF computations for IGPs too. Section 16.1.1 of [RFC2328] explains how OSPF handles it. When OSPF runs its shortest-path tree calculation and finds a shorter path to a real destination node, and that path is a single pseudonode hop, the next hop for that destination is taken from the interface IP address in the Router-LSA that corresponds to the link to the real destination node. ✨
IS-IS does it differently. The example pseudocode for Dijkstra's algorithm in Annex C of [ISO10589-Second-Edition] converts any adjacency from a real node to a pseudonode into a set of adjacencies from that real node to the neighbors of the pseudonode. So the computed next hops point all the way to the real node, never to the pseudonode 🦋
We could dodge the whole next-hop-across-a-pseudonode situation in MRT by turning the pseudonode representation into a full mesh of links between the real nodes on the same network. Lowkey tempting, but if we do that conversion before computing the GADAG, we lose track of which links actually belong to one physical interface into the broadcast network. That could give us red and blue next hops that use the same broadcast interface. Then neither the red nor the blue next hop would work as an alternate if that broadcast interface fails 😭
So we do it a different way, one that keeps the property that the red and blue next hops will avoid the broadcast network, if the topology allows it. We run the MRT Lowpoint algorithm treating pseudonodes as equivalent to real nodes in the network graph, with the exceptions noted above. On top of running it from its own point of view, a computing router connected to a pseudonode MUST also run the MRT Lowpoint algorithm from the point of view of each of its pseudonode neighbors. For example, say a computing router S finds that its MRT red next hop to reach a destination D is a pseudonode P. S then looks at its MRT Lowpoint computation from P's point of view to find P's red next hop to reach D, which is interface 1 on node X. Now S knows its real red next hop to reach D is interface 1 on node X, on the broadcast network represented by P, and it can install the matching entry in its FIB 🎀
7.2. Using MRT Next Hops as Alternates in the Event of Failures on Broadcast Networks 🚨
In the last section we covered how to compute MRT next hops when broadcast networks are involved. Now we're talking about how a PLR can use those MRT next hops when a failure involves a broadcast network 🫶
A PLR attached to a broadcast network that's running only OSPF or IS-IS with large Hello intervals has limited ability to quickly detect failures on that network. Honestly, the only failure mode it can catch quickly is the failure of its own physical interface onto the broadcast network. For that case, 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(). That picks an alternate path that avoids the broadcast network.
Here's the catch, though 👀 That alternate path won't necessarily avoid all of the real nodes connected to the broadcast network. We used the pseudonode to represent the broadcast network, and we enforced the node-protecting property of MRT on the pseudonode so it's protected if the broadcast network fails. It is not protecting against failures of the real next-hop nodes on that network. Given that the broadcast interface is the only failure mode the PLR can respond to, this is the best we can hope for 💖
We can do better if the PLR can also quickly detect a lack of connectivity across the broadcast network to a particular IP-layer node. This can be done by running BFD between all pairs of IGP neighbors on the broadcast network. Note that with OSPF, this means establishing BFD sessions between all pairs of neighbors in the 2-WAY state. Once the PLR can quickly detect the failure of a particular next hop across a broadcast network, it can be way more selective about its alternates ✨ For example, when the PLR sees that connectivity to one IP-layer node on a broadcast network has failed, it may still use the broadcast network to reach the other IP-layer nodes that are still reachable. Or, if connectivity has failed to several IP-layer nodes on the same broadcast network, it may decide to treat the entire broadcast network as failed. Picking MRT alternates for a given set of failure conditions is a local decision, since it doesn't need to coordinate with any other nodes 🌸
8. Evaluation of Alternative Methods for Constructing GADAGs 🔬
This document specifies the MRT Lowpoint algorithm. One part of that algorithm is building a common GADAG based on the network topology. The MRT Lowpoint algorithm builds the GADAG using the method described in Section 5.5. That method is all about minimizing the computation needed to build the GADAG. While developing MRT Lowpoint, two alternative GADAG construction methods were also considered. They're described in Appendices B and C. Generally, those other two methods need more computation to build the GADAG. The analysis below was done to find out whether the alternative methods produce shorter MRT alternate paths in real network topologies, and if they do, by how much 📊
Figure 30 compares the results from the three GADAG construction methods on five different service provider network topologies. MRT_LOWPOINT refers to the method specified in Section 5.5, while MRT_SPF and MRT_HYBRID refer to the methods specified in Appendices B and C, respectively. The columns on the right show the distribution of alternate path lengths for each GADAG construction method. Each MRT computation used the same GADAG root, chosen based on centrality 🧚
For three of the topologies analyzed (T201, T206, and T211), using MRT_SPF or MRT_HYBRID doesn't seem to give significantly shorter alternate path lengths than MRT_LOWPOINT. But for two of the topologies (T216 and T219), MRT_SPF gave noticeably shorter alternate path lengths than MRT_LOWPOINT or MRT_HYBRID 🫧
It was decided to use the MRT_LOWPOINT method to build the GADAG in the algorithm specified in this document. The goal was to offer an initial algorithm with lower computational requirements. These results suggest that in the future it may be useful to evaluate, and potentially specify, other MRT Lowpoint algorithm variants that use different GADAG construction methods 🌈
+-------------------------------------------------------------------+
| Topology name | percentage of failure scenarios |
| | protected by an alternate N hops |
| GADAG construction | longer than the primary path |
| method +------------------------------------+
| | | | | | | | | | no |
| | | | | | |10 |12 |14 | alt|
| |0-1|2-3|4-5|6-7|8-9|-11|-13|-15| <16|
+------------------------------+---+---+---+---+---+---+---+---+----+
| T201(avg primary hops=3.5) | | | | | | | | | |
| MRT_HYBRID | 33| 26| 23| 6| 3| | | | |
| MRT_SPF | 33| 36| 23| 6| 3| | | | |
| MRT_LOWPOINT | 33| 36| 23| 6| 3| | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+
| T206(avg primary hops=3.7) | | | | | | | | | |
| MRT_HYBRID | 50| 35| 13| 2| | | | | |
| MRT_SPF | 50| 35| 13| 2| | | | | |
| MRT_LOWPOINT | 55| 32| 13| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+
| T211(avg primary hops=3.3) | | | | | | | | | |
| MRT_HYBRID | 86| 14| | | | | | | |
| MRT_SPF | 86| 14| | | | | | | |
| MRT_LOWPOINT | 85| 15| 1| | | | | | |
+------------------------------+---+---+---+---+---+---+---+---+----+
| T216(avg primary hops=5.2) | | | | | | | | | |
| MRT_HYBRID | 23| 22| 18| 13| 10| 7| 4| 2| 2|
| MRT_SPF | 35| 32| 19| 9| 3| 1| | | |
| MRT_LOWPOINT | 28| 25| 18| 11| 7| 6| 3| 2| 1|
+------------------------------+---+---+---+---+---+---+---+---+----+
| T219(avg primary hops=7.7) | | | | | | | | | |
| MRT_HYBRID | 20| 16| 13| 10| 7| 5| 5| 5| 3|
| MRT_SPF | 31| 23| 19| 12| 7| 4| 2| 1| |
| MRT_LOWPOINT | 19| 14| 15| 12| 10| 8| 7| 6| 10|
+------------------------------+---+---+---+---+---+---+---+---+----+
Figure 30: The Length of Alternate Paths for Various GADAG
Construction Methods9. Operational Considerations 🛠️
This section covers operational considerations for the MRT Lowpoint algorithm and other potential MRT algorithm variants. For a discussion of operational considerations related to MRT-FRR in general, see the "Operational Considerations" section of [RFC7812] 💜
9.1. GADAG Root Selection ✨
Okay bestie, the Default MRT Profile looks at the GADAG Root Selection Priority that every router advertises and uses that as its main way to pick the GADAG root 👑. It is RECOMMENDED that an operator pick a group of routers as good choices for GADAG root by giving them lower (more preferred) numerical values in their GADAG Root Selection Priority 💅. How to decide which routers make the cut is coming up below 🎀.
Okay so, the research shows that a router's centrality (how central it sits in the network) can seriously change how long the alternate paths come out 🌸. That's why it is RECOMMENDED that off-line analysis looking at router centrality gets used to help figure out how good a pick each router is for GADAG root 🧠.
Now, if the router currently selected as GADAG root becomes unreachable in the IGP topology, a new GADAG root gets selected 💀. Changing the GADAG root can reshape the whole GADAG, as well as the paths of the red and MRT-Blue trees built from it 🦋. To keep the red and MRT-Blue forwarding entries from changing too much when that happens, it is RECOMMENDED that operators prioritize, for selection as GADAG root, those routers that are expected to stay part of the IGP topology consistently 🫶.
9.2. Destination-Rooted GADAGs
The MRT Lowpoint algorithm builds a single GADAG rooted at one node, the one selected as GADAG root 🧚. It's also possible to build a different GADAG for each destination, with that GADAG rooted at the destination itself 🌈. A router can then compute the MRT-Red and MRT-Blue next hops for that destination based on the GADAG rooted there ✨.
Ngl, building a different GADAG for every destination is way more computationally expensive 😭, but it may give somewhat shorter alternate paths 🍓. Using destination-rooted GADAGs would need a brand new MRT profile with a new MRT algorithm specification, because every router in the MRT Island would have to use destination-rooted GADAGs 👑.
10. Security Considerations 🔒
Honestly, no new security drama here 💅. The algorithm described in this document doesn't introduce new security concerns beyond the ones already covered in the document describing the MRT FRR architecture [RFC7812] 💜.
11. References
11.1. Normative References
- [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997,
http://www.rfc-editor.org/info/rfc2119. - [RFC7812] Atlas, A., Bowers, C., and G. Enyedi, "An Architecture for IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)", RFC 7812, DOI 10.17487/RFC7812, June 2016,
http://www.rfc-editor.org/info/rfc7812.
11.2. Informative References
- [EnyediThesis] Enyedi, G., "Novel Algorithms for IP Fast Reroute", Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics Ph.D. Thesis, February 2011,
https://repozitorium.omikk.bme.hu/bitstream/handle/10890/1040/ertekezes.pdf. - [IEEE8021Qca] IEEE, "IEEE Standard for Local and metropolitan area networks - Bridges and Bridged Networks - Amendment 24: Path Control and Reservation", IEEE 802.1Qca-2015, DOI 10.1109/IEEESTD.2016.7434544, 2016,
https://standards.ieee.org/findstds/standard/802.1Qca-2015.html. - [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, November 2002.
- [Kahn_1962_topo_sort] Kahn, A., "Topological sorting of large networks", Communications of the ACM, Volume 5, Issue 11 DOI 10.1145/368996.369025, November 1962,
http://dl.acm.org/citation.cfm?doid=368996.369025. - [MRTLinear] Enyedi, G., Retvari, G., and A. Csaszar, "On Finding Maximally Redundant Trees in Strictly Linear Time", IEEE Symposium on Computers and Communications (ISCC), 2009,
http://opti.tmit.bme.hu/~enyedi/ipfrr/distMaxRedTree.pdf. - [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/RFC2328, April 1998,
http://www.rfc-editor.org/info/rfc2328.
Appendix A. Python Implementation of MRT Lowpoint Algorithm 🐍
Below is the Python code implementing the MRT Lowpoint algorithm from this document 🌟. It's also posted on GitHub at https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/blob/python_code_RFC7811/src/mrt_lowpoint_draft_text.py 🫶.
The Python is believed to correctly match the pseudocode, but if the two ever disagree, the pseudocode is the normative one, so it wins 👑.
# This program has been tested to run on Python 2.6 and 2.7
# (specifically Python 2.6.6 and 2.7.8 were tested).
# The program has known incompatibilities with Python 3.X.
# When executed, this program will generate a text file describing
# an example topology. It then reads that text file back in as input
# to create the example topology, and runs the MRT Lowpoint algorithm.
# This was done to simplify the inclusion of the program as a single
# text file that can be extracted from the RFC.
# The output of the program is four text files containing a description
# of the GADAG, the blue and MRT-Reds for all destinations, and the
# MRT alternates for all failures.
import random
import os.path
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 = {}
class Node:
def __init__(self):
self.node_id = None
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 Interface:
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 Bundle:
def __init__(self):
self.UNDIRECTED = True
self.OUTGOING = False
self.INCOMING = False
class Alternate:
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 Proxy_Node_Attachment_Router:
def __init__(self):
self.prefix = None
self.node = None
self.named_proxy_cost = None
self.min_lfin = None
self.nh_intf_list = []
class Named_Proxy_Node:
def __init__(self):
self.node_id = None #this is the prefix_id
self.node_prefix_cost_list = []
self.lfin_list = []
self.pnar1 = None
self.pnar2 = None
self.pnar_X = None
self.pnar_Y = None
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 Interface_Compare(intf_a, intf_b):
if intf_a.metric < intf_b.metric:
return -1
if intf_b.metric < intf_a.metric:
return 1
if intf_a.remote_node.node_id < intf_b.remote_node.node_id:
return -1
if intf_b.remote_node.node_id < intf_a.remote_node.node_id:
return 1
return 0
def Sort_Interfaces(topo):
for node in topo.island_node_list:
node.island_intf_list.sort(Interface_Compare)
def Reset_Computed_Node_and_Intf_Values(topo):
topo.init_new_computing_router()
for node in topo.node_list:
node.init_new_computing_router()
for intf in node.intf_list:
intf.init_new_computing_router()
# This function takes a file with links represented by 2-digit
# numbers in the format:
# 01,05,10
# 05,02,30
# 02,01,15
# which represents a triangle topology with nodes 01, 05, and 02
# and symmetric metrics of 10, 30, and 15.
# Inclusion of a fourth column makes the metrics for the link
# asymmetric. An entry of:
# 02,07,10,15
# creates a link from node 02 to 07 with metrics 10 and 15.okay so this part is where the topology actually gets built from the file, and the lowpoint and block stuff starts to get spicy 💅🦋
def Create_Topology_From_File(filename):
topo = Topology()
node_id_set= set()
cols_list = []
# on first pass just create nodes
with open(filename + '.csv') as topo_file:
for line in topo_file:
line = line.rstrip('\r\n')
cols=line.split(',')
cols_list.append(cols)
nodea_node_id = int(cols[0])
nodeb_node_id = int(cols[1])
if (nodea_node_id > 999 or nodeb_node_id > 999):
print("node_id must be between 0 and 999.")
print("exiting.")
exit()
node_id_set.add(nodea_node_id)
node_id_set.add(nodeb_node_id)
for node_id in node_id_set:
node = Node()
node.node_id = node_id
topo.node_list.append(node)
topo.node_dict[node_id] = node
# on second pass create interfaces
for cols in cols_list:
nodea_node_id = int(cols[0])
nodeb_node_id = int(cols[1])
metric = int(cols[2])
reverse_metric = int(cols[2])
if len(cols) > 3:
reverse_metric=int(cols[3])
nodea = topo.node_dict[nodea_node_id]
nodeb = topo.node_dict[nodeb_node_id]
nodea_intf = Interface()
nodea_intf.metric = metric
nodea_intf.area = 0
nodeb_intf = Interface()
nodeb_intf.metric = reverse_metric
nodeb_intf.area = 0
nodea_intf.remote_intf = nodeb_intf
nodeb_intf.remote_intf = nodea_intf
nodea_intf.remote_node = nodeb
nodeb_intf.remote_node = nodea
nodea_intf.local_node = nodea
nodeb_intf.local_node = nodeb
nodea_intf.link_data = len(nodea.intf_list)
nodeb_intf.link_data = len(nodeb.intf_list)
nodea.intf_list.append(nodea_intf)
nodeb.intf_list.append(nodeb_intf)
return topo
def MRT_Island_Identification(topo, computing_rtr, profile_id, area):
if profile_id in computing_rtr.profile_id_list:
computing_rtr.IN_MRT_ISLAND = True
explore_list = [computing_rtr]
else:
return
while explore_list != []:
next_rtr = explore_list.pop()
for intf in next_rtr.intf_list:
if ( (not intf.IN_MRT_ISLAND)
and (not intf.MRT_INELIGIBLE)
and (not intf.remote_intf.MRT_INELIGIBLE)
and (not intf.IGP_EXCLUDED) and intf.area == area
and (profile_id in intf.remote_node.profile_id_list)):
intf.IN_MRT_ISLAND = True
intf.remote_intf.IN_MRT_ISLAND = True
if (not intf.remote_node.IN_MRT_ISLAND):
intf.remote_INTF.IN_MRT_ISLAND = True
explore_list.append(intf.remote_node)
def Compute_Island_Node_List_For_Test_GR(topo, test_gr):
Reset_Computed_Node_and_Intf_Values(topo)
topo.test_gr = topo.node_dict[test_gr]
MRT_Island_Identification(topo, topo.test_gr, 0, 0)
for node in topo.node_list:
if node.IN_MRT_ISLAND:
topo.island_node_list_for_test_gr.append(node)
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)
global_dfs_number = None
def Lowpoint_Visit(x, parent, intf_p_to_x):
global global_dfs_number
x.dfs_number = global_dfs_number
x.lowpoint_number = x.dfs_number
global_dfs_number += 1
x.dfs_parent = parent
if intf_p_to_x == None:
x.dfs_parent_intf = None
else:
x.dfs_parent_intf = intf_p_to_x.remote_intf
x.lowpoint_parent = None
if parent != None:
parent.dfs_child_list.append(x)
for intf in x.island_intf_list:
if intf.remote_node.dfs_number == None:
Lowpoint_Visit(intf.remote_node, x, intf)
if intf.remote_node.lowpoint_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.lowpoint_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
else:
if intf.remote_node is not parent:
if intf.remote_node.dfs_number < x.lowpoint_number:
x.lowpoint_number = intf.remote_node.dfs_number
x.lowpoint_parent = intf.remote_node
x.lowpoint_parent_intf = intf
def Run_Lowpoint(topo):
global global_dfs_number
global_dfs_number = 0
Lowpoint_Visit(topo.gadag_root, None, None)
max_block_id = None
def Assign_Block_ID(x, cur_block_id):
global max_block_id
x.block_id = cur_block_id
for c in x.dfs_child_list:
if (c.localroot is x):
max_block_id += 1
Assign_Block_ID(c, max_block_id)
else:
Assign_Block_ID(c, cur_block_id)
def Run_Assign_Block_ID(topo):
global max_block_id
max_block_id = 0
Assign_Block_ID(topo.gadag_root, max_block_id)
def Construct_Ear(x, stack, intf, ear_type):
ear_list = []
cur_intf = intf
not_done = True
while not_done:
cur_intf.UNDIRECTED = False
cur_intf.OUTGOING = True
cur_intf.remote_intf.UNDIRECTED = False
cur_intf.remote_intf.INCOMING = True
if cur_intf.remote_node.IN_GADAG == False:
cur_intf.remote_node.IN_GADAG = True
ear_list.append(cur_intf.remote_node)
if ear_type == 'CHILD':
cur_intf = cur_intf.remote_node.lowpoint_parent_intf
else:
assert ear_type == 'NEIGHBOR'
cur_intf = cur_intf.remote_node.dfs_parent_intf
else:
not_done = False
if ear_type == 'CHILD' and cur_intf.remote_node is x:
# x is a cut-vertex and the local root for the block
# in which the ear is computed
x.IS_CUT_VERTEX = True
localroot = x
else:
# inherit local root from the end of the ear
localroot = cur_intf.remote_node.localroot
while ear_list != []:
y = ear_list.pop()
y.localroot = localroot
stack.append(y)
def Construct_GADAG_via_Lowpoint(topo):
gadag_root = topo.gadag_root
gadag_root.IN_GADAG = True
gadag_root.localroot = None
stack = []
stack.append(gadag_root)
while stack != []:
x = stack.pop()
for intf in x.island_intf_list:
if ( intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is x ):
Construct_Ear(x, stack, intf, 'CHILD' )
for intf in x.island_intf_list:
if (intf.remote_node.IN_GADAG == False
and intf.remote_node.dfs_parent is not x):
Construct_Ear(x, stack, intf, 'NEIGHBOR')
def Assign_Remaining_Lowpoint_Parents(topo):
for node in topo.island_node_list:
if ( node is not topo.gadag_root
and node.lowpoint_parent == None ):
node.lowpoint_parent = node.dfs_parent
node.lowpoint_parent_intf = node.dfs_parent_intf
node.lowpoint_number = node.dfs_parent.dfs_number
def Add_Undirected_Block_Root_Links(topo):
for node in topo.island_node_list:
if node.IS_CUT_VERTEX or node is topo.gadag_root:
for intf in node.island_intf_list:
if ( intf.remote_node.localroot is not node
or intf.PROCESSED ):
continue
bundle_list = []
bundle = Bundle()
for intf2 in node.island_intf_list:
if intf2.remote_node is intf.remote_node:
bundle_list.append(intf2)
if not intf2.UNDIRECTED:
bundle.UNDIRECTED = False
if intf2.INCOMING:
bundle.INCOMING = True
if intf2.OUTGOING:
bundle.OUTGOING = True
if bundle.UNDIRECTED:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
else:
if (bundle.OUTGOING and bundle.INCOMING):
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.INCOMING = True
intf3.remote_intf.INCOMING = True
intf3.remote_intf.OUTGOING = True
elif bundle.OUTGOING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.OUTGOING = True
intf3.remote_intf.INCOMING = True
elif bundle.INCOMING:
for intf3 in bundle_list:
intf3.UNDIRECTED = False
intf3.remote_intf.UNDIRECTED = False
intf3.PROCESSED = True
intf3.remote_intf.PROCESSED = True
intf3.INCOMING = True
intf3.remote_intf.OUTGOING = True
def Modify_Block_Root_Incoming_Links(topo):
for node in topo.island_node_list:
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
for intf in node.island_intf_list:
if intf.remote_node.localroot is node:
if intf.INCOMING:
intf.INCOMING = False
intf.INCOMING_STORED = True
intf.remote_intf.OUTGOING = False
intf.remote_intf.OUTGOING_STORED = True
def Revert_Block_Root_Incoming_Links(topo):
for node in topo.island_node_list:
if ( node.IS_CUT_VERTEX == True or node is topo.gadag_root ):
for intf in node.island_intf_list:
if intf.remote_node.localroot is node:
if intf.INCOMING_STORED:
intf.INCOMING = True
intf.remote_intf.OUTGOING = True
intf.INCOMING_STORED = False
intf.remote_intf.OUTGOING_STORED = False
def Run_Topological_Sort_GADAG(topo):
Modify_Block_Root_Incoming_Links(topo)
for node in topo.island_node_list:
node.unvisited = 0
for intf in node.island_intf_list:
if (intf.INCOMING == True):
node.unvisited += 1
working_list = []
topo_order_list = []
working_list.append(topo.gadag_root)
while working_list != []:
y = working_list.pop(0)
topo_order_list.append(y)
for intf in y.island_intf_list:
if ( intf.OUTGOING == True):
intf.remote_node.unvisited -= 1
if intf.remote_node.unvisited == 0:
working_list.append(intf.remote_node)
next_topo_order = 1
while topo_order_list != []:
y = topo_order_list.pop(0)
y.topo_order = next_topo_order
next_topo_order += 1
Revert_Block_Root_Incoming_Links(topo)Okay bestie, the undirected links get sorted by topo order here, and then we start the SPF helpers 🦋✨
def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):
for node in topo.island_node_list:
for intf in node.island_intf_list:
if intf.UNDIRECTED:
if node.topo_order < intf.remote_node.topo_order:
intf.OUTGOING = True
intf.UNDIRECTED = False
intf.remote_intf.INCOMING = True
intf.remote_intf.UNDIRECTED = False
else:
intf.INCOMING = True
intf.UNDIRECTED = False
intf.remote_intf.OUTGOING = True
intf.remote_intf.UNDIRECTED = False
def Initialize_Temporary_Interface_Flags(topo):
for node in topo.island_node_list:
for intf in node.island_intf_list:
intf.PROCESSED = False
intf.INCOMING_STORED = False
intf.OUTGOING_STORED = False
def Add_Undirected_Links(topo):
Initialize_Temporary_Interface_Flags(topo)
Add_Undirected_Block_Root_Links(topo)
Run_Topological_Sort_GADAG(topo)
Set_Other_Undirected_Links_Based_On_Topo_Order(topo)
def In_Common_Block(x,y):
if ( (x.block_id == y.block_id)
or ( x is y.localroot) or (y is x.localroot) ):
return True
return False
def Copy_List_Items(target_list, source_list):
del target_list[:] # Python idiom to remove all elements of a list
for element in source_list:
target_list.append(element)
def Add_Item_To_List_If_New(target_list, item):
if item not in target_list:
target_list.append(item)
def Store_Results(y, direction):
if direction == 'INCREASING':
y.HIGHER = True
Copy_List_Items(y.blue_next_hops, y.next_hops)
if direction == 'DECREASING':
y.LOWER = True
Copy_List_Items(y.red_next_hops, y.next_hops)
if direction == 'NORMAL_SPF':
y.primary_spf_metric = y.spf_metric
Copy_List_Items(y.primary_next_hops, y.next_hops)
if direction == 'MRT_ISLAND_SPF':
Copy_List_Items(y.mrt_island_next_hops, y.next_hops)
if direction == 'COLLAPSED_SPF':
y.collapsed_metric = y.spf_metric
Copy_List_Items(y.collapsed_next_hops, y.next_hops)Now for the big SPF one, which is where the heap magic happens 🔥💅 Heapq can hold duplicates, so we use spf_visited to make sure each node only counts as min_node the first time it pops out. Main character energy 👑
# Note that the Python heapq function allows for duplicate items,
# so we use the 'spf_visited' property to only consider a node
# as min_node the first time it gets removed from the heap.
def SPF_No_Traverse_Block_Root(topo, spf_root, block_root, direction):
spf_heap = []
for y in topo.island_node_list:
y.spf_metric = 2147483647 # 2^31-1
y.next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric, spf_root.node_id, spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, direction)
if ( (min_node is spf_root) or (min_node is not block_root) ):
for intf in min_node.island_intf_list:
if ( ( (direction == 'INCREASING' and intf.OUTGOING )
or (direction == 'DECREASING' and intf.INCOMING ) )
and In_Common_Block(spf_root, intf.remote_node) ) :
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)
def Normal_SPF(topo, spf_root):
spf_heap = []
for y in topo.node_list:
y.spf_metric = 2147483647 # 2^31-1 as max metric
y.next_hops = []
y.primary_spf_metric = 2147483647
y.primary_next_hops = []
y.spf_visited = False
spf_root.spf_metric = 0
heapq.heappush(spf_heap,
(spf_root.spf_metric,spf_root.node_id,spf_root) )
while spf_heap != []:
#extract third element of tuple popped from heap
min_node = heapq.heappop(spf_heap)[2]
if min_node.spf_visited:
continue
min_node.spf_visited = True
Store_Results(min_node, 'NORMAL_SPF')
for intf in min_node.intf_list:
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric:
intf.remote_node.spf_metric = path_metric
if min_node is spf_root:
intf.remote_node.next_hops = [intf]
else:
Copy_List_Items(intf.remote_node.next_hops,
min_node.next_hops)
heapq.heappush(spf_heap,
( intf.remote_node.spf_metric,
intf.remote_node.node_id,
intf.remote_node ) )
elif path_metric == intf.remote_node.spf_metric:
if min_node is spf_root:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,intf)
else:
for nh_intf in min_node.next_hops:
Add_Item_To_List_If_New(
intf.remote_node.next_hops,nh_intf)Next up is Set_Edge and the per-source MRT next-hop computation, where the block root's next hops get inherited. Pure vibes ✨🫶
def Set_Edge(y):
if (y.blue_next_hops == [] and y.red_next_hops == []):
Set_Edge(y.localroot)
Copy_List_Items(y.blue_next_hops,y.localroot.blue_next_hops)
Copy_List_Items(y.red_next_hops ,y.localroot.red_next_hops)
y.order_proxy = y.localroot.order_proxy
def Compute_MRT_NH_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
y.HIGHER = False
y.LOWER = False
y.red_next_hops = []
y.blue_next_hops = []
y.order_proxy = y
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'INCREASING')
SPF_No_Traverse_Block_Root(topo, x, x.localroot, 'DECREASING')
for y in topo.island_node_list:
if ( y is not x and (y.block_id == x.block_id) ):
assert (not ( y is x.localroot or x is y.localroot) )
assert(not (y.HIGHER and y.LOWER) )
if y.HIGHER == True:
Copy_List_Items(y.red_next_hops,
x.localroot.red_next_hops)
elif y.LOWER == True:
Copy_List_Items(y.blue_next_hops,
x.localroot.blue_next_hops)
else:
Copy_List_Items(y.blue_next_hops,
x.localroot.red_next_hops)
Copy_List_Items(y.red_next_hops,
x.localroot.blue_next_hops)
# Inherit x's MRT next hops to reach the GADAG root
# from x's MRT next hops to reach its local root,
# but first check if x is the gadag_root (in which case
# x does not have a local root) or if x's local root
# is the gadag root (in which case we already have the
# x's MRT next hops to reach the gadag root)
if x is not topo.gadag_root and x.localroot is not topo.gadag_root:
Copy_List_Items(topo.gadag_root.blue_next_hops,
x.localroot.blue_next_hops)
Copy_List_Items(topo.gadag_root.red_next_hops,
x.localroot.red_next_hops)
topo.gadag_root.order_proxy = x.localroot
# Inherit next hops and order_proxies to other blocks
for y in topo.island_node_list:
if (y is not topo.gadag_root and y is not x ):
Set_Edge(y)Last stretch for this part: the storage helpers that copy the computed next hops and alts into each source's dictionaries, for island destinations and for named proxy nodes. Almost there, you're doing amazing 🌈💖
def Store_MRT_Nexthops_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
if y is x:
continue
x.blue_next_hops_dict[y.node_id] = []
x.red_next_hops_dict[y.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[y.node_id],
y.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[y.node_id],
y.red_next_hops)
def Store_Primary_and_Alts_For_One_Src_To_Island_Dests(topo,x):
for y in topo.island_node_list:
x.pnh_dict[y.node_id] = []
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
x.alt_dict[y.node_id] = []
Copy_List_Items(x.alt_dict[y.node_id], y.alt_list)
def Store_Primary_NHs_For_One_Source_To_Nodes(topo,x):
for y in topo.node_list:
x.pnh_dict[y.node_id] = []
Copy_List_Items(x.pnh_dict[y.node_id], y.primary_next_hops)
def Store_MRT_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.blue_next_hops_dict[P.node_id] = []
x.red_next_hops_dict[P.node_id] = []
Copy_List_Items(x.blue_next_hops_dict[P.node_id],
P.blue_next_hops)
Copy_List_Items(x.red_next_hops_dict[P.node_id],
P.red_next_hops)
def Store_Alts_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.alt_dict[P.node_id] = []
Copy_List_Items(x.alt_dict[P.node_id],
P.alt_list)
def Store_Primary_NHs_For_One_Src_To_Named_Proxy_Nodes(topo,x):
for prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
x.pnh_dict[P.node_id] = []
Copy_List_Items(x.pnh_dict[P.node_id],
P.primary_next_hops)okay bestie, the next batch is all code, so it's giving pure logic 💻✨
def Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order):
if D_higher and D_lower:
if F.HIGHER and F.LOWER:
if F.topo_order > D_topo_order:
return 'USE_BLUE'
else:
return 'USE_RED'
if F.HIGHER:
return 'USE_RED'
if F.LOWER:
return 'USE_BLUE'
assert(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 F and D are in different blocks
return 'USE_RED_OR_BLUE'
if primary_intf.OUTGOING:
return 'USE_BLUE'
if primary_intf.INCOMING:
return 'USE_RED'
#This can occur when primary_intf is MRT_INELIGIBLE.
#This appears to be a case where the special
#construction of the GADAG allows us to choose red,
#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'Next up, the wrapper that picks the inputs for that choice, plus the little helper that checks neighbours 🫶
def Select_Alternates(D, F, primary_intf):
S = primary_intf.local_node
if not In_Common_Block(F, S):
return 'PRIM_NH_IN_DIFFERENT_BLOCK'
if (D is F) or (D.order_proxy is F):
return 'PRIM_NH_IS_D_OR_OP_FOR_D'
D_lower = D.order_proxy.LOWER
D_higher = D.order_proxy.HIGHER
D_topo_order = D.order_proxy.topo_order
return Select_Alternates_Internal(D, F, primary_intf,
D_lower, D_higher, D_topo_order)
def Is_Remote_Node_In_NH_List(node, intf_list):
for intf in intf_list:
if node is intf.remote_node:
return True
return FalseNow the big one that actually fills in the alternates for each island destination 👑
def Select_Alts_For_One_Src_To_Island_Dests(topo,x):
Normal_SPF(topo, x)
for D in topo.island_node_list:
D.alt_list = []
if D is x:
continue
for failed_intf in D.primary_next_hops:
alt = Alternate()
alt.failed_intf = failed_intf
cand_alt_list = []
F = failed_intf.remote_node
#We need to test if F is in the island, as opposed
#to just testing if failed_intf is in island_intf_list,
#because failed_intf could be marked as MRT_INELIGIBLE.
if F in topo.island_node_list:
alt.info = Select_Alternates(D, F, failed_intf)
else:
#The primary next hop is not in the MRT Island.
#Either red or blue will avoid the primary next hop,
#because the primary next hop is not even in the
#GADAG.
alt.info = 'USE_RED_OR_BLUE'
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, 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)
# Is_Remote_Node_In_NH_List() is used, as opposed
# to just checking if failed_intf is in D.red_next_hops,
# because failed_intf could be marked as MRT_INELIGIBLE.
elif Is_Remote_Node_In_NH_List(F, D.red_next_hops):
Copy_List_Items(alt.nh_list, D.blue_next_hops)
alt.fec = 'BLUE'
alt.prot = 'LINK_PROTECTION'
elif Is_Remote_Node_In_NH_List(F, D.blue_next_hops):
Copy_List_Items(alt.nh_list, D.red_next_hops)
alt.fec = 'RED'
alt.prot = 'LINK_PROTECTION'
else:
alt.fec = random.choice(['RED','BLUE'])
alt.prot = 'LINK_PROTECTION'
D.alt_list.append(alt)Last stretch: the helpers that dump GADAG and MRT results to CSV files and the GADAG root priority bits 📁🍓
def Write_GADAG_To_File(topo, file_prefix):
gadag_edge_list = []
for node in topo.node_list:
for intf in node.intf_list:
if intf.SIMULATION_OUTGOING:
local_node = "%04d" % (intf.local_node.node_id)
remote_node = "%04d" % (intf.remote_node.node_id)
intf_data = "%03d" % (intf.link_data)
edge_string=(local_node+','+remote_node+','+
intf_data+'\n')
gadag_edge_list.append(edge_string)
gadag_edge_list.sort();
filename = file_prefix + '_gadag.csv'
with open(filename, 'w') as gadag_file:
gadag_file.write('local_node,'\
'remote_node,local_intf_link_data\n')
for edge_string in gadag_edge_list:
gadag_file.write(edge_string);
def Write_MRTs_For_All_Dests_To_File(topo, color, file_prefix):
edge_list = []
for node in topo.island_node_list_for_test_gr:
if color == 'blue':
node_next_hops_dict = node.blue_next_hops_dict
elif color == 'red':
node_next_hops_dict = node.red_next_hops_dict
for dest_node_id in node_next_hops_dict:
for intf in node_next_hops_dict[dest_node_id]:
gadag_root = "%04d" % (topo.gadag_root.node_id)
dest_node = "%04d" % (dest_node_id)
local_node = "%04d" % (intf.local_node.node_id)
remote_node = "%04d" % (intf.remote_node.node_id)
intf_data = "%03d" % (intf.link_data)
edge_string=(gadag_root+','+dest_node+','+local_node+
','+remote_node+','+intf_data+'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_' + color + '_to_all.csv'
with open(filename, 'w') as mrt_file:
mrt_file.write('gadag_root,dest,'\
'local_node,remote_node,link_data\n')
for edge_string in edge_list:
mrt_file.write(edge_string);
def Write_Both_MRTs_For_All_Dests_To_File(topo, file_prefix):
Write_MRTs_For_All_Dests_To_File(topo, 'blue', file_prefix)
Write_MRTs_For_All_Dests_To_File(topo, 'red', file_prefix)
def Write_Alternates_For_All_Dests_To_File(topo, file_prefix):
edge_list = []
for x in topo.island_node_list_for_test_gr:
for dest_node_id in x.alt_dict:
alt_list = x.alt_dict[dest_node_id]
for alt in alt_list:
for alt_intf in alt.nh_list:
gadag_root = "%04d" % (topo.gadag_root.node_id)
dest_node = "%04d" % (dest_node_id)
prim_local_node = \
"%04d" % (alt.failed_intf.local_node.node_id)
prim_remote_node = \
"%04d" % (alt.failed_intf.remote_node.node_id)
prim_intf_data = \
"%03d" % (alt.failed_intf.link_data)
if alt_intf == None:
alt_local_node = "None"
alt_remote_node = "None"
alt_intf_data = "None"
else:
alt_local_node = \
"%04d" % (alt_intf.local_node.node_id)
alt_remote_node = \
"%04d" % (alt_intf.remote_node.node_id)
alt_intf_data = \
"%03d" % (alt_intf.link_data)
edge_string = (gadag_root+','+dest_node+','+
prim_local_node+','+prim_remote_node+','+
prim_intf_data+','+alt_local_node+','+
alt_remote_node+','+alt_intf_data+','+
alt.fec +'\n')
edge_list.append(edge_string)
edge_list.sort()
filename = file_prefix + '_alts_to_all.csv'
with open(filename, 'w') as alt_file:
alt_file.write('gadag_root,dest,'\
'prim_nh.local_node,prim_nh.remote_node,'\
'prim_nh.link_data,alt_nh.local_node,'\
'alt_nh.remote_node,alt_nh.link_data,'\
'alt_nh.fec\n')
for edge_string in edge_list:
alt_file.write(edge_string);
def Raise_GADAG_Root_Selection_Priority(topo,node_id):
node = topo.node_dict[node_id]
node.GR_sel_priority = 255
def Lower_GADAG_Root_Selection_Priority(topo,node_id):
node = topo.node_dict[node_id]
node.GR_sel_priority = 128
def GADAG_Root_Compare(node_a, node_b):
if (node_a.GR_sel_priority > node_b.GR_sel_priority):
return 1
elif (node_a.GR_sel_priority < node_b.GR_sel_priority):
return -1
else:
if node_a.node_id > node_b.node_id:
return 1
elif node_a.node_id < node_b.node_id:
return -1okay bestie, the GADAG root picking and the prefix/profile loading code is next 💅✨
def Set_GADAG_Root(topo,computing_router):
gadag_root_list = []
for node in topo.island_node_list:
gadag_root_list.append(node)
gadag_root_list.sort(GADAG_Root_Compare)
topo.gadag_root = gadag_root_list.pop()
def Add_Prefix_Advertisements_From_File(topo, filename):
prefix_filename = filename + '.prefix'
cols_list = []
if not os.path.exists(prefix_filename):
return
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 Add_Prefixes_for_Non_Island_Nodes(topo):
for node in topo.node_list:
if node.IN_MRT_ISLAND:
continue
prefix_id = node.node_id + 1000
node.prefix_cost_dict[prefix_id] = 0
def Add_Profile_IDs_from_File(topo, filename):
profile_filename = filename + '.profile'
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 Island_Marking_SPF(topo,spf_root):
spf_root.isl_marking_spf_dict = {}
for y in topo.node_list:
y.spf_metric = 2147483647 # 2^31-1 as max metric
y.PATH_HITS_ISLAND = False
y.next_hops = []
y.spf_visited = False
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:
if (intf.remote_node.PATH_HITS_ISLAND
or min_node.PATH_HITS_ISLAND):
intf.remote_node.PATH_HITS_ISLAND = True
def Create_Basic_Named_Proxy_Nodes(topo):
for node in topo.node_list:
for prefix in node.prefix_cost_dict:
prefix_cost = node.prefix_cost_dict[prefix]
if prefix in topo.named_proxy_dict:
P = topo.named_proxy_dict[prefix]
P.node_prefix_cost_list.append((node,prefix_cost))
else:
P = Named_Proxy_Node()
topo.named_proxy_dict[prefix] = P
P.node_id = prefix
P.node_prefix_cost_list = [(node,prefix_cost)]
def Compute_Loop_Free_Island_Neighbors_For_Each_Prefix(topo):
topo.island_nbr_set = set()
topo.island_border_set = set()
for node in topo.node_list:
if node.IN_MRT_ISLAND:
continue
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)
for island_nbr in topo.island_nbr_set:
Island_Marking_SPF(topo,island_nbr)
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:
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)okay bestie, this bit is pure code and it's giving precision 💅 Here's how the proxy next hops get picked 🦋
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] = Truethat's the whole chunk, no prose this time, just the vibes of pure logic 🌸
okay bestie, the decision tree gets chaotic here 💅 every branch is literally checking which proxy node the primary next hop lines up with 🦋
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)that's the whole vibe for this chunk 🌸 more coming, stay tuned ✨
okay bestie, this part is pure code, so no vibes to add here. Every character stays exactly as written 💅🫶
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()Appendix B. Constructing a GADAG Using SPFs ✨
okay bestie, the big idea behind this method for building a GADAG is to use slightly modified SPF computations to find ears 🦋 In every block, we first run an SPF to find a cycle from the local root. Then SPF computations in that block keep finding ears until there are no more interfaces left to explore 💅 The result we actually use is the path of interfaces you get by following the previous hops from the minimized IN_GADAG node back to the SPF root 🧚
so first things first, all cut-vertices have to be identified and localroots assigned, as shown in Figure 12 🎀
The modifications to the SPF are lowkey small but important 💖 The root of the block is called the block-root, and it's either the GADAG root or a cut-vertex 👑
a. The SPF is rooted at a neighbor x of an IN_GADAG node y. All links between y and x get marked as TEMP_UNUSABLE. They should not be used during the SPF computation 🫶
b. If y is not the block-root, then it's marked TEMP_UNUSABLE, and it should not be used during the SPF computation either 🙈 This stops ears from starting and ending at the same node, and it avoids cycles. The exception is cycles to and from the block-root, which are acceptable and expected 💜
c. Do not explore links to nodes whose localroot is not the block-root. This keeps the SPF confined to the particular block 🌸
d. Terminate when the first IN_GADAG node z is minimized ✨
e. Respect the existing directions (e.g., INCOMING, OUTGOING, UNDIRECTED) already specified for each interface. no skipping that one bestie 😭
Mod_SPF(spf_root, block_root)
Initialize spf_heap to empty
Initialize nodes' spf_metric to infinity
spf_root.spf_metric = 0
insert(spf_heap, spf_root)
found_in_gadag = false
while (spf_heap is not empty) and (found_in_gadag is false)
min_node = remove_lowest(spf_heap)
if min_node.IN_GADAG
found_in_gadag = true
else
foreach interface intf of min_node
if ((intf.OUTGOING or intf.UNDIRECTED) and
((intf.remote_node.localroot is block_root) or
(intf.remote_node is block_root)) and
(intf.remote_node is not TEMP_UNUSABLE) and
(intf is not TEMP_UNUSABLE))
path_metric = min_node.spf_metric + intf.metric
if path_metric < intf.remote_node.spf_metric
intf.remote_node.spf_metric = path_metric
intf.remote_node.spf_prev_intf = intf
insert_or_update(spf_heap, intf.remote_node)
return min_node
SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root,
method)
Mark all interfaces between cand_intf.remote_node
and cand_intf.local_node as TEMP_UNUSABLE
if cand_intf.local_node is not block_root
Mark cand_intf.local_node as TEMP_UNUSABLE
Initialize ear_list to empty
end_ear = Mod_SPF(spf_root, block_root)
y = end_ear.spf_prev_hop
while y.local_node is not spf_root
add_to_list_start(ear_list, y)
y.local_node.IN_GADAG = true
y = y.local_node.spf_prev_intf
if(method is not hybrid)
Set_Ear_Direction(ear_list, cand_intf.local_node,
end_ear,block_root)
Clear TEMP_UNUSABLE from all interfaces between
cand_intf.remote_node and cand_intf.local_node
Clear TEMP_UNUSABLE from cand_intf.local_node
return end_earFigure 31: Modified SPF for GADAG Construction 🌈
okay so say an ear gets found by going from y to x and then running an SPF that terminates by minimizing z (like y<->x...q<->z) 🔥 Now we have to figure out which way the ear points! If y<<z, the path should be y->x...q->z. But if y>>z, the path should be y<-x...q<-z 💀 Section 5.5 handled this same problem by finding all the ears that started at a node before looking at ears starting at nodes higher in the partial order. BUT in this GADAG construction method, doing it that way could mean new ears aren't added in order of their total cost, since all the ears connected to a node would have to be found before any additional nodes could be found 😭
The alternative is to track the order relationship of each node with respect to every other node. This is done by keeping two sets at each node. The first set, Higher_Nodes, has all nodes that are known to be ordered above the node. The second set, Lower_Nodes, has all nodes that are known to be ordered below the node. This is the approach this GADAG construction method uses 🦋
Set_Ear_Direction(ear_list, end_a, end_b, block_root)
// Default of A_TO_B for the following cases:
// (a) end_a and end_b are the same (root)
// or (b) end_a is in end_b's Lower Nodes
// or (c) end_a and end_b were unordered with respect to each
// other
direction = A_TO_B
if (end_b is block_root) and (end_a is not end_b)
direction = B_TO_A
else if end_a is in end_b.Higher_Nodes
direction = B_TO_A
if direction is B_TO_A
foreach interface i in ear_list
i.UNDIRECTED = false
i.INCOMING = true
i.remote_intf.UNDIRECTED = false
i.remote_intf.OUTGOING = true
else
foreach interface i in ear_list
i.UNDIRECTED = false
i.OUTGOING = true
i.remote_intf.UNDIRECTED = false
i.remote_intf.INCOMING = true
if end_a is end_b
return
// Next, update all nodes' Lower_Nodes and Higher_Nodes
if (end_a is in end_b.Higher_Nodes)
foreach node x where x.localroot is block_root
if end_a is in x.Lower_Nodes
foreach interface i in ear_list
add i.remote_node to x.Lower_Nodes
if end_b is in x.Higher_Nodes
foreach interface i in ear_list
add i.local_node to x.Higher_Nodes
else
foreach node x where x.localroot is block_root
if end_b is in x.Lower_Nodes
foreach interface i in ear_list
add i.local_node to x.Lower_Nodes
if end_a is in x.Higher_Nodes
foreach interface i in ear_list
add i.remote_node to x.Higher_NodesFigure 32: Algorithm to Assign Links of an Ear Direction 💅
The goal of this GADAG construction method is to find the shortest cycles and ears 👑 An ear starts 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's computed via SPF. And since a shortest path is made of shortest paths, finding the shortest ears means reaching from the set of IN_GADAG nodes to the closest node that isn't IN_GADAG 🧚 So an ordered tree is maintained of the interfaces that could be explored from the IN_GADAG nodes. The interfaces are ordered by their characteristics of metric, local loopback address, remote loopback address, and ifindex, based on the Interface_Compare function defined in Figure 14 🌸
This GADAG construction method skips interfaces picked from the ordered list that belong to the block root, if the block that the interface is in already has an ear that's been computed 🙈 This is necessary because we allow at most one incoming interface to a block root in each block. That requirement comes from the way next hops are computed, as seen in Section 5.7 💖 After any ear gets computed, we go through the newly added nodes to the GADAG and insert interfaces whose far end isn't on the GADAG yet into the ordered tree for later processing ✨
Last but not least, cut-links are a special case, because there's no point in doing an SPF on a block of two nodes 🥹 The algorithm identifies cut-links simply as links where both ends are cut-vertices. Cut-links can just be added to the GADAG with both OUTGOING and INCOMING specified on their interfaces 🎀
add_eligible_interfaces_of_node(ordered_intfs_tree,node)
for each interface of node
if intf.remote_node.IN_GADAG is false
insert(intf,ordered_intfs_tree)
check_if_block_has_ear(x,block_id)
block_has_ear = false
for all interfaces of x
if ( (intf.remote_node.block_id == block_id) &&
intf.remote_node.IN_GADAG )
block_has_ear = true
return block_has_ear
Construct_GADAG_via_SPF(topology, root)
Compute_Localroot (root,root)
Assign_Block_ID(root,0)
root.IN_GADAG = true
add_eligible_interfaces_of_node(ordered_intfs_tree,root)
while ordered_intfs_tree is not empty
cand_intf = remove_lowest(ordered_intfs_tree)
if cand_intf.remote_node.IN_GADAG is false
if L(cand_intf.remote_node) == D(cand_intf.remote_node)
// Special case for cut-links
cand_intf.UNDIRECTED = false
cand_intf.remote_intf.UNDIRECTED = false
cand_intf.OUTGOING = true
cand_intf.INCOMING = true
cand_intf.remote_intf.OUTGOING = true
cand_intf.remote_intf.INCOMING = true
cand_intf.remote_node.IN_GADAG = true
add_eligible_interfaces_of_node(
ordered_intfs_tree,cand_intf.remote_node)
else
if (cand_intf.remote_node.local_root ==
cand_intf.local_node) &&
check_if_block_has_ear(cand_intf.local_node,
cand_intf.remote_node.block_id))
/* Skip the interface since the block root
already has an incoming interface in the
block */
else
ear_end = SPF_for_Ear(cand_intf.local_node,
cand_intf.remote_node,
cand_intf.remote_node.localroot,
SPF method)
y = ear_end.spf_prev_hop
while y.local_node is not cand_intf.local_node
add_eligible_interfaces_of_node(
ordered_intfs_tree, y.local_node)
y = y.local_node.spf_prev_intfFigure 33: SPF-Based Method for GADAG Construction 🧚
Appendix C. Constructing a GADAG Using a Hybrid Method ✨
okay bestie, this is the hybrid method, and it's giving best-of-both-worlds 🦋 It mixes the best bits of the lowpoint inheritance method and the SPF method. We handle nodes as they get added to the GADAG, just like lowpoint inheritance, by keeping a stack of nodes. That means we never need to keep lower and higher sets at each node to figure out ear directions, because every ear points away from the node being processed toward the end of the ear. 🧚 For actually computing the ear, though, we call an SPF 💅 That gives us the chance to find better ears (shorter path lengths), so we have way more flexibility than just using the restricted lowpoint/DFS parents. Iconic. 👑
Now, ears involving a block root are where it gets spicy 🌶️ In the SPF method, the block root's interfaces got ignored after the first ear. In the hybrid method, we have to process all of the block root's interfaces before we move on to other nodes in the block, since the direction of an ear is already decided. So whenever the block already has an ear computed and we're processing one of the block root's interfaces, we mark the block root as unusable before the SPF run that computes the ear. This makes sure the SPF ends at some node other than the block root. Which means the block root ends up with only one incoming interface in each block, and that's necessary for getting the next hops on the GADAG right. Main character energy for the block root 🎀
Bridge ears get handled as a special case, same as in the SPF GADAG. ✨
The whole algorithm is in Figure 34 below. 🌸
find_spf_stack_ear(stack, x, y, xy_intf, block_root)
if L(y) == D(y)
// Special case for cut-links
xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true
xy_intf.INCOMING = true
xy_intf.remote_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true
xy_intf.remote_node.IN_GADAG = true
push y onto stack
return
else
if (y.local_root == x) &&
check_if_block_has_ear(x,y.block_id)
//Avoid the block root during the SPF
Mark x as TEMP_UNUSABLE
end_ear = SPF_for_Ear(x,y,block_root,hybrid)
If x was set as TEMP_UNUSABLE, clear it
cur = end_ear
while (cur != y)
intf = cur.spf_prev_hop
prev = intf.local_node
intf.UNDIRECTED = false
intf.remote_intf.UNDIRECTED = false
intf.OUTGOING = true
intf.remote_intf.INCOMING = true
push prev onto stack
cur = prev
xy_intf.UNDIRECTED = false
xy_intf.remote_intf.UNDIRECTED = false
xy_intf.OUTGOING = true
xy_intf.remote_intf.INCOMING = true
return
Construct_GADAG_via_hybrid(topology,root)
Compute_Localroot (root,root)
Assign_Block_ID(root,0)
root.IN_GADAG = true
Initialize Stack to empty
push root onto Stack
while (Stack is not empty)
x = pop(Stack)
for each interface intf of x
y = intf.remote_node
if y.IN_GADAG is false
find_spf_stack_ear(stack, x, y, intf, y.block_root)Figure 34: Hybrid GADAG Construction Method
Acknowledgements 💖
huge thank-you hugs 🫶 to Shraddha Hegde, Eric Wu, Janos Farkas, Stewart Bryant, Alvaro Retana, and Deccan (Shaofu Peng) for their suggestions and review. 🙌 Also a big shoutout to Anil Kumar SN for helping clarify the algorithm description and pseudocode. You all are literally the reason this is readable 😭✨
Authors' Addresses 🌈
Gabor Sandor Enyedi
Ericsson
Konyves Kalman krt 11
Budapest 1097
Hungary
Email: Gabor.Sandor.Enyedi@ericsson.com
Andras Csaszar
Ericsson
Konyves Kalman krt 11
Budapest 1097
Hungary
Email: Andras.Csaszar@ericsson.com
Alia Atlas
Juniper Networks
10 Technology Park Drive
Westford, MA 01886
United States
Email: akatlas@juniper.net
Chris Bowers
Juniper Networks
1194 N. Mathilda Ave.
Sunnyvale, CA 94089
United States
Email: cbowers@juniper.net
Abishek Gopalan
University of Arizona
1230 E Speedway Blvd.
Tucson, AZ 85721
United States
Email: abishek@ece.arizona.edu📦 where this page comes from
- ietf: rfc7811 2016-06
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms