The Impact of Crooked Traceroute on Network Topologies

 
Measured Impact of Crooked
Traceroute
 
Matthew Luckie, David Murrell (
Univ. of Waikato
)
Amogh Dhamdhere, kc Claffy (
CAIDA/UCSD
)
 
1
 
The Problem
 
Traceroute-based algorithms are critical to
macroscopic topology collection efforts
Until recently, such algorithms ignored the
effects of per-flow load balancing
Classic traceroute + per-flow load balancing:
Inference of false loops  -- Augustin 
et al.
 IMC ’06
Lower destination reachability -- Luckie 
et al.
 IMC ’08
Inference of false links
 
6 October 2024
 
2
 
Measured Impact of Crooked Traceroute -
AIMS 2011
The Problem
Classic traceroute: probes
toward a destination can
take different paths
Augustin 
et al. 
IMC’07: 39% of
paths have at least one per-
flow load-balancer
 We try to quantify false link
inference rate
Can’t go back and fix pre-
2006 data
6 October 2024
Measured Impact of Crooked Traceroute -
AIMS 2011
3
0
1
0
2
0
0
0
1
1
0
1
1
1
2
 
Terminology
 
Artifact links: links that are inferred by classic
traceroute but not actually traversed by
packets in flows
Artifact links would not be inferred with a
traceroute algorithm that enumerates per-flow
load-balanced paths toward the destination,
e.g., MDA traceroute
An artifact link is not necessarily false!
False links: Artifact links which we believe to
not exist in the topology
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
4
 
 
Interface graph
 
With load balancing
at X, A, and B, MDA
traceroute would see
this graph
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
5
 
Y
 
Interface graph
Inferred using
classic traceroute
 
B
 
C
 
D
 
F
 
A
-
E
 
i
s
 
a
n
a
r
t
i
f
a
c
t
 
o
f
 
c
l
a
s
s
i
c
t
r
a
c
e
r
o
u
t
e
 
6 October 2024
 
6
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Y
 
B
 
C
 
D
 
F
 
A-E does not
introduce a false link
if A+B are aliases in
the router topology
 
Interface graph
revealed using
classic traceroute
 
A,B
 
6 October 2024
 
7
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
A-E does not
introduce a false link
if C+E are aliases in
the router topology
 
Interface graph
revealed using
classic traceroute
 
6 October 2024
 
8
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
A-E could introduce
a false link in this
router topology
 
Interface graph
revealed using
classic traceroute
 
6 October 2024
 
9
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Not all load balancing could produce an
artifact
 
 
 
 
6 October 2024
 
10
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Methodology
 
22 ark monitors, each probing a list of 16189
addresses
Derived from BGP data from Routeviews in Sept 2010
Identify artifact links in classic traceroute data
MDA to infer all possible links towards a destination to
99% confidence
Artifact links appear in the output of classic traceroute
but not in MDA traceroute
Determine if the artifact could introduce a
false router link
 
6 October 2024
 
11
 
Measured Impact of Crooked Traceroute -
AIMS 2011
Identifying False Links
6 October 2024
Measured Impact of Crooked Traceroute -
AIMS 2011
12
 
Use Ally and Mercator to check
for aliases
If (A,B) or (E,C) or (E,D) are
aliases, then the artifact link is not
false (classification: valid)
If (A, B, C, D, E) all exhibit
incrementing IPID but no alias is
found, the artifact could be a false
link
Otherwise artifact is unclassified.
 
Assumption (validated) is
that IPID-based alias
resolution can determine
whether or not two IP
addresses are aliases if
incrementing IPID values
are observed.
 
Routing Changes
 
To guard against false positives as a result of
path changes, we use the following procedure
1.
Initial Paris traceroute
2.
Classic traceroute
3.
MDA traceroute to 99% confidence
4.
Final Paris traceroute
Infer stable routing if neither Paris trace infers
a link not also seen with MDA
 
6 October 2024
 
13
 
Measured Impact of Crooked Traceroute -
AIMS 2011
Summary of Results
6 October 2024
Measured Impact of Crooked Traceroute -
AIMS 2011
14
 
False AS links
 
Traceroute is often used to infer AS-level
connectivity
Using prefix-AS mapping on each interface
False router links in classic traceroute can
cause false AS links
26733 AS links in UDP-based graph, 28591
in ICMP graph
58 false AS links in UDP, 23 in ICMP
3 AS links (UDP) and 2 AS links (ICMP) were
found in UCLA’s BGP AS topology
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
15
 
ISP-level Impact of False Links
 
We found small impact of false links on
macroscopic topology
But what about mapping specific ISPs?
Obtained ground truth from tier-1 ISP: 1986
routers, and set of interfaces on each router
Probed prefixes in ISP’s customer cone from
265 Planetlab sites
Observed interfaces from ~45% of ISP’s
routers, ~1400 links with Paris traceroute,
~4000 with Classic
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
16
 
ISP Router Degree Distribution
 
