PDF de programación - OSPF: Open Shortest Path First

OSPF: Open Shortest Path First

Redes y Servicios de Comunicaciones Avanzadas

Departamento de Ingeniería Telemática

Carlos J. Bernardos

[email protected]

Manuel Urueña

[email protected]

Índice

1. Protocolos de Estado de

Enlaces

2. Protocolo OSPF

❖ Funcionamiento

❖ Áreas

2

Protocolos de Estado

de Enlace (EE)

 Open Shortest Path First (OSPF) es el protocolo

de Estado de Enlaces más conocido

 Orígenes:

❖ Ya en los orígenes (ARPANET) se fue consciente de los

problemas de los protocolos de Vector de Distancias

❖ Los primeros trabajos dieron como resultado IS-IS (OSI)

y OSPF (IETF)

❖ Los protocolos de Estado de Enlaces (Link State) se
basan en el concepto de “mapa distribuido de la red”
✓ Todos los nodos tienen una copia, que se actualiza

periódicamente

✓ A partir del mapa, los nodos son capaces de calcular la ruta
más corta entre un nodo origen y cualquier otro utilizando el
algoritmo Shortest Path First (SPF), también conocido como
algoritmo de Dijkstra

3

Protocolos de EE:
Características generales

 NO hay intercambio de Vectores Distancia

(tablas encaminamiento) entre routers

 Cada router comprueba el estado de sus
enlaces con los vecinos y sólo comunica
esta información a sus vecinos

 Los vecinos, a su vez, propagarán esta

información (inundación) al resto de
routers del sistema

 Cada router reconstruye la topología

completa de la red y su propia tabla de
encaminamiento utilizando toda la
información de estado-de-enlace recibida

4

Protocolos de EE:

¿Cómo funcionan?

1. Creación de la base de datos de Estado de Enlaces:
❖ Cada router asigna un coste localmente a sus interfaces

de salida (enlaces)
● El coste de un enlace puede ser diferente en cada sentido
● Un coste menor implica un enlace mejor

2.

3.

La información sobre el estado de los enlaces se
difunde mediante inundación (flooding) en toda la red
La base de datos de cada router se construye en
base a toda la información recibida

❖

Topología completa de la red: Quién está conectado con
quién, con qué coste

4. Cada router calcula el mejor camino hacia todos los

enlaces de la red (subredes)
❖ Mediante el algoritmo de Dijkstra (Shortest Path First)

5. El router construye su tabla de encaminamiento

5

Open Shortest Path First (OSPF):

Características generales

 Protocolo Open Shortest Path First (OSPF):

❖ Definido inicialmente (OSPFv1) en la RFC 1131 (Octubre 1989)
❖ Revisado posteriormente (OSPFv2) en la RFC 1247 (Julio 1991, 189

págs.) y en las RFCs 1583 (Marzo 1994) y 2178 (Julio 1997)

❖ Última revisión: RFC 2328 (Abril 1998, 244 págs.)

 Características:

❖ Estado de Enlaces
❖ Los mensajes del protocolo se transmiten directamente sobre IP

(número de protocolo: 89)

❖ Utiliza el coste de los enlaces para calcular la ruta más “corta”

✓ Permite definir diferentes costes para diferentes tipos de aplicaciones

❖ Menor carga de señalización que RIP (aunque depende de la topología)

✓ Tras la convergencia sólo se envían los cambios

❖ Permite definir áreas de encaminamiento

✓ Encaminamiento jerárquico, menos carga de señalización

❖ Convergencia rápida, libre de conteo a infinito (topología completa)

✓ Los routers necesitan una mayor capacidad de procesamiento

6

OSPF: Tipos de mensajes

TIPO

FUNCIÓN

Protocolo Hello

(Tipo 1: Hello)

Protocolo Exchange

(Tipo 2: Database Description)

Descubrimiento y mantenimiento
de vecinos

Fase inicial del procedimiento de
sincronización de las bases de
datos

Petición de estado de enlace (EE)

