• Author / Uploaded
• Fasabi Rojas

Citation preview

FACULTAD DE INGENIERIA EN

INFORMATICA Y SISTEMAS

FACULTAD DE INGENIERÍA EN INFORMÁTICA Y SISTEMAS

TEMA: OSPF

QUE PRESENTA A:  ALUMNO: ROJAS FASABI LUIS MELBIN  DOCENTE: ING. SANTILLAN RUIZ, JOSE  CURSO : REDES Y TELECOMUNICACIONES II a.

SEMESTRE ACADEMICO: 2018 - II

b. MES Y AÑO :

OCTUBRE – 2018

CAPITULO 1

2

Objetivo

El objetivo de este trabajo de investigación es explicar cómo se diseña e implementa el protocolo OSPF, que está orientado para redes grandes, proporcionando también un respaldo de conocimiento de cómo es el protocolo OSPF, un protocolo de estado de enlace, sus funcionamientos, así como un conocimiento del Diseño y la implementación del Protocolo OSPF, en la red a diseñar e implementar. Con esto se espera proveer suficiente información para la selección de dicho protocolo, para su implementación en una red con direccionamiento clase B.

Las limitaciones de esta investigación serían las configuraciones de cada ruteador en toda la red, tan solo se mostrarán configuraciones de ruteadores, los cuales se considere clave en la arquitectura de la Red de OSPF. Para ello se realiza la información de las siguientes tesis elaborados en la escuela de ingeniería electrónica en telecomunicaciones y redes con el tema de análisis de los protocolos OPSF aplicando la redundancia Gateway; y la siguiente tesis de la configuración de protocolo OPSF en una topología de red WAN por el ingeniero Alejandro García romero. Justificación

Mediante esto busca dar un panorama nuevo y diferente en la implementación y diseño de redes grandes de alta confiabilidad. En redes grandes cuyos sistemas y recursos tecnológicos existentes son ya de poco fiar debido a su crecimiento, y a su exigencia de confiabilidad y de la necesidad de la alta disponibilidad de sus recursos de red, dado que las redes en OSPF son por zonas independientes, si una ruta se vuelve indisponible solo en su área se escucha su indisponibilidad, no disparando el mecanismo de avisos a toda la red; cosa que hacen otros protocolos.

3

Metodología Cabe aclarar que para fines explicativos, se utilizarán direccionamientos diferentes al utilizado por la implementación final de esta investigación. A través de la documentación en los capítulos se mostrara la tecnología OSPF para que se proceda a la instalación e implementación de OSPF, con el tipo de Red y dispositivos ya antes mencionados. Para utilizar este mecanismo se utiliza los siguientes pasos: • Pasol: Analice los Requerimientos • Paso 2 Desarrollo de la Topología de la Red • Paso 3: Determinación del Direccionamiento y la Convención de los Nombres • Paso 4: Provisión del Hardware • Paso 5: Aprovechamiento del Protocolo y las Características del IOS • Paso 6: Implementación Monitoreo y Manejo de la Red

4

CAPITULO 2

5

INTRODUCCIÓN DE OSPF 1. OPSF OSPF es un protocolo de ruteo dinámico estándar definido en la RFC 2328 para IPv4 y en la RFC 5340para IPv6. Su función (por ser un protocolo de ruteo) es la de recolectar la información necesaria para armar las tablas de ruteo. Se lo puede clasificar como protocolo de estado de enlace y, a su vez, dentro del grupo de los IGP (Interior Gateway Protocolo), dado que está pensado para ser utilizado dentro del dominio de un sistema autónomo.

CARACTERÍSTICAS BÁSICAS DE OSPF 

Estándar y de especificación abierta.



Intra sistema autónomo.



Converge rápidamente.



Soporta diseño jerárquico, lo que lo hace muy escalable.



Envía actualizaciones disparadas y sólo con la información que cambia.



Se comunica utilizando multicast.



Soporta autenticación.

2. INFORMACIÓN UTILIZADA POR OSPF OSPF mantiene tres tablas: 

Tabla de ruteo: el objetivo de cualquier protocolo de ruteo, lograr una tabla que dada una red de destino indique el camino para alcanzarla.



Tabla de adyacencias (o de vecinos): en esta tabla se mantiene la información sobre los vecinos con los cuáles se realizan intercambios OSPF.



Tabla de topología (o base de datos de LSA): en esta tabla se almacenan todos los LSA recibidos de toda la red. Los LSA son paquetes OSPF que contienen información sobre rutas (red y camino 6

para alcanzarla). De esta manera es como un router OSPF conoce la topología completa de la red. De hecho, utilizando la tabla de topología es posible dibujar toda la red con los costos de cada enlace.

3. ALGORITMO OSPF El algoritmo de OSPF puede resumirse en los siguientes pasos: A. Lo primero que se necesita es formar adyacencias con los vecinos directamente conectados. Por ello, todos los routers de la red envían paquetes de saludo por todas sus interfaces. Con esta información, un router OSPF conoce sus vecinos que será con los que se mantendrá en contacto para enviar la información de ruteo. B. Si se tratara de una red multiacceso como Ethernet entonces deberá elegirse un router designado (DR) y un router resignado de respaldo (BDR). El objetivo es disminuir el tráfico de ruteo intercambiado en la red haciendo que los routers se comuniquen sólo con el DR y el BDR. En un próximo post explicaré con más detalle este tema. C. Una vez establecidas las adyacencias, el siguiente paso es enviar la información de ruteo mediante paquetes LSU (un paquete que uno o más LSA) a todos los vecinos, lo que provoca una inundación (flooding) de LSU en la red. D. Terminado el paso anterior, todos los routers tienen la tabla de topología completa y ya es posible calcular las rutas más cortas hacia cada destino, lo que se hace ejecutando el algoritmo de Dijkstra (o algoritmo de SPF). Este es un proceso que ejecuta cada router OSPF por sí mismo y sin intervención de ningún otro router.

7

E. En el paso anterior se arma la tabla de ruteo con lo cual luego del mismo un router OSPF ya puede comenzar a rutear paquetes. A partir de ahora el intercambio entre los equipos serán: a. Paquetes de saludo: se envían de forma periódica para mantener las adyacencias y detectar la caída de un equipo vecino. b. Actualizaciones de estado de enlace (LSU): enviadas sólo si el estado de algún enlace cambia.

4. PROTOCOLOS RIP/OSPF/BGP RIP

(Routing

information

protocolo,

protocolo

de

información

de

encaminamiento) RIP es un protocolo de encaminamiento interno, es decir para la parte interna de la red, la que no está conectada al backbone de Internet. Es muy usado en sistemas de conexión a internet como infovia, en el que muchos usuarios se conectan a una red y pueden acceder por lugares distintos. Cuando un usuarios se conecta el servidor de terminales (equipo en el que finaliza la llamada) avisa con un mensaje RIP al router más cercano advirtiendo de la dirección IP que ahora le pertenece. Así podemos ver que RIP es un protocolo usado por distintos routers para intercambiar información y así conocer por donde deberían enrutar un paquete para hacer que éste llegue a su destino.

