Routing Area Working Group G. Enyedi
Internet-Draft A. Császár
Intended status: Standards Track Ericsson
Expires: July 13, 2016 A. Atlas
C. Bowers
Juniper Networks
A. Gopalan
University of Arizona
January 10, 2016

An Algorithm for Computing Maximally Redundant Trees for IP/LDP Fast-Reroute


A solution for IP and LDP Fast-Reroute using Maximally Redundant Trees is presented in draft-ietf-rtgwg-mrt-frr-architecture. This document defines the associated MRT Lowpoint algorithm that is used in the Default MRT profile to compute both the necessary Maximally Redundant Trees with their associated next-hops and the alternates to select for MRT-FRR.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on July 13, 2016.

Copyright Notice

Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents ( in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

1. Introduction

MRT Fast-Reroute requires that packets can be forwarded not only on the shortest-path tree, but also on two Maximally Redundant Trees (MRTs), referred to as the MRT-Blue and the MRT-Red. A router which experiences a local failure must also have pre-determined which alternate to use. This document defines how to compute these three things for use in MRT-FRR and describes the algorithm design decisions and rationale. The algorithm is based on those presented in [MRTLinear] and expanded in [EnyediThesis]. The MRT Lowpoint algorithm is required for implementation when the Default MRT profile is implemented.

Just as packets routed on a hop-by-hop basis require that each router compute a shortest-path tree which is consistent, it is necessary for each router to compute the MRT-Blue next-hops and MRT-Red next-hops in a consistent fashion. This document defines the MRT Lowpoint algorithm to be used as a standard in the default MRT profile for MRT-FRR.

As now, a router's FIB will contain primary next-hops for the current shortest-path tree for forwarding traffic. In addition, a router's FIB will contain primary next-hops for the MRT-Blue for forwarding received traffic on the MRT-Blue and primary next-hops for the MRT-Red for forwarding received traffic on the MRT-Red.

What alternate next-hops a point-of-local-repair (PLR) selects need not be consistent - but loops must be prevented. To reduce congestion, it is possible for multiple alternate next-hops to be selected; in the context of MRT alternates, each of those alternate next-hops would be equal-cost paths.

This document defines an algorithm for selecting an appropriate MRT alternate for consideration. Other alternates, e.g. LFAs that are downstream paths, may be preferred when available. See the Operational Considerations section of [I-D.ietf-rtgwg-mrt-frr-architecture] for a more detailed discussion of combining MRT alternates with those produced by other FRR technologies.

[E]---[D]---|           [E]<--[D]<--|                [E]-->[D]
 |     |    |            |     ^    |                       |   
 |     |    |            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 1

The MRT Lowpoint algorithm can handle arbitrary network topologies where the whole network graph is not 2-connected, as in Figure 2, as well as the easier case where the network graph is 2-connected (Figure 1). Each MRT is a spanning tree. The pair of MRTs provide two paths from every node X to the root of the MRTs. Those paths share the minimum number of nodes and the minimum number of links. Each such shared node is a cut-vertex. Any shared links are cut-links.

                 [E]---[D]---|     |---[J]  
                  |     |    |     |    |   
                  |     |    |     |    |   
                 [R]   [F]  [C]---[G]   |   
                  |     |    |     |    |   
                  |     |    |     |    |   
                 [A]---[B]---|     |---[H]  

                (a) a graph that isn't 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

2. 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

Please see the Terminology section of [I-D.ietf-rtgwg-mrt-frr-architecture] for a complete list of terminology relevant to this draft. The list below does not repeat terminology introduced in that draft.

spanning tree:
A tree containing links that connects all nodes in the network graph.
In the context of a spanning tree computed via a depth-first search, a back-edge is a link that connects a descendant of a node x with an ancestor of x.
partial ADAG:
A subset of an ADAG that doesn't yet contain all the nodes in the block. A partial ADAG is created during the MRT algorithm and then expanded until all nodes in the block are included and it is an ADAG.
Depth-First Search
DFS ancestor:
A node n is a DFS ancestor of x if n is on the DFS-tree path from the DFS root to x.
DFS descendant:
A node n is a DFS descendant of x if x is on the DFS-tree path from the DFS root to n.
A path along not-yet-included-in-the-GADAG nodes that starts at a node that is already-included-in-the-GADAG and that ends at a node that is already-included-in-the-GADAG. The starting and ending nodes may be the same node if it is a cut-vertex.
X >> Y or Y << X:
Indicates the relationship between X and Y in a partial order, such as found in a GADAG. X >> Y means that X is higher in the partial order than Y. Y << X means that Y is lower in the partial order than X.
X > Y or Y < X:
Indicates the relationship between X and Y in the total order, such as found via a topological sort. X > Y means that X is higher in the total order than Y. Y < X means that Y is lower in the total order than X.
X ?? Y:
Indicates that X is unordered with respect to Y in the partial order.
In the GADAG, each link is marked as OUTGOING, INCOMING or both. Until the directionality of the link is determined, the link is marked as UNDIRECTED to indicate that its direction hasn't been determined.
A link marked as OUTGOING has direction in the GADAG from the interface's router to the remote end.
A link marked as INCOMING has direction in the GADAG from the remote end to the interface's router.

4. Algorithm Key Concepts

There are five key concepts that are critical for understanding the MRT Lowpoint algorithm. The first is the idea of partially ordering the nodes in a network graph with regard to each other and to the GADAG root. The second is the idea of finding an ear of nodes and adding them in the correct direction. The third is the idea of a Low-Point value and how it can be used to identify cut-vertices and to find a second path towards the root. The fourth is the idea that a non-2-connected graph is made up of blocks, where a block is a 2-connected cluster, a cut-link or an isolated node. The fifth is the idea of a local-root for each node; this is used to compute ADAGs in each block.

4.1. Partial Ordering for Disjoint Paths

Given any two nodes X and Y in a graph, a particular total order means that either X < Y or X > Y in that total order. An example would be a graph where the nodes are ranked based upon their unique IP loopback addresses. In a partial order, there may be some nodes for which it can't be determined whether X << Y or X >> Y. A partial order can be captured in a directed graph, as shown in Figure 3. In a graphical representation, a link directed from X to Y indicates that 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             |

Figure 3: Directed Graph showing a Partial Order

To compute MRTs, the root of the MRTs is at both the very bottom and the very top of the partial ordering. This means that from any node X, one can pick nodes higher in the order until the root is reached. Similarly, from any node X, one can pick nodes lower in the order until the root is reached. For instance, in Figure 4, from G the higher nodes picked can be traced by following the directed links and are H, D, E and R. Similarly, from G the lower nodes picked can be traced by reversing the directed links and are F, B, A, and R. A graph that represents this modified partial order is no longer a DAG; it is termed an Almost DAG (ADAG) because if the links directed to the root were removed, it would be a DAG.

[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

Figure 4: ADAG showing a Partial Order with R lowest and highest

Most importantly, if a node Y >> X, then Y can only appear on the increasing path from X to the root and never on the decreasing path. Similarly, if a node Z << X, then Z can only appear on the decreasing path from X to the root and never on the inceasing path.

When following the increasing paths, it is possible to pick multiple higher nodes and still have the certainty that those paths will be disjoint from the decreasing paths. E.g. in the previous example node B has multiple possibilities to forward packets along an increasing path: it can either forward packets to C or F.

4.2. Finding an Ear and the Correct Direction

For simplicity, the basic idea of creating a GADAG by adding ears is described assuming that the network graph is a single 2-connected cluster so that an ADAG is sufficient. Generalizing to multiple blocks is done by considering the block-roots instead of the GADAG root - and the actual algorithm is given in Section 5.5.

In order to understand the basic idea of finding an ADAG, first suppose that we have already a partial ADAG, which doesn't contain all the nodes in the block yet, and we want to extend it to cover all the nodes. Suppose that we find a path from a node X to Y such that X and Y are already contained by our partial ADAG, but all the remaining nodes along the path are not added to the ADAG yet. We refer to such a path as 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 we suppose that 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 consider 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 5

In this partial ADAG, node C is not yet included. However, we can find path B-C-D, where both endpoints are contained by this partial ADAG (we say those nodes are "ready" in the following text), and the remaining node (node C) is not contained yet. If we remove R, the remaining DAG defines a partial order, and with respect to this partial order we can say that B<<D, so we can add the path to the 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 such that it doesn't create a cycle; therefore the ear must go from X to Y.

In the case, when X and Y are not ordered with each other, we can select either direction for the ear. We have no restriction since neither of the directions can result in a cycle. In the corner case when one of the endpoints of an ear, say X, is the root (recall that the two endpoints must be different), we could use both directions again for the ear because the root can be considered both as smaller and as greater than Y. However, we strictly pick that direction in 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 is starting the ordering.

Once a partial ADAG is already present, it will always have a node that is not the root R in it. As a brief proof that a partial ADAG can always have ears added to it: just select a non-ready neighbor N of a ready node Q, such that Q is not the root R, 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, then the path until the first ready node the path reached (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 is always possible to select a non-ready neighbor N of a ready node Q so that Q is not the root R. Because the network is 2-connected, N must be connected to two different nodes and only one can be R. Because the initial cycle has already been added to the ADAG, there are ready nodes that are not R. Since the graph is 2-connected, while there are non-ready nodes, there must be a non-ready neighbor N of a ready node that is not R.

   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 exists 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 graph

The algorithm in Figure 6 merely requires that a cycle or ear be selected without specifying how. Regardless of the method for selecting the path, we will get an ADAG. The method used for finding and selecting the ears is important; shorter ears result in shorter paths along the MRTs. The MRT Lowpoint algorithm uses the Low-Point Inheritance method for constructing an ADAG (and ultimately a GADAG). This method is defined in Section 5.5. Other methods for constructing GADAGs are described in Appendix B and Appendix C. An evaluation of these different methods is given in Section 8

As an example, consider Figure 5 again. First, we select the shortest cycle containing R, which can be R-A-B-F-D-E (uniform link costs were assumed), so we get to the situation depicted in Figure 5 (b). Finally, we find a node next to a ready node; that must be node C and assume we reached it from ready node B. We search a path from C to R without B in the original graph. The first ready node along this 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, we stop at this point.

4.3. Low-Point Values and Their Uses

A basic way of computing a spanning tree on a network graph is to run a depth-first-search, such as given in Figure 7. This tree has the important 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. In other words, 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 Depth-First Search algorithm

Given a node x, one can compute the minimal DFS number of the neighbours of x, i.e. min( D(w) if (x,w) is a link). This gives the earliest attachment point neighbouring x. What is interesting, though, is what is the earliest attachment point from x and x's descendants. This is what is determined by computing the Low-Point value.

In order to compute the low point value, the network is traversed using DFS and the vertices are numbered based on the DFS walk. Let this number be represented as DFS(x). All the edges that lead to already visited nodes during DFS walk are back-edges. The back-edges are important because they give information about reachability of a node via another path.

The low point number is calculated by finding:

Low(x) = Minimum of (
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 low-point value is given in Figure 8. Figure 9 illustrates how the lowpoint algorithm applies to a 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 Low-Point 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 low-point values assigned (D(x), L(x))

Figure 9: Example lowpoint value computation

From the low-point value and lowpoint parent, there are three very useful things which motivate our 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 - and therefore x is a cut-vertex. In Figure 9, this can be seen by looking at the DFS children of C. C has two children - D and F and L(F) = 3 = D(C) so it is clear that C is a cut-vertex and F is in a block where C is the block's root. 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 low-point values of all a node's DFS-children with the node's DFS-value is very useful because it allows identification of the cut-vertices and thus 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. The full path need not be taken, 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 is 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 that are:
     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 10

Consider the example depicted in Figure 10 (a). In this figure, a special graph is presented, showing us all the ways 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, and block 4 is a cut-link containing H and K. As can be observed, the first two blocks have one common node (node C) and blocks 2 and 3 do not have any common node, but they are connected through a cut-link that is block 4. No two blocks can have more than one common node, since two blocks with at least two common nodes would qualify as a single 2-connected cluster.

Moreover, observe that if we want to get from one block to another, we must use a cut-vertex (the cut-vertices in this graph are C, H, K), regardless of the path selected, so we can say that all the paths from block 3 along the MRTs rooted at R will cross K first. This observation means that if we want to find a pair of MRTs rooted at R, then we need to build up a pair of RTs in block 3 with K as a root. Similarly, we need to find another pair of RTs in block 2 with C as a root, and finally, we need the last pair of RTs in block 1 with R as a root. When all the trees are selected, we can simply combine them; when a block is a cut-link (as in block 4), that cut-link is added in the same direction to both of the trees. The resulting trees are depicted in Figure 10 (b) and (c).

Similarly, to create a GADAG it is sufficient to compute ADAGs in each block and connect them.

It is necessary, therefore, to identify the cut-vertices, the blocks and identify the appropriate local-root to use for each block.

4.5. Determining Local-Root and Assigning Block-ID

Each node in a network graph has a local-root, which is the cut-vertex (or root) in the same block that is closest to the root. The local-root is used to determine whether two nodes share a common 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)
                mark x as cut-vertex
                Compute_Localroot(c, x)
    Compute_Localroot(gadag_root, gadag_root)

Figure 11: A method for computing local-roots

There are two different ways of computing the local-root for each node. The stand-alone method is given in Figure 11 and better illustrates the concept; it is used by the GADAG construction methods given in Appendix B and Appendix C. The MRT Lowpoint algorithm computes the local-root for a block as part of computing the GADAG using lowpoint inheritance; the essence of this computation is given in Figure 12. Both methods for computing the local-root produce the same results.

   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
      for each node x in the ear that is not s or e
          x.localroot = e.localroot

Figure 12: Ear-based method for computing local-roots

Once the local-roots are known, two nodes X and Y are in a common block if and only if one of the following three conditions apply.

  • Y's local-root is X's local-root : They are in the same block and neither is the cut-vertex closest to the root.
  • Y's local-root is X: X is the cut-vertex closest to the root for Y's block
  • Y is X's local-root: Y is the cut-vertex closest to the root for X's block

Once we have computed the local-root for each node in the network graph, we can assign for each node, a block id that represents the block in which the node is present. This computation is shown in 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)
       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 computes one GADAG that is then used by a router to determine its MRT-Blue and MRT-Red next-hops to all destinations. Finally, based upon that information, alternates are selected for each next-hop to each destination. The different parts of this algorithm are described below.

  • 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 blue MRT and the red MRT the computing router x should select. [See Section 5.8]

A Python implementation of this algorithm is given in Appendix A.

5.1. Interface Ordering

To ensure consistency in computation, all routers MUST order interfaces identically down to the set of links with the same metric to the same neighboring node. This is necessary for the DFS in Lowpoint_Visit in Section 4.3, where the selection order of the interfaces to explore results in different trees. Consistent interface ordering is also necessary for computing the GADAG, where the selection order of the interfaces to use to form ears can result in different GADAGs. It is also necessary for the topological sort described in Section 5.8, where different topological sort orderings can result in undirected links being added to the GADAG in different directions.

The required ordering between two interfaces from the same router x is given in Figure 14.

Interface_Compare(interface a, interface b)
  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.

In Figure 14, if two interfaces on a router connect to the same remote router with the same metric, the Interface_Compare function returns A_EQUAL_TO_B. This is because the order in which those interfaces are initially explored does not affect the final GADAG produced by the algorithm described here. While only one of the links will be added to the GADAG in the initial traversal, the other parallel links will be added to the GADAG with the same direction assigned during the procedure for assigning direction to UNDIRECTED links described in Section 5.6. An implementation is free to apply some additional criteria to break ties in interface ordering in this situation, but that criteria is not specified here since it will not affect the final GADAG produced by the algorithm.

The Interface_Compare function in Figure 14 relies on the interface.metric and the interface.neighbor.mrt_node_id values to order interfaces. The exact source of these values for different IGPs and applications is specified in Figure 15. The metric and mrt_node_id values for OSPFv2, OSPFv3, and IS-IS provided here is normative. The metric and mrt_node_id values for ISIS-PCR in this 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 #22        |
|              | in Extended IS        | or Multi-Topology           |
|              | Reachability TLV #22  | IS Neighbor TLV #222        |
|              | or Multi-Topology     |                             |
|              | IS Neighbor TLV #222  |                             |
| ISIS-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   | SPB Instance sub-TLV  | TLV #22 or Multi-Topology   |
| networks     | (type 1) carried in   | Intermediate Systems        |
|              | MT-Capability TLV     | TLV #222.  In the case      |
|              | #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 #22  | directions.                 |
|              | or Multi-Topology     | (informational)             |
|              | Intermediate Systems  |                             |
|              | TLV #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 applications

The metrics are unsigned integers and MUST be compared as unsigned integers. The results of mrt_node_id comparisons MUST be the same as would be obtained by converting the mrt_node_ids to unsigned integers using network byte order and performing the comparison as unsigned integers. In the case of IS-IS for IP/LDP FRR with point-to-point links, the pseudonode number (the 7th octet) is zero. Broadcast interfaces will be discussed in Section 7.

5.2. MRT Island Identification

The local MRT Island for a particular MRT profile can be determined by starting from the computing router in the network graph and doing a breadth-first-search (BFS). The BFS explores only links that are in the same area/level, are not IGP-excluded, and are not MRT-ineligible. The BFS explores only nodes that are are not IGP-excluded, and that support the particular MRT profile. See section 7 of [I-D.ietf-rtgwg-mrt-frr-architecture] for more precise definitions of these criteria.

MRT_Island_Identification(topology, computing_rtr, profile_id, area)
  for all routers in topology
  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.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_node.IN_MRT_ISLAND = TRUE   
           if (not intf.remote_node.IN_MRT_ISLAND))
              intf.remote_node.IN_MRT_ISLAND = TRUE
              add_to_tail(explore_list, intf.remote_node)

Figure 16: MRT Island Identification

5.3. GADAG Root Selection

In Section 8.3 of [I-D.ietf-rtgwg-mrt-frr-architecture], the GADAG Root Selection Policy is described for the MRT default profile. This selection policy allows routers to consistently select a common GADAG Root inside the local MRT Island, based on advertised priority values. The MRT Lowpoint algorithm simply requires that all routers in the MRT Island MUST select the same GADAG Root; the mechanism can vary based upon the MRT profile description. Before beginning computation, the network graph is reduced to contain only the set of routers that support the specific MRT profile whose MRTs are being computed.

As noted in Section 7, pseudonodes MUST NOT be considered for GADAG root selection.

It is expected that an operator will designate a set of routers as good choices for selection as GADAG root by setting the GADAG Root Selection Priority for that set of routers to lower (more preferred) numerical values. For guidance on setting the GADAG Root Selection Priority values, refer to Section 10.1.

5.4. Initialization

Before running the algorithm, there is the standard type of initialization to be done, such as clearing any computed DFS-values, lowpoint-values, DFS-parents, lowpoint-parents, any MRT-computed next-hops, and flags associated with algorithm.

It is assumed that a regular SPF computation has been run so that the primary next-hops from the computing router to each destination are known. This is required for determining alternates at the last step.

Initially, all interfaces MUST be initialized to UNDIRECTED. Whether they are OUTGOING, INCOMING or both is determined when the GADAG is constructed and augmented.

It is possible that some links and nodes will be marked using standard IGP mechanisms to discourage or prevent transit traffic. Section 7.3.1 of [I-D.ietf-rtgwg-mrt-frr-architecture] describes how those links and nodes are excluded from MRT Island formation.

MRT-FRR also has the ability to advertise links MRT-Ineligible, as described in Section 7.3.2 of [I-D.ietf-rtgwg-mrt-frr-architecture]. These links are excluded from the MRT Island and the GADAG. Computation of MRT next-hops will therefore not use any MRT-ineligible links. The MRT algorithm does still need to consider MRT-ineligible links when computing FRR alternates, because an MRT-ineligible link can still be the shortest-path next-hop to reach a destination.

When a broadcast interface is advertised as MRT-ineligible, then the pseudo-node representing the entire broadcast network MUST NOT be included in the MRT Island. This is equivalent to excluding all of the broadcast interfaces on that broadcast network from the MRT Island.

5.5. Constructing the GADAG using lowpoint inheritance

As discussed in Section 4.2, it is necessary to find ears from a node x that is already in the GADAG (known as IN_GADAG). Two different methods are used to find ears in the algorithm. The first is by going to a not IN_GADAG DFS-child and then following the chain of low-point parents until an IN_GADAG node is found. The second is by going to a not IN_GADAG neighbor and then following the chain of DFS parents until an IN_GADAG node is found. As an ear is found, the associated interfaces are marked based on the direction taken. The nodes in the ear are marked as IN_GADAG. In the algorithm, first the ears via DFS-children are found and then the ears via DFS-neighbors are found.

By adding both types of ears when an IN_GADAG node is processed, all ears that connect to that node are found. The order in which the IN_GADAG nodes is processed is, of course, key to the algorithm. The order is a stack of ears so the most recent ear is found at the top of the stack. Of course, the stack stores nodes and not ears, so an ordered list of nodes, from the first node in the ear to the last node in the ear, is created as the ear is explored and then that list is pushed onto the stack.

Each ear represents a partial order (see Figure 4) and processing the nodes in order along each ear ensures that all ears connecting to a node are found before a node higher in the partial order has its ears explored. This means that the direction of the links in the ear is always from the node x being processed towards the other end of the ear. Additionally, by using a stack of ears, this means that any unprocessed nodes in previous ears can only be ordered higher than nodes in the ears below it on the stack.

In this algorithm that depends upon Low-Point inheritance, it is necessary that every node have a low-point parent that is not itself. If a node is a cut-vertex, that may not yet be the case. Therefore, any nodes without a low-point parent will have their low-point parent set to their DFS parent and their low-point value set to the DFS-value of their parent. This assignment also properly allows an ear between two cut-vertices.

Finally, the algorithm simultaneously computes each node's local-root, as described in Figure 12. This is further elaborated as follows. The local-root can be inherited from the node at the end of the ear unless the end of the ear is x itself, in which case the local-root for all the nodes in the ear would be x. This is because 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 all other scenarios, the properties of lowpoint/dfs parents ensure that the end of the ear will be in the same block, and thus inheriting its local-root would be the correct local-root for all newly added nodes.

The pseudo-code for the GADAG algorithm (assuming that the adjustment of lowpoint for cut-vertices has been made) is shown in Figure 17.

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
         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
      // Inherit local-root 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: Low-point 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