PDF de programación - Transporte fiable Ventana deslizante y go-back-N

ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS
Área de Ingeniería Telemática

Transporte fiable

Ventana deslizante y go-back-N

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

Grado en Ingeniería en Tecnologías de

Telecomunicación, 2º

a
c
i
t

Temario

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Introducción

Introducción a las tecnologías de red

1.
2. Arquitecturas de conmutación y protocolos
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6. Transporte fiable
7. Encaminamiento

2

a
c
i
t

Temario

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Introducción

Introducción a las tecnologías de red

1.
2. Arquitecturas de conmutación y protocolos
3.
4. Control de acceso al medio
5. Conmutación de circuitos
6. Transporte fiable
7. Encaminamiento

3

Nota sobre las unidades

a
c
i
t

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

• 1 byte son 8 bits (1B=8b)
• Aunque midiendo memoria se suelen usar prefijos k,M,G,T en

potencias de 2
(por ejemplos k para 210=1024 M para 220=1048576 )
No es correcto. Hay un estandar para esto
KiB = 1024B MiB =1048576

• En transmisión de datos se usan los prefijos del S.I.

1kB = 103B 1MB = 106B 1GB = 109B ...

• Las velocidades de transmisión se suelen dar en bits por

segundo (kbps, Mbps...). Cuidado con la diferencia entre B y b
1MBps=1MB/s=8Mbps=8Mb/s

• Ejemplo en Ethernet la velocidad es 10Mbps. Un paquete

de1000B se transmite en (1000B*8b/B)/10Mbps=0.0008s=0.8ms

4

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Stop & wait: prestaciones

Los protocolos de tipo stop & wait garantizan transporte fiable pero tienen poca eficiencia
en enlaces en los que el RTT es grande comparado con el tiempo de transmisión de un
paquete

En el caso mejor transmitimos un paquete cada RTT
por lo que el throughput de datos máximo es
tamañodepaquete/RTT
Si hay perdidas aun menos

Puede ser aceptable en los casos en los que RTT y tiempo de transmisión del ACK es
despreciable comparado con el tiempo de transmisión, pero necesitamos protocolos
capaces de enviar a más velocidad sobre enlaces con velocidad de transmisión alta

•

•

•

•

5

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Protocolos más eficientes

a
c
i
t

• Para aumentar la eficiencia, se envían varios paquetes

(ventana de paquetes) mientras llega el ACK
Varios paquetes en la red por confirmar
– Se usan más números de secuencia que 0 y 1
– Emisor y receptor necesitarán buffer para varios paquetes
– Varias políticas para reaccionar a los errores

• Go-Back N
• Selective repeat
• Los dos son conocidos tambien

como Ventana deslizante
(sliding window)

Emisor
paq 0
paq 1
paq 2
paq 3

Receptor

ack 0

6

Protocolo Go back-N

Empezando por lo más simple:

•
• Número de secuencia en el paquete
•
• Cada ACK confirma todos los paquetes anteriores

Se permite una ventana de N paquetes sin confirmar

(cumulative ACK)
Timeout al iniciar la ventana
Si caduca el timeout se retransmite la ventana

,

I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

•
•

•

•

Estado en el emisor
base= numero de secuencia mas bajo que aun no ha sido confirmado
nextseqnum= siguiente numero de secuencia que voy a usar
buffer con los paquetes enviados hasta que se confirmen y los descarte
Estado en el receptor
expectedseqnum= siguiente numero de secuencia que espero recibir

7

Eventos en el emisor (Go back-N)

,



I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I



I

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

• Recibo datos de la aplicación

– Si puedo enviar ( nextseqnum<base+N )

• Envia el paquete
• Si es el primero ( nextseqnum==base )

– Inicia temporizador

• nextseqnum++

– Si no puedo enviar ( nextseqnum==base+N )

• Rechazar el dato de la aplicación
• La aplicacion tendra que esperar (normalmente
tiene un buffer para que los paquetes esperen a
que se puedan enviar)

8

Eventos en el emisor (Go back-N)

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

I

a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

• Recibo un ACK (de ack_seq)

– Avanza la ventana hasta la posición confirmada

(base=ack_seq)

