PDF de programación - Enrutamiento Link-state...

REDES
Área de Ingeniería Telemática

Enrutamiento

Link-state...

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 (sesión 3)
• Arquitectura de conmutadores de paquetes
• Control de acceso al medio
• Transporte extremo a extremo

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
Á

Enrutamiento Link-State

•

Idea de funcionamiento
– Cada router es responsable de reconocer a sus vecinos y aprenderse

su nombre (identidad)

– Cada router construye un paquete llamado LSP (link state packet)

conteniendo una lista de todos sus vecinos y el coste asociado

– El LSP se envía a todos los demás routers de la red. Cada router

recuerda el ultimo LSP recibido de cada otro router

– Cada router con el mapa completo de la topologia calcula las rutas a

cada destino posible y actualiza su tabla de rutas

• Como de dificil es cada una de estas fases?

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
Á

Link-State: 1 descubrir vecinos

• Descubrimiento de vecinos

Mensaje HELO
– Contiene una identidad del router
– Periódico a la red de área local o al enlace punto a punto
– Recordar los últimos HELOs vistos (lista de identidades de

los vecinos)

– Tiempo entre mensajes
– Tiempo para dar al router por desaparecido

HELO soy el
router 65

HELO soy el
router 123

Vecinos
65
42

Visto hace
6s
14s

HELO soy el
router 42

4

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
Á

Link-State: construir LSPs

