PDF de programación - Transporte fiable Selective repeat

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

Transporte fiable
Selective repeat

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

Protocolos más eficientes

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
Á

• 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

4

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

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



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?

6

,

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
Á

Mejoras a Go-back N
• Aprovechar los paquetes que llegan

aunque se hayan perdido los anteriores?
– Receptor más complicado. Necesita buffer

para los paquetes recibidos pero no
entregados a la aplicación

– Reenviar si se reciben ACKs duplicados?

• Confirmar/rechazar paquetes por

separado

7

Selective Repeat

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
Á

• El receptor confirma (ACK) individualmente cada

paquete
– Mantiene en buffer los paquetes recibidos a la espera de
reconstruir la secuencia y pasarlos al nivel de aplicación

Ventana

paquetes recibidos que no pueden
pasarse todavía al nivel de aplicacion
• Se reenvian los paquetes no confirmados por timeout

– Timeout individual por cada paquete

• Ventana de N paquetes que pueden enviarse sin

recibir ACK

8

,

Eventos en el emisor (SR)

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
Á

• ACK recibido

– Se cancela el timeout de ese paquete
– Si se puede avanzar la ventana se avanza hasta

donde se pueda

– Si la ventana avanza se envían paquetes nuevos si

hay disponibles y se inician sus timeouts

• Timeout de un paquete

– El paquete se reenvía
– Se reinicia el timeout de ese paquete

9

,



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 (SR)
• El receptor tiene un buffer (y por tanto ventana)

limitada

• Recibidos datos en la ventana

– Se envía ACK de ese paquete
– Se guarda el paquete en su posicion del buffer
– Si el paquete es el esperado se entregan todos los paquetes

continuos disponibles en la ventana al nivel superior y se
avanza hasta donde se pueda

• Recibidos datos anteriores a la ventana

– Se ignoran los datos
– Se envía ACK de ese paquete

• Recibidos datos posteriores a la ventana

– Se ignoran y no se envía nada

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
Á

Selective Repeat

•Ventana deslizante del emisor
se pueden
enviar

confirmados
ACKed

enviados
no ACKed

transmitidos
ACKed
•Ventana deslizante del receptor

Ventana de N paquetes

no se pueden
enviar

esperados

recibidos y confirmados
en espera de poder entregarse

aceptables

confirmados
y entregados

Ventana de N paquetes

no aceptables
fuera de la ventana

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
Á

Selective repeat

Ventana de 4 paquetes

...

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

timeout

paq 2

paq 6

Receptor

ack 0
ack 1

ack 3
ack 4
ack 5

ack 2

ack 6

Aquí ACK no indica
el que espero recibir
sino indica el que confirmo 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
Á

Problemas de selective repeat
• Más complejo de programar: buffer de paquetes en
el receptor, array de temporizadores en el emisor...

• Normalmente para implementar ventanas

deslizantes el numero de secuencia es un campo
de la cabecera
– tiene un numero de bits limitado
– las reglas anteriores hay que programarlas con

contadores que se dan la vuelta

– En go-back N es facil porque con n bits puedo hacer go-

back 2n-1

– Pero en selective repeat hay algun problema...

13

El problema del selective repeat

,



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
Á

• Número de

secuencia finito

• Ejemplo

– seq= {0,1,2,3}
– N=3

• El receptor no
puede notar la
diferencia entre los
dos escenarios
• Y entrega datos
duplicados como
buenos

• Que relación debe

haber entre
#secuencia y N?

0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3

paq duplicado
entregado !!!

0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3
0 1 2 3 0 1 2 3

0 1 2 3 0 1 2 3

paq correcto
entregado

14

,

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
Á

Eficiencia Selective Repeat

• Transporte fiable garantizado (en un

escenario en el que se pierdan paquetes)

• Eficiencia mejor que stop-and-wait
• Parecida a la del go-back N
• El caso mejor es igual que en go-back N
• Si w>C*RTT

– thrmax = C

• Si w<C*RTT

– thrmax = w/RTT

• O bien

– thrmax = min{ w/RTT, C }

• Si hay errores depende de como sean
estadísticamente los errores, es más
difícil de analizar

Emisor

w1

Receptor

RTT

w2

w3

15

,



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
Á

Sesiones/conexiones

a
c
i
t

• Hasta ahora era un emisor y un receptor
• El nivel de transporte tiene que gestionar eso para diferentes sesiones

de aplicación
Los parametros de los protocolos stop&wait, go-back-N, selective
repeat,
– tienen sentido para una comunicacion entre un origen y un sentido
– una conversación son dos sentidos emisor->receptor
– un nivel de transporte tiene que gestionar varias conversaciones a

la vez
Aplicación
recibir

enviar
Emisor
Receptor

Aplicación

datos
acks

datos

acks

Receptor
Emisor

16

Sesiones/conexiones

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

• Cada pareja Emisor-Receptor necesita sus propias variables del

protocolo de ventana deslizante (base, nextseq, expectedseq, bufferes
de paquetes...)

• El nivel de transporte debe gestionar todo esto
• Sesiones de nivel de transporte (se suelen llamar conexiones)

App

App

App

E
R

E
R
E
R

App

RE

RE
R
E

App

App

17

Sesiones/conexiones

a
c
i
t

,

• Antes de empezar una comunicación hay que avisar para que se

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
Á



inicialicen las variables
App

quiero una
sesión

App
fase negociación
establecimiento
se inician variables
y buffers
expectedseq=1
...

fase transferencia

fase liberacion
cerrada

18

se inician variables
y buffers
base=1
nextseq=1
...

cierra la
sesión

datos y acks

cerrada

• El nivel de transporte incluye también protocolos para el

establecimiento y liberación de las sesiones del nivel de transporte

a
c
i
t

Conclusiones

,



I

I