(Tipo 3: Link State Request)

Petición de datos que actualicen
la base de datos

Protocolo de inundación

(Tipo 4: Link State Update)

Permiten el envío de datos
correspondientes al cambio de un
EE

Asentimiento de EE

Asentimiento del anterior

(Tipo 5: Link State Ack)

7

Formato de mensajes OSPF:

Cabecera común

0 7 8 15 16

31

Versión (1)

Tipo (1)

Long. Paquete (2)

Identificador de Router (4)

Identificador de Área (4)

Checksum (2)

Tipo de Autenticación (2)

Autenticación (8)

Formato: Nombre del campo (Tamaño en octetos)

8

Funcionamiento de OSPF

Creación de la base de datos de los enlaces

40

A

N1

20

N2

20

D

N3

10

80

B

20

20

10

40

E

50

N4

20

C

30

N5

● Cada router asigna un coste a sus enlaces:

♦ Coste asignado a la interfaz de salida
♦ Routers compartiendo un mismo enlace

pueden asignarle costes distintos:
○ Las rutas obtenidas pueden ser asimétricas

9

Funcionamiento de OSPF:

Grafo de la topología (I)

 Los routers crean una imagen de la

topología completa de la red:

❖ Creando un grafo dirigido

❖ Cada arco tiene un coste asignado

❖ Una conexión punto-a-punto se representa

como 2 arcos, uno por cada dirección

❖ Una red multiacceso (p.ej. una LAN) se

representa con un nodo “virtual” para la red en
sí misma, más un nodo para cada router
conectado (en lugar de una malla completa)

✓ Los arcos del nodo “virtual” de la red a los routers

tienen coste 0

10

Funcionamiento de OSPF:

Grafo de la topología (II)

40

N1

A

20

N2

20

D

N3

10

80

B

20

20

10

40

E

50

N4

20

C

30

N5

0

N1

20

0

N4

20

A

40

0

B

80

N2

0

20

40

0

D

0

10

E

10

N3

0

0

30

20

0

50

N5

20

C

0

11

Funcionamiento de OSPF
Link State Advertisements (LSAs)

 Los routers OSPF envían la información de estado de sus

enlaces en Link State Advertisements (LSAs)
❖ Los routers OSPF almacenan los LSAs recibidos

 Existen varios tipos de LSAs (OSPF define varios tipos de

enlaces):
❖ LSA 1 - Router Links (o Router Link LSAs o Router-LSAs)

✓ Cada router informa acerca de todos los enlaces a los que está

conectado

❖ LSA 2 - Network Links (o Network Link LSAs o Network-LSAs)

✓ Contiene información acerca de todos los routers conectados la red

multiacceso. Sólo el “Router Designado” (Designated Router, DR)
anuncia este tipo de enlaces:

✓ Este tipo de enlaces tiene siempre coste 0

❖ LSAs 3 y 4 - Summary Links (o Summary-LSAs):

✓ Tipo 3 - Summary Link to Network LSAs
✓ Tipo 4 - Summary Link to AS Boundary Router LSA

❖ LSA 5 - External Links (o External Link LSAs o AS-External-LSAs)
❖ … (más en una transparencia posterior)

12

Funcionamiento de OSPF:

Descubrimiento de los vecinos (Protocolo HELLO)

40

A

HELLO

N1

HELLO
20

N2

20
HELLO

D
HELLO
10

N3

80
B
HELLO
HELLO
20

HELLO
20

N4

C
HELLO
20

HELLO
30

N5

40
HELLO

10
E
HELLO
HELLO

50

● Cada router OSPF envía mensajes HELLO a sus

vecinos periódicamente (10-30 segs.), lo que permite:
♦ Descubrir a los routers OSPF vecinos y comprobar que el enlace es

bidireccional

♦ Comprobar el estado de los enlaces (4x HELLO time)

♦ En redes multiacceso: Elegir el Router Designado (Designated

Router, DR) y el DR de respaldo (Backup Designated Router, BDR)

13

