Subject: [Idr] Future of route flap dampening spec

From: Pekka Savola <[email-masked]>
Date: Tue, 9 Nov 2004 19:57:04 +0200 (EET)

Hi,

Just a bit of food for thought: is there something we want to do with 
the route flap dampening spec?  Move to DS, deprecate, spin in place, 
...?

Apparently there is at least one implementation claiming to be 
compliant to the spec while penalizing both at the withdraws and 
re-advertisements.  That's one thing at least that might warrant 
clarification; there may be other issues which may call for 
clarification.

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

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

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 10:47:13 -0800

Pekka Savola writes:

> Hi, Just a bit of food for thought: is there something we want to do
> with the route flap dampening spec?

Move to historic and publish "flap damping considered harmful" RFC.

  Pedro.

---

From: Dorian Kim <[email-masked]>
Date: Tue, 9 Nov 2004 13:55:16 -0500

> Move to historic and publish "flap damping considered harmful" RFC.

Agreed on moving it to historical.

It's served its purpose.

-dorian

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 14:19:28 -0500

> clarification; there may be other issues which may call for 

The major deviation from the spec in all of the implementations that I
am aware of is failure to implement the following as per spec:

  4.4.3 Per Route State

   Information must be maintained per some tuple representing a route.
   At the very minimum, the NLRI (BGP prefix and length) must be
   contained in the tuple.  Different BGP attributes may be included or
   excluded depending on the specific situation.  The AS path should
   also be contained in the tuple by default.  The tuple may also
   optionally contain other BGP attributes such as
   MULTI_EXIT_DISCRIMINATOR (MED).

   The tuple representing a route for the purpose of route flap damping
   is:

      tuple entry            default      options
      -------------------------------------------
      NLRI
        prefix               required
        length               required
      AS path                included     option to exclude
      last AS set in path    excluded     option to include
      next hop               excluded     option to include
      MED                    excluded     option to include
                                          in comparisons only

   The AS path is generally included in order to identify downstream
   instability which is not being damped or not being sufficiently
   damped and is alternating between a stable and an unstable path.
   Under rare circumstances it may be desirable to exclude AS path for
   all or a subset of prefixes.  If an AS path ends in an AS set, in
   practice the path is always for an aggregate.  Changes to the
   trailing AS set should be ignored.  Ideally the AS path comparison
   should insure that at least one AS has remained constant in the old
   and new AS set, but completely ignoring the contents of a trailing AS
   set is also acceptable.

The AS path should be included in the comparison by default.  Current
implementations do not even support using AS Path as part of the key.

This results in the type of behavior complained about in "Route Flap
Damping: Harmful?" <http://www.nanog.org/mtg-0210/flap.html>.  The
slides there say:

  Why does this happen?
  ...
  Route flap damping parameter setting
      - Cisco/Juniper punishes virtually all route changes

Anyone have an idea as to how to reflect that in the spec?  Should I
add a section describing known non-compliant implementations.

Note that over the years a few people have sent corrections to the RFC
which I haven't bothered to make.  In some cases what is written in
the RFC is wrong in some fine details but implementers have coped with
it just fine.  The failure to include AS Path is the major shortcoming
of existing implementations and causes operational problems.

I don't know what percentage of providers have opted to just turn of
damping and what percentage still have it enabled.  Providers continue
to ask that this feature be implemented.

Curtis

---

From: Dorian Kim <[email-masked]>
Date: Tue, 9 Nov 2004 14:26:16 -0500

> to ask that this feature be implemented.

[note, annectdotal evidence only]

It seems like most large providers have shifted away from dampening their
customer prefixen and are only dampening their peers at this point.

-dorian

---

From: Pekka Savola <[email-masked]>
Date: Tue, 9 Nov 2004 21:40:51 +0200 (EET)

In a slightly different order,

> to ask that this feature be implemented.

I think it's important to notice that different kinds of providers 
likely have entirely different perspective to the need for damping and 
where it should be applied (Tier-1 transit, smaller transit, edge ISP, 
...).

In the ideal case, I'd guess folks think that the 1st hop ISPs should 
be doing flap dampening, but doing so further upstream may not make 
sense (especially if the 1st hop ISPs would do the dampening :).

> add a section describing known non-compliant implementations.

Further than that, Juniper penalizes both advertisement/withdrawal, 
penalizing by default just after 1.5 flaps instead of 3.  That's not 
good.

This particular incompliance could be made more explicit by:

In 4.8.3, "Processing Route Advertisements",

