1 Performance Teoría de las Comunicaciones – Redes 1 Cuatrimestre 2011

2 “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 Calidad de Servicio en Internet

3 Performance

4 Performance Metrics  Bandwidth (throughput) m data transmitted per time unit m link versus end-to-end m notation KB = 2 10 bytes ( Peterson !!!!) Mbps = 10 6 bits per second  Latency (delay) m time to send message from point A to point B m one-way versus round-trip time (RTT) m components Latency = Propagation + Transmit + Queue Propagation = Distance / c Transmit = Size / Bandwidth

5 Bandwidth versus Latency  Relative importance m 1-byte: 1ms vs 100ms dominates 1Mbps vs 100Mbps m 25MB: 1Mbps vs 100Mbps dominates 1ms vs 100ms  Infinite bandwidth m RTT dominates Throughput = TransferSize / TransferTime TransferTime = RTT + 1/Bandwidth x TransferSize m 1-MB file to 1-Gbps link as 1-KB packet to 1-Mbps link

6 Delay x Bandwidth Product  Amount of data “in flight” or “in the pipe”  Example: 100ms x 45Mbps = 560KB

7 Algunas de los slides siguientes estan basadas en : Redes de computadores: un enfoque descendente basado en Internet, 2ª edición. Jim Kurose, Keith Ross 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.

8 ¿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. A B Paquetes en transmisión (retardo) Paquetes encolados (retardo) Búferes libres (disponibles): paquetes de llegada abandonados (pérdida) si no hay búferes libres

9 Cuatro fuentes de retardo de paquetes  1. Procesamiento nodal: m Comprueba errores de bit. m Determina la salida del enlace. A B Propagación Transmisión Procesamiento nodal Encolado  2. Encolado: m Tiempo de espera para un enlace de salida para la transmisión. m Depende del nivel de congestión del router.

10 Tipos de Retardo Componentes del retardo extremo a extremo: Retardo de Procesamiento Retardo de Colas Retardo de Transmisión Retardo de Propagación

11 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

12 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

13 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

14 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 Retardo de Propagación

15 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?

16 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 (~2x10 8 m/sec)  Retardo de propagación=d/s A B Propagación Transmisión Procesamiento nodal Encolado Nota: ¡s y R son cantidades muy distintas!

17 Analogía de la caravana  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?  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 Peaje Caravana de 10 coches 100 km

18 Analogía de la caravana  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?  ¡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! m Véase applet Ethernet en el sitio Web de AWL. Peaje Caravana de 10 coches 100 km

19 Retardo nodal  d proc = retardo de proceso m Normalmente unos pocos microsegundos o menos.  d cola = retardo de cola m Depende de la congestión.  d trans = retardo de transmisión m = L/R, significativo para enlaces de baja velocidad.  d prop = retardo de propagación m Desde unos pocos microsegundos hasta a cientos de milisegundos.

20 Retardo de cola (repaso)  R = ancho de banda del 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! Media de retardo de cola

21 Network Measurement Bandwidth Analysis

22 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.

23 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!

24 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).

25 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.

26 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.

27 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.

28 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.

29 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)

30 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:

31 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.

32 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.

33 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.

34 Sources Downey, Alan B. “Using pathchar to estimate Internet length characteristics.” http://www.acm.org/sigcomm/sigcomm99/papers/session7-1.pdf. 1999 http://www.acm.org/sigcomm/sigcomm99/papers/session7-1.pdf Jacobson, Van. “pathchar – A Tool to Infer Characteristics of Internet Paths.” ftp://ftp.ee.lbl.gov/pathchar/msri-talk.pdf. April 21, 1997.ftp://ftp.ee.lbl.gov/pathchar/msri-talk.pdf Postel, J. “RFC 792 Internet Control Message Protocol.” http://www.freesoft.org/CIE/RFC/792/index.htm. September, 1981. http://www.freesoft.org/CIE/RFC/792/index.htm

