The ISP Column An occasional column on things Internet AS Number Consumption Geoff Huston August 2005 Of the 64,510 available AS numbers, as of July 2005 we have already allocated some 39,000 AS numbers, or well over half of the number pool. This raises two immediate questions – how long before the number pool is completely exhausted, and what are our options for a expanded number pool that can encompass a larger inter-domain routing environment? We'll examine the first question in this article, and defer consideration of the next question for the following article. The Drivers for AS Number Consumption Before looking at the question of AS Number consumption in further detail, it would be useful to understand the driving factors behind AS number consumption. From one perspective it would appear to be counter-intuitive to assume that the Internet will evolve from tens of thousands of distinct routing domains to one of hundreds of thousands or even millions of distinct routing domains. Individual routing domains are essentially equivalent to individual Internet Service Providers (ISP's), and in the first instance it would appear that there is a reasonable level of correlation between the number of active ISP's in the Internet and the number of advertised AS numbers. If forecasting a future demand for hundreds of thousands or even millions of AS numbers it would appear that we are forecasting continued, If not excessive, fragmentation of the service provider industry with large numbers of small enterprises who collectively compose the Internet. This does not appear to be a likely scenario. The ISP industry has been one that has had a continuing aspect of relatively intense competition between providers, and in many, if not all, market segments there has been an underlying factor of economies of scale. Larger ISPs have access to more efficient use of their resources and are more capable of sustaining a market share at competitive prices with reasonable operating margins due to these economies of scale. Smaller providers tend to service niche markets, and, in general, are highly susceptible to pricing pressures in the competitive supply market. The overall result is strong pressure for continued aggregation in the service provider market, tending to aggregate to a smaller number of larger providers. From this perspective, if the number of AS's in use is roughly commensurate to the number of service providers, then this view of the market dynamics would lead to a view that the service provider population is either in a state of equilibrium where the entrance of new niche-oriented players is roughly the same as the rate at which smaller players are aggregated into larger providers, or one of relatively small growth based on the larger dynamics of continued expansion of the Internet on a global basis. In practice this has not been the case, and we see a continuous rate of consumption of new AS numbers. This rate appears to be some 3,500 AS numbers per year, or an average of 9.8 AS numbers per day, and this consumption rate appears to have been reasonably steady since early 2003. Does this signify a continuous rate of new entrants into the ISP industry at a global level, or are other factors at play here? It would be unlikely that this single cause would account for such continued AS number consumption, and there does appear to be some additional factors that have some bearing on total AS number consumption rates. One of these factors is the practice of multi-homing at the edge of the network. Many end site networks have business-critical needs for assured Internet connectivity, and a common way to achieve this is through the use of services from two or more upstream providers. In such situations the end site may want to express different routing policies to each upstream provider, and it does so through using its own AS number and expressing these routing policies using BGP to each of its upstream providers. AS numbers are also used in other contexts. In MPLS L3 networks one form of generating the Route Distinguisher value for a VPN client network is through the use of concatenating a VPN host AS number concatenated with a serial number (RFC 2547). To what extent this semi-private use of AS numbers in a VPN context contributes to the consumption rate of AS numbers if difficult to assess, simply because these numbers may not appear in the public Internet. With the public Internet there are other contributory factors to AS Number consumption. ISPs with diverse product portfolios may wish to express different routing policies for various product families. Again this can be achieved through the use of distinct AS numbers of each routing policy set. Also there is little incentive for AS number return and recycling. With the current framework there is no cost to maintain an AS number allocation, and the overall characteristic of AS number allocation appears to be a "once and forever" allocation model. Once AS numbers are no longer required in the context of the public Internet, AS numbers generally do not return to the unallocated pool for subsequent recycling. Taken together these factors lead to the conclusion that continued AS number consumption is based on a larger set of considerations than just the dynamics of the service provider industry. Accordingly, we can be a little more confident in making the assumption that the drivers for AS number consumption in the recent past will continue to be drivers in the near term future. This leads to some further confidence in a predictive technique that uses recent consumption data to generate trends that can made predictive forecasts of future demands. We'll apply this technique to AS number consumption data to make some forecasts of the time by which the current AS number pool will be exhausted. AS Number Pool Status There are some 65,536 AS numbers. As noted already some 1026 numbers are reserved and unable to be used in the public Internet. This leaves 64,510 for use in the Public Internet. The pool of AS numbers is administered by the Internet Assigned Numbers Authority (IANA), and blocks of 1024 numbers are allocated to the Regional Internet Registries (RIRs) periodically when an RIR's unallocated AS number pool drops below a threshold level. As of July 2005 the IANA is holding 25,600 numbers, while 38,910 numbers have been allocated to the RIRs. The overall picture of the AS number space is shown in Figure 1 [fig1.png] Figure 1 - AS Pool Status The pool of 38,910 allocated numbers is further divided up to each of the RIRs, and the complete picture of AS number allocations in shown in Figure 2.  The large number of allocations listed to the ARIN registry includes a component of historical allocations undertaken prior to the establishment of the RIR system, so this is not an accurate correlation of the distribution of AS numbers across the various global regions. [fig2.png] Figure 2 - AS allocations to RIRs While some 38,910 AS numbers have been allocated by IANA, there is a further classification of AS numbers. A working pool of numbers is held by the RIR for subsequent assignment to ISPs. Of the assigned AS numbers some are visibly used in the inter-domain routing table of the public Internet, while others are not visible in the Internet. The breakdown of AS numbers into the RIR pool, assigned but not advertised, and assigned and advertised, as of July 2005, is shown in Figure 3. Of the 32,557 assigned AS numbers, some 19,859 are advertised, while 12,698 have been allocated in the past, but are not currently advertised in the BGP routing table. [fig3.png] Figure 3 - AS number status of Advertised, Unadvertised and Unallocated pools Again, this can be further broken down to each RIR, as shown in Figure 4. It is evident from this view that the ratio of unadvertised to advertised AS's varies across the RIR system. The highest ratio is in the ARIN region, which also coincides with the earliest allocations. There appears to be some relationship between the probability of an AS being visible in the routing system and the allocation lifetime of an AS. [fig4.png] Figure 4 - AS status pools by RIR IANA AS Allocations It is also possible to construct a number of time series of the AS allocation data, showing the growth in the use of AS numbers over the past decade or so. The first of these series is the allocation of blocks of AS numbers from IANA to the RIRs, shown in Figure 5. [fig5.png] Figure 5 - IANA AS Allocation running total This is not a smooth series as IANA makes periodic allocations of blocks of 1024 AS numbers to each RIR. This can be further classifies into per-RIR allocations, as shown in Figure 6. [fig6.png] Figure 6 - IANA AS allocations per RIR It is evident that the rate of AS allocation was highest in the ARIN region across the Internet boom of 1999 - 2002, while more recent allocation activity is evident in the European region of the RIPE NCC. RIR AS Allocations These allocated AS's are then assigned to ISPs by the RIRs, and a second time series can be generated, showing the rate of AS assignment to ISPs and Local Internet Registries. This allocation time series is shown in Figure 7. Again the series shows the effects of the Internet boom across the period from 1999 through to late 2001. The subsequent market correction is also evident, which was visible in the AS allocation rate change by early 2002. [fig7.png] Figure 7 - RIR Allocations The data can also be presented on a per-RIR basis, as shown in Figure 8. Overall the picture corresponds to the earlier IANA allocation data, where the rate of allocations in the ARIN region appears to be slowing down, while the trend in Europe in the RIPE NCC-serviced regions shows rising levels of activity in recent years. [fig8.png] Figure 8 - RIR allocations BGP AS Advertisements As well as looking at allocation rates, a further source of AS number data is the inter-domain routing table. The number of distinct Autonomous Systems advertised in the inter-domain routing space of the public Internet has been measured on a regular basis since 1997. The time series of this count since that date is shown in Figure 9. [fig9.png] Figure 9 - Advertised AS Numbers The current count of advertised AS numbers is some 20,000, as of July 2005. This time series has a visible correlation to the recent Internet business cycle, with a sharp upward trend across the Internet boom period of 1999 - 2001, and a marked change in the trend in early 2001. Since that date the rate of increase of AS numbers has been far slower. There are also some 12,600 AS numbers that have been allocated, but are not advertised in the BGP table. In terms of generating projections of AS number consumption it is also necessary to factor in the trends in this unadvertised AS number pool. This in shown in Figure 10. [fig10.png] Figure 10 - Advertised and UnAdvertised AS Numbers          It is evident that the number of unadvertised AS's is rising over time. The consequent question is whether this rate of increase is greater or less than the number of advertised AS's? One way to look at this is to look at the ratio of unadvertised to advertised AS's over time. This is shown in Figure 11. [fig11.png] Figure 11 - Time Series Ratio of Unadvertised to Advertised AS's This figure indicates that since 2003 the rate of growth of unadvertised AS's is slightly lower than the growth rate of advertised ASs. AS Disposition by AS Number Block Another way to look at the AS number space is to look at the AS Numbers in blocks of 256 AS numbers. The AS number pool has been one that to a large extent has been consumed in numerical sequence. Smaller AS numbers were allocated first, and higher AS numbers were allocated more recently. Figure 12 shows the breakdown of each block of 256 AS numbers, looking at how many numbers from each of these smaller pools is currently advertised, how much is not advertised, and how much is in the RIR pre-allocation pools. [fig12.png] Figure 12 - AS Number Status by Block Interestingly the older AS number blocks appear to have a much higher amount of unadvertised AS's than more recent AS number blocks. Another way to look at this is to examine the age distribution of Unadvertised AS's. As shown in Figure 13, the age distribution of unadvertised AS numbers is one where the probability that an AS is not visible in the routing table appears to be directly related to the period that has elapsed since the initial RIR allocation. The figure also shows a peak for very recent allocations, and it would appear that there is a delay of up to three months between the allocation action and the initial appearance of the AS in the BGP routing tables. What this table indicates is that there is a constant rate of change in the Internet environment, and, without any major reclamation of unused AS numbers, then once an AS number is no longer required it does not get handed back to the unallocated pool for reuse, but is placed into a dormant state where the AS is considered to be allocated, but is unadvertised. [fig13.png] Figure 13 Age Distribution of Unadvertised AS Numbers AS Consumption Projections At this point is is now possible to make some projections on AS number consumption. The technique here is to use the available data from a starting point of the start of 2003 and using a least squares best fit to the data generate trend data series. This trend data is then projected forward in time to forecast the point in time when the resource reaches a certain threshold point. This technique is perhaps best shown in Figure 14. Here the IANA allocation data is used as the base data series, and two projection models are used. The first model is to apply a linear best fit to the data. A linear model assumes that the underlying drivers for resource use are constant and the rate of growth over time remains a constant. The second model is an exponential growth model, where the underlying drivers increase over time. The model used here is an exponential model, where the growth rate doubles over a certain time interval. The definition of the doubling time interval is based on a least squares best fit of an exponential growth curve to the available data. [fig14.png] Figure 14 - Projections of IANA AS Allocations This projection shows that a best fit to a linear (constant growth) model of AS number allocation from the IANA pool would see the final AS block being allocated in the final quarter of 2013. An exponential (increasing growth) model of AS number allocation from the IANA pool would see the final AS block being allocated in early 2011. Do the other data series provide comparable outcomes? The next place to look is in the RIR allocation data. The true point of AS number exhaustion is not when there are no further AS's for IANA to allocate to the RIRs, but the point at which the RIRs have no further AS numbers to allocate. A similar technique can be applied to the RIR allocation data. This is indicate in Figure 15. [fig15.png] Figure 15 - Projections of RIR AS Allocations This projection shows a similar picture. A linear model projects exhaustion of the RIR AS number pool in mid 2014, and an exponential growth model predicts exhaustion by the final quarter of 2010. This is reasonably aligned to the IANA data. So which model is the best reflection of the underlying drivers of AS number consumption - linear or exponential? One way to delve a little deeper into the data is to look at the first order differential of allocation rates, to see if there is a discernable trend in that data series. The daily rate of AS allocations is shown in Figure 16 [fig16.png] Figure 16 - First order differential of the time series RIR Allocations This appears to indicate that the daily rate of AS allocation has increased over time. Between mid 2003 and the recent past the daily allocation rate appears to have increased from a mean of 9 to a mean of 12 AS's per day. This would indicate that a linear model appears to be an overly conservative predictive model, and does not accurately reflect the recent history of AS allocations. The other check of the most appropriate projection model is to look at the first order differential of the logarithm of the allocation rate. If this is a constant value over time then a exponential growth model would be a best fit to the data. [fig17.png] Figure 17 - First order differential of thelogarithm of the time series RIR Allocations Here the time series appears to be relatively constant since mid-2003, with a mean value of 0.0035. The next data sequence to examine is that of the advertised AS data series. A projection of Linear and Trend (exponential) models onto the data is shown below. [fig18.png] Figure 18 - Projections of AS Advertisements This projection is flawed, in that it assumes that all AS numbers will, eventually, be reclaimed and used in the Internet’s routing space. A slightly more relevant model of consumption needs to take into account that unadvertised AS numbers will not be reclaimed and reused in the routing system. The model used here is to project forward the number of AS’s found in the Internet's BGP table (advertised AS’s), and also model the best fit projection of the ratio of unadvertised to advertised AS Numbers. These two series will allow the projection of the total assigned AS numbers. Together with a model of the behavior of the RIR AS number pool, a complete AS number consumption model can be generated. The modelling uses the most recent 800 days as the baseline data for this exercise. The next data series is the projection of the unadvertised AS count / advertised AS count ratio. This is shown in the following figure, with a linear best fit superimposed on the measured data. [fig19.png] Figure 19 - Unadvertised to Advertised AS Number Ratio The next step is to model the advertised AS number count. The previous section looked at both linear and exponential trend models. This is shown in the figure below. [fig20.png] Figure 20 - Fit of Linear and Trend models to advertised data The most recent data and the correlation to the linear and best fit models is shown in the figure below. [fig21.png] Figure 21 - Fit of Linear and Trend models to advertised data, recent data The error between the original data series and the linear and exponential trend models is shown below. The closer the values in these series are to zero, the better the fit. [fig22.png] Figure 22 - Linear and Trend model error A best fit to the data can be established by looking at the first order differential of the data. If the first order differential is constant, then a linear trend model would be the best fit to the data. This is shown in the following figure. [fig23.png] Figure 23 - First order differential of the AS advertisement rate There is a rising trend in this data, indicating that an exponential model may be a better fit. Here the first order differential of the log of the data is shown in the following figure. [fig24.png] Figure 24 - First order differential of the log of the AS advertisement rate Using this exponential trend model of advertised AS number growth and a linear trend model of the ratio of unadvertised to advertised AS numbers, it is now possible to model each RIR's projected AS allocation rate and then look at the predicted behaviour of the RIR pool size for each RIR. This is shown below. [fig25.png] Figure 25 - Model of RIR AS Pool Behaviour Using this model of each RIR’s relative rate of allocation, it is possible to generate a model of AS number consumption. Here the end point is the date where the first RIR has exhausted its available pool of 2-byte AS numbers, and no further numbers are available in the IANA unallocated pool to replenish the RIR's pool. The data available suggests a best fit predictive model where this will occur on October 2010. [fig26.png] Figure 26 - Predictive Model of 2-Byte AS Number Consumption So it would appear that we are looking at a best fit model of accelerating consumption of AS numbers, and a projected exhaustion date of late 2010 of available AS numbers to allocate to ISPs, or some 5 years from the time of writing this article. What does an AS Pool exhaustion date of 2010 actually mean? The implication of these projections is that by late 2010 there would be no further unallocated AS numbers to distribute, and by that date  the Internet should be using a new version of the inter-domain routing protocol that does not rely on Autonomous Systems Numbers at all, or, more likely, that the Internet should be using a version of BGP that supports the use of larger AS numbers that are drawn from a number pool significantly larger than 16 bits. The first option appears to be somewhat unrealistic, to say the least. And the second option, although simpler and very much the preferred path, is still going to take some years to deploy, particularly considering the growing size of the Internet's inter-domain space and the diversity of these component domains. When contemplating a transition to a larger AS Number pool, it should be remembered that every day there are more networks that will need to undertake a transition to a longer AS number field in their deployed instances of the BGP protocol. The steps in this transition path appear to include: - the completion of the relevant protocol standards for a larger AS number field in BGP, - the production of code in available implementations of BGP that support this protocol standard, - various forms of testing of this code, both in terms of its correct operation and interoperability, and in terms of the correctness and viability of the relevant transition steps, - developing the necessary infrastructural support system to manage the distribution of this new number pool, and - a process of deployment of this protocol so that the deployment of larger AS numbers can commence well before the point at which the existing AS number pool is exhausted. Even an aggressive schedule of transition across such a large and diverse network as is the Internet will take a number of years to reach the final step. It also appears that a prudent course of action would see us reach that position not by 2010, but by 2008 at the latest, allowing us a margin of some two years (and some 10,000 remaining AS numbers) to complete the task. The implication is that we have reached the end of the period when the agenda for transition can be further deferred without undue risk. We now have some 3 years to undertake these tasks if we want to avoid an uncomfortable phase of potential disruption in the Internet's inter-domain routing space. In the next article we will explore the aspects of the proposed 4-byte AS number space and the manner by which the Internet's transition across to this space can be performed. Disclaimer: The above views do not represent the views or positions of the Asia Pacific Network Information Centre. About the Author: GEOFF HUSTON holds a B.Sc. and a M.Sc. from the Australian National University. He has been closely involved with the development of the Internet for many years, particularly within Australia, where he was responsible for the initial build of the Internet within the Australian academic and research sector. He is author of a number of Internet-related books, and is currently the Senior Internet Researcher at APNIC, the Regional Internet Registry serving the Asia Pacific region.