5. OSPF (Open shortest path first, El camino más corto primero) OSPF se usa, como RIP, en la parte interna de las redes, su forma de funcionar es bastante sencilla. Cada router conoce los routers cercanos y las direcciones que posee cada router de los cercanos. Además de esto cada router sabe a que distancia (medida en routers) está cada router. Así cuando tiene que enviar un paquete lo envía por la ruta por la que tenga que dar menos saltos. Así por ejemplo un router que tenga tres conexiones a red, una a una red local en la que hay puesto de trabajo, otra (A) una red rápida frame relay de 48Mbps y una línea (B) RDSI de 64Kbps. Desde la red local va un paquete a W que 8

esta por A tres saltos y por B a dos saltos. El paquete iría por B sin tener en cuenta la saturación de la linea o el ancho de banda de la linea. La O de OSPF viene de abierto, en este caso significa que los algoritmos que usa son de disposición pública.

6. BGP (BORDER GATEWAY PROTOCOL, PROTOCOLO DE LA PASARELA EXTERNA) BGP es un protocolo muy complejo que se usa en la interconexión de redes conectadas por un backbone de internet. Este protocolo usa parámetros como ancho de banda, precio de la conexión, saturación de la red, denegación de paso de paquetes, etc. para enviar un paquete por una ruta o por otra. Un router BGP da a conocer sus direcciones IP a los routers BGP y esta información se difunde por los routers BGP cercanos y no tan cercanos. BGP tiene su propio mensaje entre routers, no utiliza RIP. BGP es usado por grandes proveedores de conectividad a internet. Por ejemplo una empresa (A) tiene alquilada una línea a telefónica-data. La empresa A no hace BGP y posiblemente los routers más cercanos no utilizarán BGP pero si los que interconecten Telefónica-Data con Hispanix (punto neutro de interconexión en España).

7. QUE ES ENCAMINAMIENTO VS. REENVÍO Encaminamiento no es lo mismo que reenvío • Encaminamiento es la creación de mapas • Cada protocolo tiene su propia base de datos • Los protocolos de encaminamiento crean la tabla de reenvío • Reenvío es pasar el paquete al próximo salto • La tabla de encaminamiento contiene la mejor ruta al próximo salto para cada prefijo IP • Solo hay UNA tabla de reenvío

9

8. ENRUTAMIENTO TIPO ESTADO DEL ENLACE • Descubrimiento automático de vecinos, Los vecinos son routers conectados físicamente • Cada router construye un Link State Packet (LSP) Distribuye el LSP a sus vecinos

utilizando un LSA (Link State

Advertisement) • Cada router calcula su mejor ruta a cada destino • Cuando hay un fallo en la red Se difunden nuevos LSPs todos los routers recalculan el árbol del camino más corto

REQUERIMIENTOS MÍNIMOS DE ANCHO DE BANDA

• Sólo se propagan los cambios

• Se utiliza Multicast en las redes multi-acceso • 224.0.0.5 para todos los routers OSPF • 224.0.0.6 para los routers DR y BDR “SHORTEST PATH FIRST” La ruta óptima se determina por la suma de los costos de las interfaces: Costo = 108/capacidad

10

9. OSPF: CÓMO FUNCIONA Protocolo Hello • Responsable de establecer y mantener las relaciones de vecindad • Elije el router designado en las redes brodcast

• Protocolo Hello

• Los mensajes Hello se envían periódicamente desde todas las interfaces donde OSPF está habilitado • Se forman “adyacencias” entre algunos vecinos • Paquete Hello • Contiene información como la prioridad del router, intervalo de Hello, lista de vecinos conocidos, intervalo de router muerto y la máscara IP • Intercambio de información usando LSAs • Los LSAs se agregan a la base de datos OSPF • Los LSAs se pasan a otros vecinos • Cada router construye una base de datos de enlaces idéntica • Se ejecuta el algoritmo SPF usando la base de datos • Se construye la tabla de reenvío a partir del árbol SPF

11

Cuando ocurre un cambio: • Se anuncia el cambio a todos los vecinos • Todos los routers efectúan el algoritmo SPF en la base de datos revisada • Se instala cualquier cambio en la tabla de reenvío

REDES BROADCAST • Estas son las redes como Ethernet • Se utilizan un router designado y uno de backup (DR y BDR) • Sólo el DR y el BDR forman adyacencias completas con los demás routers • El resto de los routers permanece en un estado “2- way” entre sí • Si fueran adyacentes, tendríamos un problema de escalabilidad tipo ncuadrado • Si el DR o el BDR “desaparecen”, se comienza una reelección

ENRUTADOR DESIGNADO (DR) Uno por cada segmento de red • Genera anuncios de enlaces de red para el segmento • Acelera la sincronización

• Todos los routers son adyacentes al DR • Todos los routers son adyacentes al BDR también • Todos los routers intercambian información den enrutamiento con el DR • BDR también se sincroniza con el DR • El DR actualiza la base de datos de todos sus vecinos 12

• El BDR espera en silencio y sólo actúa si el DR se cae • Esto puede crecer de manera sostenible! • Se vuelve un problema 2n en lugar de n-cuadrado.

• Las adyacencias sólo se forman con el DR y BDR • Los LSAs se propagan a lo largo de las adyacencias

PRIORIDAD DEL ROUTER DESIGNADO • Determinado por la prioridad de la interfaz • De lo contrario, por el ID del router mayor • (En IOS, esta es la dirección de la interfaz loopback, de lo contrario,

la IP mayor del router)

13

OSPF MÁS AVANZADO • Áreas OSPF • Enlaces virtuales • Clasificación de los enrutadores • Tipos de rutas OSPF • Rutas externas • Autenticación de rutas • Multi-rutas de costo equivalente

AREAS OSPF • Grupos de nodos y enrutadores contiguos • Base de datos topológica por área • Invisible fuera del área • Reducción de tráfico de ruteo • Contiguas al área dorsal • Todas las demás áreas deben estar conectadas a la dorsal • Enlaces virtuales • Reduce el tráfico de ruteo en el área 0 • Considere subdividir la red en áreas • Cuando el área 0 tenga más de 10 o 15 routers • Cuando la topología del área 0 se complique demasiado • El diseño de las áreas suele corresponder con el diseño típico del núcleo de la red en los ISPs. • Los enlaces virtuales se utilizan para situaciones con topologías extrañas

14

ENLACES VIRTUALES • OSPF requiere que todas las áreas estén conectadas al área 0 • Si la topología fuera tal que un área no pudiese tener una conexión física al área 0, entonces se debe configurar un enlace virtual • De lo contrario, el área desconectada solamente podrá tener conectividad con su área contigua, y no con el resto de la red

CLASIFICACIÓN DE LOS ROUTERS

Internal Router (IR) Área Border Router (ABR) Backbone Router (BR) Autonomous System Border Router (ASBR)

15

TIPOS DE RUTAS OSPF

RUTAS EXTERNAS Métrica externa tipo 2: Las métricas se comparan sin añadir los costos internos

10.

AUTENTICACIÓN DE RUTAS

Se recomienda utilizar autenticación en OSPF y en otros protocolos de enrutamiento Es susceptible a ataques de denegación de servicio OSPF utiliza TCP/IP para su transporte descubrimiento de vecinos automático Autenticación de rutas– Ejemplo de Cisco: router ospf network 192.0.2.0 0.0.0.255 area 0 16

area 0 authentication interface ethernet 0/0 ip ospf authentication-key

