asignaciÓn de recursos y control de congestiÓn

Diseño de Redes.

ASIGNACIÓN DE RECURSOS Y CONTROL DE CONGESTIÓN

Profesor: Sánchez, José.

Elaborado Por: - Casillas, Reina. - García, Zoraya. - González, Oscarilys. - Mollegas, Teresa. - Linares, María V.

Guacara, Marzo 2009.

Casillas, R.; García, Z.; González, O.; Mollegas, T.; Linares, M. UNITEC I

ÍNDICE GENERAL.

1. Asignación de Recursos. ..................................................................................... 1

1.1. Modelo de Red..................................................................................................... 1 1.1.1. Red de Packet Switching. .............................................................................. 1 1.1.2. Flujos Sin Conexión. ...................................................................................... 2 1.1.3. Modelo de Servicio. ....................................................................................... 3

1.2. Taxonomía de Mecanismos de Asignación de Recursos........................................... 3 1.2.1. Centrado en routers vs. Centrado en host. ..................................................... 3 1.2.2. Basado en reserva vs. Basado en retroalimentación. ....................................... 3 1.2.3. Basado en ventanas o basado en tasas de transmisión.................................... 4

1.3. Criterios de Evaluación. ........................................................................................ 4 1.3.1. Asignación Efectiva. ...................................................................................... 4 1.3.2. Asignación Justa. .......................................................................................... 6

2. Disciplinas de Colas. ........................................................................................... 7 2.1. FIFO. .................................................................................................................. 7 2.2. Encolamiento Justo. ............................................................................................. 8

4. Control de Congestión en el protocolo TCP. ..................................................... 14 4.1. Incremento Aditivo/Decremento Multiplicativo. .................................................... 15 4.2. Partida Lenta ..................................................................................................... 17 4.3. Retransmisión Rápida y Recuperación Rápida ...................................................... 21

Casillas, R.; García, Z.; González, O.; Mollegas, T.; Linares, M. UNITEC 1

1. Asignación de Recursos.

Antes de analizar los diversos mecanismos que se utilizan para la asignación de recursos, veremos algunas denticiones previas:

Asignación de Recursos: Proceso a través del cual un elemento de red busca obtener los recursos necesarios para satisfacer las necesidades de las aplicaciones. Los recursos principales son ancho de banda y buffers en los switches y routers.

Control de Congestión: Es el esfuerzo que realizan los nodos para responder (o prevenir) condiciones de sobrecarga. Normalmente frente a una situación de congestión hay que disminuir el envío de datos. El control de congestión en una red significa una inteligente asignación de recursos.

Control de Flujo: Se diferencia del control de congestión en que el control de flujo

sólo se ocupa de que el transmisor no inunde al receptor, en cambio el control de congestión estudia el efecto agregado de varios transmisores enviando muchos datos a la red.

1.1. Modelo de Red.

Hay tres aspectos de una arquitectura de red que nos interesa repasar: el modelo packet switching, el concepto de flujo de conexión y los modelos de servicio de una red.

1.1.1. Red de Packet Switching. Una red de packet switching consiste en una interconexión de switches o routers a través de enlaces de comunicación. Los enlaces de comunicación en general tienen ancho de banda distintos, lo cual lleva en forma natural a establecer “cuellos de botella” en los nodos. La figura 1 muestra un router congestionado en una red de packet switching.

FIGURA N° 1 Red de Packet Switching.

Fuente: Peterson, L.; Davie, B. (2003).


1.1.2. Flujos Sin Conexión.

Asumiremos el modelo IP, es decir, las redes son esencialmente “sin conexión”. Bajo esta premisa, cualquier servicio con conexión se logra vía protocolos de transporte. Básicamente este es el modelo Internet donde IP provee un servicio sin conexión y es TCP quién implementa una conexión abstracta del tipo end-to-end. Por supuesto que ATM es una alternativa a este modelo. ¿Qué significa “sin conexión"?. Profundizando más en el tema, cada datagrama es despachado en forma independiente, pero en la práctica secuencias de datagramas fluyen por un conjunto particular de routers. Un flujo es entonces una secuencia de paquetes entre un host fuente y un host destino. El concepto es el mismo de \canal", pero los flujos son visibles por los routers en cambio los canales son abstracciones. Como a través de los routers fluyen múltiples flujos, es deseable mantener información de cada uno de ellos con el objeto de tomar decisiones respecto a recursos de red. La información mantenida se denomina “soft state" en contraposición al “hard state" mantenida por switches ATM vía protocolos de señalización. Bajo esta perspectiva, un “soft state” representa un punto intermedio entre un servicio totalmente sin conexión (IP) y uno con señalización como ATM. Hay que tener presente que un flujo no implica ninguna semántica del tipo end-to-end como despacho confiable y orden de paquetes. La figura 2 muestra tres flujos diferentes.

FIGURA N° 2 Flujos.



1.1.3. Modelo de Servicio.

