Transcript long talk
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
Detect and diagnose reachability problems
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
tool exploits this TTL behavior
Time
exceeded
destination
TTL=2
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
No response
from router
1 169.229.62.1
inr-daedalus-0.CS.Berkeley.EDU
2 169.229.59.225
soda-cr-1-1-soda-br-6-2
3 128.32.255.169
vlan242.inr-202-doecev.Berkeley.EDU
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
?
9 209.247.9.170
pos8-0.hsa2.Atlanta2.Level3.net
No name resolution
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
IP traffic
Internet
destination
source
Autonomous System (AS)
Border Gateway Protocol (BGP)
Signaling path: control traffic
Origin AS
d: path=[BC]
d: path=[C]
Forwarding path: data traffic
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
5 128.32.0.66
AS11423 Calren
6 209.247.159.109 AS3356
7 *
AS3356
8 64.159.1.46
AS3356
9 209.247.9.170
AS3356
10 66.185.138.33
AS1668
11 *
AS1668
12 66.185.136.17
AS1668
13 64.236.16.52
AS5662 CNN
Level3
AOL
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 match.
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
BGP path: B C
Traceroute path: B C D
E
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
– Compute matchings using dynamic programming
– Improve mapping through iterative refinement
Measurement
methodology
– 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