Understanding Partial Reachability in the Internet Core

We define the Internet core as all active IP addresses that can Bidirectionally Route to more than 50% of the public, Potentially Reachable Internet. We define these key terms next, and expand their motivation and implications later (Subsection 2.2).

Two addresses are Bidirectionally Routable when each can initiate a connection to the other. In our realization we measure connectivity with either ICMP echo-request or with DNS queries and replies, considering alternatives in Subsection 2.2.

The Potentially Reachable Internet is all IP addresses in a graph-theoretic strongly-connected component, with graph edges defined by Bidirectional Routability. This definition means any node in the set can reach any other, either directly or perhaps through one or more hops.

We define the potentially reachable Internet via observation, so it depends only on testable, shared information, and not a central authority such as ICANN. Defining the Potentially Reachable Internet as active addresses also implies that the vast parts of unallocated IPv6 do not change our conclusions.

We use our definition of the Internet core to consider three types of partial reachability, shown in Figure 1. Here long-term and current routability are dotted and solid lines, and white regions show current data-plane reachability. All address blocks but $E$ form the core. Blocks $B$ and $C$ are on peninsulas because they do not route to each other, although data could relay through $A$. Block $X$ has an outage; its routes are temporarily down. Blocks $D$ and $E$ are islands: $D$ usually can route to the core, but not currently. $E$ uses public addresses, but has never announced routes publicly.

Peninsulas occur when portions of the Internet core are reachable from some locations and not others. They can be seen by two VPs disagreeing on reachability.

Detecting peninsulas presents three challenges. Without VPs everywhere, when all VPs are on the same “side” of a peninsula ($A$ and $C$ in Figure 1), their reachability agrees even though VPs may disagree (like $B$). Second, asynchronous observations test reachability at different times: observations in Trinocular spread over 11 minutes, and in Atlas, 5 minutes. Observations at times before and after a network change will disagree, but both are true – a difference due to weak synchronization, and not a peninsula. Third, connectivity problems near the observer (or when an observer is an island) should not reflect on the intended destination.

We identify peninsulas by detecting disagreements in block state by comparing successful VP observations that occur at about the same time. Since probing rounds occur asynchronously, we compare measurements within the measurement system’s window (11 or 5 minutes for Trinocular and Atlas). This approach sees peninsulas lasting longer than one window duration, but may miss briefer ones, or when VPs are not on “both sides”.

Formally, $O_{i,b}$ is the set of observers with valid observations about block $b$ at round $i$. We look for disagreements in $O_{i,b}$, defining $O_{i,b}^{\text{up}}\subset O_{i,b}$ as the set of observers that measure block $b$ as up at round $i$. We detect a peninsula when:

When only one VP reaches a block, we must classify it as a peninsula or an island, as described next.

According Subsubsection 2.3.2, islands occur when the Internet core is partitioned, and the component with fewer than half the active addresses is the island. Typical islands are much smaller.

We can find islands by looking for networks that are only reachable from less than half of the Internet core. However, to classify such networks as an island and not merely a peninsula, we need to show that it is partitioned, which requires global knowledge. In addition, if islands are partitioned from all VPs, we cannot tell an island, with active but disconnected computers, from an outage, where they are off.

For these reasons, we must look for islands that include VPs in their partition. Because we know the VP is active and scanning we can determine how much of the Internet core is in its partition, ruling out an outage. We also can confirm the Internet core is not reachable, to rule out a peninsula.

Formally, we say that $B$ is the set of blocks in the Internet core. $B_{i,o}^{\text{up}}\subseteq B$ are blocks reachable from observer $o$ at round $i$, while $B_{i,o}^{\text{dn}}\subseteq B$ is its complement. We detect that observer $o$ is in an island when it thinks half or more of the observable Internet core is down:

This method is independent of measurement systems, but is limited to detecting islands that contain VPs, so any deployment will certainly undercount islands. We evaluate islands in Trinocular and Atlas (Subsection 5.5), confirming more VPs see more islands, but that nearly all reported islands are correct.

Finally, because observations are not instantaneous, we must avoid confusing short-lived islands with long-lived peninsulas. For islands lasting longer than 11-minutes, we also require $|B_{i,o}^{\text{up}}|\to 0$. With $|B_{i,o}^{\text{up}}|=0$, it is an address island.

