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

From: Tony Li <[email-masked]>
Date: Thu, 21 Jun 2007 13:03:13 -0700

Hi Robin,

On Jun 21, 2007, at 8:22 AM, Robin Whittle wrote:

> The text you quoted was added to the I-D between February and
> June 2002.
>
> I wonder if router behaviour really did change before January
> 2006's RFC 4271.
>
> 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.

No, I'm sorry, I wasn't paying close attention at the time, as I was  
focused elsewhere.  Yes, having withdrawals subject to MRAI is sub- 
optimal because of the black-hole issue.  Think about how this  
compounds as it transits numerous ASes.

That said, implementing MRAI precisely per the spec turns out to be  
decidedly non-trivial.

One significant complication is policy.  After a BGP speaker  
completes its best path computation, it then proceeds to compute its  
updates to its neighbors.  Policy may be applied at this point, and  
the BGP speaker may decide that it is not allowed to send its best  
path to one or more of its neighbors.  However, it may also decide to  
advertise its best path to another set of its neighbors.  Thus, the  
BGP speaker may not know whether or not it needs to send a withdrawal  
until after it has completed its best path selection and is doing  
update computation.  This becomes awkward because if the MRAI does  
apply, then the speaker should start a timer for that prefix and for  
that particular set of neighbors.  This gets complicated in a hurry,  
and can also consume a non-trivial amount of state.

For this reason, I would not be surprised if implementations did not  
actually follow the letter of the spec and simply applied MRAI more  
broadly.

> 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.

No, it's only one cause.  Path hunting is the result of diffractive  
wavefronts that affect both updates and withdraws.  Please see our  
stability spec for some additional explanation, or come to the IDR  
meeting in Chicago and see our talk, complete with illustrations of  
path hunting behaviors.

Tony

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

---

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
>
>    The parameter MinRouteAdvertisementInterval determines the
>    minimum amount of time that must elapse between 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
>    MinRouteAdvertisementInterval is set on a per BGP peer basis.
>
>    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.
>
>    Since fast convergence is needed within an autonomous system,
>    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 15:40:59 -0700

On Jun 21, 2007, at 5:51 AM, [email-masked] wrote:

> 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'm afraid that I can't claim to have a useful opinion.

I can tell you that historically, certain implementations never  
implemented MRAI at all, and another implementation did a very  
simplistic implementation.  However, my involvement at the  
development level basically stopped in 1994, except for a very brief  
stint in 2005.

It would be far more accurate if the current maintainers of  
implementations were to step up and describe the behavior of their  
implementations currently.  Yes, I realize that there are competitive  
pressures that work against this, so some may be understandably  
reluctant.

Regards,
Tony

---

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

On Jun 21, 2007, at 5:24 AM, John G. Scudder wrote:

> On Jun 21, 2007, at 4:39 AM, Robin Whittle wrote:
>> Here is my understanding, based on Geoff's diagram and Tony's
>> 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.)

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

Tony

---

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

Hi Robin,

On Jun 21, 2007, at 1:39 AM, Robin Whittle wrote:

> Tony, can you advise on this?  Anyone else?

I'll try.

> 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.

The first thing to understand is that there is no absolute standard  
of time in any of this.  BGP (and routers in general) are 'soft' real- 
time systems.  That is, given a task to do, they will get around to  
it, but it will frequently be a 'best effort' approach, and not  
scheduled to a precise moment.  Other computations within the  
protocol and outside of the protocol in other management functions  
may cause significant time variances in event latency.

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

We should note that at this point, AS 5 should have paths as follows:

2: 2 1
3: 3 2 1
4: 4 3 2 1

> 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.

Again, this would be ideal...  Reality is that you have asynchronous  
systems, updates are not computed simultaneously, and can be delayed  
for a variety of reasons.

