PDF de programación - Acceso al medio

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

Acceso al medio

Area de Ingeniería Telemática
http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

3º Ingeniería de Telecomunicación

a
c

i
t

Temario

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

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

a
c

i
t

Temario

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

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

1/37

2/37

1

3/37

4/37

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

,



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

I

I

I



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



I

á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

• Pero… ¿y si hay varios intentando enviar a la vez?
• Problema del Acceso al Medio

Mecanismos de esperas, colisiones, turnos… (ya se
ha comentado que el de Ethernet se llama
CSMA/CD)… pero empecemos por el principio…

Problema más simple

a
c

i
t

,



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

I

I

I



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

I



a
c

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

Material

Capítulo 16 de

W. Stallings,
Data and Computer Communications

Capítulo 7 de
S. Keshav
An Engineering Approach to
Computer Networks

Acceso al medio

a
c

i
t

• Red basada en un medio compartido (de broadcast)

– Todos oyen lo que envío
– Para enviar una trama a un nodo concreto indico su

dirección (nivel de enlace/ethernet)

• Se planteo originalmente en redes por radio
• N estaciones que pueden enviar y recibir tramas por radio
• Las estaciones tienen mensajes para otras estaciones

Nivel de enlace
Generan paquetes a enviar de forma aleatoria… caracterizadas
por una variable aleatoria y con tasa media de λ tramas por
unidad de tiempo

• ¿Cuantas tramas podemos conseguir que lleguen a su destino?

N

λ

s1

λ

s2

λ

s3

λ

sn

5/37

2

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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



I

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Primera aproximación

a
c

• Si tengo un paquete para transmitir… lo envío

– Si tengo suerte llegara
– Si otro transmite a la vez no llegara ninguno de los dos
– Si en media el tiempo que tarda en llegar el siguiente paquete a

alguien es menor que el tiempo que tardo en transmitirlo bastantes
llegaran a sus destinos

Supongamos que el tiempo de propagación es muy pequeño…

s1

s2

sN

Tiempo medio 1/λ

t

perdidos

t1

t2

t3

t4

t4 t5

t6

6/37

a
c

i
t

ALOHA

• Desarrollado para redes de paquetes por radio
• En la universidad de Hawai
• Cuando la estación tiene una trama para transmitir… la envía
– La trama incluye la identificación del destino que debe recibirla
– La trama incluye un codigo de detección de errores (Frame Check

Sequence)

• Si recibo una trama correctamente (FCS=ok) envío una trama de

confirmación (ACK) al emisor
– La trama de ACK es un trama pequeña (poco mas que el destino y una

indicación de que es un ACK)

• Despues escucha durante un tiempo (un poco mas que el máximo RTT)

– Si recibe un ACK la considera transmitida (y pasa a transmitir la siguiente

que le llegue)

– Si no recibe un ACK vuelve a enviar la misma
– Si lleva n intentos de retransmisión sin recibir ACK la da por perdida (y pasa

a transmitir la siguiente que le llegue)

•

La trama se puede corromper por ruido o por mezclarse con otra trama
enviada por otra estación (colisión)

• Cualquier solpamiento de dos tramas causa una colisión

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Prestaciones ALOHA

a
c

i
t

• N estaciones
• Mensajes de tamaño fijo s bytes
• Capacidad del canal C bytes/segundo
• Cada estación genera mensajes siguiendo una proceso de

Poisson con parámetro λ (en media λ mensajes por segundo)

• Los mensajes ocupan el canal un tiempo fijo m=s/C
• La carga ofrecida (intensidad de tráfico) al medio compartido

será
Una estación:
Todas las estaciones:

ρi = m λ
ρ = N m λ

• Ej: Mensajes de 200B enviados a 1Mbps m=1.6ms

N=20 λ=5mensajes/s ρ = 0.16 16% del tiempo ocupado
N=20 λ=20mensajes/s ρ = 0.64 64% ¿muchas perdidas?
N=40 λ=20mensajes/s ρ = 1.28 128% No caben

