PRIMER CAMINO MÁS CORTO - OSPF

"Año Del Diálogo y la Reconciliación Nacional"

ESCUELA ACADÉMICO PROFESIONAL DE SISTEMAS Y TELEMÁTICA.

ASIGNATURA:

TECNOLOGÍAS DE REDES I

TEMA:

 PRIMER CAMINO MÁS CORTO - OSPF

AUTORES:

FERNANDEZ VASQUEZ POLMARTHAN

SANTOS TENORIO JOSE LUIS

TEJADA SANCHEZ FRANK YORDI

DOCENTE:

ING. MARCO AURELIO PORRO CHULLI.

BAGUA GRANDE - UTCUBAMBA

AMAZONAS
2018

PRIMER CAMINO MÁS CORTO - OSPF

1. Contenido  

Definición

Open Shortest Path First (OSPF) es un protocolo de direccionamiento de tipo enlace-estado, desarrollado para las redes IP y basado en el algoritmo de primera vía más corta (SPF). OSPF es un protocolo de pasarela interior (IGP).

En una red OSPF, los direccionadores o sistemas de la misma área mantienen una base de datos de enlace-estado idéntica que describe la topología del área. Cada direccionador o sistema del área genera su propia base de datos de enlace-estado a partir de los anuncios de enlace-estado (LSA) que recibe de los demás direccionadores o sistemas de la misma área y de los LSA que él mismo genera. El LSA es un paquete que contiene información sobre los vecinos y los costes de cada vía. Basándose en la base de datos de enlace-estado, cada direccionador o sistema calcula un árbol de extensión de vía más corta, siendo él mismo la raíz, utilizando el algoritmo SPF.

Las ventajas principales de OSPF son las siguientes:

·     En comparación con los protocolos de direccionamiento de distancia-vector como el protocolo de información de direccionamiento (RIP), OSPF es más adecuado para servir entre redes heterogéneas de gran tamaño. OSPF puede recalcular las rutas en muy poco tiempo cuando cambia la topología de la red.

·     Con OSPF, puede dividir un sistema autónomo (AS) en áreas y mantenerlas separadas para disminuir el tráfico de direccionamiento de OSPF y el tamaño de la base de datos de enlace-estado de cada área.

·     OSPF proporciona un direccionamiento multivía de coste equivalente. Se pueden añadir rutas duplicadas a la pila TCP utilizando saltos siguientes distintos.

Tráfico de encaminamiento

OSPF mantiene actualizada la capacidad de encaminamiento entre los nodos de una red mediante la difusión de la topología de la red y la información de estado-enlace de sus distintos nodos. Esta difusión se realiza a través de varios tipos de paquetes:

·     Paquetes Hello (tipo 1): cada router envía periódicamente a sus vecinos un paquete que contiene el listado de vecinos reconocidos por el router, indicando el tipo de relación que mantiene con cada uno.

·     Paquetes de descripción de base de datos estado-enlace o DataBase Description o DBD (tipo 2): se emplean en el intercambio de base de datos enlace-estado entre dos nodos, y permiten informar al otro nodo implicado en la sincronización acerca de los registros contenidos en la LSDB propia, mediante un resumen de estos.

·     Paquetes de estado-enlace o Link State Advertisements (LSA): los cambios en el estado de los enlaces de un router son notificados a la red mediante el envío de mensajes LSA. Dependiendo del estado del router y el tipo de información transmitido en el LSA, se distinguen varios formatos (entre paréntesis, las versiones de OSPF en que se utilizan):

·     (OSPFv2 y v3) Router-LSA o LSA de router.

·     (OSPFv2 y v3) Network-LSA o LSA de red.

·     (OSPFv2 y v3) Summary-LSA o LSA de resumen. En OSPFv2 se distinguen dos tipos: tipo 3, dirigidos a un router fronterizo de red; y tipo 4, dirigidos a una subred interna. En OSPFv3, los Summary-LSA tipo 3 son renombrados como Inter-Area-Prefix-LSA, y los tipo 4 pasan a denominarse Intra-Area-Prefix-LSA.

·     (OSPFv2 y v3) AS-External-LSA o LSA de rutas externas a la red.

·     (OSPFv3) Link-LSA o LSA de enlace, que no se retransmite más allá del enlace del origen.

Los direccionadores o sistemas de una red OSPF, después de haberse asegurado de que sus interfaces son funcionales, envían en primer lugar paquetes Hello, utilizando el protocolo Hello por sus interfaces OSPF, para descubrir vecinos. Vecinos son los direccionadores o sistemas que tienen interfaces con la red común. Después, los direccionadores o sistemas vecinos intercambian sus bases de datos de enlace-estado para establecer adyacencias.

