Transcript Infrasctucture measurement

Internet Infrastructure
Measurement: Challenges and
Tools
Mustafa Zali
Internet Measurement
Tuesday, 26 Aban 1388
1
Introduction




Review the physical properties of Internet
Physical Properties
 Devices (routers, NAT boxes, firewalls, switches),
Links (wired, wireless)
Topology Properties
 Various levels – Autonomous Systems, Points of
Presence, Routers, Interfaces
Traffic Properties
 Delays
(Transmission, Propagation, Queuing,
Processing etc.), Losses, Throughput, Jitter
2
Outline

Properties

Challenges

Tools
3
Properties

Review the important properties of Internet in
bottom-up approach:




Component Devices
Topology: How devices interconnected
Interaction of traffic and infrastructure
Our focus in on properties affected by
physical infrastructure
4
Physical Devices Properties



Internet: End Systems, Core
Core: Switch, Router, Link
The infrastructure that concerns us here is
core of internet.
5
Link



Viewed at the IP layer propagation of data from
one node to another is via links.
The details of links is hidden from IP layer (ch 2).
Link properties





Propagation delay
Capacity
Packet delay
Packet loss
jitter
6
Router



Routers move packets from one link to
another.
Drop tail
Active Queue Management
7
Router
Routing Engine
Forwarding table
updates
Forwarding Table
Routing Protocol
Packet
Forwarding Engine
8
Router
Buffer-Interface
Interface
Switching
Fabric
Interface
Buffer-Interface
9
Wireless



The primary goal of wireless connection is to
link users to wired infrastructure
Wireless technology: distance, data rate,
reliability, potential interference, number of
current users.
Security problem: very open nature of
wireless
10
Wireless- Technologies



Narrowband
Wideband: allows signal to be detected easily
by receiver.
Infrared: using high frequency range.
11
Wireless- Standards

802.x: 802.11a, 802.11b, 802.11g



802.11b: WiFi (Wireless fidelity)
Bluetooth: shorter distance, less power
consumption, cheaper
WiMAX: 802.16
12
Wireless

Measurements






Signal strength
Amount of power consumed
Data bite rate
Degree of coverage
Session related information (duration, set-up time)
Other traditional measurements
13
Topology properties

Four level

Autonomous systems: Independently operated and
managed network



Point of presence: Consists of one or more routers in
a single location.
Router: Router graph


BGP protocol for routing between them.
Vertices are router and edges are links between them
Interface: Interface Graph

Vertices are router intreface and edges are links onehop connection
14
Interaction of Traffic and Network

Network constrains traffic:


Minimum possible delay
Maximum possible throughput
15
Packet Delay

Routing delay





Packet processing delay
Queuing delay
Additional delay
s  packet size 
Transmission delay t transmissi on delay 
d link length 
Propagation delay
v link speed 
d  p   G d h 
16
Packet Loss

Ln
In element n:  n 
Cn

Aggregate loss:  n  1 
 1   
n ,i
i

Along pass is aggregate of hops:


log 1   p   l  p   Gl h 
17
Throughput

Cn
Throughput
T

Throughput on path t  p   Gt h 
18
Packet Jitter


Variability of packet inter arrival times
Low jitter: more predictable, more reliable
19
Challenges


Poor Observability: Observability is not built
into the design of Internet protocols and
components.
Reasons for this:




Core Simplicity
Hidden Layers
Hidden Pieces
Administrative Barriers
20
Core Simplicity




Stateless nature: Stupid network
Routers is very simple.
Explosive growth of Internet
As network elements do not track packets
individually, interaction of traffic with the
network is hard to observe
21
Hidden Layers



Below IP level, packet transmission implemented in
many ways.
These details are hidden from IP level.
Detailed measurement can not capture these
details.
22
Hidden Pieces - Middleboxes

End-to-end argument.


Firewalls – provide security
Traffic Shapers – assist in traffic management
Proxies – improve performance by terminating TCP
inside network. (Cache proxy)
NAT boxes – utilize IP address space efficiently

