Subject: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

From: "Alvaro Retana (aretana)" <[email-masked]>
Date: Tue, 8 Oct 2013 18:23:09 +0000

On 9/27/13 8:53 AM, "Alvaro Retana (aretana)" <[email-masked]<mailto:[email-masked]>> wrote:

Hi!

Thanks to all who have replied to this call!

However, I think I probably wasn't clear when I wrote:

We want to hear from people who have read and understood the draft (besides the authors!) about this topic.  Please provide some explanation as to why you support or not the adoption of the draft — avoid "+1".

As you express your support (or not) for the draft, please explain why you are supporting it (or not).

In the original message I explained how not many people who attended the meeting in Berlin seemed to have reviewed the draft to be able to gather any type of indication of support (or not) at the time.  That is one of the reasons why we want to gather information beyond just "support" (or not).  Another reason is that since the original publication of the draft I haven't been able to find comments on the list about it.

http://www.ietf.org/mail-archive/web/rtgwg/current/msg03435.html

Maybe lots of people have provided comments directly to the authors, which is great!  But for the rest of us is not clear.

Thanks!

Alvaro.

---

From: Jeff Tantsura <[email-masked]>
Date: Tue, 8 Oct 2013 18:54:40 +0000

Hi Alvaro,

I support adoption of the draft as it provides base for number of solutions we (rtgwg) have been building using mrt.

Cheers,
Jeff

From: Alvaro Retana <[email-masked]<mailto:[email-masked]>>
Date: Tuesday, October 8, 2013 11:23 AM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

Hi!

Thanks!

Alvaro.

---

From: Acee Lindem <[email-masked]>
Date: Tue, 8 Oct 2013 19:40:37 +0000

I support adoption since MRT appears to provide optimal coverage w/o as much overhead as other technologies. Also, the first MRT algorithm (draft-enyedi-rtgwg-mrt-frr-algorithm-03) is much better specified than the competing mechanisms.
Thanks,
Acee

On Oct 8, 2013, at 2:54 PM, Jeff Tantsura wrote:

Hi Alvaro,

Cheers,
Jeff

Hi!

Thanks!

Alvaro.

---

From: Lizhenbin <[email-masked]>
Date: Wed, 9 Oct 2013 03:29:48 +0000

Hi Alvaro,

I support adoption of the draft based on following reasons:
1. The algorithm implementation based on the draft has been done by us. It can work well. We think the authors have done a wide research and analysis work on the algorithm to make it mature enough.
2. The LDP-MT-based MRT FRR solutions using the algorithm have been building. We believe it is a scalable solution to provide 100% coverage for FRR.

Regards,
Robin

发件人: [email-masked] [mailto:[email-masked]] 代表 Alvaro Retana (aretana)
发送时间: 2013年10月9日 2:23
收件人: [email-masked]
主题: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

Hi!

We want to hear from people who have read and understood the draft (besides the authors!) about this topic.  Please provide some explanation as to why you support or not the adoption of the draft ― avoid "+1".

Thanks!

Alvaro.

---

From: IJsbrand Wijnands <[email-masked]>
Date: Wed, 9 Oct 2013 12:31:04 +0200

Dear WG,

From a multicast POV I support this work to be adopted. Being able to build two non-intersection paths through a single plane network is very useful for Multicast live-live and MoFRR deployments. It solves a real problem which we see in today's networks.

A more challenging question to answer is how draft-enyedi-rtgwg-mrt-frr-algorithm relates to draft-thubert-rtgwg-arc-00 and draft-thubert-rtgwg-arc-bicast-00. I don't know if both can move forward individually or if some merge is possible. It would be good if the authors get together and discuss this.

Thx,

Ice.

On 27 Sep 2013, at 14:53, Alvaro Retana (aretana) <[email-masked]> wrote:

> Hi!
> 
> This message starts a two-week Call for WG Adoption for 'Algorithms for computing Maximally Redundant Trees for IP/LDP Fast-Reroute' (draft-enyedi-rtgwg-mrt-frr-algorithm).
> 
> http://tools.ietf.org/html/draft-enyedi-rtgwg-mrt-frr-algorithm
> 
> At the meeting in Berlin the authors asked for the WG adoption of their draft, but here were very few people in the room who had actually reviewed the document to get any type of read of the room.  
> 
> This call will be over by EOD on Oct/11, 2013 (pick your favorite time zone).
> 
> Thanks!!
> 
> Alvaro.
> _______________________________________________
> rtgwg mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rtgwg

---

From: Gábor Sándor Enyedi <[email-masked]>
Date: Wed, 9 Oct 2013 14:25:20 +0000

Hi,

Please keep in mind that even if MRT and ARC are both using the "ear-decomposition", they are using it in a different way. Some merging/common work may be possible, but I don't feel the common points too strong now. Maybe we should speak about this in Vancouver.

Gabor

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of IJsbrand Wijnands
Sent: Wednesday, October 09, 2013 12:31 PM
To: Alvaro Retana
Cc: [email-masked]
Subject: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

Dear WG,

Thx,

Ice.

On 27 Sep 2013, at 14:53, Alvaro Retana (aretana) <[email-masked]> wrote:

> We want to hear from people who have read and understood the draft (besides the authors!) about this topic.  Please provide some explanation as to why you support or not the adoption of the draft - avoid "+1".
>

---

From: Alia Atlas <[email-masked]>
Date: Wed, 9 Oct 2013 10:29:10 -0400

