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 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 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 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 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 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. Geoff _______________________________________________ rrg mailing list rrg@irtf.org http://www.irtf.org/mailman/listinfo/rrg