La siguiente figura ilustra el proceso de descubrir vecinos y establecer adyacencias en el caso de dos sistemas de la subred 9.7.85.0. Cada sistema tiene una interfaz OSPF con la subred común 9.7.85.0 (interfaz 9.7.85.1 para el sistema A e interfaz 9.7.85.2 para el sistema B). La subred 9.7.85.0 pertenece al área 1.1.1.1.

Figura 1. Protocolo OSPF Hello e intercambio de base de datos

Fase EXSTART

Es el primero paso del intercambio de bases de datos de enlace-estado. Los dos sistemas negocian quién hace de maestro y quién hace de subordinado.

Fase EXCHANGE

Los dos sistemas intercambian paquetes de descripción de base de datos para averiguar qué anuncios de enlace-estado (LSA) no están en la base de datos de enlace-estado de cada sistema. Cada sistema almacena los LSA que no están en la base de datos de enlace-estado en la lista de retransmisiones.

Fase LOADING

Cada sistema envía paquetes de petición de enlace estado para pedir al vecino (en este ejemplo, sería el otros sistema) que envíe los LSA completos que se almacenaron en la lista de retransmisiones durante la fase EXCHANGE. El vecino responde a la petición con los LSA en paquetes de actualización de enlace estado.

Fase FULL

Cuando dos sistemas terminan de intercambiarse los LSA, y sus bases de datos de enlace-estado ya están sincronizadas, se establece la adyacencia entre los dos sistemas.

Cuando ya se han establecido adyacencias entre todos los direccionadores o sistemas de un área, cada direccionador o sistema del área envía periódicamente un LSA para compartir sus adyacencias o para informar de su cambio de estado. Comparando las adyacencias establecidas con los LSA, los direccionadores o sistemas del área pueden descubrir los cambios de topología del área y actualizar debidamente sus bases de datos de enlace-estado.

Direccionador designado y direccionador designado de reserva

En una red OSPF multiacceso que tenga como mínimo dos direccionadores conectados, los direccionadores eligen un direccionador designado y un direccionador designado de reserva utilizando el protocolo Hello. (Red multiacceso es aquella en la que múltiples dispositivos se pueden conectar y comunicar simultáneamente).

El direccionador designado genera anuncios de enlace-estado (LSA) para toda la red multiacceso, envía los LSA a los otros direccionadores de la red y determina qué direccionadores deben ser los adyacentes. Los demás direccionadores de la red son adyacentes al direccionador designado. El direccionador designado disminuye el tráfico de la red y el tamaño de la base de datos de enlace-estado correspondiente a esta red.

El direccionador designado de reserva no presenta diferencias con los otros direccionadores, salvo que necesita establecer adyacencias con todos los direccionadores de la red (incluido el direccionador designado). El direccionador designado de reserva queda promocionado a ser el direccionador designado cuando falla el direccionador designado actual.

Tipo de áreas

·     Standard

·     Backbone (Area 0)

·     Stub Area

·     Totally Stubby Area

·     Not-so-stuby Area (NSSA)

·     Totally Stubby NSSA

Standard

Es el área por defecto y permite actualización de enlaces, Sumarizacion de rutas y rutas externas

Backbone

Es el área principal de una topología OSPF. Es obligatorio que exista y todas las demás deben estar conectadas a ella. Se etiqueta como area 0 y tiene las mismas características de un área estándar.

Stub Area

Este tipo de área no acepta información acerca de rutas externas al sistema autónomo (redistribución), tales como  rutas desde orígenes no OSPF. Si los routers necesitan enrutar hacia redes ubicadas fuera del sistema autónomo  OSPF, utilizan una ruta por defecto (0.0.0.0/0) que es enviada por el ABR hacia los demás routers internos del área Stub. En esta área no se permiten ASBR (a menos que el ABR sea al mismo tiempo un ASBR)

Totally Stubby Area

Esta área es propietaria de Cisco y no acepta rutas de sistemas autónomos externos (redistribución) o rutas sumarizadas desde otras áreas internas del sistema autónomo. Al igual que en las áreas Stub, los ABR envían una ruta por defecto para todas las rutas externas y SUMARIZADAS (esa es la diferencia con Stub). En esta área no se permiten ASBR (a menos que el ABR sea al mismo tiempo un ASBR)

Not-so-stuby AREA (NSSA)