UDP-Classic makes the
ISP appear to have
much richer
connectivity
Router degrees inflated
by a median factor of
2.9 in UDP-Classic vs
UDP-Paris
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
17
 
ISP PoP-level Path Diversity
 
We map routers to PoPs
using geographic
information
We compute the number
of edge and node-
disjoint paths between
each pair of PoPs
UDP-Classic
overestimates path
diversity
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
18
 
Summary
 
Quantified the impact of classic traceroute +
per-flow load balancing
Macroscopic topology: small impact
0.76% of links in classic ICMP traceroute are invalid
2.71% of links in classic UDP traceroute are invalid
Classic ICMP-echo approach not as affected
by per-flow load balancers as UDP
ISP mapping: larger impact
Classic traceroute overestimates router degrees
(median factor 2.9), PoP level path diversity
 
6 October 2024
 
19
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Thanks!
Questions?
 
6 October 2024
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
20
 
www.caida.org/~amogh/crooked-CCR10.pdf
 
Artifact link impact: analytical alias resolution
 
Analytical alias resolution rule: two addresses
in a traceroute path can’t be aliases if there
are no loops.
 
0
 
0
 
0
 
0
 
1
 
0
 
0
 
Y
 
1
 
Y
 
0
 
0
 
0
 
0
 
10-15% of false links are of this form
 
6 October 2024
 
21
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Validating use of Ally technique to
classify artifact links
 
Use ping –R and ICMP-Paris traceroute
towards destination
RR IP address 
usually
 from egress interface
ICMP time-exceeded IP address 
usually
 from ingress
interface
Infer addresses used in a sequence of /30
subnets
Identify ICMP/TCP/UDP IP-ID behaviour for
each
Resolve for aliases using Ally for pairs of
addresses with incrementing IPID values.
 
a
.
b
.
c
.
5
 
a
.
b
.
c
.
6
 
d
.
e
.
f
.
8
6
 
d
.
e
.
f
.
8
5
 
g
.
h
.
i
.
1
9
4
 
g
.
h
.
i
.
1
9
3
 
t
r
a
c
e
r
o
u
t
e
 
R
R
 
6 October 2024
 
22
 
Measured Impact of Crooked Traceroute -
AIMS 2011
 
Validating use of Ally technique: results
 
22 ark monitors, 26,510 pairs of likely /30
aliases tested
Classification obtained for 20,762 (78%)
Others did not have an incrementing IP-ID
Some were incrementing but unresponsive to Ally.
93.8% inferred as aliases
Of not aliases, 6 IPs are involved in 88% of pairs
Suggests 6 outliers rather than a systematic erro
 
6 October 2024
 
23
 
Measured Impact of Crooked Traceroute -
AIMS 2011
Slide Note
Embed
Share

Traceroute-based algorithms play a crucial role in collecting network topology data, but the introduction of per-flow load balancing has raised concerns about the accuracy of these algorithms. This study examines the implications of crooked traceroute on false link inference rates and the identification of artifact links in network topologies. By analyzing classic traceroute methods alongside load-balanced paths, researchers aim to quantify the impact of these discrepancies and improve topology collection efforts.

  • Network Topology
  • Traceroute Algorithms
  • Load Balancing
  • False Link Inference
  • Network Measurement