Each of these impedes visibility of network components.




firewalls may block active probing requests
NATs hide away the no. of hosts and the structure of the
network on the other side
23
Administrative Barriers

Owing to the competition-sensitive nature of
the data required (topology, traffic etc.), ISPs
actively seek to hide these details from
outside discovery

Information that they do provide are often
simplified.

E.g.: Instead of publishing router-level topologies,
ISPs often publish PoP-level topologies
24
Tools Classification




Active Measurement
Passive Measurement
Fused/Combined Measurement
Bandwidth Measurement
25
Active Measurement Tools

Methods that involve adding traffic to the
network for the purposes of measurement

Ping: Sends ICMP ECHO_REQUEST and
captures ECHO_REPLY



Useful for measuring RTTs
Only sender needs to be under experiment control
Zing: Sends at random, exponential time
26
Traceroute

Useful for determining path from a source to
a destination

Uses the TTL (Time To Live) field in the IP
header in a clever but distorted way

A large scale measurement system called
skitter uses traceroute to discover network
topology (Chapter 10)
27
IPIP Header
and
the
TTL
field
protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
32 bits
head. type of
len service
flgs
16-bit identifier
time to upper
layer
live
ver
length
fragment
offset
Internet
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
28
Traceroute Problem

Suppose the path between A and D is to be
determined using traceroute
X
Y
D
A
B
C
29
Traceroute Process
X
A
Y
D
B: “time
exceeded”
Dest = D
TTL = 1
B
C
30
Traceroute Process
X
A
Y
D
C: “time exceeded”
Dest = D
TTL = 2
B
C
31
Traceroute Process
X
A
Y
D
D: “echo reply”
Dest = D
TTL = 3
B
C
32
Traceroute issues

Path Asymmetry (Destination -> Source need
not retrace Source -> Destination)

Unstable Paths and False Edges

Aliases

Measurement Load
33
Unstable Paths and False Edges
Inferred path: A -> B -> Y
Y: “time exceeded”
Dest = D
X
Y
TTL = 2
A
D
B: “time exceeded”
Dest = D
TTL = 1
B
C
34
Aliases




IP addresses are for interfaces and not
routers
Routers typically have many interfaces, each
with its own IP address
IP addresses of all the router interfaces are
aliases
Traceroute results require resolution of
aliases if they are to be used for topology
building
35
Aliases

Alias resolution:




Send packet to both interface.
Close IP ID field and same TTL field.
Record Route Option. (The address of interface
that is packet sent.)
Guess: difference in last bits.
36
Measurement Load


Traceroute inserts considerable load on network
links if attempting a large-scale topology discovery
Optimizations reduce this load considerably




Track interfaces visited already
Assumption: Routers are stable and only one path exists.
If single source is used, instead of going from source to
destination, a better approach is to retrace from destination
to source.
If multiple sources and multiple destinations are used,
sharing information among these would bring down load
considerably (A->B->C->D, X->B)
37
System Support





Injecting and capturing packets, has several security
problems.
Efficient packet injection and accurate measurement
of arrival and departure times are best done at kernel
level
Using scriptroute, unprivileged users can inject
and capture packets
Periscope’s API helps define new probing
structures and inference techniques for extracting
results from arrival patterns of responses
Unrestricted access to the network interface raises
security concerns
38
Passive Measurement

Methods that capture traffic generated by other
users and applications to build the topology
39
BGP




A BGP routing table is the set of paths.
Each path is the sequence of ASes.
Each AS advertises the routes that it knows.
Routeviews repository is useful for passive
internet analysis and monitoring.
40
41
BGP– Advantages and Disadvantages

Large set of AS-AS, router-router connections can
be learned by simply processing captured tables

However, especially using BGP views, there could
be potential loss of cross-connections between
ASes which are along the path

Secondly, route aggregation and filtering tends to
hide some connections

Also, multiple connections between ASes will be
shown as a single connection in the graph
42
OSPF


