104/12/23

Algoritmo de DijkstraAlgoritmo de Dijkstra

Jose Carlos Gonzalez

Fernando Jose Castillo

204/12/23

HistoriaHistoriaEdsger Wybe Dijkstra nació en Rotterdam, (Holanda) en 1930. Sus padres eran ambos intelectuales y él recibió una excelente educación. En 1942, cuando Dijkstra tenía 12 años, entró en Gymnasium Erasminium, una escuela para estudiantes especialmente brillantes.

304/12/23

HistoriaHistoriaEn 1956, Dijkstra anunció su algoritmo, algoritmo de caminos mínimos. En términos generales, encuentran la ruta más corta entre dos nodos, inicial a y final z

404/12/23

ConceptoConcepto

Es un algoritmo alternativo para determinar los caminos mas cortos desde un nodo origen hasta todos los otros nodos en la red. Este algoritmo es mas eficiente que el de Bellman-Ford.

Se requiere que todos los costos de enlace sean positivos

504/12/23

ConceptoConcepto

Se puede hacer un uso de varias metricas para determinar el “costo” de los enlaces entre los nodos, algunos ejemplos son:

Costo/Capacidad

El costo es inversamente proporcional a la capacidad del enlace, costos mayores a los enlaces de menor capacidad.

604/12/23

ConceptoConcepto

Costo retardo de paquete

El costo es proporcional al retardo medio de paquete, el cual incluye el retardo de la cola en memoria temporal y el retardo de propagacion en el enlace.

Costo congestio

el costo es proporcional a alguna medida de congestion, por ejemplo: Carga de trafico.

704/12/23

Entendemos por mejor ruta•Presenta el menor retardo medio de tránsito. •Consigue mantener acotado el retardo entre pares de nodos de la red. •Consigue ofrecer altas cadencias efectivas independientemente del retardo medio de tránsito •Permite ofrecer el menor costo.

La idea principal…La idea principal…

Es identificar los nodos mas cercanos desde el nodo origen, en orden creciente del costo del camino.

804/12/23

Ejemplos de la vida realEjemplos de la vida real

904/12/23

Ejemplo de Telecomunicaciones

Ejemplo de Telecomunicaciones

1004/12/23

Protocolo OSPFProtocolo OSPF

Opera como protocolo de estado de enlace, e implementa un algoritmo para calcular la ruta más corta a cada red de destino, basándose en el ancho de banda. OSPF es un protocolo apto para todas las redes de todo tipo y tamaño.

El protocolo OSPF (Open Shortest Path First) es un protocolo estándar de enrutamiento interno basado en el estado del enlace o algoritmo Short Path First.

1104/12/23

Mensaje del OSPFMensaje del OSPF

HELLO o Saludo

•Identificar a los vecinos, para crear una base de datos en mapa local.•Enviar señales de <estoy vivo>, al resto de routers para mantener el mapa local .•Elegir un router designado para una red multienvío•Encontrar al router designado existente.•Enviar señales de <estoy vivo>

1204/12/23

Mapa de Red LocalMapa de Red LocalSe hace a través de la tabla

•Fila: Representa a un router de la red; y cualquier cambio que le ocurra a ese router será reflejado en este registro de la tabla a través de los registros de descripción.

•Columna: Representa los atributos de un router que son almacenados para cada nodo. Entre los principales atributos por nodo tenemos: un identificador de interfase, el número de enlace e información acerca del estado del enlace, o sea, el destino y la distancia o métrica.

1304/12/23

Mapa de Red LocalMapa de Red Local

A --- 1 --- B --- 2 --- C --- 4 --- D --- 3 --- A

DE A ENLACE DISTANCIA

A B 1 1B C 2 1C D 4 1D A 3 1B A 1 1C B 2 1D C 4 1A D 3 1

1404/12/23

Ejemplo ocupando el OSPFEjemplo ocupando el OSPF

1504/12/23

Pasos para etiquetar nodosPasos para etiquetar nodos

[ d, j ]  dónde j representa el nodo precedente, d representa distancia y el numero de

integracion que se utiliza

Considere todos los nodos que estén conectados con el origen por un arco, es decir a través de un camino de longitud 1. A cada uno de ellos se le colocará una etiqueta que tiene tres componentes a saber:

1604/12/23

Pasos para etiquetar nodosPasos para etiquetar nodos

Paso 2De todos los nodos con etiqueta temporal, se elige uno cuyo componente de distancia sea mínimo y se lo etiqueta permanente. Los empates se rompen arbitrariamente. Cuando todos los nodos son permanentes se pasa al Paso 4.

1704/12/23

Pasos para etiquetar nodosPasos para etiquetar nodos

Paso 3Todo nodo que no tenga actualmente etiqueta permanente, estará sin etiqueta o con una temporal. Si i es el último etiquetado permanente considere todos los vértices que estén conectados directamente con éste a través de un camino de longitud 1. Para cada uno de ellos calcular la suma de su distancia a i  más la distancia de la etiqueta de i . Si el nodo no está etiquetado darle una etiqueta temporal. Si el nodo en cuestión ya tiene etiqueta temporal, cambiarla sólo si la distancia recién calculada es menor que la componente de distancia de la etiqueta actual. Si la distancia recién calculada es igual a la que tiene la etiqueta anterior, conservar ambas. Regresar al Paso 2.