We have deployed our algorithms as extensions to two systems: Trinocular and RIPE Atlas. In both cases, each system provides data to us via existing APIs and we then apply Taitao and Chiloe and share results back. Processing time for both is modest, with DNSmon running in minutes and Trinocular taking less time than Trinocular outage detection.

For DNSmon, we provide daily outages and peninsulas since 2022-01-01 on a public website [87]. We have also discussed these results with RIPE and the root operators; RIPE currently identifies islands manually, and one root operator is using our results to guide operations. We provide 3.5 years Trinocular analysis at our website [6], and are working with Trinocular operators to operationalize our algorithms.

We compare Taitao detections from 6 VPs to independent observations taken from more than 100 VPs in CAIDA’s Ark [14]. This comparison is challenging, because both Taitao and Ark are imperfect operational systems that differ in probing frequency, targets, and method. Neither defines perfect ground truth, but agreement suggests likely truth.

We believe this complexity is warranted because Ark provides a more diverse perspective (with 171 locations), if we can account for its much sparser frequency. Ark traceroutes also allow us to assess where peninsulas begin. We expect to see a strong correlation between Taitao peninsulas and Ark observations. (We considered RIPE Atlas as another external dataset, but its coverage is sparse, while Ark covers all /24s.)

Chiloe (Subsection 3.2) detects islands when a VP within the island can reach less than half the rest of the world.

Our evaluation assumes VPs do not share common network paths. VPs improve path diversity by network diversity and physical distance, particularly with today’s “flatter” Internet [59]. We next quantify and validate this assumption.

We measure similarity of observations between pairs of VPs. We examine only cases where one of the pair disagrees with some other VP, since when all agree, we have no new information. If the pair agrees with each other, but not with the majority, the pair shows similarity. If they disagree with each other, they are dissimilar. We quantify similarity $S_P$ for a pair of sites $P$ as $S_P=(P_1+P_0)/(P_1+P_0+D_{\ast })$, where $P_s$ indicates the pair agrees on the network having state $s$ of up (1) or down (0) and disagrees with the others, and for $D_{\ast }$, the pair disagrees with each other. $S_P$ ranges from 1, where the pair always agrees, to 0, where they always disagree.

Table 5 shows similarities for each pair of the 6 Trinocular VPs (as half of the symmetric matrix). No two sites have a similarity more than 0.14, and most pairs are under 0.08. This result shows that no two sites are particularly correlated.

We confirm our results are not time-dependent by repeating key results in multiple years, including operational result from 2022 to 2025 (Figure 7 in Subsection 6.3), and confirm all results with multiple sources and dates (see Appendix F.2 of [9]). We expect these results to apply today since partial reachability has persisted since 2001 [2], with some events lasting years [42], as our results document (Figure 7). We use older data in some examples to avoid limitations of measurement deployments. During 2017q4, Trinocular had six active VPs and Ark had three teams, providing strong statements from many perspectives. Trinocular had fewer VPs in 2019 and early 2020, and Ark has fewer teams today, but 2020 gives quantitatively similar results (see Appendix F.2 of [9]). Subsection 5.4 uses 2020q3 data because Ark observed a very large number of loops in 2017q4.

Our algorithms are influenced by the parameters in our data sources, including how often and where they probe, where they are placed, and how many VPs they employ, and how much data we analyze. We vary all of these parameters across our datasets (see Table 1), but the requirement for Internet-wide data spanning months and years means we depend on existing deployed infrastructure. Systematically varying VP frequency and location is challenging future work.

We believe these diverse data sources confirm our results apply over a range of geographic locations. We study locations quantitatively in Subsection 4.3) and confirm stable results with Atlas across 3k ASes and 12k locations in Subsection 6.3. Thus, while we certainly greatly undercount the absolute numbers of peninsulas and islands observed from Trinocular’s 6 locations (Section 5), Atlas confirms these trends apply with 12k VPs.

We estimate how often peninsulas occur in the Internet core in three ways. First, we directly measure the visibility of peninsulas by summing the duration of peninsulas as seen from six VPs. Second, we confirm the accuracy of this estimate by evaluating its convergence as we vary the number of VPs – more VPs show more peninsula-time, but a result that converges suggests it is approaching the limit. Third, we compare peninsula-time to outage-time, showing that, in the limit, observers see both for about the same duration. Outages correspond to service downtime [100], and are a recognized problem in academia and industry. Our results show that peninsulas are as common as outages, suggesting peninsulas are an important new problem deserving attention.