Funcionamiento de OSPF:
Sincronización de las bases de datos

40

A

N1

20

N2

20

D

N3

10

80

B

20

20

10

40

E

50

N4

20

C

30

N5

● Los routers sincronizan sus bases de datos intercambiando

paquetes Database Description (DD):

○ Un paquete DD incluye la lista completa de la descripción de los Anuncios de
Estado de Enlace (Link State Advertisements, LSAs) que el router tiene en su
base de datos

○ Los routers piden a su vecino aquellos registros de los que no dispone en su

base de datos (o de los que tiene una copia anticuada)

◊ Este sistema evita el intercambio de las bases de datos completas para lograr la

sincronización

14

Funcionamiento de OSPF:

Cálculo de la tabla de rutas

40

A

N1

20

N2

20

D

N3

10

80

B

20

20

10

40

E

50

N4

20

C

30

N5

de C a

por

coste

de A a

por

coste

B

C

D

E

N1

N2

N3

N4

N5

B

D

D

40

80

10

-

-

D

D

D

100

80

● Los routers construyen la tabla de rutas

30

D

E

♦ En base a la visión global de la red que tienen (convergencia)

40

♦ Utilizando el algoritmo de Dijkstra, calculan el camino más corto

20
a todos los destinos en la red
30

A

B

D

N1

N2

B

B

E

E

B

B

40

20

40

30

40

60

N3

N4

N5

E

-

-

40

20

30
15

Funcionamiento de OSPF:

Funcionamiento normal: Mantenimiento (I)

40

A

N1

20

N2

20

D

N3

10

80

B

20

20

10

40

E

50

N4

20

C

30

N5

● En estado estacionario (tras convergencia) los routers OSPF:

♦ Envían periódicamente mensajes HELLO

♦ Cuando detectan cambios, envían mensajes de Actualización
de Estado de Enlace (Link State Updates, LSUs), que incluyen
Anuncios de Estado de Enlaces (LSAs)

♦ Procesan los LSAs que reciban (en LSUs):

○ Recalculando la tabla de datos si es necesario

16

Funcionamiento de OSPF:

Funcionamiento normal: Mantenimiento (II)

40
LSU

A

N1

20

20

N2

20
LSU

D

10

N3

10

de A a

por

coste

B

C

D

E

N1

N2

N3

N4

N5

B

B

D

B

-

-

D

B

B

40

110

10

60

40

20

30

120

110

80

LSU

B
LSU

N4

C
LSU

20

20

30

40
LSU

E

50
LSU

N5

de C a

por

coste

A

B

D

E

N1

N2

N3

N4

N5

B

B

B

E

B

B

B

-

-

40

20

60

30

40

60

70

20

30

17

Funcionamiento de OSPF:

Redes jerárquicas: Áreas en OSPF

A
BR

N1

B
BR

Backbone OSPF – Área 0

N3

N2

BGP

ASBR

J

ABR

C

N5

Área 1

F
IR

N6

ABR

D

N4

ABR

E

N7

Área 2

IR
G

N9

Área

N8

192.168.10.0

H
IR

N10

IR
I

IR: Interior Router

BR: Backbone Router

ABR: Area Border Router

N11

ASBR: Autonomous System Boundary Router

18

Funcionamiento de OSPF:

Tipos de LSAs

Tipo LSA

Propósito

Generado por

Inundado a

1 – Router LSA

Describe los enlaces
del router

Todos los routers
OSPF

2 – Network LSA

Describe red
broadcast o
multiacceso

DRs del enlace

3 – Summary LSA

Describe rutas inter-
área

ABRs

4 – ASBR Summary
LSA

Describe rutas hacia
un ASBR

ABRs

5 – AS External LSA

Describe rutas
externas al AS

7 – NSSA External
LSA

Similar al Tipo-5,
pero internas a un
área de tipo NSSA

ASBRs

ASBRs

Dentro del área a la
que pertenece el
router

Dentro del área a la
que pertenece el
router

Dentro del área a la
que pertenece el ABR

Dentro