Subject: [RRG] Geoff Huston's article on BGP stability, update statistics and damping

From: Robin Whittle <[email-masked]>
Date: Tue, 19 Jun 2007 18:54:30 +1000

Geoff Huston has a new article "Damping BGP":

  http://www.potaroo.net/ispcol/2007-06/dampbgp.html

He proposes methods of identifying updates which are usually
associated with path hunting.  Typically this is one or multiple
announcements of a longer path for the prefix, followed by the
withdrawal of the prefix.  I understand from this that he
supports "path length damping" as described by Tony Li:

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

How such filtering would work when all routers implement it I am
not sure, but it seems like a good idea.

I learnt some interesting things, including that BGP routers
often use TCP to throttle the updates from peers to a rate they
can handle.  One reason this is done is to prevent local input
queues from taking up too much memory.

Meanwhile, the peers perform "output queue compression".  They
look into the queue of updates which are waiting to be sent and
remove any messages which have been rendered incorrect by events
which transpired since that message was put in the queue.

There is also a diagram depicting path hunting, and graphs
depicting the statistics of updates, based on research in April
this year.

  "10% of announced prefixes being responsible for 53% of all
   routing updates, and the busiest 1% of prefixes responsible
   for 24% of the routing updates for the month."

  "It can’t be the case that more than a million routing updates
   actually reflect true underlying changes in topology of the
   network, given that these one million updates only refer to
   2,000 prefixes."

I think the time analysis of the updates would be of interest to
anyone concerned about BGP stability.

In case anyone on this RRG list is not on the RAM list, there is
discussion on the RAM list about my "Ivip" adaptation of LISP
which should be much more amenable to incremental deployment.

  - 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: Geoff Huston <[email-masked]>
Date: Wed, 20 Jun 2007 04:48:58 +1000

> not sure, but it seems like a good idea.

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.

> queues from taking up too much memory.

Thank you John Scudder for clearly explaining this to me earlier this year.

> which transpired since that message was put in the queue.

Thank you John Scudder for clearly explaining this to me earlier this year.

> anyone concerned about BGP stability.

I would hope so. A significant proportion of the BGP traffic appears to 
be concerned with a relatively small number of "pathologies" where BGP 
itself is the amplifier.

    Geoff

---

From: [email-masked]
Date: Wed, 20 Jun 2007 07:20:21 -0400

Please see a question about MRAI below. Thank you.

Sriram
http://www.antd.nist.gov/~ksriram/

>   view it is as a more selective form of Min Route Advert Interval Timer.
My understanding is that MRAI does not apply to 
explicit withdrawals (the AWs and WWs in your taxonomy).
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.
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), and hence Router 5
will send only one AA+ and then a withdraw.
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.

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 21 Jun 2007 10:51:42 +0200

Robin,

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

These two documents show that there is still some tuning to be done with
BGP to reduce the churn. The proposed approach is mainly to change
slightly the existing implementations to reduce thenumber of BGP
messages advertised after a change. This is a valid way of incrementally
improving BGP. In the past, the measurements studies of Cragi Labotivz
and his colleagues have shown for example that a router should only send
withdraw messages for prefixes that it had previously announced. This
was not the case for most implementations at that time and
implementations have evolved.

I'm sure that some tuning can be done to the BGP damping mechanism, but
I think that the discussion on these issues belongs to the IETF (i.e.
the IDR mailing list) and not the IRTF. I hope that the IRTF can work on
longer term issues.

For example, when considering link failures a much more ambitious goal
could be to develop new interdomain routing techniques that allow to
avoid most packet losses due to link failures. Inside ASes, several
techniques, such as those relying on MPLS have been deployed by large
network operators and other, relying on pure IP, are being developped
within the IETF. Similar techniques could be used to protect BGP peering
links from failure. A possible approach was described in

O. Bonaventure, C. Filsfils, P. Francois, Achieving Sub-50 Milliseconds
Recovery Upon BGP Peering Link Failures, CoNEXT 2005,
http://inl.info.ucl.ac.be/publications/achieving-sub-50-milliseconds-recovery-upon-bgp-peering-link-failures 

This approach covers sudden failures, but these are not the only problem
that must be taken into account. Several operators report that link
failures are often caused by management activities. This implies that
there are two types of link failures :
- the sudden ones that occur due to lower layer problems
- the planned ones that occur due to maintenance operations

The first type of failure must typically be adressed quickly, by either
using a fast reroute technique or a fast convergence techniques (fast
convergence can have the diasdvantage of causing more churn than fast
reroute). The second type of failure does not need to be handled
quickly. Instead, it should be possible to recover from the planned
failure without causing any disruption.

When a link fails, packet can be lost for three reasons :
- they are sent on the failed link without noticing the failure
- they are received by a router that does not know anymore a route to
reach the destination and is forced to drop them
- they loop between two or more routers whose routing tables are
transiently inconsistents and there TTL expires after a few loops

For the first reason, fast-reroute techniques have been proposed with
MPLS, pure IP (loop-free alternate, notvia addresses, ...) and also eBGP
peering likns (see the CoNext paper mentionned above).

For the second reason, it should be possible, in the case of protected
link failures or planned maintenances, to indicate that a route should
be less preferred instead of removing it with a withdrawn. BGP graceful
restart could also have some usage here.

For the third reason, I would like to point out that there are several
solutions being discussed within the RTGWG to handle this problem with
OSPF and IS-IS, see e.g
http://tools.ietf.org/html/draft-francois-ordered-fib-02
http://www.tools.ietf.org/html/draft-bonaventure-isis-ordered-00

I think that a solution to improve the stability of BGP should aim at
solving these three problems as well because we need to address both the
stablity of BGP and avoid loosing packets when an alternate path exist.

 From this viewpoint, it might be interesting in the paper to refer
to the SIGCOMM 2006 paper by Wang et al. that shows, based on
measurements with a BGP beacon, that packet are lost during a failover
of a dual-homed stub
http://www.sigcomm.org/sigcomm2006/discussion/showpaper.php?paper_id=40

Having an interdomain routing protocol whose main objective is to avoid
losing packets (i.e. keep packets happy as Randy Bush could say) would
be an interesting long term objective for the IRTF RRG working group.

Best regards,

Olivier

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 21 Jun 2007 10:52:01 +0200

Geoff,

> be concerned with a relatively small number of "pathologies" where BGP

I think that when looking at the BGP prefixes that are responsible for
most of the churn, it is worth mentionning that some studies have looked
at traffic traces in parallel with BGP update traces and have shown
clearly that the BGP prefixes with lots of instabilities are usually
prefixes that do not carry large amount of packets.

See e.g.

S. Uhlig, V. Magnin, O. Bonaventure, C. Rapier and L. Deri
Implications of the topological properties of Internet traffic on
traffic engineering, 19th ACM Symposium on Applied Computing, Special
Track on Computer Networks, March 2004.
http://inl.info.ucl.ac.be/publications/implications-topological-properties-internet-traffic-traffic-engineering

Jennifer Rexford, Jia Wang, Zhen Xiao, and Yin Zhang, "BGP routing
stability of popular destinations," Proc. Internet Measurement Workshop,
November 2002

Olivier

---

From: [email-masked] (Noel Chiappa)
Date: Thu, 21 Jun 2007 10:00:29 -0400 (EDT)

> From: Robin Whittle <[email-masked]>

    >  "... the busiest 1% of prefixes responsible for 24% of the routing
    >  updates for the month."

While I agree that whatever's causing this ought to be fixed, there are some
points we need to not lose sight of.

First, fixing this would be a *one-time* improvement in the growth curve for
the update rate (versus long-term time). I.e. you'd see a flat spot (or a
drop) in the curve, after which it would resume its previous growth.

Second, 25% is not peanuts, but it's also not an order of magnitude, and
eliminating these wouldn't get us into a whole new operating region. I don't
know what the current growth rate for BGP updates is, but if it's anything
like the growth rate of the table itself (as one might reasonably assume it
is), 25% is not a long calendar time.

Again, it ought to be fixed, but let's not kid ourselves that this is the
solution to our problems.

	Noel

---

From: Olivier Bonaventure <[email-masked]>
Date: Thu, 21 Jun 2007 17:03:32 +0200

Noel,
> solution to our problems.

I completely agree with you. If the RRG wants to reduce the path hunting 
problem, a better approach would be to look at BGP extensions like EPIC
that allow routers to avoid transmitting unnecessary messages. This is a 
longer term approach than tuning the damping mechanisms but would 
probably be very useful. Another longer term direction could be to 
develop interdomain routing protocols that are not entirely based on 
path vector like BGP. A possible approach is HLP.

EPIC is described in

Jaideep Chandrashekar, Zhenhai Duan, Zhi-Li Zhang,
Jeff Krasky, Limiting Path Exploration in BGP, IEEE INFOCOM 2005, 
http://www.cs.fsu.edu/~duan/publications/epic_infocom05.pdf

HLP is described in

L. Subramanian, M. Caesar, C. Tien Ee, M. Handley, M. Mao, S. Shenker, 
I. Stoica, “HLP: A Next Generation Interdomain Routing Protocol,” 
SIGCOMM’05. http://portal.acm.org/citation.cfm?id=1080091.1080095

Olivier

-- 
http://inl.info.ucl.ac.be , Universite catholique de Louvain, Belgium

---

From: Marshall Eubanks <[email-masked]>
Date: Thu, 21 Jun 2007 11:33:30 -0400

On Jun 21, 2007, at 11:03 AM, Olivier Bonaventure wrote:

> I completely agree with you. If the RRG wants to reduce the path  
> hunting problem, a better approach would be to look at BGP  
> extensions like EPIC
> that allow routers to avoid transmitting unnecessary messages. This  
> is a longer term approach than tuning the damping mechanisms but  
> would probably be very useful. Another longer term direction could  
> be to develop interdomain routing protocols that are not entirely  
> based on path vector like BGP. A possible approach is HLP.
>
> EPIC is described in
>

>
> HLP is described in
>
> L. Subramanian, M. Caesar, C. Tien Ee, M. Handley, M. Mao, S.  
> Shenker, I. Stoica, “HLP: A Next Generation Interdomain Routing  
> Protocol,” SIGCOMM’05. http://portal.acm.org/citation.cfm? 
> id=1080091.1080095
>

or

http://www.sigcomm.org/sigcomm2005/paper-SubCae.pdf

which seems to be publicly available.

Regards
Marshall

---

From: Geoff Huston <[email-masked]>
Date: Fri, 22 Jun 2007 07:23:01 +1000

> solution to our problems.

Actually Noel, I'm not sure that I agree with either of your assertions, 
and the basic reason is a lack of an analysis of this over a long term 
over a number of years (the data is there, but someone has to set up the 
computational run across it). My intuition says that as the degree of 
interconnection in the inter-AS cloud increases, then the BGP 
"amplification" of underlying events increases, and the same set of 
underlying events could be the cause of 26%, 27%,... etc of all updates 
in the future. i.e. the querstion in my mind is: are the dynamics we've 
been seeing in update load an artifact of the increasing size of the 
internet, the increasing interconnection of the Internet, the increasing 
level of policy diversity within the Internet or all three - or do all 
three growth elements tend to interact with the rather chatty way in 
which BGP undertakes convergence to create a long term traffic trend? If 
this is the case and if we understand that we really cannot change the 
dynamics of the first three elements, then what precisely is the nature 
of the interaction with BGP, and is it possible that by altering BGP 
update propagation behaviors is it possible to shift the BGP load onto a 
different trajectory? Your message says to me:  "no, a modification of 
BGP creates a short term reduction in update load, but the underlying 
growth factors are independent of this." I am not sure that I agree with 
this proposition, and more data and more experimentation is probably a 
good way to understand this a little better.

    Geoff

---

From: [email-masked] (Noel Chiappa)
Date: Fri, 22 Jun 2007 10:52:29 -0400 (EDT)

> From: Geoff Huston <[email-masked]>

    >> First, fixing this would be a *one-time* improvement in the growth
    >> curve for the update rate (versus long-term time). I.e. you'd see a
    >> flat spot (or a drop) in the curve, after which it would resume its
    >> previous growth.

    >> Second, 25% is not peanuts, but it's also not an order of magnitude
    >> ... I don't know what the current growth rate for BGP updates is, but
    >> if it's anything like the growth rate of the table itself .. 25% is
    >> not a long calendar time.

    > I'm not sure that I agree with either of your assertions

I'm a little surprised to hear that, because I thought the rationale behind
them was pretty non-contentious. Let me lay it out in a bit more detail, and
you can point out where you think I've missed something. (And please excuse
the level of detail; I'm not being snarky, I want to be able to see exactly
which step isn't justified.)

As I said, I don't know what the current growth rate for the BGP *update* rate
is (and see comment below about data), but I would assume that that growth
rate is related to the growth rate of the nework (and therefore the table)
itself. Perhaps not a straight linear relationship, e.g. because as the
network grows, paths get longer, so there's a higher chance that a given
connectivity change will impact the path to a given destination. However, I
think the relationship can hardly be sub-linear (i.e. slower growth on update
rate than on the table size).

Breaking it down a bit more, if the average rate of connectivity change (i.e.
crash/failure/etc), for each type of individual element (switch, link, etc),
is basically constant over time (and yeah, there will probably be
improvements, but I don't know how fast), then the overall connectivity change
rate, for the nework as a whole, will scale linearly with the growth of the
network. I would also assume that the rate of update generation has some
reasonably simple relationship to the rate of topology change. That would mean
that the derivatives of all three (i.e. the rate of change of the network
size, the rate of change of connectivity change, and the rate of change for
the rate at which updates are generated) also have some simple (i.e. linear)
relationship.

In other words, the long-term graph of the update rate would have the same
shape as the long-term graph of the table size - and we know what that curve
looks like.

>From there, it's a simple step to the first point. Just as a one-time
reduction in the number of destinations historically produced a flat spot (or
a decline) in the size of the routing table, after which it resumed its
inexorable and painful growth, we'd see the same kind of shape in this graph.

Similarly, for the second, just as with the fairly high growth rate of the
overall routing table, a one-time reduction of 25% in routing table size
would only buy us a limited amount of time there, so too a 25% reduction in
update rate would only buy us a limited amount of time on the update rate
growth.

    > the basic reason is a lack of an analysis of this over a long term over
    > a number of years (the data is there, but someone has to set up the
    > computational run across it).

I couldn't agree more completely. The above line of reasoning seems fairly,
well, reasonable, but it might be wrong, and real data beats theorizing any
day.

    > My intuition says that as the degree of interconnection in the inter-AS
    > cloud increases, then the BGP "amplification" of underlying events
    > increases

Not just degree of interconnection; as I mentioned above, as the network
grows, the average path length grows, so intuitively (and maybe I'm wrong
here, but I think this is likely) there's a slow growth in the likelihood
that any particular connectivity change will impact any given path.

Of course, in actuality average paths lengths in the Internet aren't growing
as fast as they would in a random graph which is growing at the rate the
Internet is, but to achieve that we are seeing higher connectivity levels,
and that also has a potential impact, as you point out. So Mother Nature gets
you one way or the other!

    > and the same set of underlying events could be the cause of 26%,
    > 27%,... etc of all updates in the future.

I agree this is quite possibly true; but even if true, I don't think it
necessarily significantly conflicts with my points. Yes, if the share of
updates which are caused by this effect is slowly increasing, then getting
rid of them will not just produce a flat spot in the graph of the update
rate, but also slightly change the shape of the overall curve.

However, if the effect (numerically) is in the range you suggest, it don't
think it would make a *substantial* difference to the *overall shape* of the
curve, in the long term - that was my real, basic, point. Now, if it were
going to jump 25%, 30%, 40%, 60%, then, yes, then it would make a significant
difference.

    > the querstion in my mind is: are the dynamics we've been seeing in
    > update load an artifact of the increasing size of the internet, the
    > increasing interconnection of the Internet, the increasing level of
    > policy diversity within the Internet or all three

I would say all three, but without data, I doubt we can say much about the
relative contribution of each, which is of course what we'd like to know.

    > or do all three growth elements tend to interact with the rather chatty
    > way in which BGP undertakes convergence to create a long term traffic
    > trend?

I think you're asking if there's a synergistic effect on update rate growth
among the three? Could be, but we'd need even more detailed analysis to know,
I suspect.

    > If this is the case and if we understand that we really cannot change
    > the dynamics of the first three elements, then what precisely is the
    > nature of the interaction with BGP, and is it possible that by altering
    > BGP update propagation behaviors is it possible to shift the BGP load
    > onto a different trajectory?

Right, but a trajectory that's only slightly different doesn't really help.
But without more detailed understanding, not just of the basic curve itself
(which we don't know), but of how changes might affect it, we can't
definitely say much...

    > Your message says to me: "no, a modification of BGP creates a short
    > term reduction in update load, but the underlying growth factors are
    > independent of this." I am not sure that I agree with this proposition

Well, but looking at those growth factors (i.e. i) the increasing size of the
Internet, with its subsidiary ia) the growth in average path length; ii) the
increasing interconnection of the Internet - which does mitigate against ia;
iii) the increasing level of policy diversity within the Internet), only one
of them, the policy stuff, can possibly have any connection with BGP.

In other words, to the extent that the growth curve is being shaped by the
other three (and I think I made a reasonably argument, at the top, that they
are reasonably directly related to the growth in the update rate), we can't do
much to change it. I.e. even if we somehow dial out iii), the others will
combine to produce a growth curve which is likely to be problematic.

Now, I *can* think of ways to change the routing overhead, but it implies
more radical changes to the existing system (e.g. more abstraction, allowing
us to reduce the size of the routing tables).

    > more data and more experimentation is probably a good way to understand
    > this a little better.

Again, no disagreement with that! Real data is always better.

	Noel

---

From: Geoff Huston <[email-masked]>
Date: Sat, 23 Jun 2007 18:00:31 +1000

Noel,

If you will forgive me for hastily responding to just one observation in 
your response while working over the entire message, there is one thing 
I'd like to highlight as I found it interesting and I hope you will too.

> that any particular connectivity change will impact any given path.

This is the comment I'd like to quickly respond to

Since 1998 we have the Route-Views data, and it is possible to look at 
each individual route views peer as a data sequence that now spans a 
decade (Route-Views is truly a really valuable data resource - I'd 
suggest its far and above the best we have for this work! My profound 
thanks to the crew there for setting it upand running it!)

A set of observations across the entire route views history is graphed 
at http://www.potaroo.net/bgprpts/rva-index.html

Since 1998 the network was grown from 50,000 entries to 225,000 entries 
and advertised address space now spans 1.7 x 10**9 /32s, growing from 
0.95 x 10**9 in 1998. The number of AS's in the network has grown from 
3,000 to 26,000

BUT the average path length has remained pretty steady - most Route 
Views peers see the entire network at an average AS path length of 
around 3.4, and have done so since 1998.
(http://www.potaroo.net/bgprpts/bgp-average-aspath-length.png)

i.e. as the network grows it gets more interconnected, and not longer 
and stringer. As the network grows, the density of interconnection 
increases. i.e we are seeing higher inter-connectivity levels, which I 
would see as one of the major factors that contribute to the BGP 
behaviours we see today.

I'll respond in some further length later Noel to your response, but I 
thought you'd be interested in this particular aspect of the last 10 
years of growth of the Internet - that the "shape" of the Internet's 
growth over the past decade is not really an expanding sphere of 
relatively constant internal density, but its been more like a sphere of 
constant diameter with increasing internal density.

cheers,

    Geoff

---

From: [email-masked] (Noel Chiappa)
Date: Sat, 23 Jun 2007 12:20:52 -0400 (EDT)

> If you will forgive me for hastily responding to just one observation
    > in your response

Forgiven in general, but your particular point might have benefitted from a
more complete read... (see below :-).

    >> Not just degree of interconnection; as I mentioned above, as the
    >> network grows, the average path length grows, so intuitively ..
    >> there's a slow growth in the likelihood that any particular
    >> connectivity change will impact any given path.

    > ...
    > ..
    > and stringer.

In my original message, I did indicate that I was aware that increased
connectivity had held down path length growth:

    >> in actuality average paths lengths in the Internet aren't growing as
    >> fast as they would in a random graph which is growing at the rate the
    >> Internet is, but to achieve that we are seeing higher connectivity
    >> levels

I wasn't aware that the average AS path length was actually static, though,
so that's interesting.

Of course, this is the AS path length, not the number of actual forwarding
steps; it would be interesting to know if the actual forwarding path length
had remained the same as well.

However, for the purposes of analyzing BGP's operational behaviour in
response to connectivity changes, the AS path length is probably at least
as important...

    > As the network grows, the density of interconnection increases. i.e we
    > are seeing higher inter-connectivity levels

Right. There's actually been a fair amount of work in the graph theory world
on this topic (and also in various applied fields), covering what are called
"small-world" graphs, which have this property (that the average path length
doesn't grow as the graph grows - which is true of true random graphs).

    > which I would see as one of the major factors that contribute to the
    > BGP behaviours we see today.

It's hard to say exactly how this change in connectivity patterns is affecting
BGP's behaviour. My off-the-cuff intuition says that there are effects in both
directions, and it's not clear which dominates.

For example, in the helping direction, the diameter of the graph is not
growing as fast as it normally would, and that's probably (but not
definitely, sometimes surface analyses are wrong) having a positive impact.
(Plus to which there's a second-order effect which is the negation of the
effect which started this thread.) In the other direction, I think that the
graph has more cycles in it, and I suspect (as I gather you do) that that's
probably a negative.

The whole situation is complex enough that I suspect the only way to say for
sure what the truth is is to do some pretty hairy simulations.

Remember, the actual recorded data-set we have from the operation of the
Internet includes two different things going on at the same time: a) overall
growth (in sheer size) as well as b) increased connectivity. I'm not sure we
can look at the recorded data (in terms of the growth of the update rate) and
sort out which part of the change is due to one, and which is due to the
other.

