This is the long version of the blog post. A shorter version is available here.
There is a graph Iâ€™ve been pondering for some time that illustrates the topic Iâ€™d like to look at in this article.
There are a number of “route collectorsâ€ that gather up the inter-domain routing perspective from a number of distinct vantage points across the Internet. Figure 1 shows a plot of the number of routing entries seen in a daily snapshot from each peer of one of the Route Views servers. Each separate line in this plot is the number of route objects being passed to the Route Views server from one of its routing peers.
There are a number of servers that take in a number of BGP vantage points and publish the union of all these individual streams of routing information. In this article Iâ€™m using data pulled from the Route Views Project, as the collections are a useful size and readily traversed by scripts. The RIPE NCC also runs a set of route collectors in their Routing Information Service (RIS), which contains a large set of route snapshots and BGP updates.
What this plot is showing is that the perspectives of the Internetâ€™s routing system are slightly different for each routing peer of Route Views. Surely if the Internet were to be a single coherent domain of connectivity, and if everyone could uniformly reach everyone else somehow, then wouldnâ€™t we expect that the routing system, the system that ultimately ensures that everyone is connected to everyone else, to be much the same everywhere? And if that were the case, and routing would provide much the same view of the Internet irrespective of the particular vantage point of the BGP speakere. The consequence would be that instead of seeing in Figure 1 some 40 different tracks for the year, one from each distinct routing vantage point, we should see the same single line, drawn over 40 times.
But what this figure shows us is that each of these routing vantage points sees a slightly different Internet from their perspective. And these differences are not just temporary. Across all of 2015 these various routing vantage points see a consistently different number of route objects in their local routing system. So its not something that occured at a particular point in time and corrected via the normal operation of the routing protocol. These differences are consistent across the entire year. Some route advertisements are simply not visible from some routing vantage points. Part of the reason why we operate these routen collectors is to gather these various perspectives and understand these differences, so Iâ€™d like to look into these differences in a little more detail and see if we can conclude anything about Internet connectivity.
It might be possible to say that these differences have occured as some property of size and age, and that the venerable IPv4 Internet has these divergent routing views solely due to its age and size. So a â€œyoungerâ€ and smaller routing system may well show a single view by that reasoning. The second figure to condsider that of the IPv6 network over 2015. Rather than some 600,000 entries there are just 20,000. And still we see that some BGP speakers see more routes and others see less, and this is persistent and stable across the entire year.
What do these differences mean? Are we seeing evidence of a fragmented Internet where some places on the Internet cannot reach other places? Are these differences in the perspectives of various routing vantage points signs of underlying fractures of the fabric of connectivity in the Internet?
Before leaping to conclusions here, itâ€™s useful to pull together some further data. One possible explanation of the difference in the number of advertised routes is that the routing system contains two components of information: basic reachability and information relating to the policy of how to reach a destination. With a broad brush one could call this latter set of routes “traffic engineeringâ€ advertisements. They do not change the overall set of addresses that are announced as reachable in the routing system, but qualify some of this information with refinements on how to reach a particular address. One half of the 600,000 entries in the IPv4 routing system announce â€œreachabilityâ€ as aggregate announcements, or â€œrootâ€ routing prefixes. The other half qualify some of these basic reachability entries by refining this reachability by proposing subtly different paths (or not!) to take to reach the destination. So it may be that the differences seen from each of these vantage points are not in fact differences in basic connectivity – but the represent differences in these more specific announcements, and they represent that in different parts of the network there may be different preferred ways to reach certain destinations.
The difference in the number of routing entries as seen at each particular vantage point could be explained by observing that the efforts to exert fine-grained control over the particular paths taken by inter-domain traffic through the advertising of more specific routes are intentionally localized to some extent. The propagation of these traffic engineering prefixes is similarly intentionally localised to a particular locale or region. The conclusion therefore could well be that the variance in the number of routing objects seen at each of these routing vantage points in both the IPv4 and IPv6 networks is not due to any fundamental difference in the reachability of any addresses, but simply due to the desire to exert some additional control over the paths taken by traffic.
One way to test the validity of this conclusion is to look once more at the route collector data, but this time instead of looking at the number of route objects that are visible at each routing vantage point, lets look at the total span of addresses that are advertised as reachable. If this theory is correct then the total span of addresses should be the same from each of these vantage points and we could well be justified in believing that the Internet is indeed a uniform domain of connectivity.
Again the data does not agree with this theory – when we look at the data (Figure 4) we see that there is a range of some 5 million addresses in IPv4 where some vantage points see a larger set of addresses advertised as reachable than other vantage points. And again there is a consistency across the year: those peers that see a larger span of addresses than others appear to do so consistently across the entire year. And again, with three exceptions, those that advertise a lower span of addresses do so consistently across the entire period. The exceptions show one trend of approaching a route span that get closer to the group, while the other two peers are announcing a span that appears to be shrinking over the year.
In IPv6 we see the same situation, where different vantage points see a different span of addresses. In IPv6 there are large scale differences, so that at the extremes one routing peer sees one half of the total address span of the peer announcing the largest range (Figure 5). The difference is here is an outlier that is not seeing the same address span to the extent that they are not advertising to Route Views a /16 route that all other peers are advertising. The explanation is, this case, easily found: there is only one /16 advertisement in the IPv6 world, which is 2002::/16, the advertisement of the anycast 6to4 tunnel ingress fot the 6to4 tunnelling transition technology. It may be that this network is not operating a 6to4 gateway, or, more likely, they havce elected to run a local 6to4 relay and have restricted its advertisement to a mimited local which does not onluce their peer session with Route Views.
Figure 5 tends to suggest that IPv6 is showing a tight â€˜clusterâ€ of address reachability and in this respect is perhaps better than the equivalent picture in the IPv4 Internet However, this is not a good reflection of the IPv6 Internet. When we look at just this central cluster (Figure 6) its clear that like IPv4 there is a variance, and some networks see up to 600 more /32s than others, encompassing a range of address reacahability of a /23 in address terms.
Letâ€™s keep drilling down in this space for one further level of detail. One way to examine this is to define a â€œcoreâ€ of announced prefixes. Firstly, lets select those peers that advertise a minimum of 85% of the average number of advertised routes, so as to eliminate from consideration those peers that only provide a partial route set to route views. Then weâ€™ll use a threshold of 5/8 of the remaining peer set, or 62.5% to define a â€œquorumâ€. If 5/8 (or more) peers announce an address prefix, then we can include this prefix in a quorum set of announced routes. We can then take the set of â€œrootâ€ quorum prefixes and define a quorum span of addresses, which we can then use to compare against each peer that is announcing a route table to Route Views. What we are interested in is the extent to which individual peers announce a greater span of addresses that can be seen in the quorum set, and, by the same token the total span of addresses that exist in the quorate set, but are not explicitly announced by the peer. For example, Telstra in Austalia (AS1221) announced an address span of the equivalent of 166.06 /8s from the quorum set. Some 14 million IPv4 addresses that form part of the quorum set were not announced by AS1221, and this network also included a further set of 199,552 advertised addresses that were not part of the quorum set.
The complete analysis of all peers from a Route Views BGP snapshot taken on the 17th February 2016 is shown in Table 1. Itâ€™s evident from this table that nobody sees the same set of addresses as anyone else, and the degree of variance can be quite high.
|Route Views IPv4 Peers
|KPN KPN B.V., NL
|ESNET – ESnet, US
|TELUS Comms, CA
|SPRINTLINK – Sprint, US
|TELIANET TeliaSonera AB, SE
|AOL Transit Data Network, US
|Internet Initiative Japan, JP
|NTT America, Inc., US
|RG-BIWA – RGnet, LLC, US
|RUSNET-AS NPO RUSnet, RU
|Level 3 Communications, US
|Level 3 Communications, US
|Daisy Communications Ltd, GB
|GT-BELL – Bell Canada, CA
|Hurricane Electric, US
|AT&T Services, US
|AsiaPac Advanced Network, JP
|OBIT-AS OBIT Ltd., RU
|Education Networks, US
|Caucasus Online, GE
|Cogetel Online, KH
|SOFIA CONNECT EOOD, BG
|Connectivity IT, AU
|ASN-NY2 – Digital Ocean, US
|ASN-1 Digital Ocean, EU
|ASN-3 Digital Ocean, NL
|NY3 – Digital Ocean, US
Table 2 shows a similar report for IPv6. Again its evident that there is no single view here. Some peers have little in the way of addresses over the quorate set, while others are seeing some additional 120 â€“ 130 /32s. The picture of missing addresses is also a mixed one with some peers reporting little in the way of missing data, while others are not seeing a somewhat larger address set.
|Route Views IPv6 Peers â€“ Address Spans are show in units of /32s
|HOTNIC – Hotnic LLC, US
|NTT America, Inc., US
|RUSNET-AS NPO RUSnet, RU
|SPRINTLINK – Sprint, US
|Verizon Business, US
|Digital Ocean, EU
|AT&T Services, US
|Digital Ocean, US
|Hurricane Electric, US
|Internet initiative Japan, JP
While a single snapshot of the routing system can illustrate that in terms of explicitly announced address space there are significant differences to be seen in various parts of the Internet, what it cannot show is whether such differences are part of the normal operation of a dynamic routing protocol, which would imply that a snapshot taken one day later, or even one hour later, would see a distinctly different view, or whether these differences are structural, in which case the picture of the differences in the anniounced address set from each peer would be relatively constant over time.
An analysis of daily routing snapshots from Route Views is shown in Figure 7. The scale of this plot is Â±100M addresses, or approximately 6 /8s. Each peer traces two lines in this plot. The positive line is the number of additional addresses this peer is advertising in addition to the addresses that form the quorum set. The line in the negative space is the total amount of address space that is in the quorum set, but not advertised by this peer. Some peers see a considerably smaller span of addresses than others, and this difference is stable over time.
When we look at just the cluster closer to the quorum by adjusting the scale of the plot to Â±5M addresses (equivalent to a /10) we see a similar picture of stability of these address sets. There is some evidence of day-to-day variability at this level of detail. Interestingly there appears to be division in this data at the start of 2016, where a cluster of peers are advertising some 4M addresses (a /10) that are not being absorbed into the quorum set. This pool of additional addresses was some 2M addresses in the middle of 2015, and has doubled in the intervening 7 months.
We can also look at this at the level of detail of a span of a /16, or 65,536 addresses.
Here a number of peers are seeing additional addresses that are not part of the quorum set, and the extent to which they vary from the quorum are somewhat unstable over the year. Few peers differ from the quorum set by up to 130,000 addresses (Figure 9).
There is a similar story for the IPv6 network, where individual peers can see differences in the address span from the quorum set that encompass some 1,000M /48â€™s (Figure 10). These aonmalies appear to be relatively long lived, spanning some months.
At a finer level of detail, spanning Â±50M /48s (roughly a /22) we see see a higher degree of divergence freom the quorate set, particularly where individual peers are missing advertisements that are part of the quorum set.
Finally, when we look at the same data with a span of Â±5M /48s (roughly a span of a /27) we can see the movement of indivdual /32 advertisements in and out of the divergent set for each peer, but there is an underlying stability to these differences over the observed period for most peers.
How serious is this issue? The basic question is perhaps unanswerable in any precise manner. This is the question: â€œTo what extent are attempts by one Internet user to contact another user, or some service, prevented by a structrual breakage of the interconnectivity of the Internet?â€
While this is perhaps an unanswerable question, there are some perspectives that can provide some indirect pointers to help quantifying the extent of this issue on todayâ€™s Internet.
The first observation is that what we see in the routing system as the control plane of data and what happens at the packet forwarding level is not always aligned. As was demonstrated in a paper at IMC in 2009 (Internet Optometry: Assessing the Broken Glasses in Internet Reachabilityâ€, R. Bush, O. Maennel, M. Roughan, S Uhlig, ACM SIGCOMM IMC, 2009), a number of network operators were observed to be using a â€˜defaultâ€™ route to complement upstream connectivity. This implies that as a packet traverses a sequence of upstream connections it does not necessarily need to follow explicitly advertised routes, but instead can follow the default route. What is essential for widespread symmetric connectivity is that the routes are present as explicit routes in the tier 1 providers, as there is no further default route in use at this point in the Internetâ€™s routing hierarchy. This paper reported that some three quarters of the Ases at that time behaved in a manner that was consistent with an upstream default. However, this finding applies along data paths leading along sequences of â€˜upstreamâ€™ inter-AS relationships. It is an unusual case to see a network provider pointing their default route across a peer link, and even more anomalous to see default pointing to a customerâ€™s network. So, the use of default assists to some extent, but it can only mend a certain subset of routing anomalies, and its by no means a panacea.
The second issue is connectivity asymmetry. Its often the case that we think that connectivity breaks are symmetric, so that if endpoint A cannot send packets to endpoint B then the reverse is also assumed to be the case. In packet switched networks, particularly ones like the Internet that use a unidirectional routing protocol to maintain its internal topology and reachability, such assumptions about connectivity symmetry do not hold. In these scenarios it is not uncommon to see cases where A cannot pass packets to B but B can still pass packets to A. Can we see evidence of this?
At APNIC we run a measurement system where some 4 – 10 million Internet endpoints each day are enrolled to perform a small set of basic connection tests. These pseudo-randomly selected browsers drawn from across most of the Internet all attempt to make contact with a small set of servers that are instrumented to record connection attempts. Oddly enough not every connection attempt succeeds. Regularly there is a pattern of asymmetric failure, where the endpoint can send a packet to the experimentâ€™s server, but the serverâ€™s attempt to respond to the endpoint fails.
Over 2015 we looked at connectivity attempts from some 446 million IPv4 endpoints, and saw 1.1 million asymmetric failures. The raw data appears to be suggesting that approximately 1 in 400 connection attempts fails in this asymmetric manner. Is this the basic evidence that suggests that not everything is connected to everything else all of the time? The daily connection failure rate is shown in Figure 13.
Now there are a number of potential reasons for connection failure in thos particular experiment, and the data cannot distinguish between connections initiatited in the context of the experiment and the various address scans that scan the Internet address space using TCP SYNS in ports 80 and 443. So its unlikely that all the the asymmetric connection failures shown in Figure 13 are attributable to asymmetric connectivity. But its likely that there is a significant component of failures due to this particular form of asymmetric connectivity fragmentation in the Internet.
A comparable picture of IPv6 asymmetric failure paints a somewhat worse situation (Figure 14).
It is likely here that a number of additional factors come into play to account for this relatively high asymmetric connection failure rate of 1 in 50 connections, including suspected issues with the Consumer Premises Equipment (CPE) and a piecemeal picture of IPv6 support, but within this rather disappointing figure asymmetric network connectivity is a contributing factor.
Why is this?
Or, to put the question in the opposite sense, why isn’t all of the Internet fully connected? Surely this is a case where individual motivations coincide with the common good. Each connected network is best served by being reachable from the entirety of all other connected networks, and network is potentially detrimentally affected when there are networks that cannot reach them. This is also a symmetric desire, in that the same applies to the set of networks that can be reached by this connecting network. The theoretical value of the connection is maximised when the network can reach, and be reached by, all other connected networks.
In practice however it is not possible to purchase a service that guarantees such universal reachability. Service providers strive to fulfil such expectations on the part of their customers, but universal connectivity falls into the category of â€˜best effortâ€™ as distinct from â€œservice garanteeâ€.
Why is this?
Universal interconnection is not a requirement imposed by any regulatory fiat, nor by any deliberate arrangement between network operators. Interconnection is its own market, and the outcomes can be viewed as market-based outcomes.
Each individual service provider network operates in a domain or â€œpeering” and “tieringâ€. â€œTieringâ€ refers to an implicit structuring of networks into a collection of customer and provider relationships. This tends to be hierarchical, in that if A is a customer of B is a customer of C then it would be highly irregular to see that C is a customer of A. (Figure 15)
In this example A would be a network operating a tier 3, B at tier 2, and C at tier 1, and the money associated with the provision of connectivity and transit services would conventionally flow along the same path. In this particular case, absent any other inter-AS relationships, A has the expectation that B can provide a complete set of routes to all other connected networks, and B is relying on C in the same manner.
â€œPeeringâ€ refers to a subtly different relationship between networks, where neither is a customer of the other. The typical template of a peering relationship is that the two peering networks exchange reachability of their own and their customersâ€™ routes, but do not exchange routes that they learned from being a customer of a higher tier provider, and nor do they exchange routes learned from other peering relationships. So in our simple three network picutre of A -> B -> C, if we introduce a fourth network, D, who peers with B, then D will learn how to reach addresses of endpoints located in networks B and A, but not C. (Figure 16)
There is no incremental reachability achievable to D were it to also peer with A, and if it did B may come to the conclusion that if D is peering with one of its customers then D should also be a customer, as a peering relationship normally infers that both networks are positioned at the same tier in the customer/provider hierarchy. Obviously, commercial reality is far subtler than this and network operators have managed to invent many variations on this basic theme, but the underlying principles of interconnection are relatively constant.
If all of these relationships were static this situation would be tractable, but of course the system is constantly changing. Providers shift their relationships in the connectivity ecosystem. New providers appear, such as content distribution networks, and of course there are acquisitions, mergers and splits where the resultant entities need to recalibrate their position in the realm of connectivity.
One view is that is a surprising outcome that the connectivity on the Internet is as stable and as comprehensive as it is, given that this is a market driven outcome without any particular guarantees of the right outcome.
Perhaps it’s not as surprising as that. Another, admittedly cynical, view is that its all about what one would loosely call an â€œinformal cartelâ€ of the tier 1 providers that are at the core of connectivity. As long as each connecting network takes the effort to ensure that their routes are advertised to at least one tier one router via one or more customer / provider relationships then some level of basic connectivity is an outcome. After that basic connectivity is achieved, then peering is there to minimise the cost and/or improve the service for selected routes. Within this perspective Internet-wide connectivity is defined almost completely by the ability to have oneâ€™s routes passed into the tier one provider cartel. This group of peered interconnected networks essentially define what it is to be connected in the Internet. So another view of Internet connectivity is that this is not a distributed open market for connectivity, and instead we have a self-perpetuating routing monopoly at its â€˜coreâ€™!
Is the Internet fully interconnected? Probably not. Around its edges it a grey zone of connective asymmetry where you might be able to send a packet to me, but that does not mean that you get to see my response!