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]  

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 
number of updates.

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 

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 
updates in the convergence sequence has been steady at 2.7 updates on average.

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 

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 
http://bgpupdates.potaroo.net/instability/bgpupd.html). (again parenthetically, 
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. 


rrg mailing list

Reply via email to