PDF de programación - Acceso al medio (3) CSMA/CD

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

Acceso al medio (3)

CSMA/CD

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
Á

CSMA

• CSMA con carga moderada
• Se acerca al limite

Menos colisiones por menor tiempo
vulnerable

• Pero en carga alta hay colisiones y se

desperdicia el tiempo del canal

g =

1

1 + a

• El goodput cae por este tiempo

desperdiciado

,

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
Á

Idea CSMA/CD

• Con CSMA, la colisión 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 colisión

• En Bus

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

estación detecto colisión

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

• En topología en estrella

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

• En inalámbrico…

– Es un poco difícil en ese caso…

,

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

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
Á

Prestaciones CSMA/CD

• El goodput se mantiene mejor en carga elevada
• Hay colisiones pero dejan libre el canal para que otras

estaciones lo usen

• El modelo matemático es complejo, pero nos acercamos

mas al limite teórico

CSMA/CD

CSMA

ALOHAs

,

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
Á

Tamaño mínimo de trama

• CSMA/CD en Ethernet
• Para garantizar que todas las colisiones se detecten

– Si una estación empieza a transmitir y va a

producirse una colisión queremos asegurarnos de
que se de cuenta antes de acabar de transmitir

– Para poder retransmitir la trama

Problema
La trama enviada por
A no ha llegado a B
Pero A no ha detectado
colisión
Como se arregla?

t

A

B

C

,

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
Á

Tamaño mínimo de trama

• Caso peor

– A y C todo lo alejados que pueden estar (distancia máxima

Ethernet 2500m 4 repetidores y 500m en 10Base5)
tprop=5*500m/200e6m/s=12.5µs + 3µs(repetidor)*4 = 24.5µs

– A envía la trama más pequeña L
– C empieza a enviar justo antes de llegarle la trama de A

A

C

La trama más
pequeña
enviable debe
de tener este
tamaño

2*tprop=49µs
El estandar toma
57.6µs para tener
un poco de margen

t

L=Vtx*2*tprop

,

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
Á

Tamaño mínimo de trama

• V=10Mbps Lmin=576bits=72bytes 8pre+14+ 46datos +4crc

512 bits mas el preambulo

• De ahi viene el tamaño mínimo de trama Ethernet

• Se toma el tiempo de transmision de 512bits como slot ethernet, el

tiempo básico para los algoritmos de detección de colisiones.
En el tiempo de 1 slot se puede asumir que cualquier trama que
empecemos a transmitir habrá empezado a llegar a toda la red.
Si la trama ha colisionado, en ese tiempo ya se habra detectado la
colisión y los participantes habrán desistido de transmitir

• El slot es dependiente de la velocidad

10Base slot 512bits 51.2µs
100Base slot 512bits 5.12µs
1000Base slot 4096bits 4.09µs

,

a Recuperación de la colisión
• Una vez que detectada colisión en un

c
i
t

tiempo menor que 1slot los
participantes que intentaban transmitir
han desistido...

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
Á

• Y qué hacen ahora?
• Si reintentan los dos a la vez volveran a

colisionar

,

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 llevan tiempo reintentando un envío

– Captura del canal

,

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
Á

Conclusiones

• CSMA/CD

– Permite aproximar la eficiencia del canal al limite

teórico (dependiente de a)

• Se usa en redes reales Ethernet 10,100,1000 para

medio compartido

• ¿Y si no podemos detectar colisiones?