PDF de programación - Acceso al medio (2)

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

Acceso al medio (2)

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

3º Ingeniería de Telecomunicació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
Á

Temario

Introducción

•
• Arquitecturas, protocolos y estándares
• Conmutación de paquetes
• Conmutación de circuitos
• Tecnologías
• Control de acceso al medio en redes de área local
• Servicios de Internet

,

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
Á

Temario

Introducción

•
• Arquitecturas, protocolos y estándares
• Conmutación de paquetes
• Conmutación de circuitos
• Tecnologías
• Control de acceso al medio en redes de área local
• Servicios de Internet

,

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
Á

En la última clase

• Acceso al medio de tipo ALOHA
• Resuelven el problema de acceso al medio

de forma simple

18%-36%)

• No son demasiado eficientes (máximos de

• Funcionan independientemente de que el

tiempo de propagación sea grande o
pequeño comparado con el de transmisión

• ¿Podemos mejorar esto?

,

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
Á

Mejorando ALOHA

• ¿Podemos mejorar el protocolo si el tiempo de
propagación es pequeño comparado con el de
transmisión?

• Hay una mejora obvia…
Mirar antes de enviar

– Solo tiene sentido si la transmisión se mantendrá más

tiempo que el que tardo en decidir si hay una transmisión

es decir (propagación << transmisión)

• Y qué hago si el medio esta ocupado?
– Espero a que este libre y envío entonces?
– Espero un tiempo aleatorio?

a
c
i
t

CSMA

• CSMA (Carrier sense multiple access)

•

Acceso múltiple con detección de portadora
Tiempo de propagación corto: Las estaciónes
saben rápido si otra estación está
transmitiendo
Primero escucha y espera a que el medio
este libre (Carrier Sense)
Si el medio esta libre -> transmite
Si no espera

Aun así puede haber colisiones porque el
tiempo de propagación no es cero
Si dos estaciones empiezan a transmitir al
mismo tiempo (aproximadamente por el
tiempo de propagación)
= COLISION

La utilización máxima depende del tiempo de
propagación (longitud del medio) y de la
longitud de la trama

,

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
Á

•

•


•



•

,

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
Á

Variaciones de CSMA

Surgen de contestar a estas preguntas
• ¿Qué hago si el canal esta libre?
• ¿Qué hago si se produce a pesar de

todo una colision?

,

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
Á

CSMA No persistente

• Reglas:

– Si el medio esta libre, transmitir
– Si el medio esta ocupado, espera un tiempo generado con una

distribucion de probabilidad (retardo de retransmisión) e intentalo
de nuevo

• Ventaja
El retardo aleatorio reduce la probabilidad de colisión
• Pero…
Se desperdicia capacidad porque el medio se queda libre

después de una transmisión

• Las estaciones no persistentes son respetuosas

Ocupado

Me olvido por entre 0-100 ms

t

Y otros que llegan despues
quizas me adelanten

,

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
Á

CSMA 1-persistente

• Evita que el canal quede libre
• Reglas

– Si el medio esta libre transmitir
– Si el medio esta ocupado espera hasta que este libre; entonces

transmite inmediatamente

• Ventaja:
Aumenta la utilización del canal (no se desperdicia tiempo)
• Pero…
Si hay 2 o mas estaciones esperando la colision esta

garantizada

• Las estaciones 1-persistentes son egoistas

Ocupado
En cuanto acabe…

Pero si dos están
Esperando hay
colisiones garantizadas

t

Nadie me adelanta

,

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
Á

CSMA p-persistente

• Compromiso para intentar reducir las colisiones y que el canal no

quede vacio

• Reglas:

– Si el medio está libre transmite con probabilidad p y espera una unidad de

tiempo con probabilidad (1-p)

– Si el medio está ocupado espera hasta que este libre y repite el paso 1
– Si la transmisión se retrasa una unidad de tiempo repite el paso 1

• Pendiente: elegir el valor efectivo de p para evitar inestabilidad en alta

carga

,

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
Á

Valor de p?

•
•

•

•

•

n estaciones esperando transmitir
Al final de la transmision el numero esperado de estaciones
sera np
– Si np>1 en media habra una colision
Si hay una colisión esas n estaciones se sumaran a las que
lleguen nuevas y aumenta la probabilidad de colision
Eventualmente todas las estaciones intentan retransmitir y el
throughput tiende a cero
Asi que debe cumplirse que np<1 para los picos esperados de
n
– Si esperamos mucha carga, p debe ser pequeño
– Pero p pequeño quiere decir que las estaciones esperan mucho

para transmitir

,

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
Á

Qué algoritmo de persistencia?

IEEE 802.3 (Ethernet) usa 1-persistente

•
• No persistente y p-persistente tienen problemas de eficiencia
• 1-persistent parece más inestable que p-persistente

– Porque las estaciones son egoistas
– Pero el tiempo desperdiciado en las colisiones es pequeño

• Se puede solucionar utilizando un tiempo de backoff (tiempo sin

volver a intentarlo)
– Con un tiempo de backoff aleatorio es poco probable que vuelvan a

colisionar de nuevo en el siguiente intento

• También se puede recuperar el tiempo de la colisión:
Detección de colisiones

,

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
Á

CSMA/CD

• Con CSMA, la colision ocupa el medio durante el

tiempo de transmisión

• Se puede mejorar si las estaciones son capaces de

recibir a la vez que transmiten
– No siempre es posible
– Determinado hardware por ejemplo antenas o receptores no

permiten a la vez enviar y escuchar el medio

• CSMA/CD reglas:

– Si el medio está libre transmitir
– Si está ocupado esperar a que este libre y transmitir
– Si veo una colision dejar de transmitir
– Despues esperar un tiempo aleatorio y retransmitir

• CD = Detección de colision (collision detection)

,

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
Á

Detección de colision

• Bus en banda base

– La colision produce mayor voltaje
– Si la señar del cable es mayor que la que esta generando la

estación detecto colision

– La señal se atenua con la distancia
– Limite de 500m (10Base5) o 200m (10Base2)

• En par trenzado (topología en estrella)

– Actividad en más de un puerto es una colision
– Se usa una señal especial para indicar colisión

a
c
i
t

CSMA/CD

,

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
Á

,

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
Á

CSMA/CD

• Cada dispositivo para al detectar la colision

colisión

colisió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
Á

Backoff

• Antes de volver a transmitir en muchos protocolos se espera un

tiempo aleatorio

– Normalmente para evitar la coincidencia de varias estaciones que

puedan querer transmitir a la vez

Le llamaremos backoff

– Por ejemplo en ALOHA se usa despues de una trama errónea

para no volver a colisionar

– Consigue efectos parecidos al CSMA p-persistente

• Lo más simple es elegir un número aleatorio uniforme en un

rango conocido

• En CSMA/CD se complica un poco

No hay confirmacion

Tiempo aleatorio t1

No hay confirmacion

Tiempo aleatorio t2

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



c
i
t

l



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

i

I


e
d



a
e
r
Á

a Binary Exponential Backoff

,

IEEE 802.3 y Ethernet usan binary exponential backoff

•
• Las estaciones reintentan el envío de las tramas que colisionan
– Tiempo básico de espera 512bits en 10 o 100Mbps (51us o 5.1us)
– En los 10 primeros intentos el tiempo medio de espera se dobla

0-1 x 51us -> 0-4 x 51us -> 0-8 x 51us -> ...

– En los 6 siguientes el tiempo medio se mantiene constante
– Despues de 16 colisiones la estacion desiste y da error para esa

trama

• El algoritmo 1-persistente con binary exponential es eficiente

para un amplio rango de cargas
– Poca carga, ocupa el canal inmediatamente
– Mucha carga, espera más tiempo y hay menos colisiones

• Problema: el backoff tiene un efecto last-in, first-out

– Las estaciones con tramas nuevas tienen preferencia sobre las

que ya llev