Subject: Fwd: I-D ACTION:draft-zinin-microloop-analysis-00.txt

From: Alex Zinin <[email-masked]>
Date: Fri, 8 Oct 2004 14:36:51 -0700

Folks-

 This draft is a result of a discussion we had among a few folks (Alia, Don,
 Mike, Stewart, et al).

 My goal with this document was to try and analyze formation of microloops,
 plus identify the scenarios where they will not form, and categorize scenarios
 where they normally will.

 The next goal was to see if we can do something in the scenarios where
 microloops normally form. I didn't try to get 100% coverage though (it's likely
 to require tunnels).

 Hopefully this should help the discussion on the list.
 
-- 
Alex
http://www.psg.com/~zinin

This is a forwarded message
From: [email-masked] <[email-masked]>
To: [email-masked]
Cc: 
Date: Friday, October 8, 2004, 12:37:39 PM
Subject: I-D ACTION:draft-zinin-microloop-analysis-00.txt

===8<==============Original message text===============
A New Internet-Draft is available from the on-line Internet-Drafts directories.

	Title		: Analysis and Minimization of Microloops in Link-state 
			  Routing Protocols
	Author(s)	: A. Zinin
	Filename	: draft-zinin-microloop-analysis-00.txt
	Pages		: 10
	Date		: 2004-10-8
	
Link-state routing protocols (e.g. OSPF or IS-IS) are known to
   converge to a loop-free state within a finite period of time after a
   failure. It is normal, however, to observe short-term loops during
   the period of failure propagation, route recalculation, and
   forwarding table update, due to the asynchronous nature of link-state
   protocol operation. This document provides an analysis of formation
   of such microloops and suggests simple mechanisms to minimize them.

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-zinin-microloop-analysis-00.txt

To remove yourself from the I-D Announcement list, send a message to 
[email-masked] with the word unsubscribe in the body of the message.  
You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce 
to change your subscription settings.

Internet-Drafts are also available by anonymous FTP. Login with the username
"anonymous" and a password of your e-mail address. After logging in,
type "cd internet-drafts" and then
	"get draft-zinin-microloop-analysis-00.txt".

A list of Internet-Drafts directories can be found in
http://www.ietf.org/shadow.html 
or ftp://ftp.ietf.org/ietf/1shadow-sites.txt

Internet-Drafts can also be obtained by e-mail.

Send a message to:
	[email-masked].
In the body type:
	"FILE /internet-drafts/draft-zinin-microloop-analysis-00.txt".
	
NOTE:	The mail server at ietf.org can return the document in
	MIME-encoded form by using the "mpack" utility.  To use this
	feature, insert the command "ENCODING mime" before the "FILE"
	command.  To decode the response(s), you will need "munpack" or
	a MIME-compliant mail reader.  Different MIME-compliant mail readers
	exhibit different behavior, especially when dealing with
	"multipart" MIME messages (i.e. documents which have been split
	up into multiple messages), so check your local documentation on
	how to manipulate these messages.

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

===8<===========End of original message text===========

ENCODING mime
FILE /internet-drafts/draft-zinin-microloop-analysis-00.txt
_______________________________________________
Rtgwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rtgwg

---

From: Olivier Bonaventure <[email-masked]>
Date: 13 Oct 2004 11:33:08 +0200

Alex,
>  where they normally will.

I have several comments on your new draft.

1. Introduction

Microloops can also occur between non-directly connected routers in the
case of asymetrical link weights. Although most links use the same IGP
weights in ISPs, in some cases asymetrical weights are used, sometimes
due to configuration errors, but sometimes for valid operational
reasons. 

2.2 

The cost of checking the safety condition inside a router appears to
compute the SPT for each of its neighbors after each IGP change. Am I
right ?

3.2 Transition types

For the types B transitions, it is unclear to me how often such types
occur in real networks. I would be interested by quantitative
information on the amount of Type B cases in ISPs. I guess this be
placed in section 2.6

I think that it would be useful to provide one example of types B1 and
types B2 transitions in the draft.

3.3 Basic loop prevention mechanisms

For a change that affects a Type B route, the cost appears to be two
updates of the FIB, a transient one and the finale one.

My main concern/question over the draft are the delays mentionned in
this section. First, the starting time of the timers is unclear. Is it
the time when the ISIS/OSPF packet indicating the event is received or
something else ?

