Subject: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Tue, 9 Jun 2015 06:26:47 +0000

Hi Authors,

As discussed before, Please find my review comments :

Comment 1: Can we rename parameter which is passed to these functions as real SPF root or GADAG root ?

   Run_DFS(node root)
   Run_Lowpoint(node root)
   Compute_Localroot(root, root)
   Construct_GADAG_via_Lowpoint(topology, root)
   Add_Undirected_Links(topo, root)
   Assign_Block_ID(root, max_block_id)
   Compute_MRT_NextHops(x, root)

Comment 2:  Here parenthesis are not matching, four '(' and five ')'.
           This must be typo mistake.

In_Common_Block(x, y)
  if ( (x.block_id is y.block_id))
       or (x is y.localroot) or (y is x.localroot) )
     return true
  return false

Comment 3:   Is it possible to rephrase "if an MRT doesn't use primary_intf"
What does the sentence "MRT doesn't use primary_intf" mean ? Dose it mean neither Red interface nor Blue interface is same as primary interface ?
What does the sentence "return that MRT color" means ?

Select_Alternates_Internal(S, D, F, primary_intf,
                           D_lower, D_higher, D_topo_order)

    //When D==F, we can do only link protection
    if ((D is F) or (D.order_proxy is F))
        if an MRT doesn't use primary_intf
            indicate alternate is not node-protecting
            return that MRT color

Thanks & Regards
Anil S N

"Be liberal in what you accept, and conservative in what you send" - Jon Postel

---

From: Chris Bowers <[email-masked]>
Date: Tue, 9 Jun 2015 18:58:39 +0000

Anil,

Thanks for the suggestion to clarify the use of root to mean gadag_root or spf_root in the pseudo-code, as well as the typo.  I made the changes on github.  The diff can be found at:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/ada619050ec9d773b7919a1c622f068d5a5a5e88
Tell me if you agree with these changes.

With respect to comment#3, if ((D is F) or (D.order_proxy is F)), then there are several cases to consider:

1) If the link from S to F is a cut-link,
                a) if this is a single cut-link between S and F, then there is no alternate
                b) if there are parallel cut-links between S and F, then one can, for example, ECMP across the remaining links, noting that there is no link protection.

2) if the link from S to F is not a cut-link, then at least one of the MRT next-hops for D (red or blue) will not be the same as the primary next-hop for D.  In which case, one should use the color that is not the primary next-hop as the alternate, noting that the alternate does not provide node protection.

I agree that the existing pseudo-code is not very clear here.  I am planning to update this part of the pseudo-code in the near future to make it clearer, but hopefully the explanation above suffices for the moment.

Chris

From: rtgwg [mailto:[email-masked]] On Behalf Of Anil Kumar S N (VRP Network BL)
Sent: Tuesday, June 09, 2015 1:27 AM
To: Gábor Sándor Enyedi; [email-masked]; Alia Atlas; Chris Bowers; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Wed, 10 Jun 2015 04:18:11 +0000

Hi Chris,

                Thanks it appears to be ok.

                I will go through the draft again. If I come across some things can be updated or  improved upon, I will keep you updated.

Thanks & Regards
Anil S N

From: Chris Bowers [mailto:[email-masked]]
Sent: 10 June 2015 00:29
To: Anil Kumar S N (VRP Network BL); Gábor Sándor Enyedi; [email-masked]; Alia Atlas; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

Anil,

Chris

From: rtgwg [mailto:[email-masked]] On Behalf Of Anil Kumar S N (VRP Network BL)
Sent: Tuesday, June 09, 2015 1:27 AM
To: Gábor Sándor Enyedi; [email-masked]<mailto:[email-masked]>; Alia Atlas; Chris Bowers; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Wed, 10 Jun 2015 11:16:25 +0000

Hi Chris,

"for each interface intf of x" in Figure 8: Computing Low-Point value & "for each link (x, w)" in Figure 7: Basic Depth-First Search algorithm is based on section : "5.1. Interface Ordering" ?
If yes can it be made more specific, since this very important part of logic, if not let me know how & where section : "5.1. Interface Ordering" is used in the algorithm.

Thanks & Regards
Anil S N

Anil,

Chris

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: Chris Bowers <[email-masked]>
Date: Fri, 12 Jun 2015 18:46:06 +0000

Anil,

I updated the github version to clarify this point.  The diff is here:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/042450051d39cf4be99ba0cde7b9e017be05d282

Where interface ordering is required, I used:
foreach ordered_interface intf of x

Where interface ordering is unimportant, I left it as:
foreach interface intf of x

The short version is that the interface ordering is required in the following functions:
Lowpoint_Visit()
Construct_GADAG_via_Lowpoint()
Run_Topological_Sort_GADAG()

Tell me if the clarifications make sense.

Thanks,
Chris

From: Anil Kumar S N (VRP Network BL) [mailto:[email-masked]]
Sent: Wednesday, June 10, 2015 6:16 AM
To: Chris Bowers; Gábor Sándor Enyedi; [email-masked]; Alia Atlas; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

Hi Chris,

