rfc2439.txt

xorp源码hg

Network Working Group                                       C. Villamizar
Request for Comments: 2439                                            ANS
Category: Standards Track                                      R. Chandra
                                                                    Cisco
                                                              R. Govindan
                                                                      ISI
                                                            November 1998


                         BGP Route Flap Damping

Status of this Memo

   This document specifies an Internet standards track protocol for the
   Internet community, and requests discussion and suggestions for
   improvements.  Please refer to the current edition of the "Internet
   Official Protocol Standards" (STD 1) for the standardization state
   and status of this protocol.  Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (1998).  All Rights Reserved.

Abstract

   A usage of the BGP routing protocol is described which is capable of
   reducing the routing traffic passed on to routing peers and therefore
   the load on these peers without adversely affecting route convergence
   time for relatively stable routes.  This technique has been
   implemented in commercial products supporting BGP. The technique is
   also applicable to IDRP.

   The overall goals are:

   o  to provide a mechanism capable of reducing router processing load
      caused by instability

   o  in doing so prevent sustained routing oscillations

   o  to do so without sacrificing route convergence time for generally
      well behaved routes.

   This must be accomplished keeping other goals of BGP in mind:

   o  pack changes into a small number of updates

   o  preserve consistent routing




Villamizar, et. al.         Standards Track                     [Page 1]

RFC 2439                 BGP Route Flap Damping            November 1998


   o  minimal addition space and computational overhead

   An excessive rate of update to the advertised reachability of a
   subset of Internet prefixes has been widespread in the Internet.
   This observation was made in the early 1990s by many people involved
   in Internet operations and remains the case.  These excessive updates
   are not necessarily periodic so route oscillation would be a
   misleading term.  The informal term used to describe this effect is
   "route flap".  The techniques described here are now widely deployed
   and are commonly referred to as "route flap damping".

1 Overview

   To maintain scalability of a routed internet, it is necessary to
   reduce the amount of change in routing state propagated by BGP in
   order to limit processing requirements.  The primary contributors of
   processing load resulting from BGP updates are the BGP decision
   process and adding and removing forwarding entries.

   Consider the following example.  A widely deployed BGP implementation
   may tend to fail due to high routing update volume.  For example, it
   may be unable to maintain it's BGP or IGP sessions if sufficiently
   loaded.  The failure of one router can further contribute to the load
   on other routers.  This additional load may cause failures in other
   instances of the same implementation or other implementations with a
   similar weakness.  In the worst case, a stable oscillation could
   result.  Such worse cases have already been observed in practice.

   A BGP implementation must be prepared for a large volume of routing
   traffic.  A BGP implementation cannot rely upon the sender to
   sufficiently shield it from route instabilities.  The guidelines here
   are designed to prevent sustained oscillations, but do not eliminate
   the need for robust and efficient implementations.  The mechanisms
   described here allow routing instability to be contained at an AS
   border router bordering the instability.

   Even where BGP implementations are highly robust, the performance of
   the routing process is limited.  Limiting the propagation of
   unnecessary change then becomes an issue of maintaining reasonable
   route change convergence time as a routing topology grows.

2 Methods of Limiting Route Advertisement

   Two methods of controlling the frequency of route advertisement are
   described here.  The first involves fixed timers.  The fixed timer
   technique has no space overhead per route but has the disadvantage of
   slowing route convergence for the normal case where a route does not
   have a history of instability.  The second method overcomes this



Villamizar, et. al.         Standards Track                     [Page 2]

RFC 2439                 BGP Route Flap Damping            November 1998


   limitation at the expense of maintaining some additional space
   overhead.  The additional overhead includes a small amount of state
   per route and a very small processing overhead.

   It is possible and desirable to combine both techniques.  In
   practice, fixed timers have been set to very short time intervals and
   have proven useful to pack routes into a smaller number of updates
   when routes arrive in separate updates.  The BGP protocol refers to
   this as packing Network Layer Reachability Information (NLRI) [5].

   Seldom are fixed timers set to the tens of minutes to hours that
   would be necessary to actually damp route flap.  To do so would
   produce the undesirable effect of severely limiting routing
   convergence.

2.1 Existing Fixed Timer Recommendations

   BGP-3 does not make specific recommendations in this area [1].  The
   short section entitled "Frequency of Route Selection" simply
   recommends that something be done and makes broad statements
   regarding certain properties that are desirable or undesirable.

   BGP4 retains the "Frequency of Route Advertisement" section and adds
   a "Frequency of Route Origination" section.  BGP-4 describes a method
   of limiting route advertisement involving a fixed (configurable)
   MinRouteAdvertisementInterval timer and fixed
   MinASOriginationInterval timer [5].  The recommended timer values of
   MinRouteAdvertisementInterval is 30 seconds and
   MinASOriginationInterval is 15 seconds.