(WG-chair hat off)

I agree.  I haven't seen any work on the ARC drafts in the last year.  I
don't see the work needed to take an algorithm into the functioning MRT
architecture.  Remember that it's taken a good amount of time to flesh out
all the details for MRT.

Alia

On Wed, Oct 9, 2013 at 10:25 AM, Gábor Sándor Enyedi <
[email-masked]> wrote:

> Hi,
>
> Please keep in mind that even if MRT and ARC are both using the
> "ear-decomposition", they are using it in a different way. Some
> merging/common work may be possible, but I don't feel the common points too
> strong now. Maybe we should speak about this in Vancouver.
>
> Gabor
>
> From a multicast POV I support this work to be adopted. Being able to
> build two non-intersection paths through a single plane network is very
> useful for Multicast live-live and MoFRR deployments. It solves a real
> problem which we see in today's networks.
>
> A more challenging question to answer is how
> draft-enyedi-rtgwg-mrt-frr-algorithm relates to draft-thubert-rtgwg-arc-00
> and draft-thubert-rtgwg-arc-bicast-00. I don't know if both can move
> forward individually or if some merge is possible. It would be good if the
> authors get together and discuss this.
>
> Thx,
>
> Ice.
>
> > This message starts a two-week Call for WG Adoption for 'Algorithms for
> computing Maximally Redundant Trees for IP/LDP Fast-Reroute'
> (draft-enyedi-rtgwg-mrt-frr-algorithm).
> >
> > At the meeting in Berlin the authors asked for the WG adoption of their
> draft, but here were very few people in the room who had actually reviewed
> the document to get any type of read of the room.
> >
> > We want to hear from people who have read and understood the draft
> (besides the authors!) about this topic.  Please provide some explanation
> as to why you support or not the adoption of the draft - avoid "+1".
> >

---

From: Jeff Tantsura <[email-masked]>
Date: Wed, 9 Oct 2013 14:33:25 +0000

Agree with both comments.

Cheers,
Jeff

From: Alia Atlas <[email-masked]<mailto:[email-masked]>>
Date: Wednesday, October 9, 2013 7:29 AM
To: Gábor Sándor Enyedi <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

(WG-chair hat off)

I agree.  I haven't seen any work on the ARC drafts in the last year.  I don't see the work needed to take an algorithm into the functioning MRT architecture.  Remember that it's taken a good amount of time to flesh out all the details for MRT.

Alia

On Wed, Oct 9, 2013 at 10:25 AM, Gábor Sándor Enyedi <[email-masked]<mailto:[email-masked]>> wrote:
Hi,

Gabor

-----Original Message-----
From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of IJsbrand Wijnands
Sent: Wednesday, October 09, 2013 12:31 PM
To: Alvaro Retana
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: WG Adoption of MRT Algorithms Draft (draft-enyedi-rtgwg-mrt-frr-algorithm)

Dear WG,

Thx,

Ice.

On 27 Sep 2013, at 14:53, Alvaro Retana (aretana) <[email-masked]<mailto:[email-masked]>> wrote:

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

_______________________________________________
rtgwg mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/rtgwg
_______________________________________________
rtgwg mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/rtgwg

---

From: "Alvaro Retana (aretana)" <[email-masked]>
Date: Wed, 9 Oct 2013 18:49:48 +0000

<WG Chair Hat Off>

Hi!

I reviewed the draft and put some comments below.  In general, I think the draft is well written and surprisingly (given the potential complexity of the topic) relatively easy to follow..but not in one sitting!

I do need the authors to clarify one thing before I "cast my vote" about adoption: it's Intended Status.  The draft has an intended status of Informational.  However, the Introduction reads:  "This document defines the MRT Lowpoint algorithm to be used as a standard in the default MRT profile for MRT-FRR."  Which one is it?

IMHO, there's a significant difference in saying "this is an algorithm than can be used" (informational) vs "this is the algorithm that MUST be used" (standard).  For the record, I have no issues with adopting this draft with an intended status of Informational.

Thanks!

Alvaro.

Major Issues:

  1.  The draft has an intended status of Informational.  However, the Introduction reads:  "This document defines the MRT Lowpoint algorithm to be used as a standard in the default MRT profile for MRT-FRR."  I would like to see a clarification on what the intended status is.
  2.  I found it interesting that, even though the document is defining an algorithm that when implemented will need to have consistency across nodes, there was no reference to RFC2119 — but some of the words were capitalized anyway. Even then, only 4 "MUST" and 1 "SHOULD" appeared.  I realize that the count of MUST/SHOULD is no indication of anything, but it doesn't feel right for a 40+ page document.  I would appreciate if the authors would not just add the 2119 reference (nit), but if they would also comb the text for parts where a little more normative direction might help (which doesn't necessarily translate into MUSTs).  For example (all the text is from Section 4 (Algorithm Sections)):
     *    "The different parts of this algorithm are described below.  These work on a network graph after, for instance, its interfaces are ordered as per Figure 14."  It sounds as if Figure 14 is optional or maybe ordering the interfaces is not mandatory..   Later it is clarified: "To ensure consistency in computation, all routers MUST order interfaces identically. . . The required ordering . . . Is given in Figure 14."  But the first read sounds not normative enough to me.
     *   Figure 14 is not deterministic.  The text says that the order doesn't matter in some cases, but then offers an example of a potential tie-breaker.
     *   Root Selection.  No algorithm is provided. There's a reference to I-D.atlas-ospf-mrt, where a suggestion is made ("..the router with the highest GADAG Root Selection Priority is picked to be the GADAG Root").  IMHO, the algorithm should be specified in this draft, where the requirement to carry the Priority is defined so that the extensions draft(s) can show how to implement it in OSPF (or any other protocol)..not the other way around.
     *   "Initially, all interfaces must be initialized to UNDIRECTED."   Should that be "MUST"?
     *   "It is possible that some links and nodes will be marked as unusable.."  Same comment as the one above for the root selection:  this draft should define the requirements ("Due to operational or other issues, the capability to xxx SHOULD....") so that other docs (like I-D.atlas-ospf-mrt) can then implement the extensions..  The text right now says: "because OSPF can mark links as unusable then we'll do this.."
     *   "There are two methods to find ears; both are required."   REQUIRED?
  3.  Algorithm Alternatives and Evaluation.  There are a couple of alternatives described in the appendices, but there is no evaluation as to why the Lowpoint Algorithm is better.  In fact, the text seems to read as if the appendices describe options to the main algorithm (?) -- begging the question, are there instances where these options would/could be used?