Hence the need for simulations to give us better data (since we're unlikely
to be able to modify the Internet's connectivity to give us actual data on
how the routing algorithm would operate in a a network of the same size, but
with different connection patterns :-).

	Noel

---

From: "Medhi, Deep" <[email-masked]>
Date: Sun, 24 Jun 2007 10:40:04 -0500

> A set of observations across the entire route views history 
> is graphed at http://www.potaroo.net/bgprpts/rva-index.html
> 
> Since 1998 the network was grown from 50,000 entries to 
> 225,000 entries and advertised address space now spans 1.7 x 
> 10**9 /32s, growing from
> 0.95 x 10**9 in 1998. The number of AS's in the network has 
> grown from 3,000 to 26,000
> 
> BUT the average path length has remained pretty steady - most 
> Route Views peers see the entire network at an average AS 
> path length of around 3.4, and have done so since 1998.

I'll speculate here...

A possible reason could be the increase in the number of exchange points
(both public and private, large and small) around the world. This, in
turn, could partly be possible due to drop in price in networking gears
used at exchange points, but also due to connectivity, deployment and
drop in per unit price of submarine cables (which are pretty much all
fiber-optic based).

For instance, PeeringDB (http://www.peeringdb.com) gives the current
number for public exchange points to be nearly 170. Does anyone have
info on growth in exchange points over the years?

For a recent submarine cable map, see TeleGeography's map:

http://www.telegeography.com/products/map_cable/images/sub_cable_2007_la
rge.jpg

Thanks.

	-- Deep
	http://www.csee.umkc.edu/~dmedhi

---

From: Danny McPherson <[email-masked]>
Date: Mon, 25 Jun 2007 07:39:35 -0600

On Jun 21, 2007, at 3:23 PM, Geoff Huston wrote:

>
> Actually Noel, I'm not sure that I agree with either of your  
> assertions, and the basic reason is a lack of an analysis of this  
> over a long term over a number of years (the data is there, but  
> someone has to set up the computational run across it). My  
> intuition says that as the degree of interconnection in the inter- 
> AS cloud increases, then the BGP "amplification" of underlying  
> events increases, and the same set of underlying events could be  
> the cause of 26%, 27%,... etc of all updates in the future. i.e.  
> policy diversity within the Internet or all three - or do all three  
> growth elements tend to interact with the rather chatty way in  
> which BGP undertakes convergence to create a long term traffic  
> trend? If this is the case and if we understand that we really  
> cannot change the dynamics of the first three elements, then what  
> precisely is the nature of the interaction with BGP, and is it  
> possible that by altering BGP update propagation behaviors is it  
> possible to shift the BGP load onto a different trajectory?
>

I know I've said this a few times but figured it's worth stating here
again..  In addition to external BGP and inter-AS cloud interconnection
comments, the intra-domain BGP topologies imposed by the protocol
are considerable (iBGP advertisement rules, network topologies, etc..)
and will likely find considerable benefit in this and related  
stability work.

This amplification we're speaking of is quite obvious where BGP's
route advertisement is most strict and policy capabilities of BGP are
of less utility - in the "core" of the iBGP core internal to an AS.   
While
the FIB/RIB sizes in this "DFZ" remain on fixed trajectory, the external
interconnection denseness forces a much steeper growth curve
in RIB size (and all the underlying update oscillation, instability and
other properties) internal to the BGP network (as does a whole
additional array of path attributes).

The number of BGP paths in internal BGP core is very often 5-15x or
more than that of the AS border routers, and it's where things will  
break
first.  Keeping this in mind when considering both short and long-term
solutions is paramount.

-danny

---

From: [email-masked] (Noel Chiappa)
Date: Mon, 25 Jun 2007 14:29:26 -0400 (EDT)

> From: Danny McPherson <[email-masked]>

    > the external interconnection denseness forces a much steeper growth
    > curve in RIB size ... internal to the BGP network

Interesting observation...

    > the intra-domain BGP topologies imposed by the protocol are
    > considerable ...
    > ...
    > break first.

On the other hand, it's (in theory) a less painful problem to solve, in the
sense that any solution can be deployed on an Autonomous System (let's
remember the import of that term) by AS basis, rather than potentially
requiring system-wide coordination.

I don't have any 'off the top of my head' technical reaction to this point.
Let me ponder it for a while...

	Noel
[email-masked] [email-masked]~h