P4 · rimay: congestión

rimay ya entrega bien, pero no le importa la red: su ventana fija puede ahogar un enlace lento. En esta entrega se agrega control de congestión y se mide su comportamiento. Se usa lo visto en la semana 11. Entrega en la semana 13.

Para empezar

Esta carpeta no trae código de P3: se construye sobre el suyo. Cópienlo una vez, sin tocar la carpeta de origen:

make traer-p3 P3=../ruta/a/su/p3   # copia su src/ y sus tools/; no pisa lo que ya exista

Si falta su P3, make y make test terminan con un mensaje que dice esto mismo. La API de src/rimay.h y el formato de los paquetes no cambian: P5 se apoya en ellos.

Lo que deben agregar

1. Ventana de congestión: enviar min(cwnd, window). La unidad es el byte, y cwnd empieza en 10 paquetes (12 000 bytes). Un SYN o SYN-ACK retransmitido no cambia la ventana.
2. Slow start y congestion avoidance: con ssthresh, como en el RFC 5681. ssthresh empieza muy alto.
   • Debajo de ssthresh, cada ACK nuevo suma min(bytes confirmados, 1200).
   • Desde ssthresh, cada ACK nuevo suma alrededor de 1200 * 1200 / cwnd: un paquete por RTT.
   • Si lo que falta para llenar cwnd es menos de lo que lleva el siguiente paquete, se espera al siguiente ACK. En bytes, cwnd crece de a poco, y sin esta regla cada ACK sacaría un paquete diminuto. La ventana del receptor sí puede cortar un paquete, como en P3.
3. Fast retransmit y fast recovery: al recibir tres ACK duplicados, como en los RFC 5681 y 6582.
   • Un duplicado es un ACK sin datos, con el mismo ack, y con datos en vuelo. La cuenta vuelve a cero con cada ACK nuevo. Con uno o dos duplicados no cambia nada.
   • Con el tercero: ssthresh baja a la mitad de lo que está en vuelo (mínimo dos paquetes), se retransmite el primer byte sin confirmar y cwnd queda en ssthresh más tres paquetes. Cada duplicado más suma un paquete.
   • Un ACK parcial retransmite el siguiente hueco, descuenta de cwnd lo confirmado y no vuelve a reducir.
   • La recuperación termina cuando se confirma todo lo que estaba en vuelo al empezarla. Ahí cwnd baja a ssthresh, o a lo que esté en vuelo más un paquete si es menos: las dos salidas están en el RFC 6582, y las pruebas aceptan ambas. La segunda evita una ráfaga.
4. Timeout: ssthresh baja a la mitad de lo que estaba en vuelo (mínimo dos paquetes), y cwnd vuelve a un paquete. Los duplicados que lleguen hasta confirmar lo que estaba en vuelo no reducen otra vez.
5. Registro: si existe la variable de entorno RIMAY_LOG, cada cambio de cwnd o de ssthresh se escribe en ese archivo como tiempo_ms,cwnd_bytes,ssthresh_bytes.
   • Tres enteros, sin encabezado. tiempo_ms cuenta desde la primera línea, que trae el valor inicial de cwnd.
   • Cada línea se escribe de inmediato, con fflush, y el archivo se reemplaza al abrirlo. Un programa usa un solo archivo, aunque tenga varias conexiones: en las pruebas siempre hay una.
   • Si no se puede abrir, avisen por stderr y sigan sin registro.
6. Un segundo algoritmo: elijan uno y justifiquen la elección (por ejemplo, CUBIC, o uno de su diseño basado en el retardo). Se elige con RIMAY_CC=reno o RIMAY_CC=propio, y sin la variable es Reno. src/cc_propio.c ya trae la elección, y funciones vacías para su algoritmo. Si lo implementan con otras firmas, cámbienlas: las pruebas solo miran la conducta y el registro. El Makefile enlaza con -lm.

La retransmisión de un ACK parcial no pasa por cwnd