Casi el peor nombre del mundo escogieron para denominar este tipo. En esta área existen los LSA de tipo 7. Son similares a las área Stub ya que no aceptan información de rutas externas al sistema autónomo (el mundo OSPF) y las reemplaza por una ruta por defecto originada en el ABR. Sin embargo, la diferencia radica en que las NSSA sí aceptan un ASBR que conecte con otro protocolo de enrutamiento (ej: RIP, EIGRP, etc) directamente. El ASBR de las NSSA reenvía las rutas dentro del área como LSA 7, y el ABR correspondiente las traduce a tipo 5 para ser tratadas de forma normal.

Totally stubby NSSA

Si el anterior era casi el peor nombre, este seguro que es el peor. Totally Stubby Not-so-stubby Area o Totally Stubby NSSA es un área propietaria de Cisco que se comporta igual que las Totally Stubby Area, es decir, no permite ni rutas externas ni sumarizadas, pero que sí permite un ASBR al igual que las NSSA.

Algoritmo de Dijkstra

También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

Aplicaciones

En múltiples aplicaciones donde se aplican los grafos, es necesario conocer el camino de menor costo entre dos vértices dados:

·     Distribución de productos a una red de establecimientos comerciales.

·     Distribución de correos postales.

·     Sea G = (V, A) un grafo dirigido ponderado.

El problema del camino más corto de un vértice a otro consiste en determinar el camino de menor costo, desde un vértice u a otro vértice v. El costo de un camino es la suma de los costos (pesos) de los arcos que lo conforman.

Características del algoritmo

·     Es un algoritmo greddy.

·     Trabaja por etapas, y toma en cada etapa la mejor solución sin considerar consecuencias futuras.

·     El óptimo encontrado en una etapa puede modificarse posteriormente si surge una solución mejor.

Pasos del algoritmo

Algoritmo 24.1: Algoritmo de Dijkstra. Inicialización.

·     Sea V un conjunto de vértices de un grafo.

·     Sea C una matriz de costos de las aristas del grafo, donde en C[u,v] se almacena el costo de la arista entre u y v.

·     Sea S un conjunto que contendrá los vértices para los cuales ya se tiene determinado el camino mínimo.

·     Sea D un arreglo unidimensional tal que D[v] es el costo del camino mínimo del vértice origen al vértice v.

·     Sea P un arreglo unidimensional tal que P[v] es el vértice predecesor de v en el camino mínimo que se tiene construido.

·     Sea vinicial el vértice origen. Recordar que el Algoritmo Dijkstra determina los caminos mínimos que existen partiendo de un vértice origen al resto de los vértices.

·         Paso 1. S ← {vinicial} //Inicialmente S contendrá el vértice //   origen

·         Paso 2. Para cada v∈V, v ≠ vinicial, hacer

·          2.1. D[v] ← C[vinicial, v] //Inicialmente el costo del 

//camino   mínimo de vinicial a v es lo contenido en //la matriz de costos

·          2.2. P[v] ← vinicial //Inicialmente, el 

//predecesor de v en el   camino mínimo construido /

/hasta el momento es vinicial

·          Paso 3. Mientras (V – S ≠ ∅) hacer 

//Mientras existan vértices  para 

//los cuales no se ha determinado el //camino mínimo

·             3.1. Elegir un vértice w∈(V-S) tal que D[w] sea el mínimo.

·             3.2. S ← S ∪ {w} //Se agrega w al conjunto S, pues ya se //   

·         tiene el camino mínimo hacia w 

·             3.3. Para cada v∈(V-S) hacer

·             3.3.1. D[v] ← min(D[v],D[w]+C[w,v]) 

//Se escoge, entre 

//el   camino mínimo hacia v que se tiene 

//hasta el momento, y el camino hacia v

 //pasando por w mediante su camino mínimo, //el de menor costo.

·             3.3.2. Si min(D[v],D[w]+C[w,v]) = D[w]+C[w,v] entonces P[v] ← w 

//Si se escoge ir por w entonces //el predecesor de v por el momento es w

·          Paso 4. Fin 

Ejemplos

Router(config)#router ospf 100

Router(config-router)#network 192.168.1.0 0.0.0.248 area 0

Router(config-router)#interface ethernet 0

Router(config-if)#ip address 192.168.1.1 255.255.255.252

Router(config-if)#ip ospf priority 100

Router(config-if)#no shutdown

Router(config-if)#interface ethernet 1

Router(config-if)#ip address 192.168.1.5 255.255.255.252

Router(config-if)#ip ospf cost 10

Router(config-if)#no shutdown

2. Resumen

