Measuring the Autonomous System Path Through the Internet

Measuring the Autonomous System Path Through the Internet Jennifer Rexford Internet and Networking Systems AT&T Labs - Research; Florham Park, NJ http://www.research.att.com/ jrex Joint work with Z. Morley Mao, David Johnson, Jia Wang, and Randy Katz

IP Forwarding Path Path packets traverse through the Internet Internet IP traffic source destination Why important? Characterize end-to-end network paths Discover the router-level Internet topology

Traceroute: Measuring the Forwarding Path Time-To-Live field in IP packet header – Source sends a packet with a TTL of n – Each router along the path decrements the TTL – “TTL exceeded” sent when TTL reaches 0 Traceroute TTL 1 source TTL 2 tool exploits this TTL behavior Time exceeded destination Send packets with TTL 1, 2, 3, and record source of “time exceeded” message

Example Traceroute Output (Berkeley to CNN) Hop number, IP address, DNS name 1 169.229.62.1 inr-daedalus-0.CS.Berkeley.EDU 2 169.229.59.225soda-cr-1-1-soda-br-6-2 3 128.32.255.169vlan242.inr-202-doecev.Berkeley.EDU No response from router 4 128.32.0.249 gigE6-0-0.inr-666-doecev.Berkeley.EDU 5 128.32.0.66 qsv-juniper--ucb-gw.calren2.net 6 209.247.159.109 POS1-0.hsipaccess1.SanJose1.Level3.net 7 * ? 8 64.159.1.46 ? No name resolution 9 209.247.9.170 pos8-0.hsa2.Atlanta2.Level3.net 10 66.185.138.33 pop2-atm-P0-2.atdn.net 11 * ? 12 66.185.136.17 pop1-atl-P4-0.atdn.net 13 64.236.16.52 www4.cnn.com

Autonomous System Forwarding Path Example: Pinpoint forwarding loop & responsible AS Internet IP traffic AS B source AS C destination AS A AS D Autonomous System (AS)

Border Gateway Protocol (BGP) Signaling path: control traffic Origin AS d: path [BC] AS A d: path [C] AS B Forwarding path: data traffic AS C prefix d BGP path may differ from forwarding AS path – Routing loops and deflections – Route aggregation and filtering – BGP misconfiguration

Map Traceroute Hops to ASes Traceroute output: (hop number, IP) 1 169.229.62.1 AS25 2 169.229.59.225 AS25 Berkeley 3 128.32.255.169 AS25 4 128.32.0.249 AS25 AS1142 Calren 3 209.247.159.109 AS3356 * Level3 AS3356 64.159.1.46 AS3356 209.247.9.170 AS3356 66.185.138.33 AS1668 AOL * AS1668 66.185.136.17 AS1668 CNN 64.236.16.52 AS5662 5 128.32.0.66 6 7 8 9 10 11 12 13 Need accurate IP-to-AS mappings (for network equipment).

Candidate Ways to Get IP-to-AS Mapping Routing address registry – Voluntary public registry such as whois.radb.net – Used by prtraceroute and “NANOG traceroute” – Incomplete and quite out-of-date » Mergers, acquisitions, delegation to customers Origin AS in BGP paths – Public BGP routing tables such as RouteViews – Used to translate traceroute data to an AS graph – Incomplete and inaccurate but usually right » Multiple Origin ASes (MOAS), no mapping, wrong mapping

Refining Initial IP-to-AS Mapping Start with initial IP-to-AS mapping – Mapping from BGP tables is usually correct – Good starting point for computing the mapping Collect many BGP and traceroute paths – Signaling and forwarding AS path usually match – Good way to identify mistakes in IP-to-AS map Successively refine the IP-to-AS mapping – Find add/change/delete that makes big difference – Base these “edits” on operational realities

Extra AS due to Internet eXchange Points IXP: shared place where providers meet – E.g., Mae-East, Mae-West, PAIX – Large number of fan-in and fan-out ASes A B C D E A E F B F G C G Traceroute AS path BGP AS path Physical topology and BGP session graph do not always matc

Extra AS due to Sibling ASes Sibling: organizations with multiple ASes: – E.g., Sprint AS 1239 and AS 1791 – AS numbers equipment with addresses of another A B C H D E A F B G C Traceroute AS path E D F G BGP AS path Sibling ASes “belong together” as if they were one AS.

Weird Paths Due to Unannounced Addresses 12.0.0.0/8 A B C does not announce part of its address space in BGP (e.g., 12.1.2.0/24) ACAC C AC BAC BC Fix the IP-to-AS map to associate 12.1.2.0/24 with C

Reasons BGP and Traceroute Paths May Differ IP-to-AS mapping is inaccurate (fix these!) – Internet eXchange Points (IXPs) – Sibling ASes owned by the same institution – Unannounced infrastructure addresses Forwarding and signaling paths differ (study these!) – Forwarding loops and deflections – Route aggregation and filtering Traceroute inaccuracies (don’t overreact to these!) – Forwarding path changing during measurement – Address assignment to border links between ASes – Outgoing link identified in “time exceeded” message

