Slides TD IV - clases (10)

Vista previa del material en texto

TD4 2022TD4 2022
Agenda
▪ Servicios del nivel de transporte
▪ Multiplexación y demultiplexación
▪ Transporte no orientado a conexión: UDP
▪ Transferencia de datos confiable
▪ Transporte orientado a conexión: TCP
▪ Control de congestión
▪ Protocolos modernos: QUIC
2
TD4 2022TD4 2022 3
Protocolos confiables
TD4 2022TD4 2022
Transmisión confiable: conceptos
La complejidad del protocolo depende 
fuertemente de las particularidades del 
canal no confiable subyacente (e.g. si 
corrompe, pierde y/o reordena datos)
4
emisor del 
protocolo de 
transmisión 
confiable
proceso
emisor
proceso 
receptor
 canal no confiable
servicio confiable: implementación
datos datos
receptor del 
protocolo de 
transmisión 
confiable
TD4 2022TD4 2022
Transmisión confiable: conceptos
Los interlocutores no conocen el estado 
del otro (e.g., el emisor no puede saber si 
un mensaje fue recibido)
▪ La única forma de conocer dicho 
estado es mediante el intercambio de 
mensajes (¡que puede fallar!)
5
emisor del 
protocolo de 
transmisión 
confiable
proceso
emisor
proceso 
receptor
 canal no confiable
servicio confiable: implementación
datos datos
receptor del 
protocolo de 
transmisión 
confiable
TD4 2022TD4 2022
API (abstracta) de un protocolo confiable
rdt_send()
udt_send() rdt_rcv()
deliver_data()
header header
rdt_send(): invocada 
desde la app para pasar 
datos a entregar al nivel de 
aplicación del receptor
udt_send(): invocada por 
rdt para transmitir un 
paquete al receptor sobre el 
canal no confiable
rdt_rcv(): invocada 
cuando llega un paquete por 
el canal
deliver_data(): invocada 
por rdt para entregar datos a 
la capa de aplicación
comunicación bidireccional
datos
paquete
6
proceso
emisor
proceso 
receptor
 canal no confiable
