Subject: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

From: [email-masked]
Date: Thu, 7 Apr 2016 10:24:58 +0800

Hi Chris

There maybe some trivial mistakes in the document, please confirm it.

1) in section "5.2.  MRT Island Identification"
see pseudo-code in Figure 16, the second if-statement "if (not 
intf.remote_node.IN_MRT_ISLAND))" will never meet, the BFS will stop 
abnormally.

2) in section "5.7.5.  Complete Algorithm to Compute MRT Next-Hops"
see pseudo-code in Figure 23, in function 
"SPF_No_Traverse_Block_Root(spf_root, block_root, direction)", 
the code "path_metric = min_node.spf_metric + intf.metric" and the 
following remainder code of this function need to be included in the 
if-statement "if ( ( ((direction is FORWARD) and intf.OUTGOING) or". 

3) in section "5.9.4.  Computing MRT Alternates for Proxy-Nodes"
"Similarly, if run Select_Alternates(X, F, primary_intf) and we find that 
it is safe to USE_BLUE to reach Y"
here the first parameter X would be replaced to Y.

thanks
Deccan

--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail (and any attachment transmitted herewith) is privileged and confidential and is intended for the exclusive use of the addressee(s).  If you are not an intended recipient, any disclosure, reproduction, distribution or other dissemination or use of the information contained is strictly prohibited.  If you have received this mail in error, please delete it and notify us immediately.
--------------------------------------------------------
ZTE Information Security Notice: The information contained in this mail (and any attachment transmitted herewith) is privileged and confidential and is intended for the exclusive use of the addressee(s).  If you are not an intended recipient, any disclosure, reproduction, distribution or other dissemination or use of the information contained is strictly prohibited.  If you have received this mail in error, please delete it and notify us immediately.

---

From: Chris Bowers <[email-masked]>
Date: Wed, 20 Apr 2016 21:04:22 +0000

Deccan,

Thanks for the feedback.

See inline below with [CB].

Chris

From: [email-masked] [mailto:[email-masked]]
Sent: Wednesday, April 06, 2016 9:25 PM
To: Chris Bowers <[email-masked]>
Cc: [email-masked]
Subject: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

Hi Chris

1) in section "5.2.  MRT Island Identification"
see pseudo-code in Figure 16, the second if-statement "if (not intf.remote_node.IN_MRT_ISLAND))" will never meet, the BFS will stop abnormally.
[CB] I think the issue might be convention we are using in the pseudocode of using the indentation to indicate the scope of if, for, and while statements.  We could have chosen to use more explicit scoping like endif, endfor, and endwhile. For this discussion, I rewrote the while loop in figure 16 below using this more explicit scoping.
     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)
              endif
           endif
        endfor
      endwhile
Written in this form, it is easier to see that we are using the last if-statement to avoid adding to the explore_list any nodes that have already been marked as being in the MRT Island, and are already in the explore_list.  If we don't do this, I think the algorithm will not terminate in some topologies.  Did I understand your point correctly?  If not, can you clarify more?

2) in section "5.7.5.  Complete Algorithm to Compute MRT Next-Hops"
see pseudo-code in Figure 23, in function "SPF_No_Traverse_Block_Root(spf_root, block_root, direction)",
the code "path_metric = min_node.spf_metric + intf.metric" and the following remainder code of this function need to be included in the if-statement "if ( ( ((direction is FORWARD) and intf.OUTGOING) or".
[CB]  Thanks for catching this error.  This is a case where using the indentation to indicate scope made this error less obvious.  I will change the indentation of "if ( ( ((direction is FORWARD) and intf.OUTGOING) etc" to correct this.  Do the text below now convey the correct meaning?
   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 == 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)

3) in section "5.9.4.  Computing MRT Alternates for Proxy-Nodes"
"Similarly, if run Select_Alternates(X, F, primary_intf) and we find that it is safe to USE_BLUE to reach Y"
here the first parameter X would be replaced to Y.
[CB]  Thanks. We will correct this as well.

thanks
Deccan

---

From: [email-masked]
Date: Thu, 21 Apr 2016 11:10:31 +0800

Hi Chris 

Thanks for the detailed reply.

See inline below with [Deccan]

Deccan

Chris Bowers <[email-masked]> 
2016-04-21 05:04

收件人
"[email-masked]" <[email-masked]>, 
抄送
"[email-masked]" <[email-masked]>
主题
RE: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

Deccan, 
 
Thanks for the feedback.

Chris

Hi Chris 