Peninsulas have multiple root causes: some are short-lived routing misconfigurations while others reflect long-term disagreements in routing policy. In this section we determine the distribution of peninsulas in terms of their duration to determine the prevalence of persistent peninsulas. We will show that there are millions of brief peninsulas, likely due to transient routing problems, but that 90% of peninsula-time is in long-lived events (5 h or more, following Subsection 4.1).

We use Taitao to see peninsula duration for all detected in 2017q4: some 23.6M peninsulas affecting 3.8M unique blocks. If instead we look at long-lived peninsulas (at least 5 h), we see 4.5M peninsulas in 338k unique blocks.

Figure 4 examines peninsula duration in three ways: a cumulative distribution (CDF) counting all peninsula events (left, solid, purple line), the CDF of the number of peninsulas for VP-down events longer than 5 hours (middle, solid green line), and the cumulative size of peninsulas for VP down events longer than 5 hours (right, green dashes).

We see that there are many very brief peninsulas (purple line): about 65% last only 20–60 minutes ($\sim$2–6 observations). With two or more observations, these events are not just one-off measurement loss. These results suggest that while the Internet core is robust, there are many small connectivity glitches (7.8M events). Events that are two rounds (20 minutes) or shorter may be due to transient BGP blackholes [12].

The number of day-long or multi-day peninsulas is small, only 1.7M events (2%, the purple line). However, about 57% of all peninsula-time is in such longer-lived events (the right, dashed line), and 20% of time is in events lasting 10 days or more, even when longer than 5 hours events are less numerous (compare the middle, green line to the left, purple line). Day-long events persist long enough for human network operators to respond, and events lasting longer than a week suggest potential policy disputes and intentional unreachability. Together, these long-lived events suggest that there is benefit to identifying non-transient peninsulas and addressing the underlying routing problem.

When network issues cause connectivity problems like peninsulas, the size of those problems may vary, from country-size(see Appendix G.2 in [9]), to AS-size, and also for routable prefixes or fractions of prefixes. We next examine peninsula sizes.

We begin with Taitao peninsula detection at a /24 block level. We match peninsulas across blocks within the same prefix by start time and duration, both measured in one hour timebins. This match implies that the Trinocular VPs observing the blocks as up are also the same.

We compare peninsulas to routable prefixes from Routeviews [65], using longest prefix matches with /24 blocks.

Routable prefixes consist of many blocks, some of which may not be measurable. We therefore define the peninsula-prefix fraction for each routed prefix as fraction of blocks in the peninsula that are Trinocular-measurable blocks. To reduce noise provided by single block peninsulas, we only consider peninsulas covering 2 or more blocks in a prefix.

3(a) shows the number of peninsulas for different prefix lengths and the fraction of the prefix affected by the peninsula as a heat-map, where we group them into bins.

We see that about 10% of peninsulas are likely due to routing problems or policies, since 40k peninsulas affect the whole routable prefix. However, a third of peninsulas (101k, at the bottom of the plot) affect only a very small fraction of the prefix. These low prefix-fraction peninsulas suggest that they happen inside an ISP and are not due to interdomain routing.

Finally, we show that long-lived peninsulas are likely due to routing or policy choices. 3(b) shows the same data source, but weighted by fraction of time each peninsula contributes to the total peninsula time during 2017q4. Here the larger fraction of weight are peninsulas covering full routable prefixes – 20% of all peninsula time during the quarter (see left margin).

Firewalls, link failures, and routing problems cause peninsulas on the Internet, and can occur at AS boundaries or inside an AS. We next show that many peninsulas occur at AS boundaries, consistent with policies as a cause for long-lived events. (Short-lived events at AS boundaries may be routing transients or operator error that is quickly corrected.)

To detect where the Internet breaks into peninsulas, we look at traceroutes that failed to reach their target address, either due to a loop or an ICMP unreachable message. Then, we examine if the traceroute halts at the target AS and target prefix, or before the target AS and prefix.

For our experiment we run Taitao to detect peninsulas at target blocks over Trinocular VPs, we use Ark’s traceroutes [15] to find last IP address before halt, and we get target and halting ASNs and prefixes using RouteViews.