Minor Issues:

  1.  Some important terms are not properly defined, or at least not defined in Section 2.
     *   "cut-edge"  The term is not defined in Section 2.  Later in the document it is described as "The algorithm identifies cut-edges simply as links where both ends of the link are cut-vertices.", which is the definition for cut-link.  It looks like cut-edges is used more through out.
     *   "MRT Island"  I know it is defined in the architecture draft.  It would be nice to carry the definition over to Section 2.
     *   "UNDIRECTED/OUTGOING/INCOMING"  These are used in the algorithm in various points, but are not really defined as to
  2.  I think that the algorithm in Figure 6 is not right — of course, I may be misunderstanding it.  When talking about the endpoints of the ear (X and Y) it says "if Y is root"..but a couple of paragraphs above the text reads: "Once a partial ADAG is already present, we can always add ears to it: just select a non-ready neighbor N of a ready node Q, such that Q is not the root.."  It then sounds like the starting point can't be the root..
  3.  The explanation of the motivation of the low-point values (after Figure 9) needs either better examples or a better explanation — or maybe I got lost.  You first start explaining about when 'L(c) >= D(x)', but the example mentions the 'L(x) < D(x)' case.  An example for the second reason would be nice.
  4.  Algorithm Evaluation.  While it is interesting to see MRT compared to rLFA, it would be much more interesting to see it compared to the options in the appendices or to ARC.  I would move the comparison to rLFA to an appendix.

Nits:

  1.  Section 2.  "standard pseudo-node representation"  Reference?
  2.  Section 2; in the definition of MRT-Red and MRT-Blue:  s/described/describe
  3.  Section 2; ADAG definition: "whith"  ??
  4.  "strictly greater/lower"  These  terms are used in a couple of places, but the << or >> notation is used most of the time.  It would be nice to be consistent to avoid confusion.
  5.  Section 3.2: "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 already in the ADAG."   Too many "already".
  6.  It would be nice to include "partial ADAG" in the definitions section.  Yes, it is defined elsewhere, but a central place is nice in case you forget. ;-)
  7.  I know sometimes it's hard, but please try to format the text so that the figures are not split between pages.
  8.  Section 3.4, after Figure 10. "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 one in block 2 with C as a root, and finally, we need the last one in block 1 with R as a root."  When talking about blocks 1 and 2, you really mean a pair to RTs (just like in block 3), not just "one", right?
  9.  Section 3.5: "The method for local-root computation is used in the MRT Lowpoint algorithm for computing a GADAG using Low-Point inheritance and the essence of it is given in Figure 12."  s/is used/used  and s/inheritance and/inheritance, and   To improve readability.
  10. There are a couple of out of date references.

---

From: Alia Atlas <[email-masked]>
Date: Wed, 9 Oct 2013 17:06:06 -0400

<WG Chair Hat Off also>

Hi Alvaro,

Some responses in-line.

Thanks for taking the time to give a good review.

Alia

On Wed, Oct 9, 2013 at 2:49 PM, Alvaro Retana (aretana)
<[email-masked]>wrote:

>  On 9/27/13 8:53 AM, "Alvaro Retana (aretana)" <[email-masked]> wrote:
>
> as to why you support or not the adoption of the draft — avoid "+1".
>
>
>  <WG Chair Hat Off>
>
>  Hi!
>
>  I reviewed the draft and put some comments below.  In general, I think
> the draft is well written and surprisingly (given the potential complexity
> of the topic) relatively easy to follow..but not in one sitting!
>

[Alia] It does take a couple reads to sink in.  If you have suggestions on
how to improve it, please do send them along.  We've tried to make it as
readable as possible - but after being heads-down in it for a while, it's
hard to get that perspective.

> I do need the authors to clarify one thing before I "cast my vote" about
> adoption: it's Intended Status.  The draft has an intended status of
> Informational.  However, the Introduction reads:  "This document defines
> the MRT Lowpoint algorithm to be used as a standard in the default MRT
> profile for MRT-FRR."  Which one is it?
>

[Alia] I think that the algorithm draft needs to be standards track.  I
apologize for not updating the intended status - I was focused on the
contents.

 IMHO, there's a significant difference in saying "this is an algorithm