Uploaded on Oct 06, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Measured Impact of Crooked Traceroute Matthew Luckie, David Murrell (Univ. of Waikato) Amogh Dhamdhere, kc Claffy (CAIDA/UCSD) 1

  2. The Problem Traceroute-based algorithms are critical to macroscopic topology collection efforts Until recently, such algorithms ignored the effects of per-flow load balancing Classic traceroute + per-flow load balancing: Inference of false loops -- Augustin et al.IMC 06 Lower destination reachability -- Luckie et al.IMC 08 Inference of false links Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 2

  3. The Problem Classic traceroute: probes toward a destination can take different paths Augustin et al. IMC 07: 39% of paths have at least one per- flow load-balancer We try to quantify false link inference rate Can t go back and fix pre- 2006 data 1 0 A C 1 0 1 0 2 0 Y X 2 1 B D 1 0 1 0 X0 A0 D0 Y0 X0 B0 C0 Y0 Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 3

  4. Terminology Artifact links: links that are inferred by classic traceroute but not actually traversed by packets in flows Artifact links would not be inferred with a traceroute algorithm that enumerates per-flow load-balanced paths toward the destination, e.g., MDA traceroute An artifact link is not necessarily false! False links: Artifact links which we believe to not exist in the topology Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 4

  5. X Interface graph B A With load balancing at X, A, and B, MDA traceroute would see this graph C D E F Y Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 5

  6. Interface graph Inferred using classic traceroute X B A C D F E A-E is an artifact of classic traceroute Y Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 6

  7. X X B A,B A C D E F C D F E Y Y A-E does not introduce a false link if A+B are aliases in the router topology Measured Impact of Crooked Traceroute - AIMS 2011 Interface graph revealed using classic traceroute 6 October 2024 7

  8. X X B B A A C D F C,E D,F E Y Y A-E does not introduce a false link if C+E are aliases in the router topology Measured Impact of Crooked Traceroute - AIMS 2011 Interface graph revealed using classic traceroute 6 October 2024 8

  9. X X B B A A C D F C,D E,F E Y Y A-E could introduce a false link in this router topology Measured Impact of Crooked Traceroute - AIMS 2011 Interface graph revealed using classic traceroute 6 October 2024 9

  10. Not all load balancing could produce an artifact X X A B A C X B Y Y B A D C D E F Y Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 10

  11. Methodology 22 ark monitors, each probing a list of 16189 addresses Derived from BGP data from Routeviews in Sept 2010 Identify artifact links in classic traceroute data MDA to infer all possible links towards a destination to 99% confidence Artifact links appear in the output of classic traceroute but not in MDA traceroute Determine if the artifact could introduce a false router link Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 11

  12. Identifying False Links Use Ally and Mercator to check for aliases If (A,B) or (E,C) or (E,D) are aliases, then the artifact link is not false (classification: valid) If (A, B, C, D, E) all exhibit incrementing IPID but no alias is found, the artifact could be a false link Otherwise artifact is unclassified. Assumption (validated) is that IPID-based alias resolution can determine whether or not two IP addresses are aliases if incrementing IPID values are observed. B A C D F E Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 12

  13. Routing Changes To guard against false positives as a result of path changes, we use the following procedure 1.Initial Paris traceroute 2.Classic traceroute 3.MDA traceroute to 99% confidence 4.Final Paris traceroute Infer stable routing if neither Paris trace infers a link not also seen with MDA Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 13

  14. Summary of Results Total IP-level links ICMP UDP Classic 427,211 413,040 Paris 422,130 398,179 MDA 455,965 462,762 Artifact links 13,313 32,233 Fraction of classic links 3.12% 7.8% Inferred valid 45.9% 38.6% Inferred false 24.3% 34.7% Unclassified 29.9% 26.7% False Links 3,230 11,179 Fraction of classic links 0.76% 2.71% Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 14

  15. False AS links Traceroute is often used to infer AS-level connectivity Using prefix-AS mapping on each interface False router links in classic traceroute can cause false AS links 26733 AS links in UDP-based graph, 28591 in ICMP graph 58 false AS links in UDP, 23 in ICMP 3 AS links (UDP) and 2 AS links (ICMP) were found in UCLA s BGP AS topology Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 15

  16. ISP-level Impact of False Links We found small impact of false links on macroscopic topology But what about mapping specific ISPs? Obtained ground truth from tier-1 ISP: 1986 routers, and set of interfaces on each router Probed prefixes in ISP s customer cone from 265 Planetlab sites Observed interfaces from ~45% of ISP s routers, ~1400 links with Paris traceroute, ~4000 with Classic Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 16

  17. ISP Router Degree Distribution UDP-Classic makes the ISP appear to have much richer connectivity Router degrees inflated by a median factor of 2.9 in UDP-Classic vs UDP-Paris Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 17

  18. ISP PoP-level Path Diversity We map routers to PoPs using geographic information We compute the number of edge and node- disjoint paths between each pair of PoPs UDP-Classic overestimates path diversity Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 18

  19. Summary Quantified the impact of classic traceroute + per-flow load balancing Macroscopic topology: small impact 0.76% of links in classic ICMP traceroute are invalid 2.71% of links in classic UDP traceroute are invalid Classic ICMP-echo approach not as affected by per-flow load balancers as UDP ISP mapping: larger impact Classic traceroute overestimates router degrees (median factor 2.9), PoP level path diversity Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 19

  20. Thanks! Questions? www.caida.org/~amogh/crooked-CCR10.pdf Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 20

  21. Artifact link impact: analytical alias resolution Analytical alias resolution rule: two addresses in a traceroute path can t be aliases if there are no loops. 0 X C Y1 Y X D 0 0 0 0 0 A 0 C 0 B 1 0 10-15% of false links are of this form Y 0 D Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 21

  22. Validating use of Ally technique to classify artifact links Use ping R and ICMP-Paris traceroute towards destination RR IP address usually from egress interface ICMP time-exceeded IP address usually from ingress interface Infer addresses used in a sequence of /30 subnets Identify ICMP/TCP/UDP IP-ID behaviour for each Resolve for aliases using Ally for pairs of addresses with incrementing IPID values. d.e.f.86 g.h.i.194 RR a.b.c.5 a.b.c.6 d.e.f.85 g.h.i.193 traceroute Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 22

  23. Validating use of Ally technique: results 22 ark monitors, 26,510 pairs of likely /30 aliases tested Classification obtained for 20,762 (78%) Others did not have an incrementing IP-ID Some were incrementing but unresponsive to Ally. 93.8% inferred as aliases Of not aliases, 6 IPs are involved in 88% of pairs Suggests 6 outliers rather than a systematic erro Measured Impact of Crooked Traceroute - AIMS 2011 6 October 2024 23

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#