Subject: Re: Updated: draft-zinin-microloop-analysis-01.txt

From: mike shand <[email-masked]>
Date: Fri, 03 Jun 2005 10:33:33 +0100

At 19:02 27/05/2005 +0100, Stewart Bryant wrote:
>Alex
>
>Some comments on: draft-zinin-microloop-analysis-01.txt
>
>--------------------------------
>
>2.1 Terminology
>
>    The following terms are used in the draft.
>
>      Downstream neighbor
>           Neighbor N of router S is considered S's downstream neighbor
>           for destination D, if Dopt(N, D) < Dopt(S, D)
>
>SB> You need to provide a definition of the function Dopt()

This is already defined in the IPFRR framework (as Distance_opt(A, B) )

         Mike

_______________________________________________
Rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: mike shand <[email-masked]>
Date: Fri, 03 Jun 2005 10:56:34 +0100

At 16:43 31/05/2005 -0400, Alia Atlas wrote:
>Stewart & Alex,
>
>At 02:02 PM 5/27/2005, Stewart Bryant wrote:
>>      Primary neighbor
>>           Neighbor N of router S is considered S's primary neighbor for
>>           destination D, if N provides the shortest path to D according
>>           to the SPF calculation.
>>
>>SB> Need to say something formal like selecting N such that
>>SB> Dopt(N.D) is minimised.
>
>AA> There's always the possibility that a potential primary neighbor isn't 
>selected.  Consider the case
>AA> where a router only selects up to 4 equal-cost paths, and there are 5 
>or more.  The definition should
>AA> handle this case as well.
>
>>  2.2 Next hop safety condition
>>
>>    We start the analysis with the following observation:
>>
>>      When router X learns about a topology change and starts using
>>      neighbor Y as its new primary neighbor for a given destination, a
>>      microloop between X and Y can only form if the topology before
>>      failure or topology after failure are such that Y uses X as its
>>      primary neighbor for the same destination.
>>
>>SB> I don't think that this is quite right. You say that X uses
>>SB> Y as its new next hop, AND Y uses X as it's new next hop. That
>>SB> would be a failure of the IGP, which is out of scope.
>
>AA> Perhaps a better way to phrase it is:
>
>AA> "... a microloop between X and Y can only form if the topology before 
>the failure is such that Y used
>AA> X as its primary neighbor for the same destination."
>
>AA> And then need to clarify the opposite case as well - where the roles 
>of X and Y are reversed.  I think
>AA> you were trying to - but I agree that it isn't clear.
>
>>    Routers SHOULD use the symmetric-link safety condition by default,
>>    MAY attempt to dynamically determine the method that needs to be
>>    applied based on the topological information from the routing
>>
>>SB> I think that we need to discuss which algorithm should
>>SB> be the default. Given that many networks that are thought
>>SB> to be symmetric turn out to be asymmetric, it's not clear
>>SB> which we should choose and why.
>
>AA> How many of the symmetric networks that actually turn out to be 
>asymmetric have multi-hop loops in
>AA> them?  Couldn't this be something that was flagged by a MIB - to 
>indicate that the "symmetric"
>AA> network isn't really.  Surely this is something that the network 
>operators would want to know so that it
>AA> can be corrected??

Yes, I wonder how much of a problem this really is. Given that the 
algorithm doesn't prevent all loops anyway, then a small increment in the 
number of loops caused by incorrectly handled asymmetric cost cases doesn't 
seem to be much a price to pay, especially since using the stronger 
condition to handle them correctly will result in the overall coverage 
being less. i.e. the total number of loops may get WORSE by using the 
asymmetric cost fixing algorithm.

I know.... something for me to simulate :-)

>AA> Another related question is how does PLSN work with max-cost 
>links?  How should it work?  Is it
>AA> acceptable to use a max-cost link to reach a safe neighbor that isn't 
>a potential primary neighbor on
>AA> either the old or new topology?  That seems potentially bad to me, 
>since it could cause additional
>AA> traffic loss, depending on why the link was set to max-cost.

I think a max-cost link should be treated as unreachable, since that is 
probably why it was set to max cost.

>>------------------------
>>
>>3.3 IP Fast Reroute Considerations
>>
>>    If the router implements [IPFRR] and performs local failure repair,
>>    procedures describes in this document still need to be applied in
>>    order to prevent micro-loops while reconverging on the new topology.
>>
>>SB> This is stricter than it should be. Say we implement basic [IPFRR]
>>SB> AND some other enhanced mechanism. We may wish to use some other
>>SB> mechanim in place of this.
>
>AA> I think that the intention should be to say that PLSN is useful to 
>avoid micro-loops during
>AA> re-convergence and this benefit is not provided simply by using basic 
>[IPFRR] or another repair
>AA> mechanism.  Both a repair mechanism and a convergence control 
>mechanism are desirable.
>AA> I do think it would be useful to specify the risks/undesirability of 
>using PLSN without a repair
>AA> mechanism when the topology change includes failures.

Yes.

>AA> I do agree with Stewart that the phrasing should consider the 
>possibility of future techniques being
>AA> introduced.

Agreed.