> than can be used" (informational) vs "this is the algorithm that MUST be
> used" (standard).  For the record, I have no issues with adopting this
> draft with an intended status of Informational.
>

[Alia] The intent is to have signaling that says this is the algorithm
being used. There's capabilities to indicate different algorithms - but I
do think that this particular algorithm and details must be standards-track
for interoperability.

 Thanks!
>
>  Alvaro.
>
>
>  Major Issues:
>
>    1. The draft has an intended status of Informational.  However, the
>    Introduction reads:  "This document defines the MRT Lowpoint algorithm
>    to be used as a standard in the default MRT profile for MRT-FRR."  I
>    would like to see a clarification on what the intended status is.
>
> [Alia] Agreed - it should be Standards Track and I'll update the next
version.

>
>    1. I found it interesting that, even though the document is defining
>    an algorithm that when implemented will need to have consistency across
>    nodes, there was no reference to RFC2119 — but some of the words were
>    capitalized anyway. Even then, only 4 "MUST" and 1 "SHOULD" appeared.  I
>    realize that the count of MUST/SHOULD is no indication of anything, but it
>    doesn't feel right for a 40+ page document.  I would appreciate if the
>    authors would not just add the 2119 reference (nit), but if they would also
>    comb the text for parts where a little more normative direction might help
>    (which doesn't necessarily translate into MUSTs).
>
> [Alia] Agreed - in general, what I intend to do is to have the explanatory
text that explains the logic of the algorithm and how it works much as it
is - and then to pull together the different parts of the pseudo-code into
a fully detailed algorithm (some by reference to the earlier parts) that
indicates the MUST/SHOULD aspects.   The specific request though seems more
to be to take a careful read through and clarify what is MUST and what is
SHOULD.

>
>    1.   For example (all the text is from Section 4 (Algorithm Sections)):
>       -  "The different parts of this algorithm are described below.
>        These work on a network graph after, for instance, its interfaces
>       are ordered as per Figure 14."  It sounds as if Figure 14 is optional or
>       maybe ordering the interfaces is not mandatory..   Later it is clarified:
>       "To ensure consistency in computation, all routers MUST order interfaces
>       identically. . . The required ordering . . . Is given in Figure 14."  But
>       the first read sounds not normative enough to me.
>
> [Alia] Sure - I can clarify that one.

>
>    1.
>       - Figure 14 is not deterministic.  The text says that the order
>       doesn't matter in some cases, but then offers an example of a potential
>       tie-breaker.
>
> [Alia] Yes - which parallel link is used doesn't matter.  That is a point
to clarify - probably by breaking the function into the normative and
optional parts.  It's useful to have an interface-ordering function that
always returns a result for use in data-structures and calling functions.

>
>    1.
>       - Root Selection.  No algorithm is provided. There's a reference to
>       I-D.atlas-ospf-mrt, where a suggestion is made ("..the router with the
>       highest GADAG Root Selection Priority is picked to be the GADAG Root").
>        IMHO, the algorithm should be specified in this draft, where the
>       requirement to carry the Priority is defined so that the extensions
>       draft(s) can show how to implement it in OSPF (or any other protocol)..not
>       the other way around.
>
> [Alia] The Root Selection is described in
draft-ietf-rtgwg-mrt-frr-architecture in Sec 7 as
'"GADAG Root Selection Priority: Among the routers in the MRT Island and
with the highest priority advertised, an implementation MUST  pick the
router with the highest Router ID to be the GADAG root."

>
>    1.
>       - "Initially, all interfaces must be initialized to UNDIRECTED."
>       Should that be "MUST"?
>       - "It is possible that some links and nodes will be marked as
>       unusable.."  Same comment as the one above for the root selection:  this
>       draft should define the requirements ("Due to operational or other issues,
>       the capability to xxx SHOULD....") so that other docs (like
>       I-D.atlas-ospf-mrt) can then implement the extensions..  The text right now
>       says: "because OSPF can mark links as unusable then we'll do this.."
>
> [Alia] ?? The desire to be able to mark links as unusable comes out of the
manageability draft and basic requirements.  The general requirements are
defined in the draft-ietf-rtgwg-mrt-frr-architecture - but you are right
that this is only indirectly mentioned by

" For any MRT profile, the MRT Island is created by starting from the computing
router. If the computing router supports the default MRT profile, add it to
the MRT Island. Add a router to the MRT Island if the router supports the
default MRT profile and is connected to th  MRT Island via bidirectional
links eligible for MRT."

>
>    1.
>       - "There are two methods to find ears; both are required."
>       REQUIRED?
>
> [Alia] Yes - both are part of  the algorithm.  In explanatory text, I
don't think it needs normative language.  That can/should be given with a
reference to the pseudo-code.

>
>    1. Algorithm Alternatives and Evaluation.  There are a couple of
>    alternatives described in the appendices, but there is no evaluation as to
>    why the Lowpoint Algorithm is better.  In fact, the text seems to read as
>    if the appendices describe options to the main algorithm (?) -- begging the
>    question, are there instances where these options would/could be used?
>
> [Alia] True - in our initial evaluations, we didn't find significant
differences in the path lengths for the alternates.  Chris Bowers can
comment on that a bit.  I thought that I'd cleaned up the text in the main
draft to clarify that the lowpoint algorithm - which has much less
computation - is preferable.  Can you point to where the algorithms in the
appendices are considered equivalent?  I will, of course, take another read
through as well - trying to reduce that issue.

 Minor Issues:
>       - "cut-edge"  The term is not defined in Section 2.  Later in the
>       document it is described as "The algorithm identifies cut-edges simply as
>       links where both ends of the link are cut-vertices.", which is the
>       definition for cut-link.  It looks like cut-edges is used more through out.
>
> [Alia] cut-edge and cut-link are the same thing.  If we've got
inconsistent terminology, I'll fix it.  Vertex/edge come from graph theory
while we talk about nodes and links.

>
>    1.
>       - "MRT Island"  I know it is defined in the architecture draft.  It
>       would be nice to carry the definition over to Section 2.
>
> [Alia] OK

>
>    1.
>       - "UNDIRECTED/OUTGOING/INCOMING"  These are used in the algorithm
>       in various points, but are not really defined as to
>
> [Alia]  umm, how would you define them beyond their obvious meaning?
 Outgoing is from the interface's router to the remote end.   Incoming is
from the remote router to the interface's router.

>
>    1.
>    2. I think that the algorithm in Figure 6 is not right — of course, I
>    may be misunderstanding it.  When talking about the endpoints of the ear (X
>    and Y) it says "if Y is root"..but a couple of paragraphs above the text
>    reads: "Once a partial ADAG is already present, we can always add ears to
>    it: just select a non-ready neighbor N of a ready node Q, such that Q
>    is not the root.."  It then sounds like the starting point can't be the
>    root..
>
> [Alia] I believe this is a misunderstanding.  The description of how an
ear can be added is basically a proof that one can always add a new node
into the ADAG (in a 2-connected graph) by starting from a neighbor N  of a
node Q  that isn't the root.  Then an SPF with Q removed can be done to
find a path from Q to the root.   The reason that Q can't be the root is
just b/c Q is removed from the graph.  Figure 6 accurately describes the
high-level algorithm.  An ear will have 2 ends.  If the ear were found via
an SPF to the root R and didn't intersect any other nodes already in the
ADAG, then that ear would have two ends that are Q and R.

>
>    1. The explanation of the motivation of the low-point values (after
>    Figure 9) needs either better examples or a better explanation — or maybe I
>    got lost.  You first start explaining about when 'L(c) >= D(x)', but the
>    example mentions the 'L(x) < D(x)' case.  An example for the second reason
>    would be nice.
>
> [Alia]  I am not yet sure where you got lost or how I could thus improve
the explanation.  There are two points that we tried to make.   First, if
the L(c) >= D(x) then the child c (and its descendents) have no paths to an
ancestor of the parent x except via that parent x.  Thus x is a cut-vertex.
  The point with L(c) < D(x) (typo of L(x) ) is to describe a special case
where x is a cut-vertex and has multiple DFS children which are in
different blocks.  As show in the example, some of those children of a node
C - such as D in the example - will have L(D) < D(C)  ( 0 < 3) while other
children - such as F in the example will have L(F) >= D(C) ( 3 >= 3).  SO -
to determine if a node is a cut-vertex, all of that node's DFS-children
must be checked.

[Alia] The second point is that by tracing where each node inherited its
lowpoint value from, a path to attach to a node above the DFS parent can be
found.  This is critical - since this lowpoint inheritance path is used to
find the ears for DFS children in the algorithm.  It's a fast way to find a
diverse path from the DFS tree.

>
>    1. Algorithm Evaluation.  While it is interesting to see MRT compared
>    to rLFA, it would be much more interesting to see it compared to the
>    options in the appendices or to ARC.  I would move the comparison to rLFA
>    to an appendix.
>
> [Alia]  It is being compared to other options that are being seriously
used for fast-reroute.  That includes rLFA.  I don't understand why you
think the comparison isn't relevant?   We didn't quite have time to get the
comparison fully done for MRT lowpoint compared to the SPF-based and hybrid
versions.  I think that is something we can add - but again, we didn't find
a significant impvorement.

> [Alia] Do you just want me to refer to OSPFv2?  I can go hunt a reference
for better normative explanation or just describe transforming all
broadcast interfaces into a pseudo-node with p2p links with appropriate
costs.

>
>    1. Section 2; in the definition of MRT-Red and MRT-Blue:
>     s/described/describe
>    2. Section 2; ADAG definition: "whith"  ??
>    3. "strictly greater/lower"  These  terms are used in a couple of
>    places, but the << or >> notation is used most of the time.  It would be
>    nice to be consistent to avoid confusion.
>    4. Section 3.2: "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
>    already in the ADAG."   Too many "already".
>    5. It would be nice to include "partial ADAG" in the definitions
>    section.  Yes, it is defined elsewhere, but a central place is nice in
>    case you forget. ;-)
>
> [Alia] Sure to all the above.

>
>    1. I know sometimes it's hard, but please try to format the text so
>    that the figures are not split between pages.
>
> [Alia] Do you know a magic xml2rfc method for doing that?

>
>    1. Section 3.4, after Figure 10. "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 one in block 2 with C as a root, and finally, we need the last
>    one in block 1 with R as a root."  When talking about blocks 1 and 2, you
>    really mean a pair to RTs (just like in block 3), not just "one", right?
>
> [Alia] Yes, probably rephrasing as "another pair of RTs" and "last pair of
RTs" would help.

>
>    1. Section 3.5: "The method for local-root computation is used in the
>    MRT Lowpoint algorithm for computing a GADAG using Low-Point
>    inheritance and the essence of it is given in Figure 12."  s/is
>    used/used  and s/inheritance and/inheritance, and   To improve readability.
>    2. There are a couple of out of date references.
>
> [Alia] Sure - will fix.

---

From: "Alvaro Retana (aretana)" <[email-masked]>
Date: Thu, 10 Oct 2013 14:12:26 +0000

On 10/9/13 5:06 PM, "Alia Atlas" <[email-masked]<mailto:[email-masked]>> wrote:

<WG Chair Hat Off>

Alia:

Hi!

I pruned most of the text off to leave the relevant parts.

Thanks!!

Alvaro.

. . .

The draft has an intended status of Informational.  However, the Introduction reads:  "This document defines the MRT Lowpoint algorithm to be used as a standard in the default MRT profile for MRT-FRR."  Which one is it?

[Alia] I think that the algorithm draft needs to be standards track.  I apologize for not updating the intended status - I was focused on the contents.

[Alia] The intent is to have signaling that says this is the algorithm being used. There's capabilities to indicate different algorithms - but I do think that this particular algorithm and details must be standards-track for interoperability.

The capabilities you're talking about are in I-D.atlas-ospf-mrt, right?

What I see in there is a way to indicate which profile is supported..which I guess ties into the algorithm (for example, the Lowpoint is tied in the draft to the default profile)..  It's not a direct way of indicating the algorithm, but that's what you mean, right?

BTW, I have no problem in the indication being indirect..

BTW2, on the architecture draft (Section 7) the default profile is described..but it took me a while to find it because the words "default MRT profile" showed up 2-3 paragraphs before the profile was actually defined.  It might be nice (for people like me) to clearly state: "This is the default MRT profile:".

I should read the architecture draft closer..but isn't it like putting the carriage before the horse to specify there (and not in the algorithm draft) that the Lowpoint algorithm is the one used in the default MRT profile?

. . .

  1.  I found it interesting that, even though the document is defining an algorithm that when implemented will need to have consistency across nodes, there was no reference to RFC2119 — but some of the words were capitalized anyway. Even then, only 4 "MUST" and 1 "SHOULD" appeared.  I realize that the count of MUST/SHOULD is no indication of anything, but it doesn't feel right for a 40+ page document.  I would appreciate if the authors would not just add the 2119 reference (nit), but if they would also comb the text for parts where a little more normative direction might help (which doesn't necessarily translate into MUSTs).