Thanks & Regards
Anil S N

From: Chris Bowers [mailto:[email-masked]]
Sent: 10 June 2015 00:29
To: Anil Kumar S N (VRP Network BL); Gábor Sándor Enyedi; [email-masked]<mailto:[email-masked]>; Alia Atlas; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: RE: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

Anil,

Chris

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Mon, 15 Jun 2015 04:53:33 +0000

Chris,

                I think the changes are fine.

Thanks & Regards
Anil S N

Sent: 13 June 2015 00:16

Anil,

Thanks,
Chris

To: Chris Bowers; Gábor Sándor Enyedi; [email-masked]<mailto:[email-masked]>; Alia Atlas; [email-masked]<mailto:[email-masked]>

Hi Chris,

Thanks & Regards
Anil S N

Anil,

Chris

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Mon, 15 Jun 2015 08:24:58 +0000

Hi Chris,

                I couldn't find psudocode for indentifying and marking a link as cut-link and vertex as cut-vertex. Please correct me if I am wrong.

Thanks & Regards
Anil S N

Sent: 13 June 2015 02:46

Anil,

Thanks,
Chris

Hi Chris,

Thanks & Regards
Anil S N

Anil,

Chris

Hi Authors,

   Run_DFS(node root)
   Run_Lowpoint(node root)

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: Chris Bowers <[email-masked]>
Date: Wed, 17 Jun 2015 22:28:18 +0000

Anil,

Thanks for pointing this out.  Construct_Ear() mentions identifying a cut-vertex in a comment, but doesn't actually set it explicitly.  I added it as below, as reflected in the github diff link.

Construct_Ear(x, Stack, intf, ear_type)
...
   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   <<< New line here
      localroot = x
   else

https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/6a92a3fe9f578af2566d0dbb042181cb22469c57

With respect to identifying cut-links, I'd like to propose the following changes to the Add_Undirected_Links() to have it deal better with parallel-links from the block root (cut-vertices or the GADAG root) to another node.   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 links involving the block root.  There are three cases below.

case 1a) 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.
case 1b) In the case of parallel cut links, we set all of the parallel links to both INCOMING and OUTGOING.
case 2) Otherwise, the undirected link in question is set to OUTGOING from the block root node.

With this version of Add_Undirected_Links(), a cut-link can be identified by the fact that it will be directed both INCOMING and OUTGOING in the GADAG.

I put proposed pseudo-code to replace figure 18 in the github diff below.

https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/5d5e5c9c74ef963195e29cb2e7b449c8884facd4

The proposed next text and pseudo-code is copied below as well.

To convert a GADAG to a DAG, it is necessary to remove all links that
   point to a root of block from within that block.  That provides the
   necessary conversion to a DAG and then a topological sort can be
   done.  When adding undirected links to the GADAG, links connecting
   the block root to other nodes in that block need special handling
   because the topological order will not always give the right answer
   for those links.  There are three cases to consider.  If the
   undirected link in question has another parallel link between the
   same two nodes that is already directed, then the direction of the
   undirected link can be inherited from the previously directed link.
   In the case of parallel cut links, we set all of the parallel links
   to both INCOMING and OUTGOING.  Otherwise, the undirected link in
   question is set to OUTGOING from the block root node.  A cut-link can
   then be identified by the fact that it will be directed both INCOMING
   and OUTGOING in the GADAG.  The exact details of this whole process
   are captured in Figure 18

     Add_Undirected_Block_Root_Links(topo, gadag_root):
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if (i.remote_node.localroot is not x
                                         or i.PROCESSED )
                         continue
                     Initialize bundle_list to empty
                     bundle.UNDIRECTED = true
                     bundle.OUTGOING = false
                     bundle.INCOMING = false
                     foreach interface i2 in x
                         if i2.remote_node is i.remote_node
                             add_to_list_end(bundle_list, i2)
                             if not i2.UNDIRECTED:
                                 bundle.UNDIRECTED = false
                                 if i2.INCOMING:
                                     bundle.INCOMING = true
                                 if i2.OUTGOING:
                                     bundle.OUTGOING = true
                     if bundle.UNDIRECTED
                         foreach interface i3 in bundle_list
                             i3.UNDIRECTED = false
                             i3.remote_intf.UNDIRECTED = false
                             i3.PROCESSED = true
                             i3.remote_intf.PROCESSED = true
                             i3.OUTGOING = true
                             i3.remote_intf.INCOMING = true
                     else
                         if (bundle.OUTGOING and bundle.INCOMING)
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.OUTGOING = true
                                 i3.INCOMING = true
                                 i3.remote_intf.INCOMING = true
                                 i3.remote_intf.OUTGOING = true
                         else if bundle.OUTGOING
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.OUTGOING = true
                                 i3.remote_intf.INCOMING = true
                         else if bundle.INCOMING
                             foreach interface i3 in bundle_list
                                 i3.UNDIRECTED = false
                                 i3.remote_intf.UNDIRECTED = false
                                 i3.PROCESSED = true
                                 i3.remote_intf.PROCESSED = true
                                 i3.INCOMING = true
                                 i3.remote_intf.OUTGOING = true

     Modify_Block_Root_Incoming_Links(topo, gadag_root):
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if i.remote_node.localroot is x
                         if i.INCOMING:
                             i.INCOMING = false
                             i.INCOMING_STORED = true
                             i.remote_intf.OUTGOING = false
                             i.remote_intf.OUTGOING_STORED = true

     Revert_Block_Root_Incoming_Links(topo, gadag_root):
         foreach node x in topo
             if x.IS_CUT_VERTEX or x is gadag_root
                 foreach interface i of x
                     if i.remote_node.localroot is x
                         if i.INCOMING_STORED:
                             i.INCOMING = true
                             i.remote_intf.OUTGOING = true
                             i.INCOMING_STORED = false
                             i.remote_intf.OUTGOING_STORED = false

     Run_Topological_Sort_GADAG(topo, gadag_root):
         Modify_Block_Root_Incoming_Links(topo, gadag_root)
         foreach node x in topo:
             node.unvisited = 0
             foreach interface i of x:
                 if (i.INCOMING):
                     node.unvisited += 1
         Initialize working_list to empty
         Initialize topo_order_list to empty
         add_to_list_end(working_list, gadag_root)
         while working_list is not empty
             y = remove_start_item_from_list(working_list)
             add_to_list_end(topo_order_list, y)
             foreach ordered_interface i of y
                 if intf.OUTGOING
                     i.remote_node.unvisited -= 1
                     if i.remote_node.unvisited is 0
                         add_to_list_end(working_list, i.remote_node)
         next_topo_order = 1
         while topo_order_list is not empty
             y = remove_start_item_from_list(topo_order_list)
             y.topo_order = next_topo_order
             next_topo_order += 1
         Revert_Block_Root_Incoming_Links(topo, gadag_root)

     def Set_Other_Undirected_Links_Based_On_Topo_Order(topo):
         foreach node x in topo
             foreach interface i of x
                 if i.UNDIRECTED:
                     if x.topo_order < i.remote_node.topo_order
                         i.OUTGOING = true
                         i.UNDIRECTED = false
                         i.remote_intf.INCOMING = true
                         i.remote_intf.UNDIRECTED = false
                     else
                         i.INCOMING = true
                         i.UNDIRECTED = false
                         i.remote_intf.OUTGOING = true
                         i.remote_intf.UNDIRECTED = false

     Add_Undirected_Links(topo, gadag_root)
         Add_Undirected_Block_Root_Links(topo, gadag_root)
         Run_Topological_Sort_GADAG(topo, gadag_root)
         Set_Other_Undirected_Links_Based_On_Topo_Order(topo)

     Add_Undirected_Links(topo, gadag_root)

            Figure 18: Assigning direction to UNDIRECTED links

Sent: Monday, June 15, 2015 3:25 AM

Hi Chris,

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Thu, 18 Jun 2015 07:42:54 +0000

Chris,

                I will go through the changes,  it will take some time to verify :)

I found one more things :

             [E]----|
            (5,0)   |
              |     |
              |     |
             [R]   [D]---[C]
            (0,0) (4,0) (3,0)
              |           |
              |           |
             [A]---------[B]
            (1,0)       (2,0)

        In above 6 router topology, there are no ears.
        As per psudocode only GADAG root [R] will be assigned with IN_GADAG flag. A,B,C,D,E will not have the flag IN_GADAG set.

Thanks & Regards
Anil S N

Sent: 18 June 2015 03:58

Anil,

Hi Chris,

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Thu, 18 Jun 2015 07:02:47 +0000

Chris,

             [E]----|
            (5,0)   |
              |     |
              |     |
             [R]   [D]---[C]
            (0,0) (4,0) (3,0)
              |           |
              |           |
             [A]---------[B]
            (1,0)       (2,0)

        In above 6 router topology, there are no ears.
        As per psudocode only GADAG root will be assigned with IN_GADAG flag.

Psudocode in Draft :

              ear_list = empty

              cur_node = intf.remote_node

              cur_intf = intf

              not_done = true

              while not_done

                 cur_intf.UNDIRECTED = false

                 cur_intf.OUTGOING = true

                 cur_intf.remote_intf.UNDIRECTED = false

                 cur_intf.remote_intf.INCOMING = true

                 if cur_node.IN_GADAG is false

                    cur_node.IN_GADAG = true

                    add_to_list_end(ear_list, cur_node)

                    if ear_type is CHILD

                       cur_intf = cur_node.lowpoint_parent_intf

                       cur_node = cur_node.lowpoint_parent

                    else  // ear_type must be NEIGHBOR

                       cur_intf = cur_node.dfs_parent_intf

                       cur_node = cur_node.dfs_parent

                 else

                    not_done = false

                 localroot = x

              else

                 // 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)

             root.IN_GADAG = true

             root.localroot = None

             Initialize Stack to empty

             push root onto Stack

Thanks & Regards
Anil S N

Anil,

Hi Chris,

Thanks & Regards
Anil S N