Transcript Performance Metrics

Performance
Teoría de las Comunicaciones
a.k.a “Redes”
2 Cuatrimestre 2011
Calidad de Servicio en Internet
“El Santo Grial de las redes de computadores es
diseñar una red que tenga la flexibilidad y el bajo
costo de la Internet, pero que ofrezca las
garantías de calidad de servicio extremo a extremo
de la red telefónica.”
S. Keshav: 'An Engineering Approach to Computer
Networking‘, 1997
Performance
Computer Networks: A Systems Approach, 5e
Larry L. Peterson and Bruce S. Davie
Chapter 1
Foundation
Copyright © 2010, Elsevier Inc. All rights Reserved
4
Performance
 Bandwidth
 Width of the frequency band
 Number of bits per second that can be transmitted over
a communication link
 1 Mbps: 1 x 106 bits/second = 1x220 bits/sec
 1 x 10-6 seconds to transmit each bit or imagine
that a timeline, now each bit occupies 1 micro
second space.
 On a 2 Mbps link the width is 0.5 micro second.
 Smaller the width more will be transmission per
unit time.
Performance Metrics
 Bandwidth (throughput)



data transmitted per time unit
link versus end-to-end
notation
• KB = 210 bytes !!!!!!!
• Mbps = 106 bits per second !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 Latency (delay)


time to send message from point A to point B
one-way versus round-trip time (RTT), one-two-delay
Bandwidth
Bits transmitted at a particular bandwidth can be
regarded as having some width:
(a) bits transmitted at 1Mbps (each bit 1 μs wide);
(b) bits transmitted at 2Mbps (each bit 0.5 μs wide).
Performance
 Latency = Propagation + transmit + queue
 Propagation = distance/speed of light . β
 Transmit = size/bandwidth
 One bit transmission => propagation is important
 Large bytes transmission => bandwidth is
important
 β = 1 in the vacuum, β < 1 in the media
 in the vacuum, usually denoted by c, is a physical
constant , 300.000 km/sec
Delay X Bandwidth
 We think the channel between a pair of processes
as a hollow pipe
 Latency (delay) length of the pipe and bandwidth
the width of the pipe
 Delay of 50 ms and bandwidth of 45 Mbps
 50 x 10-3 seconds x 45 x 106 bits/second
 2.25 x 106 bits = 280 KB data.
Network as a pipe
Delay x Bandwidth Product ( 2)
 Amount of data “in flight” or “in the pipe”
 Example: 100ms x 45Mbps = 560KB
Delay
Bandw idth
Delay X Bandwidth
 Relative importance of bandwidth and
latency depends on application
For large file transfer, bandwidth is critical
 For small messages (HTTP, NFS, etc.), latency
is critical
 Variance in latency (jitter) can also affect some
applications (e.g., audio/video conferencing)

Delay X Bandwidth
How many bits the sender must transmit before
the first bit arrives at the receiver if the
sender keeps the pipe full
 Takes another one-way latency to receive a
response from the receiver
 If the sender does not fill the pipe—send a
whole delay × bandwidth product’s worth of
data before it stops to wait for a signal—the
sender will not fully utilize the network

Delay X Bandwidth
 Infinite bandwidth
RTT dominates
 Throughput = TransferSize / TransferTime
 TransferTime = RTT + 1/Bandwidth x
TransferSize

 Its all relative
 1-MB file to 1-Gbps link looks like a 1-KB packet
to 1-Mbps link
Relationship between bandwidth and latency
A 1-MB file would fill the 1-Mbps link 80
times,
but only fill the 1-Gbps link 1/12 of one time
Bandwidth versus Latency
 Relative importance
 1-byte: 1ms vs 100ms dominates 1Mbps vs 100Mbps
 25MB: 1Mbps vs 100Mbps dominates 1ms vs 100ms
 Infinite bandwidth

RTT dominates
• Throughput = TransferSize / TransferTime
• TransferTime = RTT + 1/Bandwidth x TransferSize