Después de un timeout, cwnd es un paquete, pero lo que figura en vuelo es casi toda la ventana anterior. Si el ACK parcial esperara a que hubiera lugar en cwnd, no saldría nada hasta el siguiente RTO, y P3 ya exige que salga de inmediato. Por eso esa retransmisión queda fuera de cwnd, como en NewReno: es un solo paquete por ACK, y ese ACK dice que otros ya salieron de la red. En cambio, los datos nuevos siempre respetan min(cwnd, window).

Reglas que revisan las pruebas

El enlace de las pruebas es de 20 Mbit/s y 40 ms de RTT, con un buffer de 100 000 bytes en el cuello de botella, más o menos un producto ancho de banda por retardo. Sale de tc: un tbf en la salida de r hacia h2, y el retardo en el camino de los ACK. Los flujos parten juntos y se miden pasados los primeros 15 s.

• Todas las pruebas de P3 siguen pasando, con dos ajustes: ver Las pruebas de P3.
• El registro muestra crecimiento exponencial y después lineal, y una reducción a la mitad tras una pérdida.
• Pasado el arranque, usa al menos el 70 % de la capacidad, es decir, 14 Mbit/s de datos.
• Dos flujos de rimay que comparten un cuello de botella llegan a un índice de equidad de Jain mayor o igual a 0,8.
• Un flujo de rimay no se apodera del enlace frente a un flujo TCP con CUBIC: cada uno recibe por lo menos el 20 %.
• Con RIMAY_CC=propio: el archivo llega idéntico, usa al menos el 50 % de la capacidad, cwnd baja alguna vez y crece tras una pérdida si el RTT no cambia, y con un mismo guion de paquetes su ventana difiere de la de Reno en al menos dos paquetes en alguna ronda.
• Un guion paquete por paquete revisa cada regla de la lista de arriba, mirando lo que sale a la red y lo que dice el registro.

Una laptop ocupada puede arruinar una medición. Por eso, si una medición sale mal se repite una vez. Un programa con un error falla las dos.

La solución de referencia, en una laptop con Docker Desktop: 19 Mbit/s pasado el arranque (el 95 %, que es el máximo, porque cada 1200 bytes de datos ocupan 1260 en el cable), Jain de 0,99 entre dos flujos, y entre el 35 % y el 49 % del enlace frente a TCP. Por eso los límites de arriba se pueden cumplir con margen sin ningún truco.

Por qué se mide pasado el arranque

rimay no tiene SACK: cada ACK parcial revela un solo hueco. El primer slow start se pasa de largo, se pierden decenas de paquetes de una sola ventana y se repara uno por RTT. En la referencia, con 20 Mbit/s y 40 ms, esa primera recuperación dura casi 7 s, y en toda una corrida de 30 s el promedio queda en unos 15 Mbit/s. No es un error de su programa, y por eso se mide después. TCP no sufre esto porque tiene SACK. Es una buena pregunta para el informe.

Los buffers de los sockets UDP

No hace falta tocarlos, y las pruebas no los tocan. El buffer de recepción de un socket UDP es de 212 992 bytes (net.core.rmem_max). En el enlace de las pruebas, el contador RcvbufErrors de la referencia quedó en 0, porque el cuello de botella separa los paquetes. Con 100 y 200 Mbit/s no se perdieron datos por esa razón; como mucho, unos cientos de ACK, que el siguiente cubre. Sin cuello de botella, una ventana de cientos de paquetes sí llega de golpe y desborda el socket: es una pérdida más, y cwnd reacciona. Se puede mirar con udp_drops de tests/p4_lab.py, y medir/datos/equidad.csv y algoritmos.csv lo anotan como descartes_udp.

Informe

informe.md, de dos a cuatro páginas, con gráficos generados por sus scripts:

• cwnd en el tiempo, en dos enlaces distintos.
• Throughput y RTT según el tamaño del buffer. ¿Pueden ver el bufferbloat?
• Equidad de rimay consigo mismo y con TCP.
• Comparación entre Reno y su segundo algoritmo, y una opinión sobre cuál elegirían y para qué red.