Second, most routers do not recompute their SPT immediately when a link
state packet indicating a change is received. Instead, they wait for the
expiration of a timer whose interval may be fixed or depend on the
previous runs of the SPF computation. The interactions between this
timer and the two timers that you propose should probably be discuss

Third, you implicitly assume that the fault-propagation-time (which
includes the time to compute the SPT and check the safety condition) is
below 2 seconds. There have been few studies on the time required to
propagate a link state packet inside ISP networks, but this time may be
high in some environments. The two publically available studies related
to this topic are :

@Unpublished{Villfor_Operator:2004,
  author = 	 {H. Villfor},
  title = 	 {Operator Experience from ISIS Convergence Tuning},
  note = 	 {Presented at RIPE47},
  month =	 {January},
  year =	 2004
}
http://www.ripe.net/ripe/meetings/ripe-47/presentations/ripe47-routing-igp.pdf

@Unpublished{Alaettinoglu:ISIS:2001,
  author = 	 {C. Alaettinoglu and S. Casner},
  title = 	 {ISIS Routing on the Qwest Backbone: a Recipe for Subsecond
ISIS Convergence},
  note = 	 {NANOG23, http://www.nanog.org/mtg-0202/cengiz.html },
  month =	 {October},
  year =	 2001
}

Best regards,

Olivier Bonaventure
-- 
CSE Dept. UCL, Belgium - http://www.info.ucl.ac.be/people/OBO/

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 13 Oct 2004 11:32:54 -0400

In message <1097588577.1283.39.camel@pcobo>
> due to configuration errors, but sometimes for valid operational

Transient loops can also occur where the IGP has symmetric costs if
multiple IGP changes occur.  You need both an up and a down transition
and a few routeres to react to it in a different order.  It could be
an up on one link very close to a down on another or a very fast
down/up transition on one link (which should never occur) or a very
quick up/down (which sometimes can't be helped).  Flapping links
caused by either intermittent failure or degredation that is close to
a threshhold of link acceptance can do it.  With logical links going
throught the same physical equipment (TDM, WDM) this can occur on
multiple links simultaneously.  This was more of a problem when some
routers converged very slowly a decade ago compared to today.

Asymetric costs just make it possible for the loop to form as a result
of a single transition.  Otherwise a minimum of two closely spaced
transitions is required.

Microloops probably still occur, but are brief enough to be very hard
to observe, certainly impossible looking only at the packet counters
on a link.  You can only see it if you have a way to record queue
utilization (particularly capture peak utilization or queue overflow)
since loops today may only last a few RTT of the loop.  Queue overflow
on low utilization links occurs if the RTT of the loop is small
compared to the RTT of the traffic crossing it and/or the loop
persists for more than a few RTT, so sometime you know it has
happenned just by the non-zero SNMP counters on links with very low
utilization that happen to form a cycle.  A decade ago when routers
ran their SPF every couple of seconds (or more) this "curriosity" was
often observed but not considered a problem since a rare few seconds
of loss was considered acceptable.

For example, in the early days of the T3-NSFNET (early 1990s) link
costs were symetric, link utilizations were low (20-30% at most), and
evidence of loops were observed.

These things are fairly rare but if you are trying to get IGP
restoration times that are comparable to path RTTs with some form of
local protection and have built in consequences for exceeding it (like
SLA violation refunds for example), then they might be a real problem.

Of course, with assymetric costs, an isolated failure can cause a loop
so loops will be more common.  This is what Alex is trying to address
in draft-zinin-microloop-analysis.

I don't think any mechanism on top of a link state protocol short of
end to end tunneling such as RSVP/TE would completely solve the
problem of intermittent failing links.

Curtis

---

From: Alex Zinin <[email-masked]>
Date: Wed, 13 Oct 2004 12:49:23 -0700

Olivier,

> due to configuration errors, but sometimes for valid operational

I purposely avoided looking at the asymmetric link cost case as a rather rare
situation. I do have it on my to-do list for my next flight, which will be next
week :)

> compute the SPT for each of its neighbors after each IGP change. Am I

With reasonable optimizations, if the router already implements basic IP FRR,
the cost should be not be very high. Here's some considerations:

 - if the node implements IP FRR, the LFA BF condition should be precomputed
   and known a priori

 - checking the safety condition for type-As costs almost nothing, since
   after the regular SPT you know new primaries

 - checking the no-LFA-BF part of type-Cs also has low overhead

 - for the remaining cases (checking the DS AF part of the safety condition)
   it is necessary to calculate SPT only for neighbors that were LFA BF for
   some destinations that need to be checked for type-B/C.

If the implementation is more advanced and does incremental SPF, it may as
well decide to compute SPTs for each of its neighbors.

> information on the amount of Type B cases in ISPs. I guess this be

Alia modified its tool to do coverage analysis by this method. We're working on
normalizing the data and making sense of it ;) I hope we'll have some
interesting data by DC.

