On the Internet Everyone is Connected to Everyone Else – Right?

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.

Figure 1 – Number of Routes announced by each BGP peer of Route Views for 2015

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.

Figure 2 – Number of IPv6 Routes announced by each BGP peer of Route Views for 2015

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.

Figure 3 – Proportion of the routing system announcing More Specific Routers, as seen at AS131072

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 4 – Aggregate span of reachable IPv4 addresses announced by each BGP peer of Route Views for 2015

Figure 5 – Aggregate span of reachable IPv6 addresses announced by each BGP peer of Route Views for 2015

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.

Figure 6 – Detail of Aggregate span of reachable IPv6 addresses announced by each BGP peer of Route Views for 2015

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
Peers:			40
Quorum:			25
Announcements:			618,124
Quorum-Announcements:			570,372
Span:			167.48 (/8s)
Quorum Span			166.90 (/8s)
AS	# Objects	Quorum (/8s)	Missing /32s	Additional /32s	AS Name
AS286	570,258	166.89	279,808	416,656	KPN KPN B.V., NL
AS293	581,940	166.79	2,002,432	4,471,122	ESNET – ESnet, US
AS852	571,209	166.59	5,376,256	325,632	TELUS Comms, CA
AS1221	571,660	166.06	14,228,736	199,552	Telstra, AU
AS1239	568,202	166.02	14,801,192	0	SPRINTLINK – Sprint, US
AS1299	563,988	163.38	59,226,624	66,048	TELIANET TeliaSonera AB, SE
AS1668	569,862	166.61	4,953,856	39,168	AOL Transit Data Network, US
AS2152	571,882	166.74	2,842,112	1,123,584	CSUNET-NW, US
AS2497	577,689	166.39	8,639,232	4,958,976	Internet Initiative Japan, JP
AS2914	569,261	166.46	7,479,608	4,992	NTT America, Inc., US
AS3130	570,348	166.89	290,560	9,600	RG-BIWA – RGnet, LLC, US
AS3257	569,221	166.83	1,264,608	54,016	TINET-BACKBONE, DE
AS3277	581,618	166.83	1,194,240	5,018,144	RUSNET-AS NPO RUSnet, RU
AS3303	571,302	166.66	4,088,064	310,784	SWISSCOM, CH
AS3356	566,679	164.14	46,459,904	1,792	Level 3 Communications, US
AS3549	569,244	166.77	2,337,216	72,448	Level 3 Communications, US
AS3561	569,285	166.37	8,959,232	1,536	Savvis, US
AS3741	571,241	166.62	4,758,528	304,640	IS, ZA
AS5413	570,940	166.85	852,480	182,816	Daisy Communications Ltd, GB
AS6539	574,633	166.88	438,784	100,864	GT-BELL – Bell Canada, CA
AS6762	571,435	166.88	478,464	12,032	SEABONE-NET, IT
AS6939	580,094	166.77	2,348,800	3,721,728	Hurricane Electric, US
AS7018	567,633	162.44	74,979,328	45,056	AT&T Services, US
AS7660	556,519	161.39	92,543,856	1,421,960	AsiaPac Advanced Network, JP
AS8492	581,296	166.84	1,122,048	4,744,960	OBIT-AS OBIT Ltd., RU
AS11686	573,309	166.76	2,376,952	1,081,856	Education Networks, US
AS13030	569,627	166.84	1,078,016	2,768,397	INIT7, CH
AS20771	589,700	166.79	1,871,360	4,280,576	Caucasus Online, GE
AS20912	576,857	166.77	2,221,822	2,743,621	Panservice, IT
AS22652	574,852	166.89	241,664	342,272	Fibrenoire, CA
AS23673	584,638	166.48	7,168,256	11,248,384	Cogetel Online, KH
AS37100	574,864	166.66	4,088,576	4,175,104	SEACOM-AS, MU
AS40191	571,528	166.90	40,448	163,200	AS-PRE2POST-1, CA
AS47872	592,253	166.82	1,391,360	4,277,664	SOFIA CONNECT EOOD, BG
AS53364	570,002	166.87	587,264	54,016	AS-PRE2POST-2, US
AS58511	589,579	166.82	1,500,822	6,139,973	Connectivity IT, AU
AS62567	570,671	166.90	104,448	111,104	ASN-NY2 – Digital Ocean, US
AS200130	571,269	166.86	772,096	2,549,760	ASN-1 Digital Ocean, EU
AS202018	570,636	166.90	72,704	103,936	ASN-3 Digital Ocean, NL
AS393406	570,588	166.89	187,648	116,736	NY3 – Digital Ocean, US

Table 1 – Route Views per-peer view of the IPv4 routing table, 17 February 2016

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
Peers:			24
Quorum:			15
Announcements:			28,935
Quorum-Announcements:			26,232
Span:			87,688
Quorum Span			87,468
AS	# Objects	Quorum	Missing /32s	Additional /32s	AS Name
AS33437	26,013	87,194	275	120	HOTNIC – Hotnic LLC, US
AS2914	26,144	87,296	174	2	NTT America, Inc., US
AS47872	27,037	87,466	4	123	SOFIA-CONNECT, BG
AS3277	27,699	87,467	3	170	RUSNET-AS NPO RUSnet, RU
AS1239	25,694	87,155	314	1	SPRINTLINK – Sprint, US
AS30071	23,696	73,520	13,949	4	OCCAID, US
AS20912	26,666	87,466	4	126	Panservice, IT
AS37100	26,199	87,412	58	6	SEACOM-AS, MU
AS31019	26,730	87,459	11	160	MEANIE, NL
AS701	25,989	87,025	445	1	Verizon Business, US
AS200130	26,609	87,467	3	129	Digital Ocean, EU
AS7018	26,127	87,019	451	3	AT&T Services, US
AS202018	26,608	87,467	3	121	Digital Ocean,NL
AS393406	26,608	87,467	3	121	Digital Ocean, US
AS3257	26,006	87,299	171	1	Tinet, DE
AS62567	26,608	87,467	3	121	Digital Ocean,US
AS53364	26,428	87,306	164	1	AS-PRE2POST-2, US
AS22652	27,377	87,412	58	2	FIBRENOIRE-INTERNET, CA
AS40191	27,562	87,466	4	122	AS-PRE2POST-1, CA
AS6939	25,979	86,932	537	120	Hurricane Electric, US
AS3741	26,885	87,434	36	123	IS, ZA
AS2497	26,251	87,463	7	121	Internet initiative Japan, JP
AS13030	26,876	87,394	76	27	Init7, CH
AS209	26,653	86,949	520	120	CENTURYLINK, US

Table 2 – Route Views per-peer view of the IPv6 routing table, 18 February 2016

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.

Figure 7 – Non Quorum IPv4 Address Advertisements per peer for 2015

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.

Figure 8 – Non Quorum IPv4 Address Advertisements per peer for 2015

We can also look at this at the level of detail of a span of a /16, or 65,536 addresses.

Figure 9 – Non Quorum IPv4 Address Advertisements per peer for 2015

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.

Figure 10 – Non Quorum IPv4 Address Advertisements per peer for 2015

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.

Figure 11 – Non Quorum IPv4 Address Advertisements per peer for 2015

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.

Figure 12 – Non Quorum IPv6 Address Advertisements per peer for 2015

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.

Figure 13 – IPv4 Asymmetric Connection Failure Rate

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).

Figure 14 – IPv6 Asymmetric Connection Failure Rate

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)

Figure 15 – Customer/Provider Relationships

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)

Figure 16 – Customer/Provider and Peering Relationships

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!