Apunte de Control de Congestión (Teoría de las Comunicaciones)
Control de congestión
Taxonomía de mecanismos de reserva de recursos
Router-Céntricos vs. Host-Céntricos
En el primer caso, cada router se encarga de seleccionar que paquetes se forwardean y cuáles se dropean, y de informar a los hosts cuántos paquetes se les permite enviar.
En el segundo caso, los hosts observan las condiciones de la red y ajustan su comportamiento acorde a eso.
Basados en reservas vs. basados en feedback
En los primeros, el host le pide a la red cierta cantidad de capacidad al tiempo que se establece un flujo. Cada router entonces reserva recursos para satisfacer este pedido. Si el pedido no puede ser satisfecho en algún router, el router rechaza el flujo. Esto es análogo a recibir una señal de "ocupado" cuando llamamos por teléfono.
En los segundos, el host empieza a enviar datos sin hacer reservas previamente y luego ajustan su frecuencia de envío de acuerdo al feedback que reciben. Este feedback puede ser explícito (el router envía un mensaje "bajá un cambio" al host) o implícito (el host se ajusta a partir del comportamiento que observa de la red, por ejemplo la pérdida de paquetes).
Cabe destacar que un sistema basado en reservas siempre implica un mecanismo router-céntrico. Esto se debe a que cada router es responsable de controlar cuánto de su capacidad fue reservado, y que cada host esté usando lo que pidió reservar.
Basados en ventanas vs. basados en rate
No hay mucho por aclarar en este caso. En el caso de los basados en ventanas, el receptor indica cuántos datos puede bufferear, y en el segundo caso lo que indica es un rate en bits por segundo.
Resumen de taxonomía
Si bien estas tres dimensiones de dos valores cada una definirían 8 tipos de servicios distintos, en la práctica son sólo 2 las que prevalecen.
Por un lado, un modelo de servicio best-effort (donde cada paquete es tratado igualitariamente) usualmente implica que se utilice feedback, ya que no se permite que el usuario haga reservas sobre la red. Esto a su vez implica que la mayor responsabilidad del control de congestión recae sobre los hosts, y en la práctica este tipo de red usan ventanas en vez de rates. Este es el caso general de Internet.
Por otro lado, un modelo de servicio QoS probablemente implemente algún tipo de reserva. Soportar este servicio en general requiere participación del router para tratar diferencialmente a paquetes provinientes de distintos flujos. Además, es natural expresar las reservas en términos de rates, ya que las ventanas están indirectamente reacionadas a las necesidades de ancho de banda de un usuario.
Criterio de evaluación
Reserva efectiva de recursos
Considerar las dos métricas principales en lo que respecta redes: throughput y delay. Queremos lo máximo de throughput y lo mínimo de delay posible.
Una manera de subir el throughput es permitir todos los paquetes que sean posibles en la red, para exprimir al máximo cada enlace. Pero incrementar la cantidad de paquetes en la red también alarga las colas en cada router, y esto implica que los paquetes sufren de un mayor delay en la red.
Para describir esta relación, se propuso la unidad "Power" donde:
Power = Throughput / Delay
El objetivo será maximizar este ratio, que es una función de la carga que ubicamos en la red.
Reserva "justa" de recursos
Salvo información explícita en contrario, cuando muchos flujos comparten un enlace en particular, vamos a querer que cada flujo reciba una porción igual del ancho de banda. Con esta definición estamos asumiendo que una porción "justa" es una porción "igualitaria", pero incluso en un sistema sin reservas, esto puede no ser así. No deberíamos considerar también la longitud de los paths que los flujos deben recorrer?
Un tal Raj Jain propuso una métrica suponiendo porción justa = porción igualitaria. Dados x1,...,xn throughputs de n flujos, la métrica consiste en tomar el cociente del cuadrado de la sumatoria de x1,...,xn sobre la sumatoria de los mismos elementos al cuadrado multiplicada por n (si alguien quiere poner la fórmula, bienvenido sea).
Disciplinas de Queuing
FIFO o FCFS
Lo usual, el primero que llega es el primero que se va. Si la cola se llena, los mensajes que lleguen serán descartados. A esto último se lo llama tail drop.
Igualmente no debe pensarse que siempre que se hace FIFO se hace tail drop. FIFO es una disciplina de scheduling (determina el orden en que los paquetes se forwardean) y tail drop es una política de descarte. A la combinación FIFO-tail drop se la llama vanilla queuing.
Vanilla queuing es el más usado en los routers de Internet. Esto significa que el control de congestión en Internet actualmente recae principalmente en TCP.
Una variación simple de FIFO es usar colas de prioridad. La idea es marcar cada paquete con una prioridad, que podría ir por ejemplo en el campo Type of Service (TOS) de IP. Los routers entonces implementan una cola para cada prioridad, dando siempre a las de mayor prioridad la oportunidad de vaciarse antes que las de menor prioridad. Dentro de una misma prioridad, el criterio sigue siendo FIFO.
El problema de las colas de prioridad, como ya vimos en Sistemas Operativos, es que pueden provocar inanición de las colas de menor prioridad.
Una situación típica en que se usan las colas de prioridad en Internet es para proteger los paquetes más importantes, como las actualizaciones de routeo que estabilizan las tablas de routeo luego de un cambio de topología. Generalmente hay una cola especial para esos paquetes, identificados por el TOS de IP.
Fair queuing
La idea de fair queuing es mantener una cola separada para cada flujo manejado por el router. Luego el router utiliza round-robin para enviar un paquete de cada cola a la vez. Cuando un flujo manda paquetes demasiado rápido, su cola se llena, y se empieza a descartar mensajes. De esta forma, un flujo no puede abusar de los recursos de la red en detrimento de otros.
A pesar de la simpleza de esta idea, hay más detalles a tener en cuenta. Por ejemplo, la longitud de los paquetes que está enviando un flujo. Si tenemos dos flujos, uno que envía paquetes de 1000 bytes y otro 500 bytes, hacer un simple round-robin va a redundar en que el primero tendrá 2 tercios del ancho de banda y el segundo sólo un tercio.
Lo que en realidad queremos un round-robin bit a bit. Lo que hace el mecanismo FQ es estimar cuándo un paquete terminaría de ser transmitido si se usara round-robin bit a bit, y usar ese momento como número de "secuencia" de los paquetes para transmisión.
Notar que el mecanismo no simula un bit a bit perfecto. Supongamos que empezamos a enviar un paquete de 10 bits de un flujo A, y llega un paquete de 2 bits de un flujo B. En un mecanismo bit a bit, el paquete del flujo de B terminaría de ser enviado antes del paquete del flujo A, sin embargo esto no ocurre, el paquete de 10 bits es enviado entero y después ocurre lo mismo con el de 2 bits.
Hay 2 cosas a notar sobre FQ: el link nunca deja de estar activo mientras haya algún paquete en alguna cola. A esta propiedad se la denomina work-conserving. Esta propiedad es deseable, ya que implica que si estoy compartiendo un enlace con flujos que no están enviando datos, puedo aprovechar toda la capacidad para mi propio flujo. La otra cosa a notar es que si el enlace está a pleno con n flujos enviando datos, no puedo usar mas que un n-avo del ancho de banda. Si trato de enviar más, mis paquetes serán scheduleados para más tarde.
Existe una variación de FQ llamada WFQ (la W es por weighted) que permite asignar un peso a cada flujo. Este peso especifica cuántos bits se mandan cada vez que el router le da el turno a ese flujo.
Control de congestión de TCP
Incremento aditivo / Decremento multiplicativo
TCP mantiene un nueva variable de estado para cada conexión, llamada CongestionWindow, que es utilizada por la fuente para limitar cuántos datos se puede tener en tránsito en un momento dado. Con esto, TCP se modifica de tal forma que el máximo número de bytes no ackeados es el menor entre la CongestionWindow y AdvertisedWindow (recordar ventana deslizante en TCP).
MaxWindow = MIN(CongestionWindow, AdvertisedWindow) EffectiveWindow = MaxWindow - (LastByteSent - LastByteAcked)
El host fuente en TCP setea un valor de CongestionWindow basado en el nivel de congestión que percibe en la red. Esto implica bajar la ventana de congestión cuando el nivel de congestión sube y vice-versa.
El host fuente se da cuenta de que la red está congestionada a partir de la observación de que la principal razón por las que los paquetes no llegan y dan timeout, es que fueron dropeados por congestión. TCP interpreta los timeouts como señales de congestión. Específicamente, cada vez que ocurre un timeout, la fuente setea CongestionWindow a la mitad de su valor anterior. De ahí el "decremento multiplicativo".
La ventana de congestión no puede bajar a menos del tamaño de un sólo paquete, lo que en la terminología se denomina maximum segment size (MSS).
La política para incrementar CongestionWindow es la siguiente. Cada vez que el equivalente a una CongestionWindow es ackeado exitosamente, se incrementa el valor de CongestionWindow en el equivalente a 1 paquete. En la práctica, lo que ocurre en realidad es que TCP incrementa CongestionWindow un poquito cada vez que un único ACK llega:
Increment = MSS x (MSS/CongestionWindow) CongestionWindow += Increment
Slow Start
El mecanismo anterior está muy bien cuando la conexión ya está en un régimen regular, pero es un bajón cuando arranca hacer incremento lineal de la ventana, ya que la conexión tarda mucho en aprovechar los recursos de la red. Es por esto que se usa el mecanismo paradójicamente llamado Slow Start para incrementar la ventana de congestión rápidamente al iniciar la conexión. Con Slow Start, la ventana de congestión se incrementa exponencialmente en vez de linealmente.
La fuente empieza seteando CongestionWindow a un paquete. Cuando llega el ACK, CongestionWindow se incrementa en uno. Cuando llegan los 2 ACKs, se incrementa en 2 y así sucesivamente, duplicando el tamaño de la ventana a cada RTT.
Hay dos situaciones en las que actúa slow start. La primera es la que ya comentamos, al inicio de la conexión. CongestionWindow se incrementa exponencialmente hasta que obtiene un timeout, y entra en la fase "Incremento aditivo / Decremento multiplicativo".
La otra situación es cuando la conexión se muere esperando que ocurra un timeout. Cuando el timeout ocurre, en vez de transmitir utilizando toda la advertised window, se vuelve a utilizar slow start, como si la conexión recién se estableciera.
Si bien en esta situación volvemos a usar slow start, tenemos un valor de CongestionWindow que nos da algo más de información sobre el estado de la red que si recién empezáramos. Lo que se hará entonces es usar ese valor de CongestionWindow como valor "objetivo" del mecanismo slow start. Se incrementará exponencialmente hasta llegar a ese valor, y a partir de allí se volverá a utilizar incremento aditivo, sin esperar a obtener un timeout para hacer este switch de mecanismo. Como ahora además de CongestionWindow tenemos un valor objetivo para recordar, TCP introduce una nueva variable temporal, llamada CongestionThreshold.
Fast Retransmit y Fast Recovery
Fast retransmit es una heurística que a veces dispara la retransmisión de un paquete dropeado antes que el mecanismo regular de timeout de TCP. Fast retransmit no reemplaza dicho mecanismo, sólo intenta mejorarlo cuando es posible.
Cada vez que un paquete llega, el receptor envía un ACK, incluso si ya envió el número de ACK correspondiente al paquete que llegó. Entonces, cuando llega un paquete fuera de orden, se envía el último ACK nuevamente. A este nuevo ACK se lo denomina ACK duplicado. Cuando el emisor recibe un ACK duplicado, se da cuenta de que del otro lado llegó un paquete fuera de orden, lo que sugiere que un paquete anterior se pudo haber perdido. Como el paquete puede estar demorado en vez de perdido, el emisor espera a recibir un par de ACKs duplicados más y entonces retransmite el paquete supuestamente perdido. En la práctica, TCP espera 3 ACKs duplicados para retransmitir.
Cuando el mecanismo de fast retransmit detecta congestión, en vez de volver a la etapa de slow start, se puede utilizar los ACKs que están en el pipe para tomarle el tiempo al envío de paquetes. A esto se lo llama fast recovery. Cuando se dispara este mecanismo, se recorta la ventana de congestión a la mitad y se vuelve a la etapa de incremento aditivo.