OLD:
    If an damping structure exists, the figure of merit is decayed and
    the figure of merit and last time updated fields are updated.  A
    decision is now made as to whether the route can be used immediately
    or needs to be suppressed for some period of time.

NEW:
    If an damping structure exists, the figure of merit is decayed and
    the last time updated field is updated; figure of merit doesn't increase.
    A decision is now made as to whether the route can be used immediately
    or needs to be suppressed for some period of time.

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 15:04:18 -0500

> customer prefixen and are only dampening their peers at this point.

That means that it is in use.  Which means it would be premature to
move it to historic.

I do agree that route flap damping **as currently implemented** (in
violation of the spec), is harmful.  I'd rather we fixed the
implementations but that would require pressure from providers on
their vendors to make the fix.  Fixing the known problem in the spec
itself wouldn't be a bad idea either (yes - I know - I should be doing
that).

Curtis

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 15:13:33 -0500

> sense (especially if the 1st hop ISPs would do the dampening :).

No one seems to want to damp their own customers and exend an outage.
OTOH if someone else has a route that can't keep stable they'd rather
eliminate it.

The original motivation for Route Flap Damping was massive instability
coming from parts of the Internet, some quite distant, in the 1993
time frame.  Some of the problem was sloppy circuits (lossy,
unreliable) and part was due to router problems in those days.  

Some of that (poor network administration) still goes on.  I don't
know if we still have any blocks of routes that withdraw and
readvertise 1,500 a day like we did in the old days.

>     or needs to be suppressed for some period of time.

Very good suggestion.

Curtis

---

From: Dorian Kim <[email-masked]>
Date: Tue, 9 Nov 2004 15:21:31 -0500

> itself wouldn't be a bad idea either (yes - I know - I should be doing

I think there's a third consideration here.

Even with fixed spec and fixed implementations, is flap dampening necessary
in today's Internet? Things have changed considerably since the days when
most routers were based on woefully underpowered 68K processors. 

As you say, the current state is pretty harmful.

I'm not sure if we've gone beyond needing flap dampening, but it seems 
like we could live without it currently.

This is probably a bit short sighted perspective, but given the current state of 
things, and the fact that it's getting to be non-trivial to get vendors fix their 
implementations, I do wonder if it's better to just declare victory and move on..

-dorian

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 15:47:44 -0500

In message <[email-masked]>
Dorian Kim writes:
> Even with fixed spec and fixed implementations, is flap dampening
> necessary in today's Internet? Things have changed considerably since
> the days when most routers were based on woefully underpowered 68K
> processors.

The point was always that route flap damping gave the option to get
rid of route announcements that just keep going up and down all day.
Continuous heavy flap can slow BGP convergence when a real change
occurs (not that BGP has ever been know to converge quickly).

Some providers still see a need to do this.

> like we could live without it currently.

I don't want to make a value judgement on this but its in use.  I do
think it could be useful and not harmful if implemented as per spec.

> This is probably a bit short sighted perspective, but given the
> current state of things, and the fact that it's getting to be
> non-trivial to get vendors fix their implementations, I do wonder if
> it's better to just declare victory and move on..
>  
> -dorian

There are people who could force the issue at providers for any of the
given major vendors.  I just don't happen to be one of them (the
people at a provider that can force the issue).

Curtis

---

From: Pekka Savola <[email-masked]>
Date: Tue, 9 Nov 2004 22:58:04 +0200 (EET)

> OTOH if someone else has a route that can't keep stable they'd rather

Think about a problem in the link, which is causing problems.  This is 
only applicable to those customers which are multihomed, and hence no 
outage should occur unless I'm missing something..

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 16:47:01 -0500

> outage should occur unless I'm missing something..

In the better providers single homed customers are static routed on
the last hop specificly so that the route is never withdrawn.  The
problem is when the customer is multihomed to another provider.  If
the link is intermittent, then the provider instead of holding it down
will bring it back up and announce it as soon as it appears feasible
again.  There may be no BGP to the customer.  If there is, then it
isn't damped.  That's just what providers do.  Ideally the IGP would
hold down an adjacency that bounced a lot (the rfc does mention that
even though it primarily addresses BGP).

Curtis

---

From: Jeffrey Haas <[email-masked]>
Date: Tue, 9 Nov 2004 17:11:48 -0500

On Tue, Nov 09, 2004 at 04:47:01PM -0500, Curtis Villamizar wrote:
> Ideally the IGP would

I believe at a previous NANOG, Cengiz (for Packet Design) presented
a study of IGP convergence issues.

I don't recall a lot of that presentation, but I believe one bit
of speculation was that applying route damping to flapping LSAs
was a potentially sane way to deal with that particular problem space.

