Overview

Business relationships between Autonomous Systems (ASes) are typically confidential, so they must be inferred from data that is publicly available. This page explains, step by step, the algorithm CAIDA uses to infer those relationships from public BGP paths, and how the inferred relationships are then used to compute each AS's customer cone and rank. This page focuses on the algorithm itself; for background on what relationships, degrees, and customer cones are, see the about page or the paper AS Relationships, Customer Cones, and Validation .

The algorithm classifies each observed link between two ASes as one of two relationship types:

• customer-to-provider (c2p / p2c): the customer obtains transit from the provider to reach the rest of the Internet, and
• peer-to-peer (p2p): the two ASes exchange traffic between themselves and their customers, typically settlement-free.

The algorithm rests on three assumptions about the structure of the Internet:

1. An AS enters into a provider relationship to become globally reachable. A provider announces its customers' routes to its own providers and peers, so at least one vantage point should observe a provider announcing its customer's routes.
2. There exists a clique of large transit providers at the top of the hierarchy. These ASes peer with each other in a full mesh so that their customers (and their customers' customers) obtain global connectivity.

The full pipeline runs in the following stages, each explained in a section below:

1. Collect BGP paths and clean them of loops, poisoned paths, unassigned ASes, and IXP route servers.
2. Sort ASes into the top-down order in which their relationships will be inferred, with the clique at the top.
3. Infer relationships in eight steps: the clique's peering mesh first, then c2p links from strongest to weakest evidence, and finally p2p for every link that remains.
4. Compute each AS's customer cone from the inferred relationships and the observed paths.
5. Rank ASes by the size of their customer cones.

Input Data and Path Cleaning

The input to the algorithm is the set of AS paths extracted from BGP routing table snapshots collected by the Route Views project and RIPE's Routing Information Service (RIS). Each BGP peer that supplies routes to a collector is a vantage point (VP): it shows an AS-level view of the Internet from that peer's perspective, and it appears as the first AS on the left of every path it supplies. Paths containing AS-sets are discarded, and path padding is compressed (a path "A B B C" becomes "A B C").

Raw BGP paths contain artifacts that would corrupt relationship inference, so paths are first cleaned:

• Loops: paths where an AS appears more than once, separated by at least one other AS, are discarded. Such loops indicate path poisoning, where an AS inserts another AS into a path to prevent that AS from selecting the route. A poisoned path implies a link between two ASes where in reality none may exist.
  Example: 64496 3356 64497 3356 — AS3356 appears twice, separated by AS64497, so the path is discarded.
• Separated clique ASes: paths where two clique ASes are separated by a non-clique AS are discarded. A clique AS is by definition transit-free, so this condition also indicates poisoning.
  Example: 64496 3356 64497 1239 — 3356 and 1239 are both clique ASes, but a non-clique AS64497 sits between them, so the path is discarded.
• Unassigned ASes: paths containing AS numbers not assigned by IANA to any organization are discarded, since these ASes should not be routed on the Internet.
  Example: 64496 23456 1239 — AS23456 is a reserved, special-purpose ASN (used to let old routers that only understand 2-byte ASNs interoperate with 4-byte ASNs) and should never appear in a real path, so it is discarded.
• IXP route servers: ASes operated by Internet Exchange Point route servers are removed from paths, so that the exchange's participants — who hold the actual relationship — appear adjacent in the path.
  Example: 64496 64500 1239 becomes 64496 1239 — AS64500 is an IXP route server, so it is removed and the two exchange participants become adjacent.

After cleaning, the algorithm computes each AS's node degree and transit degree, and sorts all ASes into the order in which their relationships will be inferred: clique ASes first, then all other ASes by decreasing transit degree, breaking ties by node degree and then by AS number. Sorting by transit degree rather than node degree avoids mistaking high-degree ASes that provide no transit (for example, content providers with many peers) for transit providers. This top-down order matters: c2p relationships are inferred along the degree gradient, which is also what prevents cycles of c2p links from forming.

The Clique

The clique is the set of large transit providers at the top of the hierarchy. Clique ASes are transit-free: they have no providers, and instead maintain a full mesh of settlement-free peering with each other, which gives their customers global reachability. The clique anchors the whole inference: its members are placed at the top of the top-down order, its internal links are the first relationships assigned (Step 1), and paths crossing the clique provide the initial evidence from which c2p relationships propagate downward.

The algorithm uses the following set of settlement-free peers as the clique:

174, 209, 286, 701, 1239, 1299, 2828, 2914, 3257, 3320, 3356, 3491, 5511, 6453, 6461, 6762, 6830, 7018, 12956

Inferring Relationships: Steps 1–8

With clean paths, degrees, and the clique in hand, the algorithm infers a relationship for every observed link in eight steps. Steps 2 through 7 infer c2p links, ordered from the strongest evidence to the weakest; Step 8 classifies everything that remains as p2p. These are the same step numbers used in the per-link inference reports elsewhere on this site.

AS path triplets. Most steps make inferences using AS path triplets: three consecutive ASes in a path, i.e. an adjacent pair of links. Triplets provide the constraints needed to infer c2p relationships while allowing the algorithm to ignore non-hierarchical segments elsewhere in a path. For example, the path "1239 3356 9002 6846" contains two triplets: "1239 3356 9002" and "3356 9002 6846". A triplet "X Y Z" is read from the vantage point outward: the route was announced by Z to Y, and by Y onward to X. In other words, Y is forwarding Z's routes to X — and since an AS only announces its customers' routes to its providers and peers, seeing Y announce Z's routes to a known provider or peer of Y is evidence that Z is a customer of Y. This observation is the engine of the whole algorithm.

Notation. In the tables and text below, "X → Y" means X is inferred to be a provider of Y (a p2c link), and "X – Y" means X and Y are inferred to be peers (a p2p link).

Preventing cycles. Whenever a c2p relationship is inferred, the customer is recorded in the customer cone of the provider and of all the provider's upstream providers. The algorithm never infers a c2p relationship where the would-be provider is already in the would-be customer's cone, so no cycle of c2p links can form.

Step 1: Set peering in clique

Every pair of ASes in the clique is assigned a p2p relationship — a full mesh of settlement-free peering. This follows directly from the second assumption: clique members are transit-free and obtain connectivity to each other by peering. No paths are used by this step; it simply encodes the clique.

Step 2: Initial provider assignment

This is responsible for roughly 90% of all c2p inferences. ASes are visited in the top-down order established earlier, skipping clique ASes (which have no providers). When visiting AS Z, the algorithm examines each of Z's neighbors Y and infers Y → Z if it observes a triplet "X Y Z" where X is already known to be a provider or peer of Y. The reasoning: Y announced Z's routes upward to its provider or peer X, and an AS only announces customer routes upward, so Z must be Y's customer. Peer evidence that is not corroborated by upstream announcements is only trusted when observed repeatedly (more than twice).

The order of ASes within the triplet matters. To minimize false c2p inferences caused by route leaks (an AS mistakenly announcing provider or peer routes to a peer), the provider or peer must be observed closer to a vantage point than the customer in at least one triplet. This builds on the first assumption: an AS enters a provider relationship to become globally reachable, so at least one VP should see the provider announcing the customer's routes.

Because Z's inferred providers all have a larger transit degree than Z (they were visited earlier in the top-down order), c2p links are assigned along the degree gradient and no c2p cycle can form.

Step 3: Providers for stub ASes

Some vantage points supply routes to only a small fraction of the Internet. The algorithm treats VPs that provide routes to fewer than 2% of all ASes as partial VPs: they have either configured their BGP session with the collector as p2p (exporting only customer routes), or configured it as p2c while holding a default route to their provider. Either way, the routes they export are customer routes.

For each path of exactly three ASes "VP Y Z" supplied by a partial VP, where Z is a stub (an AS with transit degree zero) and the Y–Z link is still unresolved, the algorithm infers Y → Z. The link between the VP and Y may be either p2c or p2p, but in both cases Y would only announce Z's routes to the VP if Z were Y's customer.

Step 4: Provider to larger customer

Step 2 infers providers along the transit-degree gradient, so it misses c2p relationships where the provider has a smaller transit degree than its customer. These do occur — for example, a large content network obtaining transit from a small regional provider. Given an AS Y with a known provider X, and a neighbor Z of Y whose transit degree is at least as large as Y's, the algorithm infers Y → Z when both:

• a triplet "X Y Z" is observed (Y announces Z's routes to its provider X), and
• at least one path ends with "X Y Z", i.e. Z originates a prefix that is announced through Y to X.

The second condition guards against path poisoning: poisoned path segments do not announce address space, so requiring Z to originate a prefix ensures the link is real. Because inferences against the degree gradient carry more risk, the evidence must be observed at least three times. After inferring Y → Z, the inference cascades: neighbors of Z observed downstream of "Y Z" become customers of Z under the same logic.

Step 5: Provider-less networks

Steps 2 and 4 both require an AS to already have a provider or peer before its customers can be identified. Some ASes have no providers at all yet are not in the clique — typically large regional or research networks. The algorithm visits each AS X that still has no inferred provider, is not in the clique, and has a transit degree of at least 10, and examines triplets "W X Y" with X in the middle:

• W – X: W is inferred to be a peer of X, because in all the earlier steps W was never observed announcing X's routes to a provider or peer — if W were X's provider, it would have been.
• X → Y: X announces Y's routes to W, so Y is X's customer. As in step 4, the inference cascades to neighbors of Y observed further downstream.

Unlike step 2, this step does not require the peer to be observed closest to a VP, because provider-less ASes are mostly observed through downstream customers that provide a public BGP view.

Step 6: C2P for stub-clique relationships

If a link is observed between a stub AS (transit degree zero) and a clique AS and no relationship has been inferred for it, the clique AS is inferred to be the provider of the stub. Step 2 could only have classified this link if a route crossing it had been observed by another clique AS, which does not always happen — for example, when the link is a backup transit relationship. Stub networks are extremely unlikely to meet the peering requirements of clique members, so a customer relationship is by far the most likely explanation. No triplet is used; the inference is purely topological.

Step 7: Fold p2p links

At this point some triplets "X ? Y ? Z" remain in which neither link has a relationship. If both were left to become p2p in step 8, the result would be two adjacent p2p links — which implies anomalous behavior such as free transit or route leakage, since an AS does not announce routes learned from one peer to another peer. To avoid this, ASes are traversed top-down one final time, and for each unresolved triplet "X ? Y ? Z" the algorithm attempts to resolve one side as p2c, inferring Y → Z (with X – Y then following in step 8). If other triplets involving X and Y suggest a conflicting orientation (evidence that Y is instead X's provider, or that X is Y's customer via some other neighbor), the algorithm is no longer confident which side of the triplet is the p2c link and makes no inference, leaving both links to step 8.

Step 8: Everything else is p2p

Every link that still has no inferred relationship is classified as p2p. No triggering pattern is required — these are simply the links for which steps 1–7 found no evidence of a transit relationship.

Worked Example

The following example, adapted from our IMC 2013 paper, traces the algorithm over a small set of BGP paths. Four of the ASes involved (3356, 701, 6461, and 1239) are clique members. Three ASes provide the vantage points: 1239, 9002, and 15169; each appears as the leftmost AS of the paths it supplies. AS 15169 supplies routes to only a small fraction of ASes, so it is treated as a partial VP.

The ASes are sorted top-down: the clique members first, then the rest by decreasing transit degree:

3356, 701, 6461, 1239,  9002, 15169, 11164, 2152, 27065, 6846, 721, 7377, 6432, 2629, 13395, 36040

The algorithm then makes the following inferences. Recall that "X → Y" means X is inferred to be a provider of Y, and "X – Y" means X and Y are inferred to be peers.

Computing Customer Cones

With every link classified, the algorithm computes each AS's customer cone: the set of ASes it can reach by following only p2c (customer) links. This sounds simple, but there is more than one way to compute it, and the choice matters:

• Recursive: follow p2c links transitively through the graph — A's cone contains A's customers, their customers, and so on. This over-counts, because it assumes a provider receives (and can reach) all of its customers' routes. In reality a customer may announce only some prefixes to a given provider, so the provider cannot necessarily reach everything below that customer.
• BGP observed: include C in A's cone only if some observed BGP path actually reaches C from A by a sequence of p2c links. This avoids the over-counting, but inflates the cones of ASes that host a vantage point, since far more paths are observed from them than from other ASes.
• Provider/peer observed: compute A's cone using only the routes observed from A's providers and peers. Since an AS announces only its customers' routes to its providers and peers, anything they are observed reaching through A must be in A's customer cone. This method avoids both problems above, and it is the method used to compute the customer cones on this site.

The provider/peer observed method can underestimate a cone, because public BGP data contains only the best path selected by each AS rather than all paths. We accept this limitation because the alternative methods systematically inflate cones, and inflated cones distort the comparison between ASes that host vantage points and the vast majority that do not.

Computing Rank

Finally, ASes are ranked by the size of their customer cones: an AS's rank is one greater than the number of ASes with larger customer cones, so ASes with equally large cones share the same rank. See the about page for a worked example of the ranking rule.

Learn More

• The about page provides background on AS relationships, degrees, and customer cones.
• The algorithm, its validation (99.6% of c2p and 98.7% of p2p inferences confirmed correct against ground truth), and the customer cone analysis are described in full detail in our IMC 2013 paper: M. Luckie, B. Huffaker, k. claffy, A. Dhamdhere, and V. Giotsas, "AS Relationships, Customer Cones, and Validation".
• The inferred relationships are published monthly in CAIDA's AS Relationships dataset.