>>    Another difference is when the router could not repair the failure,
>>    the new primary next-hops do not satisfy the safety condition, and
>>    there's no other neighbor that does, i.e. a type-C situation. Unlike
>>    other routers in the network, the router directly connected to the
>>    network does not have the old next-hop any more, and cannot continue
>>    using it. In this situation, the router MUST revert to the regular
>>    convergence procedures, and update the route with the new next-hops
>>    with no additional delay.
>>
>>SB> We need to think about this some more. When we have an imperfect
>>SB> repair we need to consider the "greater good" and that might
>>SB> be to control the convergence of the rest of the network.
>
>AA> Given that no other router in the network is aware that the router (S) 
>doesn't have an alternate, I'm
>AA> not sure what better option can exist.  I think that the convergence 
>of the rest of the network is being
>AA> controlled.  The micro-loops related to S are not being handled.  The 
>worst-case that I see is that S
>AA> uses a neighbor N where that neighbor is type-B and is using S as its 
>safe neighbor.  I do agree that
>AA> we need to think about this more.
>
>>3.4 Architectural Constants
>>
>>    The following architectural constants have been used in the descrip-
>>    tion of the algorithm above:
>>
>>      DELAY_SPF
>>           The delay between the moment the router receives a topology
>>SB> s/a/the first/
>>           update after a period of stability and the moment it starts
>>           its routing table recalculation.  This delay is necessary to
>>           collect multiple updates originated by different routers that
>>           relate to the same topological event.
>>
>>SB> We might want to more formally state the start/inhibit criteria
>
>AA> I agree.
>
>>      DELAY_TYPEB and DELAY_TYPEC
>>           Periods of time used by the router to delay installation of
>>           new primary next-hops after a topology change when the router
>>           has (type-B) or has not (type-C) a safe neighbor to temporary
>>           divert the traffic to in the meantime.
>>
>>    While correctness and effectiveness of the algorithm described here
>>    does not depend on the actual values assigned to the architectural
>>    constants, it does depend on the relationship between them, and the
>>    assumption that all routers in the same network use the same values.
>>
>>    To satisfy these constrains, and yet allow these delays to be
>>    decreased as implementations continue to improve towards faster con-
>>    vergence, this document defines the architectural constants as con-
>>    figurable, specifies the required relationship between the values,
>>    and the default values that should be used by the implementations.
>>
>>SB> I wonder if we need to signal these, for example in the LSP/LSA
>>SB> I am concerned that there is little chance that all routers
>>SB> in the network will be correctly configured. The trouble is
>>SB> that if there is a mis-config it will be very hard to detect.
>
>AA> What would be done by the routers with this additional 
>information?  Why isn't this a management
>AA> problem?  These values could be in (yet another) MIB & then the values 
>of the routers could be
>AA> compared.  I don't like the idea of adding signaling to check for 
>inconsistency - when all the router
>AA> could do on detecting this would be a log or, I guess, disabling the 
>functionality in the case of mis-AA> matches.

I think I agree with Alia here. While at first sight it seems that there 
might be something you could do with advertising these things in the 
protocol, life can get very complicated when you start considering what 
happens when various routers and or regions of the network come and go. 
There is a very real danger that an "automated"dynamic synchronization 
scheme would result in more errors than a manual static one.

Simply using an advertisement in the protocol to give a warning that some 
static misconfiguration has been made (as I think Stewart was suggesting) 
is more workable, but seems like a poor use of the protocol, especially 
since (as Alia points out) the information should be available for 
management application to check anyway.

Mike

>Alia

---

From: Stewart Bryant <[email-masked]>
Date: Fri, 03 Jun 2005 12:37:48 +0100

> This is already defined in the IPFRR framework (as Distance_opt(A, B) )

OK, then it needs an explicit reference to framework at that point.

Stewart

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 09:27:51 -0400

At 05:56 AM 6/3/2005, mike shand wrote:
>number of loops caused by incorrectly handled asymmetric cost cases 
>doesn't seem to be much a price to pay, especially since using the 
>stronger condition to handle them correctly will result in the overall 
>coverage being less. i.e. the total number of loops may get WORSE by using 
>the asymmetric cost fixing algorithm.
>

AA> Exactly ;-)   Please let us know what you find.  I suspect that the 
total number of loops would be
AA> increased.  As I recall, going to the asymmetric safety condition meant 
that about only half of the micro-
AA> loops otherwise resolved by PLSN were handled.

AA> A point of interest in the simulation might be not merely the number of 
loops but the number of affected
AA> links.

>probably why it was set to max cost.

AA> The condition I have for LFA is that if the cost of the link or the 
cost of the associated reverse link are
AA> max-cost or (for ISIS) the neighbor is over-loaded, then don't consider 
the link as a candidate alternate
AA> next-hop.  For PLSN, I'd modify it to the following.  "If no links to a 
neighbor could be considered as a
AA> candidate alternate next-hop and the neighbor is not either a new 
primary neighbor or a old primary
AA> neighbor, then the neighbor cannot be a safe neighbor. "

Alia

---

From: Stewart Bryant <[email-masked]>
Date: Fri, 03 Jun 2005 16:31:55 +0100

>> AA> problem?  These values could be in (yet another) MIB & then the 
>> values of the routers could be
>> AA> could do on detecting this would be a log or, I guess, disabling 
>> the functionality in the case of mis-AA> matches.
> 
> 
> Simply using an advertisement in the protocol to give a warning that 
> some static misconfiguration has been made (as I think Stewart was 
> suggesting) is more workable, but seems like a poor use of the protocol, 
> especially since (as Alia points out) the information should be 
> available for management application to check anyway.
> 

I don't like the idea of requiring consistent configuration across the
network, because there is a strong chance that it will be wrong, and
it's always a problem when it has to be changed because of the inclusion
or removal of a particular router. There is also the issue that the
parameter is in some sence dynamic, being dependent on the size of the
network so it's going to need to be tuned as time goes by.

Nor do I much like the idea of requiring an NMS to se the parameter
because not all networks have an NMS that is responsible of the
configuration of the routers.

