Ing. en Redes y Comunicaciones Diseño de Redes OSPF (Open Shortest Path First)

Ing. en Redes y Comunicaciones Diseño de Redes

OSPF (Open Shortest Path First)


OSPF

Es un protocolo de enrutamiento jerárquico de pasarela interior o IGP (Interior Gateway

Protocol), Utiliza el algoritmo de Dijkstra para calcular el árbol de ruta más corta de cada

par (Origen y grupo)

Además, construye una base de datos enlace-estado (link-state database, LSDB)

idéntica en todos los enrutadores de la zona.

2


OSPF

Se desarrolló debido a una necesidad en la comunidad de Internet de introducir un

protocolo abierto (no propietario) de alta funcionalidad del tipo Interior Gateway

Protocol (IGP) para el protocolo de la familia TCP / IP

El protocolo OSPF (Open Shortest Path First – primero la trayectoria libre más corta) está

definido en el RFC 1583.

3


OSPF

Requisitos a cumplir cuando se diseñó:

- Ser abierto, que no fuera propiedad de una compañía. - Que permitiera reconocer varias métricas.- Ser dinámico.- Ser capaz de realizar encaminamiento dependiendo del tipo de servicio.

4


OSPF

OSPF es la respuesta de IAB a través del IETF, ante la necesidad de crear un protocolo de

pasarela interior que cubriera las necesidades en Internet de encaminamiento interno que el

protocolo RIP versión 1 ponía de manifiesto:

Lenta respuesta a los cambios que se producían en la topología de la red.

Imposibilidad de repartir el tráfico entre dos nodos por varios caminos si estos existían por la creación de bucles que saturaban la red.

5


OSPFImposibilidad de discernir entre host, routers, diferentes tipos de redes dentro de un mismo

Sistema Autónomo.

Algunos de estos puntos han sido resueltos por RIP versión 2 que cuenta con un mayor número de métricas así como soporta CIDR (Classless Interdomain Routing), por subred

y transmisión multicast.

6


Características de OSPF

OSPF es un protocolo complejo en comparación con RIP.

Es un protocolo de estado de enlace, de primero el camino libre más corto.

Los cambios de estado se producen como resultado de eventos (Actualización por

excepción)

7


El Algoritmo de OSPFLa algoritmia SPF sobre la que se basa

OSPF permite con la tecnología actual que existe en los nodos un tiempo de respuesta en cuanto tiempo de computación para el

calculo del mapa local de la red mucho más rápido que dicho calculo en el protocolo RIP.

Además como todos los nodos de la red calculan el mapa de manera idéntica y

poseen el mismo mapa se genera sin bucles ni nodos que se encuentren contando en infinito; principal problema sufrido por los

protocolos basados en la algoritmia de vector distancia como RIP.

8


OSPFSoporte de Múltiples Métricas

La tecnología actual hace que sea posible soportar varias métricas en paralelo.

Evaluando el camino entre dos nodos en base a diferentes métricas es tener distintos mejores caminos según la métrica utilizada en cada caso, pero surge la duda de cual es el mejor. Esta elección se realizara en base a

los requisitos que existan en la comunicación.

9


OSPF

Diferentes métricas utilizadas pueden ser:

Mayor rendimiento

Menor retardo

Menor coste

Mayor fiabilidad10


OSPF

Balanceado de carga en múltiples caminos.

OSPF permite el balanceado de carga entre los nodos que exista más de un camino. Para realizar

este balanceo aplica:

Una versión de SPF con una modificación que impide la creación de bucles parciales.

Un algoritmo que permite calcular la cantidad de tráfico que debe ser enviado por cada camino.

11


Funcionalidad en OSPF

Descubrir vecinos OSPF

Elegir el DR

Formar adyacencias

Sincronizar bases de datos

Calcular la tabla de encaminamiento

Anunciar los estados de enlaces.

12


OSPFDescubrimiento vecino OSPF

Cuando los “routers” OSPF se activan, inician y mantienen relaciones con sus vecinos usando el