Open Shortest Path First (OSPF), Primer Camino Más Corto, es un protocolo de red para encaminamiento jerárquico de pasarela interior o Interior Gateway Protocol (IGP), que usa el algoritmo Dijkstra, para calcular la ruta más corta entre dos nodos.

Su medida de métrica se denomina cost, y tiene en cuenta diversos parámetros tales como el ancho de banda y la congestión de los enlaces. OSPF construye además una base de datos enlace-estado (Link-State Database, LSDB) idéntica en todos los routers de la zona.

OSPF puede operar con seguridad usando MD5 para autenticar sus puntos antes de realizar nuevas rutas y antes de aceptar avisos de enlace-estado.

OSPF es probablemente el protocolo IGP más utilizado en redes grandes; IS-IS, otro protocolo de encaminamiento dinámico de enlace-estado, es más común en grandes proveedores de servicios. Como sucesor natural de RIP, acepta VLSM y CIDR desde su inicio. A lo largo del tiempo, se han ido creando nuevas versiones, como OSPFv3 que soporta IPv6 o las extensiones multidifusión para OSPF (MOSPF), aunque no están demasiado extendidas. OSPF puede "etiquetar" rutas y propagar esas etiquetas por otras rutas.

Interfaces

Los nodos de una red basada en OSPF se conectan a ella a través de una o varias interfaces con las que se conectan a otros nodos de la red. El tipo de enlace define la configuración que asume la interfaz correspondiente. OSPF soporta los siguientes tipos de enlace, y provee para cada uno de ellos una configuración de interfaz:

·         Punto a punto (point-to-point, abreviado ptp), cuando la interfaz está conectada exclusivamente a otra interfaz.

·         Punto a multipunto (point-to-multipoint, abreviado ptmp).

·         Broadcast, para enlaces en los que todas las interfaces pueden conectarse directamente entre ellas. El ejemplo típico de enlace broadcast es el que corresponde a una red de tipo Ethernet.

·         Enlace virtual (virtual link), cuando no responde a una topología física.

·         Enlace de acceso múltiple acceso sin difusión (Non-Broadcast Multiple Access, NBMA), para enlaces en los que el medio es compartido, pero no todas las interfaces participantes pueden comunicarse directamente entre sí.

3. Summary

Open Shortest Path First (OSPF), Shortest First Path, is a network protocol for hierarchical routing of the internal Gateway or Interior Gateway Protocol (IGP), which uses the Dijkstra algorithm, to calculate the shortest route between two nodes.

Its metric measure is called cost, and it takes into account various parameters such as bandwidth and link congestion. OSPF also builds an identical link-state database (LSDB) on all routers in the area.

OSPF can operate safely using MD5 to authenticate its points before making new routes and before accepting link-state announcements.

OSPF is probably the most used IGP protocol in large networks; IS-IS, another link-state dynamic routing protocol, is more common in large service providers. As a natural successor to RIP, it accepts VLSM and CIDR from its inception. Over time, new versions have been created, such as OSPFv3 that supports IPv6 or the multicast extensions for OSPF (MOSPF), although they are not too widespread. OSPF can "tag" routes and propagate those labels by other routes.

Interfaces

The nodes of an OSPF-based network connect to it through one or more interfaces with which they connect to other nodes in the network. The type of link defines the configuration assumed by the corresponding interface. OSPF supports the following types of links, and provides an interface configuration for each of them:

o   Point-to-point, abbreviated ptp, when the interface is connected exclusively to another interface.

o   Point to multipoint (point-to-multipoint, abbreviated ptmp).

o   Broadcast, for links in which all interfaces can connect directly to each other. The typical broadcast link example is the one corresponding to an Ethernet type network.

o   Virtual link (virtual link), when it does not respond to a physical topology.

o   Non-broadcast access multiple access link (NBMA), for links in which the medium is shared, but not all participating interfaces can communicate directly with each other.

4. Recomendaciones

Ø  Si un router tiene todas las interfaces en una sola área, en vez de gastar el tiempo declarando cada red de manera independiente, podemos utilizar el comando: “network 0.0.0.0 255.255.255.255 area n”. A menos que tengamos requerimientos especiales que necesiten la declaración específica, el cual en este caso podríamos emplear la primera recomendación.

Ø  Tener mucho cuidado con la declaración de las interfaces en el proceso OSPF ya que esto implica la emisión de paquetes Hello, a través de interfaces que no deseamos que las emitan (interfaces de acceso, por ejemplo), por lo que el comando passive-interface y la configuración de autenticación pueden ayudar a evitar brechas de seguridad.

