LA CAPA DE TRANSPORTE
Capa de transporte 3-1
Principios de transferencia
de datos fiable
Capa de transporte 3-2
Principios de trasferencia de datos fiable
Importante en las capas de aplicación, transporte y enlace
En la lista de los 10 tópicos más importantes de redes!
Las características del canal no fiable determinarán la complejidad
del protocolo de transferencia de datos fiable (rdt)
Capa de transporte 3-3
Principios de trasferencia de datos fiable
Importante en las capas de aplicación, transporte y enlace
En la lista de los 10 tópicos más importantes de redes!
Las características del canal no fiable determinarán la complejidad
del protocolo de transferencia de datos fiable (rdt)
Capa de transporte 3-4
Principios de trasferencia de datos
fiable
Importante en las capas de aplicación, transporte y enlace
En la lista de los 10 tópicos más importantes de redes!
Las características del canal no fiable determinarán la complejidad
del protocolo de transferencia de datos fiable (rdt)
Capa de transporte 3-5
Transferencia de datos fiable: comenzando
rdt_send(): llamado de arriba, (e.g., deliver_data(): llamado por rdt
por una aplicación). Pasa datos para para entregar datos a la capa
entregar a la capa superior del receptor superior
Lado Lado
emisor receptor
udt_send(): llamado por rdt, rdt_rcv(): llamado cuando llega un
para transferir un paquete paquete al lado receptor del canal
sobre un canal no fiable al
receptor
Capa de transporte 3-6
Transferencia de datos fiable: comenzando
¿Qué haremos? :
Desarrollar incrementalmente los extremos emisor y receptor del
protocolo de transferencia de datos fiable (rdt)
Considerar solo la transferencia de datos unidireccional
Pero la información de control fluirá en ambas direcciones!
Usar máquinas de estado finito (FSM) para especificar el emisor y
el receptor
Evento que causa el cambio de estado
estado: estando en
Acciones tomadas al cambiar el estado
este “estado”, el
siguiente estado
estado
se determina estado
1 evento
univocamente 2
por el siguiente acción
evento
Capa de transporte 3-7
Rdt1.0: Transferencia fiable sobre un canal fiable
Canal subyascente perfectamente fiable
No hay errores de bit
No hay pérdida de paquetes
FSMs separados para emisor, receptor:
Emisor envia datos al canal subyascente
Receptor lee datos del canal subyascente
Espera rdt_send(data) Espera rdt_rcv(packet)
llamada packet = make_pkt(data) llamada extract (packet,data)
de arriba udt_send(packet) de abajo deliver_data(data)
emisor receptor
Capa de transporte 3-8
Rdt2.0: canal con errores de bit
Canal subyascente puede invertir los bits en un
paquete
checksum para detectar errores de bit
La pregunta: como recuperarse de errores:
confirmación (ACKs): el receptor explícitamente le dice al
emisor que un paquete se recibio bien
Confirmación negativa (NAKs): el receptor explícitamente le
dice al emisor que el paquete tuvo errores
El emisor retransmite el paquete al recibir un NAK
Nuevos mecanismos en rdt2.0 (sobre rdt1.0):
Detección de errores
Retroalimentación del receptor: mensajes de control (ACK,
NAK) del receptor al emisor
Capa de transporte 3-9
rdt2.0: Especificación FSM
rdt_send(data)
snkpkt = make_pkt(data, checksum) receptor
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Espera Wait for rdt_rcv(rcvpkt) &&
llamada de ACK or udt_send(sndpkt) corrupt(rcvpkt)
arriba NAK
udt_send(NAK)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Espera
L
llamada de
abajo
emisor
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Capa de transporte 3-10
rdt2.0: operación sin errores
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Espera Espera rdt_rcv(rcvpkt) &&
llamada de ACK o udt_send(sndpkt) corrupt(rcvpkt)
arriba NAK
udt_send(NAK)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Espera
L llamada de
abajo
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Capa de transporte 3-11
rdt2.0: Escenario con error
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Espera Espera rdt_rcv(rcvpkt) &&
llamada de ACK o udt_send(sndpkt) corrupt(rcvpkt)
arriba NAK
udt_send(NAK)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Espera
L llamada de
abajo
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Capa de transporte 3-12
rdt2.0 tiene una falla fatal!
¿Qué ocurre si los Manejar duplicados:
ACK/NAK se corrompen? El emisor retransmite el
paquete atual si el ACK/NAK
está dañado
El emisor no sabe que ocurrió
El emisor agrega un número de
en el receptor!
secuencia a cada paquete
No puede retransmitir
El receptor descarta (no
simplemente: posible
entrega hacia arriba) el
duplicado
paquete duplicado
Parada y espera (Stop and wait)
El emisor envia un paquete y espera la respuesta del receptor
Capa de transporte 3-13
rdt2.1: El emisor maneja ACK/NAKs dañados
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt) rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Espera Espera
ACK o
isNAK(rcvpkt) )
llamada 0
NAK 0 udt_send(sndpkt)
de arriba
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) rdt_rcv(rcvpkt)
&& isACK(rcvpkt) && notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
L
Espera Espera
ACK o llamada 1
rdt_rcv(rcvpkt) && NAK 1 de arriba
( corrupt(rcvpkt) ||
isNAK(rcvpkt) ) rdt_send(data)
udt_send(sndpkt) sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
Capa de transporte 3-14
rdt2.1: el receptor maneja ACK/NAKs dañados
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum) sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt) udt_send(sndpkt)
Espera Espera
rdt_rcv(rcvpkt) && 0 de 1 de rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && abajo abajo not corrupt(rcvpkt) &&
has_seq1(rcvpkt) has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum) sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt) udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
Capa de transporte 3-15
rdt2.1: Discusión
Emisor: Receptor:
#sec agregado al Debe verificar si el
paquete paquete recibido es
Dos #sec (0,1) serán duplicado
suficientes. ¿Porqué? El estado indica si el
#sec esperado es 0 o 1
Debe verificar si el
nota: el receptor no
ACK/NAK recibido esta
dañado puede saber si su
último ACK/NAK fué
Dos veces mas estados
recibido correctamente
Un estado debe “recordar”
en el emisor
si el paquete “actual” tiene
#sec 0 o 1
Capa de transporte 3-16
rdt2.2: Un protocolo libre de NAK
La misma funcionalidad que rdt2.1, usando solo ACKs
En vez de un NAK, el receptor envía un ACK por el
último paquete recibido OK
El receptor debe incluir explícitamente el #sec del paquete
confirmado
Un ACK duplicado en el emisor resulta en la misma
acción que un NAK: se retransmite el paquete actual
Capa de transporte 3-17
rdt2.2: Fragmentos del emisor y receptor
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait for Wait for
ACK isACK(rcvpkt,1) )
call 0 from
above 0 udt_send(sndpkt)
sender FSM
fragment rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
rdt_rcv(rcvpkt) && && isACK(rcvpkt,0)
(corrupt(rcvpkt) || L
has_seq1(rcvpkt)) Wait for receiver FSM
0 from
udt_send(sndpkt) below fragment
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt) Capa de transporte 3-18
rdt3.0: Canal con errores y pérdida
Nueva presunción: Enfoque: el emisor espera por un
tiempo “razonable” un ACK
El canal subyascente Retransmite si no se recibe ningun
puede también perder ACK en ese tiempo
paquetes (de datos o Si el paquete (o ACK) solo se retrasó
ACKs) (no se perdió) :
La retransmisión generará un
Suma de verificación,
duplicado, pero el uso de #sec
#sec, ACKs y
resuelve este problema
retransmisiones son de
El receptor debe especificar #sec
ayuda, pero no del paquete confirmado
suficientes
Requiere de un contador
descendente
Capa de transporte 3-19
rdt3.0 emisor
rdt_send(data)
rdt_rcv(rcvpkt) &&
sndpkt = make_pkt(0, data, checksum) ( corrupt(rcvpkt) ||
udt_send(sndpkt) isACK(rcvpkt,1) )
rdt_rcv(rcvpkt) start_timer L
L Wait for Wait
for timeout
call 0from
ACK0 udt_send(sndpkt)
above
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) rdt_rcv(rcvpkt)
&& isACK(rcvpkt,1) && notcorrupt(rcvpkt)
stop_timer && isACK(rcvpkt,0)
stop_timer
Wait Wait for
timeout for call 1 from
udt_send(sndpkt) ACK1 above
start_timer rdt_rcv(rcvpkt)
rdt_send(data) L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) || sndpkt = make_pkt(1, data, checksum)
isACK(rcvpkt,0) ) udt_send(sndpkt)
start_timer
L
Capa de transporte 3-20
rdt3.0 en acción
Capa de transporte 3-21
rdt3.0 en acción
Capa de transporte 3-22
Desempeño de rdt3.0
rdt3.0 funciona, pero el desempeño es bajo
Ejemplo:
En un enlace de 1 Gbps, con retardo de propagación de 15 ms, y
tamaño de paquete de 8000 bits:
𝐿 8000𝑏
𝑑𝑡𝑟𝑎𝑛𝑠 = = 9 = 8µ𝑠
𝑅 10 𝑏𝑝𝑠
Utilización del emisor
Uemisor : Fracción de tiempo que el emisor está ocupado
enviando
RTT : Tiempo de ida y vuelta (Round Trip Time)
3-23
rdt3.0: operación de parada y espera
emisor receptor
Primer bit de paquete transmitido, t = 0
Ultimo bit de paquete transmitido,
t=L/R
Llega primer bit de paquete
RTT Llega último bit de paquete, enviar
ACK
ACK llega, enviar siguientepaquete,
t = RTT + L / R
𝐿ൗ 0.008𝑚𝑠
𝑈𝑒𝑚𝑖𝑠𝑜𝑟 = 𝑅 = = 0.00027
𝐿
𝑅𝑇𝑇 + ൗ𝑅 30.008𝑚𝑠
1 PDU de 1KB cada 30 ms → 33KBps (267Kbps) aún sobre un enlace de 1Gbps
El protocolo de red limita el uso de los recursos físicos!
3-24
Protocolos entubados (encauzados)
Encauzamiento: el emisor permite múltiples paquetes, “en camino”,
por confirmar
El rango de números de secuencia debe incrementarse
Buffers en el emisor y receptor
Dos formas genéricas de protocolos encauzados: regresar a N,
repetición selectiva
3-25
Encauzamiento: utilización mejorada
sender receiver
Primer bit de paq. transmitido, t = 0
Ultimo bit transmitido,
t=L/R
Llega primer bit de paquete
RTT Llega último bit de paquete, enviar ACK
Llega último bit de 2° paquete, enviar ACK
Llega último bit de 3° paquete, enviar ACK
ACK llega, enviar siguiente paquete,
t = RTT + L / R
Incrementa la utilización
en un factor de 3!
3 × 𝐿ൗ𝑅 0.024
𝑈𝑒𝑚𝑖𝑠𝑜𝑟 = = = 0.0008
𝐿
𝑅𝑇𝑇 + ൗ𝑅 30.008
3-26
Protocolos encauzados
Regresar a N: Repetición selectiva:
El emisor puede tener hasta N El emisor puede tener hasta
paquetes sin confirmar en el N paquetes sin confirmar en
cauce el cauce
El receptor solo envía ACKs El receptor confirma paquetes
acumulativos individuales
No confirma un paquete si existe El emisor mantiene un
un espacio temporizador por cada
El emisor tiene un temporizador paquete sin confirmar
para el paquete mas viejo sin Cuando expira el
confirmar temporizador, retransmite
Si el temporizador expira, solo el paquete no
retransmite todos los paquetes confirmado
no confirmados
3-27
Regresar a N
Emisor:
#sec de k bits en encabezado de paquete
“Ventana” de hasta N, paquetes consecutivos sin confirmar permitidos
ACK(n): Confirma todos los paquetes hasta #sec n inclusive – “ACK
acumulativo”
Puede recibir ACKs duplicados (ver receptor)
Timer para cada paquete en camino
timeout(n): Retransmite el paquete n y todos los paquetes con #sec mayor
en la ventana
3-28
Regresar a N: FSM extendido del emisor
rdt_send(data)
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum)
start_timer
nextseqnum++
}
L else
refuse_data(data)
base=1
nextseqnum=1
timeout
Esperar start_timer
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
rdt_rcv(rcvpkt) && corrupt(rcvpkt) …
udt_send(sndpkt[nextseqnum-1])
L
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else
start_timer 3-29
Regresar a N: FSM extendido del receptor
default
udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
L
expectedseqnum=1 Wait extract(rcvpkt,data)
sndpkt = make_pkt(0,ACK,chksum) deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++
ACK-only: siempre envía un ACK por paquete correctamente recibido con
el mayor #sec en orden
Puede generar ACKs duplicados
Solo necesita recordar expectedseqnum
Paquetes fuera de orden:
descartar (no poner en buffer) -> no requiere buffer en el receptor!
Reconfirmar el paquete con el mayor #sec en orden
3-30
Regresar a N en acción
3-31
Repetición selectiva
El receptor confirma individualmente todos los
paquetes correctamente recibidos
Pone en buffer los paquetes, según se requiera, para su
eventual entrega ordenada a la capa superior
El emisor solo reenvía los paquetes para los cuales no
se recibió un ACK
Un timer por cada paquete no confirmado en el emisor
Ventana del emisor
N #sec consecutivos
Limita los #sec de paquetes enviados sin confirmar
3-32
Repetición selectiva: ventanas de emisor y
receptor
3-33
Repetición selectiva
Emisor Receptor
Datos desde arriba : Paquete n en [rcvbase, rcvbase+N-1]
Si el siguiente #sec disponible enviar ACK(n)
esta en la ventana, enviar Fuera de orden: buffer
paquete En orden: entregar (también
Timeout(n): entregar paquetes ordenados
Reenviar paquete n, reiniciar en buffer), avanzar la ventana al
timer siguiente paquete por recibir
ACK(n) en [sendbase,sendbase+N]: Paquete n en [rcvbase-N,rcvbase-1]
Marcar paquete n como recibido Paquete duplicado. Enviar
Si n es el paquete menor sin
ACK(n)
confirmar, avanzar la base de la En otro caso:
ventana al siguiente #sec sin Ignorar paquete
confirmar
3-34
Repetición selectiva en acción
3-35
Repetición selectiva:
dilema
Ejemplo:
#’s sec: 0, 1, 2, 3
Tamaño de ventana=3
El receptor no ve ninguna
diferencia en los dos escenarios!
Erroneamente pasa datos
duplicados como nuevos en (a)
Preg: ¿Que relación existe entre el
tamaño de #sec y el tamaño de la
ventana?
3-36
