Slides TD IV - clases (11)

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
rdt3.0: escenarios
emisor receptor
envía 
paquete 0
 0
(a) sin pérdida
emisor receptor
(b) pérdida de paquete (datos)
4
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
5
(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 2022 6
(d) ACK demorado
emisor receptor
timeout
reenvía 
paquete 1 1
0envía paquete 0
0
envía 
paquete 0
1envía 
paquete 1
1envía 
paquete 1
0
envía
ACK 0
0
envía
ACK 0
1
envía
ACK 1
1
envía
ACK 1
descarta 
duplicado
ignora 
ACK 1
(e) ACK muy
 demorado
emisor receptor
timeout
reenvía 
paquete 1 1
0envía paquete 0
0envía 
paquete 0
1envía 
paquete 1
1envía 
paquete 1
0
envía
ACK 0
0
envía
ACK 0
1
envía
ACK 1
1
envía
ACK 1
descarta 
duplicado
ignora 
ACK 1
rdt3.0: escenarios
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
7
▪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)
8
TD4 2022TD4 2022
Rendimiento utilizando pipelining
un pipelining de 3 paquetes 
aumenta 3x el rendimiento 
del protocolo
9
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
10
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
TD4 2022TD4 2022
Go-Back-N: receptor
▪ El receptor siempre envía un ACK para el paquete con el #SEQ más 
alto (en orden) recibido correctamente
• Puede generar ACKs duplicados
• Debe recordar el siguiente #SEQ esperado, rcv_base
▪ Al recibir un paquete fuera de orden,
• Es posible almacenarlo o descartarlo (decisión de implementación)
• Se reenvía ACK para el paquete con el #SEQ más alto recibido
 
rcv_base
recibidos y ACKeados
recibidos fuera de orden (sin ACK)
aún no recibidos
espacio de #SEQs desde la óptica del receptor
 
 … …