datos datos
datosdatos
emisor del 
protocolo de 
transmisión 
confiable rdt
receptor del 
protocolo de 
transmisión 
confiable rdt
TD4 2022TD4 2022
Diseño de un protocolo confiable
▪ Vamos a diseñar incrementalmente las características de un protocolo de 
transmisión confiable, rdt (Reliable Data Transfer)
▪ Motivación para entender la complejidad de protocolos como TCP
▪ Consideramos flujo unidireccional de datos (pero no así de información 
de control)
▪ Utilizaremos máquinas de estados finitos (FSMs) para especificar el 
protocolo:
7
estado
1
evento que causa
transición de estados
acciones tomadas al transicionar
el siguiente estado queda 
unívocamente determinado 
por el siguiente evento
estado
2evento
acciones
TD4 2022TD4 2022
rdt1.0: transmisión confiable sobre un canal confiable
▪ Comenzamos asumiendo que el canal subyacente es perfectamente 
confiable
• No introduce errores en los bits
• Tampoco pierde paquetes
packet = make_pkt(datos)
udt_send(packet)
rdt_send(datos)
extract(packet,datos)
deliver_data(datos)
rdt_rcv(packet)esperar
llamadareceptor
▪Tenemos una FSM para el emisor y otra para el receptor:
• El emisor envía datos al canal subyacente
• El receptor lee datos del canal
emisor
esperar 
llamada
8
TD4 2022TD4 2022
rdt2.0: transmisión sobre un canal con errores
▪ El canal subyacente puede corromper bits en los paquetes
• Se pueden detectar vía checksum 
▪ ¿Cómo podemos recuperarnos de los errores?
• Acknowledgements (ACKs): el receptor indica explícitamente 
que el paquete llegó bien
• Negative Acknowledgements (NAKs): el receptor indica 
explícitamente que el paquete llegó con errores
• El emisor retransmite el paquete al recibir un NAK
stop and wait
el emisor envía un paquete y luego espera la respuesta del receptor
9
TD4 2022TD4 2022
rdt2.0: especificación
esperar
ACK / NAK
udt_send(NAK)
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
extract(rcvpkt,datos)
deliver_data(datos)
udt_send(ACK)
rdt_rcv(rcvpkt) && !corrupt(rcvpkt)
sndpkt = make_pkt(datos, checksum)
udt_send(sndpkt)
rdt_send(datos)
 
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Λ esperar
llamada receptor
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
10
Nota: el emisor no tiene forma de conocer el 
estado del receptor a menos que el mismo se 
comunique explícitamente
esperar 
llamada
emisor
TD4 2022TD4 2022
rdt2.0: ACKs/NAKs corruptos
Este protocolo falla si hay corrupción 
en ACKs/NAKs
▪El emisor no tiene forma de saber 
qué ocurrió en el receptor
▪No es posible retransmitir: podría 
generar datos duplicados
Manejo de duplicados:
▪El emisor retransmite el 
paquete actual ante 
corrupción de ACK/NAK
▪Agrega un número de 
secuencia a cada paquete
▪El receptor descarta paquetes 
duplicados valiéndose de este 
valor
11
stop and wait
el emisor envía un paquete y luego espera la respuesta del receptor
TD4 2022TD4 2022
rdt2.1: manejo de ACKs/NAKs corruptos
udt_send(sndpkt)
rdt_rcv(rcvpkt) && 
(corrupt(rcvpkt) || isNAK(rcvpkt))
12
emisor
udt_send(sndpkt)
rdt_rcv(rcvpkt) && 
(corrupt(rcvpkt) || isNAK(rcvpkt))
esperar
ACK / 
NAK
0
sndpkt = make_pkt(0, datos, checksum)
udt_send(sndpkt)
rdt_send(datos)
esperar
Llamada
1
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && isACK(rcvpkt) 
Λ
sndpkt = make_pkt(1, datos, checksum)
udt_send(sndpkt)
rdt_send(datos)
esperar
ACK / 
NAK
1
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && isACK(rcvpkt) 
Λ
esperar
Llamada 
0
TD4 2022TD4 2022
rdt2.1: manejo de ACKs/NAKs corruptos
rdt_rcv(rcvpkt) && 
!corrupt(rcvpkt) && has_seq(rcvpkt, 1)
sndpkt = make_pkt (ACK, checksum)
udt_send (sndpkt)
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
sndpkt = make_pkt (NAK, checksum)
udt_send (sndpkt)
13
receptor
rdt_rcv(rcvpkt) && 
!corrupt(rcvpkt) && has_seq(rcvpkt, 0)
sndpkt = make_pkt (ACK, checksum)
udt_send (sndpkt)
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
sndpkt = make_pkt (NAK, checksum)
udt_send (sndpkt)
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && has_seq(rcvpkt, 0) 
extract(rcvpkt,datos)
deliver_data (datos)
sndpkt = make_pkt (ACK, checksum)
udt_send (sndpkt)
esperar 
1
esperar 
0
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && has_seq(rcvpkt, 1) 
extract(rcvpkt,datos)
deliver_data (datos)
sndpkt = make_pkt (ACK, checksum)
udt_send (sndpkt)
TD4 2022TD4 2022
rdt2.1: conclusiones
Emisor
▪ Agrega un número de secuencia a 
los paquetes
▪ Sólo utiliza dos números de 
secuencia
▪ Debe comprobar corrupción de 
los ACKs/NAKs recibidos
▪ Duplica la cantidad de estados
• El estado debe recordar el 
número de secuencia del paquete 
esperado
Receptor
▪ Debe comprobar si el paquete 
recibido es un duplicado
• El estado indica el número de 
secuencia del paquete 
esperado
▪ El receptor no puede saber si 
su último ACK/NAK llegó 
correctamente al emisor
14
TD4 2022TD4 2022
rdt2.2: eliminando los NAKs
▪ Misma funcionalidad que rdt2.1 pero sólo empleando ACKs
▪ En vez de un NAK, el receptor envía un ACK del último paquete 
recibido correctamente
• El receptor debe indicar explícitamente el número de secuencia 
del paquete ACKeado
▪ Un ACK duplicado en el emisor dispara la misma acción que 
un NAK: retransmitir el paquete actual
TCP utiliza este enfoque (más sobre esto luego)
15
TD4 2022TD4 2022
rdt2.2: eliminando los NAKs
16
esperar
llamada
esperar
ACK 0
Λ
emisor
sndpkt = make_pkt(0, datos, checksum)
udt_send(sndpkt)
rdt_send(datos)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) || isACK(rcvpkt, 1))
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && isACK(rcvpkt, 0) 
esperar 
0 receptor
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) || has_seq(rcvpkt, 1))
sndpkt = make_pkt(1, ACK, checksum)
udt_send (sndpkt)
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && has_seq(rcvpkt, 1) 
extract(rcvpkt,datos)
deliver_data (datos)
sndpkt = make_pkt(1, ACK, checksum)
udt_send (sndpkt)
(FSM parciales)
TD4 2022TD4 2022
rdt3.0: transmisión sobre un canal con errores y pérdidas
Nueva suposición: el canal subyacente, además de introducir 
errores, puede perder paquetes (datos y/o ACKs)
• Necesitamos checksums, números de secuencia, ACKs y 
retransmisiones, pero con esto solo no alcanza
17
Enfoque: el emisor espera un ACK durante cierto tiempo
▪ Si no llega, retransmite el paquete
▪ Si hay demoras (en vez de pérdidasefectivas),
• La retransmisión causará duplicados (pero ya lo contemplamos con 
los números de secuencia)
• El receptor debe indicar el número de secuencia del paquete ACKeado
▪ La espera se controla con un timer que produce interrupciones cada 
cierto intervalo de tiempo (timeout)
TD4 2022TD4 2022
rdt3.0: especificación del emisor
udt_send (sndpkt)
start_timer()
timeoutesperar
llamada
0
Λ
rdt_rcv(rcvpkt)
18
Λ
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) || isACK(rcvpkt, 1))
Λ
rdt_rcv(rcvpkt)
udt_send (sndpkt)
start_timer()
timeout
Λ
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) || isACK(rcvpkt, 0))
sndpkt = make_pkt(0, datos, checksum)
udt_send(sndpkt)
start_timer()
rdt_send(datos)
sndpkt = make_pkt(1, datos, checksum)
udt_send(sndpkt)
start_timer()
rdt_send(datos)
stop_timer()
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && isACK(rcvpkt, 1) 
stop_timer()
rdt_rcv(rcvpkt) &&
!corrupt(rcvpkt) && isACK(rcvpkt, 0) 
esperar
ACK 1
esperar
ACK 0
esperar
llamada
1
TD4 2022TD4 2022
rdt3.0: escenarios
emisor receptor
envía 
paquete 0
 0