35 Retardo y rutas “reales” en Internet  ¿Cómo son los retardos y las rutas “reales” en Internet?  Programa Traceroute : mide el retardo desde la fuente al router por el recorrido de Internet terminal a terminal hacia el destino. Para todo ello: m Envía tres paquetes que alcanzarán el router i de camino a su destino. m El router i le devolverá los paquetes al remitente. m Intervalo de tiempos de envío entre la transmisión y la respuesta. 3 sondas

36 Retardo y rutas “reales” en Internet 1 cs-gw (128.119.240.254) 1 ms 1 ms 2 ms 2 border1-rt-fa5-1-0.gw.umass.edu (128.119.3.145) 1 ms 1 ms 2 ms 3 cht-vbns.gw.umass.edu (128.119.3.130) 6 ms 5 ms 5 ms 4 jn1-at1-0-0-19.wor.vbns.net (204.147.132.129) 16 ms 11 ms 13 ms 5 jn1-so7-0-0-0.wae.vbns.net (204.147.136.136) 21 ms 18 ms 18 ms 6 abilene-vbns.abilene.ucaid.edu (198.32.11.9) 22 ms 18 ms 22 ms 7 nycm-wash.abilene.ucaid.edu (198.32.8.46) 22 ms 22 ms 22 ms 8 62.40.103.253 (62.40.103.253) 104 ms 109 ms 106 ms 9 de2-1.de1.de.geant.net (62.40.96.129) 109 ms 102 ms 104 ms 10 de.fr1.fr.geant.net (62.40.96.50) 113 ms 121 ms 114 ms 11 renater-gw.fr1.fr.geant.net (62.40.103.54) 112 ms 114 ms 112 ms 12 nio-n2.cssi.renater.fr (193.51.206.13) 111 ms 114 ms 116 ms 13 nice.cssi.renater.fr (195.220.98.102) 123 ms 125 ms 124 ms 14 r3t2-nice.cssi.renater.fr (195.220.98.110) 126 ms 126 ms 124 ms 15 eurecom-valbonne.r3t2.ft.net (193.48.50.54) 135 ms 128 ms 133 ms 16 194.214.211.25 (194.214.211.25) 126 ms 128 ms 126 ms 17 * * * 18 * * * 19 fantasia.eurecom.fr (193.55.113.142) 132 ms 128 ms 136 ms Traceroute: gaia.cs.umass.edu a www.eurecom.fr Tres medidas de retardo desde gaia.cs.umass.edu hasta cs- gw.cs.umass.edu * Quiere decir que no existe respuesta (probe lost, router not replying) Enlace trasatlántico

37 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.

38 Adicionales ( Importantes!)

39 Payload Voz TransporteRedEnlaceFísico G.711, G.729, G.723(.1) RTP/UDPIP MLPPP/FR/ATM AAL1 – – – Voz sobre IP Protocolos de señalización ( H.323, MGCP, SGCP, SIP etc)

40 Requerimientos de ancho de banda de los Codecs Encoding/Compression G.711 PCM A-Law/u-Law G.726 ADPCM G.727 E-ADPCM G.729 CS-ACELP G.728 LD-CELP G.723.1 CELP Resulting Bit Rate 64kbps (DS0) 16, 24, 32, 40 kbps 8kbps 16kbps 6.3/5.3 kbps

41 Fluctuación del retardo—“Jitter” t t Emisor Transmite Receptor Recibe A A B B C C A A B B C C 50 ms EmisorReceptor Red 50 ms90 ms Congestión Retardo: 70 ms  20 ms (retardo: 70 ms, jitter: 40 ms) Red vacía

42 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

43 PSTN Wireless access network “voz paquetizada”  one-way delay aceptable : 0-150 ms (ITU-T G.114) m Latencia=transmisión + propagación + queuing delay 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.)

44 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

45 Sliding Window Host A Host B ACK Window Size Round-trip time (1) RTT > Window size ACK Window Size Round-trip time (2) RTT = Window size ACK Window Size ???

46 Utilización vs RTT normalizado Fuente : Stallings W. Comunicaciones y Redes de Computadores- 7 Edición