PDF de programación - Enrutamiento (1)

ARQUITECTURA DE REDES, SISTEMAS Y SERVICIOS

Área de Ingeniería Telemática

Enrutamiento (1)

Area de Ingeniería Telemática

http://www.tlm.unavarra.es

Arquitectura de Redes, Sistemas y Servicios

3º Ingeniería de Telecomunicación

Basadas en el material docente de Lawrie Brown sobre el libro de
William Stallings (Data and Computer Communications)


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

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

Temario


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
Á

Introducción

1. 
2.  Arquitecturas, protocolos y estándares
3.  Conmutación de paquetes

• 
• 

Principios
Problemas básicos
• 
• 
• 
• 
• 

Como funcionan los routers (Nivel de red)
Encaminamiento (Nivel de red)
Transporte fiable (Nivel de transporte en TCP/IP)
Control de flujo (Nivel de transporte en TCP/IP)
Control de congestión (Nivel de transoporte en TCP/IP)

4.  Conmutación de circuitos
5.  Tecnologías
6.  Control de acceso al medio en redes de área local
7.  Servicios de Internet

2/30


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
Á

Enrutamiento en redes de paquetes
•  Problema clave
•  Elegir camino a través de la red de nodos
•  Características

–  corrección
–  simplicidad
–  robustez
–  estabilidad
–  justicia
–  optimalidad
–  eficiencia

compromiso

compromiso

3/30


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
Á

Criterio de prestaciones
•  Elegido para comparar rutas
•  El más sencillo “minimum hop count” = mínimo

número de saltos
–  Encontrar la ruta de con menor numero de saltos(nodos)
•  Se puede generalizar como mínimo coste (least

cost)
–  Encontrar la ruta con menor coste (peso del camino)
–  Si el peso de cada enlace es 1 es equivalente al anterior

4/30


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
Á

Ejemplo

En general grafo dirigido
con enlaces con pesos

5/30


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
Á

Ejemplo
Mínimo número de saltos (hops)
De N1 a N6

Mínimo coste
De N1 a N6

6/30


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
Á

de la red

•  Lugar

Tiempo y lugar de decisión
•  Tiempo

– Por paquete o por circuito virtual
– Fija por destino o cambia según el estado

– distribuida - cada nodo decide
– centralizada
– origen (source routing) el nodo que origina

la información elige todo el camino

7/30

Información de la red
•  Normalmente el enrutamiento requiere

conocer información sobre la red (no
siempre)
–  Enrutamiento distribuido


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
Á

•  Conocimiento local, información de nodos vecinos…

–  Enrutamiento centralizado

•  Información de todos los nodos

•  Actualización de la información sobre la red

¿Cuándo?
–  Enrutamiento estático - nunca se actualiza
–  Enrutamitneo adaptativo - actualizaciones

regulares

8/30


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
Á

Estrategias de enrutamiento
•  Enrutamiento estático
•  Enrutamiento por inundación
•  Enrutamiento aleatorio
•  Enrutamiento adaptativo

9/30


,



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



l



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

i

I


e
d



a
e
r
Á

Enrutamiento estático

•  Ruta única y permanente para cada destino
•  Se calcula con algún algoritmo de mínimo coste
•  La ruta es fija (la configura el administrador de la

red)
–  Al menos hasta que haya un cambio de topología que
–  No puede responder a los cambios en el tráfico

habrá que configurar nuevas

•  Ventaja: simplicidad
•  Desventaja: falta de flexibilidad

10/30

Ejemplo con
enrutamiento
estático


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
Á

Enrutamiento por Inundación
•  Si un nodo recibe un paquete lo envía a todos sus vecinos

(menos a aquel que se lo ha enviado)

•  Simple, pero funciona
•  Eventualmente múltiples copias llegarán al destino
•  No requiere información de la red para funcionar
•  Necesitamos identificar cada paquete para distinguir si un

paquete lo hemos recibido ya o no. (Pero es facil, basta con
poner un número de secuencia en el paquete)

•  Algún problema más?

Paquete con destino D

D

12/30


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
Á

Enrutamiento por Inundación
Problemas:

–  Los ciclos crean tráfico infinito

¿Cómo limitamos los el tráfico en los ciclos?

–  Los nodos podrían recordar los paquetes que han reenviado y no volver a
reenviar de nuevo (Cuanto tiempo deben recordarlos? Que problema hay
si lo recuerdan mucho tiempo?)

–  Se puede incluir un numero máximo de saltos en cada paquete e ir

decrementando en cada salto (recuerde TTL de IP)

13/30


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
Á

Ejemplo

14/30


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
Á

Propiedades de la inundación
•  Todos los posibles caminos se prueban

– Muy robusto

•  Al menos un paquete viaja por el

camino más rápido
– Muy util para establecer circuitos virtuales

•  Todos los nodos son visitados

– Util para distribuir información a múltiples

destinos (Broadcast y Multicast)

•  Desventaja: mucho tráfico generado

(incluso con limitaciones)

15/30


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
Á

Enrutamiento aleatorio
•  La simplicidad de la inundación con mucha menos

carga

•  Cada nodo que debe reenviar un paquete:

–  Elige uno de los enlaces de salida y lo envía por ese
–  La selección puede ser al azar o bien ir eligiendo uno cada
–  Una refinamiento es asignar una probabilidad diferente de

vez (Round Robin)

ser elegido a cada enlace

•  No requiere información de la red

D

16/30


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
Á

Enrutamiento aleatorio
•  Al final acaba llegando al destino
•  Aunque la ruta aleatoria normalmente no es ni la de

menos salto ni la de menos coste

•  Si los paquetes tienen un número de saltos limitado
el enrutamiento aleatorio tiene una probabilidad de
entregar el paquete menor que 1

•  Puede parecer malo pero hay ocasiones en las que

es util
–  Ventajas: muy simple y poca carga (comparado con la

inundación) y visita un numero grande de nodos (aunque
menos que la inundación)

–  Desventajas: no siempre llega, normalmente no llega por el

camino mas corto

•  En que situación es útil esto?

17/30


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
Á

Enrutamiento adaptativo

•  Usado por prácticamente todas las redes de conmutación de paquetes
•  Las decisiones de enrutamiento cambian conforme cambia el estado

de la red, debido a fallos y desconexiones de enlaces o a la congestión

•  Necesita información de la red
•  Desventajas

–  Decisiones más complejas
–  Compromiso entre información de la red utilizada y trafico extra introducido

por el enrutamiento (mejor información más capacidad de red
desperdiciada en trafico de enrutamiento)

–  Compromisos de estabilidad

•  Reaccionar muy rápido puede causar oscilaciones y desorden o ciclos

momentaneos

•  Reaccionar muy lento = información desactualizada, perdidas por enlaces caidos

18/30


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
Á

Enrutamiento adaptativo
Ventajas
•  Mejores prestaciones
•  Puede ayudar al control de congestión

•  Pero es un sistema complejo por lo que es

difícil conseguir las ventajas teóricas
–  La mayoría de las redes de paquetes han sufrido
problemas de enrutamiento debido a fallos en los
sistemas de enrutamiento adaptativos y han
cambiado de sistemas de enrutamiento a lo largo
del tiempo

19/30


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
Á

–  Local (aislado)

–  Nodos vecinos