MULTI-RUTAS DE COSTO EQUIVALENTE (EQUAL COST MULTIPATH)

Si hay n rutas al mismo destino con costo equivalente, OSPF instalará n entradas en la tabla de reenvíos: 

Balanceo de carga sobre las n rutas



Útil para expandir enlaces a través de la dorsal de un ISP



No se necesitan multiplexores en hardware



No se necesitan rutas estáticas

OSPFv3 • OSPFv2 sólo soporta IPv4 • OSPFv3 desarrollado para IPv6 solamente • Redes de doble pila necesitan activar ambos protocolos • Son independientes uno del otro OSPFv2 vs. OSPFv3 • Muy similar, con algunas diferencias: • Nuevos tipos de LSAs para separar los enlaces de los prefijos asociados a estos. • Evita recalcular el algoritmo SPF cuando sólo el prefijo IP cambia • No incluye autenticación dentro de OSPF • Utiliza los encabezados de seguridad de IPv6 • Soporta múltiples instancias

17

CAPITULO 3 OSPF

18

3.1 OSPF (La Primera Trayectoria Más Corta Abierta) OSPF (Open Short Firt Path) es un protocolo de encaminamiento de estado de enlace. Se diseña para ser de funcionamiento interno en solo Sistema Autónomo. Cada Ruteador de OSPF mantiene una base de datos idéntica que describe la topología del sistema autónomo. De esta base de datos, una tabla de encaminamiento es calculada construyendo un camino más corto de trayectoria.

OSPF recalcula las rutas rápidamente cuando encara cambios topológicos, utilizando un mínimo de tráfico de protocolo de encaminamiento. OSPF proporciona ayuda para la repartición equitativa de costos multidireccionales. Se proporciona una capacidad de encaminamiento de área, permitiendo un nivel adicional de protección de encaminamiento y de una reducción en el tráfico de protocolo de encaminamiento. Además, se autentifican todos los intercambios del protocolo de encaminamiento de OSPF. La meta del algoritmo de la trayectoria más corta de Edsger Dijkstra es encontrar la ruta más corta entre dos puntos con una serie. Para describir la operación de su algoritmo en los términos del claros, mire el ejemplo siguiente.

Suponga que usted está intentando encontrar la trayectoria más corta entre dos Ciudades: lima y Trujillo (un sistema base de ruteadores). El propósito en este ejemplo es determinar el tiempo mínimo necesario para conducir a cada ciudad (ruteador) en una base expandida de ciudades (red). La secuencia para encontrar este valor mínimo de tiempo es como sigue: 1. Comience en la ciudad de origen (ruteador). El tiempo (distancia) necesitó para alcanzar esta ciudad es, por supuesto, cero porque es su origen. 2. Entonces usted descubre una ciudad nueva, que usted llamará la ciudad X (ruteador), que usted desea alcanzar.

19

 Si el tiempo de conducir (distancia) a la ciudad X es más corto que el tiempo de conducir a cualquier otra ciudad fuera del sistema base.  Si el tiempo de conducir a la ciudad X es el tiempo mínima de conducir a la ciudad Y en la base fijada de Atlanta, más el tiempo de conducir de Y a X. 3. Entonces agregue la ciudad X al sistema de la base (red), y registre el tiempo es computado (distancia) 4. Si es una ciudad es llamada Boston entonces listo, si no, se repite.

Este ejemplo ayuda a demostrar la razón detrás del nombre del algoritmo.

Estas características y porque la especificación fue desarrollada en una manera abierta por el IETF explican el nombre del protocolo OSPF " la primera trayectoria más corta abierto ". También, el protocolo de OSPF es un estándar abierto que permite la publicación de todos los datos referente a su diseño y función. Esta información se ha publicado en una serie de RFCs. OSPF encamina los paquetes de IP basados solamente en la Dirección IP de destinación encontrada en el encabezado del paquete de IP. Se encaminan los paquetes de IP "como son" ~ no se encapsulan en cualquier otro encabezado de otro protocolo como para transitar en el Sistema Autónomo. El OSPF es un protocolo dinámico de encaminamiento. Detecta rápidamente cambios topológicos en el AS (por ejemplo las fallas de interfaz del ruteador) y calcula las rutas libres de bucles, nuevas después del período de la convergencia. Cada ruta externa se puede también marcar con etiqueta por el ruteador de publicidad, permitiendo pasar la información adicional entre los Ruteadores de Frontera del Sistema Autónomo.

20

3.2 Ambiente Funcional del OSPF Esta sección describe las características básicas y las características del ambiente funcional de OSPF. El ambiente en el cual OSPF funciona es definido por las características de su operación y de diseño. Puesto simplemente, que el ambiente funcional de OSPF define pues la arquitectura de red, en la cual el protocolo funcionará correctamente. Con ese ejemplo en mente, aquí se presentan los tres tipos de red que OSPF reconoce.

3.2.1 Tipos de Redes en OSPF

21

Punto a Punto. Un solo circuito que conecta dos ruteadores de OSPF, que permitirán que una sola relación vecina sea construida. Multiacceso: Un circuito que tiene por lo menos dos ruteadores de OSPF conectados con él y les permite comunicarse uno a otro. Esto proporciona el potencial para las relaciones vecinas múltiples y para ser formadas las adyacencias, pero de prevenir esto, un ruteador designado como (DR) construye todas las adyacencias y las distribuye hacia fuera a todos los ruteadores conectados

3.2.2 Redes de Multiacceso de no Difusión En un medio de Multiacceso de no Difusión (NBMA) Las redes de NBMA son muy similares a las redes de multiacceso, con la excepción que no permiten el tráfico de difusión (por ejemplo, X.25) Las redes de NBMA también tienen el potencial para las adyacencias múltiples, pero los circuitos virtuales pueden no conectar todos los ruteadores. En algunos casos, esto requeriría que las adyacencias sean configuradas manualmente.

Si usted se preguntara por las redes punto Multipunto el RFC de OSPF lo explica mejor: en una de dos redes grandes de modos de no difusión. El primer modo, llamado de no difusión, de multiacceso o NBMA, simula la operación de OSPF en una red de difusión. El otro modo, llamado punto a multipunto, trata la red de no difusión como enlaces colectivos de un punto a punto Las redes de no difusión se refieren como red de NBMA

3.2.3 Identificación De Ruteador Cada ruteador que funciona en OSPF dentro de una red debe tener una identificación única de ruteador. Éste es el número de ficción que es de 32-bit, un número con el cual se identifica un ruteador de otro, en el Sistema Autónomo (AS). La identificación del ruteador es utilizada por la base de datos de estado de enlace de OSPF (como método a seguir para cada ruteador en el AS y la asociación de los enlaces a él)

22

Al configurar la Dirección de IP para su interfaz de loopback, tenga presente que no debe ser una dirección IP "verdadera", que utiliza un espacio de dirección valioso. La alternativa es utilizar una Dirección de IP "falsa", que es esencialmente Una Dirección IP hecha que no es parte del rango normal de Direcciones IP de su red. El RFC 1597 pude ser un buen lugar para comenzar si usted decide utilizar este método de hacer que el primer octeto dure.