I suggest that each router includes it's max required time in its
LSP/LSAs and the network uses the max of the max. The parameter
can be extracted as part of the SPF calculation. Since, for the
topology calculation to be consistent, all routers have to be
using the same set of active links in their calculation we know that
they will all extract the same maximum value for delay. If the network
is unstable in such a way that not all routers are using the same links
to claculate the SPT, then we have bigger problems.

A standard concern is the inclusion of removal of large sections of the
network changin the parameter, but this comes out in the wash, provided
the algorithm (at least conceptually) is to find the max value during
the parsing of the active links.

A futher standard concern is what happens when a value changes. When a
router is re-configured it issues a new set of LSPs with the new timer
value. However this has a null effect on the topology, and we can
expressly prevent a transition taking place when a router issues an
LSP in which the only change is the ephoch time request.

There is the issue concerning inconsistency during the window where one
router has issued a time change LSP and concurrently a failure occurs.
This is probably better, and certainly no worse than a failure occuring
during a time in which the NMS is issuing a timer value change to
the routers in the net.

- Stewart

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 11:36:43 -0400

Stewart,

>during a time in which the NMS is issuing a timer value change to

I think that this could be a very nice solution to the problem.  I really 
like it :-)

If each router advertises its max compute-install time (which could be 
configured or derived), then all routers could compute the max, possibly 
add a small certainty factor and use that for the DELAY_TYPEC and DELAY_TYPEB.

Alia

---

From: mike shand <[email-masked]>
Date: Fri, 03 Jun 2005 17:05:44 +0100

>add a small certainty factor and use that for the DELAY_TYPEC and DELAY_TYPEB.

Yes, I agree that such an automatic dynamic scheme would be very nice IF it 
were unconditionally stable. Stewart's arguments seem convincing, but I 
have been burnt too often in the past by such things to immediately accept 
that it will never cause any problems:-)

I don't THINK it will, but I think it needs a bit more analysis of nasty 
cases to be sure that there aren't any situations where it could make bad 
things happen, or in particular make more bad things happen than if we 
hadn't done it.

I do agree that SOMETHING needs to be done, since the consequences of 
getting it wrong manually are clearly pretty severe, and changing a value 
manually is a real pain.

I think it all boils down the veracity (or otherwise) of Stewart's statement

"If the network
is unstable in such a way that not all routers are using the same links
to claculate the SPT, then we have bigger problems."

If indeed we do have bigger problems, then this is probably all OK. But if 
the problems introduced by an unsynchronized topology are actually much 
LESS than the problems caused by using inconsistent delay values (long 
persistence of loops), then maybe it is not such a good idea.

         Mike

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 12:48:06 -0400

At 12:05 PM 6/3/2005, mike shand wrote:
>Yes, I agree that such an automatic dynamic scheme would be very nice IF 
>it were unconditionally stable. Stewart's arguments seem convincing, but I 

A good cautionary point and certainly we need to think about it a lot more, 
but it does seem like a very promising way of solving what we seem to agree 
is a problem.

Thinking it over a bit more, if the time advertised by a router dynamically 
changed as a result of the number of routes to be installed, I think I 
might be concerned - but I'm not sure if my concern is well grounded.   I 
think the concern would be because of the potentially larger number of 
updates that might occur as a result of a single change.

I do think that because of the DELAY_SPF, all routers should have heard the 
same updates before computing & so should be working on the same exact 
topology with the same set of max-install-times.

Another interesting aspect might be the partial deployment scenarios that 
could benefit from this.  For instance, if a router doesn't advertise its 
max-install-time, then that router can be presumed not to support 
PLSN.   Possibly at some point, one could even say that the router could be 
presumed not to support IPFRR - so if the topology change was a failure was 
local to that router, then revert to  converge ASAP.

Alia

---

From: Stewart Bryant <[email-masked]>
Date: Fri, 03 Jun 2005 18:42:22 +0100

Alia Atlas wrote:

>>> I think that this could be a very nice solution to the problem.  I 
>>> really like it :-)
>>>
>>> If each router advertises its max compute-install time (which could 
>>> be configured or derived), then all routers could compute the max, 
>>> possibly add a small certainty factor and use that for the 
>>> DELAY_TYPEC and DELAY_TYPEB.
>>
>>
>> Yes, I agree that such an automatic dynamic scheme would be very nice 
>> IF it were unconditionally stable. Stewart's arguments seem 
>> convincing, but I have been burnt too often in the past by such things 
>> to immediately accept that it will never cause any problems:-)
>>
>> I don't THINK it will, but I think it needs a bit more analysis of 
>> nasty cases to be sure that there aren't any situations where it could 
>> make bad things happen, or in particular make more bad things happen 
>> than if we hadn't done it.
>>
>> getting it wrong manually are clearly pretty severe, and changing a 
>> value manually is a real pain.
>>
>> If indeed we do have bigger problems, then this is probably all OK. 
>> But if the problems introduced by an unsynchronized topology are 
>> actually much LESS than the problems caused by using inconsistent 
>> delay values (long persistence of loops), then maybe it is not such a 
>> good idea.
> 
> 
> A good cautionary point and certainly we need to think about it a lot 
> more, but it does seem like a very promising way of solving what we seem 
> to agree is a problem.
> 
> Thinking it over a bit more, if the time advertised by a router 
> dynamically changed as a result of the number of routes to be installed, 
> I think I might be concerned - but I'm not sure if my concern is well 
> grounded.   I think the concern would be because of the potentially 
> larger number of updates that might occur as a result of a single change.