1-MB file to 1-Gbps link as 1-KB packet to 1-Mbps
link
Algunas de los slides
siguientes estan basadas
en :
Nota sobre el uso de estas diapositivas ppt:
Proporcionamos estas diapositivas de forma gratuita para todos (profesores,
estudiantes, lectores). Se encuentran en formato PowerPoint, por lo que
puede añadir, modificar y borrar diapositivas (incluida la presente) y su
contenido según sus necesidades. Evidentemente, significan un gran trabajo
por nuestra parte. A cambio, sólo pedimos para su uso:
 Que mencione la fuente si usa estas diapositivas (por ejemplo, en clase),
sin alterar su contenido de forma considerable (¡nos gustaría que la gente
usara nuestro libro!).
 Que indique que dichas diapositivas son una adaptación o copia de las
nuestras y que muestre el copyright de nuestro material si cuelga las
mismas en un sitio web, sin alterar su contenido de forma considerable.
¡Gracias y disfrute! JFK/KWR
Copyright 1996-2002.
J.F Kurose y K.W. Ross.
Todos los derechos reservados.
Redes de
computadores: un
enfoque descendente
basado en Internet,
2ª edición.
Jim Kurose, Keith Ross
¿Cómo se producen el retardo y
la pérdida?
Paquetes encolados en los búferes de router:
 La tasa de llegada de paquetes al enlace excede la
capacidad de salida del enlace.
 Cola de paquetes esperando turno.
Paquetes en transmisión (retardo)
A
B
Paquetes encolados (retardo)
Búferes libres (disponibles): paquetes de
llegada abandonados (pérdida) si no hay
búferes libres
Cuatro fuentes de retardo de
paquetes
 1. Procesamiento nodal:
 Comprueba errores de
bit.
 Determina la salida del
enlace.
 2. Encolado:
 Tiempo de espera para
un enlace de salida para
la transmisión.
 Depende del nivel de
congestión del router.
Transmisión
A
Propagación
B
Procesamiento
Encolado
nodal
Tipos de Retardo
 Componentes del retardo extremo a extremo:
Retardo de Procesamiento
Retardo de Colas
Retardo de Transmisión
Retardo de Propagación
Retardo de Procesamiento
 Tiempo requerido en analizar el encabezado y
decidir a dónde enviar el paquete (ej. decisión
de enrutamiento)

En un enrutador, dependerá del número de entradas
en la tabla de rutas, la implementación (estructuras
de datos), el hardware, etc.
 Puede incluir la verificación de errores
Retardo de Colas
 Tiempo en que el paquete espera en un
búfer hasta ser transmitido
 El número de paquetes esperando en cola
dependerá de la intensidad y la naturaleza
del tráfico
 Los algoritmos de colas en los enrutadores
intentan adaptar estos retardos a ciertas
preferencias, o imponer un uso equitativo
Retardo de Transmisión
 El tiempo requerido para empujar todos los
bits de un paquete a través del medio de
transmisión
 Para R=Tasa de bits, L=Longitud del paquete, d
= delay o retardo:
d = L/R
 Por ejemplo, para transmitir 1024 bits
utilizando Fast Ethernet (100 Mbps):
d = 1024/1x10e8 = 10.24 micro
segundos
Retardo de Propagación
 Una vez que el bit es 'empujado' en el medio, el tiempo
transcurrido en su propagación hasta el final del
trayecto físico
 La velocidad de propagación del enlace depende más que
nada de la distancia medio físico
 Cercano a la velocidad de la luz en la mayoría de los
casos
 Para d = distancia, s = velocidad de propagación
Dp = d/s
Transmisión vs. Propagación
 Puede ser confuso al principio
 Considerar un ejemplo:

Dos enlaces de 100 Mbps.
Fibra óptica de 1 Km
Via Satélite, con una distancia de 30Km entre base y
satélite