protocolo Hello.

El protocolo además asegura que la comunicación entre vecinos sea bidireccional.

Los paquetes Hello se envían periódicamente al exterior por todas las interfaces de los “routers”.

13


OSPF

Determinando el DR

Se usa el protocolo Hello. El “router” examina la lista de sus vecinos, desecha cualquiera que no

tenga comunicación bidireccional o que tenga un RP de ver, y graba el DR, el BDR y la RP que ha declarado cada uno de ellos. El “router” se añade

él mismo a la lista, usando el valor RP configurado para la interfaz cero (desconocido)

para el DR y el BDR, en el caso de que este proceso esté en proceso de activación.

Se determina el BDR y el DR.

14


OSPF

La siguiente decisión es si se debería formar una adyacencia con uno de sus vecinos:

En redes multiacceso, todos los “routers” se hacen adyacentes al DR y la BDR.

En enlaces punto a punto (virtuales), cada “router” forma siempre una adyacencia con

el “router” del otro extremo.15


OSPF

Sincronización de las bases de datos.

Después de terminar el DEP (“Database Exchange Process”),cada “router” tiene una lista de aquellos anuncios para los que el vecino tiene más instancias acutalizadas,

que se solicitan por medio de paquetes LSR (“Link State Request”). La respuesta aun LSR es un LSU (“Link State Update”) que contiene algunos o todos los anuncios

solicitados.

16


OSPF

Calculando la tabla de encaminamiento

Usando como entrada las bases de datos de estados de enlaces de las áreas con

las que está conectado, el “router” ejecuta el algoritmo SPF para contruir su tabla de

encaminamiento.

17


OSPFAnunciando los estados de los enlaces

Un “router” anuncia periódicamente el estado de su enlace, por lo que la ausencia de un anuncio reciente

indica a los vecinos del “router” que no está activo. Todos los “routers” que hayan establecido comunicación

bidireccional con un vecino ejecutan un contador de inactividad para detectar ese suceso.

La comunicación se debe establecer desde cero, incluyendo la re-sincronización de las bases de datos.Un “router” también relanza sus anuncios cuando su

estado cambia.

18


Single Area de OSPF(OSPF de una sola área)


Repaso de OSPF

• Open Shortest Path First (OSPF), como RIP, está basado en estándares “Abiertos”.– RFC 2328

• OSPF es frecuentemente preferido sobre RIP por su escalabilidad.– Puede ser configurado en

redes más pequeñas usando una “Área” (mostrado en amarillo).

– O escalado a redes más grandes sin límites virtualmente.

• Las Redes y Areas son fácilmente agregadas o eliminadas.

– VLSM y Rutas Sumarizadas son totalmente soportados.

172.16.0.0/16

172.16.0.0/19

172.16.32.0/19172.16.64.0/19

172.16.32.0/22

172.16.36.0/22

172.16.40.0/22172.16.64.0/22

172.16.68.0/22

172.16.72.0/22

172.16.0.0/22

172.16.4.0/22

172.16.8.0/22


Actualizaciones• RIP envía en broadcast su tabla de enrutamiento completa cada 30

segundos haya habido un cambio o no.• Cuando el temporizador de un router expira, éste envía una

actualización a sus vecinos directamente conectados.• El comportamiento de RIP llega a ser un problema cuando redes

crecen en más de 30 o 50 routers. Imagine 50 actualizaciones siendo enviadas cada 30 segundos a pesar de la condición de convergencia de la red.


Velocidad de Convergencia• OSPF es manejado-por evento.

– Solo cambios son enviados a otros routers.

– Envía un LSA (link state advertisement) cuando un cambio ocurre.

– La red casi instantáneamente re-converge con la nueva información contenida en el LSA del router originador.

22


Selección de Ruta• RIP puede tomar rutas subóptimas porque solo considera a los saltos.• OSPF calcula el “Costo” de cada enlace, el cual se basa en el ancho de

banda.

23


Terminología de OSPF – Enlaces (Links)—redes que un router conoce; cada interface del router