When I said about dynamic, I was thinking on a very course, rarely changed
scale, as much dependent on the OS version, or the mix of vendors as the
gross size of the network.

Stewart

> 
> I do think that because of the DELAY_SPF, all routers should have heard 
> the same updates before computing & so should be working on the same 
> exact topology with the same set of max-install-times.
> 
> Another interesting aspect might be the partial deployment scenarios 
> that could benefit from this.  For instance, if a router doesn't 
> advertise its max-install-time, then that router can be presumed not to 
> support PLSN.   Possibly at some point, one could even say that the 
> router could be presumed not to support IPFRR - so if the topology 
> change was a failure was local to that router, then revert to  converge 
> ASAP.
> 
> Alia
> 
>

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 11:22:17 -0700

Alia,

> Alex,

> Just a few comments on the updated draft...

> In Section 3.1, it might be worth clarifying that more updates might be 
> expected than just the other end of a point-to-point link.  That might make
> it seem that a router could start its delayed SPF once the second update 
> had arrived.

Will do.

> Also in Section 3.1, with the fallback policy, it might be useful to 
> describe how this interacts with the standard SPF hold-down policies that
> currently exist.

When I thought about this, I ended up concluding that all this document can
define is what needs to be done in order for the described mechanism to
work, and then leave interactions with possible SPF hold-down
implementation details to the implementations. I'm open for suggestions
though, so if you had an idea on what it might look like--please send it.

> In Section 3.2, case 2, I believe that for the ECMP case, it isn't possible
> to have, for a destination, some next-hops that are type A and some that 
> are type C.  If there's at least one next-hop that is type A, then that 
> provides the not-this-primary next-hop that is safe for type B.

I think you're right. Will remove the second part in the "()".

> In Sec 3.3, it seems to me that if there isn't an IPFRR alternate, then it
> is possible for traffic to be dropped for DELAY_TYPEC.  This would be the
> case where S's new primary next-hop is a type C itself.  I'm not sure if 
> there's any way around this - but it may be worth thinking about a bit.

Indeed, I meant to ask for opinions on this. I had to put something in the
text, so I made a decision ;) I'll send a separate e-mail on this.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 11:43:57 -0700

Stewart,

I'll revise the text based on the editorial comments and the discussion

>     applied based on the topological information from the routing

SB>> I think that we need to discuss which algorithm should
SB>> be the default. Given that many networks that are thought
SB>> to be symmetric turn out to be asymmetric, it's not clear
SB>> which we should choose and why.

Just like with the situation where the repairing router has type-C
next-hops, I needed to propose a way of dealing with it, but this certainly
needs to be discussed. From what I see on the list, Mike will check
his simulation models and let us know.

>     For situation 2 (an A/B or an A/C combination), the implementation:

>       1)   SHALL update the route with the new next-hops that satisfy the
>            safety condition without an additional delay

>       2)   SHALL add the remaining new next-hops after DELAY_TYPEB.

SB>> maybe clarify type B is NOT used, although, there seems to
SB>> be no protocol reason why use type B cannot be used.

I'm not sure I understand what you mean here.

>     order to prevent micro-loops while reconverging on the new topology.

OK, what the reason I put this text there is to define exactly how PLSNs
work with Basic FRR, if IPFRR is used.

SB>> This is stricter than it should be. Say we implement basic [IPFRR]
SB>> AND some other enhanced mechanism. We may wish to use some other
SB>> mechanim in place of this.

Stewart, what do you see as too strict here? How do you think the text
should be changed?

AA>> I think that the intention should be to say that PLSN is useful to
AA>> avoid micro-loops during re-convergence and this benefit is not
AA>> provided simply by using basic [IPFRR] or another repair mechanism.
AA>> Both a repair mechanism and a convergence control mechanism are
AA>> desirable. I do think it would be useful to specify the
AA>> risks/undesirability of using PLSN without a repair mechanism when the
AA>> topology change includes failures. I do agree with Stewart that the
AA>> phrasing should consider the possibility of future techniques being
AA>> introduced.

I can add some text in the intro to say that a repair mechanism is
desirable and why.

Alia, Stewart, I don't think the text disallows future repair techniques,
but let me know, guys, how you think the text could be improved.

>     The following equations define the relationship between the constants
>     that needs to be maintained in order for the mechanism described here
>     to provide desireable results:

>      DELAY_SPF > update-propagation-time

>      DELAY_STABLE > DELAY_TYPEB > DELAY_TYPEC > fault-propagation-time

SB>> I deleted soem of the text from this edit. Did you say that
SB>> FIB updates MUST be completed by expiry of appropriate timer?

The definition of fault-propagation-time includes the FIB update time.

> ------------------------------

>     The implementations SHOULD use the following default values for the
>     architectural constants:

>          Constant                   Default val
>         ----------------------------------------
>          DELAY_SPF                   500 msec
>          DELAY_TYPEC                   2 sec
>          DELAY_TYPEB                   4 sec
>          DELAY_STABLE                 10 sec

SB>> On what basis? I imagine that you pulled these out of a hat,
SB>> and I suspect that they are as good values, but I think
SB>> that you need to say that is what you did.

As we discussed this before, yes, these are the default times pulled out of
a hat. The text actually describes that at certain length:

>    The following equations define the relationship between the constants
>    that needs to be maintained in order for the mechanism described here
>    to provide desireable results:

Let me know what you think should be added.

> 5 Security Considerations
...
SB>> Isn't there a threat in which some vulnerable link is failed
SB>> causing extended C-C outage?