[Alia] Agreed - in general, what I intend to do is to have the explanatory text that explains the logic of the algorithm and how it works much as it is - and then to pull together the different parts of the pseudo-code into a fully detailed algorithm (some by reference to the earlier parts) that indicates the MUST/SHOULD aspects.   The specific request though seems more to be to take a careful read through and clarify what is MUST and what is SHOULD.

I think the end result should be the same.  All I want it to make sure that the mandatory parts are clear for everyone to implement.

. . .

  1.

[Alia] The Root Selection is described in draft-ietf-rtgwg-mrt-frr-architecture in Sec 7 as
'"GADAG Root Selection Priority: Among the routers in the MRT Island and with the highest priority advertised, an implementation MUST  pick the router with the highest Router ID to be the GADAG root."

This goes back to my comment above about the capabilities and the default profile definition: If this is part of the algorithm it should be specified in the algorithm draft, not somewhere else.

. . .

  1.  Algorithm Alternatives and Evaluation.  There are a couple of alternatives described in the appendices, but there is no evaluation as to why the Lowpoint Algorithm is better.  In fact, the text seems to read as if the appendices describe options to the main algorithm (?) -- begging the question, are there instances where these options would/could be used?

[Alia] True - in our initial evaluations, we didn't find significant differences in the path lengths for the alternates.  Chris Bowers can comment on that a bit.  I thought that I'd cleaned up the text in the main draft to clarify that the lowpoint algorithm - which has much less computation - is preferable.  Can you point to where the algorithms in the appendices are considered equivalent?  I will, of course, take another read through as well - trying to reduce that issue.