3.2.4 Vecinos OSPF considera que dos ruteadores tengan una interfaz situada en una red común como vecinos. Cuando OSPF descubre a sus vecinos, éste es el primer paso de descubrir la red y de construir una tabla de encaminamiento. Este proceso comienza por el ruteador que aprende los números de identificación de los ruteadores. En redes de multiacceso, el protocolo de OSPF descubre a estos vecinos dinámicamente mediante los Helios, que serán discutidos más tarde.

Para construir las relaciones de vecinos estables de OSPF, asegúrese de que el número de ruteadores por LAN sea pequeño. Utilice el comando de prioridad para organizar quien es el DR y de evitar de tener el mismo ruteador de DR para más de un enlace, con el uso del comando de prioridad de OSPF.

3.2.5 Adyacencias Para las adyacencias, OSPF debe primero haber descubierto a sus vecinos. Las adyacencias se forman con el fin de intercambiar información de encaminamiento. No cada ruteador vecino formaría una adyacencia. Las seis condiciones bajo las cuales el OSPF formará adyacencias son las siguientes: • La conectividad de la red es punto a punto • El Ruteador es el Ruteador Designado (DR) • El Ruteador vecino es el Ruteador Designado (DR) • El Ruteador es el ruteador DR de respaldo • El Ruteador vecino es el ruteador DR de respaldo 23

Las adyacencias controlan la distribución de las actualizaciones de encaminamiento en el sentido de que solamente los ruteadores adyacentes a este solo envían actualizaciones y las procesan.

3.3.6 Ruteadores Designados OSPF construye adyacencias entre los ruteadores para propósitos de intercambiar la información de encaminamiento. Cuando OSPF tiene que ocuparse de ambientes de multiacceso de no difusión (NBMA) o redes de Difusión, sin embargo, estos representan un problema en sí mismo. En estos tipos de redes, existen ruteadores múltiples, que darían lugar enteramente también a muchas adyacencias. Para combatir adyacencias superfluas el ruteador designado es introducido. Los pasos descritos en cómo se elige un DR, asumen que ninguno existe en esa red. Si éste no es el caso, el proceso se altera levemente y usted debe referirse al RFC 2328 para información adicional. 1. OSPF selecciona un ruteador al azar y examina su lista de vecinos; llame a este ruteador T. Esta es una lista de vecinos de ruteadores, que consiste en todos los ruteadores que han comenzado la comunicación bidireccional entre ellos mismos. Esta comunicación, se refiere como de "2 vías " y es el estado más avanzado de la comunicación, que los ruteadores vecinos pueden alcanzar sin realmente la formación de una adyacencia. 2. El ruteador T, quita de esa lista a todos los ruteadores que son inelegibles para ser DR. Esto consistiría en que los ruteadores que tiene una prioridad otorgada por el protocolo OSPF de 0. Se procede al siguiente paso con los ruteadores restantes en la lista. 3. El DR de respaldo se elige realmente primero, y se determina con los cálculos en los cuales el ruteador tiene la prioridad más alta. Si más de un ruteador tiene el mismo valor de prioridad, esencialmente se han enlazado. Los valores de la prioridad pueden ser definidos, o permitir los valores por defecto. OSPF tomará el ruteador con la identificación más alta de 24

ruteador para romper el lazo. Si hay ya un DR en existencia, entonces cualquier otro ruteador es inelegible para la elección en este punto. 4. Si ningún otro ruteador se ha declarado para ser el DR, entonces es asignado el de respaldo nuevamente para ser el DR. 5. Si el ruteador T ahora es el nuevo DR, después repita los pasos 3 y 4 para conseguir un DR de respaldo y para proceder al paso 6. Por ejemplo, si el ruteador T es el DR, no será elegible para la elección cuando se repita el paso 3. Esto se asegura, de que ninguna ruteador se declare DR y el respaldo DR. 6. Como resultado de estos cálculos, el ruteador T se ha convertido en DR y el ruteador de OSPF y el estado del sus interfaces se fija por consiguiente. Por ejemplo, el DR tiene un nuevo estado de interfaz de DR y el DR de respaldo tiene un estado de interfaz de DR diferente. 7. El DR ahora comenzará a enviar los paquetes Helio, para comenzar el proceso de construir las adyacencias necesarias, con el resto de los ruteadores de la red

3.3 Protocolos en OSPF Los ruteadores de OSPF se comunican con cada uno usando el protocolo de OSPF. OSPF funciona sobre IP, aunque OSPF se compone de tres sus protocolos:  el Helio  de Intercambio  el flooding. Las secciones siguientes discuten estos tres subprotocolos con mayor detalle. Todos los paquetes de OSPF comienzan con un encabezado común. La figura 3-2 ilustra una porción (por campo) del encabezado común, encontrado al principio de cada paquete publicado por un subprotocolo de OSPF.

25

3.3.1 Protocolo Helio El protocolo Helio es usado para tres principales tareas: • Para verificar que los enlaces estén operando. • Para Elegir el Dñ o el DR de respaldo, en redes de difusión o de no Difusión. • Para descubrir, establecer y mantener las relaciones entre los vecinos. Además, el protocolo Helio, es responsable de asegurarse de que la comunicación entre los vecinos de OSPF sea bidireccional (dos vías) Este tipo de comunicación se establece cuando el ruteador ve por sí mismo, la lista de los paquetes helios de sus vecinos.

3.3.2 Variación de Operación del Protocolo Helio Tipos de Redes en OSPF El protocolo Helio trabaja diferentemente en redes: punto a punto, multiacceso, y de Multi Acceso por No Difusión NBMA en OSPF. En redes de difusión, cada ruteador se anunciará periódicamente enviando multitrasmisiones de paquetes helio, que permiten descubrir a sus vecinos dinámicamente. En redes punto a punto o de punto a multipunto, el ruteador de OSPF enviará los paquetes helios a cada vecino con quien pueda comunicarse directamente. En redes de punto a punto, un paquete Helio de OSPF se envía como paquete de multitransmisión. En redes de punto a multipunto, podrían ser enviados como multitransmisión, si la capa de enlace de datos repliega el paquete. O la información del vecino pudiera configurarse para indicar quién envía las réplicas de los helios cuando la capa de enlace de datos no aplica, por ejemplo el modelo del servidor de ATM ARP. 26

3.3.3 Formato del paquete del Protocolo Helio Los paquetes del protocolo Helio de OSPF se ajustan al formato solamente en una dirección. Todos los paquetes de OSPF comienzan con un encabezado estandardizado de 24-bytes, que contenga la información que determina, si el proceso ocurrirá en el resto del paquete. Todos los campos en este formato son de 32 bits, a excepción de los campos siguientes: Intervalo Helio, que es 16 bit; Opciones, el cual es 8 bits; y el de prioridad, que es 8 bits. Version #

|Tipo

Packet length

Router ID Area ID Checksum I AuType Authentication Authentication

3.3.4 Protocolo de Intercambio Cuando dos ruteadores de OSPF han establecido una comunicación bidireccional, o comunicación de dos vías, sincronizarán sus bases de datos de encaminamiento (estado de enlace). Para los enlaces de punto a punto, los dos ruteadores se comunicarán la información directamente entre sí mismos. En los enlaces de red (es decir, redes de multiacceso por difusión o de no difusión) esta sincronización ocurrirá entre el nuevo ruteador de OSPF y el DR. El protocolo de intercambio primero se utiliza para sincronizar las bases de datos de encaminamiento (estado de enlace) Después de la sincronización, Versión #