I don't think so. The DELAY_TYPE? values are the same O() as SPF hold-downs
in the majority of deployed networks.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 12:02:13 -0700

Alia,

I'll add something along these lines. Thanks.

Alex

>>probably why it was set to max cost.

AA>> The condition I have for LFA is that if the cost of the link or the 
> cost of the associated reverse link are
AA>> max-cost or (for ISIS) the neighbor is over-loaded, then don't consider
> the link as a candidate alternate
AA>> next-hop.  For PLSN, I'd modify it to the following.  "If no links to a
> neighbor could be considered as a
AA>> candidate alternate next-hop and the neighbor is not either a new 
> primary neighbor or a old primary
AA>> neighbor, then the neighbor cannot be a safe neighbor. "

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 12:09:14 -0700

Stewart, et al-

 Do you guys mean

  - announcing values of configurable delays that are only changed
    by an admin action OR

  - announcing results of router's dynamic delay measurements?

 I would rather we not go in the latter direction.

-- 
Alex
http://www.psg.com/~zinin

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 17:06:33 -0400

I like the former as well.  The latter makes me a bit nervous.

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 17:13:06 -0400

>I'm not sure I understand what you mean here.

Safe but not new primary neighbors (type B) could be used during the 
transition period.  This is expressing a policy that they will not be; it 
would be safe to use them.

...
>but let me know, guys, how you think the text could be improved.

How about just changing where you have "procedures describes in this 
document ...."  to "a controlled convergence mechanism such as that 
described in the procedures in this document"?

Alia

---

From: Stewart Bryant <[email-masked]>
Date: Fri, 03 Jun 2005 22:15:57 +0100

>   - announcing values of configurable delays that are only changed

Yes

>   - announcing results of router's dynamic delay measurements?

No

>  I would rather we not go in the latter direction.

I agree

Stewart

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 17:18:59 -0400

Alex,

>though, so if you had an idea on what it might look like--please send it.

I'll think about it more.  Off-hand, I'm tempted to say that if an SPF 
hold-down is in force, then PLSN shouldn't be used.  I.e., only use PLSN if 
the topology has been stable for long enough that all routers will delay 
only DELAY_SPF before computing - and not more.

>text, so I made a decision ;) I'll send a separate e-mail on this.

The joy of writing it :-)
My only opinion right now is that it'd be nice to find something better 
;-)  I'll think about it some more.

Is it interesting to distinguish between the case where a router doesn't 
support IPFRR and the case where the router supports IPFRR but doesn't have 
an alternate for the particular destination?

Alia

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 14:38:52 -0700

Alia,

> transition period.

That's what the text says, right?

> This is expressing a policy that they will not be; it

Sorry, still not clear enough to me--are you guys suggesting the text is
changed, if so how?

> described in the procedures in this document"?

OK, I see what you mean. How about this?

     If a router implementing this specification also implements [IPFRR]
     and performs a local failure repair, the following considerations
     apply.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 15:37:33 -0700

Stewart, Alia-

 Good. Let's think about this a little more before jumping on it.

 Meanwhile, one thought I had while reading this thread: Stewart, you
 suggested that the max delay is found during the SPF calculation. It seems
 (or I hope ;) you didn't mean finding destination-specific max values, but
 instead merely using SPF's graph exploration property--visiting all
 reachable vertices.

 While this would work algorithmically, I would instead prefer finding the
 max among all available announcements, whether the corresponding nodes are
 momentarily reachable or not. This would be more robust, easier to debug,
 and save extra fluctuations when the network topology changes. If any of
 the routers becomes unreachable for an extended period of time, its
 LSAs/LSPs would finally age out and hence taken out of consideration.

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 19:14:37 -0400

>That's what the text says, right?

Well, it's a bit unclear.  It says "with the new next-hops", so that 
implies, to me at least, that those are safe new primary next-hops.

Also, the fact that in step 2 the remaining new next-hops are added and the 
type B next-hops aren't removed indicates that the type B next-hops aren't 
used.

>Sorry, still not clear enough to me--are you guys suggesting the text is

Do you want the policy of using type B or not? If not using them, then the 
text is ok - but needs a clarifying statement that this means that the type 
B next-hops are not used due to policy.

>      and performs a local failure repair, the following considerations

Sounds good to me.

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 19:18:33 -0400

>  Good. Let's think about this a little more before jumping on it.

Absolutely :-)

>  LSAs/LSPs would finally age out and hence taken out of consideration.

Yes, I was assuming that this would be the approach.

Alia

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 16:48:55 -0700

Alia,

> B next-hops are not used due to policy.

OK, understood. Personally, I'd rather avoid extra next-hop flip-flop (and
hence traffic rerouting) and not use the temporary safe nbrs unless I have
to (as in the type-B case), but if you think we should explicitly allow
them, I'll add a MAY in step 1 and words on removal in 2.

Let me know.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Fri, 3 Jun 2005 16:57:10 -0700

Alia,

> ;-)  I'll think about it some more.

My logic was: there seems to be two options:

 1) switch to the new next-hop immediately and risk having loops OR
 2) keep the old next-hops and black-hole the traffic until it's safe

and unless a loop is so micro it may recover before BW is severely affected
or TTL gets down to 0, I generally prefer to black-hole, hence the
decision.

> an alternate for the particular destination?

Not on Friday afternoon ;) Do you envision their reactions could be
different even though both ultimately can't repair the failure?

Alex

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 22:44:53 -0400

Alex,

>them, I'll add a MAY in step 1 and words on removal in 2.

I'm fine with not explicitly allowing type B in this scenario.  I guess I'd 
put SHOULDs in the text you have & explain that not using type B is 
recommended policy for the above reasons.