Where in the main draft?  And by "main draft" do you mean the architecture one?

My point was that you are presenting options to the proposed algorithm that are not used..but there is no clear explanation as to why not (at least not that I found in this draft).  IOW, I think that if these options are not part of the main algorithm then you should explain why not (but you already said above that there weren't significant differences in the results), or just take them out to avoid confusion.

. . .

  1.

[Alia]  umm, how would you define them beyond their obvious meaning?  Outgoing is from the interface's router to the remote end.   Incoming is from the remote router to the interface's router.

:-)

The text starts talking about marking the links (and even the pseudo-code uses the terms), but they are not defined.  Yes, I can guess what they mean..but if we want consistency you don't want people guessing.

. . .

  1.  Algorithm Evaluation.  While it is interesting to see MRT compared to rLFA, it would be much more interesting to see it compared to the options in the appendices or to ARC.  I would move the comparison to rLFA to an appendix.

[Alia]  It is being compared to other options that are being seriously used for fast-reroute.  That includes rLFA.  I don't understand why you think the comparison isn't relevant?   We didn't quite have time to get the comparison fully done for MRT lowpoint compared to the SPF-based and hybrid versions.  I think that is something we can add - but again, we didn't find a significant impvorement.

I didn't say that the comparison is irrelevant..I just said that I would move it to an appendix.