2.2 Desirable Properties of Damping Algorithms

   Before describing damping algorithms the objectives need to be
   clearly defined.  Some key properties are examined to clarify the
   design rationale.

   The overall objective is to reduce the route update load without
   limiting convergence time for well behaved routes.  To accomplish
   this, criteria must be defined for well behaved and poorly behaved
   routes.  An algorithm must be defined which allows poorly behaved
   routes to be identified.  Ideally, this measure would be a prediction
   of the future stability of a route.

   Any delay in propagation of well behaved routes should be minimal.
   Some delay is tolerable to support better packing of updates.  Delay
   of poorly behave routes should, if possible, be proportional to a
   measure of the expected future instability of the route.  Delay in
   propagating an unstable route should cause the unstable route to be



Villamizar, et. al.         Standards Track                     [Page 3]

RFC 2439                 BGP Route Flap Damping            November 1998


   suppressed until there is some degree of confidence that the route
   has stabilized.

   If a large number of route changes are received in separate updates
   over some very short period of time and these updates have the
   potential to be combined into a single update then these should be
   packed as efficiently as possible before propagating further.  Some
   small delay in propagating well behaved routes is tolerable and is
   necessary to allow better packing of updates.

   Where routes are unstable, use and announcement of the routes should
   be suppressed rather than suppressing their removal.  Where one route
   to a destination is stable, and another route to the same destination
   is somewhat unstable, if possible, the unstable route should be
   suppressed more aggressively than if there were no alternate path.

   Routing consistency within an AS is very important.  Only very
   minimal delay of internal BGP (IBGP) should be done.  Routing
   consistency across AS boundaries is also very important.  It is
   highly undesirable to advertise a route that is different from the
   route that is being used, except for a very minimal time.  It is more
   desirable to suppress the acceptance of a route (and therefore the
   use of that route in the IGP) rather than suppress only the
   redistribution.

   It is clearly not possible to accurately predict the future stability
   of a route.  The recent history of stability is generally regarded as
   a good basis for estimating the likelihood of future stability.  The
   criteria that is used to distinguish well behaved from poorly behaved
   routes is therefore based on the recent history of stability of the
   route.  There is no simple quantitative expression of recent
   stability so a figure of merit must be defined.  Some desirable
   characteristics of this figure of merit would be that the farther in
   the past that instability occurred, the less it's affect on the
   figure of merit and that the instability measure would be cumulative
   rather than reflecting only the most recent event.

   The algorithms should behave such that for routes which have a
   history of stability but make a few transitions, those transitions
   should be made quickly.  If transitions continue, advertisement of
   the route should be suppressed.  There should be some memory of prior
   instability.  The degree to which prior instability is considered
   should be gradually reduced as long as the route remains announced
   and stable.







Villamizar, et. al.         Standards Track                     [Page 4]

RFC 2439                 BGP Route Flap Damping            November 1998


2.3 Design Choices

   After routes have been accepted their readvertisement will be briefly
   suppressed to improve packing of updates.  There may be a lengthy
   suppression of the acceptance of an external route.  How long a route
   will be suppressed is based on a figure of merit that is expected to
   be correlated to the probability of future instability of a route.
   Routes with high figure of merit values will be suppressed.  An
   exponential decay algorithm was chosen as the basis for reducing the
   figure of merit over time.  These choices should be viewed as
   suggestions for implementation.

   An exponential decay function has the property that previous
   instability can be remembered for a fairly long time.  The rate at
   which the instability figure of merit decays slows as time goes on.
   Exponential decay has the following property.

         f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2)

   This property allows the decay for a long period to be computed in a
   single operation regardless of the current value (figure-of-merit).
   As a performance optimization, the decay can be applied in fixed time
   increments.  Given a desired decay half life, the decay for a single
   time increment can be computed ahead of time.  The decay for multiple
   time increments is expressed below.

        f(figure-of-merit, n*t0) = f(figure-of-merit, t0)**n = K**n

   The values of K ** n can be precomputed for a reasonable number of
   "n" and stored in an array.  The value of "K" is always less than
   one.  The array size can be bounded since the value quickly
   approaches zero.  This makes the decay easy to compute using an array
   bound check, an array lookup and a single multiply regardless as to
   how much time has elapsed.

3 Limiting Route Advertisements using Fixed Timers

   This method of limiting route advertisements involves the use of
   fixed timers applied to the process of sending routes.  It's primary
   purpose is to improve the packing of routes in BGP update messages.
   The delay in advertising a stable route should be bounded and
   minimal.  The delay in advertising an unreachable need not be zero,
   but should also be bounded and should probably have a separate bound
   set less than or equal to the bound for a reachable advertisement.

   The BGP protocol defines the use of a Routing Information Base (RIB).
   Routes that need to be readvertised can be marked in the RIB or an
   external set of structures maintained, which references the RIB.



Villamizar, et. al.         Standards Track                     [Page 5]

RFC 2439                 BGP Route Flap Damping            November 1998


   Periodically, a subset of the marked routes can be flushed.  This is
   fairly straightforward and accomplishes the objectives.  Computation
   for too simple an implementation may be order N squared.  To avoid N
   squared performance, some form of data structure is needed to group
   routes with common attributes.

   An implementation should pack updates efficiently, provide a minimum
   readvertisement delay, provide a bounds on the maximum
   readvertisement delay that would be experienced solely as a result of
   the algorithm used to provide a minimum delay, and must be
   computationally efficient in the presence of a very large number of
   candidates for readvertisement.