Alia

---

From: Alia Atlas <[email-masked]>
Date: Fri, 03 Jun 2005 23:24:02 -0400

Alex,

>or TTL gets down to 0, I generally prefer to black-hole, hence the

Absolutely agree.  I can't think of any other possibilities.  If S doesn't 
have either a loop-free alternate or a safe neighbor, then, without an 
advanced method, S can't safely send to any neighbor until that neighbor 
has converged - which means I don't think there are any other options.

>different even though both ultimately can't repair the failure?

Amazing how conversations seem to start on Fridays...

The difference could be based on what type of topology change has 
occurred.  Based on the updates, a router can determine if any elements 
have failed & then whether the associated routers could potentially locally 
repair them.

Basically, we have the following 5 cases:
    1) Topology changes are added links and/or metric cost changes.  PLSN 
can be used regardless of whether all the routers local to the change can 
do IPFRR.

     2) The only topology change is a single failure - whether node, link, 
or SRLG.  All the routers local to the change can do IPFRR.  PLSN can be 
safely used.

     3) The only topology change is a single failure - whether node, link 
or SRLG.  One or more routers local to the change does not do IPFRR.  PLSN 
shouldn't be used - because it delays the convergence & traffic is being lost.

     4) The topology change contains multiple failures.  PLSN probably 
can't be safely used.  Theoretically, some of the IPFRR alternates might 
still be good - but it's not clear how easy that is to determine or safe to 
guess.

    5) The topology change contains a failure and at least one other change 
(added link or cost change).  I think that this case can apply PLSN.

Thinking about this a bit more, I think that the draft may need some words 
about the handling of different topology event combinations.  What do you 
think?

Alia

---

From: Stewart Bryant <[email-masked]>
Date: Sat, 04 Jun 2005 09:26:14 +0100

Alex

In the general case we have to assume that every router has been configured
with a different value for the time that it's operator thinks it will need.
So the problem is how to make sure that the network has a consistent view
of the max value.

My thought was that since the set of LSPs that were used to calculate the
topology had to be consistent over the network (or the network would be
unstable), then if the delay parameter was imbedded in the LSPs it would
be consistent amongst the routers that were converging.

By using the value extracted from the current topology info, you avoid
a whole load of messy protocol associated with routers joining, or leaving
and wanting to change the value - it just happens automatically.

By using historical values - as you seem to propose, you need to consider
how you propose to synchronize the addition or removal of routers from
the max-time algorithm. I am proposing that this happen automatically
as part of the convergence calculation, whilst your approach needs to
consider quasi asynchronous removal of a router that has the net max
value, just as the topology changes. Extracting the info from the LSPs
makes such actions a synchronous event.

If I look at your second para:
 >  momentarily reachable or not.
 >  This would be more robust,

What can be more robust than extracting the parameter from the set of
topology info that EVERYONE is using for THIS transition?

 >  easier to debug,

Not convinced, you know which routers are in the net, you know what the
time should be. The other way you get strange bugs due to the
asynchronous aging of LSPs

 >  and save extra fluctuations when the network topology changes.

I am not sure how much of a problem this is in practice.

 >  If any of

In the past this was a garbage collection activity with no topology
significance, and did not need to be synchronized. We are now making
it a topology significant event that needs to be synchronized so that
max-time is synchronously removed across the network.

- Stewart

---

From: mike shand <[email-masked]>
Date: Mon, 06 Jun 2005 08:59:13 +0100

>max-time is synchronously removed across the network.

But it IS already synchronized to the same degree that "live" LSP 
propagation is synchronized, in IS-IS at least... I assume also in OSPF. 
Remember that as soon as the first copy of the LSP ages out it performs a 
zero age purge of any other copies in the network. This propagates at the 
same rate and with the same synchronization properties as any other LSP.

However, this does raise a problem...

Ageing out of LSPs occurs asynchronously with any real topology change 
events in the network. Hence it is possible that an LSP requiring the 
largest delay happens to age out at approximately the same time as some 
real event which we are trying to protect against looping. This could have 
the effect that some routers use different values for the delay for the 
real event because they received the purge of the LSP at different points 
(we assume that even in implementations which [IMHO] wrongly do not remove 
the contents of a zero aged LSP, we would still not take notice of a delay 
value advertised in a zero age LSP). This could be minimized by recomputing 
the maximum delay every time a new LSP arrives even if it is determined 
that it is one which does not trigger an SPF. But this means we need to 
perform extra scans of the LSP database at times we would not usually do so.

I'm still not convinced that even using the set in the current SPT will 
unconditionally protect against this sort of error.

I suspect that any errors introduced by the "automatic" scheme are smaller 
than those which are very likely to be introduced by any manual scheme, 
especially when it becomes necessary (as it inevitably will) to change to 
delay values. This leads me to think that the "automatic" way is the right 
way to go, but I am still uncomfortable about it.

         Mike

         Mike

---

From: Alex Zinin <[email-masked]>
Date: Mon, 6 Jun 2005 16:39:40 -0700

Stewart,

> be consistent amongst the routers that were converging.

I meant the same announcement mechanism in my message--stick a TLV in an
LSP/LSA.

> and wanting to change the value - it just happens automatically.

I assume you mean the standard link-state database synchronization
mechanisms here. Yes, I meant to use the same in my message.

> makes such actions a synchronous event.

This is where you lost me.

Injection of info from newly joined routers and removing stale information
from unreachable routers is a solved problem. Have I missed something?

> max-time is synchronously removed across the network.