es un “link”.– Área—un grupo de routers identificado con un único ID; todos los routers

en la misma área comparten la misma base de datos link-state.– Costo—es el ancho de banda del medio; puede ser configurado

manualmente.– Algoritmo SPF (Dijkstra)—calculado por cada router para seleccionar la

ruta de costo más bajo.– Link-state—¿está un enlace “up” o “down”?– LSA—un anuncio de link state– Base de Datos de Adyacencias—lleva la cuenta de todos los routers

directamente conectados (también llamados vecinos).– Base de Datos Link-State—también conocido como base de datos

Topológica; fotografía de quién está conectado a qué; todos los routers deberán tener la misma L-S DB.

– Base de Datos Forwarding—conocida como la tabla de Enrutamiento donde las rutas de más bajo costo son instaladas.

– Designated Router/Backup Designated Router (DR/BDR)— routers que son elegidos en redes multiacceso para ser el punto focal para actualizaciones de enrutamiento.

24


Tipos de Paquetes


Tipos de Paquetes OSPF • OSPF usa una variedad de paquetes para

comunicarse con los vecinos y los DR/BDR– Tipo 1: Hello; un paquete de 64-byte enviado a

intervalos regulares para mantener un enlace “vivo”.– Tipo 2: DBD (Descripción de Base de Datos);

resumen que contiene la base de datos link-state del router enviada a un nuevo vecino descubierto.

– Tipo 3: LSR (Link-State Request); solicitud de información más específica acerca de un enlace de la base de datos link-state de u vecino.

– Tipo 4: LSU (Link-State Update); transporta LSAs a los routers vecinos; por ejemplo, una respuesta a un LSR.

– Tipo 5: LSAck (Link-State Acknowledgement); acuses de recibo de un LSA; las actualizaciones de enrutamiento de OSPF son orientadas a conexión.

26


Encabezado del Paquete de OSPF (Todos los Tipos)• Un encabezado de 20 bytes es agregado al frente de todos los

paquetes de OSPF, conteniendo:– Versión especifica la versión de OSPF; los routers deberán estar

corriendo la misma versión o la adyacencia con los vecinos no puede ser establecida.

– Tipo especifica el tipo de paquete (Tipo 1, Tipo 2, etc.)– Longitud del Paquete es la longitud del paquete entero de OSPF en

bytes, incluyendo el encabezado estándar del paquete de OSPF.– ID del Router es la identidad IP del router que está originando el

paquete.– ID de Área es el área de OSPF que el paquete en la que el paquete

está siendo enviado. – Autenticación, si es configurada, es especificada.

27


Encabezado del Paquete Hello (Tipo 1)

• Campos adicionales agregados al encabezado del paquete de OSPF para hacer un encabezado de paquete Hello de OSPF incluyen:

– Máscara de Red es el número de bits encendidos en la máscara de Subred usada enviando el ID del Router

– Hello Interval es el número de segundos entre los hellos del router que los envía (10 seg. o 30 seg., dependiendo del tipo de red)

– Router Priority es usada para las elecciones de DR/BDR. Si es puesto en 0, el router que envía no es elegible para llegar a ser Designated Router.

– Dead Interval es el número de segundos antes de que el router que envía considere a un vecino mudo como caído. El predeterminado es 4 veces el Hello Interval.

– Designated Router es la identidad IP del DR para esta red, desde el punto de vista del router que envía.

– Backup Designated Router es la identidad IP del BDR para esta red, desde el punto de vista del router que envía.

– Neighbor Router IDs son los IDs de cada router de quienes los paquetes Hello han estado recientemente dentro del Dead Interval.

28


Encabezado de Paquete Hello (Tipo 1)

Network Mask

Hello Interval Options Router Priority

Dead Interval

Designated Router

Backup Designated Router

Neighbor Router ID

(additional Neighbor Router ID fields, if necessary)

29


Estados de OSPF


Estados de OSPF: 7 Pasos• Las adyacencias de vecinos OSPF son

