1 Introducción Sub1 Parte
Agregación Diferentes 10 Mbps 1000 Mbps LAN a WAN 10 Mbps
64 Kbps Administración de Buffers Tendencia a llenarse de
los buffers (TCP windowing) Buffering reduce Loss, introduce
Delay Overflow de buffers => se descartan paquetes (o frames)
Para garantizar QoS se deben prealocar y reservar
3 Que hacer ?? Sobredimensionamiento (Overprovisioning)
Diseñar ……. Controlar , Evitar
…..
4 Soluciones La presencia de congestión significa que la
carga 8 a veces en forma temporaria ) es mayor que los recursos.
Desde otro punto de vista que podemos hacer : Incrementar los
recursos ( BW , Buffers ??) Decrementar la carga 😉
5 Retardo de una COLA – M/M/1 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
6 “One way delay”
7 Antecedentes [1] [1] de la presentacion de Van Jacobson
“Notes on Using Red for queue management and Congestion
Avoidance “ Junio 1998 Dispositivo control presión
en una Máquina de vapor
8 Fundamentos del control de la congestión
Congestión: Informalmente: “demasiadas fuentes
enviando demasiados datos demasiado de prisa por la red como para
poder manejarlo”. ¡Diferente del control de flujo!
Manifestaciones: Pérdida de paquetes (Los buffer se
saturan en los routers o sw). Largos retardos (por las colas en
los buffer ). ¡Uno de los diez problemas
fundamentales!
9 Consideraciones sobre los nodos De no expresarse lo contrario
se asume que : FIFO el primer paquete que llega se transmite
Cuando se llena la cola se descarta , drop tail FIFO es un
mecanismo de scheduling , drop tail es una política
Introducen sincronización global cuando los paquetes son
descartados desde diversas conexiones
10 Congestión Estado sostenido de sobrecarga de una red
donde la demanda de recursos (enlaces y buffers) se encuentra al
límite o excede la capacidad de los mismos.
11 Congestion vs. Flow Control Los mecanismos de control de la
Congestión deberían poder evaluar la capacidad de
la subnet para transportar determinado tráfico.
Congestión es una cuestión global involucra todos
los hosts y routers Flow control : controla tráfico
point-to-point entre un receptor y un transmisor
(supercomputadora – PC sobre fibra)
12 Métricas Varias métricas podría usar para
detectar congestión % de paquetes descartados por falta de
espacio en buffer Longitud media de una cola ( buffer) # paquetes
que generan time out y son RTX average packet delay standard
deviation of packet delay En todos los casos el crecimiento de
alguna de esta metricas indican congestion
13 Politicas que influyen en la congestion
14 Causas Inundo con trafico destinado a una misma línea
de salida (la cola se llena – tail drop ) Mas Memoria no
necesariamente resuelve el problema Procesadores lentos, o
problemas con software de ruteo Partes del Sistema ( varias
líneas rápidas y una lenta ) Congestión
tiene a realimentarse y empeorar
15 Consideraciones Control de Congestión: Es el esfuerzo
hecho por los nodos de la red para prevenir o responder a
sobrecargas de la red que conducen a perdidas de paquetes. Los
dos lados de la moneda Pre-asignar recursos (ancho de banda y
espacio de buffers en routers y switches) para evitar la
congestión Controlar la congestión si ocurre (y
cuando ocurra) Objetivo: asignar los recursos de la red en forma
“equitativa”; es decir cuando haya problemas
compartir sus efectos entre todos los usuarios, en lugar de
causar un gran problema a tan solo unos pocos. (Gp:) Destination
(Gp:) 1.5-Mbps T1 link (Gp:) Router (Gp:) Source (Gp:) 2 (Gp:)
Source (Gp:) 1 (Gp:) 100-Mbps FDDI (Gp:) 10-Mbps Ethernet
16 Consideraciones (cont) Control de flujo v/s control de
congestión: el primero previene que los transmisores
sobrecarguen a receptores lentos. El segundo evita que los
transmisores sobrecarguen el interior de la red. Dos puntos para
su implementación maquinas en los extremos de la red
(protocolo de transporte) routers dentro de la red (disciplina de
encolado, RED , etc ) Modelo de servicio de los niveles
inferiores best-effort o mejor esfuerzo (lo asumimos por ahora).
Es el servicio de Internet. múltiples calidades de
servicio QoS . Por ejemplo ancho de banda (para video streaming
bajo) y retardo (para Voz sobre IP VoIP).
17 Marco de trabajo En redes orientadas a conexión. Se
reserva ancho de banda y espacio al establecer la
conexión. => Subutilización de recursos. Flujos
de datos en redes sin conexión (datagramas : Internet)
secuencia de paquetes enviados entre el par fuente/destino
mantenemos soft-state en el router Taxonomía Centrado en
router versus centrado en los hosts basados en reservación
versus los basados en realimentación basados en ventanas
versus los basados en tasa de transferencia (Gp:) Router (Gp:)
Source (Gp:) 2 (Gp:) Source (Gp:) 1 (Gp:) Source (Gp:) 3 (Gp:)
Router (Gp:) Router (Gp:) Destination (Gp:) 2 (Gp:) Destination
(Gp:) 1
18 Criterios de Evaluación (1) La idea es que la red sea
utilizada eficientemente y al mismo tiempo en forma equitativa
Buen indicador para eficiencia: Potencia =throughput / retardo
(Gp:) Optimal (Gp:) load (Gp:) Load (Gp:) Throughput/delay Muy
conservativo: Subutilización de recursos Paquetes que
saturan capacidad y colas crecen, crece retardo
19 Criterios de Evaluación (2) Equidad: los recursos sean
compartidos equitativamente. Indicador de equidad de Jain: Dados
n flujos por un enlace (x1, x2, …xn) 0 ? f ? 1
20 Performance de la red en función de la carga (Gp:)
Carga (Gp:) Knee (Gp:) Cliff (Gp:) Carga (Gp:) Knee (Gp:) Cliff
(Gp:) Tiempo de Respuesta (Gp:) Throughput
21 Performance de la red en función de la carga (2) A
medida que la carga (la tasa de datos transmitida) de la red
aumenta, el throughput (tasa de datos que alcanzan el destino) se
incrementa linealmente. Sin embargo, a medida que la carga
alcanza la capacidad de la red, los buffers en los routers
comienzan a llenarse. Esto causa el incremento del tiempo de
respuesta (el tiempo que tardan los datos en atravesar la red
entre el origen y destino) y disminuye el throughput. Una vez que
los buffers de los routers comienzan a sobrecargarse ocurre la
pérdida de paquetes. Incrementos en la carga más
allá de este punto incrementa la probabilidad de
pérdida de paquetes. Bajo cargas extremas, el tiempo de
respuesta tiende a infinito y el throughput tiende a cero; este
es el punto del colapso de congestión. Este punto es
conocido como el cliff debido a la extrema caída en el
throughput.
22 Congestión y Calidad de Servicio Sería muy
fácil dar Calidad de Servicio si las redes nunca se
congestionaran. Para ello habría que sobredimensionar
todos los enlaces, cosa no siempre posible o deseable. Para dar
QoS con congestión es preciso tener mecanismos que
permitan dar un trato distinto al tráfico preferente y
cumplir el SLA (Service Level Agreement). El SLA suele ser
estático y definido en el momento de negociación
del contrato con el proveedor de servicio o ISP (Internet Service
Provider).
23 Carga Rendimiento Sin Congestión Congestión
Fuerte Congestión Moderada Efectos de la congestión
en el tiempo de servicio y el rendimiento Sin Congestión
Congestión Fuerte Congestión Moderada Tiempo de
Servicio Carga QoS útil y viable QoS inútil QoS
inviable QoS útil y viable QoS inútil QoS inviable
Por efecto de retransmisiones Aquí QoS!!
24 Calidad de Servicio (QoS) Decimos que una red o un proveedor
ofrece ‘Calidad de Servicio’ o QoS (Quality of
Service) cuando se garantiza el valor de uno o varios de los
parámetros que definen la calidad de servicio que ofrece
la red. Si el proveedor no se compromete en ningún
parámetro decimos que lo que ofrece un servicio
‘best effort’. El contrato que especifica los
parámetros de QoS acordados entre el proveedor y el
usuario (cliente) se denomina SLA (Service Level Agreement)
25 Calidad de Servicio en Internet La congestión y la
falta de QoS es el principal problema de Internet actualmente.
TCP/IP fue diseñado para dar un servicio ‘best
effort’. Existen aplicaciones que no pueden funcionar en
una red congestionada con ‘best effort’. Ej.:
videoconferencia, VoIP (Voice Over IP), etc. Se han hecho
modificaciones a IP para que pueda funcionar como una red con
QoS
26 Resumiendo Se utiliza el término control de
congestión para describir los esfuerzos que ha de realizar
un nodo de red (ya sea un router o un end-host) para prevenir o
responder a condiciones de sobrecarga. Llegar al punto de la
existencia de congestión es generalmente un mal
síntoma. Por lo cual, es conveniente tomar medidas
preventivas, y no correctivas cuando ya el problema fue
detectado. Una de las posibles soluciones sería
simplemente persuadir a unos pocos hosts que disminuyan el flujo
de tráfico generado, con una consecuente mejora en la
situación del resto de los hosts. Sin embargo, esto lleva
a enviar mensajes de señalización a algunos pocos
hosts, en vez tratar de distribuirla en forma mas equitativa;
obligando así a los mecanismos de control de
congestión a poseer una noción de alocación
de recursos dentro de ellos.
27 Agenda ( 2 Parte) Control de Congestion ( cont.) Taxonomia
Lazo Cerrado-Abierto RED FRED ( optativo)
28 Taxonomia De acuerdo a la taxonomía de Yang y Reddy
(1995), los algoritmos de control de congestión se pueden
clasificar en lazo abierto y lazo cerrado. A su vez los de lazo
cerrado se pueden clasificar de acuerdo a como realizan la
realimentación.
29 Taxonomia [YR95] Control Congestión Lazo Abierto
principalmente en redes conmutacion de circutos (GMPLS) Lazo
Cerrado Usado principalmente en redes de paquetes Usa informacion
de realimentación : global & local
Realimentación Implícita “End-to-end
congestion control” EJ: TCP Tahoe, TCP Reno, TCP Vegas,
etc. Realimentación Explicita “Network-assisted
congestion control” Ej: IBM SNA, DECbit, ATM ABR, ICMP
source quench,, ECN
30 “Congestion Control and Avoidance “congestion
control” : reactivo “congestion avoidance” :
proactivo
31 Feedback Implícito vs. Explicito “Implicit
feedback Congestion Control” “La red dropea”
paquetes cuando ocurre la congestión La fuente infiere la
congestión en forma implícita time-out, ACKs
duplicados, etc. Ej. : CC end-to-end TCP Implementación
relativamente simple , “eficiente” ? Normalmente
Implementada a nivel de transporte (Ej.., TCP, SCTP )
32 Feedback Implícito vs. Explicito (cont.)
“Explicit feedback Congestion Control “ Componentes
de red (Ej., router, sw ) proveen indicación explicita de
la congestión a las fuentes usa “packet
marking”, o celdas RM (en ATM ABR control) Ej. DECbit, ECN,
ATM ABR CC, etc. Provee informacion mas precisa a las fuentes Mas
complicada la implementación Se necesitan cambiar fuente y
algoritmo de red Es necesaria cooperación entre fuentes y
Componentes de red
33 RED
34 RED El algoritmo RED se tiene por objetivo evitar la
congestión y de mantener el tamaño medio de las
colas en niveles bajos. RED no necesita que los routers mantengan
ninguna información del estado de las conexiones. RED fue
diseñado para trabajar en la colaboración con un
protocolo del control de la congestión de la capa de
transporte (TCP, SCTP).
35 Detección aleatoria temprana (Random Early Detection,
RED) Notificación es implícita solo descarta el
paquete (en TCP habrá timeout) podría hacerse
explícita marcando el paquete Descarte aleatorio temprano
en lugar de esperar por que se llene la cola, descarta cada
paquete de entrada con alguna probabilidad de descarte cada vez
que la cola excede algún nivel de descarte
36 Detalles de RED Calcula largo de cola promedio AvgLen = (1 –
Weight) * AvgLen + Weight * SampleLen 0 < Weight < 1
(usualmente 0.002) SampleLen es el largo de la cola cada vez que
un paquete llega (Gp:) MaxThreshold (Gp:) MinThreshold (Gp:) A
(Gp:) vgLen
37 Detalles RED (cont) Dos umbrales de largo de cola if AvgLen
<= MinThreshold then encole el paquete if MinThreshold <
AvgLen < MaxThreshold then calcule probabilidad P descarte
paquete entrante con probabilidad P if ManThreshold <= AvgLen
then descartar paquete entrante
38 Detalles RED (cont) Computo de probabilidad P TempP = MaxP *
(AvgLen – MinThreshold)/ (MaxThreshold – MinThreshold) P =
TempP/(1 – count * TempP) Count cuneta el número de
paquetes encolados mientras el AvgLen está entre los dos
umbrales Curva de probabilidad de descarte (Gp:) P(drop) (Gp:)
1.0 (Gp:) MaxP (Gp:) MinThresh (Gp:) MaxThresh (Gp:) A (Gp:)
vgLen
39 Sintonía en RED Probabilidad de descartar un flujo
particular de paquetes es aproximadamente proporcional a parte
del ancho de banda que el flujo está obteniendo MaxP es
típicamente fijada en 0.02, es decir cuando el
tamaño promedio de la cola es la mitad entre los dos
umbrales, el gateway descarta +o- uno de cada 50 paquetes. Si el
tráfico es rafagoso, entonces MinThreshold debería
ser suficientemente grande para permitir que la
utilización del enlace sea mantenida a un nivel
aceptablemente alto Diferencia entre los dos umbrales
debería ser más grande que el incremento
típico en el largo de cola promedio calculado en un RTT;
fijar MaxThreshold a dos veces MinThreshold es razonable para el
tráfico de hoy en Internet
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN
LA VERSIÓN DE DESCARGA