11
TD4 2022TD4 2022
Go-Back-N: ejemplo
receptorventana (N = 4)
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 
0 1 2 3 4 5 6 7
emisor
12
X
envía 0
envía 1
envía 2
envía 3
recibe 0; envía ACK 0
recibe 1; envía ACK 1
recibe 3; envía ACK 1
recibe ACK 0; envía 4
recibe ACK 1; envía 5
recibe 4; envía ACK 1
recibe 5; envía ACK 1
timeout
reenvía paquetes 2,...,5
recibe 2; envía ACK 2
recibe 3; envía ACK 3
recibe 4; envía ACK 4
recibe 5; envía ACK 5
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
recibe ACK 1; lo ignora
TD4 2022TD4 2022
Pipelining vía Selective Repeat
▪Con Selective Repeat, el receptor reconoce uno a uno cada 
paquete recibido correctamente
• Almacena en buffers los paquetes para entregarlos (en orden) a la 
capa superior, eventualmente
▪El emisor dispara un timeout y retransmite cada paquete 
individualmente
• Mantiene un timer por cada paquete sin ACK
▪La ventana de emisión consta de N #SEQs consecutivos
13
TD4 2022TD4 2022
Ventanas en Selective Repeat
14
#SEQs
ACKeados
#SEQs
en vuelo
#SEQs utilizables
(no enviados)
#SEQs
no utilizables
#SEQs
recibidos
#SEQs
aceptables
#SEQs
no utilizables
#SEQs
no recibidos
send_base próximo #SEQ
ventana 
de largo N
ventana 
de largo N
rcv_base
vista del emisor
vista del receptor
Demo: https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
TD4 2022TD4 2022
Ventanas en Selective Repeat
15
#SEQs
ACKeados
#SEQs
en vuelo
#SEQs utilizables
(no enviados)
#SEQs
no utilizables
#SEQs
recibidos
#SEQs
aceptables
#SEQs
no utilizables
#SEQs
no recibidos
send_base próximo #SEQ
ventana 
de largo N
ventana 
de largo N
rcv_base
vista del emisor
vista del receptor
Demo: https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/content/interactiveanimations/selective-repeat-protocol/index.html
TD4 2022TD4 2022
Acciones de emisor y receptor en SR
Datos desde capa superior
▪ Si el próximo #SEQ disponible está 
dentro de la ventana, enviar el 
paquete
timeout(n)
▪ Reenviar paquete n; reiniciar timer
ACK(n) en [send_base, send_base+N]
▪ Marcar paquete n como recibido
▪ Si n es el #SEQ más chico sin ACK, 
desplazar la base de la ventana al 
próximo #SEQ sin ACK
Emisor
16
Paquete n en 
[rcv_base,rcv_base+N-1]
▪ Enviar ACK(n)
▪ Si está fuera de orden, almacenarlo
▪ Sino, entregarlo (junto con otros en 
orden); desplazar ventana al siguiente 
#SEQ aún no recibido
Paquete n en [rcv_base-N,rcv_base-1]
▪ Enviar ACK(n)
En cualquier otro caso 
▪ Ignorar y descartar el paquete
Receptor
TD4 2022TD4 2022
Selective Repeat: ejemplo
X
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7
17
receptorventana (N = 4) emisor
envía 0
envía 1
envía 2
envía 3
recibe 3; envía ACK 3; bufferea 3
recibe ACK 0; envía 4
recibe ACK 1; envía 5
recibe 4; envía ACK 4; bufferea 4
recibe 5; envía ACK 5; bufferea 5recibe ACK 3;
marca 3 recibido
timeout(2)
reenvía paquete 2
recibe 2; envía ACK 2; entrega 2,...,5
0 1 2 3 4 5 6 7
recibe 0; envía ACK 0; entrega 0 
recibe 1; envía ACK 1; entrega 1
TD4 2022TD4 2022
El dilema de la repetición0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
pkt0
pkt1
pkt2
0 1 2 3 0 1 2 pkt0
timeout!
retransmite pkt0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
X
X
X
Recibe paquete 
con #seq = 0
Escenario b)Escenario a)
¿Paquete nuevo o retransmisión?
▪ #seq: 0, 1, 2, 3 (base 4)
▪ Ventana N = 3
18
ReceptorEmisor
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
pkt0
pkt1
pkt2
0 1 2 3 0 1 2 pkt0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
X
Recibe paquete 
con #seq = 0
0 1 2 3 0 1 2 pkt3
ReceptorEmisor
TD4 2022TD4 2022
Ejercicio!
0 1 2 3 0 1 
20 1 2 3 0 1 
20 1 2 3 0 1 
2
pkt
0pkt
1pkt
2
0 1 2 3 0 1 
2
pkt
0
timeout
retransmit 
pkt0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
X
X
X
Recibe paquete 
con #seq = 0
(b) oops!
Receptor
0 1 2 3 0 1 
2
pkt
2
0 1 2 3 0 1 
20 1 2 3 0 1 
2
0 1 2 3 0 1 2
pkt
0pkt
1
pkt
0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
X
Recibe paquete 
con #seq = 0
0 1 2 3 0 1 
2
pkt
3
(a) no problem
▪ El receptor no puede ver "el otro lado".
▪ Comportamiento idéntico en ambos casos. 
▪ Algo salió (muy) mal!
19
¿Cuál es la relación que se necesita entre el tamaño de 
la ventana y la base de los números de secuencia para 
evitar este problema?
Receptor
TD4 2022TD4 2022
Protocolos confiables: resumen
▪ Checksum: se utiliza para detectar errores en los bits de un paquete.
▪ Timer: se utiliza para disparar retransmisiones, posiblemente debido a la pérdida de 
un paquete o su ACK. Las retransmisiones pueden generar duplicados. 
▪ Números de secuencia: permiten ordenar y detectar pérdida de paquetes o 
duplicados. 
▪ ACKs: usados por el receptor para notificar que un paquete se recibió 
correctamente. En general, informan el #seq del paquete. Pueden ser individuales o 
acumulativos. 
▪ NACKs: usados por el receptor para notificar que un paquete no se recibió 
correctamente. En general, informan el #seq del paquete.
▪ Ventanas/Pipelining: aumentan la utilización del canal (U), permitiendo que 
múltiples paquetes puedan ser enviados, aún en el caso de no haber recibido sus 
respectivos ACKs. 
20
TD4 2022TD4 2022 21
El protocolo TCP
TD4 2022TD4 2022
TCP: vista general [RFCs: 793,1122, 2018, 5681, 7323]
▪ ACKs acumulativos
▪ Pipelining
• La ventana de emisión se 
define mediante el control de 
flujo y el control de congestión 
▪ Orientado a conexión
• Se inicializa estado en los 
interlocutores mediante un 
proceso de handshaking 
(intercambio de mensajes de 
control)
▪ Control de flujo
• Permite que el emisor no sature 
al receptor
▪ Punto a punto
• Un emisor y un receptor 
por conexión
▪ Flujo (stream) de bytes 
confiable y en orden
• Sin límites de mensajes
▪ Canal full-duplex
• Flujo de datos bidireccional 
en la misma conexión
22
TD4 2022TD4 2022
Estructura del segmento TCP
puerto src puerto dst
32 bits
sin 
uso ventana rec. cantidad de bytes que el 
receptor está dispuesto 
a aceptar
nro. de secuencia
cuenta cantidad de bytes 
enviados por el stream de 
datos
datos de la aplicación
(longitud variable)
datos enviados al 
socket TCP por la 
aplicación 
A
nro. de ACK
ACK: nro. de secuencia del 
próximo byte esperado
flag A: indica ACK
opciones (longitud variable)
opciones de TCP
head
len
longitud del header
checksumMismo que en UDP
(Internet checksum)
flags RST, SYN, FIN:
manejo de conexión
FSR
URG pointer
PUC E
flags C, E:
notificación de congestión
23
TD4 2022TD4 2022
Números de secuencia y ACKs
Número de secuencia
• Índice en el stream de bytes 
del primer byte en el payload
enviados, 
con ACK
enviados, 
sin ACK
aún no 
enviados
no utilizables
tamaño de ventana, N
espacio de números de secuencia 
puerto src puerto dst
#SEQ
#ACK
checksum
rwnd
URG pointer
segmento del emisor
Número de ACK
• Número de secuencia del 
siguiente byte esperado por 
el otro interlocutor
• ACK acumulativo
El manejo de segmentos fuera de orden 
queda a cargo de la implementación
24
N
puerto src puerto dst
#SEQ
#ACK
checksum
rwnd
URG pointer
segmento del receptor
A
TD4 2022TD4 2022
Números de secuencia y ACKs
El host envía un 
ACK de la ‘C’ 
recibida
El host envía un ACK de 
‘C’ y manda de vuelta el 
caracter
Ejemplo: telnet
Host BHost A
El usuario tipea ‘C’ #SEQ=42, #ACK=79,
payload = ‘C’
#SEQ=79, #ACK=43,
payload = ‘C’
#SEQ=43, 
#ACK=80
25