Reducing the BGP Table Size – A Fairy Tale

Here’s the chart of the current state of the Internet, as autonomous system numbers (ASN) and IPv4 (above) and ASN and IPv6 prefix count (below):

Figure 1: ASN count and prefixes over time

Because of the scaling differences between the two types of IP, it’s a little hard to tell, but this pair of graphs makes it clear that first, there are far more announced IPv4 prefixes than IPv6, and second, that the rate of growth in IPv6 doesn’t look to be approaching that of IPv4 in either prefix terms or ASN terms.

The ratios of IPv6 to IPv4 appear to be tracking the deployment rate of IPv6 in both prefix and ASN counts, and neither are growing spectacularly. ASN deployment is actually not bad, approaching 1/4 (25%) of globally visible ASNs in BGP making one or more IPv6 announcements. In prefix terms however, it’s a sad story. IPv4 prefixes continue to deploy in what looks to be a non-linear rate, but the ratio of IPv4 to IPv6 is not improving at the same rate as the ASN ratio.

So while its tempting to say “Oooh look: IPv6 is growing faster than IPv4” it’s also possible to say “IPv6 is much much smaller than IPv4, both in terms of the prefix count, and the number of ASNs routing it”. In fact, here’s a table showing the current difference between the two protocols:

Clearly, IPv6 is operating at a far lower intensity than IPv4, both in terms of prefixes, and ASNs.

A central thesis for some, which came out during the discussion at the last APNIC meeting, is that the IPv6 routing cloud will only be ‘real’ when it has as many announced prefixes as the IPv4 cloud. Since we currently have around 600,000 prefixes in the IPv4 BGP view, this tends to suggest that we have to plan for that many prefixes in IPv6.

But is this true?

An alternate view of ‘success’

What we see in IPv4 BGP is a huge success story: a story about two different kinds of success. First we have successful uptake of a technology (IP) and a specific form of that technology (BGP) being deployed worldwide at scale. And, second, we have the success story of IP address management in the RIR system which helped extend the life of the IPv4 story by many years, preventing excessive consumption of the older A/B/C classful prefixes.

So, the IPv4 BGP success story is in part dominated by the adoption of processes to ‘ration’ IPv4, which made it necessary for people to route a larger total number of prefixes because they had no choice: they had to get un-aggregateable prefixes in order to get that many addressable end-hosts.

But in IPv6, this isn’t necessarily true. It’s more likely that a significant number of IPv6 holders can live inside one /32 assignment from a Regional Internet Registry (RIR), because this represents the entire IPv4 space, 2^32 bits of assignment inside that organisation, to the /64 level which is the normal default host assignment. So everyone has enough IPv6 for simplistic models.

Ok. So let’s imagine a counter-factual IPv4 world.

What if prefix-aggregating pixies really exist?

What if we could magically fix de-aggregation in IPv4 address space that was handed out in needs-based chunks? You can visualise the magic fix for this being “prefix pixies”, that, every night, when we’re asleep and the Inter-tubes only carry trickles of IP packets, they go around every BGP speaker on the global Internet, and they swap addresses.

If you have 128 different /24 prefixes which add up to a total of a /17 they magically give you one contiguous /17 of space. So you don’t have to announce 128 prefixes any more: you just announce one.

And the 128 prefixes you had, they get sorted very quickly, back into the right holes in the address space, and then at the next BGP speaker, they do the same trick: they swap the 1,024 different /24 prefixes (it’s a bigger ISP) out, and they replace it by a /12 of continuous address space. And so on. All around the world.

So, if you do this trick, how big is the current IPv4 routing table?

Well, it’s pretty small. It’s actually only 92,000 prefixes big. Once the magic pixie dust settled, everybody has as much IPv4 space as before, just space which was expressible in a far smaller set of prefix originations.

(everyone knows routing works on pixie dust: when you see smoke coming out of a router, that’s the pixie dust leaving and soon after it crashes.)

The “prefix pixies” are smart: if the change would increase the number of prefixes announced, they don’t do that. in IPv4, that almost never happens. But in IPv6 the effect is quite extreme in how many new prefixes are needed to represent a non-aligned set of a prior IPv6 prefix which now is a set of smaller chunks. This is because people have few prefixes, and if there is ‘hole punching’ (i.e. give a more specific to a customer to route from another ASN, but still announce the covering prefix) this would result in many extra prefixes if our pixies wouldn’t be careful.