Existe una multiplicidad de modelos de servicios. En un extremo, está el más simple llamado modelo de servicio del tipo \mejor esfuerzo", donde cada paquete es tratado exactamente de la misma manera no permitiendo que los host den ciertas garantías a algunos de sus flujos. En el otro extremo es posible proveer múltiples calidades de servicio (Q o S) como por ejemplo garantizar un determinado ancho de banda a un flujo de video.

1.2. Taxonomía de Mecanismos de Asignación de Recursos. Existen incontables formas a través de las cuales los mecanismos de asignación de recursos difieren. El espacio total es un espacio tridimensional.

1.2.1. Centrado en routers vs. Centrado en host. Los mecanismos de asignación se pueden incorporar tanto al interior de la red, es decir, en routers o switches o en el borde de la red, es decir, en los host y probablemente en los protocolos de transporte. En un esquema basado en routers, cada router toma la responsabilidad de decidir cuándo despachar paquetes y también decidir cuáles paquetes serán descartados. Son los routers quienes informan a los host cuantos paquetes pueden enviar. En un esquema centrado en host, son los host los que observan las condiciones bajo las cuales está operando la red. Podría ocurrir por ejemplo que el host observe muchas pérdidas de paquetes y ajuste su comportamiento acorde a esta información. Se puede observar también que es posible mezclar los dos esquemas.

1.2.2. Basado en reserva vs. Basado en retroalimentación. En un sistema basado en reserva, los host preguntan a la red si dispone de la capacidad requerida en el momento de establecer el flujo. En base a esta pregunta, cada router asigna recursos suficientes para satisfacer el requerimiento. Si algún router no puede satisfacer el requerimiento, el router rechaza el flujo. Bajo un esquema basado en retroalimentación, los host envían datos sin necesidad de reserva, pero ajustan la tasa de envío a la retroalimentación que reciben. Esta retroalimentación puede ser explicita, es decir un router congestionado envía un mensaje que dice “por favor más lento" o implícita en la cual los host observan comportamientos externos de la red como por ejemplo pérdidas de paquetes.


Se puede observar que un esquema basado en reserva siempre implica un mecanismo de asignación centrado en routers.

1.2.3. Basado en ventanas o basado en tasas de transmisión. Esto puede ser confuso en el sentido que se utilizan mecanismos similares tanto para control de flujo como control de congestión. Tanto el control de flujo como los mecanismos de asignación de recursos necesitan formas de indicar al transmisor la cantidad de datos que pueden transmitir. Para esto existen dos mecanismos: ventana o tasa de transmisión. Por ejemplo en TCP, el receptor le anuncia una ventana al transmisor. Esta ventana corresponde al tamaño de buffer que el receptor tiene y por lo tanto establece un límite a los datos que el transmisor le puede entregar. Un mecanismo similar, o sea, el anuncio de ventana, puede ser utilizado en una red para soportar la asignación de recursos (X.25 trabaja con este esquema). Otra estrategia diferente es establecer cuantos bits por segundo el receptor o la red puede absorber. Por ejemplo, el receptor puede ser capaz de procesar video a una tasa de 1 Mbps, y el transmisor se ajusta a ella.

1.3. Criterios de Evaluación. El problema a resolver es la asignación de recursos en forma efectiva y justa. ¿Cuándo es efectiva y justa? Para resolver este problema es necesario establecer métricas que evalúen distintas estrategias de asignación. Examinaremos algunas de estas métricas.

1.3.1. Asignación Efectiva. Las métricas principales de redes son dos: ancho de banda y retardo. Es deseable lograr el mayor ancho de banda con el mínimo retardo. Lamentablemente ambos aspectos son interdependientes ya que para optimizar el ancho de banda se requiere aumentar la capacidad de buffer, y por lo tanto aumentar el retardo. Para describir esta relación se define el concepto de potencia de la r ca en (1). ed como se indi

(1)

Como lo establece la definición 1, mayor potencia significa alto ancho de banda y mínimo retardo, por lo tanto el objetivo es maximizar esta fracción, lo cual se hace operando la red bajo una carga optima. La figura 3 muestra una curva representativa de potencia de una red.


FIGURA N° 3

Ancho de Banda vs. Retardo en función de la carga.


En la práctica es muy difícil operar una red en la zona optima y lo frecuente es operar bajo condiciones de alta carga, es decir al lado derecho de la curva de la figura 3. Una red de comportamiento estable es aquella que continúa operando (no colapsa) aún en condiciones extremas de carga.

1.3.2. Asignación Justa. La asignación de recursos debe hacerse también bajo un criterio de ecuanimidad. ¿Qué significa una asignación justa? Cuando múltiples flujos comparten un mismo enlace de comunicación, es deseable que cada flujo reciba un ancho de banda similar, o sea, bajo esta premisa compartir ancho de banda en forma justa significa distribuir el ancho de banda en partes iguales, sin embargo el tema es más complejo ya que compartir con igualdad no necesariamente significa compartir con justicia. Para ilustrar mejor este punto, consideremos una situación como la mostrada en la figura 4 donde se muestra un flujo que realiza 4 saltos compitiendo por recursos con otros 3 flujos de un salto cada uno. En esta situación. ¿Qué sería favorecer lo justo?