Para dos paquetes del mismo tamaño, cuál tiene
mayor retardo de transmisión? Y propagación?
Retardo en redes de conmutación
de paquetes
3. Retardo de transmisión:
 R=ancho de banda del
enlace (bps).
 L=longitud del paquete
(bits).
 Tiempo de envío de bits
hacia el enlace = L/R.
4. Retardo de propagación:
 d = longitud del enlace físico
 s = media de velocidad de
propagación (~2x108 m/sec)
 Retardo de propagación=d/s
Transmisión
A
Nota: ¡s y R son
cantidades muy
distintas!
Propagación
B
Procesamiento
Encolado
nodal
Analogía de la caravana
100 km
Caravana de Peaje
10 coches
 Los coches se “propagan”
a 100 km/h.
 El peaje tarda 12 seg en
servir a un coche (tiempo
de transmisión).
 Coche~bit; caravana ~
paquete.
 P: ¿Cuánto tiempo
transcurre hasta que la
caravana se alinee ante el
segundo peaje?
100 km
Peaje
 Tiempo para “soltar” toda
la caravana pasando los
peajes a la autopista =
12*10 = 120 seg.
 Tiempo hasta que el
último coche se propaga
del primer al segundo
peaje:
100km/(100km/h)= 1 h.
 R: 62 minutos
Analogía de la caravana
100 km
100 km
Caravana de Peaje
10 coches
 Ahora los coches se
“propagan” a 1000 km/h.
 El peaje tarda 1 min en
servir un coche.
 P: ¿Llegarán los coches al
segundo peaje antes de
que se sirva a todos en el
primero?
Peaje
 ¡Sí! Tras 7 min., el primer
coche se encuentra en el
segundo peaje y aún quedan
tres coches en el primero.
 ¡El primer bit de paquete
puede llegar al segundo
router antes de que se haya
transmitido el paquete por
completo al primer router!

Véase applet Ethernet en el
sitio Web de AWL.
Retardo nodal
d nodal  d proc  d cola  d trans  d prop
 dproc = retardo de proceso
 Normalmente unos pocos microsegundos o menos.
 dcola = retardo de cola
 Depende de la congestión.
 dtrans = retardo de transmisión
 = L/R, significativo para enlaces de baja velocidad.
 dprop = retardo de propagación
 Desde unos pocos microsegundos hasta a cientos de
milisegundos.
Retardo de cola (repaso)
 R = ancho de banda del
Media de
retardo de cola
enlace (bps).
 L = longitud del paquete
(bits).
 a = media de tasa de
llegada del paquete.
Intensidad de tráfico = La/R
 La/R ~ 0: media de retardo de cola pequeño.
 La/R -> 1: aumentan los retardos.
 La/R > 1: ¡Llega más “trabajo” del que puede
servirse, media de retardo infinita!
Perfomance del Protocolo de
Ventana deslizante
 Sea un Host A, que usa protocolo de
ventana deslizante, si debe transmitir un
archivo de unos 10 GB con un Host B
 Window size = 64KB
 RTT de la red es de 1 segundo
 Cual es la velocidad esperada con que el
emisor envia datos?
 64KB/s
Sliding Window
Round-trip time
Round-trip time
Window Size
Host A
Host B
???
Window Size
ACK
(1) RTT > Window size
Window Size
ACK
ACK
(2) RTT = Window size
Utilización vs RTT normalizado
Fuente : Stallings W . Comunicaciones y Redes de Computadores- 7 Edición
Throughput protocolo ventana
delizante
T < W/RTT !!!!!!!
One way delay
Fluctuación del retardo—“Jitter”
Emisor
Receptor
Red
B
A
C
Emisor Transmite
t
A
50 ms
B
50 ms
Red vacía
C
90 ms
Receptor Recibe
t
Congestión
Retardo: 70 ms  20 ms (retardo: 70 ms, jitter: 40 ms)
Fin temas del primer parcial
Los slides que siguen los iremos
viendo a lo largo de la segunda parte
de la materia
Network Measurement
Bandwidth Analysis
Why measure bandwidth?
 Network congestion has increased tremendously.
 Bottlenecks are not always obvious.
 Measuring bandwidth may become more essential for service
