BGP routing table growth is one of the major Internet scaling issues, and prefix deaggregation is thought to be a major contributor to table growth.
While some prefixes are announced for traffic engineering (TE), prefix hijacking protection, or traffic blackholing, they are often not necessary for reachability. These prefixes put a burden on the overall routing system by providing additional features to a few players.
We focused on this issue in some recent research. Firstly, we quantified the fragmentation of the routing table by the type of IP prefix. We observed that the proportion of deaggregated prefixes has quasi doubled in the past 15 years. Our study also showed that the deaggregated prefixes are the least stable; they appear and disappear more frequently.
While we cannot see significant differences in path prepending between the categories, deaggregated prefixes do tend to be announced more selectively, indicating traffic engineering. We found cases where lonely prefixes are actually deaggregation in disguise.
Indeed, some large transit ISPs advertise a large number of lonely prefixes when they own the covering prefix. We show the extent of this practice and its negative impact on the routing table even though it can usually be avoided.
Introduction
We used data from the Level3 (AS3356) BGP feed into the Route Views project, a full feed from a large transit provider. We found no notable differences among Route Views or the RIPE Routing Information Service RIS BGP peers for our purpose, so we considered this feed representative. We classified prefixes using the taxonomy defined in reference 1 below:
- Lonely: a prefix that does not overlap with any other prefix
- Top: a prefix that covers at least one smaller prefix but is not itself covered
- Deaggregated: a prefix covered by another less specific prefix originated by the same AS
- Delegated: a prefix covered by another less specific prefix originated by a different AS
Figure 1 shows an example of this classification.
Figure 1: BGP prefixes classification, taken from Cittadini et al [1]
In this configuration, we have three ASes. A route collector gathers all prefixes announced by AS 20 and classifies them. Here, AS 20 hands over a customer view to the monitor. 10.2/16 is not overlapping with any other prefix, so it is classified as lonely. However, 10.1/16 is covering two other prefixes: it is classified as top. 10.1.1/24 is announced by the same AS as its covering prefix (AS 10), so it is deaggregated. Finally, 10.1.2/24 is covered by 10.1/16, but it is announced by another AS (AS 20): the prefix is delegated.
We classified the data from the past 15 years. As shown in Figure 2 below, the proportion of deaggregated prefixes increases from 22% in 2003 to 38% in 2017, while the proportion of delegated prefixes declines from 30% to 13%. Top and lonely prefixes are stable, at 42% and 6%, respectively. Recently, the rate of increase of deaggregated prefixes is not as steep as observed previously (see reference 1). As the routing table increases, the absolute number of deaggregated prefixes increases but the proportion of these prefixes does not increase as much. This slowdown is also visible in the rate of decrease of delegated prefixes.
Figure 2: Prefix classification over time
Is it Traffic Engineering?
We looked at AS path prepending and at selective announcements, as these are signs of traffic engineering (TE). Here, we used data from all the Route Views route collector peers. We saw a 3% increase in popularity of AS path prepending: from 9% of all prefixes in 2001 to 12% in 2016.
We noted that this increase of AS-path prepending is not specific to deaggregated or lonely prefixes; it occurs for all classes of prefixes. To detect selective announcements we count, given a prefix, how many peers see it. We consider a prefix to be selectively announced if it is seen by less than half of the route collector peers. Figure 3 shows our results.
Figure 3: Proportion of selectively announced prefixes by category over time
It appears that lonely and deaggregated prefixes follow the same trend, and are the most selectively announced. In 2016, 13% were selectively announced, where the proportion was 5% for delegated prefixes and 1% for top prefixes. We conclude that not only deaggregated but also lonely prefixes are used for traffic engineering.
Who is engineering traffic?
To see what kinds of ASes use TE, we first selected the tier-one ASes using CAIDA’s AS ranking and selected the known content providers, based on the presence of keywords in their name. We extracted 30 large transit providers and 137 content providers out of 53,731 ASes. The complete list of keywords is available on GitHub for review. The large transit providers announce 2.33% of the prefixes: these prefixes correspond to 9.97% of the address space. Similarly, the content providers announce 1.25% of the prefixes, which correspond to 0.67% of the address space.
As shown in Figure 4, we find that large transit providers (followed by content providers) tend to announce more deaggregated prefixes: 45.22% of all prefixes announced by large transit providers are deaggregated. To a smaller extent, they also advertise more lonely prefixes than other AS types: 28.73%. Large transit providers may be splitting their address space into smaller prefixes to do traffic engineering or segregate PoPs.
Figure 4: Distribution of the percentage of deaggregated prefixes per AS
Hidden deaggregation
We also tried to detect prefixes moving between categories. We observed a significant number of lonely prefixes becoming deaggregated and vice versa. We believe that these movements happen when an AS that announces multiple lonely prefixes starts announcing a large covering prefix, and the reverse. This hints that our original postulate for deaggregated prefixes may also apply to the class of lonely prefixes.
Some ASes may hold a large prefix but announce it only in smaller pieces. Why would ASes do that? Probably for the same reasons as the advertisement of deaggregated prefixes; we saw that both types of prefixes are selectively announced to the same extent. In the case of lonely prefixes, operators may assume sufficient redundancy to not need the advertisement of the covering prefix. The aggregation of the prefixes from these two classes could help reduce the size of the routing table. This is a new finding: Cittadini et al [1] do not consider lonely prefixes to be aggregatable.
Reducing the routing table size
We saw in section 2 above that both lonely and deaggregated prefixes are used to do traffic engineering. In this section we want to estimate to what extent these prefixes could be aggregated. We consider two prefixes to be aggregatable if (1) they have the same AS origin, (2) they are consecutive, and (3) the aggregate falls on a power of two boundary. This lets us estimate the level of pollution of the global routing table.
This estimate does not take into account the fact that some content providers may split their address space because they lack a proper backbone. In this case, replacing the prefixes by an aggregate would not be an option, as traffic may not reach the proper geographic location. Figure 5 shows the lonely and deaggregated prefixes that could be removed from the Level 3 feed after aggregation.
Figure 5: Amount of aggregatable prefixes
This amount is increasing: going from 9.5% aggregatable prefixes in 2001 to 19.5% in 2016. Clearly, there would be a real benefit to aggregate lonely and deaggregated prefixes as much as possible. The gain is less than described in Sobrinho et al [2] but our criteria allow one to aggregate prefixes and still be able to do route origin validation (see Why origin validation can’t help DRAGON routing).
Related work and conclusion
Others have studied the extent of pollution of the routing table. In this work, we extend Cittadini et al [1] and study the state of deaggregation from 2001 to 2016. In Reducing the BGP table size – a Fairy Tale, George Michaelson et al. compute the required allocation if prefixes could be redistributed optimally.
Dragon [2] is a solution to dynamically filter the deaggregated as well as to aggregate prefixes conditionally while ensuring BGP convergence and correctness. Krenc and Feldmann [3], looking at only delegated prefixes, find both provider-to-customer delegation and the reverse.
In this work, we observed that the proportion of deaggregated prefixes has increased over the past 15 years. While we see only 3% growth in path prepending, deaggregated and lonely prefixes tend to be announced more selectively, indicating traffic engineering. We find cases where lonely prefixes are actually deaggregation in disguise.
Traffic engineering is not solely used by stub ASes. We found that some large transit ASes heavily fragment their address space. Aggregating these prefixes would reduce the routing table size by roughly 20%. The key question is, which traffic do they try to control? If it concerns the traffic from a few ASes, one could imagine TE being negotiated separately, outside the routing protocol.
Please also see my presentation at the RIPE 74 Meeting in Budapest.
Julien Gamba is a graduate student at the University of Strasbourg, France, who is currently working on iBGP correctness.
Contributors: Romain Fontugne, Cristel Pelsser, Randy Bush, Emile Aben
References
- L. Cittadini, W. Mühlbauer, S. Uhlig, R. Bush, P. François, and O. Maennel. Evolution of internet address space deaggregation: Myths and reality. IEEE journal on selected areas in communications, 2010.
- J. L. Sobrinho, L. Vanbever, F. Le, and J. Rexford. Distributed route aggregation on the global network. ACM CoNEXT 2014, 2014.
- T. Krenc and A. Feldmann. BGP prefix delegations – a deep dive. In IMC 2016, 2016.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.