FIGURA N° 4

Un flujo compitiendo con otros tres.


Asumiendo que justicia signifique igualdad y que todas las rutas sean del mismo largo, Raj Jain propuso una métrica que se puede utilizar para cuantificar la justicia de un mecanismo de control. Dado un conjunto de flujos (x1; x2,…, xn) donde xi representa ancho de banda medidos en unidades consistentes (bps). El í dice de justicia se define en la ecuación 2. n

, ,… ∑ ∑

(2)

El índice de justicia siempre resulta en un número que está entre 0 y 1, donde el 1 representa la justicia máxima. Por ejemplo consideremos el caso de n flujos cada uno de ellos recibiendo 1 unidad de datos por segundo. En este caso podemos ver que el índice de justicia es:

1

2. Disciplinas de Colas.

Independientemente del mecanismo de asignación utilizada, cada router debe implementar una disciplina de cola que establezca el criterio de como los paquetes se almacenan mientras esperan ser transmitidos. La disciplina de cola afecta directamente la latencia que experimenta cada paquete. Se analizarán dos disciplinas de colas: FIFO y la llamada “Encolamiento justo".

2.1. FIFO. El primer paquete que llega es el primero en ser transmitido. La figura 5 (a) muestra los espacios libres y ocupados de un buffer FIFO.


FIGURA N° 5

Cola FIFO.


Como el espacio de buffers siempre es finito, si un paquete llega y la cola está llena, el router descarta el paquete tal como se aprecia en la figura 5 (b). La acción de descartar un paquete se realiza sin considerar a cual flujo pertenece el paquete o cuán importante es. Es importante considerar 2 ideas ortogonales detrás de una disciplina FIFO: un aspecto es que FIFO es una disciplina de itineración, es decir, determina el orden en que los paquetes son transmitidos. El otro aspecto es la política de rechazo de paquetes que determina cual paquete será descartado. Actualmente la mayoría de los routers de Internet utilizan este esquema: la consecuencia práctica es que los routers poco tiene que hacer frente a la congestión. Una variación al encolamiento FIFO es incorporar prioridad. La idea es marcar cada paquete con una prioridad. Esta marca puede ir por ejemplo en el campo TOS del datagrama IP. El router siempre transmite paquetes de la cola de mayor prioridad. Se puede apreciar que la mayor dificultad de FIFO con prioridad es que se puede bloquear las demás colas. También es difícil implementar este esquema en un sistema descentralizado como Internet. Actualmente Internet utiliza un esquema de prioridad para proteger los paquetes más importantes como por ejemplo paquetes que transportan información de enrutamiento los cuales son completamente necesarios para estabilizar la red.


2.2. Encolamiento Justo.

Tal como se vio en 2.1, el principal problema de FIFO es que no es capaz de discriminar entre diferentes flujos. Como el mecanismo de control de congestión debe implementarse en los host, FIFO no sirve para controlar como se está comportando la red. En particular, es posible que un determinado flujo se apropie de una fracción importante de la capacidad total de la red. Un ejemplo es un determinado servicio de Internet que no utilice TCP, y por lo tanto, se salte su mecanismo de control de congestión. Podría ocurrir que esta aplicación (por ejemplo telefonía IP) inunde la red con sus propios paquetes descartando paquetes de otras aplicaciones. El Encolamiento Justo sirve para evitar las dificultades de FIFO. La idea esencial es separar en distintas colas cada flujo manejado por el router. El router sirve las colas utilizando un servicio del tipo round-robin, tal como se muestra en la figura 6.

FIGURA N° 6 Encolamiento justo implementado en un error.


Si un flujo es muy rápido, su cola se va a llenar rápidamente y se va a proceder a descartar paquetes. Se logra algo bien importante: ningún flujo puede en forma arbitraria apoderarse de capacidad de red a expensas de otros flujos. La única complicación se produce cuando los paquetes que llegan a las colas tienen largos diferentes. Para asignar ancho de banda al link de salida de una manera “justa”, es necesario tomar en consideración los largos de paquete. Por ejemplo si hay dos flujos cuyos paquetes son de 1000B para el flujo 1 y 500B para el flujo 2; un servicio round-robin asigna 2/3 al flujo 1 y 1/3 del ancho de banda al flujo 2. ¿Cómo evitar esta injusticia? Una forma es modificar el servicio round-robin y hacerlo a nivel de bit, pero evidentemente esto no es factible ya que los bits de diferentes flujos no se pueden entrelazar. El Encolamiento Justo lo que hace es simular el comportamiento de bit estableciendo el orden de despacho de los paquetes si se transmitieran en un orden de bits y posteriormente se utiliza este orden para transmitir los paquetes.