providers as congestion increases.
 Measuring bandwidth enables us to improve current systems as well
as diagnosis network problems.
 Measuring bandwidth may be the key to observing what is wrong
with current protocol standards. In effect, measurement is a tool
for research in general.
Why measure bandwidth?
 Network congestion has increased tremendously.
 Bottlenecks are not always obvious.
 Measuring bandwidth may become more essential for service
providers as congestion increases.
 Measuring bandwidth enables us to improve current systems as well
as diagnosis network problems.
 Measuring bandwidth may be the key to observing what is wrong
with current protocol standards. In effect, measurement is a tool
for research in general.
Why measure bandwidth?
 Network congestion has increased tremendously.
 Bottlenecks are not always obvious.
 Measuring bandwidth may become more essential for service
providers as congestion increases.
 Measuring bandwidth enables us to improve current systems as well
as diagnosis network problems.
 Measuring bandwidth may be the key to observing what is wrong
with current protocol standards. In effect, measurement is a tool
for research in general.
How we measure bandwidth
 It’s really more complicated than a connection speed.
 We might want to look at capacity or we might be looking at
throughput or bandwidth congestion.
 We can observe packet loss, propagation delay, link capacity, but
some of this results in educated “guess work.”
 There are many theories and applications intended to measure
bandwidth and network statistics.
 For our purposes we will look at the three most common utilities
used: traceroute, ping, and pathchar.
 It really depends on what you are after!
traceroute
 Written by Van Jacobsen in 1988 to solve persistent network
problems.
 Traceroute counts hops : roughly tracing the path of an IP packet
from the client to the destination.
 Traceroute does this by sending UDP packets with an extremely
short TTL.
 If all routing nodes in the path are working properly, an ICMP
(Internet Connection Message Protocol) Time Exceeded message is
sent (RFC 792).
traceroute
 Traceroute utilizes the
information encapsulated in
the ICMP message to
determine the source (the
router that sent the packet).
 We continue sending packets
until we get an ICMP “host
unreachable message” (this
implies that we have reached
the destination) or until the
max number of hops has been
reached.
traceroute disadvantages
Traceroute is a simple tool that is based on a few key ideas:
1. All packets will be sent on the same paths (going).
2. Consistent Routing (all packets will be routed back the same
way).
3. TCP/IP implementations supporting ICMP.
In reality, poor TCP/IP implmentation means that Traceroute is not
dependable.
Using three different Traceroute implementations, to the same IP
address, resulted in three different routes.
ping
One of the most widely
distributed analysis tools. First
released in 1980.
 The UNIX version of ping is
slightly more robust, allowing us
to specify the testing data and
modify the patterns.
 ping, works by sending a single
packet and waiting for the ICMP
Echo response.

ping
 ping puts its own Round Trip Time value on each packet so we are
not left at the mercies of the router (as in traceroute).
 ping also provides us with a diagnostic of ICMP messages, usually
buried by the system.
 ping is clearly a much different tool from traceroute, but it’s
simplicity makes it more reliable.
 ping is only useful for estimating bandwidth under certain
conditions.
Pathchar
 Also written by Van Jacobson, in 1997.
 pathchar attempts to improve upon traceroute by adding
mathematical analysis to the problems that occur in propagation.
 Working in the same basic manner as traceroute, pathchar sends
out packets and waits for the response. Only instead of one set of
packets, it sends out several.
 The difference being the analysis of the returned data.
 pathchar attempts to account for:
- loss rate
- link capacity
- propagation and queing delay
(Grossglauser, pg40)
pathchar
Taking into account the rtt from two nodes, say n and n – 1 we generate the
following formula using Van Jacobson’s specifications:
But he assumes three things:



The error message is small enough to ignore (toss error_size/bandwidth out)
The forward time is not big enough to worry about.
If enough transmission groups are sent at least one will not have any queuing delays.
And so, we get:
pathchar

