Actividad No 7 - Caminos Minimos

Vista previa del material en texto

UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORÍA DE GRAFOS Semestre: IX Actividad No. 7 
Profesor: Jose Waldo de la Ossa Temática: Búsqueda de caminos mínimos en grafos 
 
1 | T e o r í a d e G r a f o s V e r . 5 . 2 0 
 
Consideraciones Generales 
La fecha de presentación es el 31-05-2023 a las 6:00 PM, en grupo (3 personas). 
Recuerde que debe imprimir la actividad, desarrollarla a mano (bien presentado) y 
entregarlo al inicio de la clase. Pero, antes de entregar, un integrante del grupo debe 
escanear todo el documento y subirlo a la plataforma. 
 
 
Introducció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.1 
En el encaminamiento estado de enlace, se pueden establecer cinco elementos diferenciados 
 
1. Descubrimiento de vecinos: uso de paquetes HELLO 
2. Estimación del coste con los vecinos. Por ejemplo, en base al retardo con cada uno de 
ellos: paquetes ECHO 
3. Construcción de un paquete con la información correspondiente 
4. Envío del paquete al resto de nodos (routers). Difusión [broadcast] de información: 
inundación 
5. Cálculo de la ruta. Uso del algoritmo de Dijkstra – necesidad de disponer de información 
global. 
 
 
Problema 1 (Valor 3 puntos) 
a) Calcule teóricamente, en base al algoritmo de Dijkstra, una ruta óptima para el 
envío de un paquete desde R2 hacia el routers R10 en la siguiente topología (Figura 
1). El número entre paréntesis representa el costo del mismo. 
 
1 http://www.ibm.com/support/knowledgecenter/es/ssw_ibm_i_71/rzajw/rzajwospf.htm 
 
UNIVERSIDAD DE CÓRDOBA 
FACULTAD DE INGENIERÍAS 
Programa de Ingeniería de Sistemas 
Asignatura: TEORÍA DE GRAFOS Semestre: IX Actividad No. 7 
Profesor: Jose Waldo de la Ossa Temática: Búsqueda de caminos mínimos en grafos 
 
2 | T e o r í a d e G r a f o s V e r . 5 . 2 0 
 
b) Elabore la tabla de análisis de resultados, indique el o los caminos mínimos y la 
distancia. 
 
 
Figura 1 
 
Problema 2 (valor 2 puntos) 
Tras varios años de explotación, la configuración de la red de comunicaciones de una 
compañía es la que se muestra en la figura 2, donde los costos por enlace se han estimado 
en función de diferentes parámetros: distancia, amortización de la inversión necesaria, etc. 
El nodo central S envía información al resto, según la topología de red. 
 
a) Utilizar el algoritmo de Dijkstra para 
encontrar las rutas más cortas entre S 
y el resto de nodos de la red. 
 
b) Con base en el resultado obtenido en 
el literal anterior, cuál es el número 
medio de enlaces que un paquete 
tiene que atravesar (en promedio)? 
 
Figura 2