– Si aun quedan paquetes pendientes recalcular el

temporizador

– Al aumentar base puede enviar los siguientes paquetes

que de la aplicación hasta llenar la ventana

• Caduca el timeout del primer paquete de la

ventana
– Reenvía todos los paquetes enviados en la ventana

(desde base hasta nextseqnum-1)

– Reinicia el temporizador

9

Eventos en el emisor (Go back n)

enviados
no ACKed

se pueden
enviar

base+N

,

a
c
i
t

• Ventana deslizante

base

nextseqnum



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

transmitidos
ACKed

Ventana de N paquetes

no se pueden
enviar

Llega este ACK

Timeout del primer paquete

pueden enviarse
nuevos paquetes

La ventana se desliza hacia
mayores números de secuencia

Volvemos a enviar

10

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Eventos en el receptor (Go back-N)
• Llega el paquete esperado

– Envía un ACK indicando el siguiente esperado
– Entrega datos al nivel superior

• Llega otra paquete

– Envía un ACK indicando el paquete que estoy

esperando

– Descarta los datos

11

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Go back-N

Ventana de 4 paquetes

Emisor
paq 0
paq 1
paq 2
paq 3
paq 4
paq 5

timeout paq 2
paq 2
paq 3
paq 4
paq 5

...

Receptor

Ok 0
Ok 1

ack 1
ack 2

ack 2
ack 2
ack 2

Ok 2
Ok 3
Ok 4

ack 3
ack 4
ack 5

12

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I



I



a
c
i
t

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

Resumen Go-back N

• Simple (¿sabríais programarlo?)
• Más eficiente que stop & wait
• ¿Cuál es la velocidad máxima?
• N s / RTT ?
• ¿y si el tiempo de transmisión no es

despreciable?

• Mejoras fáciles a go-back N?

13

Velocidad de go-back N

a
c
i
t

,



I



I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á



• Supongamos que la aplicación

envía constantemente,
siempre hay datos pendientes

• Enviamos

w=N s bytes cada RTT
• La ventana empieza a

repetirse en cuanto recibimos
el primer ACK, no el último

• La velocidad máxima es

w/RTT N s/RTT

• Pero solo si la ventana se
envía entera antes de que
vuelva un ACK

Emisor

w1

Receptor

RTT

w2

w3

14

Velocidad de go-back N

a
c
i
t

,

I



I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

• Si hay errores habrá timeouts

y retransmisiones

• Si la aplicación no envía datos

irá mas despacio

Emisor

Receptor

RTT

• w/RTT es un limite del

protocolo.
Depende del valor que
elijamos para N y s

• Analizar las prestaciones de

estos casos es más difícil

15

Velocidad de go-back N

a
c
i
t

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S



I

l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

I

• Puede que no de tiempo a
enviar la ventana antes de
que vuelva el ACK
Ejemplo con N=4
El throughput aqui es
3s/RTT<Ns/RTT

• El problema es que no nos da
tiempo a enviar w bytes en el
tiempo RTT
• Eso ocurre si

w/C > RTT o sea si C<w/RTT
• El limite es w/RTT salvo que el

canal tenga menor C (Vtx)

Emisor

Receptor

w

RTT

16

Velocidad de go-back N

a
c
i
t

,



I

I

S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á



• En resumen
• Si w < C*RTT

Emisor

Receptor

El límite de velocidad lo pone
el protocolo w/RTT
La ventana cabe en el canal

w

• Si w > C*RTT

El limite lo pone el canal
La ventana no cabe en el
canal
Estamos aprovechando al
máximo el canal

RTT

17

a
c
i
t

Conclusiones

,



I

I



S
E
D
E
R
E
D
A
R
U
T
C
E
T
U
Q
R
A

S
O
C
V
R
E
S
Y
S
A
M
E
T
S
S

I

I



l



á
m
e
e
T
a
í
r
e
n
e
g
n

i

I


e
d



a
e
r
Á

• Se pueden construir protocolos que

garantizan transporte fiable y son más
eficientes que stop & wait

• Ventana deslizante

– Go back N

• Como mejorar go-back-N

– Aprovechar los paquetes que llegan aunque

se hayan perdido los anteriores?

18