Ø  Si las direcciones IP de un área específica están bien asignadas, podemos utilizar UN solo comando “network” para cubrir TODA el área.

5. Conclusiones

§  El protocolo puede ser implementado en enlaces como de borde externo y tiene excelentes alternativas desarrolladas por proyectos open source tales como OpenOSPFD.

§  Aprendí a definir el router principal y de respaldo a través de las direcciones loopback.

§  También aprendí que el protocolo ospf es un protocolo de estado de enlace, la gran ventaja al utilizar este protocolo y la funcionabilidad de este.

6. Apreciación del Equipo

v Podemos usar o enviar información de manera que el router nos va a dar o indicar cuál es el mejor camino, ya que si un cable se daña podemos usar otro camino sin importar su ancho de banda, claro siempre vamos a usar el que tenga más ancho de banda, pero si falla usara uno de respaldo para que el paquete llegue hasta donde lo estamos enviando. ya que estamos usando un diseño donde se está implementada redundancia.

v Tener en cuenta en hacer las configuraciones bien antes de implementar el protocolo, como por ejemplo tener en cuenta que los ID no se repitan y/o no sean el mismo en todos los routers. 

v Es muy importante tener en cuenta que en el momento de agregar y/o enseñarles las direcciones de red a los routers implementado el protocolo OSPF debemos ver que si estén o pertenezcan a la misma área para que se puedan comunicar ya que podemos crear varias áreas, pero solo se comunicaran las que estén en esa área.

7. Glosario de Términos

DBD: El paquete de Descripción de bases de datos (DBD) incluye una lista abreviada de la base de datos de estado de enlace del router emisor y lo utilizan los routers receptores para comparar con la base de datos de estado de enlace local.

LSR: Los routers receptores pueden luego solicitar más información acerca de una entrada en la DBD enviando una Solicitud de estado de enlace (LSR).

LSU: Los paquetes de Actualización de estado de enlace (LSU) se utilizan para responder las LSR y para anunciar nueva información. Las LSU contienen siete tipos diferentes de Notificaciones de estado de enlace (LSA). Las LSU y LSA se analizan brevemente en un tema posterior.

LSAck: Cuando se recibe una LSU, el router envía un Acuse de recibo de estado de enlace (LSAck) para confirmar la recepción de LSU.

WILDCARD-MASK:  Al igual que con EIGRP, la máscara wildcard puede configurarse en forma inversa a una máscara de subred. Por ejemplo, la interfaz FastEthernet 0/0 de R1 se encuentra en la red 172.16.1.16/28. La máscara de subred para esta interfaz es /28 ó 255.255.255.240. Lo inverso a la máscara de subred es la máscara wildcard.

ALGORITMO OSPF: Cada router OSPF mantiene una base de datos de estado de enlace que contiene las LSA recibidas por parte de todos los demás routers. Una vez que un router recibió todas las LAS y creó su base de datos de estado de enlace local, OSPF utiliza el algoritmo shortest path first (SPF) de Dijkstra para crear un árbol SPF.

COMANDO ROUTER OSPF: OSPF se habilita con el comando de configuración global router ospf process-id. El comando process-id es un número entre 1 y 65535 elegido por el administrador de red. El comando process-id es significativo a nivel local, lo que implica que no necesita coincidir con otros routers OSPF para establecer adyacencias con dichos vecinos.

NETWORK: El comando network utilizado con OSPF tiene la misma función que cuando se utiliza con otros protocolos de enrutamiento IGP.

UIT (Unión Internacional de Telecomunicaciones): Organismo internacional, con sede en Ginegra, cuya misión es definir estándares para las redes de comunicación.

WAN (Red de Área Amplia): red que permite conectar físicamente varios ordenadores, y cuya titularidad es pública. Son las Redes Públicas de Datos, normalmente. En ellas se basa la Red Internet.

WAP (Wireless Access protocol): protocolo de acceso sin hilos, utilizado para la transmisión de datos a través de Internet desde un teléfono móvil a un servidor internet. Es un protocolo que se puede utilizar siempre que se trate de acceso de ordenadores a internet a través de redes inalámbricas.

8. Bibliografía o Linkografía

Ø https://www.ibm.com/support/knowledgecenter/es/ssw_ibm_i_73/rzajw/rzajwospf.htm

Ø  https://www.ecured.cu/Algoritmo_de_Dijkstra

Ø  http://www.redescisco.net/sitio/2011/08/11/tipos-de-areas-en-ospf/

Ø https://www.ibm.com/support/knowledgecenter/es/ssw_ibm_i_73/rzajw/rzajwospf.htm