In practice pathchar is not the easiest tool to use. It can be difficult to
implement and its output is often chaotic.


A better implementation of pathchar was made by Bruce Mah, called pchar
Here is an example of a particular node in a trace.
What we learn from pathchar
 Pathchar’s focus is on the statistics of data loss and the analysis of





delay.
Instead of capacity, we can look at data loss and latency.
Using pathchar and traceroute, one is more likely to track down the
source of delay than to estimate bandwidth in the sense of
capacity.
In a commercial sense, we can utilize this information to see where
end users are running into difficulty.
In private application weak network components can be sorted out.
For our purposes, bandwidth congestion allows us to think
intelligibly about improving network protocols and gives us some
real world metric to diagnosis real world problems.
Conclusion
 There are two things we can conclude from this:
 ICMP may need to be rewritten to facilitate better tools.
 Bandwidth Analysis is at it’s heart a simple idea.
Sources
Downey, Alan B. “Using pathchar to estimate Internet length
characteristics.”
http://www.acm.org/sigcomm/sigcomm99/papers/session7-1.pdf.
1999
Jacobson, Van. “pathchar – A Tool to Infer Characteristics of
Internet Paths.” ftp://ftp.ee.lbl.gov/pathchar/msri-talk.pdf. April
21, 1997.
Postel, J. “RFC 792 Internet Control Message Protocol.”
http://www.freesoft.org/CIE/RFC/792/index.htm. September,
1981.
Pérdida de paquetes
 La cola (también conocida como búfer) que
precede a un enlace en el búfer tiene una
capacidad limitada.
 Cuando un paquete llega a una cola llena,
éste es abandonado (es decir, se pierde).
 El paquete perdido puede o no ser
retransmitido por un nodo anterior, por una
fuente del sistema terminal.
Adicionales ( Importantes!)
Voz sobre IP
Protocolos de señalización ( H.323, MGCP, SGCP, SIP etc)
Payload Voz
Transporte
Red
G.711, G.729, G.723(.1)
RTP/UDP
IP
Enlace
MLPPP/FR/ATM AAL1
Físico
–––
Requerimientos de ancho de banda de los
Codecs
Encoding/Compression
Resulting Bit Rate
G.711 PCM A-Law/u-Law
64kbps (DS0)
G.726 ADPCM
16, 24, 32, 40 kbps
G.727 E-ADPCM
16, 24, 32, 40 kbps
G.729 CS-ACELP
8kbps
G.728 LD-CELP
16kbps
G.723.1 CELP
6.3/5.3 kbps
Fluctuación del retardo—“Jitter”
Emisor
Receptor
Red
B
A
C
Emisor Transmite
t
A
50 ms
B
50 ms
Red vacía
C
90 ms
Receptor Recibe
t
Congestión
Retardo: 70 ms  20 ms (retardo: 70 ms, jitter: 40 ms)
Reducción del Jitter
 La principal causa de jitter es la congestión
 Se puede reducir el jitter añadiendo un retardo
adicional en el lado del receptor. Por ejemplo con
un retardo de 70  20 ms se puede asegurar jitter
0 si se añade un retardo de 40 ms (90  0 ms).
 Para el retardo adicional el receptor ha de tener
un buffer suficientemente grande.
 En algunas aplicaciones no es posible añadir mucho
retardo pues esto reduce la interactividad. Ej.:
videoconferencia, telefonía por Internet
“voz paquetizada”

one-way delay aceptable : 0-150 ms (ITU-T G.114)

Latencia=transmisión + propagación + queuing delay
PSTN
PSTN
Wireless access network
• Queuing delay: variable, se necesita acotar
=> Assume 10* hops, per hop queuing delay < 5 ms
(*Vern Paxson’s results: 8-12 hops typical across U.S.)
Bandwidth Estimation:
Metrics Mesurement Techniques and Tools
By Ravi Prasad, Constantinos Dovrolis, Margaret Murray
and Kc Claffy
IEEE Network, Nov/Dec 2003
Variable size packet probing
 Measures capacity of each hop
 Measure RTT
 Limit packet propogation by TTL
 Uses ICMP to measure RTT until that hop