In this draft you're proposing an algorithm to be used as the default in MRT.  We already know that rLFA can't always provide 100% coverage.  I think that comparing the proposed algorithm to something that we know doesn't provide the same coverage is interesting, but it doesn't illustrate why this algorithm should be the default — it just proves that "the 100% coverage provided by MRT comes at the expense of a modest increase in alternate path length."  That is an interesting result..I just find it purely informational wrt to the contents and objective of the draft.

OTOH, if the algorithm was to be compared with other potential candidates (including the options in the appendices) then it could provide better justification..and it would fit better in a section titled "Algorithm Alternatives and Evaluation" that starts with the following text: "This specification defines the MRT Lowpoint Algorithm, which is one option among several possible MRT algorithms.  Other alternatives are described in the appendices."

Nits:

[Alia] Do you just want me to refer to OSPFv2?  I can go hunt a reference for better normative explanation or just describe transforming all broadcast interfaces into a pseudo-node with p2p links with appropriate costs.

I usually think about ISIS when I think about pseudo-nodes..which is why we need a reference to that the "standard representation" is.  ;-)

---

From: Alia Atlas <[email-masked]>
Date: Thu, 10 Oct 2013 17:07:59 -0400

Replies in-line as always...

On Thu, Oct 10, 2013 at 10:12 AM, Alvaro Retana (aretana) <[email-masked]
> wrote:

>  On 10/9/13 5:06 PM, "Alia Atlas" <[email-masked]> wrote:
>
>  <WG Chair Hat Off>
>
>  Alia:
>
>  Hi!
>
>>  The draft has an intended status of Informational.  However, the
>> to be used as a standard in the default MRT profile for MRT-FRR."  Which
>> one is it?
>>
>
>  What I see in there is a way to indicate which profile is
> supported..which I guess ties into the algorithm (for example, the Lowpoint
> is tied in the draft to the default profile)..  It's not a direct way of
> indicating the algorithm, but that's what you mean, right?
>

[Alia] Right - the algorithm is one aspect of a profile - and different
profiles can be specified.

>  BTW2, on the architecture draft (Section 7) the default profile is
> described..but it took me a while to find it because the words "default MRT
> profile" showed up 2-3 paragraphs before the profile was actually defined.
>  It might be nice (for people like me) to clearly state: "This is the
> default MRT profile:".
>

[Alia]  Sure -  I expect that we co-authors should go over the arch draft
and make sure that the normative details are clearly specified as such and
clearly.  In this case, I think it's just reordering a bit - since the
architecture draft talks about the concept of MRT profiles and that there
is a default MRT profile before defining what that default is.  I don't
expect to have that done for this IETF - unless there is serious concern
about a lack of clarity.

> I should read the architecture draft closer..but isn't it like putting the
> carriage before the horse to specify there (and not in the algorithm draft)
> that the Lowpoint algorithm is the one used in the default MRT profile?
>

[Alia] I didn't think so (but you knew that ;-) - having it make sense to
define the default MRT profile where the concept of MRT profiles is
defined.  I do agree that it makes sense to have the algorithm draft
reference the architecture draft and that the lowpoint algorithm is used in
the default MRT profile - so basically say it in both places :-)

>>  [Alia] Agreed - in general, what I intend to do is to have the
> explanatory text that explains the logic of the algorithm and how it works
> much as it is - and then to pull together the different parts of the
> pseudo-code into a fully detailed algorithm (some by reference to the
> earlier parts) that indicates the MUST/SHOULD aspects.   The specific
> request though seems more to be to take a careful read through and clarify
> what is MUST and what is SHOULD.
>
>
>  I think the end result should be the same.  All I want it to make sure
> that the mandatory parts are clear for everyone to implement.
>

[Alia] Absolutely.

>  . . .
>
>
>>    1.
>>       - Root Selection.  No algorithm is provided. There's a reference
>>       to I-D.atlas-ospf-mrt, where a suggestion is made ("..the router with the
>  This goes back to my comment above about the capabilities and the
> default profile definition: If this is part of the algorithm it should be
> specified in the algorithm draft, not somewhere else.
>

[Alia] Ah - the GADAG root selection is part of the MRT profile but not,
IMHO, part of the algorithm...  The same Lowpoint algorithm can be used
with different GADAG root selection.  For example, for multicast, one might
do an MRT profile where the multicast S is picked to be the GADAG root -
and the same Lowpoint algorithm is run.

>  Where in the main draft?  And by "main draft" do you mean the
[Alia] Sorry to have been unclear - by main draft I meant the algorithm
draft that isn't in the appendices.

My point was that you are presenting options to the proposed algorithm that
> are not used..but there is no clear explanation as to why not (at least not
> that I found in this draft).  IOW, I think that if these options are not
> part of the main algorithm then you should explain why not (but you already
> said above that there weren't significant differences in the results), or
> just take them out to avoid confusion.
>

[Alia] Sure - I put them in an appendix while we decided which to do :-)

. . .
>  The text starts talking about marking the links (and even the
> pseudo-code uses the terms), but they are not defined.  Yes, I can guess
> what they mean..but if we want consistency you don't want people guessing.
>

[Alia] True...  I do describe everything about how they are used - but I'll
try for better text too.

. . .
>  In this draft you're proposing an algorithm to be used as the default in
> MRT.  We already know that rLFA can't always provide 100% coverage.  I
> think that comparing the proposed algorithm to something that we know
> doesn't provide the same coverage is interesting, but it doesn't illustrate
> why this algorithm should be the default — it just proves that "the 100%
> coverage provided by MRT comes at the expense of a modest increase in
> alternate path length."  That is an interesting result..I just find it
> purely informational wrt to the contents and objective of the draft.
>

[Alia] AH - I am trying to show that MRT Lowpoint is a good fast-reroute
mechanism that offers 100% coverage with good computation and without
causing absurdly long alternates (in most/many networks).    In that
context, the comparison is to the "optimal"
and Remote-LFA is to help show what the trade-offf for alternate length is.
 If we want to see if a different MRT algorithm gives better alternate
lengths, that is also interesting but comes at a computational cost.

>
>  OTOH, if the algorithm was to be compared with other potential
> candidates (including the options in the appendices) then it could provide
> better justification..and it would fit better in a
> section titled "Algorithm Alternatives and Evaluation" that starts with the
> following text: "This specification defines the MRT Lowpoint Algorithm,
> which is one option among several possible MRT algorithms.  Other
> alternatives are described in the appendices."
>

[Alia] Yes - I should have cleaned that text up.  We'll try for some
comparison results - if not in time for this IETF - then shortly after.

>>  [Alia] Do you just want me to refer to OSPFv2?  I can go hunt a
> reference for better normative explanation or just describe transforming
> all broadcast interfaces into a pseudo-node with p2p links with appropriate
> costs.
>
>
>  I usually think about ISIS when I think about pseudo-nodes..which is why
> we need a reference to that the "standard representation" is.  ;-)
>

Sounds like spelling it out to be a representation where all links are p2p
and the necessary pseudo-nodes are added to make it so - basically the same
network graph as an SPF is run on....

Alia

---

From: "Alvaro Retana (aretana)" <[email-masked]>
Date: Fri, 11 Oct 2013 18:04:39 +0000

<WG Chair Hat Off>

Hi!

On 10/10/13 5:07 PM, "Alia Atlas" <[email-masked]<mailto:[email-masked]>> wrote:

. . .

  1.

[Alia] Ah - the GADAG root selection is part of the MRT profile but not, IMHO, part of the algorithm...  The same Lowpoint algorithm can be used with different GADAG root selection.  For example, for multicast, one might do an MRT profile where the multicast S is picked to be the GADAG root - and the same Lowpoint algorithm is run.

But the performance of the algorithm can be affected by the selection of the root.  In 6.1 you wrote: "The particular choice of a common GADAG root is expected to affect the quality of the MRT alternate paths, with a more central common GADAG root resulting in shorter MRT alternate path lengths."  For the results you chose a centrally located node to be the root.  What would have happened if the root had been selected randomly?  (Or the equivalent which would be to assign random Priorities.)

I guess my point here is that one of the reasons the Lowpoint algorithm performs well is because of how the root is selected.  We could go back and forth all day about whether the root selection should be part of the "default algorithm" or just part of the "default profile"..but I think it would be more important to stress (even mandate) that the location of the nodes be considered when assigning the Priority.

Note that the current text ("Off-line analysis that considers the centrality of a router may help determine how good a choice a particular router is for the role of GADAG root." -- which is too soft for my taste) is in the algorithm draft, not in the architecture draft (which defines the profile), so it may not be completely clear..

Thanks!

Alvaro.

---

From: Alia Atlas <[email-masked]>
Date: Fri, 11 Oct 2013 14:14:58 -0400

On Fri, Oct 11, 2013 at 2:04 PM, Alvaro Retana (aretana)
<[email-masked]>wrote:

>  <WG Chair Hat Off>
>
>  Hi!
>
>  On 10/10/13 5:07 PM, "Alia Atlas" <[email-masked]> wrote:
>
>  . . .
>
>
>>>    1.
>  But the performance of the algorithm can be affected by the selection of
> the root.  In 6.1 you wrote: "The particular choice of a common GADAG root
> is expected to affect the quality of the MRT alternate paths, with a more
> central common GADAG root resulting in shorter MRT alternate path lengths."
>  For the results you chose a centrally located node to be the root.  What
> would have happened if the root had been selected randomly?  (Or the
> equivalent which would be to assign random Priorities.)
>

[Alia] There is variability, of course, but we found that up to the first
50th percentile of centrality nodes were fairly similar.   This is really a
"don't locate it in Timbuktu" if your network is mostly in NA kind of thing.

> I guess my point here is that one of the reasons the Lowpoint algorithm
> performs well is because of how the root is selected.  We could go back and
> forth all day about whether the root selection should be part of the
> "default algorithm" or just part of the "default profile"..but I think it
> would be more important to stress (even mandate) that the location of the
> nodes be considered when assigning the Priority.
>

[Alia] Absolutely - the operator should do some basic analysis and pick a
node for GADAG root that is basically well connected and in the spine/core
of the network.   I'm sorry if the difference between "default algorithm"
and "default profile" seems like pedantry -  I'm trying to set up MRT to
work for multiple purposes (multicast live-live and MRT-FRR) and keep the
right parts separated.

Note that the current text ("Off-line analysis that considers the
> centrality of a router may help determine how good a choice a particular
> router is for the role of GADAG root." -- which is too soft for my taste)
> is in the algorithm draft, not in the architecture draft (which defines the
> profile), so it may not be completely clear..
>

[Alia] Sure - I see your point and would be happy to add in some comments
there.  I'm afraid that the analysis giving clue as to importance of GADAG
root selection came while I was updating drafts and may not have gone
through them sufficiently.

Alia