Para entender el algoritmo round-robin utilizado en el Encolamiento Justo, consideremos el comportamiento de un flujo simple e imaginemos un reloj que hace un tick cada vez que se transmite un bit de todos los flujos activos (flujos que tienen datos en la cola). Para este flujo, sea Pi el largo del paquete i, sea Si el tiempo cuando el router comienza a transmitir el paquete i, y sea Fi, el tiempo cuando el router termina de transmitir el paquete i. Si Pi se expresa en terminas de ticks qué toma transmitir el paquete i (no olvidar que el tiempo avanza un tick cuando el flujo avanza 1 bit de servicio), es fácil ver que: Fi = Si + Pi. ¿Cuándo comenzar a transmitir el paquete i? La respuesta depende si el paquete i llegó antes o después que el router terminó de transmitir el paquete i – 1 de su flujo. Si llegó antes, el primer bit del paquete i se transmite inmediatamente después que el último bit del paquete i – 1. Por otra parte, también es posible que el router haya terminado de transmitir el paquete i – 1 mucho tiempo antes que i haya llegado, lo cual significa que existió un periodo de tiempo en el cual la cola para ese flujo estaba vacía, y por lo tanto el mecanismo round-robin no podía transmitir ningún paquete de ese flujo. Si tomamos como Ai el tiempo al cual el paquete llega al router, Si = max ( i – 1 , Ai). Por lo tanto, se puede calcular: entonces F

max ,

(3) Ahora analicemos el caso donde hay más de un flujo y que existe la forma de determinar Ai. No podemos leer el tiempo en el “reloj de la pared” cuando llega un paquete. Como el tiempo avanza un tick toda vez que los flujos activos avanzan un bit de servicio bajo round-robin, lo que se necesita es un reloj que avance más lento cuando hay más flujos. Específicamente, el reloj avanza un tick si se transmiten n bits de n flujos activos. Este reloj se utiliza para el cálculo de Ai. Ahora, de cada flujo se calcula Fi para cada paquete que llega usando la ecuación 3. De esta forma, todos los Fi se tratan como marcas de tiempo, y el siguiente paquete que se trasmite es aquel que tiene la menor marca de tiempo, o sea, el paquete que debería terminar antes que los todos los demás. Se puede observar que si un paquete llega sobre alguno de los flujos, y si es más corto que alguno de otro flujo que está en la cola esperando ser transmitido puede ser insertado en la cola a la cabeza de aquel más largo. Sin embargo esto no significa que un paquete que llegue recientemente pueda interrumpir un paquete que está siendo transmitido. Es precisamente la falta de capacidad de interrupción lo que hace que la implementación del Encolamiento Justo pueda simular un servicio round-robin bit por bit al cual deseamos aproximarnos. Para ilustrar el funcionamiento del algoritmo consideremos el ejemplo que se ilustra en la figura 7. La parte (a) muestra las colas para dos flujos; el algoritmo selecciona los dos paquetes del flujo 1 para transmitirse antes que el paquete que está en la cola del flujo 2. En (b), el router ya comenzó a transmitir un paquete del flujo 2 cuando llega un paquete al flujo 1. Aunque el paquete que llega al flujo 1 podía terminar antes que el del flujo 2 si se pudiera


usar un sistema de cola bit por bit perfecta, la implementación no interrumpe el paquete del flujo 2 que se está transmitiendo.

FIGURA N° 7 Ejemplos de encolamiento justo.


Se puede observar que el link de comunicación nunca estará ocioso si al menos hay un paquete en la cola. La consecuencia es que si se comparte el link de comunicación entre varios flujos que no están enviando datos, el link se utiliza a su máxima capacidad. También se aprecia que si el link está totalmente ocupado y hay n flujos enviando datos, no puedo usar más de 1/n del ancho de banda del link de comunicación. Si existe bajo estas circunstancias un flujo muy activo, lo que puede ocurrir es que sus paquetes se les asignarán marcas de tiempo cada vez más grandes que harán que el paquete deba esperar en la cola para ser transmitido y después de un tiempo los paquetes se descarten porque no hay espacio en esa cola.

3. Control de congestión. Comprende todo un conjunto de técnicas para detectar y corregir los problemas que surgen cuando no todo el tráfico ofrecido a una red puede ser cursado, con los requerimientos de retardo, u otros, necesarios desde el punto de vista de la calidad del servicio. Por tanto, es un concepto global, que involucra a toda la red.


FIGURA N° 8

Congestión en un nodo


3.1. Soluciones. Mecanismos de control de congestión. El problema del control de congestión puede enfocarse matemáticamente desde el punto de vista de la teoría de control de procesos, y según esto pueden proponerse soluciones en bucle abierto y en bucle cerrado.

3.1.1. Soluciones en bucle abierto. También llamadas soluciones pasivas. Combaten la congestión de las redes mediante un adecuado diseño de las mismas. Existen múltiples variables con las que el diseñador puede jugar a la hora de diseñar la red. Estas variables influirán en el comportamiento de la red frente a la congestión. Las resumiremos en función del nivel del modelo OSI al que hacen referencia:

• Enlace

Diseño de temporizadores y política de retransmisiones: Cuando los temporizadores agotan su cuenta, los paquetes afectados serán retransmitidos por la fuente. Si este tiempo es muy pequeño, habrá gran cantidad de retransmisiones. Por el contrario, si es grande, habrá menos congestión, pero el retardo medio aumentará. Además, podemos controlar lo que se retransmite cuando el temporizador se agota (por ejemplo, cuando un paquete es sólo una porción de un mensaje, puede retransmitirse el mensaje entero o sólo el paquete afectado).

Política de descartes y almacenamiento de paquetes que llegan fuera de orden: El rechazo puede ser simple, que origina más retransmisiones, o


bien selectivo, obligando a un almacenamiento temporal de los paquetes que llegan fuera de orden y mejorando la congestión.

Política de asentimientos: El piggybacking, o utilización de parte de un

paquete de datos para enviar asentimientos de paquetes anteriormente recibidos, reduce, en principio, el tráfico, pero puede dar lugar a retransmisiones que contribuyan a la congestión.

Política de control de flujo: Parando a una fuente que vierte mucho tráfico

podemos reducir el riesgo de congestión.

• Red Circuitos Virtuales frente a datagramas: Muchos algoritmos de control de

congestión funcionan sólo en modo circuito virtual.

Política de colas y de servicio: Los router pueden diseñarse con una cola por línea de entrada, una cola por línea de salida, o ambos. Además, puede jugarse con el orden en que los paquetes son procesados, dan do más prioridad a los paquetes de control, que contienen información útil desde el punto de vista de la congestión.

Política de descarte de paquetes: De nuevo, la correcta elección de los paquetes que se descartan puede disminuir el riesgo de congestión.

Algoritmo de enrutamiento: Es bueno desde el punto de vista de la

congestión el balanceo del tráfico entre todas las líneas de la red.

Tiempo de vida de los paquetes: La correcta elección de esta variable permite reducir el número de retransmisiones, mejorando así el comportamiento de la red desde el punto de vista de la congestión.

• Transporte

Análogo al nivel de enlace, pero entre sistemas finales.

3.1.2. Soluciones en bucle cerrado.

También llamadas soluciones activas. Actúan cuando se detectan problemas. Tienen tres fases:

• Monitorización de parámetros. Se vigilan los siguientes parámetros:

Ocupación de los enlaces y de los buffers (colas de espera en los nodos)


Porcentaje de descartes Número de retransmisiones Retardos y "jitters". Jitter: oscilaciones de la separación temporal entre paquetes.

En aplicaciones que requieren sincronización (videoconferencia, sincronizar audio con video), es muy importante que esas oscilaciones sean pequeñas.

• Reacción: envío de información a los puntos necesarios.

La comunicación se realiza gracias a:

Paquetes especiales. NO están sometidos a control de congestión y se saltan las colas de espera en los nodos. Los envía el nodo que, gracias a la monitorización, ha detectado la congestión.

Bits de cabecera. En los paquetes enviados, indico en la cabecera que empieza a haber congestión. (Ejemplo Frame Relay).

Información específica. Si se recibe una alerta de congestión (mediante bits de cabecera de paquetes que circulan por la red), se solicita más información.

• Ajuste del sistema.

Hay varias medidas:

Reducir la velocidad de envío. Control de acceso. No se permiten más conexiones. Tirar paquetes. Controlar ráfagas de paquetes que llegan.

4. Control de Congestión en el protocolo TCP.

Un excelente ejemplo de control de congestión se aprecia en el protocolo TCP. Si bien TCP no utiliza ninguna estrategia de reserva de recursos lo que hace es reaccionar a eventos que pueden ocurrir. Se asume que en los routers, las colas son del tipo FIFO. La idea básica es considerar por separado cada conexión TCP. El lado fuente de la conexión, es decir, el lado que envía datos, debe procurar que los paquetes en tránsito permanezcan en forma segura. Una vez determinado el número de paquetes en tránsito, se utilizan los ACK como señal que indica que un paquete ha abandonado la red y por lo tanto se puede insertar uno nuevo sin aumentar el nivel de congestión. La utilización de ACK para frenar la transmisión de paquetes se puede ver como un “auto-reloj de sincronización”. Como el ancho de banda disponible varia en el tiempo, las fuentes de datos en forma permanente deben ajustar el número de paquetes en tránsito. En las siguientes secciones se describirán algoritmos que se utilizan en TCP para el control de congestión.


4.1. Incremento Aditivo/Decremento Multiplicativo.

Para cada conexión nueva, TCP mantiene una nueva variable de estado. Ésta se denomina CongestionWindows. Esta ventana de congestión es la contraparte de la ventana llamada AdvertisedWindow. TCP se modifica de tal manera, que el número máximo de bytes de datos no reconocidos permitidos es ahora el mínimo entre la ventana de congestión y la ventana de advertencia. Ahora la ventana efectiva se calcula acorde a:

MaxWindow = MIN(CongestionWindow, AdvertisedWindow) EffectiveWindow = MaxWindow - (UBE – UBR) UBE: Último byte enviado UBR: Último Byte Reconocido

Esto significa que la fuente de TCP está restringida al componente más lento que puede ser la red o el host destino. ¿Cómo puede TCP aprender un valor apropiado para la ventana de congestión? En el caso de la ventana de advertencia, ésta es enviada por el extremo receptor de la conexión, pero no existe ningún envío de CongestionWindows. La respuesta es que el extremo fuente de la conexión fija un CongestionWindows basándose en el nivel de congestión que percibe que existe en la red. De esta manera sube y baja el valor de la ventana de congestión. Entonces, ¿cómo el extremo fuente de la conexión determina si la red está congestionada? Simplemente porque hay paquetes que no llegan y actúan los timeout debido a pérdidas por congestión. La consideración es que pérdida de paquetes por errores durante la transmisión son escasos y es raro que ocurra. Cada vez que ocurre timeout, el extremo fuente divide en dos el valor de CongestionWindows. Por esta razón esta técnica se denomina decremento multiplicativo. Si bien es cierto que CongestionWindows está definida en términos de bytes, es más fácil pensar el decremento multiplicativo en términos de paquetes completos. De esta manera si CongestionWindows tiene valor 16 paquetes, al llegar timeout, baja a 8, con un nuevo time out baja a 4 y así hasta 1. En TCP, CongestionWindows no puede ser menor que el tamaño de un paquete, o sea, el MSS (tamaño máximo de segmento). Es necesario incrementar la ventana de congestión cuando existe mayor capacidad en la red. Esto se hace usando el llamado “incremento aditivo” lo cual significa que por cada paquete enviado después del último RTT y que ha sido correctamente reconocido se agrega un paquete a la ventana de congestión. Este incremento lineal se muestra en la figura 8.


FIGURA N° 9

Paquetes en tránsito durante incremento aditivo.

Fuente: Peterson, L.; Davie, B. (2003). Específicamente la ventana de congestión se incrementa de la siguiente manera cada vez que llega un ACK:

Esto significa que en vez de incrementar por un valor entero de MSS en bytes lo incrementa en una fracción. Durante el ciclo de vida de la conexión, este patrón en forma continua se incrementa y decremento. La variación temporal de la CongestionWindows se ve como los dientes de un serrucho, tal como se aprecia de la figura 9.


FIGURA N° 10

Patrón de dientes de serrucho de la ventana de congestión.


La fuente de la conexión puede reducir el tamaño de la ventana en forma mucho más rápida que aumentarla. Esto es importante para la estabilidad del mecanismo de control de congestión. Intuitivamente se puede ver que la consecuencia de tener ventanas grandes de transmisión son peores que ventanas pequeñas, por ejemplo los paquetes descartados son retransmitidos aumentando aún más la congestión.

4.2. Partida Lenta El mecanismo estudiado en el punto 4.1 es útil cuando la fuente de la conexión está operando cerca de la máxima capacidad disponible en la red, pero toma demasiado tiempo cuando se desea levantar una conexión desde cero. Por esta razón TCP provee un segundo mecanismo denominado partida lenta, que se utiliza para aumentar “rápidamente” la ventana de congestión desde una partida en frio. Irónicamente se denomina partida lenta. La partida lenta incrementa la ventana de congestión exponencialmente en vez de linealmente. La fuente de la conexión comienza fijando la ventana de congestión a un paquete. Al llegar el ACK de este paquete, TCP le suma 1 a la CongestionWindow y envía dos paquetes. Una vez recibido los ACK correspondientes, TCP incrementa en 2 por cada paquete, es decir envía 4 paquetes. El resultado es doblar el número de paquetes en tránsito en cada RTT. La figura 10 muestra el crecimiento en el número de paquetes en tránsito durante la partida lenta.


FIGURA N° 11

Paquetes en tránsito en una partida lenta.


