Tech-invite3GPPspecsGlossariesIETFRFCsGroupsSIPABNFsWorld Map

RFC 7811

Proposed STD
Pages: 118
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: RTGWG

An Algorithm for Computing IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)

Part 1 of 6, p. 1 to 17
None       Next RFC Part


Top       ToC       Page 1 
Internet Engineering Task Force (IETF)                         G. Enyedi
Request for Comments: 7811                                    A. Csaszar
Category: Standards Track                                       Ericsson
ISSN: 2070-1721                                                 A. Atlas
                                                               C. Bowers
                                                        Juniper Networks
                                                              A. Gopalan
                                                   University of Arizona
                                                               June 2016

             An Algorithm for Computing IP/LDP Fast Reroute
               Using Maximally Redundant Trees (MRT-FRR)


   This document supports the solution put forth in "An Architecture for
   IP/LDP Fast Reroute Using Maximally Redundant Trees (MRT-FRR)"
   (RFC 7812) by defining 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 is an Internet Standards Track document.

   This document is a product of the Internet Engineering Task Force
   (IETF).  It represents the consensus of the IETF community.  It has
   received public review and has been approved for publication by the
   Internet Engineering Steering Group (IESG).  Further information on
   Internet Standards is available in Section 2 of RFC 7841.

   Information about the current status of this document, any errata,
   and how to provide feedback on it may be obtained at

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

Top      ToC       Page 3 
   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  . . . . . . . . . . . . . . . . . . . . . . . 118

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 that
   experiences a local failure must also have predetermined 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.

   The MRT Lowpoint Algorithm defined in this document, when used for
   MRT Fast-Reroute as described in [RFC7812], guarantees 100% recovery
   for single failures when the network is 2-connected.  This guaranteed
   coverage does not depend on the link metrics, which an operator may
   be using to traffic-engineer the IP network.  Thus, the link metrics
   and general network topology are largely decoupled from the
   guaranteed coverage.

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

Top      ToC       Page 4 
   A router's Forwarding Information Base (FIB) will continue to 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., Loop-Free
   Alternates (LFAs) that are downstream paths, may be preferred when
   available.  See the "Operational Considerations" section of [RFC7812]
   for a more detailed discussion of combining MRT alternates with those
   produced by other FRR technologies.

   [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 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-

Top      ToC       Page 5 
                        [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-Connected

2.  Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in [RFC2119].

3.  Terminology and Definitions

   Please see the Terminology section of [RFC7812] for a complete list
   of terminology relevant to this document.  The list below does not
   repeat terminology introduced in that RFC.

   spanning tree:  A tree that contains links and that connects all
      nodes in the network graph.

   back-edge:  In the context of a spanning tree computed via a depth-
      first search, a back-edge is a link that connects a descendant of
      a node x with an ancestor of x.

   partial ADAG:  A subset of an Almost Directed Acyclic Graph (ADAG)
      that doesn't yet contain all the nodes in the block.  A partial
      ADAG is created during the MRT Lowpoint algorithm and then
      expanded until all nodes in the block are included and it becomes
      an ADAG.

   DFS:  Depth-First Search

Top      ToC       Page 6 
   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.

   ear:  A path along nodes that are not yet included in the Generalized
      ADAG (GADAG) 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.

   UNDIRECTED:  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.

   OUTGOING:  A link marked as OUTGOING has direction in the GADAG from
      the interface's router to the remote end.

   INCOMING:  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
   Lowpoint 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

Top      ToC       Page 7 
   2-connected cluster, a cut-link or an isolated node.  The fifth is
   the idea of a localroot 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.

Top      ToC       Page 8 
     [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 increasing 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.  For example, 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.

Top      ToC       Page 9 
           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.

Top      ToC       Page 10 
   Once a partial ADAG is already present, it will always have a node
   that is not the root R in it.  The following is 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 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 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 Lowpoint
   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 Appendices B and 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

Top      ToC       Page 11 
   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.  Lowpoint Values and Their Uses

   A basic way of computing a spanning tree on a network graph is to run
   a DFS, 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 DFS Algorithm

   Given a node x, one 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.  What is interesting,
   though, is the earliest attachment point from x and x's descendants.
   This is what is determined by computing the Lowpoint 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.

Top      ToC       Page 12 
   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 given in
   Figure 8.  Figure 9 illustrates how the Lowpoint algorithm applies to
   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

Top      ToC       Page 13 
            [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 Computation

   From the lowpoint value and lowpoint parent, there are three very
   useful things that 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; 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

Top      ToC       Page 14 
   to reach R.  Comparing the lowpoint 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

   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

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.

Top      ToC       Page 15 
                  [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 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.

Top      ToC       Page 16 
   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 localroot to use for each block.

4.5.  Determining Localroot and Assigning Block-ID

   Each node in a network graph has a localroot, which is the cut-vertex
   (or root) in the same block that is closest to the root.  The
   localroot is used to determine whether two nodes share a common

               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 Localroots

   There are two different ways of computing the localroot 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 Appendices B and C.  The MRT Lowpoint algorithm computes the
   localroot 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 localroot produce the same results.

Top      ToC       Page 17 
            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 Localroots

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

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

   o  Y's localroot is X: X is the cut-vertex closest to the root for
      Y's block

   o  Y is X's localroot: Y is the cut-vertex closest to the root for
      X's block

   Once we have computed the localroot for each node in the network
   graph, we can assign for each node, a Block-ID that represents the
   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

Next RFC Part