-- 
Jeff Haas 
NextHop Technologies

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 14:19:00 -0800

Curtis Villamizar writes:

> The major deviation from the spec in all of the implementations that
> I am aware of is failure to implement the following as per spec:

I don't see how adding the as-path to the key fixes the problem...

While BGP is reconverging it may just as well change state a few
times maintaining as-path... example neighoring as is using MEDs and
has a big mesh: second best med election may cause the route to go up
and down in rapid succession.

It also seems to me that adding it may create a much much worse
problem; that would mean maintaining history for a large number of
as-path combinations that a prefix may experience when being deleted.

It seems a non-starter...

  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 18:02:10 -0500

In message <[email-masked]>
> It seems a non-starter...

There was speculation on whether the amount of memory would be too
great from the start.  Two things came of that.  One was to include
the ability to configure it off (to ignore the AS path).  The second
was the observation that a smart implementation could throw away 
those entries that were the oldest in order to bound memory
consumption.

The common case is where a small number of routes, less than 5% of
routes advertised account for the vast majority of route churn.  An
uncommon case is where something very bad happenned a few hops away
and a very large number of prefixes cycled through a substantial set
of AS paths.  In this case the smart implementation that had the means
to bound the consumption of memory would at worst toss out history.

It would avoid suppressing routes just becuase there was a large set
of potential paths and one path went down.

Quite a lot of information is stored with BGP routes already.  AS path
usually effectively incurs 4 bytes per route because it is a pointer
to an AS path struct that is shared by many routes.  Each history
struct would be key size (prefix and AS path) plus figure-of-merit,
time-update, config block pointer, reuse list traversal pointers (2).
Seems like 28 bytes per history entry.

Curtis

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 16:57:07 -0800

> those entries that were the oldest in order to bound memory

I would interpret that as saying that a route only gets penalized if
it has an attribute change w/ the same as-path or if the route gets
withdrawn and gets advertised back with the same as-path.

It changes the current model but it still penalizes events that are
perfectly ok. So it doesn't solve the problem, imho...

The real issue is to first define what is the goal. What kind of
events and situations are do we want to be dampen... to me the answer
is far from clear. Once we understand that collectivly then maybe we
can try to figure out if a given algorithm does or not meet the goal.

> routes advertised account for the vast majority of route churn.

That observation apears to be confirmed by existing measurements.

>  An
> of AS paths.

A path being deleted by the originator cycles through a substantial
set of as-paths if you are observing it from a highly interconnected
as. So i disagree with you here that this is uncommon. 

>  In this case the smart implementation that had the
> means to bound the consumption of memory would at worst toss out
> history.

> of potential paths and one path went down.

But those multiple paths can all share the same as-path... i've seen
situations where one med change in one as (which doesn't propagate
meds outbound) causes 3 flaps and the route to be dampened by its
peer. This is quite nasty...

It would be nice to approach this problem from the point of view of
trying to identify what types of events should be dampened and how to
really distinguish them correctly from normal routing behaviour.

  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 21:19:52 -0500

In message <[email-masked]>
> can try to figure out if a given algorithm does or not meet the goal.

Your interpretation is close.

The idea is to penalize any given route/AS-path only once when it is
no longer being used.  If dozens of other AS paths are advertised and
withdrawn or replaced they get penalized only once.

If a single event ocurs, then the desired AS-paths are penalized once.

If a single prefix keeps switching between two prefixes, both will get
penalized and suppressed.  If one peering is switching between two AS
paths and another peering maintains a constant path, the constant path
will be used even if the others are otherwise more preferable.

> as. So i disagree with you here that this is uncommon. 

Bad word choice or insufficient context on my part.

Maybe I should replace "An uncommon case is where ..." with
"accounting for a far lesser amount of churn is the case where ...".

> peer. This is quite nasty...

Each flap must have a different AS path.  If nothing changed, the peer
doesn't advertise a change.  If the 3 flaps have 3 different AS paths,
then each is penalized once.

> really distinguish them correctly from normal routing behaviour.

Please reconsider what you wrote since you had misunderstood the use
of the AS-path in computing the penalty.  You may no longer feel that
we need to "start over from first principles".

I'd also like to remind you that this in not discussion of a change in
the spec, but rather a discussion of the RFC as it is currently
written, but not correctly implemented.

Curtis

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 18:47:07 -0800

Curtis Villamizar writes:

> no longer being used.  If dozens of other AS paths are advertised
> and withdrawn or replaced they get penalized only once.

> If a single prefix keeps switching between two prefixes, both will
> get penalized and suppressed.