Entonces, ¿por qué se denomina “partida lenta”?. La respuesta está en la historia. No se compara con el mecanismo de incremento lineal visto en 4.1, sino en los orígenes de TCP. ¿Qué pasa cuando se establece una conexión, no hay paquetes en tránsito y la fuente comienza a enviar paquetes? Si el extremo fuente de la conexión envía tantos paquetes como lo permite la ventana de advertencia – exactamente lo que se hacía en la antigüedad – los routers no son capaces de consumir la avalancha de paquetes que llegan y todo va a depender de la capacidad de buffers disponibles en los routers. Por esto la partida lenta está diseñada para espaciar paquetes de forma tal que no ocurra un peak muy alto de paquetes en un determinado momento. En otras palabras este mecanismo es más lento que enviar un número de paquetes dado por la ventana de advertencia. Existen dos situaciones diferentes a través de las cuales se puede iniciar una “partida lenta”. Primero, al comienzo de una conexión; segundo cuando la conexión se congela a la espera de un timeout (recordemos que los ACK actúan como “clock" de transmisión). Eventualmente llega el timeout, pero a estas alturas no hay paquetes en tránsito, lo cual significa que el extremo fuente de la transmisión no ha recibido ACK para enviar nuevos paquetes. En vez de


esto, la fuente recibe un ACK acumulativo que reabre la ventana de advertencia completa, pero la fuente utiliza la partida lenta para restablecer el flujo de datos. Aunque el extremo fuente de la conexión utiliza una vez más la partida lenta, esta vez dispone de mayor información que al principio. En particular dispone del valor actualizado de CongestionWindow. Este valor corresponde al valor anterior de la última pérdida de paquetes dividido por 2 como resultado de la pérdida. Se podría pensar que este valor es el “blanco”, o sea, el valor al cual debe converger la CongestionWindow y la partida lenta permite llegar en forma rápida a este valor (aunque parezca contradictorio con el nombre). Aparece un nuevo problema: ¿cómo diferenciar la CongestionWindow actual, del valor estacionario anterior que se desea lograr? Para esto TCP introduce una variable temporal para almacenar la CongestionWindow “blanco” resultado del decremento multiplicativo del valor actual. Esta nueva variable se llama CongestionThreshold y es inicializada con el valor de CongestionWindow resultado del decremento multiplicativo. La variable CongestionWindow se inicializa con 1 paquete y se duplica por cada ACK recibido (partida lenta) hasta llegar al valor de CongestionThreshold a partir del cual se incrementa en un paquete por cada RTT (Incremento Aditivo/Decremento Multiplicativo). La figura 11 muestra como la variable CongestionWindow varía en el tiempo e ilustra la interacción entre la partida lenta y el mecanismo de incremento aditivo/decremento multiplicativo.

FIGURA N° 12 Comportamiento del control de congestión TCP.

Fuente: Peterson, L.; Davie, B. (2003). El la figura 11, los puntos negros representan timeouts. Las barras verticales cortas sobre el grafico representan los tiempos en los cuales cada paquete es transmitido. Las barras verticales largas representan los tiempos en los cuales un paquete que será eventualmente retransmitido fue transmitido por primera vez. La primera observación es el rápido crecimiento de la ventana de congestión al comienzo de la conexión. Esta etapa corresponde a la fase “partida lenta”. La fase de “partida lenta” continúa hasta que se pierden varios paquetes lo cual ocurre 0.4 segundos después del inicio de la conexión, y a partir de este tiempo, la CongestionWindow queda constante con un valor


de 34KB. La ventana de congestión tiene un comportamiento plano debido a que no llegan ACK debido a la pérdida de paquetes. A los 2 segundos del comienzo ocurre time out y la ventana de congestión se divide por 2 y la variable CongestionThreshold almacena este valor. El mecanismo “partida lenta” hace que se fije el valor de la variable CongestionWindow a un paquete y se comience a subir nuevamente. ¿Qué pasa cuando un par de paquetes se pierden justo después de 2 segundos? A partir de ahí se salta a incremento aditivo en la ventana de congestión lo cual ocurre entre 2 y 4 segundos. A los casi 4 segundos, la CongestionWindow se aplana nuevamente debido a las pérdidas de paquetes. Ahora un nuevo evento ocurre a los 5.5 segundos:

1. Se genera un time out, cuyo efecto es dividir por 2 la ventana de congestión, cayendo de 22KB a 11KB. La CongestionThreshold se fija a este valor.

2. La CongestionWindow se fija a 1 paquete. El transmisor entra en “partida lenta”.

3. La partida lenta hace que CongestionWindow crezca exponencialmente hasta llegar a CongestionThreshold.

4. A partir de ahí, CongestionWindow crece linealmente.

El mismo patrón se vuelve a aplicar a los 8 segundos al ocurrir otro time out. ¿Por qué se pierden muchos paquetes en el periodo inicial de la “partida lenta”?. Lo que TCP trata de hacer es saber cuándo ancho de banda hay disponible en la red. Si el transmisor no fuera muy agresivo en esta etapa – por ejemplo, si la ventana de congestión creciera linealmente – tomaría demasiado tiempo averiguarlo, lo cual podría tener un impacto negativo en el troughput de la conexión. Por otro lado, al crecer exponencialmente la ventana de Congestión del transmisor asume el riesgo de perder la mitad de los paquetes de la ventana en la red. Para analizar con más profundidad lo que ocurre durante el crecimiento exponencial consideremos la situación en la cual el transmisor es capaz de sólo enviar 16 paquetes exitosamente a través de la red, con el efecto de doblar la ventana de congestión a 32. Pero supongamos que la red sólo tiene capacidad para soportar 16 paquetes de esta fuente de datos. El resultado probable es que 16 de los 32 paquetes enviados bajo la nueva ventana de congestión se pierdan. Estrictamente este es el peor caso ya que algunos paquetes quedarán en buffers de algunos routers. Este problema se vuelve más severo en la medida que el producto retardo x ancho de banda aumenta. Por ejemplo un producto retardo x ancho de banda de 500KB significa que potencialmente cada conexión puede perder hasta 500KB de datos al comienzo de la conexión.


4.3. Retransmisión Rápida y Recuperación Rápida

El mecanismo descripto hasta aquí fue parte de la propuesta original de agregar a TCP control de congestión. La experiencia mostró que la implementación de timeout lleva a largos periodos de tiempo durante el cual la conexión va a morir mientras espera que expire el timer. Debido a esto se agregó a TCP un nuevo mecanismo llamado Retransmisión Rápida. La retransmisión rápida es una heurística que algunas veces dispara la retransmisión de paquetes perdidos en forma más rápida que el mecanismo de timeout regular. La retransmisión rápida no reemplaza los timeout regulares, sólo mejora su aplicabilidad. La idea es simple. Cada vez que llega un paquete al receptor, éste responde con un ACK, aún cuando el número de secuencia ha sido reconocido. Entonces, cuando un paquete llega fuera de orden, es decir, TCP no puede reconocer el dato que contiene el paquete porque datos anteriores aún no han llegado, TCP reenvía el mismo ACK que envió la _ultima vez. Esta segunda transmisión del mismo ACK se denomina ACK duplicado. Cuando el lado transmisor ve el ACK duplicado, sabe que el otro lado ha recibido un paquete fuera de orden, lo que le sugiere que un paquete enviado con anterioridad se perdió. Como también es probable que ese paquete no se haya perdido sino que esté atrasado, el transmisor espera la llegada de otros ACK duplicados antes de retransmitir el paquete perdido. En la práctica espera sólo hasta tres. La figura 12 muestra como los ACK duplicados llevan a una rápida retransmisión. En el ejemplo que se muestra, el receptor recibe los paquetes 1 y 2, pero el paquete 3 se pierde en la red. Frente a esto, el receptor, duplica el ACK del paquete 2 al llegar el paquete 4, y nuevamente al llegar el paquete 5 y así sucesivamente en vez de enviar el ACK de cada paquete. Cuando el transmisor observa el tercer duplicado para el paquete 2, retransmite el paquete 3. Ahora al llegar una copia del paquete 3, el receptor envía el ACK acumulativo incluido el paquete 6 al transmisor.


FIGURA N° 13

Retransmisión rápida basada en duplicación ACK.

Fuente: Peterson, L.; Davie, B. (2003). La figura 13 muestra el comportamiento de la versión de TCP que ahora incorpora el mecanismo de retransmisión rápida. Es ilustrativo comparar con el comportamiento de TCP mostrado en la figura 11 donde esta opción no está implementada.

FIGURA N° 14 Comportamiento de TCP con Recuperación Rápida.

Fuente: Peterson, L.; Davie, B. (2003). Se aprecia en 13 que el largo periodo donde la ventana permanecía plana y no se enviaban paquetes ahora se elimina. En general, esta técnica es capaz de eliminar cerca de la mitad de los timeout de “grano grueso” de una conexión típica TCP, resultando en una mejora del 20% en desempeño.


Se puede ver también que la estrategia de retransmisión rápida no elimina todos los timeouts de “grano grueso”. En efecto, para tamaños de ventana pequeños, no hay suficientes paquetes en tránsito para producir suficientes duplicados de ACK. Dada una pérdida de paquetes suficiente, por ejemplo durante la fase inicial de la partida rápida, el algoritmo de ventana deslizante eventualmente bloquea el transmisor hasta la ocurrencia de timeout. Dado el máximo de 64MB de tamaño de ventana que se puede advertir, en la práctica TCP es capaz de detectar hasta 3 paquetes perdidos. Finalmente es posible introducir una nueva mejora. Cuando el mecanismo de retransmisión rápida señala congestión, en vez de contraer la ventana de congestión a 1 paquete y correr la partida lenta, es posible usar el ACK que todavía está en la red para gatillar el envío de paquetes. Este mecanismo llamado recuperación rápida, efectivamente elimina la fase de “partida lenta” que ocurre cuando la retransmisión rápida detecta un paquete perdido y comienza el incremento aditivo. Por ejemplo, la recuperación rápida evita el periodo de “partida lenta” entre los segundos 3.8 y 4 tal como se aprecia en la figura 13 y en vez de eso corta la ventana de congestión a la mitad (de 22 KB a 11 KB) y continúa con el incremento aditivo. En otras palabras, la “partida lenta” es sólo usada al comienzo de una conexión y toda vez que ocurre un timeout de “grano grueso”. En cualquier otra oportunidad, la ventana de congestión sigue un patrón marcado sólo por incremento aditivo/decremento multiplicativo.

asignaciÓn de recursos y control de congestiÓn

Documents