1) in section "5.2.  MRT Island Identification" 
see pseudo-code in Figure 16, the second if-statement "if (not 
intf.remote_node.IN_MRT_ISLAND))" will never meet, the BFS will stop 
abnormally. 
[CB] I think the issue might be convention we are using in the pseudocode 
of using the indentation to indicate the scope of if, for, and while 
statements.  We could have chosen to use more explicit scoping like endif, 
endfor, and endwhile. For this discussion, I rewrote the while loop in 
figure 16 below using this more explicit scoping.
     while (explore_list is not empty)
        next_rtr = remove_head(explore_list)
        for each intf in next_rtr
           if (not intf.MRT-ineligible         [Deccan] it is necessary to 
add "not intf.IN_MRT_ISLAND", as the same reason you described.
              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     [Deccan] so, here 
the "intf.remote_node" need to be changed to "intf.remote_intf" 
              if (not intf.remote_node.IN_MRT_ISLAND))
                 intf.remote_node.IN_MRT_ISLAND = TRUE
                 add_to_tail(explore_list, intf.remote_node)
              endif
           endif
        endfor
      endwhile
Written in this form, it is easier to see that we are using the last 
if-statement to avoid adding to the explore_list any nodes that have 
already been marked as being in the MRT Island, and are already in the 
explore_list.  If we don’t do this, I think the algorithm will not 
terminate in some topologies.  Did I understand your point correctly?  If 
not, can you clarify more?

[Deccan]  According to your meaning that if I understand correctly, I put 
the suggestion directly on the above pseudo-code, please see it.

[CB]  Thanks for catching this error.  This is a case where using the 
indentation to indicate scope made this error less obvious.  I will change 
the indentation of “if ( ( ((direction is FORWARD) and intf.OUTGOING) etc
” to correct this.  Do the text below now convey the correct meaning?
[Deccan] yes.

[Deccan]  There maybe another issue in section "5.6.  Augmenting the GADAG 
by directing all links". In function "Run_Topological_Sort_GADAG(topo, 
gadag_root)", because we only first add gadag_root to working_list, but 
not all other cut-vertexes, it is possible that some blocks have no chance 
to get Topological_Sort. For example, see Figure 10 (a), the block 3 which 
contains K, L, M, N, O, P will totally have no chance to  get 
Topological_Sort.  To be specific, since the cut-vertex K's all incoming 
interface have be removed temporarily, note that cut-link H-K is set to 
bidirectional before Run_Topological_Sort_GADAG, K has no chance to be 
visited based on the VISIT_ACTION originated from GADAG root. Although in 
this example all links in block3 have already be directed, we can get 
another example with a complicated block that will need Topological_Sort 
to set undirected links. Please see if it is so.

---

From: Chris Bowers <[email-masked]>
Date: Thu, 21 Apr 2016 21:41:55 +0000

Deccan,

With respect to the pseudo-code for MRT_Island_Identification(), I understand what you are saying.  In fact, the existing Python code has the line
intf.remote_intf.IN_MRT_ISLAND = True
instead of:
intf.remote_node.IN_MRT_ISLAND = True
so I will change the pseudocode to match.

From what I can tell, the additional if-condition "not intf.IN_MRT_ISLAND" is not absolutely required for correctness, but it is more efficient and clearer, so I will update both the pseudo-code and the Python code.

I am still looking into your question about section 5.6 and the topological sort.

Thanks for pointing out these issues.

Chris

From: [email-masked] [mailto:[email-masked]]
Sent: Wednesday, April 20, 2016 10:11 PM
To: Chris Bowers <[email-masked]>
Cc: [email-masked]
Subject: 答复: RE: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

Hi Chris

Deccan

Chris Bowers <[email-masked]<mailto:[email-masked]>>

2016-04-21 05:04

收件人

"[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>,

抄送

"[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>

主题

Deccan,

Thanks for the feedback.

Chris

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]]
Sent: Wednesday, April 06, 2016 9:25 PM
To: Chris Bowers <[email-masked]<mailto:[email-masked]>>
Cc: [email-masked]<mailto:[email-masked]>
Subject: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