7/37

8/37

3

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



,



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

I

a
c

i
t

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Prestaciones ALOHA

a
c

• ¿Cual es la probabilidad de que un mensaje llegue al otro extremo?

P[llegar]=P[no haya otro paquete “cerca”]

t

Tiempo vulnerable 2m

• Un paquete desde m segundos antes hasta m segundos despues nos

estropea el envío

• Numero de paquetes que llegan en ∆t=2m es un v.a. de Poisson con

parámetro 2mNλ

• Probabilidad de 0 llegadas en ∆t=2m

Prestaciones ALOHA

• Tráfico ofrecido ρ = Nmλ
• Mensajes que llegan λ’= λP[llegar]= λe-2mNλ
• Tráfico aprovechado (cursado, goodput)

g = Nmλ’ = Nmλe-2mNλ = ρe-2mNλ = ρe-2ρ

g=f(ρ)

9/37

10/37

Prestaciones ALOHA

a
c

i
t

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

• Máximo goodput ~ 18% (para ρ=50%)
• No parece muy eficiente
• Si transmitimos al canal 1Mbps como mucho tendremos
180Kbps para repartir entre todos los que transmitan…

• Por otra parte si la velocidad es aceptable ALOHA resuelve el

problema del acceso al medio

g max 18%

ρ=16%

ρ=64%

ρ=128%

11/37

4

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á



I

I

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



I

Mejorando ALOHA

a
c

• Mejora tipica ALOHA ranurado
• Dispositivos sincronizados en el tiempo. Existen intervalos

temporales (slots) conocidos por todas las estaciones
Slots de la duración de la trama

• Algoritmo: Igual que ALOHA

– Salvo que sólo se puede empezar a transmitir al principio del slot.
– Si un paqute se genera en un slot deberá esperar a que comience
t

el siguiente

Esperan al comienzo
del intervalo

s1

s2

sN

Se generan
mensajes

ALOHA ranurado

a
c

i
t

,



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

I



I

I

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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

• La trama colisionará con los paquetes que llegan en el mismo

slot

• Si llegan cerca pero en el siguiente slot esperarán
• El tiempo vulnerable es ahora m
• La probabilidad de no colisionar es ahora la probabilidad de que

se produzcan 0 llegadas en un tiempo m

t

Tiempo vulnerable m

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

ALOHA ranurado

a
c

i
t

• El goodput en función de la carga ahora sera g = ρe-ρ
• Mejora el de ALOHA
• El máximo alcanzable es ahora ~36%

• Desventaja: es más complejo, tener sincronización en los nodos

no siempre es facil

g max ~36%

ALOHA ranurado

ALOHA

12/37

13/37

14/37

5

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



Tiempo de propagación

a
c

• Estabamos suponiendo en los dibujos que el tiempo de

transmisión era pequeño

• ¿Que pasa si no lo es?

Nada. Es más dificil de dibujar. Pero ALOHA funciona igual

• De hecho protocolos de tipo ALOHA se usan en escenarios de

comunicación por satélite

• El análisis de las colisiones es equivalente, lo que importa son

los tiempos en los que las tramas llegan al receptor
– Si llegan a la vez habrá colisión

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

ALOHAs resumiendo

a
c

i
t

• Resuelven el problema de acceso al medio

de forma simple

• No son demasiado eficientes (máximos de

18%-36%)

• Funcionan independientemente de que el

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

• ¿Podemos mejorar esto si el tiempo de

propagación es pequeño comparado con el
de transmisión?

,



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

I

I

I



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

I



á
m
e
e
T

l



a

i

í
r
e
n
e
g
n

I


e
d



a
e
r

Á

Mejorando ALOHA

a
c

i
t

• ¿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?

15/37

16/37

17/37

6

,



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

I

i
t
á
m
e
e
T

l

i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

I

I



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

I



a
c

CSMA

• CSMA (Carrier sense multiple access)

•

Acceso múltiple con detección de portadora
Tiempo de propagación corto: Las estació