I think above you're assuming that every router would age out stale
LSPs/LSAs independently. Both IS-IS and OSPF have mechanisms to flush an
LSP/LSA from the domain once it has aged in one of the routers.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Mon, 6 Jun 2005 17:02:58 -0700

> propagation is synchronized, in IS-IS at least... I assume also in OSPF. 

Yes, in OSPF too.

> same rate and with the same synchronization properties as any other LSP.

Right. Though there maybe some momentary differences in router LSDBs, they
get synchronized within a finite period of time (absent more frequent
changes, strictly speaking).

> However, this does raise a problem...

I believe considering behavior of update-delay announcements in the light
of topological events is a wrong direction. Update-delay information has no
correlation with topological activity and only changes due to an
administrative action, and the fact that it would share the same transport
with topological information is coincidental from this perspective.

Yes, it is probable that some topological event will happen right at the
moment when an old LSP is being purged or a new one is flooded. However, it
happening won't be less probable than if the times were changed on all
routers manually, and not more probable than if they were configured via
say SNMP.

Alex

---

From: Alex Zinin <[email-masked]>
Date: Mon, 6 Jun 2005 18:20:46 -0700

> happening won't be less probable than if the times were changed on all

"won't be less probable than" -> "will be less probable than"

Alex

---

From: Bill Fenner <[email-masked]>
Date: Tue, 14 Jun 2005 16:09:34 -0400

>I will ask Bill to check WG consensus on taking this doc as a WG item.
>Please read and send your comments to the list.

After driving for 8 days across country with dogs
and baby, and taking a little time to unwind from
same (see http://pegland.net/EastCoastRoadTrip2005/ and
http://t-mobilepictures.com/BillFenner/myjournal/), it's time to see if
the WG is ready to take this on.

There's certainly been discussion on the technical content, but
let's look for consensus on the meta-issue: should this document
be a rtgwg work item?  Let's make this a 1 week WG call for comments;
both for and against (well, we don't *need* any against, but if they're
there I want to hear them!).  I'll evaluate WG consensus on June 22.

Thanks,
  Bill

---

From: Alia Atlas <[email-masked]>
Date: Tue, 14 Jun 2005 16:29:47 -0400

I think this should be a rtgwg work item.

Alia

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 14 Jun 2005 17:09:34 -0400

> there I want to hear them!).  I'll evaluate WG consensus on June 22.

Bill,

It seems to me that the whole IPFRR effort is way more complicated
than what it set out to replace, RSVP-TE FRR, when the justification
for doing IPFRR was to avoid complexity.  Regardless, here we are.

My initial thought was that Alex's internet draft covered a topic that
needed to be covered.  As the safety conditions were "fine tuned", the
draft has become a bit more complicated in that you now have to
determine if the router is Type A, B, or C with respect to a given
prefix.  A prerequisite to accepting this draft should be documenting
the existance of an efficient algorithm that makes this determination
for the entire set of prefixes.  The algorithm must also be
unencumbered by intellectual property restrictions.

In the mean time, can we let the technical discussion settle down and
have someone summarize what the microloop loop threat remains when the
mechanism Alex is proposing is used?  I'm not sure what changes if any
have come out of the discussion since the volume of messages has
obscured any conclusion of the discussion for me anyway.

Curtis

---

From: mike shand <[email-masked]>
Date: Wed, 15 Jun 2005 08:00:57 +0100

>for doing IPFRR was to avoid complexity.  Regardless, here we are.

I have a certain sympathy with that position. However, remember that the 
microloop prevention came out of addressing a problem which was not 
addressed, and which remains a problem, with MPLS-TE when used with LDP. 
i.e. the loop prevention is applicable to that environment as well.

>prefix.

That has always been the case since Alex first presented his draft. What we 
have been discussing recently is the relative merits of adopting a more 
conservative safety criteria in an attempt to avoid multi-hop loops at the 
expense of reducing the overall level of protection against any loops. My 
finding suggest that sticking with the existing safety criterion is 
actually more effective.

>  A prerequisite to accepting this draft should be documenting
>mechanism Alex is proposing is used?

The difficulty with that  is that a single metric does not give a good 
picture of what is going on. We have talked about

percentage of failures which generate no loops
percentage of the failures which without protection would produce loops 
which still produce loops wen protected

the same for percentage of destinations

the same for percentage of source destination pairs.

All the above for node failure as opposed to link failure.

The best visualization I have come up with is the diagrams I have presented 
at IETF showing a histogram across all the links of percentage of source 
destination pairs looped using no protection, PLSN as in the draft and 
PLSN, but treating type B as type C.

>  I'm not sure what changes if any

I think the bottom line of the recent discussion is that the proposed 
change to use a stricter criterion for networks containing asymmetric costs 
is counter-productive.

         Mike

---

From: "Adrian Farrel" <[email-masked]>
Date: Wed, 15 Jun 2005 16:37:58 +0100

> i.e. the loop prevention is applicable to that environment as well.

Did I miss this problem being brought to the MPLS working group?

Thanks,
Adrian

---

From: mike shand <[email-masked]>
Date: Wed, 15 Jun 2005 17:33:42 +0100

>Did I miss this problem being brought to the MPLS working group?

No, but we have just submitted a draft which describes the wider 
applicability of the microloop issue.

See:-

http://www.ietf.org/internet-drafts/draft-bryant-shand-lf-applicability-00.txt

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 15 Jun 2005 18:40:47 -0400

> i.e. the loop prevention is applicable to that environment as well.

Good point.

> finding suggest that sticking with the existing safety criterion is 

