Internet Topology
Download
Report
Transcript Internet Topology
Lecture 26:
Internet Topology
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.
Ignore all ICMP packets
ICMP rate-limiting
Ignore ICMP when congested
Filter ICMP at border
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
Cheleby System Overview
PlanetLab
Vantage Points
Traces
• x - - L.2 - S.2 - y
• x - - A.1 - W.1 - - z
• y - S.1 - L.1 - - x
• y - S.1 – U.1 - - C.1 - - z
• z - - C.2 - - - x
• z - - C.2 - - U.2 - S.3 - y
Raw Data
Initial Pruner
(IP)
Structural
Graph
Indexer (SGI)
SubNet
Inferrer (SNI)
S
y
U
L
x
K
H
C
A
N
W
z
Analytical IP
Graph Based
Alias Resolver
Network Topology
Induction
v2
(GBI)
(APARv2),
iffinder
http://cheleby.cse.unr.edu
Cheleby: Subnet-Level Internet Topology
21
Degree Distribution
Exponents : -2.17, -2.02, -1.92, respectively
Cheleby: Subnet-Level Internet
Topology
22
Interface Distribution
Exponents : -2.71, -2.69, -2.74, respectively
Cheleby: Subnet-Level Internet
Topology
23
Subnet Distribution
Exponents : -3.42, 3.62, respectively
Nodes in Subnets
Cheleby: Subnet-Level Internet Topology
24
Synthetic Topology Generation
Network Size
Generate
Nodes
ID
SD
Calculate
Degree
Distribution
based on DD
Heterogeneous
Swap
Generate
Subnets
Satisfies Subnet
& Interface
Distributions !!!
no
Match ?
Cheleby: Subnet-Level Internet Topology
yes
Final
Topology
25
Connectivity Analysis
Relation between Interface Distribution
and Number of Subnets
• Single connected component
is feasible only when
• connectivity parameter <1
Feasible Region
Cheleby: Subnet-Level Internet Topology
26
Autonomous System Level
http://www.caida.org/publications/animations/active_monitoring/as_core.mpg
27
28
29