3

Longitud del Paquete

ID del Ruteador ID del Area Checksurnl AuType

Checksurnl AuType Autenticación Autenticación

Hellointérvall

Mascara de Red Opciones RouterDeadinterval Ruteador Designado Ruteador Designado de respaldo Vecino 27

Rtr Pri

cualquier cambio en los enlaces del ruteador utilizarán el protocolo de flooding para poner al día todos los ruteadores de OSPF.

3.3.5 Protocolo de Flooding El subprotocolo de flooding de OSPF es responsable de distribuir y de sincronizar la base de datos de estado de enlace, siempre que un cambio ocurra a un enlace. Cuando un enlace cambia de estado (se cae), el ruteador que experimentó el cambio publicará un paquete de flooding que contiene el cambio de estado. Esta actualización inunda todo hacia todas las interfaces de los ruteadores. Con la tentativa de asegurarse de que el paquete de flooding haya sido recibido por todos sus vecinos, el ruteador continuará retransmitiendo la actualización hasta que recibe un reconocimiento de sus vecinos. Un enlace es cualquier tipo de conexión (Frame Ralay, Ethernet, etc) entre los ruteadores de OSPF.

28

3.4.1 Sincronización de las Bases de Datos de Estado de Enlace

1. Estableciendo de la comunicación bidireccional (2 vías): Logrado por los helios de descubrimiento de los ruteadores y de elección de un DR. 2. Estado de Exstart: Dos ruteadores vecinos forman una relación maestro/esclavo y convienen en una secuencia que comienza y que se incrementada para asegurar que los LSAs se reconozcan correctamente y ninguna duplicación ocurra. Los paquetes de descripción de base de datos (DD) son los que comienzan. 3. Estado de Intercambio. Los paquetes de descripción de la base de datos (DD) continúan fluyendo mientras que el ruteador auxiliar reconoce los paquetes del amo. En este paso, OSPF se considera operacional porque los ruteadores pueden enviar y recibir LSAs. 4. Estado de carga. Las peticiones de Estado de Enlace se envían a los vecinos que piden los anuncios recientes que todavía no se han descubierto. En esta etapa, el ruteador construye varias listas para asegurar que todos los enlaces estén actualizados y para ser reconocidos correctamente 5. Estado completo: Los ruteadores vecinos son completamente adyacentes porque sus bases de datos de estado de enlace se sincronizan completamente.

29

3.4.2 Tipos de Paquete de LSA Distintamente a los protocolos de vector de distancia (RIP o IGRP), OSPF no envía realmente su tabla de encaminamiento a otros ruteadores. En lugar, las tablas de encaminamiento se derivan de la base de datos de LSA.

3.4.3 Ejemplo de fa Operación de Avisos de Estado de Enlace Ahora que se han discutido los seis LSA y usted entiende cómo funcionan dentro del ambiente funcional de OSPF.

3.5 Base de Datos de estado de Enlace Los ruteadores de OSPF en la misma área todos tendrán la misma base de datos de estado de enlace y ejecutarán el mismo algoritmo de SPF. Los expedientes en esta base de datos son utilizados por el algoritmo de SPF para determinar la topología de la red y para computar la trayectoria más corta a una destinación. Las características de la base de datos de estado de enlace son como sigue: • Todos los ruteadores que pertenezcan a la misma área tienen la base de

datos de estado de enlace idéntica. • Calcular las rutas usando el SPF que se realiza por separado para cada área • El flooding de LSA se contiene dentro del área que experimentó el cambio 30

• La base de datos de estado de enlace se compone de los seis diversos tipos de LSA • Un ruteador tiene una base de datos de estado de enlace separada para cada área a la cual pertenezca.

3.6 Ruteadores y Redes 3.6.1 Sistemas Autónomos (AS) El algoritmo de SPF entonces se utiliza para computar la trayectoria más corta del ruteador local de OSPF a cada destinación dentro de la red. Mientras que estos cómputos funcionan y la trayectoria más corta es determinada, esta información se pone en una tabla de encaminamiento. De estos cómputos el ruteador deriva el ruteador del siguiente (salto) que se debe utilizar para alcanzar la destinación. Esta información es utilizada por el ruteador para encaminar los paquetes a su destinación.

3.6.2 Ruteo Jerárquico en OSPF Una de las características más importantes dentro del protocolo OSPF es su capacidad para utilizar una estructura del ruteo jerárquico. Hay dos características, que usted debe tener presente al considerar cómo OSPF funciona dentro de este tipo de estructura jerárquica. • La estructura debe existir o crear un orden para que OSPF funcione correctamente • La topología explícita tiene precedencia sobre la dirección

31

CAPITULO 4 CONCEPTOS BÁSICOS DE DISEÑO DE OSPF

32

4.1 Conceptos de Diseño de OSPF Algoritmos de OSPF. El algoritmo de OSPF será discutido en mayor detalle con la introducción de costos. Con la adición de costos, las tablas de encaminamiento de OSPF se alteran, y esta sección explica cómo y porqué. • Convergencia de OSPF. Esta sección cubre las ediciones que rodean la convergencia con el protocolo, incluyendo las ventajas de OSPF y de su capacidad de converger muy rápidamente. • Pautas Del Diseño del OSPF. Esta sección comienza la introducción para diseñar redes del OSPF y se concentra en dos puntos principales: topología y escabilidad de la red. Esta sección comienza a examinar los requisitos y la disposición físicas necesarias antes de que el trabajo real comience. • Consideraciones Del Diseño Del Área. Los fundamentos verdaderos de cualquier red de OSPF son sus áreas. El diseño apropiado de estas áreas es absolutamente esencial y se discuten muy diversas áreas: la espina dorsal, non-stub, y todas las variaciones del área de Stub. • Selección De Ruta de OSPF. El encaminamiento es la esencia de cada protocolo, y cómo el protocolo determina sus rutas es el área primaria el foco en esta sección. Se incluye dentro de este capítulo la capacidad inherente de OSPF para conducir balancear la carga. La derivación de rutas externas también se discute extensamente. • Direccionamiento de IP y Sumarización de Ruta en OSPF. Las técnicas generales y los procedimientos de sumarización de ruta usados por OSPF se examinan y se demuestran a través de diversos panoramas con los cuales un ingeniero de red puede tener contacto. Esta sección concluye con una discusión a profundidad de VLSM y las ventajas de su uso en su red de OSPF.

4.2 Algoritmos de OSPF El algoritmo de la trayectoria más corta por sí mismo es absolutamente complicado, y sus funcionamientos internos están realmente más allá del alcance de esta investigación. Pero entender su lugar y operación es esencial para la realización de una comprensión completa de OSPF el texto sigue

33

revisiones de la operación de calcular la trayectoria más corta y después aplica eso a un ejemplo

Topología de la red

34

