```Hi Thomas,

With reference to the draft you have written in the scaleability of Internet
Routing I'd like to add some comments based on an update to my work cited by
this draft (namely [1]
<http://www3.ietf.org/proceedings/06mar/slides/grow-3.pdf>).```
```
I was struck by the the two key drivers you reference in section 3, namely the
growth of the number of entries in the routing system and the growth in the

I have been looking at this for some time, as you are aware, and I'd like to
point you to a presentation pack I've prepared that is an update to the data
you reference in the draft. The referenced presentation refers to data
collection over 2005. The more recent presentation refers to a longer term data
set that spans multiple years. You can find the pack at:
http://www.potaroo.net/presentations/2010-02-01-bgp2009.pdf. (This work is
being presented at APRICOT this week in Kuala Lumpur.)

The first observation I'd like to make is that the growth in the number of
prefixes is not clearly superlinear as the draft appears to assert. I have used
a technique of taking the one hour snapshots of the BGP table size for the
so-called DFZ and firstly generating a daily average, and then applying a
sliding window smoothing function to generate a smoothed curve (slide 19 of the
pack). I can then generate the daily differences to generate a first order
differential (slide 20). If this first order derivative is approximately linear
(green line in that slide) then the underlying data function is a second order
polynomial (quadratic). If this first order derivative is increasing then the
underlying data function is either a higher order polynomial or an exponential
function.

What is evident in the data is the global recession in 2009. What is not
clearly evident is that the 6 year trend of this first order differential of
growth is anything other than a relatively uniform linear function. This
assumption of a linear first order differential yields a polynomial data
function of F = 1389 year2 – 5545164 year + 5533345999, which is compared to
the raw data on slide 21. I'd offer the opinion that the extended model of eBGP
table growth fits a quadratic function remarkably well (x**2) at the moment,
and that there is less compelling evidence to suggest that the growth is
exponential with a constant doubling period (e**x). Projections of growth of
this model are on page 23.

So I agree with your observation that the growth in the number of routed
prefixes in BGP in the public Internet is higher than linear, but the long term
data series leans towards a model of quadratic growth over a model of
exponential growth of this data.

The other observation you make here is based on analysis in 2005 of the update
rates of BGP. I claimed in early 2006 that the overall rate of growth of BGP
updates is increasing. Further analysis based on observation of the ensuing 5
years of BGP behaviour suggests that I was wrong in making that claim.

Slide 35 of the presentation plots the number of updates each day. When I
remove the updates that were the outcome of local BGP session resets (full
table transfer). Whats left is a data series of non-local updates that in the
first instance looks to be decreasing rather than increasing. A multi-year view
(page 36) suggests that the long term trend is a constant, of some 90,000
updates per day (slide 36). Any growth trend in the data is linear at best
(slide 37). Withdrawals are similar. They are decreasing, not increasing. The
multi-year trend is not so apparent (slide 39), but I'm hesitant to make any
claims here about longer term trends.

I then looked at the data using a different form of filter - asking the
question "how many prefixes were the subject of oner or more BGP updates each
day?". Here (slide 41) you can clearly see those days where there were one of
more local session resets (top data series). On the other days where there was
no full table reset the number of prefixes that were the subject of updates is
close to a constant for some years (page 42). I find this somewhat surprising,
but it is certainly part of the data.

In order to understand this a little better I split the updates into isolated
events where a given prefix was updated (withdrawn or announced) as an isolated
event, and "sequences" where the same prefix is updated multiple times, with no
more than 4 MRAI intervals (130 seconds to be precise) between successive
updates. The daily number of such convergence sequences is also close to
constant over the past 1,000 days. The average time duration of the convergence
sequences has been relatively steady at some 73 seconds, and the number of

In the past 1,000 days the network has increased in population by some 40%, yet
the metrics of instability in the network appear to be stable. (I have to say
that this is a surprising result. Its a bit like taking the same trip to work
each day in your car for years, and noticing that over time the roads have not
changed, but you have seen that the number of cars on the roads has doubled,
yet your trip to work takes the same time! This observation about the stability
of long term convergence behaviour in BGP seems in the first instance to be
counter-intuitive.)

In attempting to find a metric of the topology of the Internet that had some
correlation to convergence behaviour I plotted the distribution of the number
of convergence events of each size over the past 1000 days against the
distribution of AS path lengths in the BGP route table. For the first 11
entries, or for 98.6% of all convergence events the correlation is surprisingly
good (slide 54).

I suspect that the instability of BGP in terms of the behaviour of a distance
vector protocol that is seeking to reach a converged state is related primarily
to the metric of the diameter of the network, and not primarily related to the
number of discrete elements (prefix count or AS count) that participate in the
distribution computation that is the routing protocol. As long as the
"diameter" of the network remains approximately constant then the instability
of the network (or the convergence properties of the network) is also
relatively stable. I therefore cannot completely agree with the assertions in
section 5.1 of the draft, and would offer the alternative view that for as long
as continued growth of the Internet remains within an overall characteristic of
increased "density" while preserving its overall "diameter", then the topology
factor that would increase the "amplification" factor of distance vector
protocol convergence computation remains bounded. (Parenthetically, if this is
indeed the case, then it is possible that slight changes to BGP may provide
significant payback in terms of further reducing the update load associated
with the convergence seeking behaviour of BGP. The ideas described in
draft-li-bgp-stability-01.txt (from 2007) points to one such approach (section
4.3) where a modification of the MRAI behaviour allows a reduction in the
number of updates that are generated in the convergence seeking process while
having minor impact on the overall time to reach convergence. There may well be
other approaches of a similar form.)

As your draft notes, it remains the case that the distribution of updates is a
heavy tail distribution, and 1% of the origin ASs continue to contribute more
than 40% of the update load in  BGP (recent data is at
this observation may also provide some approaches to update filtering that
would attempt to filter out persistent instability from BGP updates.)

In any case, I would offer the opinion that there is more to understand about
the actual behaviour of this network in terms of dynamic routing behaviour. It
is not immediately apparent that the underlying growth over the past few years
of BGP in both population count and in dynamic update behaviour in and of
itself represents sufficient grounds to believe that BGP routing is in a dire
place at present. However, it is an unconstrained system as you point out in
section 3.2 of your draft, and the pressures of address exhaustion in IPv4 in
the coming years represent a massive unknown when attempting to forecast the
near term future for routing scale.

Geoff

_______________________________________________
rrg mailing list
rrg@irtf.org
http://www.irtf.org/mailman/listinfo/rrg
```