Figure 2 shows the IPv4 and IPv6 prefix counts over time, comparing the unadjusted (real) number of prefixes seen, and the minimum necessary prefix count, if we could reorganise the address map to give people aligned space. This can be considered a theoretical minimum, and we fully realise we’re glossing over some practicalities that make this infeasible in practice, but hang on, we’ll deal with some of that later.

Figure 2: Number of unadjusted and minimum prefix counts

This reorganisation has had a radical effect on the overall prefix count. Firstly, it shows a decline from arguably exponential growth to a much more linear rate of growth in IPv4. The total prefix count drops from over 500,000 to under 100,000. And secondly, even in IPv6 there are opportunities to reduce the number of globally routed prefixes if we could reorganise.

But the clear observation is that if we compare the IPv4 and IPv6 minimum prefix dynamics, there is no sign of convergence of IPv6 onto IPv4 in these ideal conditions. The rate of IPv6 deployment does not appear to be such that we can expect to see similar prefix intensities anytime soon.

Figure 3: IPv4 and IP IPv6 minimum prefix counts compared

A major factor to consider in the minimum prefix counts is that some of the prefixes announced can not be ignored: they are there for either ‘customer nets’ being dual-homed, or for traffic engineering.

Classifying prefixes according to Figure 4, many prefixes are delegated (i.e. there is a less specific originated another ASN), or deaggregated (i.e. there is a less specific originated from the same ASN).

Figure 4: The four types of prefixes explained (figure taken from Cittadini, Luca, et al. “Evolution of internet address space deaggregation: myths and reality.” Selected Areas in Communications, IEEE Journal on 28.8 (2010): 1238-1249.  )

Address space that is delegated is handled elegantly by the prefix-pixie model: this address space only counts towards the ASN announcing it and is subtracted from the address space for ASN that originates the covering prefix.

Address space that is deaggregated is only counted once towards the ASN that originates it, but we can’t ignore it: some of this is for specific purposes like traffic engineering, or prefix hijack protection. For this reason we counted the number of prefixes per ASN in this category, so we can take them into account in this model.

For some networks our prefix-pixie trick may not work: Some networks announce a number of small address blocks, and can’t fulfil their routing needs with a single covering prefix. An example would be content networks without a backbone between their PoPs. For now we ignore these networks in our model and assume the vast majority of the Internet exists of contiguous ASNs capable of ingesting traffic for all of its address space at all of their ingress points so they could originate their full address space from all BGP speakers at these ingress points.

We can’t ignore the deaggregated address space though. So, if we take the very conservative approach that none of the deaggregation is spurious (even though we know some probably is), we’d need to put all of these prefixes back into our model. Figure 5 shows the volumes of these prefixes compared to our minimum necessary prefix counts.

Figure 5: Deaggregated and minimum prefix counts

An interesting quality in the data is that the amount of deaggregated more specifics seen in IPv6 is significantly lower than the amount of originated prefixes, whereas in IPv4, it’s significantly more than the minimum necessary to route the hostcount equivalent: This is because there is a lot more de-aggregation going on in IPv4, and it’s likely that some of this contributes to the concern that IPv6 is not yet ‘real’ because these engineering differences haven’t yet emerged.

So taking this model of the combination of the minimum necessary prefix counts, and the observed deaggregation, what does the scale difference between IPv4 and IPv6 look like?

Figure 6: Deaggregated and minimum prefix comparison

If size were the only thing that mattered, this would still be a sad story for IPv6, because the weight of deaggregation in IPv4 is large. But there are signs that the comparative scale between the two network ecologies is changing. It is likely that IPv4 is going to see more fragmentation, especially with RIRs depleting their IPv4 pools and the increase of market-based IPv4 address transfers. It is also likely that the pace of IPv6 deployment, and its deaggregation will be increasing.

Conclusion

Do we have to plan for dealing with as many IPv6 prefixes as IPv4 prefixes? This analysis suggests we don’t. IPv6 address space isn’t rationed as IPv4 address space was, and thus the theoretical lower bounds of how the current IPv4 and IPv6 routing tables are calculated, are radically different. The IPv6 routing table is much closer to its theoretical minimum, so if our assumptions hold, this suggests a mature IPv6 routing table being significantly smaller then the equivalent IPv4 routing table.

We should be pretty happy with our little helpers!

Figure 7: our little helpers