• Construir LSPs
– Periódicamente
– Cada vez que veo un nuevo vecino
– Cada vez que cambia el coste a un vecino
– Cada vez que dejo de ver a un vecino (ha pasado el tiempo definido sin

escuchar HELOs de ese vecino

• El LSP contiene

El router de identidad X tiene esta lista de vecinos
Vecino 1: Y con coste c1
Vecino 2: Z con coste c2
Vecino 3 ..

• En que se diferencia de los distance-vector??

5

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

Link-State: 3 distribuir LSPs

• Cada router necesita los LSPs de todos los demás, no solo el de sus vecinos
• Recibo estos

de R1
vecinos
R2 / 3

3

R2

R1

de R3
vecinos
R2 / 2
R4 / 7

R2

2

R3

R4

7

de R4
vecinos
R3 / 7

R4

R3

7

de R2
vecinos
R3 / 2
R1 / 3
R5 / 4

R1

R3

3

4

R5

Base de datos de nodos y enlaces en la red

•
• Usando el algoritmo de Dijkstra calculo caminos

R1

R2

R4

R3

7

R3

R5

Link-State: 3 distribuir LSPs

Si hay un cambio en la red los routers que lo ven envían el cambio a todos
El resto de los enlaces están en la base de datos

•
•
• Con el cambio de ese enlace se recalculan los caminos en todos
• No hay cuentas a infinito
• Reaccion muy rapida

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

Link-State: 3 distribuir LSPs

• El destino de los LSPs

Son todos los routers de la red
Es facil enviar a los vecinos pero no a cualquier router de la red... (no se
las direcciones de todos, no puedo basarme en la tabla de rutas para llegar
a ellos)

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
Á

•

• Es necesario un sistema de envío a cualquier destino que no requiera que

funcionen las tablas de rutas.
Inundación?
La distribución de LSPs es el punto critico de los algoritmos de tipo link-
state
– Si no llega la información a todos, las rutas son incoherentes y puede
haber ciclos de enrutamiento (recordar cuentas a infinito con un solo
enlace en desacuerdo)

– Si no tenemos cuidado la inundación puede causar mucho trafico
extra, los routers pueden saturarse y dedicar gran parte de su cpu
simplemente a recalcular rutas tras recibir

8

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
Á

Link-State: 3 distribuir LSPs

Inundando LSPs

•
• Cada router escucha LSPs de sus vecinos y reenvía
• Como limitar el tráfico

– TTLs?
– Con LSPs ya estamos guardando estado (cada router recuerda el
ultimo LSP de cada destino) usar esto para limitar la inundacion
(ignorar un LSP si ya lo he visto)
Sólo recordar el más reciente... no es tan facil

• No necesariamente llegan en orden
• Etiquetar los LSPs con la fecha (timestamp) de creacion?

– Problemas si un nodo genera un timestamp en el futuro ya no

se olvida y nunca se sustituye

– Timestamp con significado global permite descartar pero es

dificil tener tiempo global entre routers

9

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
Á

Link-State: 3 distribuir LSPs

LSP numeros de secuencia y edad

•
• Se asigna un numero de secuencia a cada LSP nuevo que se envía

– Los routers solo se quedan con el LSP si tiene mas numero de

secuencia que el anterior

• Casi... pero aun tiene problemas

– Los campos tienen longitud finita... si llego al maximo vuelvo a 0

a < b significa

>a
a

<a

0

– que pasa si un router se apaga y vuelve a encender y no recuerda el

numero de secuencia que llevaba?

– que pasa si dos partes de la red quedan aisladas y mientras estan
aisladas el numero de secuencia de un router avanza hasta el punto de
que al volver a unirse los routers que llevan tiempo sin verlo piensan
que sus numeros de secuencia son menores

• Se resuelve añadiendo edad a los LSPs

10

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
Á

Un protocolo de distribucion de LSPs

• Un router genera un LSP que contiene

– La identidad del router origen
– Un numero de secuencia que es 1 mas que el anterior LSP que envió
– Una edad (tipo TTL) que es un valor maximo
– La lista de vecinos con el peso

• Un router que recibe un LSP lo compara con el LSP que tiene almacenado para

ese destino
– Si tiene mayor numero de secuencia que el almacenado lo sustituye por el

nuevo

– Si el almacenado tiene edad 0 es sustituido independientemente de la

secuencia (me olvido de los que llegan a edad 0)

– Si he sustituido el LSP almacenado por el recibido lo propago enviandolo a

todos los vecinos excepto al que me lo ha enviado

• Cada cierto tiempo descuento 1 a la edad de todos los LSPs almacenados
• Caso real: edad 3bits 0-7 x8s (56 segundos y se descuenta cada 8s)

se genera un LSP cada 60s (el primero al encender el router espera 90s)
Parece razonable?

•

11

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
Á

The ARPANET incident

•
•

Ese algoritmo consiguió bloquear totalmente ARPANET
Supongamos que un router funcionando mal envía tres LSPs seguidos con
numeros de secuencia a, b, c de forma que a < b < c pero c < a

• Con el algoritmo anterior como cada router que los recibe los acepta y reenvia
porque cree que son nuevos, cada uno de los que lo recibe los acepta y reenvia
y al recibirlos de nuevo los sigue aceptando.
Esto desencadena una inundación total, ocurrió en la realidad. Una noche
ARPAnet dejo de funcionar. Al parar routers y examinarlos se veia que tenien la
cola de salida saturada de esos tres LSPs toda ARPANET estaba al 100%
enviando esos 3 mensajes
El router que los habia enviado tenia un fallo y fue desconectado
Pero eso no detuvo el problema todos los routers tenian copias de esos
mensajes si reinicias un router en cuanto vuelve a funcionar sus vecinos le
envian de nuevo copias y se llena

•

• Una solucion obvia es apagar toda ARPANET
•

Alguna otra forma de resolverlo?

• Hay que tener cuidado con los algoritmos distribuidos a gran escala

12

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

The ARPANET incident

• Qué falla en el protocolo?

– Los mensajes no envejecen por que son sustituidos por nuevos antes de

que pasen los 8s

– Solución envejecer el mensaje en cuando un router lo toque

• Mejoras que se implementan hoy en dia

– El numero de secuencia es lineal y no da la vuelta
– El campo de edad se decrementa en 1 en cuanto un router lo recibe.

Mientras esta almacenado se ira decrementando mas

– Cuando se decide que un LSP es nuevo no se genera y se pone en cola

sino que se marca que debe enviarse.
Cuando el router decide que puede mandar un LSP elige uno que este
marcado, lo construye y lo envia
De forma que nunca hay encolado mas de una copia del mismo LSP

– Los LSP se confirman pero tampoco se encolan los ACKs solo un ACK

pendiente por origen

•

Básicamente el algoritmo anterior con estas modificaciones lo implementan
todos los protocolos link-state modernos

13

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
Á

Link-State: 4 calcular rutas

Los LSPs se guardan en una link-state database
Se utiliza el algoritmo de Dijkstra para calcular caminos
Se colocan las rutas de este nodo teniendo en cuenta esos caminos

Si la red es muy grande todos los routers necesitan mas recursos que en el
caso de distance-vector
– Deben almacenar todos los enlaces de la red

(mucha mas memoria que el vector de distancias)

– Deben calcular el algoritmo de Dijkstra cada vez que ven un cambio

(mucho mas complicado que la iteracion del Bellman-Ford)

La convergencia es rapida porque los LSPs llegan a todos y no hay
ambiguedades de caminos ni cuentas a infinito.

•
•
•

•

•

14

a
c
i
t

l



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

i

I


e
d



a
e
r
Á

S
E
D
E
R

Distance-vector vs Link-state

•
•

•
•

•

•

En uso de memoria: menor distance-vector
En tráfico de red: controvertido distance-vector no hace inundacion pero la
inestabilidad dura ma