Hi Chris

           if (not intf.MRT-ineligible         [Deccan] it is necessary to add "not intf.IN_MRT_ISLAND", as the same reason you described.
              intf.remote_node.IN_MRT_ISLAND = TRUE        [Deccan] so, here the "intf.remote_node" need to be changed to "intf.remote_intf"
Written in this form, it is easier to see that we are using the last if-statement to avoid adding to the explore_list any nodes that have already been marked as being in the MRT Island, and are already in the explore_list.  If we don’t do this, I think the algorithm will not terminate in some topologies.  Did I understand your point correctly?  If not, can you clarify more?

[Deccan]  According to your meaning that if I understand correctly, I put the suggestion directly on the above pseudo-code, please see it.

[CB]  Thanks for catching this error.  This is a case where using the indentation to indicate scope made this error less obvious.  I will change the indentation of “if ( ( ((direction is FORWARD) and intf.OUTGOING) etc” to correct this.  Do the text below now convey the correct meaning?

[Deccan]  There maybe another issue in section "5.6.  Augmenting the GADAG by directing all links". In function "Run_Topological_Sort_GADAG(topo, gadag_root)", because we only first add gadag_root to working_list, but not all other cut-vertexes, it is possible that some blocks have no chance to get Topological_Sort. For example, see Figure 10 (a), the block 3 which contains K, L, M, N, O, P will totally have no chance to  get Topological_Sort.  To be specific, since the cut-vertex K's all incoming interface have be removed temporarily, note that cut-link H-K is set to bidirectional before Run_Topological_Sort_GADAG, K has no chance to be visited based on the VISIT_ACTION originated from GADAG root. Although in this example all links in block3 have already be directed, we can get another example with a complicated block that will need Topological_Sort to set undirected links. Please see if it is so.

---

From: Chris Bowers <[email-masked]>
Date: Thu, 21 Apr 2016 23:11:22 +0000

Deccan,

Responding to this question:
====================
[Deccan]  There maybe another issue in section "5.6.  Augmenting the GADAG by directing all links". In function "Run_Topological_Sort_GADAG(topo, gadag_root)", because we only first add gadag_root to working_list, but not all other cut-vertexes, it is possible that some blocks have no chance to get Topological_Sort. For example, see Figure 10 (a), the block 3 which contains K, L, M, N, O, P will totally have no chance to  get Topological_Sort.  To be specific, since the cut-vertex K's all incoming interface have be removed temporarily, note that cut-link H-K is set to bidirectional before Run_Topological_Sort_GADAG, K has no chance to be visited based on the VISIT_ACTION originated from GADAG root. Although in this example all links in block3 have already be directed, we can get another example with a complicated block that will need Topological_Sort to set undirected links. Please see if it is so.
===========================

I think the key to understanding why the current pseudo-code and Python code works is the following sentence:
“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.”
In figure 10a, for block 4 containing H and K, H is the block root (since R is the GADAG root).  So we need Modify_Block_Root_Incoming_Links() to temporarily remove the link INCOMING to H from K.  That still leaves the link OUTGOING from H to K unmodified.   The OUTGOING direction is not modified because K is not the root of block 4 (even though it is the root of block 3).  The OUTGOING link from H to K is how Run_Topological_Sort_GADAG() will reach K and the rest of block 3.

Modify_Block_Root_Incoming_Links() only makes the direction from K to H temporarily unusable, because of the condition:

if i.remote_node.localroot is x

H is the localroot of K, but K is NOT the localroot of H.

You might also try stepping through the basic_topo example in mrt_lowpoint_draft_text.py:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/tree/master/src

You can insert print statements to see what is happening, which is what I did to look at the behavior of the code to answer this question.

It is possible that there is another topology that breaks this, so it would help to give me a specific topology that doesn’t work if you find one.

Thanks,
Chris

Hi Chris

Deccan

2016-04-21 05:04

收件人

抄送

主题

Deccan,

Thanks for the feedback.

Chris

Hi Chris

---

From: [email-masked]
Date: Fri, 22 Apr 2016 11:40:57 +0800

Chris

You are right.

thanks,
Deccan

2016-04-22 07:11

收件人
"[email-masked]" <[email-masked]>, 
抄送
"[email-masked]" <[email-masked]>
主题
RE: RE: some issues in draft-ietf-rtgwg-mrt-frr-algorithm-09

Deccan,

I think the key to understanding why the current pseudo-code and Python 
code works is the following sentence:
“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.”
In figure 10a, for block 4 containing H and K, H is the block root (since 
R is the GADAG root).  So we need Modify_Block_Root_Incoming_Links() to 
temporarily remove the link INCOMING to H from K.  That still leaves the 
link OUTGOING from H to K unmodified.   The OUTGOING direction is not 
modified because K is not the root of block 4 (even though it is the root 
of block 3).  The OUTGOING link from H to K is how 
Run_Topological_Sort_GADAG() will reach K and the rest of block 3. 
 
Modify_Block_Root_Incoming_Links() only makes the direction from K to H 
temporarily unusable, because of the condition:
if i.remote_node.localroot is x
H is the localroot of K, but K is NOT the localroot of H. 
 
You might also try stepping through the basic_topo example in 
mrt_lowpoint_draft_text.py:
https://github.com/cbowers/draft-ietf-rtgwg-mrt-frr-algorithm/tree/master/src
 
You can insert print statements to see what is happening, which is what I 
did to look at the behavior of the code to answer this question. 
 
It is possible that there is another topology that breaks this, so it 
would help to give me a specific topology that doesn’t work if you find 
one.
 
Thanks,
Chris

Hi Chris 

Deccan

收件人

Deccan, 
  
Thanks for the feedback. 

Chris 

Hi Chris 

              intf.remote_node.IN_MRT_ISLAND = TRUE        [Deccan] so, 
here the "intf.remote_node" need to be changed to "intf.remote_intf"