Optimization Framework Start with initial IP-to-AS map A(x) – IP address x maps to A(x), a set of ASes Iterative refinement – Apply A(x) to the hops in each traceroute path – Compare the traceroute hops to the BGP AS path – Compute mismatch statistics for each entry x – Modify A(x) depending on a small set of rules Terminate when no further modifications

Matching Function and Unavoidable Error Matching function m for BGP/traceroute pair – Traceroute path: t1, t2, , tn of n IP addresses – BGP path: b1, b2, , bl of l AS numbers – Matching: associate IP hop ti with AS hop bm(i) Find t: 7 13 b: A 6 5 8 B 3 10 2 C the matching m that minimizes error – Number of traceroute hops with bm(i) not in A(ti) – Dynamic programming algorithm to find best m

Rules for Modifying the IP-to-AS Mapping Computing match statistics across paths – Focusing on path pairs with at most two errors Example rules – Create a mapping: A(x) is null » Assign to the AS y that appears in the most matchings – Replace a mapping: A(x) has one entry » If an AS y not in A(x) accounts for 55% of matchings – Delete from a mapping: A(x) has multiple entries » If an AS y in A(x) accounts for 10% of matchings Algorithm converges in less than ten iterations

Measurement Data: Eight Vantage Points Sweep the routable IP address space – 200,000 IP addresses – 160,000 prefixes – 15,000 destination ASes Organization Location Upstream Provider AT&T Research NJ, US UUNET, AT&T UC Berkeley CA, US Qwest, Level3, Internet 2 PSG home network WA, US Sprint, Verio Univ of Washington WA, US Verio, Cable&Wireless ArosNet UT, US UUNET Nortel ON, Canada AT&T Canada Vineyard.NET MA, US UUNET, Sprint, Level3 Peak Web Hosting CA, US Level 3, Global Crossing, Teleglobe

Initial Analysis of BGP and Traceroute Paths Traceroute paths: initial mapping A from BGP – Unmapped hops: match no ASes (1-3% of paths) – MOAS hops: match any AS in the set (10-13% of paths) – “*” hops: match any AS (7-9% of paths) BGP paths: discard 1% of prefixes with AS paths – Routing changes based on BGP updates – Private AS numbers (e.g., 65100) – Empty AS paths (local destinations) – Apparent AS-level loops from misconfiguration – AS SET instead of AS sequence

Comparison of IP-to-AS Mappings Comparing BGP and Traceroute AS paths for various IP-to-AS mappings Whois Match Mismatch Ratio 47% 53% 0.88 BGP origins 85% 15% 5.8 Refined mapping 95% 5% 18 Whois: unmapped hops cause half of mismatches BGP tables: mostly match, as our algorithm assumes Refined mapping: change 2.9% of original mapping – Robust to reducing # of probes and introducing noise

Validating the Changes to the Mapping AT&T’s tier-1 network (AS 7018) – Dump of configuration state from each of the routers – Explains 45 of 54 changes involving AS 7018 » E.g., customer numbered from AT&T addresses » E.g., Internet exchange point where AT&T connects Whois query on prefix or AS – Look for “exchange point” or “Internet exchange” » Explains 24 of the changes to the mappings – Look for ASes with similar names (Sprintlink vs. Sprintlink3) » Explains many of the changes to the mappings List of known Internet eXchange Points – Explains 24 of the MOAS inferences – Total of 38 IXPs contributed to mapping changes

Exploring the Remaining Mismatches Route aggregation B C C D D E BGP path: B C Traceroute path: B C D E – Traceroute AS path longer in 20% of mismatches – Different paths for destinations in same prefix Interface B numbering at AS boundaries B C D D BGP path: B C D Traceroute path: B D – Boundary links numbered from one AS – Verified cases where AT&T (AS 7018) is involved

Contributions Problem formulation – AS-level traceroute tool for troubleshooting – Compute an accurate IP-to-AS mapping Optimization approach Measurement methodology – Compute matchings using dynamic programming – Improve mapping through iterative refinement – Traceroute and BGP paths from many locations Validation of our results – Changes to the IP-to-AS mappings – Remaining mismatches between traceroute and BGP

Future Work on AS Traceroute Lower measurement overhead – Avoid traceroute probes that would discover similar paths – Work with BGP routing tables rather than live feeds Limiting the effects of traceroute inaccuracies – Catch routing changes through repeat experiments – Use router-level graphs to detect AS boundaries – Detect routers using outgoing link in “time exceeded” Public AS traceroute tool – Periodic data collection and computation of IP-to-AS mapping – Software to apply mapping to traceroute output Network troubleshooting – Analyze valid differences between forwarding and signaling paths – Use the AS traceroute tool to detect and characterize anomalies