4.3 Topología de Red de OSPF El OSPF trabaja lo mejor posible en un ambiente de encaminamiento jerárquico. La primera y la más importante decisión cuando diseña una red en OSPF es de determinar qué ruteadores y enlaces deben ser incluidos en la espina dorsal (área 0) y cuáles son incluidos en cada área. Lo siguiente son las tres características importantes de OSPF y su necesidad de una estructura de una estructura jerárquica: Varios artículos importantes para considerar cuando se diseña la topología para una red de OSPF (serán discutidas largamente en las secciones que siguen) son como sigue: • El número de ruteadores en un área. • El número de áreas conectadas a un ruteador frontera de área (ABR). • El número de vecinos para cualquier ruteador. • El número de las áreas soportadas por cualquier ruteador. • Seleccionar el ruteador designado (DR). • ELLSDB.

4.3.1 El Número de Ruteadores en un Área.

Generalmente, un área debe tener no más de 50 ruteadores. ¿Eso no significa que no funcionarán las redes con 60 o 70 ruteadores en un área, pero para porqué experimentar con la estabilidad si usted no lo necesita? Las áreas con enlaces inestables deben ser más pequeñas.

Sin

embargo,

esas

recomendaciones

se

hacen

de

acuerdo

con

recomendaciones "oficiales" de Cisco con respecto a redes del OSPF. Los estudios y las implementaciones verdaderas en el mundo han ido más lejos.

Por ejemplo, la estadística en la tabla 4-1 vine "del informe de estándar del OSPF del IETF.

35

Parámetro Ruteador en un Dominio Ruteador por una sola area Áreas por Dominio

mínimo

media

máxima

20

510

1000

20

560

350

1

23

60

4.3.2 Topologías de Red Totalmente Conectada contra Parcialmente Interconectado Las nubes de Multiacceso de no Difusión (NBMA), tales como Frame Relay o X.25, son siempre un desafío. La combinación de bajo ancho de banda y muchos LSA's es también perjudicial incluso para OSPF .Una topología parcialmente enlazada se ha demostrado que se comporta mucho mejor que una topología de la red totalmente enlazada.

4.3.3 Reglas de Oro para El Diseño de Áreas Entonces usted comienza a diseñar su red de OSPF, Primero será necesario que usted comenzará con el área 0, el área de la espina dorsal de cada red del OSPF. Hay dos reglas muy importantes, que si está seguido, le consigue comenzó correctamente: 1. Un área contigua de la espina dorsal debe estar presente. 2. El resto de las áreas deben tener una conexión al área de la espina dorsal.

36

Los siguientes son reglas más generales y las capacidades de OSPF que ayudarán a asegurarse de que su red de OSPF siga siendo flexible y proporciona, la clase de funcionamiento necesaria para entregar el servicio confiable a todos sus usuarios: • Considere la proximidad física al definir áreas • Reduzca el tamaño máximo de áreas si los enlaces son inestables. • Asegure las áreas individuales contiguas. • Utilice los parámetros de Retoque de OSPF.

4.3.3.1 Asegurando Continuidad en Áreas Individuales

Un área contigua en OSPF es un área en la cual una trayectoria puede ser trazada de cualquier ruteador en una área a cualquier ruteador en la misma área. Esto no significa que todos los ruteadores deben compartir un mismo común medio de red (como Ethernet).

37

4.3.3.2 Usando Parámetros de Retoque de OSPF

Recuerde, los ruteadores de Cisco no mostrarán los valores prefijados, en sus archivos de configuración. Los Parámetros de Retoque en OSPF son los siguientes: • ip ospf hello-interval (seconds) Este comando está por defecto a 10 segundos. Modificándose este valor usted puede especificar el intervalo de la transmisión de los paquetes helio enviados de una interfaz • ip ospf dead interval (seconds) Este comando omite un valor cuatro veces hola el intervalo. Este comando especifica cuánto tiempo los paquetes de una ruteador hola no deben haber sido vistos antes de que sus vecinos declaren la ruteador abajo. • ip ospf retransmission- interval (seconds) Este comando omite un valor de cinco segundos. Modificando este valor, usted puede especificar el número de segundos entre las retransmisiones de LSA. • ip ospf transmit-delay (seconds) Este comando omite un valor de un segundo. Modificando este valor, usted puede fijar la hora a retrasa antes de transmitir un LSA de un interfaz.

4.4 Áreas Stub Normales El comando de configuración area # stub comienza el encaminamiento del área stub. Las rutas externas que son anunciadas en el OSPF debe ser hecho vía el comando summary-address esto es hecho típicamente en un ASBR.

El comando que configura un área Stub es como sigue: area stub [no-summary] El comando que configura un costo por defecto en un área es como sigue: area area-id default-cost cost

38

CAPITULO 5 ALGORITMO DIJKSTRA MATEMATICAMENTE

39

HISTORIA Nació en Rotterdam, (Holanda) en 1930. a. En 1942, cuando Dijkstra tenía 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes, donde dio clases, fundamentalmente, de Griego, Latín, Francés, Alemán, Inglés, biología, matemáticas y química. En 1945, Dijkstra pensó estudiar Derecho y trabajar como representante de Holanda en las Naciones Unidas. Sin embargo, debido a su facilidad para la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. De hecho, cuando solicitó una licencia de matrimonio en 1957, tuvo que señalar que su profesión era físico teórico. Dijkstra continuó trabajando en el Centro Matemático hasta que aceptó un trabajo como desarrollador en Burroughs Corporation, en los Estados Unidos, a principio de la década de los 70. En 1972 ganó el Premio Turing ACM, y ,en 1974, el AFIPS Harry Good Memorial. Dijkstra se trasladó a Austin, Texas a principio de los 80. En 1984, se le ofreció un puesto en Ciencias de la Computación en la Universidad de Texas, donde ha permanecido desde entonces. Es miembro honorario de la Academia Americana de Artes y Ciencias y de Real Academia Holandesa de Artes y Ciencias. Además es miembro distinguido de la Sociedad de Computación Británica. Finalmente es Doctor Honoris Causa en Ciencias por la Queen's University Belfast. Una red de comunicaciones involucra un conjunto de nodos conectadas mediante arcos, que transfiere vehículos desde determinados nodos origen a otros nodos destino. La forma más común para seleccionar la trayectoria (o ruta) de dichos vehículos, se basa en la formulación de la ruta más corta. En particular a cada arco se le asigna un escalar positivo el cual se puede ver como su longitud La solución es encontrar la trayectoria más corta. Esperando que dicha trayectoria contenga pocos enlaces no congestionados; de esta forma los enlaces menos congestionados son candidatos a pertenecer a la ruta. Hay 40

algoritmos de ruteo especializados que también pueden permitir que la longitud de cada enlace cambie en el tiempo, dependiendo del nivel de tráfico de cada enlace. De esta forma un algoritmo de ruteo se debe adaptar a sobrecargas

temporales

y

rutear

paquetes

alrededor

de

nodos

congestionados. Dentro de este contexto, el algoritmo de ruta más corta para ruteo opera continuamente, determinando la trayectoria más corta con longitudes que varían en el tiempo 5. ALGORITMO DE DIJKSTRA El algoritmo de Dijkstra, es 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 dirigido y con pesos en cada arista.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo). 6. ALGORITMO Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

41

A. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.

B. Sea a = x (tomamos a como nodo actual).

C. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.

D. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es: si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi) E. Marcamos como completo el nodo a.

F. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados. Una vez terminado al algoritmo, D estará completamente lleno.

