PDF de programación - Acceso al medio (1) Intro y ALOHA

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

Acceso al medio (1)

Intro y ALOHA

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
Á

Material

Capítulo 16 de
W. Stallings,
Data and Computer Communications

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

Computer Networks

Capitulo 5 de
J.F. Kurose & K.W. Ross
Computer Networking. A top-down

approach featuring the Internet

Acceso al medio

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

,

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
Á

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

,

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
Á

Problema más simple

• 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

,

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
Á

Primera aproximación

• 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

,

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
Á

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

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 Midiendo las prestaciones

,

• La entrada al sistema son todos los paquetes que se intentan

enviar pero no todos se reciben

• Como de eficiente es la red
• Cuanto tráfico puede atravesar la red??

ALOHA

• Como se mide?
• Capacidad y Carga

Carga=lo que intenta pasar

Capacidad=lo que puede pasar

Carga<Capacidad = no problema

a Midiendo las prestaciones

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
Á

ALOHA

Carga=lo que intenta pasar

• Capacidad

Capacidad=lo que puede pasar

Los recursos de la red. El limite físico de lo que se podría transmitir en
el mejor caso.
Transmisor de 20Mbs -> en el caso ideal 20Mbps para repartir

• Carga (Intensidad de tráfico)

Cantidad de servicio pedido al sistema.
Puede ser más que la capacidad

• Calidad de servicio

Servicio obtenido del sistema
¿Que hacemos con lo que no podemos transmitir?
Perderlo? Acumularlo?

,

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
Á

Midiendo el tráfico

• N estaciones
• Cada una genera λ tramas por segundo
• Cada trama ocupa el canal un tiempo m=tamaño/C [b]/[b/s]=[s]
• ¿Cuanto tiempo haría falta para enviar todo el trafico que se genera en

un segundo?
tdemanda=N λ m

• Medida de la carga independiente de la capacidad

•

Intensidad de tráfico

I =

Volumen de tráfico

Tiempo de observación

• Sin unidades físicas. Se mide en Erlangs (E) (Agner Krarup Erlang

1878-1929)
1 Erlang = el tráfico que mantiene ocupado completamente un canal
durante el tiempo de observación
Intensidad de tráfico media: empleando el volumen medio de tráfico en
el intervalo de observació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 ALOHA

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

ρi = m λ
ρ = N m λ

Una estación:

Todas las estaciones:
• Ej: Mensajes de 200B enviados a 1Mbps m=1.6ms
N=20 λ=5mensajes/s ρ = 0.16 E 16% del tiempo ocupado
N=20 λ=20mensajes/s ρ = 0.64 E 64% ¿muchas perdidas?
N=40 λ=20mensajes/s ρ = 1.28 E 128% No caben

,

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 ALOHA

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

,

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 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(ρ)

,

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 ALOHA

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

,

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

• 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 paquete se genera en un slot deberá esperar a que comience
t

el siguiente

Esperan al comienzo
del intervalo

s1

s2

sN

Se generan
mensajes

,

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
Á

ALOHA ranurado

• 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

,

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