Transcript Internet Measurements - Computer Science & Engineering

Lecture 14:
Internet Measurement
CS 765: Complex Networks
Internet
 Web of interconnected networks
 Grows with no central authority
 Autonomous Systems optimize local communication efficiency
 The building blocks are engineered and studied in depth
 Global entity has not been characterized
 Most real world complex-networks
have non-trivial properties.
 Global properties can not be inferred from local ones
 Engineered with large technical diversity
 Range from local campuses to transcontinental backbone
providers
2
Internet Measurements
 Need for Internet measurements arises due to
commercial, social, and technical issues
 Realistic simulation environment for developed products,
 Improve network management
 Robustness with respect to failures/attacks
 Comprehend spreading of worms/viruses
 Know social trends in Internet use
 Scientific discovery
 Scale-free (power-law), Small-world, Rich-club, Dissasortativity,…
3
Internet Topology Measurement
CAIDA 2006
4
Internet Topology Measurement
5
CAIDA 2006
5
Internet Topology Measurement
6
Internet Topology Measurement
7
CAIDA 2006
7
Internet Topology Measurements
Probing
 Direct probing
IPB
IPD
Vantage Point
IPBD TTL=64
A
B
C
D
 Indirect probing
IPB
IPC
Vantage Point
IPD TTL=1
TTL=2
A
B
C
D
http://www.caida.org/publications/animations/active_monitoring/traceroute.mpg
8
Internet Topology Measurement
Topology Collection (traceroute)
 Probe packets are carefully constructed to elicit intended response
from a probe destination
IPB
IPA
IPC
IPD
Vantage Point
Destination
TTL=1
TTL=2
TTL=3
TTL=4
S
A
B
C
D
 traceroute probes all nodes on a path towards a given destination
 TTL-scoped probes obtain ICMP error messages from routers on the path
 ICMP messages includes the IP address of intermediate routers as its source
 Merging end-to-end path traces yields the network map
9
Internet Topology Measurement:
Background
Internet2 backbone
S s.3
s.2
n.1
c.2
u.1
U
c.1
u.2
k.1
u.3
l.1
K
k.2
C
w.1
c.3
c.4
L
a.1
l.3
Trace to Seattle
A
a.3
h.2
h.1
H
h.3
h.4
d
10
W
w.2
w.3
k.3
l.2
n.3
N
a.2
Trace to NY
Internet Topology Measurement:
Background
s.1
e
f
S s.3
n.2
s.2
n.1
c.1
u.1
U
u.2
k.1
u.3
l.1
K
k.2
c.2
C
w.1
c.3
c.4
a.1
l.2
l.3
A
a.3
h.2
h.1
H
h.3
h.4
d
11
W
w.2
w.3
k.3
L
n.3
N
a.2
Topology Sampling
Issues
 Sampling to discover networks
 Infer characteristics of the topology
 Different studies considered
 Effect of sample size [Barford 01]
 Sampling bias [Lakhina 03]
 Path accuracy [Augustin 06]
 Sampling approach [Gunes 07]
 Utilized protocol [Gunes 08]
 ICMP echo request
 TCP syn
 UDP port unreachable
12
Anonymous Router Resolution
Problem
 Anonymous routers do not respond to traceroute
probes and appear as a  in path traces
 Same router may appear as a  in multiple traces.
 Anonymous nodes belonging to the same router should be resolved.
 Anonymity Types
1.
2.
3.
4.
5.
Ignore all ICMP packets
ICMP rate-limiting
Ignore ICMP when congested
Filter ICMP at border
Private IP address
13
Anonymous Router Resolution
Problem
e
f
Internet2 backbone
S
N
C
U
W
K
L
A
H
d
14
Traces
•d--L-S-e
•d--A-W--f
•e-S-L--d
•e-S-U--C--f
•f--C---d
•f--C--U-S-e
Anonymous Router Resolution
Problem
S
U
L
e
Traces
•d--L-S-e
•d--A-W--f
•e-S-L--d
•e-S-U--C--f
•f--C---d
•f--C--U-S-e
H
d
S
K
C
N
A
f
W
Sampled network
C
U
f
L
A
e
d
W
Resulting network
15
Graph Based Induction
Common Structures

A
x
y1
y2
y3
C



A
x
y1
y2
y3
C
Parallel nodes
x
A
D
w
x
C
E
z
y
Clique
x