In Table 7 we show how many traces halt at or before the target network. The center, gray rows show peninsulas (disagreement between VPs) with their total sum in bold. For all peninsulas (the bold row), more traceroutes halt at or inside the target AS (235k vs. 134k, the left columns), but they more often terminate before reaching the target prefix (308k vs. 61k, the right columns). (While traceroutes are imperfect, these large differences ($2\times$ or more) suggest a robust qualitative conclusion.) This difference suggests policy is implemented at or inside ASes, but not at routable prefixes. By contrast, outages (agreement with 0 sites up) more often terminate before reaching the target AS. Because peninsulas are more often at or in an AS, while outages occur in many places, it suggests that long-lived peninsulas are policy choices consistent with public operator reports [67, 62, 3, 76, 93, 17].

Multiple groups have shown that there are many network outages in the Internet [89, 75, 90, 80, 49]. We have described (Section 2) two kinds of outages: full outages where all computers at a site are down (perhaps due to a loss of power), and islands, where the site is cut off from the Internet core, but computers at the site can talk between themselves. We next use Chiloe to determine how often islands occur. We study islands in two systems with 6 VPs for 3 years and 13k VPs for 3 months.

Islands causes range from brief connectivity loss to long-term policy differences, so we next evaluate island duration.

We compare the distributions of island durations observed from RIPE Atlas (the left line) and Trinocular (right) in 5(b). Since Atlas’ frequent polling means it detects islands lasting seconds, while Trinocular sees only islands of 660 s or longer, we split out Atlas events lasting at least 660 s (middle line). All measurements follow a similar S-shaped curve, but for Trinocular, the curve is truncated at 660 s. With only 6 VPs, Trinocular sees far fewer events (23 in 3 years compared to 235k in a yearly quarter with Atlas), so the Trinocular data is quantized. In both cases, about 70% of islands are between 1000 and 6000 s. This graph shows that Trinocular’s curve is similar in shape to Atlas-660 s, but about $2\times$ longer. All Trinocular observers are in datacenters, while Atlas devices are often at homes, so this difference may indicate that datacenter islands are rarer, but harder to resolve.

In Subsection 6.2 we discussed secession and expulsion qualitatively. Here we ask: Does any country or group have enough addresses to secede and claim to be “the Internet core” with a majority of addresses? Alternatively, if a country were to exert control over their allocated addresses, would they become a country-sized island or peninsula? We next use our reachability definition of more than 50% to quantify control of the IP address space.

To evaluate the power of countries and Regional Internet Registries over the Internet core, Table 6 reports the number of active IPv4 addresses as determined by Internet censuses [51] for RIRs and selected countries. Since estimating active IPv6 addresses is an open problem, we provide allocated addresses for both v4 and v6 [53, 54]. (IPv4 has been fully allocated since 2011 [55]).

Table 6 shows that no individual RIR or country can secede and take the Internet core, because none controls the majority of IPv4 addresses. ARIN has the largest share with 1673M allocated (45.2%). Of countries, U.S. has the largest share of allocated IPv4 (1617M, 43.7%). Active addresses are more evenly distributed with APNIC (223M, 33%) and the U.S. (40M, 21%) the largest RIR and country.

IPv6 is also an international collaboration, since no RIR or country surpasses a 50% allocation for control. RIPE (an RIR) is close with 46.7%, and China and the U.S. have large allocations; with most v6 unallocated, this balance may change.

IPv4 reflects a first-mover bias, where early adopters acquired many addresses, but this factor is smaller in IPv6. Our definition’s use of active addresses also reduces this bias, since numbers of active IPv4 addresses is similar to allocated IPv6 addresses (legacy IPv4 addresses are less used).

We next examine how a clear definition of the Internet core can inform policy tussles [21]. Our hope is that our conceptual definition can make sometimes amorphous concepts like “Internet fragmentation” more concrete, and an operational definition can quantify impacts and identify thresholds.

DNSmon [1] monitors the Root Server System [84], with each RIPE Atlas VP measuring its anycast-determined neighbor [82]. For years, DNSmon has often reported IPv6 loss rates of 4-10%. Since the DNS root is well provisioned and anycast, we expect minimal or no loss.

RIPE Atlas operators are aware of problems with some Atlas VPs. Some VPs support IPv6 on their LAN, but not to the global IPv6 Internet – such VPs are IPv6 islands. Atlas periodically tags and culls these VPs from DNSmon. However, our study of DNSmon for islands and peninsulas improves their results. Using concepts pioneered here (Section 2 and Section 3), we give full analysis in a workshop paper [86]; Here we add new data showing these results persist for 3 years (Figure 7).