6.1. Complejidad Orden de complejidad del algoritmo: O(|V|2+|E|) = O(|V|2) sin utilizar cola de prioridad, O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).

Podemos estimar la complejidad computacional del algoritmo de Dijkstra (en términos de sumas y comparaciones). El algoritmo realiza a lo más n-1 iteraciones, ya que en cada iteración se añade un vértice al conjunto distinguido. Para estimar el número total de operaciones basta estimar el número de operaciones que se llevan a cabo en cada iteración. Podemos identificar el vértice con la menor etiqueta entre los que no están en S k 42

realizando n-1 comparaciones o menos. Después hacemos una suma y una comparación para actualizar la etiqueta de cada uno de los vértices que no están en Sk. Por tanto, en cada iteración se realizan a lo sumo 2(n-1) operaciones, ya que no puede haber más de n-1 etiquetas por actualizar en cada iteración. Como no se realizan más de n-1 iteraciones, cada una de las cuales supone a lo más 2(n-1) operaciones, llegamos al siguiente teorema.

TEOREMA: El Algoritmo de Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices. 6.2. PSEUDOCÓDIGO DIJKSTRA (Grafo G, nodo_fuente s) para u ∈ V[G] hacer distancia[u] = INFINITO padre[u] = NULL distancia[s] = 0 Encolar (cola, grafo) mientras que cola no es vacía hacer u = extraer_minimo(cola) para v ∈ adyacencia[u] hacer si distancia[v] > distancia[u] + peso (u, v) hacer distancia[v] = distancia[u] + peso (u, v) padre[v] = u 6.3. EJEMPLOS DE UN ALGORITMO DE DIJKSTRA El siguiente ejemplo se desarrollará con el fin de encontrar el camino más corto desde a hasta z:

43

Leyenda: 

Rojo: Aristas y vértices pertenecientes a la solución momentánea.



Azul: Aristas y vértices candidatos.

Paso 1

En este primer paso, podemos apreciar que hay tres candidatos: Los vértices b, c y d. En este caso, hacemos el camino desde el vértice a, hasta el vértice d, ya que es el camino más corto de los tres.jump!!! Solución momentánea:  

Camino: AD Distancia:5

Paso 2

44

Ahora, vemos que se añade un nuevo candidato, el vértice e, y el vértice c, pero esta vez a través del d. Pero el camino mínimo surge al añadir el vértice c. Solución momentánea: 

Camino: ADC



Distancia:9

Paso 3

En este paso no se añade ningún candidato más puesto que el último vértice es el mismo que en el paso anterior. En este caso el camino mínimo hallado es el siguiente: Solución momentánea: 

Camino: ADCB



Distancia:11

45

Paso 4

Como podemos comprobar, se han añadido dos candidatos nuevos, los vértices f y g, ambos a través del vértice b. El mínimo camino hallado en todo el grafo hasta ahora es el siguiente: Solución momentánea: 

Camino: ADCBF



Distancia:15

Paso 5

En este antepenúltimo paso, se añaden tres vértices candidatos, los vértices g, z y e. Este último ya estaba pero en esta ocasión aparece a través del vértice f. En este caso el camino mínimo, que cambia un poco con respecto al anterior, es: Solución momentánea: 

Camino: ADCBF 46



Distancia:17

Paso

6

En el penúltimo paso, vuelve a aparecer otro candidato: el vértice z, pero esta vez a través del vértice g. De todas formas, el camino mínimo vuelve a cambiar para retomar el camino que venía siguiendo en los pasos anteriores: Solución momentánea: Camino: ADCBFE Distancia: 18 Paso 7

Por fin, llegamos al último paso, en el que sólo se añade un candidato, el vértice z a través del e. El camino mínimo y final obtenido es: Solución Final: 

Camino: ADCBFEZ



Distancia:23 47

6.4. Ejemplo N° 2 Aplicar el algoritmo de Dijkstra sobre el siguiente grafo siendo el nodo origen

15

4

2

100

10

20

50

1

30

3

48

60

5

CONJUNTO ETAPA

CANDIDATOS

SELECCIÓN

CONJUNTO

VECTOR D

VECTOR P

S C

1

3 -30

1

2 -100

(2,3,4,5)

(1) 1

2

3

4

5

1 2 3 4 5

INICIO

0

1

2 - 100

Nodo 3

(2,4,5)

(1,3)

1

0

2

3

4

5

1 2 3 4 5

1 0 2

3

1

3

4 - 40

1

3

5 - 90

1

2 - 100

Nodo 4

3

5 -90

1

3

4

1

3

5 - 90

1

3

4 - 90

(1,3,4)

1

2

(5)

5

30

40

()FIN

1 2 3 4 5

2

3

4

5

1 2 3 4 5

0 55

30

40

90

0 4 2 3

2

3

4

5

1 2 3 4 5

0 55

30

40

90

0 4 1 3 5

0

(1,2,3,4)

5 55

1

4

1

Nodo 5

0

3

0 Nodo 2

1

(2,5)

10

1 3

(1,2,3,4,5)

1 4

49

50

CAPITULO 5 ALGORITMO DIJKSTRA EN UN LENGUAJE DE PROGRMACION C ++

51

ALGORITMO EN PSEUDOCÓDIGO Considerar distancia[i] como la distancia más corta del vértice origen ingresado al vértice i. 1 método Dijkstra (Grafo, origen): 2

creamos una cola de prioridad Q

3

agregamos origen a la cola de prioridad Q

4

mientras Q no este vacío:

5

sacamos un elemento de la cola Q llamado u

6

si u ya fue visitado continuo sacando elementos de Q

7

marcamos como visitado u

8

para cada vértice v adyacente a u en el Grafo:

9

sea w el peso entre vértices ( u , v )

10

si v no ah sido visitado:

11

Relajacion( u , v , w )

1 método Relajacion( actual , adyacente , peso ): 2

si distancia[ actual ] + peso < distancia[ adyacente ]

3

distancia[ adyacente ] = distancia[ actual ] + peso

4

agregamos adyacente a la cola de prioridad Q

52

EJEMPLO Y CÓDIGO PASO A PASO Tengamos el siguiente grafo, cuyos ID están en color negro encima de cada vértice, los pesos está en color azul y la distancia inicial en cada vértice es infinito

Algunas consideraciones para entender el código que se explicara junto con el funcionamiento del algoritmo.

#define MAX 10005

//máximo número de vértices

#define Node pair< int , int >

//definimos el nodo como un par (first , second ) donde first es el vértice adyacente y second el peso de la arista

53

#define INF 1 Q; //priority queue propia del c++, usamos el comparador definido para que el de menor valor este en el tope Int V;

//número de vértices

Y la función de inicialización será simplemente lo siguiente //función de inicialización Void init () { For (int i = 0; i vértice 1 es 0 por estar en el mismo lugar.

Q.push( Node( inicial , 0 ) );

//Insertamos el vértice inicial en la Cola de Prioridad

Distancia [inicial] = 0;

//Este paso es importante, inicializamos la distancia del inicial como 0

