Identifying rewriters in longer AS_PATHs

Based on these initial results, we extended our methodology to process longer paths and infer the behavior of more ASes. Briefly, our algorithm works as follows: We seed our trusted set (T) with AS13335. T holds all the ASes that preserve the ORIGIN. For each AS_PATH:Filter out all ASes in T. If only one AS remains, we can attribute the ORIGIN to that AS.

We record the mapping AS → ORIGIN(s). For each pair AS → ORIGIN(s):If ORIGIN(s) == original value, we add AS to T. Else, we add AS to M(odifiers). If T was updated in 3, repeat the procedure from 2. Applied to the routes of our IPv4 and IPv6 prefixes originated with EGP and INCOMPLETE, this methodology increases our AS attribution to 606 out of 802 (75.

6%) visible ASes in the AS_PATHs, out of which 64 (10. 6%) are changing the ORIGIN to IGP. Motivated by the Tier-1s adopting this technique, we studied the significance of the attributed ASes using CAIDA’s AS Rank. AS Rank provides a ranking of the ASes based on their customer cone (i. e.

, themselves and all the ASes that can be reached through provider-customer links). In the figure below, we show the cumulative distribution (CDF) of AS Ranks of the attributed ASes. An interesting observation is that the IGP-rewriting ASes are highly concentrated at the top of the AS hierarchy, with 20. 3% of the rewriting ASes falling in the top-50 of AS Rank.