Subject: [RRG] BGP path hunting, MRAI timer and Path Length Damping

From: Robin Whittle <[email-masked]>
Date: Thu, 21 Jun 2007 18:39:26 +1000

I am finalising some technical writing explaining path hunting,
based on the understanding I initially gained from Geoff's
article - but looking more closely, my understanding of what
would happen doesn't match Geoff's diagram.

I don't see how Geoff's example, with my understanding of BGP
and its MRAI timer, would lead to something resembling Tony's
explanation either.

I am keen to establish whether Geoff's explanation is realistic
or not.  My understanding of Sriram's message is that he thinks
it is not.

Tony, can you advise on this?  Anyone else?

The second question is whether the MRAI timer applies to
withdrawals.  I think it does (as I explain below), but Sriram
thinks not.

Geoff's diagram :

  http://www.potaroo.net/ispcol/2007-06/dampbgp.html
	
explains the pattern of behavior which results in a series of
longer best-path messages emanating out from the local part of
the network, followed by a withdrawal.

I am not sure about the time elapsed between the four sections
of Fig 1, which I will call A, B, C and D.

Geoff doesn't explain it in text, and Tony gives this explanation:

http://tools.ietf.org/html/draft-li-bgp-stability-01#section-1.3.1

  . . . when a prefix is withdrawn from the network, as the
  local BGP speaker receives the prefix withdrawal from a BGP
  peer it may substitute a previously received announcement
  for this prefix from a different peer in its place and
  announce this replacement route to its peers in response to
  the received withdrawal.  If this replacement path is
  subsequently withdrawn, the local BGP speaker will again
  select another previously received announcement from a
  different peer, if one exists.  This process may continue
  until the original prefix withdrawal has propagated across
  the entire routing space.

Here is my understanding, based on Geoff's diagram and Tony's
written explanation.  Is there a better explanation somewhere?

A   This is the steady state before T = 0.0, when (2) detects
    that its link to (1) goes down.

B, sort of . . .

T =  0.1 secs

   (2) sends withdrawals to (5) and (3).

   This is almost immediately after the link goes down - say
   a 0.1 second processing time after (2) determines that (1)
   is unreachable.  This is the time it takes to generate two
   withdrawal announcements.

   (3) gets the withdrawal too.  This is where my understanding
   departs from the diagram.  In B, (5) has sent an
   announcement but 3 hasn't.  I figure they would typically
   send their announcements at about the same time.

   In my understanding, at 0.1 seconds, both (5) and (3) have
   been sent the withdrawal from (2) but have not yet processed
   them.