Variable size packet probing
 RTT includes:

Serialization delay
• Delay to send packet of length L across channel of
capacity C = L/C

Propogation delay
• Time taken to traverse the link

Queuing delay
• Delay in routers/Switches
Variable size packet probing
 Send multiple packets and calculate minimum
RTT

Assumption: for minimum RTT no queuing delay
 RTT has two terms
 Delay independent of packet size = α
 Based on packet size
i
L
Ti ( L)    
   i L
k 1 Ck
i
where
1
i  
k 1 C k
Variable size packet probing
i
1
i  
k 1 Ck
Ci 
i
1
  i 1
packet size vs RTT
Packet pair dispersion probing
 Measures end-to-end capacity
 out

L
 max 

,
 in C
i





L
L
L
 r  max   

min i 0,... H Ci  C
i 0 ,1,... H  Ci 
Problems
 Assumption that no other traffic exists is
not real
 Existing traffic can increase/decrease the
estimate
 Solution?

Send multiple pairs and get a statistical
estimate
• Does not always yield a correct estimate
Self-loading periodic streams
 Measures end-to-end available bandwidth
 Sends k packets at different rates
 Receiver notifies the “one way delay
trends”
 If stream rate greater than available b/w

One way delay will grow large
 Else
 Packets will not make the one way delay large
One way delay
Train dispersion probing
 Similar to packet pair dispersion probing
 Instead of sending just two packets send a
train of packets
 Calculate the average dispersion rate
Taxonomy of estimation tools
Per-hop capacity estimation
tools
 Pathchar
 First tool to implement
 Clink
On routing instability collects data along all
paths
 Until one path provides statistically significant
estimate

 Pchar
 Uses linear regression algorithms
Taxonomy of estimation tools
end-to-end capacity
estimation tools
 BProbe
 Uses packet pair dispersion
 Uses variable sized packets to improve efficiency
 Access needed only in sender side, uses ICMP messages
 Nettimer
 Uses sophisticated “kernel density algorithm” to provide
better accuracy
 Pathrate
 Sprobe
Available bandwidth estimation
tools
 CProbe
 Measures dispersion of a train of eight maximum sized
packets
 It measures dispersion rate and not available bandwidth
 Dispersion rate depends on all links of the path and the
train’s initial rate
 Available b/w depends only on tight link of the path
 Pathload
 Implements SLoPS
 Used UDP and requires access at both ends
 Reports range
• Center represents the average
• Range represents values during mesurement period
TCP throughput and BTC
measurement tools
 Treno
 emulates TCP sends UDP packets to receiver
 Replies with ICMP port unreachable
 Does not require access to remote end
 ICMP rate limited
• Accuracy of Treno affected
 Cap
 More accurate than Treno
 Uses UDP for TCP data and ACK
 Requires access at both ends
Intrusiveness
 If probe packets comparable to available
b/w
 VPS are non intrusive

One packet per RTT
 PPTD tools create bursts which last only
for a very short duration

Only a small fraction of available b/w used
 BTC tools are intrusive
 They capture all b/w for a specific duration
Teoría de Colas
Notación Kendall
 A/B/m/K/N
A: distribución del tiempo de entrada de
paquetes.
B: distribución del tiempo de servicio de
paquetes.
Ej.: M (Markov) , D (Determinístico), G
(General)
m: cantidad de servidores para procesar el
trabajo.
K: capacidad máxima de paquetes (cola +
servicio).
(Si es ∞ se omite.)
Cola M/M/1
 Es una cola en la que la entrada de los
paquetes es un proceso de Poisson y el
tiempo de servicio de paquetes es
exponencial.
 Hay un único servidor.
 La cola tiene capacidad infinita. (L(t)=0)