Las cifras son reales y se pueden volver a generar con make medir (unos 11 minutos): medir/medir.py deja los datos en medir/datos/, y medir/graficar.py hace los gráficos en figuras/. make test revisa que informe.md no tenga partes con [completar] y que sus gráficos existan. Entreguen también medir/datos/ y figuras/.

Las mediciones usan tests/p4_lab.py, que pone el enlace y corre los flujos. Pueden agregar lo que quieran en medir/.

Archivos

Agreguen sus pruebas en archivos test_*.py, en esta misma carpeta: make test las corre al final, con la topología todavía arriba.

Cómo se corren las pruebas

Dentro del contenedor del curso (env/run.sh), desde esta carpeta:

make             # compila en build/
make test        # P4 y P3 completas: levanta la topología, corre todo y la destruye (unos 12 minutos)
make test-p4     # solo P4 (unos 3 minutos): es lo que van a usar mientras trabajan
make test-p3     # solo P3 sobre esta entrega (unos 9 minutos)
make test-local  # solo lo que no usa topología (menos de un minuto)
make clean       # destruye la topología y borra lo generado; no borra medir/ ni figuras/

Para correr una sola prueba mientras trabajan:

make && python3 -m unittest -v p4_public_test.LocalCongestion.test_slow_start_doubles_each_round

La revisión corre make test completo y, además, pruebas privadas con otra topología, otro enlace, otras semillas y otros archivos.

Las pruebas de P3

p3_public_test.py es la misma copia de P3, y p3_en_p4.py la corre con P3_MIN_WINDOW_PACKETS=10 y P3_MAX_WINDOW_PACKETS=874, porque la ventana ya no es fija: esos dos valores los pone el Makefile. Cuatro pruebas de P3 suponen una ventana fija de 64 paquetes, y un programa correcto ya no las puede pasar tal cual. Se cambian solo esas, y siguen revisando lo mismo:

• test_rto_short_rtt, test_rto_follows_long_rtt y test_karn usan un archivo de 100 MB y no de 5 MB. Con slow start y un RTT corto, 5 MB se acaban antes de que se pueda medir el RTO.
• test_all_acks_of_a_window_lost pierde los ACK 5 a 12, y no los ACK 5 a 40. Con cwnd en unos 14 paquetes, no queda nada en vuelo que cubra los otros: cada uno costaría un RTO, y a los 30 s de silencio la conexión se abandona, como manda P3.

Probar a mano

h1 10.94.1.10 ---\
                  r === cuello de botella ===> 10.94.2.10 h2
h3 10.94.3.10 ---/

make topo-up
make enlace ARGS="20 40 100000"     # Mbit/s, RTT en ms, buffer en bytes
make recibir ARGS="9000 copia" &
RIMAY_LOG=cwnd.csv make enviar ARGS="10.94.2.10 9000 archivo"
make sin-enlace

nsenter sirve para gdb, valgrind o tcpdump, como en P3 (clab-p4-rimay-h1 en vez de clab-p3-rimay-h1). Al terminar, make topo-down.

Si una prueba falla

• Falta src/rimay.h. Falta su P3: make traer-p3 P3=../ruta/a/su/p3.
• test_initial_window_is_ten_packets dice que salieron 64 paquetes. Sigue la ventana fija de P3.
• test_partial_ack_reveals_next_hole de P3 falla. Esa retransmisión no debe esperar a cwnd: lean arriba por qué.
• cwnd en el registro llega a cientos o miles de paquetes. Durante una recuperación larga es normal, porque cada duplicado la infla. Al terminar debe bajar.
• Salen paquetes de pocos bytes. Falta esperar al siguiente ACK cuando cwnd no alcanza para un paquete entero.
• Todo pasa a mano, pero el guion falla por poco. Las pruebas de guion confirman cada paquete apenas termina la ráfaga. Revisen que cwnd cambie por cada ACK, y no una vez por ventana.