> types B2 transitions in the draft.

I'll note this for the next rev.

> updates of the FIB, a transient one and the finale one.

That is correct. The first one reroutes traffic to safe hops, and the
second installs the final next-hops.

> the time when the ISIS/OSPF packet indicating the event is received or

your start the timer once you know you're type-B or type-C for that
destination.

> timer and the two timers that you propose should probably be discuss

Yes, this is probably worth noting. The sub-second IGP convergence effort drove
some implementations towards the behavior where they react quickly to a small
"stand-alone" set of topology changes, and then start to increase the delay to
ensure robustness if the network topology becomes unstable. This is consistent
with the FRR and microloops prevention.

> high in some environments. The two publically available studies related

Difference in topologies, link delays, and implementations is exactly why those
delays were made configurable variables.

On the other hand, I will note that for a given failure, only a subset of nodes
will be actually affected (will change their next-hops), and it will be even
smaller subset where the delays will actually matter. In other words, excluding
pathological cases (e.g. networks made of big rings), we're interested in
clusters of nodes, not the whole network, so practically, 2 secs is likely to
be enough, and I would even expect it to go lower as more implementations
support subsecond convergence. Yet again, it's configurable...

Alex

---

From: mike shand <[email-masked]>
Date: Wed, 13 Oct 2004 22:31:22 +0100

>second installs the final next-hops.

As we discussed, the document should say that for ECMP where not all of the 
splits meet the "type A" criterion, you need to treat it as "type B". i.e. 
have an interim FIB update to the safe path(s) and delay as for type B.

         Mike

---

From: Thomas Eriksson <[email-masked]>
Date: Thu, 14 Oct 2004 18:08:57 +0200

Just a short comment on one of the references below.

>The two publically available studies related
>to this topic are :

This link is to the presentation by Clerance Filsfis. The actual document 
referenced can be found at:

http://www.ripe.net/ripe/meetings/ripe-47/presentations/ripe47-routing-isis.pdf

Thomas

---

From: Alia Atlas <[email-masked]>
Date: Thu, 14 Oct 2004 12:34:51 -0400

Curtis,

>problem of intermittent failing links.

I'm a bit puzzled by this.  Certainly, with TE, how adaptive a tunnel is to 
topology changes can dampen the effects.  That is just because the CSPF 
won't be run for a while and thus won't use the link.

Presumably, a similar effect could be gained by dampening the reporting of 
the link into the IGP.  For instance, the exponential back-off based on how 
recently the link has flapped.

Alia

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 15 Oct 2004 11:56:15 -0400

> won't be run for a while and thus won't use the link.

There are two separate timers.  One is referred to as the resilience
timer and is used to reroute when the existing path fails (with FRR
handling the traffic until the reroute occurs).  The other is
adaptivity timer and is used when new resources become available.  The
resilience timer is very short.  The adaptivity timer is very long (in
practice it can be tens of minutes to a few hours).  

If a failure occurs, the TE FRR backup is supposed to go into use
within 50 msec.  If a very large number of tunnels must reroute, the
new primary tunnels may all be available within seconds, after which
the old is taken down and the FRR backup goes down with it.  If the
link flaps the long adaptivity timer alone results in the link being
avoided but past history can be used in the decsion to move a tunnel
from a stable path to one of lower cost to further insure a flapping
link is not used.

> recently the link has flapped.

If you are running a link state IGP you probably don't want to keep
the link down for 10 minutes to a few hours.  If you have massively
overprovisioned, then maybe you do want to hold a link down for a very
long time period after it seems to be usable.