That was not the case when the draft was privately circulated prior to
initially being submitted or presented.  Originally the delay was
proportional to the distance from the failure.  Distance from the
failure is quite easy to determine and does not vary per prefix.  Type
A, B, or C varies per prefix and I'm not sure that there is an easy
way to determine it.

> >unencumbered by intellectual property restrictions.

You didn't comment on this.

> change to use a stricter criterion for networks containing asymmetric costs 

Thanks for the summary.

>          Mike

Other than some concern about whether an efficient unencumbered
algorithm to determine Type A, B, or C, I have no objections to this
being accepted as a WG document.  If there is no efficient algorithm
or no efficient unencumbered algorithm, then there is reason to at
least simplify this, possibly back to the delay based on distance
approximation that Alex first considered (but not to the WG).

Curtis

---

From: Alia Atlas <[email-masked]>
Date: Wed, 15 Jun 2005 20:00:09 -0400

Curtis,

>A, B, or C varies per prefix and I'm not sure that there is an easy

I think you are remembering the Ordered FIB installation approach.  You 
might take a look at 
http://psg.com/~zinin/ietf/rtgwg/IETF61-rtgwg-uloop-prev.ppt, which 
describes the different approaches considered.

>You didn't comment on this.

The information required is the same as for LFA.  This simply requires 
remembering the neighbors that were loop-free in the previous topology.  I 
think that this is actually a nice complement to LFA because, while it does 
require another decision per prefix, it doesn't require additional SPFs or 
equivs to be run.

Alia

---

From: mike shand <[email-masked]>
Date: Thu, 16 Jun 2005 15:20:38 +0100

>there I want to hear them!).  I'll evaluate WG consensus on June 22.

Yes, I think it should be WG document. It plays nicely with the "Basic" 
IPFFR solution. However, I would not like this to prevent us working on 
methods which give complete prevention of loops for use with IPFRR 
mechanisms which give complete repair.

On the complexity front, I think we can probably omit the type B 
destinations (treating them as type Cs). This will give slightly worse 
performance (but my simulations indicate this is quite a small change), but 
will allow the convergence to be complete after 1 rather than 2 delay 
cycles, and will avoid the need to change a FIB entry for a destination 
twice. This is probably a tradeoff worth making (since neither gives 
complete protection).

         Mike

---

From: Alex Zinin <[email-masked]>
Date: Thu, 16 Jun 2005 15:09:13 -0700

Curtis,

> being accepted as a WG document.

As Alia explained, the algorithm in the document uses the before-failure
calculations done by IP FRR. The after-failure calculations are the same
you'd need to do to find LFAs for the after-failure topology for IP FRR.
You then need to visit all prefixes, identify the type and calculate the
safe neighbors for Type-Bs. There are some straight-forward optimizations
to shorten the list of prefixes that need to be checked (e.g. early
detection of type-As and some type-Cs).

Re IPR: to the best of my knowledge, at this point I am not aware of any
patents issued to, or claims filed or being prepared by me, any other
person, or a company with regards to the algorithm documented in the draft.

--
Alex

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 17 Jun 2005 10:24:28 -0400

Alex,

Thanks for making that statement regarding IPR.

Curtis

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 20 Jun 2005 10:45:27 +0100

> describes the different approaches considered.

or look at

http://www.ietf.org/internet-drafts/draft-bryant-shand-lf-conv-frmwk-01.txt

which describes all of the methods that are being considered
and looks at how they might complement each other.

- Stewart

---

From: Stewart Bryant <[email-masked]>
Date: Mon, 20 Jun 2005 11:00:01 +0100

I agree with Mike, although I would suggest that we take a more
conservative approach.

I think that we should start by understanding the wider need
for this technology, as outlined in:

which demonstrates the applicability of the work to the MPLS WG
and to the OPS area.

When we understand those requirements, we will better understand
the context of this partial solution to the microloop problem.

My concerns in moving this to a WG item are two fold:

Firstly that adoption of this may inhibit work on one of the more
complete solutions, and secondly that although safe neighbours
clearly complements some of the other solutions, it would be
better to design it as an enhancement - to ensure a good
match - rather than to fit the rest of the solution round safe
neighbours.

- Stewart

mike shand wrote:

> performance (but my simulations indicate this is quite a small change), 
> but will allow the convergence to be complete after 1 rather than 2 
> delay cycles, and will avoid the need to change a FIB entry for a 
> destination twice. This is probably a tradeoff worth making (since 
> neither gives complete protection).
> 
>         Mike
>  
>

---

From: Alex Zinin <[email-masked]>
Date: Fri, 24 Jun 2005 10:18:29 -0700

Stewart,

I don't quite understand where you're coming from.

> I agree with Mike,

Do you mean you agree with making this a WG document?

> although I would suggest that we take a more
> conservative approach.

> the context of this partial solution to the microloop problem.

I think we understand those.

> complete solutions,

I don't see why or how it would. From the DT recommendation text:

                 Another positive aspect of the PLSN method is that it does not
   preclude later extensions to improve coverage and prevent loops for destinations
   left out by PLSN by employing other mechanisms for them (e.g. tunnel-based or
   FIB ordering).

> and secondly that although safe neighbours

I don't understand what you mean here.

--
Alex

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 24 Jun 2005 13:37:05 -0400

Alex, Bill,

All of my questions and concerns were answered so count me as agreeing
to make this a WG document.  Just in case that wasn't clear from the
prior email.

Curtis

---

From: Thomas Eriksson <[email-masked]>
Date: Mon, 27 Jun 2005 13:25:53 +0200

A bit late perhaps but I support this document becoming a work item.

Thomas