1804/12/23

Pasos para etiquetar nodosPasos para etiquetar nodos

Paso 4Las etiquetas permanentes indican la distancia más corta desde el origen a cada nodo de la red. También indican el nodo predecesor en la ruta más corta hacia cada nodo

1904/12/23

Ejemplo PracticoEjemplo Practico

Paso 1: Identificar el nodo Origen y destino.

Nodo Origen es 1, Nodo destino es 5.

2004/12/23

Pasos para la solucionPasos para la solucion

Paso 2: Busca la ruta mas corta, de las tres conexiones disponibles. Primero revisa la ruta por el nodo 2.

2104/12/23

Pasos para la solucionPasos para la solucion

Paso 3: Conoce el costo del camino por la via del nodo 2.

2204/12/23

Pasos para la solucionPasos para la solucion

Paso 4: Busca la alternativa por el nodo 3.

2304/12/23

Pasos para la solucionPasos para la solucion

Paso 5: Conoce el costo del camino por la via del nodo 3.

2404/12/23

Pasos para la solucionPasos para la solucion

Paso 6: Busca la alternativa por el nodo 6.

2504/12/23

Pasos para la solucionPasos para la solucion

Paso 7: Conoce el costo del camino por la via del nodo 6.

2604/12/23

Pasos para la solucionPasos para la solucion

Paso 8: Identifica que la ruta mas corta sera por el nodo 2.

2704/12/23

Pasos para la solucionPasos para la solucion

Paso 9: Busca el costo de la ruta hacia el nodo 3.

2804/12/23

Pasos para la solucionPasos para la solucion

Paso 10: Conoce el costo de la ruta hacia el nodo 3, viajando por el nodo 2 y hace la comparacion.

2904/12/23

Pasos para la solucionPasos para la solucion

Paso 11: Encuentra que la ruta por el nodo 2 y 3 es mas larga.

3004/12/23

Pasos para la solucionPasos para la solucion

Paso 12: Busca la alternativa por el nodo 4.

3104/12/23

Pasos para la solucionPasos para la solucion

Paso 13: Conoce el costo del camino hacia el nodo 4.

3204/12/23

Pasos para la solucionPasos para la solucion

Paso 14: El nodo dos ya conoce los siguientes pasos y no tiene incognitas del costo de las rutas.

3304/12/23

Pasos para la solucionPasos para la solucion

Paso 15: Nos posicionamos en el nodo 3.

3404/12/23

Pasos para la solucionPasos para la solucion

Paso 16: Busca el costo hacia el nodo 4.

3504/12/23

Pasos para la solucionPasos para la solucion

Paso 17: Compara el costo anterior con el nuevo costo.

3604/12/23

Pasos para la solucionPasos para la solucion

Paso 18: Se queda con la ruta de menor costo.

3704/12/23

Pasos para la solucionPasos para la solucion

Paso 19: Posicionado en el nodo 3, revisa la ruta por el nodo 6.

3804/12/23

Pasos para la solucionPasos para la solucion

Paso 20: Realiza la comparacion del costo inicial de 14 con el nuevo costo encontrado 11.

3904/12/23

Pasos para la solucionPasos para la solucion

Paso 21: Determina que la ruta 3 y 6 es la mas corta.

4004/12/23

Pasos para la solucionPasos para la solucion

Paso 22: Remarca que ya conoce todos los valores desde el nodo 3.

4104/12/23

Pasos para la solucionPasos para la solucion

Paso 23: Nos posicionamos en el nodo 6.

4204/12/23

Pasos para la solucionPasos para la solucion

Paso 24: Buscamos el valor hacia el nodo 5.

4304/12/23

Pasos para la solucionPasos para la solucion

Paso 25: Encontramos que la ruta hacia el nodo 5 es 20.

4404/12/23

Pasos para la solucionPasos para la solucion

Paso 26: Definimos que es la ruta mas corta.

4504/12/23

Pasos para la solucionPasos para la solucion

Paso 27: Finalizamos el proceso.

4604/12/23

Solucion animadaSolucion animada

4704/12/23

Ejemplo 2Ejemplo 2

4804/12/23

Ejemplo 3Ejemplo 3

4904/12/23

Ejemplo 3Ejemplo 3

5004/12/23

Ejemplo 3Ejemplo 3

5104/12/23

Ejemplo 3Ejemplo 3

5204/12/23

Ejemplo 3Ejemplo 3

5304/12/23

Ejemplo 3Ejemplo 3

5404/12/23

Ejemplo 3Ejemplo 3

5504/12/23

Ejemplo 3Ejemplo 3

5604/12/23

Ejemplo 3Ejemplo 3

5704/12/23

Preguntas o comentariosPreguntas o comentarios

¿?