y

A
C


C
E
F
z
x
A

v
Complete Bipartite
D

w
C


y
D
A
w

x
A

E
z
C

16
x
A



y
F
w
E
z
w

E
D
Star

 
z
D
y
v
C
D
E
y
w
z
Alias Resolution:
.33
 Each interface of a router
.5
has an IP address.
 A router may respond with
different IP addresses to
different queries.
.18
Denver
.7
.13
 Alias Resolution is the process of grouping the interface
IP addresses of each router into a single node.
 Inaccuracies in alias resolution may result in a network
map that
 includes artificial links/nodes
 misses existing links
17
IP Alias Resolution
Problem
s.1
e
f
S s.3
n.2
s.2
n.1
u.1
U u.2
c.1
k.1
l.1
C
w.1
c.3
W
w.2
w.3
c.4
K k.2
u.3
c.2
N n.3
k.3
L
a.1
l.2
l.3
A
a.2
a.3
h.2
h.1
H
h.3
h.4
d
18
Traces
• d - h.4 - l.3 - s.2 - e
• d - h.4 - a.3 - w.3 - n.3 - f
• e - s.1 - l.1 - h.1 - d
• e - s.1 - u.1 - k.1 - c.1 - n.1 - f
• f - n.2 - c.2 - k.2 - h.2 - d
• f - n.2 - c.2 - k.2 - u.2 - s.3 - e
IP Alias Resolution
Problem
S
U
K
C
N
f
Sampled network
L
e
H
A
W
d
s.3
u.1
k.1
c.1
n.1
u.2
k.2
c.2
n.2
s.1
e
f
s.2
w.3
l.1
l.3
n.3
a.3
h.2
h.1
h.4
Sample map
without alias resolution
d
19
Traces
• d - h.4 - l.3 - s.2 - e
• d - h.4 - a.3 - w.3 - n.3 - f
• e - s.1 - l.1 - h.1 - d
• e - s.1 - u.1 - k.1 - c.1 - n.1 - f
• f - n.2 - c.2 - k.2 - h.2 - d
• f - n.2 - c.2 - k.2 - u.2 - s.3 - e
Genuine Subnet Resolution
Problem
 Alias resolution
 IP addresses that belong to the same router
IP2
IP3
IP1
IP4
IP6
IP5
 Subnet resolution
 IP addresses that are connected over the same medium
IP1
IP1
IP2
IP3
IP2
20
IP3
Autonomous System Level
21
22
http://www.caida.org/publications/animations/active_monitoring/as_core.mpg
23
Traffic Measurements
 Monitoring and measuring network traffic
 to produce better models of network behavior
 to diagnose failures and detect anomalies
 to defend against unwanted traffic
 Live weather map
 Internernet2
 PlanetLab
24
Code-Red Worm
 On July 19, 2001, more than 359,000 computers connected to the
Internet were infected with the Code-Red (CRv2) worm in less than
14 hours
 Spread
25
Sapphire Worm
 was the fastest computer worm in history
 doubled in size every 8.5 seconds
 infected more than 90 percent of vulnerable hosts within 10
minutes.
26
Witty Worm
 reached its peak activity after approximately 45 minutes
 at which point the majority of vulnerable hosts had been infected
 World
 USA
27
Nyxem Email Virus
 Estimate of total number of infected computers is
between 470K and 945K
 At least 45K of the infected computers were also
compromised by other forms of spyware or botware
 Spread
28
Scam Hosting
 Study dynamics of scam hosting infrastructure
29
Measurement Studies
 Glasnost
 tests whether BitTorrent is being blocked or throttled
 BW-meter
 Measurement tools for the capacity and load of Internet paths
 NPAD Diagnostics Servers
 Automatic diagnostic server for troubleshooting end-systems and
last-mile network problems
 iPlane
 construct a router interface-level atlas of the Internet
 measuring link attributes
 Hubble
 find persistent Internet black holes as they occur
30
Internet Measurements
 The Internet is man-made, so why do we need to
measure it?
 Because we still don’t really understand it
 Sometimes things go wrong
 Malicious users
 Measurement for network operations
 Detecting and diagnosing problems
 What-if analysis of future changes
 Measurement for scientific discovery
 Creating accurate models that represent reality
 Identifying new features and phenomena
31