With TE you can (and should) apply a brief holddown, but then
advertise the link as back up and let each ingress decide when/if to
use it.  Our implementation (the "adaptivity linear" method which
allows two peicewise linear relationships to be configured) allow the
percentage of link utilization to be used in the decision as to when
to schedule an initial CSPF and then uses the percentage link
utilization gained to make the decison as to whether to actually
reroute now or schedule the reroute farther in the future.  This way
if the primary path for one ingress/egress is too heavily loaded it
will move back to a better path quickly but if for another
ingress/egress there is not much to be gained by moving to another
path, the reroute will be deferred for a very long time (we suggest up
to hours, but it could be indefinite) in the interest of not moving
around traffic often (avoiding the brief delay discontinuity and
reordering of a reroute, though it is lossless) in addition to
avoiding any use of a flapping path except where there is no
sufficiently uncongested alternate.

Other TE implementations are free to take similar approaches with TE
but this sort of more intelligent use of the available resources is
not possible if IGP forwarding is used.  This just goes back to the
question of whether TE is useful, and if someone feels that it is not,
then how about when a link is persistently down or when a link is
flapping.

I vaguely recall the anecdote that "Too much optimizing of transient
behevior might lead to blindness".  I think that Yakov deserved credit
for that (but its not worth searching 10 year old email archives to
find out for sure).  Completely avoiding microloops in a link state
IGP may be unacheivable.  The draft Alex came up with is simple enough
and does afford some improvement so it doesn't seem to meet the
criteria for "too much optimizing of transient behevior" and Alex is
probably safe.  Anyone trying to completely eliminate microloops in a
link state IGP probably isn't.

Curtis

---

From: Alia Atlas <[email-masked]>
Date: Fri, 15 Oct 2004 12:18:40 -0400

>from a stable path to one of lower cost to further insure a flapping

Certainly using the past history allows other routers to decide not to use 
the flapping link.  If all of the IP traffic is expected to be carried 
inside these TE tunnels, then doesn't this suffer from the same problem of 
not wanting to keep a link down for 10 minutes to a few hours?  I.e., the 
link may be up, but not carrying substantial real traffic, because the TE 
tunnels avoid it.

>link state IGP probably isn't.

Certainly the longer that the network hasn't converged after a failure, the 
more vulnerable the network is to a second failure.

Alia

---

From: Curtis Villamizar <[email-masked]>
Date: Fri, 15 Oct 2004 13:56:22 -0400

> link may be up, but not carrying substantial real traffic, because the TE 

Each ingress decides separately and each decides on a per path basis
whether there is a better path.  If you need to use a link that has
recently gone down, at least you will be making minimal use of it.

> more vulnerable the network is to a second failure.

The ability to support SRLGs helps, but even with SRLG, the real world
is full of examples of correlated failures for which you couldn't
reasonably expect SRLG to be configured.  Off the top of my head,
these range from an Amtrak train taking out the fiber on both sides of
the track in 192 in a major fiber run in NJ, to floods in the midwest
in 1993 submerging entire POPs, to hurricanes in NC taking out fiber,
to the Raritan bridge collapsing and breaking fiber, to an earthquake
in San Diego taking out three of four fiber paths, most if not all of
these affecting every major provider since many the same right of
ways.  There have been plenty of examples, way too many to list.

No SLA promising extremely low outages based on expectation of fast
restoration covering every possible scenario will ever go unbroken for
very long.  Also TCP's end-to-end congestion avoidance will still come
in handy for the rare but inevitable extensive outages.

Curtis

ps - my last message wasn't intended to go out to the list, but no
serious harm done.  We are a bit off topic though.

---

From: Alex Zinin <[email-masked]>
Date: Fri, 15 Oct 2004 17:07:05 -0700

Right. Here's an excerpt from our discussion:

>  For ECMP, we have the following possibilities:
> 
>   1) All NPs are safe
>   2) Some NPs are safe, some not
>   3) All NPs are not safe, but they are B1's (one safe-hop makes
>      all unsafe NPs B1's)
>   4) All NPs are C's
> 
>  Cases 1, 3, and 4 are simple.
>  For case 2, I would install safe NPs and schedule SPF for a later time
>  to give the rest of NPs a chance to get installed.

Alex