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

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

,



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

Á

a
c

i
t

Temario

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

1/30

2/30

1

a Enrutamiento en redes de paquetes

c

,



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



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

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

compromiso

compromiso

,



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

Á

a Criterio de prestaciones

c

i
t

• 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

3/30

4/30

a Ejemplo

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

Á

En general grafo dirigido
con enlaces con pesos

5/30

2

a Ejemplo

c

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

,



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



Mínimo coste
De N1 a N6

a Tiempo y lugar de decisión

c

i
t

• Tiempo

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

de la red

• Lugar

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

la información elige todo el camino

,



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

Á

a Información de la red

c

• Normalmente el enrutamiento requiere

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

• 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

6/30

7/30

8/30

3

a Estrategias de enrutamiento

c

,



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



• Enrutamiento estático
• Enrutamiento por inundación
• Enrutamiento aleatorio
• Enrutamiento adaptativo

a Enrutamiento estático

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

Á

• 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

habrá que configurar nuevas

– No puede responder a los cambios en el tráfico

• Ventaja: simplicidad
• Desventaja: falta de flexibilidad

Ejemplo con
enrutamiento
estático

9/30

10/30

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



a Enrutamiento por Inundación

c

• 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

,



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

Á

a Enrutamiento por Inundación

c

i
t

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)

a Ejemplo

i
t

c

,



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

Á

13/30

14/30

5

,



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



i


a
í
r
e
n
e
g
n
I

e
d

a
e
r

Á

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

i
t
á
m
e
e
T

c

l

– 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 Enrutamiento aleatorio

c

i
t

• 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

vez (Round Robin)

– Una refinamiento es asignar una probabilidad diferente de

ser elegido a cada enlace

• No requiere información de la red

,



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

Á

D

16/30

a Enrutamiento aleatorio

c

i
t

• 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

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 Enrutamiento adaptativo

c

• 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

,



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

Á

a Enrutamiento adaptativo

c

i
t

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

18/30

19/30

Clasificación del enrutamiento adaptativo

a
c

i
t

• Según la fuente de información

– Local (aislado)

• Enviar por el enlace mas descargado (menos paquetes en cola)
• Puede incluir bias de enrutamiento estatico
• Se usa muy poco ya

– Nodos vecinos

• Información sobre retardo o disponibilidad (caidas de enlaces) se

envían a los vecinos

– Todos los nodos

• La información sobre los enlaces y su retardo se envía a todos los

dem