Tech-invite3GPPspaceIETF RFCsSIP
in Index   Prev   Next

RFC 7811

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

Pages: 118
Proposed Standard
Part 6 of 6 – Pages 108 to 118
First   Prev   None

Top   ToC   RFC7811 - Page 108   prevText
def Run_MRT_for_One_Source(topo, src):
    MRT_Island_Identification(topo, src, 0, 0)

def Run_Prim_SPF_for_One_Source(topo,src):
    Normal_SPF(topo, src)

def Run_MRT_for_All_Sources(topo):
    for src in topo.node_list:
        if src in topo.island_node_list_for_test_gr:
            # src runs MRT if it is in same MRT island as test_gr
            if src is topo.gadag_root:
            # src still runs SPF if not in MRT island

def Write_Output_To_Files(topo,file_prefix):
Top   ToC   RFC7811 - Page 109
def Create_Basic_Topology_Input_File(filename):
    data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
    with open(filename + '.csv', 'w') as topo_file:
        for item in data:
            if len(item) > 3:
                line = (str(item[0])+','+str(item[1])+','+
                line = (str(item[0])+','+str(item[1])+','+

def Create_Complex_Topology_Input_File(filename):
    data = [[01,02,10],[02,03,10],[03,04,11],[04,05,10,20],[05,06,10],
    with open(filename + '.csv', 'w') as topo_file:
        for item in data:
            if len(item) > 3:
                line = (str(item[0])+','+str(item[1])+','+
                line = (str(item[0])+','+str(item[1])+','+

    data = [[01,0],[02,0],[03,0],[04,0],[05,0],
    with open(filename + '.profile', 'w') as topo_file:
        for item in data:
            line = (str(item[0])+','+str(item[1])+'\n')

    data = [[2001,05,100],[2001,07,120],[2001,03,130],
Top   ToC   RFC7811 - Page 110
    with open(filename + '.prefix', 'w') as topo_file:
        for item in data:
            line = (str(item[0])+','+str(item[1])+','+

def Generate_Basic_Topology_and_Run_MRT():
    this_gadag_root = 3
    topo = Create_Topology_From_File('basic_topo_input')
    res_file_base = 'basic_topo'
    Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
    Write_Output_To_Files(topo, res_file_base)

def Generate_Complex_Topology_and_Run_MRT():
    this_gadag_root = 3
    topo = Create_Topology_From_File('complex_topo_input')
    Compute_Island_Node_List_For_Test_GR(topo, this_gadag_root)
    res_file_base = 'complex_topo'
    Write_Output_To_Files(topo, res_file_base)




Appendix B. Constructing a GADAG Using SPFs

The basic idea in this method for constructing a GADAG is to use slightly modified SPF computations to find ears. In every block, an SPF computation is first done to find a cycle from the local root and then SPF computations in that block find ears until there are no more interfaces to be explored. The used result from the SPF computation is the path of interfaces indicated by following the previous hops from the minimized IN_GADAG node back to the SPF root. To do this, first all cut-vertices must be identified and localroots assigned as specified in Figure 12.
Top   ToC   RFC7811 - Page 111
   The slight modifications to the SPF are as follows.  The root of the
   block is referred to as the block-root; it is 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 are marked as TEMP_UNUSABLE.  They should
       not be used during the SPF computation.

   b.  If y is not the block-root, then it is marked TEMP_UNUSABLE.  It
       should not be used during the SPF computation.  This prevents
       ears from starting and ending at the same node and avoids cycles;
       the exception is because cycles to/from the block-root 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.

    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
              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
Top   ToC   RFC7811 - Page 112
    SPF_for_Ear(cand_intf.local_node,cand_intf.remote_node, block_root,
       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,
       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_ear

              Figure 31: Modified SPF for GADAG Construction

   Assume that an ear is found by going from y to x and then running an
   SPF that terminates by minimizing z (e.g., y<->x...q<->z).  Now it is
   necessary to determine the direction of the ear; if y<<z, then the
   path should be y->x...q->z; but if y>>z, then the path should be
   y<-x...q<-z.  In Section 5.5, the same problem was handled by finding
   all ears that started at a node before looking at ears starting at
   nodes higher in the partial order.  In this GADAG construction
   method, using that approach could mean that new ears aren't added in
   order of their total cost since all ears connected to a node would
   need to be found before additional nodes could be found.

   The alternative is to track the order relationship of each node with
   respect to every other node.  This can be accomplished by maintaining
   two sets of nodes at each node.  The first set, Higher_Nodes,
   contains all nodes that are known to be ordered above the node.  The
   second set, Lower_Nodes, contains all nodes that are known to be
   ordered below the node.  This is the approach used in this GADAG
   construction method.
Top   ToC   RFC7811 - Page 113
      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
           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
         // 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
            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_Nodes

         Figure 32: Algorithm to Assign Links of an Ear Direction

   A goal of this GADAG construction method is to find the shortest
   cycles and ears.  An ear is started by going to a neighbor x of an
   IN_GADAG node y.  The path from x to an IN_GADAG node is minimal,
Top   ToC   RFC7811 - Page 114
   since it is computed via SPF.  Since a shortest path is made of
   shortest paths, to find the shortest ears requires reaching from the
   set of IN_GADAG nodes to the closest node that isn't IN_GADAG.
   Therefore, an ordered tree is maintained of 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 ignores interfaces picked from the
   ordered list that belong to the block root if the block in which the
   interface is present already has an ear that has been computed.  This
   is necessary since we allow at most one incoming interface to a block
   root in each block.  This requirement stems from the way next hops
   are computed as was seen in Section 5.7.  After any ear gets
   computed, we traverse the newly added nodes to the GADAG and insert
   interfaces whose far end is not yet on the GADAG to the ordered tree
   for later processing.

   Finally, cut-links are a special case because there is no point in
   doing an SPF on a block of two nodes.  The algorithm identifies cut-
   links simply as links where both ends of the link are cut-vertices.
   Cut-links can simply be added to the GADAG with both OUTGOING and
   INCOMING specified on their interfaces.

        for each interface of node
           if intf.remote_node.IN_GADAG is false

        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)
       root.IN_GADAG = true
       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
Top   ToC   RFC7811 - Page 115
                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
             if (cand_intf.remote_node.local_root ==
                 cand_intf.local_node) &&
                 /* Skip the interface since the block root
                 already has an incoming interface in the
                 block */
             ear_end = SPF_for_Ear(cand_intf.local_node,
                     SPF method)
             y = ear_end.spf_prev_hop
             while y.local_node is not cand_intf.local_node
                     ordered_intfs_tree, y.local_node)
                 y = y.local_node.spf_prev_intf

            Figure 33: SPF-Based Method for GADAG Construction

Appendix C. Constructing a GADAG Using a Hybrid Method

The idea of this method is to combine the salient features of the lowpoint inheritance and SPF methods. To this end, we process nodes as they get added to the GADAG just like in the lowpoint inheritance by maintaining a stack of nodes. This ensures that we do not need to maintain lower and higher sets at each node to ascertain ear directions since the ears will always be directed from the node being processed towards the end of the ear. To compute the ear however, we resort to an SPF to have the possibility of better ears (path lengths) thus giving more flexibility than the restricted use of lowpoint/dfs parents. Regarding ears involving a block root, unlike the SPF method, which ignored interfaces of the block root after the first ear, in the hybrid method we would have to process all interfaces of the block root before moving on to other nodes in the block since the direction
Top   ToC   RFC7811 - Page 116
   of an ear is predetermined.  Thus, whenever the block already has an
   ear computed, and we are processing an interface of the block root,
   we mark the block root as unusable before the SPF run that computes
   the ear.  This ensures that the SPF terminates at some node other
   than the block-root.  This in turn guarantees that the block-root has
   only one incoming interface in each block, which is necessary for
   correctly computing the next hops on the GADAG.

   As in the SPF GADAG, bridge ears are handled as a special case.

   The entire algorithm is shown below in Figure 34.

      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
            if (y.local_root == x) &&
               //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
Top   ToC   RFC7811 - Page 117
         Compute_Localroot (root,root)
         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


The authors would like to thank Shraddha Hegde, Eric Wu, Janos Farkas, Stewart Bryant, Alvaro Retana, and Deccan (Shaofu Peng) for their suggestions and review. We would also like to thank Anil Kumar SN for his assistance in clarifying the algorithm description and pseudocode.
Top   ToC   RFC7811 - Page 118

Authors' Addresses

Gabor Sandor Enyedi Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Andras Csaszar Ericsson Konyves Kalman krt 11 Budapest 1097 Hungary Email: Alia Atlas Juniper Networks 10 Technology Park Drive Westford, MA 01886 United States Email: Chris Bowers Juniper Networks 1194 N. Mathilda Ave. Sunnyvale, CA 94089 United States Email: Abishek Gopalan University of Arizona 1230 E Speedway Blvd. Tucson, AZ 85721 United States Email: