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

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Sun, 21 Jun 2015 13:06:50 +0000

HI Authors,

Comment 1:
In below topology if [R] is the local root of the topology, Block id of R is 0 and Block ID of all other nodes in the topology as per psudo-code, I feel it should be 0/1 for all.
When Assign_Block_ID is invoked, root gets the blockid 0, then since first DFS child local root is GADAG root block id is incremented to 1 and assigned, for all other DFS child block-id
Is assigned without incrementing it gets the value 1.

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

global_var: max_block_id

                 Assign_Block_ID(x, cur_block_id)
                   x.block_id = cur_block_id
                   foreach DFS child c of x
                      if (c.local_root is x)
                         max_block_id += 1
                         Assign_Block_ID(c, max_block_id)
                      else
                        Assign_Block_ID(c, cur_block_id)

                 max_block_id = 0
                 Assign_Block_ID(gadag_root, max_block_id)

Comment 2:  "This is necessary for the DFS in
   Lowpoint_Visit above, where the selection order of the interfaces to
   explore results in different trees."

This sentence can be changed,
"This is necessary for the DFS in  Lowpoint_Visit  as per section 4.3. , where the
selection order of the interfaces to explore results in different trees."

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 above, 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.

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: Sun, 21 Jun 2015 21:38:06 +0000

Anil,

Thanks.  With respect to comment 1, I think your description is the expected behavior for block-ids.  The localroot for a given block will not have the same block-id as the rest of the nodes in the block.  This is taken into account in In_Common_Block() which not only compares block-ids, but also checks if either node is the localroot for the other node.  It was not initially obvious to me why it was done this way, but if you think about a topology where a given node is the localroot for two different blocks, it makes sense that the localroot can't share the same block-id with both blocks.  Therefore, the simplest thing is to have the localroot not share the block-id with either of the blocks.

I incorporated comment 2 in the github commit at:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/commit/b5d1fe5354d44e9416f27b0fac1f99a66e54a79c

Chris

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

HI Authors,

Comment 1:

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

global_var: max_block_id

                 max_block_id = 0

5.1.  Interface Ordering

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Mon, 22 Jun 2015 05:23:14 +0000

Chris,

                It makes sense, thanks.

Thanks & Regards
Anil S N

From: Chris Bowers [mailto:[email-masked]]
Sent: 22 June 2015 03:08
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: Anil Kumar S N (VRP Network BL) [mailto:[email-masked]]
Sent: Sunday, June 21, 2015 8:07 AM
To: Chris Bowers; 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: [rtgwg] draft-ietf-rtgwg-mrt-frr-algorithm-03

HI Authors,

Comment 1:

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

global_var: max_block_id

                 max_block_id = 0

5.1.  Interface Ordering

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Tue, 23 Jun 2015 11:03:50 +0000

Hi Chirs,

gadag_root.localroot will remain as  None at the end of algorithm and gadag_root.block_id will be 0 (rest of the nodes in the block will be 1 higher than gadag_root.block_id)
Below psudocode will return false while comparing a node in a block and gadag_root.

                Please correct me if I am wrong.

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

Thanks & Regards
Anil S N

Anil,

Chris

HI Authors,

Comment 1:

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

global_var: max_block_id

                 max_block_id = 0

5.1.  Interface Ordering

Thanks & Regards
Anil S N

---

From: Chris Bowers <[email-masked]>
Date: Tue, 23 Jun 2015 14:48:39 +0000

Anil,

Reusing the topology below, R (the gadag_root) will have block_id=0 while A,B,C,D and E will have block_id=1. so the first OR'd condition in In_Common_Block(R,y) will always be false when determining if R is in the same block as A,B,C,D, or E.  The third OR'd condition will also be false because R.localroot = None.  However, the second OR'd condition will be true because R = B.localroot (for example), returning true for In_Common_Block(R,B). Does this make sense?

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

Sent: Tuesday, June 23, 2015 6:04 AM

Hi Chirs,

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Tue, 23 Jun 2015 15:59:14 +0000

Chris,

                Yes it definitely makes sense,  thanks I should have thought about this.

Thanks & Regards
Anil S N

Sent: 23 June 2015 20:19

Anil,

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

Hi Chirs,

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: "Anil Kumar S N (VRP Network BL)" <[email-masked]>
Date: Thu, 25 Jun 2015 12:53:40 +0000

Chris,

                Store_Results should be called after nexthop is updated, The last node processed and its nexthop is not updated I feel.
I might be wrong, Please correct me if I am wrong.

Base :

SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
   Initialize spf_heap to empty
   Initialize nodes' spf_metric to infinity and next_hops to empty
   spf_root.spf_metric = 0
   insert(spf_heap, spf_root)
   while (spf_heap is not empty)
       min_node = remove_lowest(spf_heap)
       Store_Results(min_node, direction)
       if ((min_node is spf_root) or (min_node is not block_root))
          foreach interface intf of min_node
                if ( ( ((direction is FORWARD) and intf.OUTGOING) or
                       ((direction is REVERSE) and intf.INCOMING) )
                       and In_Common_Block(spf_root, intf.remote_node) )
                path_metric = min_node.spf_metric + intf.metric
                if path_metric < intf.remote_node.spf_metric
                   intf.remote_node.spf_metric = path_metric
                   if min_node is spf_root
                     intf.remote_node.next_hops = make_list(intf)
                   else
                     intf.remote_node.next_hops = min_node.next_hops
                   insert_or_update(spf_heap, intf.remote_node)
                else if path_metric is intf.remote_node.spf_metric
                   if min_node is spf_root
                      add_to_list(intf.remote_node.next_hops, intf)
                   else
                      add_list_to_list(intf.remote_node.next_hops,
                                       min_node.next_hops)

Modified :

SPF_No_Traverse_Block_Root(spf_root, block_root, direction)
   Initialize spf_heap to empty
   Initialize nodes' spf_metric to infinity and next_hops to empty
   spf_root.spf_metric = 0
   insert(spf_heap, spf_root)
   while (spf_heap is not empty)
       min_node = remove_lowest(spf_heap)
       Store_Results(min_node, direction)
       if ((min_node is spf_root) or (min_node is not block_root))
          foreach interface intf of min_node
                if ( ( ((direction is FORWARD) and intf.OUTGOING) or
                       ((direction is REVERSE) and intf.INCOMING) )
                       and In_Common_Block(spf_root, intf.remote_node) )
                path_metric = min_node.spf_metric + intf.metric
                if path_metric < intf.remote_node.spf_metric
                   intf.remote_node.spf_metric = path_metric
                   if min_node is spf_root
                     intf.remote_node.next_hops = make_list(intf)
                   else
                     intf.remote_node.next_hops = min_node.next_hops
                   insert_or_update(spf_heap, intf.remote_node)
                else if path_metric is intf.remote_node.spf_metric
                   if min_node is spf_root
                      add_to_list(intf.remote_node.next_hops, intf)
                   else
                      add_list_to_list(intf.remote_node.next_hops,
                                       min_node.next_hops)
       Store_Results(min_node, direction)

Thanks & Regards
Anil S N

From: Anil Kumar S N (VRP Network BL)
Sent: 23 June 2015 21:29
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

Chris,

Thanks & Regards
Anil S N

From: Chris Bowers [mailto:[email-masked]]
Sent: 23 June 2015 20:19
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
             [E]----|
            (5,0)   |
              |     |
              |     |
             [R]   [D]---[C]
            (0,0) (4,0) (3,0)
              |           |
              |           |
             [A]---------[B]
            (1,0)       (2,0)

Hi Chirs,

In_Common_Block(x, y)

Thanks & Regards
Anil S N

---

From: Chris Bowers <[email-masked]>
Date: Fri, 26 Jun 2015 01:49:59 +0000

Anil,

I think the pseudocode will work correctly as currently written.   It is safe to store the next-hops for spf_root to reach min_node immediately after removing min_node, the heap element with the lowest value of spf_metric, from spf_heap.  The reasoning is described below.

spf_heap starts out with just spf_root in it, and spf_root gets removed the first time that the line min_node = remove_lowest(spf_heap) is hit.  So now spf_heap is empty and the only way that a node gets put into spf_heap is with the line: insert_or_update(spf_heap, intf.remote_node).  Immediately before this line, intf.remote_node.next_hops are either created based on intf, or inherited from min_node.  Either way, a given node G can't get into spf_heap without having its next_hops value set to some value.  The G.next_hops are the interfaces on spf_root to reach G on the shortest path yet explored.  As the SPF algorithm runs, the value of G.next_hops can be changed, either as a new shortest path is explored, or as an equal cost path is explored.

When it comes time to remove G from spf_heap (via min_node = remove_lowest(spf_heap) ), G has the lowest spf_metric of any node remaining on the heap.  There is no chance that any paths explored in the SPF algorithm after G is removed from the heap will result in changing G.next_hops because any such path would necessarily have an spf_metric higher than G.spf_metric.  Therefore, it is safe to call Store_Results(G, direction) after G is removed from spf_heap, because G.next_hops won't get changed anymore.

The last node on spf_heap (the one with the highest value of spf_metric in the topology) will get removed and Store_Results will get called, so last node will be completely processed.  The algorithm will go through the motions of exploring all of the interfaces of last node, but it won't result in any new remote nodes being added to spf_heap.  So "while (spf_heap is not empty)" will terminate the next time around.

I hope this makes sense.

Chris

From: Anil Kumar S N (VRP Network BL) [mailto:[email-masked]]
Sent: Thursday, June 25, 2015 7:54 AM
To: Anil Kumar S N (VRP Network BL); 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

Chris,

Base :

Modified :

Thanks & Regards
Anil S N

From: Anil Kumar S N (VRP Network BL)
Sent: 23 June 2015 21:29
To: 'Chris Bowers'; 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

Chris,

Thanks & Regards
Anil S N

Anil,

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

Hi Chirs,

In_Common_Block(x, y)

Thanks & Regards
Anil S N