(a) sin pérdida
emisor receptor
(b) pérdida de paquete (datos)
19
0
envía
ACK 0
1envía paquete 1
1
envía
ACK 1
0envía 
paquete 0
 0 envíaACK 0
0 envíaACK 0
0
envía
ACK 0
1 envía
ACK 1
0envía paquete 0
0envía 
paquete 0
1
X
envía 
paquete 1
1
timeout
reenvía 
paquete 1
TD4 2022TD4 2022
rdt3.0: escenarios
20
(c) pérdida de paquete (ACK) (d) ACK demorado
emisor receptor
emisor receptor
1
timeout
reenvía 
paquete 1
timeout
reenvía 
paquete 1 1
0envía 
paquete 0
0envía 
paquete 0
0envía paquete 0
0
envía 
paquete 0
1envía paquete 1
1envía 
paquete 1
1envía 
paquete 1
0
envía
ACK 0
0
envía
ACK 0
0
envía
ACK 0
0
envía
ACK 0
1
X
envía
ACK 1
1
envía
ACK 1
1
envía
ACK 1
1
envía
ACK 1
descarta 
duplicado
descarta 
duplicado ignora 
ACK 1
TD4 2022TD4 2022
rdt3.0: rendimiento (stop-and-wait)
emisor receptor
t = 0: transmisión del primer bit 
RTT 
recepción del primer bit
recepción del último bit
envío de ACK
t = t1: recepción de ACK y 
envío de siguiente paquete
21
▪Veamos cómo estimar la utilización del canal U por parte del emisor
t = t0: transmisión del último bit 
t0 = delay de transmisión, L / R
t1 = RTT + L / R
U =
L / R
RTT + L / R
▪ Si por ej. L = 8 kb, R = 1 Gbps y RTT = 30 ms, U = 0.00027
■ Rendimiento muy pobre
▪ El protocolo limita el rendimiento del canal subyacente
TD4 2022TD4 2022
rdt3.0: pipelining
Podemos incrementar el rendimiento mediante la técnica de pipelining
• El emisor mantiene múltiples paquetes “en vuelo” (en vez de sólo uno)
• Los números de secuencia respectivos se incrementan ante cada nueva 
transmisión
• Se deben gestionar buffers (en el emisor y/o receptor)
22
TD4 2022TD4 2022
Rendimiento utilizando pipelining
un pipelining de 3 paquetes 
aumenta 3x el rendimiento 
del protocolo
23
RTT 
recepción del primer bit (paquete 1)
recepción del último bit (paquete 1); envío de ACK
recepción del último bit (paquete 2); envío de ACK
recepción del último bit (paquete 3); envío de ACK
emisor receptor
transmisión del primer bit (paquete 1) 
transmisión del último bit (paquete 1) 
recepción de ACK #1;
envío del siguiente paquete
U =
3L / R
RTT + L / R
= 0.00081
TD4 2022TD4 2022
Pipelining vía Go-Back-N (GBN)
▪ El emisor mantiene una ventana de hasta N paquetes en vuelo
• Utiliza un número de secuencia (#SEQ) de k bits en el header
▪ ACK acumulativo, ACK(n): reconoce todos los paquetes hasta el de #SEQ n 
(incluido)
• Al recibir un ACK(n), se desplaza la ventana hacia adelante para comenzar en n+1
▪ El timer corresponde al paquete en vuelo más antiguo
▪ timeout(n) dispara una retransmisión del paquete n junto con todos los de 
#SEQ más grande en la ventana
24
base próximo #SEQ
ventana 
de largo N
#SEQs
ACKeados
#SEQs
en vuelo
#SEQs utilizables
(no enviados)
#SEQs
no utilizables
Demo: https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/go-back-n-protocol/index.html
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/go-back-n-protocol/index.html