Algoritmos de Estado de Enlaces
Dentro de los algoritmos de Estado de Enlaces el más conocido es el algoritmo de Dijskra. Para describir este algoritmo partiremos del grafo de la figura 35. En esta figura, hemos marcado el nodo origen A. A partir de este, etiquetaremos cada nodo con su distancia a él a través de la mejor ruta que conocemos. Como inicialmente no se conocen las mejores rutas, todas la etiquetamos a infinito y a medida que va avanzando el algoritmo se van actualizando las etiquetas mostrando las mejores rutas.
Figura 35: Ejemplo de un grafo
Inicialmente todas las etiquetas son provisionales, aunque cuando una ruta se descubre que es la óptima, entonces se etiqueta como definitiva.
En definitiva, la idea principal de este algoritmo consiste en explorar las rutas mejores que salen del nodo origen y que van llegando al resto de los nodos. En el momento que se llega a la ruta mejor el algoritmo se detiene.
Figura 36: Aplicación del algoritmo de Dijsktra: paso 1
Veamos cómo funciona este algoritmo con un ejemplo.
La figura 35 representa el grafo de una red de enrutadores, donde los pesos que tiene cada enlace es el costo de la línea (que recordamos puede ser el salto, la distancia, el retardo, etc). Se pretende encontrar la ruta óptima entre A y el resto de los enrutadores.
En la figura 36 se ha etiquetado cada nodo siguiendo el criterio de poner entre paréntesis con su distancia al nodo origen a través de la mejor ruta conocida. Así, B(2, A) indica que la distancia al nodo origen (A) es 2 y se llega por A. Y C(1, A) indica que la distancia al nodo origen es 1 y se llega a través A. Como la ruta mejor (la que tiene el valor mas bajo) es la de C, marcamos al nodo C como definitivo (lo sombreamos). Y ahora en el siguiente paso es el nodo el que se considera como el nuevo nodo de trabajo.
Figura 37: Aplicación del algoritmo de Dijsktra: paso 2
Partiendo del nodo C, nos fijamos en sus nodos vecinos. Sumamos la etiqueta de C y el coste desde C al nodo vecino. Si esta suma es menor que la etiqueta actual entonces actualizamos la etiqueta. Así, en la figura 37 tenemos al nodo D y G como vecinos no marcados. C está etiquetado con 1 y el costo de este al nodo D es de 4, por tanto, D lo etiquetamos con D(min{(∞, 1+4)=5},C), ya que antes D estaba etiquetado con (∞, -). El costo de C a G es 3, por tanto, G lo etiquetamos con G(1+3, C). Como, en este caso B, es el que tiene la etiqueta con menor costo, lo marcamos.
Figura 38: Aplicación del algoritmo de Dijsktra: paso 3
Hacemos lo mismo, pero partiendo del nodo B, que solo tiene el vecino D (figura 38). Si sumamos la etiqueta de B y el coste desde B a D, tenemos 4, que es menor que la etiqueta actual de D (que es 5). Por tanto, cogemos min(4,5) como nuevo coste etiquetado de D, es decir, D(4, B). Como D y G pesan los mismo, podemos marcar cualquiera de los dos, por ejemplo, marcamos G.
Ahora partimos del nodo G (figura 39). Los vecinos no marcados son D y H. D se etiquetaría como el mínimo de (4, B) y (4+2, C), es decir, nos quedaríamos con D(4, B). Y el nodo H lo etiquetaríamos con H(4+5, G). Al tener el nodo D la etiqueta con menor peso, lo marcamos.
Figura 39: Aplicación del algoritmo de Dijsktra: paso 4
En el siguiente paso (figura 40), D solo tiene un vecino no marcado, F, que lo etiquetaríamos con F(4+2, D). Marcaríamos ahora a F por pesar menos que G.
Figura 40: Aplicación del algoritmo de Dijsktra: paso 5
Por último, tal como vemos en la figura 41, H estaría etiquetado con H(6+1, F).
Figura 41: Aplicación del algoritmo de Dijsktra: paso 6
Para ver cuál sería la ruta óptima, por ejemplo, de A hasta H, empezaríamos con H, luego F (ya que la etiqueta de H indica F), le seguiría D, B y A.
Vemos que este al algoritmo es iterativo y distribuido. Es centralizado porque cada encaminador o un ente externo maneja información de toda la red.
En sí mismo, este algoritmos puede trabajar de forma asíncrona, aunque esto puede dar problemas a si cada encaminador calcula la ruta en instantes distintos, ya que pueden partir de información diferente. Por ello, estos algoritmos se aconsejan que sen síncronos, es decir, que todos los enrutadores estén sincronizados entre sí.
Formalización del algoritmo
El el algoritmo de Dijkstra, como dijimos es iterativo, y en la k-ésima iteración se calculan las rutas mejores hacia k nodos de destino. El número de veces que se ejecuta es el número de nodos de la red.
Para formalizar este algoritmo se aplica lo siguiente:
Se define:
El coste c(x,v) desde x hasta al nodo v
D(v) como la ruta mejor desde el nodo origen al nodo v
p(v) representa al nodo justo anterior a v, que está dentro de la ruta mejor
N' es el subconjunto de nodos que pertenece a la ruta mejor y que se conocen de forma definitiva
En cada iteración la ruta mejor se actualiza a través de la fórmula:
Dv=min {D(v), c w, vD w}
donde w no pertenece a N' de tal forma que D(w) es el mínimo.
*