Extraemos el tope de la cola de prioridad While ( !Q.empty() ) {

//Mientras cola no este vacía

Actual = Q.top ().first;

//Obtengo de la cola el nodo con menor peso, en un comienzo será el inicial

Q.pop ();

//Sacamos el elemento de la cola

55

Si el tope ya fue visitado entonces no tengo necesidad de evaluarlo, por ello continuaría extrayendo elementos dela cola:

If (visitado [actual]) continúe;

//Si el vértice actual ya fue visitado entonces sigo sacando elementos de la cola

En este caso al ser el tope el inicial no está visitado por lo tanto marcamos como visitado. 1 visitado [actual] = true;

//Marco como visitado el vértice actual

Hasta este momento la tabla quedaría de la siguiente manera

Ahora vemos sus adyacentes que no hayan sido visitados. Tendríamos 2 y 4. for( int i = 0 ; i < ady[ actual ].size() ; ++i ) {

//reviso sus adyacentes del vértice actual Adyacente = ady [actual] [i].first;

//id del vértice adyacente

Peso = ady [actual] [i].second;

//peso de la arista que une actual con

(actual, adyacente) If ( !visitado[ adyacente ] ) {

//si el vértice adyacente no fue visitado

56

adyacente

Evaluamos primero para vértice 2

Vemos que la distancia actual desde el vértice inicial a 2 es ∞, verifiquemos el paso de relajación:

Distancia [1] + 7 < distancia [2]

->

0+7

7

0+2

2

2+3

5

5 + 1 < 10

->

6 < 10

En esta oportunidad hemos encontrado una ruta más corta partiendo desde el vértice inicial al vértice 3, dicha ruta sería 1 -> 4 -> 2 -> 3 cuyo peso es 6 que es mucho menor que la ruta 1 – > 4 -> 3 cuyo peso es 10, actualizamos la distancia en el vértice 3 quedando:

63

El siguiente vértice de la cola de prioridad es el vértice 3 y su único adyacente no visitado es el vértice 5.

Vemos que la distancia actual del vértice inicial al vértice 5 es 7, verifiquemos el paso de relajación: Distancia [3] + 5 < distancia [5]

->

6+5

11 < 7

En esta oportunidad se no cumple por lo que no relajamos el vértice 5, por lo que la tabla en cuanto a distancias no sufre modificaciones y no agregamos vértices a la cola:

64

Ahora tocaría el vértice 2 pero como ya fue visitado seguimos extrayendo elementos de la cola, el siguiente vértice será el 5.

Al ser el último vértice a evaluar no posee adyacentes sin visitar por lo tanto hemos terminado el algoritmo. En el grafico anterior observamos que 2 aristas no fueron usadas para la relajación, las demás si fueron usadas. La tabla final quedaría de la siguiente manera:

De la tabla si deseo saber la distancia más corta del vértice 1 al vértice 5, solo tengo que acceder al valor del arreglo en su índice respectivo (Distancia [5]). Shortest Path Tree

65

En el proceso anterior usábamos el arreglo previo[u] para almacenar el ID del vértice previo al vértice con ID = u, ello me sirve para formar el árbol de la ruta más corta y además me sirve para imprimir caminos de la ruta más corta.

Impresión del camino encontrado.

Para imprimir el camino más corto deseado usamos el arreglo previo[u], donde u tendrá el ID del vértice destino, o sea si quiero imprimir el camino más corto desde vértice 1 -> vértice 3 partiré desde previo [3] hasta el previo [1]. De manera similar a lo que se explicó en el algoritmo BFS, en este caso se realizara de manera recursiva: //Impresión del camino más cortó desde el vertice inicial y final ingresados Void print (int destino) { If ( previo [destino]!= -1) Print (previo [destino]); Printf ("%d “, destino );

//si aún poseo un vertice previo //recursivamente sigo explorando //terminada recorridos

}

66

la

recursión

imprimo

los

vértices

Veamos gráficamente el funcionamiento, desde el grafo comenzamos en 3

El previo de 3 es el vértice 2, por lo tanto ahora evaluó 2:

67

Ahora el previo de 2 es el vértice 4:

68

El previo de 4 es el vértice inicial 1

Como el previo de 1 es -1 terminamos el recorrido, ahora en el retorno de las llamadas recursivas imprimo el camino: 1 4 2 3

69

CAPITULO 6 70

ALGORITMO DIJKSTRA EN UN SIMULADOR PAKET TRECER

71

72

CAPITULO 7

CONCLUSIONES a. Algoritmo de estado del enlace Cada router tiene una base de datos que representa un mapa de toda la topología o Enlaces o Su estado (incluyendo el costo) o Todos los routers obtienen la misma información o Todos los routers calculan la mejor ruta a cada destino o Cualquier cambio de estado de un enlace se difunde a través de toda la red 73

o “Difusión global de información local”

b. OSPF permite que los sistemas de redes sean agrupados juntos. Tal agrupamiento se llama área. La topología de un área se oculta del resto del Sistema Autónomo. El este ocultar de la información permite una reducción significativa en tráfico de la encaminamiento. También, encaminando dentro del área es determinado solamente por propia topología del área, prestando la protección del área contra malos datos de la encaminamiento. Un área es una generalización de un IP segmentar la red. c. Aquí pudimos ver las ventajas del encaminamiento jerárquico, y como funcionan los LSA, así como también pudimos ver cuáles son los distintos subprotocolos, por lo cueles se componen OSPF. Los tipos de Ruteadores, lo cual nos da herramientas para poder hacer un diseño más acorde con la tecnología OSPF.

RECOMENDACIONES 

Como recomendación principal,-se presenta la no perdida de vista de que si se va a diseñar una red en OSPF, diseñarla con especial cuidado, sobre todo si no se quiere ser víctima de un retroceso, al no poder implementar esta tecnología correctamente, por diversos factores, tales como incompatibilidad de protocolos de encaminamiento anteriores, tales como RIP, IGRP, EIGRP, estos protocolos sino se vinculan bien con el nuevo diseño suelen hacer serias, tales como se vieron en el capítulos , donde se pudo observar las serias implicaciones que causaban ios bucles de encaminamiento, y esto en una red que se supone debe ser altamente confiable es muy peligroso.



Buscar siempre al diseñar proteger las áreas de alto riesgo de conectividad, así también tratar de controlar todos los aspectos tales como: la corriente eléctrica, el ambiente de trabajo, y la energía ininterrumpida. Muchas veces los enlaces son altamente confiables, lo que hace las rutas indisponibles son los incontrolables apagones sobre todo en México donde el diseño eléctrico no muchas veces es el indicado.

74



También se recomienda la revisión cuidadosa de la compatibilidad del hardware, pues muchas veces el hardware, como ya se mencionó viene dañado, o ¿por qué no?, se utilizan otras marcas de equipos que muchas veces llegarían a ser incompatibles pues manejan protocolos propietarios de encaminamiento, haciendo más difícil así la redistribución de rutas.

BIBLIOGRAFÍAS 

https://www.mikroways.net/2009/07/20/introduccion-a-ospf/



https://www.cisco.com/c/es_mx/support/docs/availability/high-availability/15408ospf-snmp-config.pdf



http://neo.lcc.uma.es/evirtual/cdd/tutorial/red/protocols.html



https://nsrc.org/workshops/2011/walc/routing/rawattachment/wiki/Agenda/Intro_OSPF.pdf



http://eprints.uanl.mx/5385/1/1020149266.PDF



http://sedici.unlp.edu.ar/handle/10915/2165

75