P3 · rimay: entrega confiable

rimay (“hablar” en quechua) es un protocolo de transporte confiable sobre UDP, escrito en C. En esta entrega se ocupa de que los bytes lleguen completos y en orden sobre una red mala. Se usa lo visto en las semanas 9 y 10. Entrega en la semana 11.

Formato de cada paquete

Todos los campos van en orden de red. El encabezado mide 18 bytes, sin relleno: ojo con sizeof de un struct, que puede dar 20. Cada paquete lleva como máximo 1200 bytes de datos.

Reglas de cada campo:

• SYN y FIN ocupan un número de secuencia cada uno. Los datos empiezan en ISN + 1, y el FIN va justo después del último byte.
• Solo DATA lleva datos. Todo paquete lleva ack y window, salvo el SYN, cuyo ack es 0.
• Un paquete se descarta sin responder si: mide menos de 18 bytes, su checksum falla, flags no es 0, type es desconocido, length no coincide con el tamaño del datagrama, length pasa de 1200, o trae datos sin ser DATA.
• Un ack de algo que nunca se envió se ignora.

La biblioteca

int rimay_listen(uint16_t port);                         // socket para esperar conexiones
int rimay_accept(int listener);                          // espera un cliente
int rimay_connect(const char *host, uint16_t port);      // abre una conexión
ssize_t rimay_send(int conn, const void *buf, size_t n); // bloquea hasta aceptar n bytes
ssize_t rimay_recv(int conn, void *buf, size_t n);       // 0 si el otro extremo cerró
int rimay_close(int conn);                               // termina con FIN y libera todo

Los detalles están en src/rimay.h, que no se modifica:

• Los int son identificadores de la biblioteca, no descriptores: no sirven con poll.
• Los errores devuelven -1 con errno: EBADF (identificador inválido), ETIMEDOUT (abandono), EPIPE (rimay_send después de que el otro cerró) y EINVAL (argumentos inválidos).
• rimay_send vuelve cuando copió los bytes, no cuando los confirmaron. De eso se ocupa rimay_close: vuelve con 0 solo si se confirmaron todos los datos y el FIN.
• Un listener atiende a varios clientes, distinguidos por dirección y puerto. Todos los paquetes de esas conexiones salen del puerto del listener.
• Conexiones distintas se usan a la vez desde hilos distintos, y en una misma conexión un hilo puede enviar mientras otro recibe. P5 se apoya en esto.
• rimay_connect acepta direcciones IPv4 y nombres. Solo IPv4.

Con eso armen rimay_send_file <host> <puerto> <archivo> y rimay_recv_file <puerto> <archivo>. El segundo espera un solo cliente. Ambos terminan con 0 si todo salió bien, y con otro código y un mensaje en stderr si no.

Sugerencia de diseño: los ACK, los temporizadores y las sondas tienen que funcionar aunque la aplicación no esté llamando a la biblioteca, por ejemplo mientras no lee. La forma simple es un hilo que atiende los sockets con poll. El Makefile ya compila con -pthread.

Pensando en P4: dejen en una sola función la cuenta de cuántos bytes se pueden enviar, porque ahí entrará cwnd. Y no guarden nada indexado por “paquete módulo 64”.

Lo que debe cumplir

• Conexión: handshake de tres pasos, número de secuencia inicial aleatorio y cierre con FIN.
  • Si se pierde el último ACK, un DATA o un FIN que confirme el SYN-ACK también completa el handshake.
  • Un SYN repetido recibe de nuevo el SYN-ACK, y un SYN-ACK repetido recibe de nuevo el ACK.
  • Cada extremo envía su FIN al llamar a rimay_close, después de enviar todos sus datos. Después de rimay_close no se lee más, así que un FIN del otro extremo significa que ya no leerá. Si los dos FIN se cruzan, cada extremo sigue retransmitiendo el suyo hasta que lo confirmen.
  • Quien cierra primero espera al menos 1 s después de confirmar el FIN del otro, para volver a confirmarlo si se perdió su ACK.
• Ventana deslizante: ventana fija de 64 paquetes (76 800 bytes en vuelo), con ACK acumulativo. Recordar los paquetes que llegan fuera de orden es obligatorio. El receptor responde con un ACK a cada DATA y a cada FIN válidos, también si son duplicados, están fuera de orden o quedan fuera de la ventana. Un FIN con un hueco antes no se da por recibido.
• Retransmisión: RTO calculado como en el RFC 6298, con retroceso exponencial y el algoritmo de Karn, con estos valores: inicial de 1 s, mínimo de 200 ms y máximo de 10 s. El RFC recomienda un mínimo de 1 s y pide un máximo de al menos 60 s. Aquí el mínimo es menor para que cada pérdida cueste menos. El máximo sale de medir la solución de referencia con 1 MB y todas las fallas juntas: con 10 s, las 25 corridas terminaron bien en menos de 3 minutos; con 60 s, 7 de 25 fallaron o no terminaron en 15 minutos.
  • Un timeout retransmite el primer byte sin confirmar.
  • Después de un timeout, un ACK parcial, que avanza pero no llega a lo que estaba enviado, dice dónde está el siguiente hueco: se retransmite de inmediato. Sin SACK, la alternativa es esperar un RTO por cada hueco, mucho más lento.
  • Un ACK que cubre algo retransmitido no sirve como medición (Karn), y el retroceso se queda hasta tener una medición válida.
  • Conviene recordar el momento de envío de cada paquete en vuelo, y medir con el más nuevo que confirme cada ACK. Cronometrar solo uno a la vez deja muy pocas mediciones.