establecidas a través de un proceso de siete pasos:– Down– Init– 2Way– ExStart– Exchange– Loading– Full

31


Estados Down, Init, 2Way • Cuando un router inicia primero, está en el

Estado Down y empieza enviando paquetes Hello Tipo 1

• Cuando otro router escucha el nuevo paquete Hello Tipo 1 del router por primera vez, éste entrara en Estado Init.

• Una vez que el nuevo router ve su propio ID en el paquete Hello enviado por el vecino, los routers se mueven al Estado 2Way

32


Estados Down, Init, 2Way

33


Estado ExStart • Los routers ahora entran en el Estado ExStart.• La prioridad del Router o el ID del Router es usada para

determinar la relación maestro/esclavo.

34


Estado Exchange• Durante el Estado Exchange, paquetes DBD Tipo 2

son intercambiados.– Estos son un resumen de la Base de Datos Link-State de

cada router.

35


Estado Loading• El Estado Loading es usado solo si uno o más routers en la red

no convergida “escucharon nueva información”.

36


Estado Full • Los routers entran a Estado Full y ahora ambos

pueden calcular el algoritmo SPF en paralelo (Dijkstra).

37


Operación de OSPF


Pasos en la operación de OSPF• Los routers se mueven a través de cinco

pasos distintos de operación.– Paso 1: Establecer Adyacencias de Router – Paso 2: Elegir un DR y BDR– Paso 3: Descubrir Rutas– Paso 4: Seleccionar Rutas Apropiadas– Paso 5: Mantener la Información de

Enrutamiento

39


Paso 1: Descubrir Vecinos & Establecer Adyacencias

• Este proceso—ya discutido anteriormente en la descripción de los estados Init y 2Way –es similar para redes broadcast

40


Paso 2: Elegir unDR y un BDR• Ocurre durante el esado ExStart • El router con la más alta prioridad o la dirección IP más alta configurada llega a ser el DR.• El BDR es seleccionado de la misma forma.

41


Paso 3: Descubrir Rutas• Tipo2 DBDs ahora son intercambiadas

42


Paso 3: Descubrir Rutas• Tipo 2 DBDs ahora son intercambiadas

43


Paso 4: Seleccione Rutas Apropiadas• El Algoritmo SPF es ahora calculado en paralelo con cada router en el Área.

44


Paso 5: Mantener la Información de Enrutamiento

• Intercambia Hellos periódicos para detectar cambios en el estado de los vecinos.

45


Tipo de Red Características ¿DR/BDR Elegido?

Ethernet, Token Ring, FDDI Si

Frame Relay, X.25, SMDS Si

PPP, HDLC

No, Master/Slave relationship dictates the

exchange of routing information

Configured by administrator with subinterfaces

No, Master/Slave relationship dictates the

exchange of routing information

Tipos de Redes

Nonbroadcast Multiaccess

Point-to-Point

Point-to-Multipoint

Broadcast Multiaccess

46


Paquetes Multicast Hello

Los routers que escuchan agregan el

nuevo router a la tabla de adyacencias

Los routers responden a los paquetes Hello con sus propios paquetes Hello

Init StateDown

2Way State

El router originador agrega a todos los

routers que responden a la tabla de adyacencias

Seleccionar DR/BDR

Tipo de Enlace es multiacceso

Compare todos los valores de

Prioridad del Router

¿Son iguales?Compare los IDS del Router

Si

Toma el valor más alto

Tomar el segundo valor

más alto

No

Full State

Intercambie información Link-State

Cualquier LSAs finales son también

intercambiadas

Intercambie paquetes Hello a intervalos para mantener información

de enrutamiento actualizada

Exchange

Loading

ExStart State

Tipo de enlace es punto-a-punto;

determine “maestro/esclavo”

Asignarlo como BDR

Asignarlo DR

Las Adyacencias deberán ser

establecidas (depende del tipo de enlace)

47

Documents

Ing. en Redes y Comunicaciones Diseño de Redes OSPF (Open Shortest Path First)