>    (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.

Recall 5's path table from above.  After processing the update from  
(2), it's path table should look like:

3: 3 2 1
4: 4 3 2 1

Since 5 and 3 are not synchronized at all, there's a significant race  
between the withdrawal from 3 and the advertisement of "5 3 2 1" by (5).

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

In figure B, we see (5) advertising its alternate path.  It has  
processed the withdrawal from 2, but not processed the to-be- 
delivered withdrawal from 3.

> 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.

First, that is *exactly* path hunting.

You're assuming that 5 implements MRAI and doing so fairly  
precisely.  If 5 does not implement MRAI, you'd see exactly the set  
of updates in Geoff's diagram.

> 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.

You just need a slightly richer topology to create more interesting  
race conditions.

> II 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.

The assumption was that this would subsume MRAI.

> 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.

Exact ownership of the algorithm isn't clear to me.  It's been kicked  
around a bit and I thought I heard of it from someone, but I checked  
with them and they denied it.  In any case, I'll explicitly  
relinquish any claim to it.  I'm much more interested in getting it  
deployed...

> 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.

Sounds right.

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

Co-edited and really just for 1771.

As always, I think that the RFC is a fine goal, and that implementors  
frequently take short cuts that may or may not be warranted.  I'm not  
throwing rocks at them because frankly, many of those rocks would end  
up back in my lap.  As I noted earlier, implementing MRAI per the  
letter of the spec is non-trivial, and I sympathize with those who  
decided not to implement it.  On the flip side, I'm also leery of  
having a system that has no built-in protections against persistent,  
rapid oscillation.  If there are no protections built in, then some  
poor network operator will be awakened at 4am with a router that is  
melting down under the update load.  I've done that too and wouldn't  
wish that on anyone.  Thus, I think we have a responsibility to  
provide a better set of mechanisms.

Regards,
Tony

---

From: Robin Whittle <[email-masked]>
Date: Fri, 22 Jun 2007 18:27:44 +1000

Hi Tony,

Thanks for your response.  My knowledge of BGP is shallower than
probably everyone on this list.  I hope to understand BGP and
the behavior of the BGP system better.  Maybe I can contribute
some useful ideas or provoke helpful discussion.

I am glad to have worked out those examples and found what you

> First, that is *exactly* path hunting.

with the qualification that actual behavior varies a lot due to
timing variations, topology, router implementation details,
configuration etc.

I also understand that the term "path hunting" extends to the
broader patterns which resemble reverberation in acoustics - of
series of typically longer-path announcements for a prefix,
often at about 30 second intervals, which are later followed by
a withdrawal.

Your I-D also states that "path hunting" occurs when a prefix is
first advertised, but that seems pretty natural and hard to
prevent.  I don't think this would be as destructive as the MRAI
timer holding back a withdrawal for 30 seconds just after an AA+
has been sent.

"Path hunting" after a first advertisement is a consequence of
the path-vector protocol.  Maybe your proposed Path Length
Damping would be marginally effective at reducing the
propagation of sub-optimal "best paths" sometimes before the
final, stable, optimal "best path", by expediting the
announcements of shorter paths and withdrawals, and delaying
longer path announcements.

> The assumption was that this would subsume MRAI.

I am reading the second version of your ID now:

  http://tools.ietf.org/html/draft-li-bgp-stability

and I see Geoff is a co-author and that you have a section
"Deprecate MRAI".

Perhaps you could add to the "Path Hunting" section the history
of the MRAI timer's changing specification - as discussed in the
last day or so - and the statement from 2002 that few router
vendors implemented the RFC 1771 version of it.

Does the apparent failure of Flap Damping coincide with the
general change from (I guess) late 1990s MRAI compliance with
RFC 1771 to the problematic RFC 4271 mode of also stopping
withdrawals?

I think it would also be helpful to add minimal example of the
mechanism, as I tried to work it out for single and multiple
systems.  All that is needed is:

           (3)         (6)
           / \         / \
          /   \       /   \       Upstream
(1)--X--(2)---(4)---(5)---(7)---> routers

to show how it generates a prompt AA+, a 30 second delayed A++
and a 60 second delayed withdrawal.  Also, I could show how the
new algorithm would result in a much better outcome.

I can write a concise account of this, for an appendix of your
I-D if you like.  I would base it on the exact timings as I did
before, but add the qualification that in reality, timings would
not be so exact, but the behavior would be broadly similar.

>From the 01 version of your and Geoff's I-D:

   (39% of activity involves a pair of updates inside 31
    seconds.)

   Only 28% of the updates for the month are not part of any
   sequence, while 26% of updates are part of a coupled update
   pair, and 46% of updates are part of sequences of 3 or more
   updates.

So more than 2/3 of activity is seems clearly to be associated
with delays caused by the MRAI timer in a small triangle of
routers/ASes, or in more complex mesh structures.  Getting rid
of that mechanism would greatly reduce the burden of messages
and speed up the propagation of withdrawals.  Sequences of
multiple messages might be replaced by a single message, which
is more informative, and propagates quickly.

> Exact ownership of the algorithm isn't clear to me.  It's been
> kicked around a bit and I thought I heard of it from someone,
> but I checked with them and they denied it.  In any case, I'll
> explicitly relinquish any claim to it.  I'm much more
> interested in getting it deployed...

Now I understand from messages on this list that the MRAI
function is typically not implemented in a way which lets
through withdrawals quickly, and looking at Geoff's analysis, it
seems to me that some changes as you suggest would make a really
significant reduction in message volumes and convergence time.

> As I noted earlier, implementing MRAI per the letter of
> the spec is non-trivial, and I sympathize with those who
> decided not to implement it.  On the flip side, I'm also
> leery of having a system that has no built-in protections
> against persistent, rapid oscillation.  If there are no
> protections built in, then some poor network operator will
> be awakened at 4am with a router that is melting down under
> the update load.  I've done that too and wouldn't wish that
> on anyone.

I entirely agree, and unless something is done, the rising tide
of prefixes and delayed, reverberated, unnecessary AA+ messages,
with the much delayed withdrawals, will swamp all existing
transit and multihomed border routers.  All Internet users
collectively pay for running and replacing these routers.

> Thus, I think we have a responsibility to provide a better set
> of mechanisms.

Yes, but it seems to me the old RFC 1771 had a much better MRAI
specification than what router vendors were generally
implementing by 2002 or so, and better than is mandated by RFC 4271.

Thanks John for the excerpt from the IDR list archives.

>> > 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.
>>

I don't understand these statements enough to criticise them.

>> 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 am a newbie to BGP, but the behavior of path length hunting is
a major burden on all the routers, so I think that while the
above statement may have some theoretical truth to it, the
practical situation is that delaying the withdrawals is more
more trouble than it is worth.

>> I also believe that it is a major mistake to treat
>> 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...

This is written by someone who presumably knows far more about
BGP than I do, but I don't see why this would be true.

>> rate-controller/queueing in a way as to threat updates and
>> withrawns differently.
>>
>>   Pedro.

Lets say we have 500,000 prefixes.  Do we have a single down
counter for each prefix?  I guess so.  As far as I know, the
same announcements go to all peers.

This is a major challenge to implement.  It is either a massive
number of downcounters each with its own pointers to whatever it
affects, or some kind of linked list of events to remember in
the future, which could get very long, and would require tricky
methods to take things out of and to incrementally chew through
and take action upon as time passes by.

There would never be 500,000 timers active at once, so maybe it
could be implemented by having a pool of downcounters, say a few
thousand, which are used by the first instances which need them
and which are returned to the pool once they time out or no
longer needed.

Maybe there could be 4,000 down counters and each instance which
wanted another down counter when the 4,000 are all busy would
have its details and a time-stamp put into a queue.  That would
function as a timer and from the point of view of each instance.
  (However, then clearing the timer means finding the pointer in
he queue and setting it to zero.)  The end of the timer period
would be when its pointer appeared at the exit of the queue.
The router wouldn't bother emptying that queue while it was so
busy as to be running 4,000 MRAI-like down-counters, which would
only be for brief periods.

Then there is the question of each router's message queue to
each peer being throttled via TCP, with the software being able
to find messages in the queue and delete them if something else
happens after they were put in the queue.

It seems there is now general agreement that Path Length Damping
is a worthwhile goal.  This is a slightly fancier version of the
old (RFC 1771) MRAI specification.

Yet by 2002, we are told that Cisco, Juniper et. al. had given
up on following RFC 1771's strict instructions to exempt
withdrawals from the MRAI mechanism.

They presumably didn't do this lightly.  I guess it was either
that the cost of fully implementing RFC 1771's MRAI spec was
either prohibitive, considering all the other things the CPU is
trying to do - and/or that some engineers had already decided
that there was little or no value in treating withdrawals
differently from advertisements of feasible paths.

Now the cost of this simplification in implementations - now
mandated by the RFC 4271 - is either unacceptable or so costly
that the simple MRAI function needs to be replaced by something
fussier.

CPUs and memories of newer routers have become faster, so maybe
it is easier now to have the more complex MRAI-like timer.  On
the other hand, there are now far more prefixes and maybe more
peers it has to be implemented for.

Implementing a more complex MRAI-like timer in new firmware
upgrades to older routers may be prohibitive.

So I guess the trick is to find the simplest solution which will
solve the problem.

Here are my thoughts on the various algorithms:

RFC 1771 MRAI
-------------

Data:   "most recently sent update"
        "most recent update not yet announced"
        Timer down counter

[ Is update a
[ withdrawal?  Yes: Announce immediately and clear the counter.
[                   Write it to "most recently sent update".
[
[             No:

                 Counter set? No: Announce update, save it as
                                  "most recently sent update"
                                  and set timer to count down.

                              Yes: Store update in "most
                                   recent update not yet
                                   announced".

When timer
counts down:      If "most recent update not yet announced"
                  differs from "most recently sent update", then
                  announce "most recently received update not
                  yet announced" and write this to "most
                  recently sent update".

RFC 4271 MRAI
-------------

This is the same as the above, minus the first section marked
with '['.

This is simpler logic, but I don't see that it involves any less
state than the RFC 1771 version.

Path Length Damping
-------------------

Data:   "most recently sent update"
        "most recent update not yet announced"
        Integer: "previously announced update length"
        Timer down counter

Update:    (Treat withdrawal as having zero length.)
           Compare this update's length with "previously
           announced update length".

           Write this update's length to "previously announced
           update length".

           Was new update longer?

              Longer:  Write it to "most recent update not
                       yet announced".  Set timer to count down.

              Same or
              shorter: Send update, write it to "most recently
                       sent update" and clear counter.

When timer
counts down:      Announce "most recently received update not
                  yet announced" and write this to "most
                  recently sent update".

This requires storing an extra 16 bit integer for each prefix on
each interface.  I can't think of a simpler solution.

I don't know enough about routers to estimate the real
implementation costs of these, but I don't see why there was
such resistance to implementing the RFC 1771 MRAI timer.

It would be interesting to know what the difficulty was -
because those difficulties may still be important and might
prevent the adoption of Path Length Damping or some other
mechanisms as your I-D suggests.

By the way, I have a web page pointer to this discussion, which
started on the RRG list and moved to here at the IDR list:

http://www.firstpr.com.au/ip/sram-ip-forwarding/#BGP_hunting_MRAI_disc

and am trying to maintain a set of papers and proposals
regarding improvements to BGP, and analysis of its problems:

http://www.firstpr.com.au/ip/sram-ip-forwarding/#BGP_improvements

The list starts with this I-D.

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

---

From: "tom.petch" <[email-masked]>
Date: Fri, 22 Jun 2007 12:29:18 +0200

You could also look at RFC4276, the BGP4 implementation report, which
gives some details for four implementations.

Tom Petch

---

From: "John G. Scudder" <[email-masked]>
Date: Fri, 22 Jun 2007 13:20:55 -0400

Robin,

On Jun 22, 2007, at 4:27 AM, Robin Whittle wrote:
...
>>> From:    Pedro Roque Marques <[email-masked]>
...
> more trouble than it is worth.

The above statement is not only theoretically true, it is also true  
in a practical sense.  Perhaps an example will help.  Consider the  
following very common scenario:

P1--AS--P2
  | / |
  |/  |
C1  C2

AS connects to two peer ASes, P1 and P2.  AS provides service to  
multi-homed customer C1, and transit customer C2.

Normally, AS will reach C1 through the (C1, AS) link, and will  
advertise C1 reachability to P1, P2 and C2.  Similarly, P1 will reach  
C1 through (C1, P1) and will advertise C1 reachability to AS.

If (C1, AS) goes down, AS will reach C1 through P1.  Due to policy,  
AS will not advertise this path to P2, and will advertise it to C2.   
Thus, one "bad news" event (the (C1, AS) link down) has been turned  
into an update with replacement route to one peer (C2) and an update  
with withdraw to two others (P1 and P2).

Note that this scenario uses perfectly common types of BGP peering  
relationships and policies.

--John

---

From: Tony Li <[email-masked]>
Date: Fri, 22 Jun 2007 14:01:25 -0700

Hi Robin,

> prevent.

Please read the rest of the draft.  ;-)

>   I don't think this would be as destructive as the MRAI

MRAI is simply one other cause of diffraction, resulting in path  
hunting and more unnecessary messaging.

> longer path announcements.

Please read the rest of the draft.  ;-)  In particular the sections  
on optimal path damping and delayed best path selection.

> routers/ASes, or in more complex mesh structures.

Your assumption here seems to be that all delays are due to MRAI.   
That seems highly unlikely.  MRAI just gives larger delays.  There  
are others that are of influence as well.

> Getting rid

Exactly why some implementations have taken that path.

> BGP than I do, but I don't see why this would be true.

Yes, Pedro knows a good bit about BGP.  I put high value on his opinion.

To understand his perspective, I think you also need to consider  
cases where there are link failures within a more meshed topology.   
Rapid propagation of withdrawals (bad news) and slow propagation of  
alternate paths (good news) means that convergence to alternate paths  
will go through unnecessary churn.  For example, the withdrawal might  
rapidly propagate up past the point where the alternate path would  
come into play and result in a blackhole while the alternate path  
information slowly catches up.  As these are the cases where you  
really would like to converge quickly, this is problematic.

> same announcements go to all peers.

This is fundamentally incorrect.  Policy is peer specific.

> and which are returned to the pool once they time out or no

It's not particularly hard to set up a router that has multiple  
copies of the full routing table, prefers only one of them, and then  
has all of the preferred routes withdrawn.  So, yes, you need to  
provision for all 500,000 timers.  This assumes you're willing to  
bound your implementation to that number.  FWIW, that number is no  
longer competitive and would need to be more like 1-2M.  Certain  
folks seem to already be claiming 10M.

> happens after they were put in the queue.

Removing messages after they are placed into the TCP stream is not a  
practical approach.  Once the message has been played out of BGP and  
into the TCP socket, it is quite effectively "gone".  The best that a  
BGP implementation can do is to ensure that it has filled the socket  
and not computed too many additional messages.  Such messages would  
have to be explicitly buffered in BGP, which is expensive.  It's far  
more effective to simply not compute updates faster than they are  
consumed and leave the data in BGP's internal data structures.

> withdrawals from the MRAI mechanism.

You're assuming that they complied with it in the first place.

> They presumably didn't do this lightly.

True, but they didn't spend eons thinking about the problem either.

> peers it has to be implemented for.

The problem has not gotten easier.

> So I guess the trick is to find the simplest solution which will

Isn't it always?  ;-)

> mechanisms as your I-D suggests.

Rather than 'difficulty', I would say that developers made the  
judgement call that the cost/benefit ratio was unacceptable.

Tony

---

From: Robin Whittle <[email-masked]>
Date: Sat, 23 Jun 2007 17:59:16 +1000

Thanks very much Tony, Geoff, John, Tom, Noel, Ricardo and Sriram.

The Internet's routing and addressing system has trouble coming
as surely as a freight train or a rising flood.

I came to the RAM list asking questions and offering ideas,
recognising I was a newbie.  This lead me via the RRG and now to
the home of those who build and try to improve BGP - the IDR
mailing list.

Here I sit asking difficult questions and receiving good answers
from The Elders - on why the BGP mountain really can't be moved
very much, or at least nowhere near enough that a new
architecture will not be needed soon.

I accept that while it would be good to improve BGP, including
by any implementable changes as Tony and Geoff suggest, and
perhaps with Root Cause Notification and other proposals, there
is nothing we can do for the BGP routing system which will allow
it to cope sufficiently with the growth in advertised routes
which will occur unless some drastic action is taken, with a new
architecture such as LISP or Ivip etc. and probably some new
address policy to go with it.

Thanks Tom to the pointer to the BGP Implementation RFC:

   http://tools.ietf.org/html/rfc4276#section-3.45

The four manufacturers state that they comply with the "delay
withdrawals too" RFC 4271 MRAI timer specification.

Tony suggests maybe not many routers ever implemented the "don't
delay withdrawals" RFC 1771 specification.

It would be good to hear from those who write the router code
what chances there are of implementing anything more complex,
such as Tony and Geoff's Path Length Damping, Optimal Path
(Length) Hysteresis and/or Delayed Best Path Selection.

Here a brief account of what I have learned so far, including
from John's diagram and explanation of Pedro's statement.  I
don't expect anyone to read or respond.  I really appreciate the
help you have given me to date.

This is my understanding so far about the crisis in routing and
addressing, why we need a new architecture which broadly accepts
the limits of the BGP system, and why heroics such as LISP are
being seriously considered:

There is an FIB problem, but the real problem is in the RIB and
the CPU's ability to handle the demands of BGP communications.
The fundamental problem is the routers' inability to cope with
the number of advertised prefixes.

If routers could handle endless prefixes and rapid updates then
there would probably still be plenty of IPv4 addresses available
because the space could be sliced and diced finely - including
down to individual IP addresses - and used very efficiently.
Portability, using the routing system for TE and probably
mobility would be easily achieved by rapid changes to the
routing system.

The main problem seems to be the requirements placed on the
routers' CPUs in simultaneously handling a complex group
conversation with X number of peers, with a separate
conversation about Y number of prefixes.  Each peer may be sent
a different message, for instance due to local policy which may
be specific to each prefix and peer.  Similarly, the messages
received from each peer need to be considered in the light of
peer-specific and prefix-specific policy.  The messages and/or
the result of this processing, usually needs to be stored.
These messages can be quite long, and will get longer with
longer paths and 32 bit AS numbers.  (Also, with more optional
transitive things being added to BGP messages.)

Y is potentially millions, since this many end-users would like
multihoming and portability.  X, I guess, is typically 3 to 10,
but I understand some transit routers have dozens or potentially
hundreds of peers.

Even if it was possible to use arbitrary amounts of RAM (which
requires a 64 bit CPU) cope with whatever X*Y turns into, there
is the problem of CPU speed and communications speed when
considering the frequency of updates.

Theoretically, if all routers could respond in close to zero
time, with arbitrary numbers of peers and prefixes, all would be
well.

Because they can't and never will be able to, the time delays
multiplied by the approximate edge-to-edge number of router hops
from one side of the core to the other result in long delays in
achieving connectivity and later optimally short paths.

To ease the burden on routers - and so speed them up and enable
them to handle more prefixes - BGP intentionally shortens the
path description messages, whilst still providing robust loop
protection and a rougher, but still useful, measure of "length".

However, this simplified AS-based message means that a router
(4) can't figure out for sure that path 4-3-2-1 is not going to
work when it has just been told by its peer (2) that 2-1 doesn't
work any more.

                              /
           (3)     /--------(5)--
           / \    /         / \
          /   \  /         /      /
  (1)-X-(2)---(4)--->-----------(6)--
    \                    /      / \
   (10)-(11)-(12)-(13)-(14)----/

As far as (4) knows, (2) isn't a solitary router, but something
like the arrangement of routers 'R' below:

           (3)
          /  \
    /----R    \
   /           \
 (1)---R-------(4)

So until (3) gets a withdrawal message to (4), and until (4) can
propagate the resulting withdrawal to its peers (5) and (6)
there is going to be a black hole with packets being sent to (4)
when (4) has is no path to (1).  The two sole points of
connection to the rest of the Net (5) and (6) could also send
packets to (1) via the longer path 14-13-12-11-10-1. But they
won't until (4) issues its withdrawal.

The current function of the MRAI timer, delaying withdrawals,
means (typically, or often, depending on actual timings etc.) a
30 second delay in the withdrawal propagating from (4) in
structures like that described above.  The minimal structure for
this problem to occur is something like:

           (3)
           / \
          /   \
  (1)-X-(2)---(4)----

As I wrote in previous messages, the current MRAI timer
typically delays the withdrawal another 30 seconds for every
iteration of this loop system, although the actual behavior
depends very much on policy and timing.

The old MRAI specification from RFC 1771 had no such problem.
(4) would quickly announce an AA+ and then very shortly after
would announce a withdrawal.

John explained why Pedro's 2002 statement

>> event... or what information you wish to send fast/slow.

is true both theoretically and practically.

I have added some other upstream links to John's original diagram:

       P1--AS--P2
        | / |
        |/  |
       C1  C2

because I understand P1, AS and P2 are all ASes, presumably ISPs
with multiple connections to other ASes.  I assume that C1 has
only the links shown and that C2 has links to many other systems.

 \  /    \  /  /  \  /
  ASa-\  ASb--/---ASc
   \   \ / \ /    /\
    \   /   /    /  \
     \ / \ / \  /   |
  --- P1--AS--P2---ASd----
       | / | /     /
       |/  |/     /
      C1  C2-----/
           |\

> AS connects to two peer ASes, P1 and P2.  AS provides
> service to multi-homed customer C1, and transit customer C2.
>
> Normally, AS will reach C1 through the (C1, AS) link, and
> will advertise C1 reachability to P1, P2 and C2.  Similarly,
> P1 will reach C1 through (C1, P1) and will advertise C1
> reachability to AS.
>
> If (C1, AS) goes down, AS will reach C1 through P1.
>
> Due to policy, AS will not advertise this path to P2

OK - I understand this is due to AS wanting to accept traffic
for its customer C1, but only as long as C1 connects to AS's
network (and pays for it). AS does not want to attract traffic
directed to C1 through its network if it just has to pass it
over to P1, which probably costs money or at least doesn't
generate income.

> and will advertise it to C2.

I could understand this if C2 was a singlehomed or multihomed
AS-end-user edge network.

Since C2 is a transit provider, I understand that AS's
relationships are:

   P1 and P2 are other ISPs.  AS doesn't offer transit of
   packets from these networks, unless to a customer's
   network, such as C1 was, until the link went down.

   C2 is a transit provider (no local customers, like C1).
   AS will offer transit of packets to C2, so C2 can use
   AS's network as it would the network of another transit
   provider: to carry any packets anywhere.

   C2's network will also advertise to AS all its prefixes
   and so accept packets addressed to anywhere, if the AS
   network finds this path to C2 to be the best.

> Thus, one "bad news" event (the (C1, AS) link down) has been
> turned into an update with replacement route to one peer (C2)
> and an update with withdraw to two others (P1 and P2).

By "update with withdraw" I understand you mean a single
"withdraw" message.

Thanks very much for this diagram and explanation.  I understand
this justifies Pedro's statement.

But this doesn't make me think well of the MRAI timer delaying
withdrawals.

I worked through what happens next and didn't immediately find
problems caused by the MRAI timer.  The problem condition
occurs, for instance, when one router:

1 - First receives something caused by an event which is
    not reflective of the full story.  This typically
    causes an A++.

2 - Shortly after, receives something else which is a fuller
    account of the situation, but does not announce its
    response for ~30 seconds due to the MRAI timer.

If the second thing it announces was simply a longer path, or
perhaps the same or a shorter path, then there is probably no
trouble, because at all times the router could forward the
packets to their destination.

The problem arises primarily when the true situation was that
the second item of news causes the router to realise it can't
forward the packets to the destination at all.  Then, there is a
black hole for 30 seconds because the RFC 4271 MRAI timer won't
let it announce to its peers that it really can't handle this
prefix any more.  The original RFC 1771 MRAI timer would not
delay the withdrawal, so there would be no black hole for 30
seconds.

What I find more convincing about the potential evils of rushing
withdrawals and delaying some announcements of feasible paths is
withdrawals propagating faster than the later news that the
destination is now reachable.  I imagined this and Tony
mentioned it too.

Tony wrote, in part:

> Please read the rest of the draft.  ;-)  In particular the
> sections on optimal path damping and delayed best path
> selection.

I think all three proposals look promising, as far as my limited
understanding of BPG goes - and that probably two of them might
do the trick as well as all three.

It seems the real limitation is what the router vendors will
actually implement, since for the last 5 years or more they
wouldn't implement what I think is the relatively simple logic
of testing for a withdrawal, in order to fully implement RFC
1771.  I am not convinced that a genuine RFC 1771 MRAI timer
would delay the propagation of feasible paths so much as to let
a wave of withdrawals run faster through the system.

(Various other comments which I agree with snipped.)

> This is fundamentally incorrect.  Policy is peer specific.

OK, thanks.

> It's not particularly hard to set up a router that has
> multiple copies of the full routing table, prefers only one of
> them, and then has all of the preferred routes withdrawn.

I don't understand this.  Can you give an example?

> So, yes, you need to provision for all 500,000 timers.  This
> assumes you're willing to bound your implementation to that
> number.  FWIW, that number is no longer competitive and would
> need to be more like 1-2M.  Certain folks seem to already be
> claiming 10M.

Whew!!!

>> each peer being throttled via TCP, with the software being
>> able to find messages in the queue and delete them if
>> something else happens after they were put in the queue.
>
> Removing messages after they are placed into the TCP stream is
> not a practical approach.  Once the message has been played
> out of BGP and into the TCP socket, it is quite effectively
> "gone".

Yes, I understood this.  I imagined a queue of messages for each
peer, with the software reaching into that queue and plucking
out things which have been made irrelevant by more recent
developments.  Geoff's recent article suggests that this is a
common technique.

> The best that a BGP implementation can do is to ensure that it
> has filled the socket and not computed too many additional
> messages.  Such messages would have to be explicitly buffered
> in BGP, which is expensive.  It's far more effective to simply
> not compute updates faster than they are consumed and leave
> the data in BGP's internal data structures.

OK - this makes sense.

I thought it might be good for every router to wait a short
time, such as 0.5 seconds, before transmitting anything - just
in case something arrived on the heels of the first message
which was more significant.  This would be good for one router,
but would slow the whole system down with no benefits if they
all did it.

>> Yet by 2002, we are told that Cisco, Juniper et. al. had
>> given up on following RFC 1771's strict instructions to
>> exempt withdrawals from the MRAI mechanism.
>

I assumed this because the RFC was so clear and warned about
black holes.  It just an historical question now.

...

>> So I guess the trick is to find the simplest solution which
>> will solve the problem.
>
> Isn't it always?  ;-)

Indeed. The push for simplicity is so strong that much has been lost

Prefixes are so numerous that the path is described in a way
that the router can't make as well an informed decision as it
could otherwise.  For instance if the path had a complete
specification of the identity of each router, with a time-stamp
(or router-local 32 bit message sequence number) for when each
router last announced a feasible path which make subsequent
routers include it on this path, then it would be easy for a
router (4) to determine that the next best path 4-3-2-1 wasn't
worth using, because "2" identifies a router, and the timestamp
on "2" in this path was earlier than the time-stamp on 2's
withdrawal message.  I haven't read how Root Cause Notification
works, but I understand it is intended to achieve the same outcome.

Similarly, prefixes and numbers of peers are so numerous that
five or more years ago router vendors for some reason gave up
complying with RFC 1771's requirement to forward withdrawals
promptly.

> judgement call that the cost/benefit ratio was unacceptable.

Maybe if your and Geoff's I-D is successful and contributes
either to a new RFC for BGP, or a separate RFC which updates RFC
4271's MRAI timer section, then if operators and/or router
vendors are convinced of the benefits, they can rewrite at least
some of the versions of their operating systems and market their
routers with the new improved feature of providing optional RFC
xxxx Path Length Damping etc.

That would be really good.  I find it striking that what you are
proposing, at least with Path Length Damping, is similar to and
not much more complex than what was absolutely required in 1995,
probably widely ignored by 2002, and then formally prohibited in
2006!

  - Robin

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 23 Jun 2007 13:01:43 +0200

Hi Robin,

Just few observations ...

* MRAI - Some implementations do not use it at all. Some have had a knob 
for years to configure it to zero, some have it zero only for particular 
AFI/SAFIs. I am not sure if from vendor point of view anything more is 
needed here. Perhaps this discussion will result in more broader tuning 
(lowering) of def MRAI timer between operators on those routers which 
have large defaults.

* Control plane sizing - Internet table today is let's say 300K. Other 
applications routers have to deal with today are already reaching their 
tables to 1-2M. On average between implementations it takes about 50-70 
MB for 100K of control plane routes (bgp/rib). So for one million we 
would use 500-700MB. Current RPs already have 4GB of RAM. Control plane 
distribution between many RPs is already available as well, resulting 
that only common RIB needs to keep all prefix + best (backup best) 
paths. The bottom line is that from control plane RAM point of view we 
still have some runway to the cliff.

* CPUs + current internet stability proposals - I think this is the area 
which requires most current focus. Our laptops have few times more 
powerful CPUs then routers. Intel is pretty clear that scaling CPUs went 
into the multi-core avenue and speeding up the clock has significantly 
stopped. We (well all vendors) should utilize available CPU technology. 
Geoff's data that most churn is generated by roughly 10% of bad netizens 
of the Internet and recent proposals from tli/geoff have IMHO very good 
potential to vastly reduce churn leaving more BGP dedicated CPUs for 
actual BGP update/best-path processing. Other proposals in that space 
for example BGP Aggregate Withdraw could also help (IMHO :).

* Indeed there are many various proposals to introduce hierarchy to the 
Internet today. I like hierarchy and word "tunneling" does not raise 
high blood pressure to me. But on the other hand I am not clear how can 
we all be sure that with some proposals today we are not just shifting 
current path hunting problem as well as other problems from flat BGP to 
a new mapping plane ? And if this mapping plane is free from such 
issues, why current BGP control plane could not be ? After all only 
scalable & realistic deployment model is to use those same CPUs and the 
same routers for all the work.

Another point which usually I am finding not so intuitive is that most 
people does see Internet as huge chain of interconnected ASes to get 
from A to B. But here comes a surprise ... current average AS_PATH 
length is 3.4 - 3.8 depends on the geography.

One of my & my colleague's proposals in that space to just aim at 
introducing hierarchy was to simply tunnel to automatically derived IP 
address representation of endpoint AS number. It would not address 
mobility nor Internet TE. But could introduce hierarchy. The issue with 
this is that due to such short AS_PATH as well as transit AS ASBRs which 
do home their customers all what we would gain is to keep P routers from 
storing all the BGP unicast routing tables. And that has been possible 
for years now already via many technologies.

* From my point of view the biggest gain one could envision while 
introducing some form of mapping abstraction between EID & locators are 
not those which are listed in the IAB report. For me it is the 
opportunity to build and deliver internet wide new services. It has a 
full potential to become a direct analogy to introduction "Intelligent 
Network" layer to phone networks 15 years back. And that was a huge 
disruptive change to the way operators were delivering their services 
for X previous years. Not too mention that ISPs could be very happy and 
economically interested to deploy it as for them it could immediately 
result in new services to their customers they could finally start 
charging - something quite useful in the commodity Internet world today :-).

Cheers,
R.

---

From: Curtis Villamizar <[email-masked]>
Date: Sun, 24 Jun 2007 12:31:14 -0400

In message <[email-masked]>
> as surely as a freight train or a rising flood.
[...]
> architecture will not be needed soon.
[...]

Your message had some good technical content but this was not good
technical content.

We've been hearing about the eminent collapse of BGP routing,
exhaustion of IP routes, and other predictions of doom and calls for
radical changes to the architecture for well over a decade, most of it
from people with a limited knowledge of Internet operations if any.
Please don't be counted among that set by including this sort of
nonsense with your technical discussion.

Thanks,

Curtis

---

From: Robin Whittle <[email-masked]>
Date: Mon, 25 Jun 2007 03:04:45 +1000

(By the way, I don't seem to be getting IDR list messages,
although I am subscribed.)

Hi Curtis,

You criticised my statements, which were framed as being my
understanding, although on their own they look like I was

> nonsense with your technical discussion.

As far as I know, the first quoted statement is consistent with
the consensus of the RAW conference:

  http://tools.ietf.org/html/draft-iab-raws-report
  http://www.iab.org/about/workshops/routingandaddressing/

and with the exhaustion of IPv4 address space ca. 2010:

  http://www.potaroo.net/tools/ipv4/

As far as I know, the second quoted statement is consistent with
the opinions expressed by most people on this list recently, and
before that on the RRG and RAM list discussions: that while some
worthwhile improvements probably can be made to the BGP system,
with changes to the protocol and/or the configuration of
routers, that these changes, combined with likely technical
improvements in routers, will not on their own be able to cope
with the growing "global BGP routing table" and with the update
traffic which results from this growth and all other factors
affecting updates.

The fact that predictions of doom and gloom may have been made
for a decade doesn't convince me that the current predictions
are wrong.  Also, as far as I know, the people who are now
making these predictions are fully informed of the situation.

If you can convince me that these statements are false, I would
really appreciate it.  I think it would be best if you did so
with technical arguments rather than with the history of concern
or unsupported negative assessments of the expertise of people
who currently have serious concerns about the BGP system,
addressing etc.

---

From: Curtis Villamizar <[email-masked]>
Date: Sun, 24 Jun 2007 13:53:15 -0400

In message <[email-masked]>
>   http://www.potaroo.net/tools/ipv4/

If you look back at the RFC archives you'll find prior IAB workshops
and reports predicting doom all the way back from the calls to convert
from IP to OSI and from BGP to IDRP in the mid-1990s.  In fact IDR was
renamed from BGP to accomodate IDRP which then died due to lack of
interest.  If you want to see some real nonsense, take a look in the
IRTF archives at the decade worth of discussions of replacing the
interdomain routing system that sort of died down a few years ago.

The fact that the IAB has repeatedly cried wolf doesn't mean they are
addressing a non-issue.  If calling an issue a crisis gets action more
promptly then calling it a crisis prematurely may be good thing.

In the past small changes (to the extent CIDR was a small change) have
addressed the issues that were referred to as a crisis and that were
used as justification to consider massive change or a wholesale new
architecture.

Lets get back to the topic of damping and broader topic of addressing
the "issue" or route churn and let any "crisis" related to route churn
or any other crisis be discussed elsewhere if people find a need to
claim yet another crisis.

As the author of the original route damping I can say that there never
was a crisis or route churn.  It was considered a good idea for two
reasons.  Eliminating the minority of constantly oscillating routes
(that existed then) relieve the burden on core routers and make
convergence for mostly stable routes faster.  The widespread use of
something more intellegent to limit route churn might allow greatly
reducing (but probably not quite eliminating) MRAI.  

The high level of route churn at that time (and probably now) was more
of a nuisance than a crisis.  It was more about improving the
performance of the Internet rather than saving it from disaster.

Part of the problem with route damping as currently implemented is the
spec clear calls for damping on a per destination per AS-path basis
while implementation only allow a per destination basis.  The result
is that transient AS path changes resulting from a withdrawl penalize
the destination even when the valid alternate AS path is very stable
but takes a bit longer to arrive (which could happen for various
reasons).  That was a real problem that could magnify the impact of
one or two route changes and cause unwanted damping.  It should be
noted (but rarely is) that if damping was implemented *as specified*
this magnification would not happen.

A separate practical problem was occasionally bringing up something
new and having it go up and down a lot could cause the aggrevation of
having it damped (and that sort of poor network admin could result in
public whining about damping being harmful, for example from a certain
individual at the last NANOG).

The other part of the problem is one vendor set the default parameters
too short.  That was easily solved by RIPE making some reasonable
recommendations for configuring the timers.

btw- If most routes are mostly stable, the small churn on a transition
is not really an issue.  

Peace,

Curtis