In that case one must maintain multiple <key, merit, bookkeeping>
data. You say one may be "smart" about it and drop some... which then
gives a different behaviour. I don't think this is an actractive
option. Undeterministic behaviour is really not something i would
consider a feature.

>> But those multiple paths can all share the same as-path... i've
>> seen situations where one med change in one as (which doesn't
>> propagate meds outbound) causes 3 flaps and the route to be
>> dampened by its peer. This is quite nasty...

> Each flap must have a different AS path.  If nothing changed, the
> peer doesn't advertise a change.  If the 3 flaps have 3 different AS
> paths, then each is penalized once.

advertise -> withdrawl -> advertise -> withdrawl ...

> of the AS-path in computing the penalty.  You may no longer feel
> that we need to "start over from first principles".

I do believe that it is necessary. It is not evident to me that the
option you point out in the spec, of including as-path in the key,
leads to an improvement.

> I'd also like to remind you that this in not discussion of a change
> in the spec, but rather a discussion of the RFC as it is currently

I'm not going to argue the definition of what is "correctly
implemented"...

The only reason the internet works at all is because implementors
ignored the parts of 1771 that proven in the field to be drawbacks
(igp synchronization comes to mind). No disrespect to the authors of
1771 or to the authors of flap damping. The best we can hope for is
for authors to write down the best idea of consensus given what is
known at the time... but we must be able to modify those
specifications as new data and problems exist.

You may be correct that adding as-paths to the damping key is the
silver bullet, but i don't see it... and i think your chances of
convinving me or other implementors would increase if you can explain
how the proposal matches a problem definition.

regards,
  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 09 Nov 2004 23:37:10 -0500

In message <[email-masked]>
> option. Undeterministic behaviour is really not something i would

Undeterministic in the event of a network disaster is not a big deal.
If you toss the entries that are oldest or with lowest metric you
won't be tossing anything that you just added and you are tossing
history for the most stable prefixes that you have any history on.
This is done across the entire set, not across a single prefix.

Anyway, this smarter allocation is outside of the scope of the
document.

> advertise -> withdrawl -> advertise -> withdrawl ...

Please give an example where one MED change results in "advertise ->
withdrawl -> advertise -> withdrawl ..." where the same AS-path is
withdrawn multiple times.

> option you point out in the spec, of including as-path in the key,

One change (one down peering) can cause a very large number of updates
downstream.  If each causes the same prefix to be penalized it is
incorrectly suppressed.  That behaviour is considered "harmfull".

Considering the AS-path eliminates this problem.  If this behavior is
considered harmfull and we eliminate this behavior, its an
improvement.

> I'm not going to argue the definition of what is "correctly

Implemented as per the spec.

> how the proposal matches a problem definition.

Note that the spec allows the current behaviour to be offerred as a
configured option so please get off the soapbox about implementors
ignoring the spec and doing whats right.

Curtis

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 20:59:15 -0800

> Undeterministic in the event of a network disaster is not a big

I'm not talking about any disaster... within normal operation you can
get many paths flipping between as-paths. The ammount of state for
that must be bound... if, when you hit whatever limit, the behaviour
changes, this is underterministic behaviour that is very hard to
troubleshoot.
 
> Anyway, this smarter allocation is outside of the scope of the

The feasibility of what you propose depends on the resource
consumption that it takes. I don't think it is outside the scope at all. 

> withdrawn multiple times.

AS X has an ibgp mesh. It receives a path originated by AS1 advertised
with multiple meds in different places. AS X border routers only know
the lowest MED route. When that route flaps, all other ibgp mesh
routers that have an alternate path do advertise their own path and
then proceed to withdraw it if they see a better MED. The AS X border
router to another AS Y can see a sequence of update -> withdrawls w/
the same as-path.

Same thing can happen w/ other attributes such as local-pref.

> One change (one down peering) can cause a very large number of
> updates downstream.  If each causes the same prefix to be penalized
> it is incorrectly suppressed.  That behaviour is considered
> "harmfull".

Indeed. btw: lets be clear. It is paths that get penalized not
prefixes. With the current behaviour one down peer only makes the
prefix unavailiable if it is close to the source where you are likely
to see same as-paths.

> Considering the AS-path eliminates this problem.  If this behavior
> is considered harmfull and we eliminate this behavior, its an
> improvement.

I don't think you have answered the objections i raise...

imho better improvement is to disable damping. Does it do anything
useful ? Empirical evidence suggests that networks are much better off
without it.

> Implemented as per the spec.