• Integridad: un paquete con checksum incorrecto se descarta.
• Control de flujo: nunca enviar más allá de ack + window. El buffer del receptor mide entre 64 paquetes y 4 MiB. Con la ventana en cero, y nada en vuelo, se envía cada cierto tiempo una sonda: un DATA de largo 0 con el seq del siguiente byte. La sonda no consume números de secuencia y se responde con un ACK. Sin ella, si se pierde el ACK que abre la ventana la conexión se traba para siempre.
• Abandono: una conexión que pasa 30 s sin recibir ningún paquete válido del otro extremo devuelve error con ETIMEDOUT, sin colgarse. Vale para rimay_connect, rimay_send, rimay_recv y rimay_close. Una conexión quieta pero viva no se abandona: tras 10 s de silencio envíen una sonda, que el otro extremo responde. Solo rimay_accept espera sin límite.

Reglas que revisan las pruebas

Se transfieren archivos de 1 KB y 1 MB en cada condición, y además 20 MB sin fallas, y se compara su hash. Las fallas se ponen en las dos interfaces del router, así que valen para cada sentido por separado.

Con mucha pérdida, una transferencia demora bastante y varía mucho, también en un programa correcto. Es lo esperado: en una ventana de 64 paquetes con 10 % de pérdida casi siempre hay algún hueco, así que casi todo ACK cubre algo retransmitido y Karn no deja medir. El RTO queda arriba con su retroceso hasta que aparezca una medición válida. En una laptop ocupada, la solución de referencia demoró con 1 MB y 10 % de pérdida entre 39 y 227 s, con una mediana de 155 s, en 25 corridas a la vez. Con todo junto, entre 45 y 245 s. Los límites de la tabla salen de esas cifras, con margen.

netem corrupt no alcanza a probar su checksum: el bit cambiado también rompe el checksum de UDP, y el kernel descarta el datagrama antes de que llegue a su programa. Por eso, además, las pruebas tienen un proxy en Python que pierde, duplica, desordena y corrompe con semilla fija, y reenvía cada datagrama con un checksum de UDP correcto. Ese bit cambiado sí llega a su programa.

Las pruebas también hablan directamente con sus programas, paquete por paquete, desde Python. Revisan la ventana, las sondas, el RTO con RTT corto y largo, el retroceso, Karn, los ACK parciales, el handshake con cualquier paso perdido, el cierre con cualquier FIN o ACK perdido, la vuelta de los números de secuencia en 2^32 y varios clientes a la vez. Para forzar esa vuelta, si existe la variable de entorno RIMAY_TEST_ISN, úsenla como ISN (en decimal).

También se revisa el formato en una captura real, con un disector de Wireshark que viene con las pruebas (tests/rimay.lua):

make ver-captura PCAP=captura.pcap PUERTO=9000

Wireshark no carga scripts de Lua si corre como root, y en el contenedor todo corre como root: por eso el Makefile corre tshark como nobody.

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        # compila, levanta la topología, corre todo y la destruye (unos 15 minutos)
make test-local  # solo lo que no usa topología
make clean       # destruye la topología y borra lo generado

Para correr una sola prueba mientras trabajan:

make && python3 -m unittest -v p3_public_test.LocalSender.test_zero_window_probe

La revisión corre además pruebas privadas con otra topología, otras tasas de falla, otras semillas y otros archivos.

Probar a mano

h1 10.93.1.10 --- r --- 10.93.2.10 h2

Sus programas se compilan y corren en el contenedor del curso, y solo entran a la red de un nodo con nsenter. Por eso funciona igual en amd64 y arm64:

make topo-up
make falla ARGS="delay 20ms loss 10%"
make recibir ARGS="9000 copia" &
make enviar ARGS="10.93.2.10 9000 archivo"
make sin-falla

El mismo truco sirve para gdb, valgrind o tcpdump:

H1=$(docker inspect -f '{{.State.Pid}}' clab-p3-rimay-h1)
nsenter -n -t $H1 valgrind build/rimay_send_file 10.93.2.10 9000 archivo
nsenter -n -t $H1 tcpdump -n -i eth1 udp port 9000

Al terminar, make topo-down.

Si una prueba falla

• La transferencia con pérdida pasa del límite. Revisen los ACK parciales y el RTO máximo de 10 s. Unos minutos con 1 MB y 10 % de pérdida son normales; más de 10 no.
• rimay_send_file termina con error después de transferir todo. Se perdió un ACK del FIN y el otro extremo ya se fue. Quien cierra primero debe esperar al menos 1 s para volver a confirmar.
• Pasa entre sus dos programas, pero falla contra las pruebas. Sus dos lados pueden tener el mismo error: un checksum que no cubre los datos, por ejemplo, o un campo sin htonl. Las pruebas calculan todo por su cuenta.
• El archivo llega bien, pero falla test_window_is_honest. window debe contar lo que de verdad está libre en su buffer.
• El programa se queda colgado con la ventana en cero. Faltan las sondas, o nadie atiende la red mientras la aplicación no llama a la biblioteca.