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

Grado en Ingeniería en Tecnologías de

Telecomunicación, 2º


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



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



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



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 CSMA/CD, persistencia
3. 
4.  CSMA/CA

Ideas y clasificación de protocolos MAC

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



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



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)


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



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…


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



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


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



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


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



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)

que le llegue)

–  Si recibe un ACK la considera transmitida (y pasa a transmitir la siguiente
–  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
•  La trama se puede corromper por ruido o por mezclarse con otra trama
•  Cualquier solpamiento de dos tramas causa una colisión

enviada por otra estación (colisión)

a transmitir la siguiente que le llegue)

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)


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

l



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

i

I


e
d



a
e
r
Á

•  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


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



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

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

estropea el envío

parámetro 2mNλ

•  Probabilidad de 0 llegadas en ∆t=2m


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

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


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

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%


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



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

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



l



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

i

I


e
d



a
e
r
Á

slot

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

•  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


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

l



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

i

I


e
d



a
e
r
Á

ALOHA ranurado
•  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


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



l



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

i

I


e
d



a
e
r
Á

Tiempo de propagación
•  Estábamos suponiendo en los dibujos que el tiempo de
•  ¿Que pasa si no lo es?

propagación era pequeño

Nada. Es más difícil 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


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

l



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

i

I


e
d



a
e
r
Á

ALOHAs resumiendo

de forma simple

•  Resuelven el problema de acceso al medio
•  No son demasiado eficientes (máximos de
•  Funcionan independientemente de que el

18%-36%)

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

•  ¿Podemos mejorar esto?


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



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