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

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

Acceso al medio (2)

CSMA

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º

,

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

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
8. Programación para redes y servicios

,

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

1.
2. Arquitecturas de conmutación y protocolos
3.
4. Control de acceso al medio

Introducción a las tecnologías de red

1. ALOHA y ALOHA ranurado
2. CSMA y variantes, persistencia
3. CSMA/CD
4. CSMA/CA
5.

Ideas y clasificación de protocolos MAC

5. Conmutación de circuitos
6. Transporte fiable
7. Encaminamiento
8. Programación para redes y servicios

,

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 ultima clase...

ALOHAs

de forma simple

18%-36%)

• Resuelven el problema de acceso al medio

• 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
Á

El parámetro a

• Relación tiempo de propagación y transmision

t

t

a alto

a bajo

Prestaciones

• Si veo que alguien esta transmitiendo no transmito,

El tiempo vulnerable de colisión es menor

,

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
Á

A

B

Si B transmite antes A
detectara portadora y no
transmitira
Si B transmite ahi
habra colisión
Si B transmite despues
vera a A y no transmitira

t

El tiempo vulnerable ya no es 2*m
mas bien es a*m

t

m

,

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
Á

Prestaciones

• Menor tiempo vulnerable

= menos probabilidad de colisión
= mas goodput

CSMA
Mayores valores
que ALOHAs
pero depende de a

En carga muy alta
acaba habiendo
colisiones todo el
tiempo y cae como
ALOHA

,

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
Á

Prestaciones CSMA ideal

• CSMA en el caso ideal

Transmisión durante un tiempo m (=ttx)
Tiempo vulnerable ~am ~2am se desperdicia
No hay colisiones
Carga alta

am m

• Segun el tiempo que
perdamos en media

g =

m

m + am

g =

m

m + 2am

=

=

1

1 + a

1

1 + 2a

Resumen eficiencia ALOHA

,



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



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• Goodput

• ALOHA

⌘ = ⇢e2⇢

Máximo 18% para un carga de aprox ρ=0.5
Independiente del tiempo de propagación

• ALOHA ranurado

⌘ = ⇢e⇢

Máximo de 36% para una carga de aprox ρ=1.0
Independiente del tiempo de propagació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
Á



Resumen eficiencia de CSMA
• Eficiencia de CSMA ideal

• Hay aproximaciones para el limite en carga alta

que dependen del parametro a

• No son exactas depende de lo que transmitan

las estaciones, del algoritmo de persistencia
pero vale para hacernos una idea del orden

ALOHA vs CSMA

,

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



I

a
c
i
t

l



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

i

I



e
d
a
e
r
Á

• ¿Podríamos decir que ALOHA era la forma antigua y CSMA lo ha

sustituido ya que es más eficiente?

• NO
• El orden de exposición ha sido ese y ALOHA apareció primero
• CSMA es una evolución adaptada para mejorar en el caso

tpropagación<<ttransmision

Tipico en LANs pero no siempre se cumple
• Parámetro a= tpropagación/ttransmision


• Variantes de ALOHA se usan hoy en dia

a<<1 CSMAs tienen sentido y su eficiencia es mejor que la de ALOHA
a>1 ALOHA es simple y su eficiencia no depende de a

• En telefonía movil para realizar peticiones de recursos
• En comunicaciones vía satelit