T =  0.2 secs

    This is a 0.1 second processing delay after (5) gets the
    withdrawal  from (2), it decides that its current best path
    "5, 2, 1" is invalid and so adopts the next best path: "5,
    3, 2, 1".

    It announces this new, longer, best path (AA+) to its peers,
    and we are only interested in the announcement which goes
    out to other peer routers (upstream peers) to the top right
    of the diagram.  That AA+ triggers a cascade of such
    announcements through many other routers, perhaps across the
    entire Net, if there is no better alternative - which there
    isn't, according to this diagram.

    (5) sets its FIB to send the packets to (3) rather than (2).

      [ Sidebar on Root Cause Notification
      [
      [  My understanding of RCN (Root Cause Notification) is
      [  that with RCN, (5) would be able to tell that this new
      [  longer path is not going to work either, and neither
      [  would the other path(s) it knows about.  So with RCN
      [  (5) would now announce a withdrawal to its upstream
      [  peers, which is optimal behavior.
      [
      [  If these numbers identified routers, even without
      [  RCN, (5) could figure out that the "5, 3, 2, 1" path
      [  wouldn't work, because (2) has told (5) it can't
      [  reach (1).  However to minimise BGP messages and RIB
      [  state, these numbers identify Autonomous Systems, and
      [  there's no definite reason for (5) to assume that (3)
      [  can't reach (1) via some other router in AS (2) -
      [  although it does have to assume that AS 2 has internal
      [  routing problems if (3) can reach (1) via AS (2) but
      [  that 5's peer router in AS (2) can't.

   (5) sets its MRAI timer, so it will expire at T = 30.2
   seconds.

   (3) responds to the withdrawal it got from (2) by announcing
   a withdrawal to (5) and (4).  It doesn't use (4)'s path to
   (1) because that path flows through (3)'s own Autonomous
   System.

   (3)'s MRAI timer is also set to time out at T = 30.2 seconds
   but that does not concern us.

T =  0.3 secs

   (5) receives from (3) the withdrawal of the path to (1).
   At this point in time, (5) chooses the previously announced
   path via (4): "4, 3, 2, 1", and applies it to its FIB.
   However, (5) will not announce it because its MRAI timer has
   been set and will expire at T = 30.2 seconds.

   (4) sends a withdrawal announcement to (5).

T = 0.4 secs

   (5) processes the withdrawal it received from (4).

   Since there are no further paths available to (1) from (5),
   (5) changes its RIB state for this prefix to reflect the
   fact it has no such path - and it configures its FIB to drop
   packets addresses to the prefix.

   However, (5) does not announce anything because its MRAI
   timer is still running.

T = 30.2 secs

   (5)'s MRAI timer expires, so it sends the withdrawal to its
   upstream peers.

So in my understanding, there is a 30.2 second period of packets
being dropped, while for 30.1 seconds of this time (5) still
says it has a path "5, 3, 2, 1" for this prefix.  This may be
preferred by many other routers, even though they actually have
a longer, path (not shown) to (1).  So this may cause lost
connectivity to (1) for 30 seconds even though it has another,
much longer, link to other routers somewhere.

In my understanding, there is no strung out sequence of longer
and longer paths being announced by 5, as Geoff's diagram
depicts.  Just the first announcement at T = 0.1s of a longer
path, followed by a withdrawal at T = 30.2 seconds.  This does
not really resemble the "path hunting" pattern Geoff and Tony
refer to.

My understanding of what Geoff writes is that "path hunting"
occurs anyway, and is exacerbated in variations in the time
constant of the Minimum Route Advertisement Interval (MRAI)
Timer.  I am not sure if these are small variations of fractions
of a second from the default 30 seconds, or some other default
or configured values such as 20 to 50 seconds.  I don't see how
various values of MRAI in different routers would affect my
explanation of what happens in the situation depicted by Geoff's
diagram, other than to change the delay time to 20.2 or 50.2
seconds, for instance.

In an earlier message ("Geoff Huston's article ...") I wrote
about my understanding of Tony's Li's proposal for Path
Length Damping (PLD):

  http://tools.ietf.org/html/draft-li-bgp-stability-01#section-3.4

which involves a new algorithm looking for updates giving a
longer path than previously, (AA+ in Geoff's article) and
suppressing announcements regarding this prefix which also
extend the length of the best path, for a period of time.

I guess this would need to replace the MRAI timer's function, or
operate with longer time constants than that timer, but I don't
think Tony's I-D mentions this.

Tony's I-D

  http://tools.ietf.org/html/draft-li-bgp-stability-01#section-3.4

cites Geoff's article and includes:

  We therefore suggest that this event could be used to
  trigger a suppression period, which would allow the
  prefix to oscillate arbitrarily without propagation to
  the remainder of the network.

  When a BGP speaker found that it needed to change its best
  path for a prefix and that the new best path was longer than
  the previous best path, then it would suppress the
  advertisement of the longer AS path to its neighbor and start
  a timer.  Subsequent changes to the prefix that continue to
  lengthen the AS path would restart the timer.  If the BGP
  speaker installed a shorter best path, or undertook a local
  withdrawal it would remove the suppressed update and cancel
  the timer.  Otherwise, when the timer expired, the BGP
  speaker would advertise the result, if any.

This sounds like a great idea.  I understand that when applied
to Geoff's diagram, here is what would happen, assuming for the
moment that there was no MRAI timer:

T = 0.1 seconds

   (2) sends withdrawals to (5) and (3).

T = 0.2 seconds.

   (5) gets (2)'s withdrawal and does not announce anything,
   since its best path "3, 2, 1" is now longer than before,
   and Tony's (Geoff's?) PLD algorithm is invoked.

   (5)'s PLD timer is set to count down, lets say with a
   40 second time constant.  Absolute time of expiry will be
   40.2 secs.

   (5) changes its FIB to direct the packets to the next
   best path it knows, via (3).

   (3) gets (2)'s withdrawal too.  Since (3) has no other
    path, it announces a withdrawal to (5) and (4).

T = 0.3 seconds

   (5) gets a withdrawal from (3) and does not announce
   anything, since its best path is now longer than before:
   "4, 3, 2, 1".

   (5)'s PLD timer is reset and made to count down, lets say
   from 40 seconds.  Absolute time of expiry will be 40.3 secs.

   (5) changes its FIB to direct the packets to the next
   best path it knows, via (4).

   (4) gets (3)'s withdrawal too - and sends a withdrawal to
   (5).

T = 0.4 seconds

   (5) gets a withdrawal from (4).

   Because this eliminates the last path (5) had to (1):
   "4, 3, 2, 1", (5) needs to announce a withdrawal.

   It does so immediately, and disables the PLD timer.

   (5) configures its FIB to drop packets addressed to this
   prefix.

So with this PLD algorithm, as I understand it, there is only
one message sent by (5), and it is the correct one, sent at 0.4
seconds, not at 30.2 seconds as with current arrangements.

With PLD, (5) exhibits to its peers no false optimism about
delivering packets to (1), other than waiting for a very short
time (ensured by the PLD algorithm in the other routers, and by
the topology) to announce the withdrawal as soon as it was
certain it had was no path to (1).

Geoff wrote to the list:

> The withdrawal would propagate, or the path would stabilise.
> One way to  view it is as a more selective form of Min Route
> Advert Interval Timer.

Responding this and previous discussion of my message, Sriram wrote:

> My understanding is that MRAI does not apply to 
> explicit withdrawals (the AWs and WWs in your taxonomy).

However, my interpretation of the RFC:

  http://tools.ietf.org/html/rfc4271#section-9.2.1.1

is that the MinRouteAdvertisementIntervalTimer (MRAI Timer),
which defaults to 30 seconds (Section 10), applies to all
announcements, with no exemption for withdrawals.

  Two UPDATE messages sent by a BGP speaker to a peer that
  advertise feasible routes and/or withdrawal of unfeasible
  routes to some common set of destinations MUST be separated
  by at least MinRouteAdvertisementIntervalTimer.

So I think Sriram's understanding is incorrect.

> Did you happen to verify this based on the observed data?
> The reason I am asking is if this were implemented,
> then in your illustration of Fig. 1 (path hunting),
> all the withdraws (W) will make it quickly to Router 5.

I am not sure whether this last line refers to "this" being the
implementation of PLD or the way he thinks BGP routers already
behave, with the MRAI timer not stopping withdrawal messages.

However, the behavior Sriram goes on to describe accords with my
own interpretation, as described above, of how the routers would
behave with current BGP.

> BGP Router 5 may have sent one AA+ in response to the very first withdraw
> from Router 2 but any subsequent AA+ it tries to send will be
> held back for MRAI interval and during that time the
> other withdraws from Routers 3 and 4 will make it to Router 5
> (because they are not subjected to MRAI), 

So far, I agree with Sriram's interpretation.  I understand his
"not subjected to MRAI" as meaning that the withdrawal cascade
from (2) to (3) to (4) propagates rapidly (0.1 sec per step in
my explanation) because this is the first change regarding this
prefix in quite a long time.

However, I think Sriram believes a second, or perhaps the only
reason, the cascade is so quick is because he believes that the
MRAI timer does not apply to withdrawals.

> and hence Router 5
> will send only one AA+ and then a withdraw.

If the MRAI timer did not stop withdrawals, then the outcome
would be the same as for my understanding of what would happen
with Tony's PLD algorithm: (5) would propagate the withdrawal at
T = 0.4 seconds.

> If "not applying MRAI to explicit withdrawals" is implemented,
> then withdrawals propagate much faster than AA+ or AA0 updates, 
> hence path hunting related updates would be significantly reduced.
> I would think this is how MRAI was intended to expedite
> BGP convergence and reduce churn.

This may have been the intention, but to my understanding, the
MRAI timer delays withdrawals so they are announced at least 30
seconds after all previous announcements.  The highly meshed
topology of Geoff's diagram, which is typical of the Internet,
ensures that (5) first announces an AA+ and then waits 30
seconds before announcing the withdrawal.

Here is the summary of my current understanding.  Please correct
 it!

Geoff's diagrams don't give enough timing detail for me to
critique properly, but I think that with current BGP behavior,
the outcome for the rest of the BGP routers is really bad:

T =  0.2 sec       AA+ longer path announcement
T = 30.2 sec       Withdrawal.

Sriram seems to believe MRAI was developed with an intent to
achieve this, and thinks the RFC specifies that it should not
stop withdrawals.  But my understanding of the RFC is that MRAI
does delay withdrawals, in any circumstance like (5)'s, where it
has a next-best path which it announces first, because it hasn't
yet received a withdrawal from (3) or (4).

Tony, you co-wrote the RFC - what do you think?

   - Robin          http://www.firstpr.com.au/ip/ivip/

--
to unsubscribe send a message to [email-masked] with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg

---

From: Robin Whittle <[email-masked]>
Date: Thu, 21 Jun 2007 22:22:36 +1000

BGP is a complex system and I don't pretend to be an expert.
That doesn't stop me trying to understand patterns of behavior.

Assuming for the moment that my analysis of Geoff's Fig 1
scenario is correct, here is what happens if that Fig 1 pattern:

           |
           |
          (5)
         / | \
        /  |  \
       /   |   \
     (2)--(3)--(4)
      |
      |
     (1)

is plugged into another such structure with routers in ASes 6 to 9:

          (10) (11) (12)
            \   |   /
             \  |  /
              \ | /
               (9)
              / | \
             /  |  \
            /   |   \
          (6)--(7)--(8)
           |
           |
          (5)
         / | \
        /  |  \
       /   |   \
     (2)--(3)--(4)
      |
      |
     (1)

As before, each router is in its own autonomous system and the
same principles probably apply in general to many meshed
networks with more realistic arrangements of routers, such as
two or more routers in the same AS instead of just one as shown
above.

The upstream peers (10), (11) and (12) all get this sequence
from (9):

T =  0.4 sec  AA+      "9, 6, 5, 3, 2, 1" replacing:
                          "9, 6, 5, 2, 1".

T = 30.4 sec  AA+   "9, 7, 6, 5, 3, 2, 1".

T = 60.4 sec  Withdrawal.

Assuming my analysis is correct, and going on gut feel from
there, I would say that generally any meshed pattern of routers
will probably do much the same thing.  It propagates AA+
messages at MRAI intervals and finally a withdrawal.  The number
of AA+ messages probably depends on how many pairs of detours
and bottlenecks there are in the system.

I haven't checked, but I think this should generate four AA+
messages followed by a withdrawal, 120 seconds later than it
should have been propagated:

     (2)         (3)         (9)        (12)     /
     / \         / \         / \         / \    /   Upstream
    /   \       /   \       /   \       /   \  /    routers
  (1)---(3)---(4)---(6)---(8)--(10)---(11)-(13)----
   |
   X
   |
  (0)

If the RFC's text:

was extended to include 6 extra words:

    unless the second UPDATE is a withdrawal.

then the withdrawals would not be delayed by 30 seconds for each
stage of 4-stage the pattern above.

Then, maybe we wouldn't be so unhappy about BGP's convergence
rate and the number of messages - which are two of the primary
reasons we are having to invent a new routing and addressing
architecture.

Maybe if the sentence was changed, to:

   An UPDATE message sent by a BGP speaker to a peer that
   advertises a longer feasible route than previously
   announced to that peer for a common set of destinations MUST
   be separated by at least MinRouteAdvertisementIntervalTimer
   from the any previous UPDATE message for that common set.

   If such a message is delayed by this timer while a new
   UPDATE message for the common set would otherwise be
   sent, advertising a still longer feasible route, then
   the delayed message is replaced by the new message and
   the timer restarted.

This would let through withdrawals, shorter best path and
same-length best path messages without any delay, though perhaps
it would be best to delay any same-length messages too.

My working of the problem is below.

  - Robin

The lower system's output, from (5) is:

 T =  0.2 sec       AA+ longer path announcement: "5, 3, 2, 1"
 T = 30.2 sec       Withdrawal.

Here is what I think occurs.

T = 0.3 sec

    (6), having received the above AA+ announcement, announces
    to (9) and (7) another AA+:
    "6, 5, 3, 2, 1".  Previously it had announced
       "6, 5, 2, 1".

    (6) sets its MRAI timer to expire at 30.3 seconds.

T = 0.4 sec

!   (9), having received the above AA+ announcement, announces
!   to its upstream peers (10), (11) and (12) another A++:
    "9, 6, 5, 3, 2, 1".  Previously it had announced:
       "9, 6, 5, 2, 1".

    (9) sets its MRAI timer to expire at 30.4 seconds.

    (7) also sets its MRAI timer to expire at 30.4 seconds and
    announces a similar A++:
    "7, 6, 5, 3, 2, 1".  Previously it had announced:
       "7, 6, 5, 2, 1".

T = 0.5 sec

   (9) receives (7)'s AA+ but this doesn't alter (9)'s
   best path.

   (8) receives it as well, and this does alter its best path.
   It sets its MRAI timer to expire at 30.5 seconds and
   announces to (9):
   "8, 7, 6, 5, 3, 2, 1".  Previously it had announced:
      "8, 7, 6, 5, 2, 1".

T = 0.6 sec

   (9) receives (8)'s AA+ but this doesn't alter (9)'s
   best path.

T = 30.2 sec

   (5) announces the withdrawal to (6).

T = 30.3 sec

   (6) receives this withdrawal and its RIB is updated to the
   drop packets addressed to this prefix.

   The MRAI timer expires at this time, so (6) announces a
   withdrawal to (9) and (7).

T = 30.4 sec

   (9) receives the withdrawal and changes its RIB to have a
   new longer path.  Its MRAI timer expires at this time, and
!  so it announces its new best path AA+ to its upstream peers:
!  "9, 7, 6, 5, 3, 2, 1".  Previously it had been:
      "9, 6, 5, 3, 2, 1".

   (9) configures its FIB to forward this prefix to (7) instead
   of (6).

   (9) sets its MRAI timer to expire at T = 60.4 seconds.

   (7) receives this withdrawal and changes its FIB to drop
   packets to this prefix.

   (7) announces a withdrawal to (9) and (8), and sets its
   MRAI timer to expire at 60.4 seconds.

T = 30.5 sec

   (9) receives this withdrawal from (7) and updates its best
   path to be via (8):

   "9, 8, 7, 6, 5, 3, 2, 1".  Previously (0.1s) it had been:
      "9, 7, 6, 5, 3, 2, 1".

   (9) configures its FIB to forward this prefix to (8) instead
   of (7).

   (9) does not announce anything, because the MRAI timer has
   not yet expired.

   (8) also receives the withdrawal from (7) and so announces
   a withdrawal to (9).  (8) also configures its FIB to drop
   packets addressed to this prefix.

T = 30.6 sec

   (9) receives the withdrawal from (8) and updates its RIB
   to have no best path for the prefix.  It updates its FIB
   to drop packets addressed to this prefix.

   It does not announce anything, because its MRAI timer is
   still running.

T = 60.4 sec

!  (9)'s MRAI timer expires, so it announces the withdrawal
!  to its upstream peers.

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 21 Jun 2007 08:24:18 -0400

> written explanation.  Is there a better explanation somewhere?
[of path hunting]

"Delayed Internet routing convergence" by Labovitz, Ahuja, Bose and  
Jahanian.  (IEEE/ACM Transactions on Networking, June 2001.  A  
version appeared in the SIGCOMM 2000 proceedings also I think.)

--John

---

From: [email-masked]
Date: Thu, 21 Jun 2007 08:51:51 -0400

I have learned the following about MRAI since I sent my email yesterday. 
It appears that the recommendation about whether or not to 
apply MRAI to withdrawals went through a change from 
RFC 1771 to RFC 4271 (4271 obsoletes 1771).
The reasons for the change are not clear to me. 
The latest recommendation per RFC 4271 is not to apply
MRAI to withdrawals. RFC 4271 was issued relatively recently
in January 2006. And as late as June 2005 another RFC 4098 
(on benchmarking BGP convergence) cited RFC 1771 and
stated that MRAI did not apply to explicit withdrawals (in Section 3.12):  

3.12.  MinRouteAdvertisementInterval (MRAI)

    Definition:
       (Paraphrased from RFC 1771) The MRAI timer determines the minimum
       time between advertisements of routes to a particular destination
       (prefix) from a single BGP device.  The timer is applied on a
       pre-prefix basis, although the timer is set on a per-BGP device
       basis.

    Discussion:
       Given that a BGP instance may manage in excess of 100,000 routes,
       RFC 1771 allows for a degree of optimization in order to limit the
       number of timers needed.  The MRAI does not apply to routes
       received from BGP speakers in the same AS or to explicit
       withdrawals.  RFC 1771 also recommends that random jitter is
       applied to MRAI in an attempt to avoid synchronization effects
       between the BGP instances in a network.  In this document, we
       define routing plane convergence by measuring from the time an
       NLRI is advertised to the DUT to the time it is advertised from
       the DUT.  Clearly any delay inserted by the MRAI will have a
       significant effect on this measurement.

Based on this one might infer that BGP routers have implemented
"not applying MRAI to withdrawals" for a fairly long time (prior to RFC 4271).
To what extent have router vendors updated and deployed the MRAI 
per RFC 4271 (so that MRAI does indeed apply to withdrawals)?   
Tony: Can you please share with us your thoughts on this?

I certainly like the PLD proposal and also Geoff's additional suggestions
in his recent paper, and suggest that a careful further 
investigation be done of these methods to see if there are 
any inter-dependencies with the way MRAI is implemented.
I like to see "MRAI not applied to withdrawals" for reasons I
stated in my previous email (although it goes against RFC 4271).
I also think that Robin's explanations about inherent MRAI-based damping
of AA+ type of updates is further strengthened if
MRAI did not apply to withdrawals.  

Sriram
-------------------------------------------------------------

---

From: Robin Whittle <[email-masked]>
Date: Fri, 22 Jun 2007 01:22:40 +1000

Thanks Sriram for this quote from RFC 4098:

  http://tools.ietf.org/html/rfc4098#section-3.12

It makes no reference to RFC 1771's specific exclusion of
withdrawals from the MRAI mechanism.  However, that exclusion
was in a separate paragraph so the authors may have missed it or
considered it unimportant.

The text you quoted was added to the I-D between February and
June 2002.

http://tools.ietf.org/html/draft-ietf-bmwg-conterm-02#section-4.5.2

Below my signature is how the RFC 1771 text:

  http://tools.ietf.org/html/rfc1771#section-9.2.3.1

differs from the same section in RFC 4271:

I wonder if router behaviour really did change before January
2006's RFC 4271.

The change regarding MRAI and withdrawals is in the the I-D
versions which lead to RFC 4271 17 (Jan 2002) and 18 (Oct 2002):

http://tools.ietf.org/html/draft-ietf-idr-bgp4-17#section-9.2.1.1
http://tools.ietf.org/html/draft-ietf-idr-bgp4-18#section-9.2.1.1

Tony, can you tell us the background for this change to the
scope of the MRAI timer?  I imagine there was a strong reason,
since the removed text talks about avoiding long-lived
black-holes as being the reason to exempt withdrawals from the
MRAI delay system.

Thanks John for the pointer to the "Delayed Choice in Routing
Convergence" paper of late 2000 or early 2001, I guess:

http://www.cs.toronto.edu/syslab/courses/csc2209/06au/papers/bgp.pdf

I read some of it with great interest.  I don't have time to
read it all now.

On page 186 the authors write that some routers used a single 30
second timer for all updates to a particular peer, which tended
to greatly slow down convergence.

This paragraph makes me think their research was in the days
when most or all routers did not delay withdrawals with the MRAI
timer:

   At least one major router vendor has made an implementation
   decision to apply MinRouteAdver to both announcements and
   withdrawals. A discussion of the motivation and engineering
   tradeoffs for applying MinRouteAdver to withdrawals is
   outside the scope of this paper and remains an active area
   of our current research.

So this research probably is not directly relevant to the
pattern of behavior I worked out in the previous messages.

I would really appreciate someone with more experience with BGP
checking how I worked out that behavior.

If that pattern is the sole or primary cause of "path hunting",
then it seems that this significant problem can be attributed to
the change in the BGP RFC, maybe the I-Ds which lead to it and
whatever decisions "one major router vendor" made around late 2000.

  - Robin

RFC 1771 >> RFC 4271

   The parameter MinRouteAdvertisementInterval determines the
   minimum amount of time that must elapse between advertisement

+  and/or withdrawal

   of routes to a particular destination from a single BGP
   speaker. This rate limiting procedure applies on a
   per-destination basis, although the value of
   MinRouteAdvertisementInterval is set on a per BGP peer basis.

   Two UPDATE messages sent from a single BGP speaker that
   advertise feasible routes

+  and/or withdrawal of unfeasible routes

   to some common set of destinations received from BGP speakers
   in neighboring autonomous systems must be separated by at
   least MinRouteAdvertisementInterval. Clearly, this can only
   be achieved precisely by keeping a separate timer for each
   common set of destinations. This would be unwarranted
   overhead. Any technique which ensures that the interval
   between two UPDATE messages sent from a single BGP speaker
   that advertise feasible routes

+  and/or withdrawal of unfeasible routes

   to some common set of destinations received from BGP speakers
   in neighboring autonomous systems will be at least
   MinRouteAdvertisementInterval, and will also ensure a
   constant upper bound on the interval is acceptable.

   Since fast convergence is needed within an autonomous system,

-  this procedure does not apply for routes receives from other
-  BGP speakers in the same 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 to routes sent to internal peers.

-  To avoid long-lived black holes, the procedure does not apply
-  to the explicit withdrawal of unfeasible routes (that is,
-  routes whose destinations (expressed as IP prefixes) are
-  listed in  the WITHDRAWN ROUTES field of an UPDATE message).

   This procedure does not limit the rate of route selection,
   but only the rate of route advertisement.  If new routes are
   selected multiple times while awaiting the expiration of
   MinRouteAdvertisementIntervalTimer, the last route selected
   SHALL be advertised at the end of
   MinRouteAdvertisementIntervalTimer.

---

From: "Ricardo V. Oliveira" <[email-masked]>
Date: Thu, 21 Jun 2007 11:55:01 -0400

FYI, a more recent and exaustive study of path exploration (or path  
hunting) can be found here (IMC'06):
http://www.cs.ucla.edu/~rveloso/papers/pathrank.pdf

--Ricardo

---

From: Robin Whittle <[email-masked]>
Date: Fri, 22 Jun 2007 04:00:33 +1000

Hi Ricardo,

Thanks for this link:

  Quantifying Path Exploration in the Internet
  Ricardo Oliveira, Beichuan Zhang, Dan Pei, Rafit Izhak-Ratzin
  and Lixia Zhang

I looked over it quickly and my impression that it is a good
survey of actual Internet behavior.  There is mention of the
MRAI timer, mainly to say that some routers do not have it
turned on.  There's no mention of the change in the BGP standard
for this timer's behavior, or how some routers in use today
probably use the old system and others the new, regarding
whether or not the MRAI timer delays withdrawal messages.

I am hoping someone can check my manual attempt to predict
behavior of routers in my previous messages in this thread.

---

From: Tony Li <[email-masked]>
Date: Thu, 21 Jun 2007 12:39:23 -0700

<co-chair hat on>

Hi all,

I'm very pleased to see such energy and interest.  I think it's a  
very fruitful topic.  That said, I also feel compelled to point out  
that most of this discussion would be MUCH more appropriate on the  
idr mailing list.  I'm asking that folks redirect the discussion  
there and will send my own replies there too.  For folks not on the  
mailing list, you can subscribe here:

	http://www.ietf.org/html.charters/idr-charter.html.

Please note that there is also an archive, so if you are just  
subscribing, any subsequent  conversation may be found there.

In general, I'd say that work within the existing BGP framework  
rightfully belongs on that mailing list, especially when it comes  
down to dealing with mechanisms within BGP.  The RRG mailing list  
would be more appropriate for routing architecture issues,  
alternative inter-domain protocol work, or major conceptual changes  
to BGP.  Yes, I realize that there's a large fuzzy gray line between  
these two and no, I'm not trying to discourage the discussion, it's  
just that it would be better to have this discussion where more BGP  
folks might be likely to participate.

Thanks very much.

</co-chair hat on>

Regards,
Tony

---

From: "John G. Scudder" <[email-masked]>
Date: Thu, 21 Jun 2007 16:31:50 -0400

[replies directed to [email-masked]; rrg bcc'd]

> black-holes as being the reason to exempt withdrawals from the

Well I'm not Tony but a perusal of the IDR mailing list from 2002  
quickly reveals the below message which introduces substantially the  
same text as is found in RFC 4271.  In the cited text, Pedro argues  
that one cannot readily distinguish in BGP between "good news" and  
"bad news" and thus it makes no sense to treat withdraws differently.

(N.b. the archive at ietf.org seems to only extend back to June 1,  
2003.  I've already suggested the IDR co-chairs look into this.)

--John

> To: [email-masked]
> Subject: BGP4 -17 version
> Date: Mon, 25 Mar 2002 07:31:31 -0800
> From: Yakov Rekhter <[email-masked]>
> Sender: [email-masked]
>
> Folks,
>
> In view of the last paragraph in the attached, how about if 9.2.1.1
> be replaced with the following:
>
>    9.2.1.1 Frequency of Route Advertisement
>
>    and/or withdrawal of routes to a particular destination by a
>    BGP speaker to a peer. This rate limiting procedure applies on
>    a per-destination basis, although the value of
>    Two UPDATE messages sent by a BGP speaker to a peer that advertise
>    feasible routes and/or withdrawal of unfeasible routes to some
>    common set of destinations MUST be separated by at least
>    MinRouteAdvertisementInterval. Clearly, this can only be achieved
>    precisely by keeping a separate timer for each common set of
>    destinations. This would be unwarranted overhead.  Any technique
>    which ensures that the interval between two UPDATE messages sent
>    from a BGP speaker to a peer that advertise feasible routes
>    and/or withdrawal of unfeasible routes to some common set of
>    destinations will be at least MinRouteAdvertisementInterval,
>    and will also ensure a constant upper bound on the interval is
>    acceptable.
>
>    either (a) the MinRouteAdvertisementInterval used for internal
>    peers SHOULD be shorter than the MinRouteAdvertisementInterval
>    used for external peers, or (b) procedure describe in this
>    section SHOULD NOT apply for routes sent to internal peers.
>
>    This procedure does not limit the rate of route selection, but
>    only the rate of route advertisement. If new routes are selected
>    multiple times while awaiting the expiration of
>    MinRouteAdvertisementInterval, the last route selected SHALL be
>    advertised at the end of MinRouteAdvertisementInterval.
>
>
> ------- Forwarded Message
>
> Date:    Tue, 05 Mar 2002 10:50:02 -0800
> From:    Pedro Roque Marques <[email-masked]>
> To:      Alex Zinin <[email-masked]>
> cc:      <[email-masked]>
> Subject: Re: RFC Violation
>
> Alex Zinin writes:
>
> > Pedro,
>
> >  I see your point. Note that when you are sending a WITHDRAWN, you
> > know it is a bad news.
>
> Alex,
> A link up event will often cause a router to send withrawns as it
> changes it's best path from one that it's policy and/or ibgp flooding
> rules allow it to advertise to one that is rejected.
>
> The inverse is true for a link down event...
>
> I still maintain that it is not possible in BGP to distinguish if an
> update corresponds to a link up/down event... or what information you
> wish to send fast/slow.
>
> I also believe that it is a major mistake to threat advertisements
> differently than withrawns, specially from a queuing/timing point of
> view. The only thing you are going to get out of that is weird
> blackholes and more instability...
>
> AFAIK, no major vendor implements their advertisement
> rate-controller/queueing in a way as to threat updates and withrawns
> differently.
>
>   Pedro.
>
> ------- End of Forwarded Message

---

From: Tony Li <[email-masked]>
Date: Thu, 21 Jun 2007 16:56:57 -0700

Hello again Robin,

> reasons we are having to invent a new routing and addressing

I don't believe that we have anything like consensus on that view.   
In fact, rough consensus (as of Prague) was quite the contrary:  
convergence and messaging _can_ be handled without architectural  
changes.

Regards,
Tony

---

From: [email-masked] (Noel Chiappa)
Date: Fri, 22 Jun 2007 09:46:31 -0400 (EDT)

> From: Tony Li <[email-masked]>

    >> BGP's convergence rate and the number of messages - which are two of
    >> the primary reasons we are having to invent a new routing and
    >> addressing architecture.

    > rough consensus (as of Prague) was quite the contrary: convergence and
    > messaging _can_ be handled without architectural changes.

Was that really the conclusion, as of Prague? I thought the only thing that
people agreed on was that the growth rate of the forwarding/routing tables,
in the static case (i.e. pure size, ignoring dynamic issues) was *technically
feasible* (which is not the same thing as 'economically feasible', n.b.).

I thought there was still significant concern about the dynamics... I mean,
it is a truism that as the network gets larger, the inter-event time for
topology changes goes down, and the stabilization time goes up, and the two
do have to cross somewhere...

	Noel

---

From: Tony Li <[email-masked]>
Date: Fri, 22 Jun 2007 10:06:43 -0700

> feasible* (which is not the same thing as 'economically feasible',  

Yes, the consensus was that the dynamics do NOT require architectural  
changes.  This was based on the discussion during the routing area  
meeting.

> do have to cross somewhere...

Yes, there's "significant concern", primarily coming from the  
operations community.  While decreasing the total data space by  
decreasing DFZ prefixes seems like a beneficial side effect of  
architectural change, it seemed sensible to also pursue some of the  
optimizations to the existing architecture.  Since those changes  
would seem to have significant benefits, this seems like it was a  
reasonable approach.

Regards,
Tony