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

Redes

4º Ingeniería Informática

a
c
i
t

l



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

i

I


S
E
D
E
R

e
d



a
e
r
Á

Hoy...

1. Introducción a las redes
2. Tecnologías para redes de área local
3. Conmutación de circuitos
4. Tecnologías para redes de área extensa y última milla
5. Encaminamiento
6. Arquitectura de conmutadores de paquetes
7. Control de acceso al medio
• Transporte extremo a extremo

,

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

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

3/34

,

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

4/34

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…

5/34

,

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

6/34

,

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

7/34

,

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

8/34

,

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á

Una estación:

Todas las estaciones:
• Ej: Mensajes de 200B enviados a 1Mbps m=1.6ms
N=20 λ=5mensajes/s

ρi = m λ
ρ = N m λ

ρ = 0.16 16% del tiempo

ocupado

N=20 λ=20mensajes/s ρ = 0.64 64% ¿muchas perdidas?

9/34

,

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λ

10/34

,

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

11/34

,

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%

12/34

,

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

13/34

,

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

Tiempo vulnerable m

t

14/34

,

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

• 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

15/34

,

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
Á

Tiempo de propagación

• Estábamos suponiendo en los dibujos que el tiempo de

propagación era pequeño

• ¿Que pasa si no lo es?
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

16/34

ALOHAs resumiendo

• Resuelven el problema de acceso al medio

• No son demasiado eficientes (máximos de

,

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
Á

de forma simple

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?

17/34

,

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?

18/34

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

•

•


•



•

,

I

I



S
E
D
E