These two statements, above and bellow seem contradictory to
me. Specially coupled with the assumption that the resource
consumption of other alternatives are outside of the scope, it seems
to me that the most reasonable approach for an implementation today is
to ignore as-path.

> configured option

  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 10 Nov 2004 00:48:49 -0500

In message <[email-masked]>
> changes, this is underterministic behaviour that is very hard to

The point is that you have to get a very large number of AS-path
advertised and withdrawn for a very large number of prefixes for there
to be a problem with allocating too much memory.  That would qualify
as a network disaster.

> consumption that it takes. I don't think it is outside the scope at all. 

A protocol spec need only point out that memory consumption can be an
issue.  It need not provide the solution to that issue.  It helps to
know that a feasible solution exists.  One such solution is add more
memory, and another involves using memory more wisely.

> Same thing can happen w/ other attributes such as local-pref.

Sounds like an implementation bug.  When one is route is withdrawn
from within the IBPG, another BGP peer should announce the next best
route to IBGP immediately.  The peer on the other side of the network
sees no change within the MinInterval period.

If the best IBGP route goes away, you propogate a route you already
know to IBGP immediately.  You propogate a route change that you
learned to EBGP after a delay.  This avoids the problem you just
mentioned and prevents inconsistent routes within IBGP.

> useful ? Empirical evidence suggests that networks are much better off

There is no evidence of harmful effects if implemented as per the
spec.  There is only evidence of harmful effects with the
non-compliant implementation and it is a harmful effect that was
warned about in the spec before that emperical evidence existed.
Violating the spec in this way has a predicable harmful effect and it
has been observed.

If you want to disable damping that's OK with me.

> > Note that the spec allows the current behaviour to be offerred as a

The spec requires you to implement both options and allows the current
behavior to be configured.  It also states that the default should be
to consider AS-path.

Curtis

---

From: Pedro Roque Marques <[email-masked]>
Date: Tue, 9 Nov 2004 22:13:14 -0800

Curtis Villamizar writes:

>> AS X has an ibgp mesh. It receives a path originated by AS1
>> advertised with multiple meds in different places. AS X border
>> routers only know the lowest MED route. When that route flaps, all
>> other ibgp mesh routers that have an alternate path do advertise
>> their own path and then proceed to withdraw it if they see a better
>> MED. The AS X border router to another AS Y can see a sequence of
>> update -> withdrawls w/ the same as-path.
>>  

> route to IBGP immediately.  The peer on the other side of the
> network sees no change within the MinInterval period.

If you assume that MinAdvInterval is used then
a) it is typically used in ibgp also, as per spec.
b) it is unclear when the interval period starts. 

Some implementations start the interval when the first event occurs
and delay the advertisement... others start it at any possibly
unrelated event and have an undeterministic delay.

> learned to EBGP after a delay.

That doesn't match reality in terms of deployments... You may get all
the delays to line up and you may not.

Claiming that is an implementation bug is probably not going to
help. It is delibrate behaviour with which you may agree or not. I
personally don't believe that there is "one correct behaviour" that is
optimal in all circunstances.

  Pedro.

---

From: Curtis Villamizar <[email-masked]>
Date: Wed, 10 Nov 2004 11:44:20 -0500

In message <[email-masked]>
> optimal in all circunstances.

Whether or not we call it a bug, this has been discussed long ago.  If
it isn't in the BGP spec we have an ommission.  Way back some
implementations advertised a route into IBGP even if it learned a
better route from IBGP specificly to avoid this.  The functionality
was changed to reduce the number of routes in IBGP routers but it was
noted that if this was done it shouldn't be counted in any of the
timers so that the change was not visible external to the AS.

Possible the only remnant of that is the paragraph below in section
"9.2.1.1 Frequency of Route Advertisement".

   Since fast convergence is needed within an autonomous system,
   either (a) the MinRouteAdvertisementIntervalTimer used for internal
   peers SHOULD be shorter than the MinRouteAdvertisementIntervalTimer
   used for external peers, or (b) the procedure describe in this
   section SHOULD NOT apply for routes sent to internal peers.

It is also the reason that in discussion of whether there should be a
separate and shorter MinRouteWithdrawInterval than the
MinRouteAdvertisementIntervalTimer the withdraw interval wouldn't be
set to zero.

Whether you want to call it a bug or not, the behavior you describe
does not conform to the above paragraph in BGP, although it does
specify a SHOULD rather than a MUST.

If we continue this discussion of how the BGP timers should be set, we
should start a separate thread.

Your point that bug or not, implementations do it is valid.

Using the AS-path as part of the key for flap history fixes a
problem.  It doesn't fix this problem.

Curtis