Capture link state announcements within
routing domain.
Announcements


Topology changes
External routes change availability
43
Fused Measurement




Combine
both
active
and
passive
measurements.
Active: large amount of traffic.
One way is to using passive measurement
Another way is to augment passively
obtained BGP topologies with additional inter
AS connections.
44
Bandwidth Measurement


Bandwidth – amount of data the network can
transmit per unit time
Bandwidth measure requirements




Streaming media applications
Server selection
Estimating the bandwidth for TCP flow control
Verification of service level agreement
45
Bandwidth Measurement

Bandwidth measurement is a active process
Bottleneck: link with minimum bandwidth

Three kinds of bandwidth:



capacity: max throughput a link can sustain,
available bandwidth: capacity – used bandwidth and
u t    

u  x dx

 
1
t
t
1  ut   C
bulk transfer capacity: rate that a new single long-lived
TCP connection would obtain over a path
46
Bandwidth Measurement


Tight link: Link with minimum available
bandwidth
Narrow link : Link with minimum capacity
bandwidth  f queueing delay, transmission delay 
47
Bandwidth Measurement Methods

These focus on observing how packet delay
(queuing and transmission) is affected by link
properties
Four types:
 Packet-pair Methods
 Size-delay Methods
 Self-induced Congestion
 Bulk Transfer Capacity Measurement
48
Packet-Pair Methods



Methods to measure capacity and available bandwidth
Involve sending probe packets with known inter-packet
gaps and measuring the same gap downstream
where C is the capacity, L is the length of probe packets,
max delta is the maximum inter-packet gap measured
downstream
49
Packet-Pair Methods- Capacity

L
 i 1  max   i , 
 Ci 



 L 
L 
L
, 
 h 1  max   h ,   max  max   h 1 ,

Ch 
C
C
h

1
h








 L
L
L
 max  max   0 , , ,..., 
C0  C1
Ch 



 1 
L


 h 1  max   0 , L  max    
i0 ,..., H C
 i   min Ci 

i0 ,..., H
50
Packet-Pair Methods- Capacity

Capacity of narrow link can be estimated:
L
C
 h 1

The packets should be queued at bottleneck
L
link:
 0 
C

Cross traffic: sending many probe packets
51
Packet-Pair Methods- Bandwidth

Assumption:
 FIFO queuing
 Router queue is not empty between first
and second probe packet
 Tight link is narrow link
  h1   0 

A  C  1 
0


52
Size Delay Methods






Useful for measuring link capacities on each link along a
path
Based on the observation that transmission delay is
affected by link capacity and packet size
The idea is to send many different sized packets and
measure the difference in delays affected by packet size.
Then the capacity of each link will be a function of these
differences
Method assumes there is no cross-traffic, no variation in
packet size
Measurements become less accurate if the length of the
path grows
53
Size Delay Methods



Queuing delay
Transmission delay
Propagation delay
54
Size Delay Methods
i
L
Ti L    i  
k 1 Ck
i
1
i  
k 1 Ck
Ti L    i  i L
1
Ci 
Bi  Bi 1
55
Self Induced Congestion



Find the maximum probe rate that create
congestion
Increase R until congestion occurs
Problem: cross traffic
56
Bulk Transfer Capacity Management

One opens a TCP connection over the path
and sends as much as data that the path can
handle
57
Caveats in Bandwidth Measurements

High rate links make it difficult to measure
bandwidth accurately because of small delays

Wireless links affect rate dramatically on fine
timescales

FIFO order is not guaranteed in wireless links

Layer 2 devices can cause underestimation of a IP
hop’s capacity by introducing additional transmission
delays
58
Conclusion





Internet Measurement is key to designing the next
generation communication network
Fundamental design principles of the current internet
make it harder for measuring various aspects of it
Preliminary research has resulted in a set of basic tools
and methods to measure aspects like topology, traffic
etc.
Accuracy of such methods is still an open question
There is still a lot of ground to cover in this direction and
this is where researchers like you come into the
equation!
59