Groups of bars in Figure 7 show query loss for each of the 13 root service identifiers, as observed from all available Atlas VPs (10,082 IPv4, and 5,173 IPv6) on 2022-07-23. (We are similar to DNSmon, but it uses only about 100 well-connected “anchors”, so our analysis is wider.) The first two groups show loss rates for IPv4 (light blue, left most) and IPv6 (light red), showing IPv4 losses around 2%, and IPv6 from 9 to 13%.

We apply Chiloe to these VPs, detecting as islands those VPs that cannot see any of the 13 root identifiers over 24 hours. (This definition is stricter than regular Chiloe because these VPs attempt only 13 targets, and we apply it over a full day to consider only long-term trends.) The middle two groups of bars show IPv4 and IPv6 loss rates after removing 188 v4 and 388 v6 VPs that are islands. Without islands, v4 loss drops to 0.005 from 0.01, and v6 to 0.01 from 0.06. These rates represent a more meaningful estimate of DNS reliability. Users of VPs that are IPv6 islands will not expect global IPv6, and such VPs should not be used for IPv6 in DNSmon.

The third bar in each red cluster of IPv6 is an outlier: that root identifier shows 13% IPv6 loss with all VPs, and 6% loss after islands are removed. This result is explained by persistent routing disputes between Cogent (the operator of C-Root) and Hurricane Electric [67]. Omitting islands (the middle bars) makes this difference much clearer.

Applying Taitao to detect peninsulas, we find 14 to 57 v4 peninsulas and 266 (Cogent) and 19 to 49 (others) v6 peninsulas. Peninsulas suggest persistent routing problems meriting attention from ISPs and root operators. The darker, right two groups show loss remaining (after removal of islands and peninsulas), representing underlying events worth root operator attention. These bars show all letters see similar events rates, after we remove persistent problems.

This example shows how understanding partial reachability can improve the sensitivity of existing measurement systems. Removing islands makes it easy to identify persistent routing problems. Removing peninsulas makes transient changes (perhaps from failure, DDoS, routing) more visible. Each layer of these problems can be interesting, but considering each separately, the interesting “signal” of routing changes (appearing in the right two groups in Figure 7), is hidden under the $5\times$ or $9.7\times$ times larger peninsulas and islands (the left two groups). Improved sensitivity also shows a need to improve IPv6 provisioning, since IPv6 loss is statistically higher than IPv4 loss (compare the right blue and red groups), even accounting for known problems. After sharing the results with root operators and RIPE Atlas, two operators adopted them in regular operation.

We next re-evaluate reports from existing outage detection systems, considering how to resolve conflicting information in light of our new algorithms. We compare findings to external information in traceroutes from CAIDA Ark.

Figure 8 compares Trinocular with 21 days of Ark topology data, from 2017-10-10 to -31 from all 3 probing teams. For each Trinocular outage we classify the Ark result as success or three types of failure: unreachable, loop, or gap.

Trinocular’s 6-site-up case suggests a working network, and we consider this case as typical. However, we see that about 25% of Ark traceroutes are “gap”, where several hops fail to reply. We also see about 2% of traceroutes are unreachable (after we discard traceroutes to never reachable addresses). Ark probes a random address in each block; many addresses are non-responsive, explaining these.

With 1 to 11 sites up, Trinocular is reporting disagreement. We see that the number of Ark success cases (the green, lower portion of each bar) falls roughly linearly with the number of successful observers. This consistency suggests that Trinocular and Ark are seeing similar behavior, and that there is partial reachability – these events with only partial Trinocular positive results are peninsulas.

Since 5 sites give the same results as all 6, single-VP failures likely represent problems local to that VP. This data suggests that all-but-one voting will track true outages.

With only partial reachability, with 1 to 4 VPs (of 6), we see likely peninsulas. These cases confirm that partial connectivity is common: while there are 1M traceroutes sent to outages where no VP can see the target (the number of events is shown on the 0 bar), there are 1.6M traceroutes sent to partial outages (bars 1 to 5), and 850k traceroutes sent to definite peninsulas (bars 1 to 4). This result is consistent with the convergence we see in Figure 2.