Algoritmos de Vector Distancia
Dentro de los algoritmos de Vector Distancia el más conocido es el algoritmo de Bellman-Ford. Este algoritmo se basa en que cada encaminador tiene una tabla de reenvío que nos indica la siguiente información:
la línea por la que tiene tiene que salir para ir a un destino determinado y
el coste asociado a la mejor ruta conocida.
La actualización de la tabla se lleva a cabo solo a través de la información que le aportan sus vecinos inmediatos. Inicialmente la única información que tiene cada encaminador es el coste a sus vecinos. A partir de esta información, y de la que le van enviando sus inmediatos vecinos se calcula la mejor ruta. Es decir, los pasos que sigue este algoritmo son:
Cada nodo calcula el coste entre él y todos sus vecinos.
Almacena esta información en una tabla.
Cada nodo comunica su tabla a todos sus vecinos.
A partir de esta nueva información, cada nodo recalcula su tabla.
Figura 42: Ejemplo de grafo de una red de comunicaciones
Esto se hace continuamente hasta que el algoritmo se para.
Figura 43: Aplicación del algoritmo de Bellman-Ford: paso 1
Veamos un ejemplo de cómo funciona este algoritmo partiendo de la red de la figura 42, donde cada enlace tiene un coste asociado.
Podemos crear las tablas para cada encaminador solo con la información de los costes que tienen todas sus líneas (figura 43). A partir de la información que tiene cada encaminador de sus líneas, podemos crear las tablas representadas en figura. Cada tabla tiene la información que en ese momento dispone cada encaminador del coste que supone llegar a cada uno de los enrutadores de la red. Por ejemplo, el encaminador origen (N1) sabe que para llegar a N2 tiene un coste de 1 y para llegar a N3 tiene un coste de 2. Para el resto de los nodos (N4 y N5) los costes son ∞, ya que no dispone de información. En este caso, para llegar a N2, se iría con el enlace que va directamente a N2 (esto no tiene que ser siempre así) y para llegar a N3, también, iría por el enlace que va directamente a N3. Lo mismo se puede aplicar al resto de los enrutadores.
Figura 44: Aplicación del algoritmo de Bellman-Ford: paso 2
En el siguiente paso, cada encaminador comunica a sus vecinos inmediatos la información de cada una de su tabla de reenvío. Con esa información, cada encaminador actualiza su tabla. Así, en el caso de N1, recibe las tablas de N2 y N3. La tabla de N2 le informa a N1 el coste que le supone llegar al resto de los enrutadores (excepto a N5 que todavía no tiene información suficiente). Y la tabla de N3 le informa de lo mismo. La tabla de N2 le indica que para llegar a N4 le cuesta 2, que junto con lo que le cuesta a N1 llegar a N2, el coste total es de 1 + 2 (= 4). La tabla de N3 indica que para llegar a N4 le cuesta 2, con lo que a N1 yendo por N3 le cuesta 2 + 2 (=4). Como la ruta a través de N2 es inferior a la otra, la tabla se actualiza tal como se refleja en la figura 44. Y lo mismo para el resto de las tablas.
En el siguiente paso (figura 45), se realiza el mismo proceso. Así, en N1 con la información que le da N2 y N3, conoce el coste que le supone llegar a N5, ya que el paso anterior, tanto N2 como N3 obtuvieron el coste que le supondría a ellos llegar a N5.
Figura 45: Aplicación del algoritmo de Bellman-Ford: paso 3
Este algoritmo se para cuando las tablas no se modifican con la información que les envía a cada encaminador sus vecinos.
Vemos que este al algoritmo es iterativo, asíncrono y distribuido. Es asíncrono por que no es necesario que todos los enrutadores estén sincronizados entre sí. Es distribuido porque cada encaminador solo maneja información suya y la de sus vecinos.
Formalización
Para formalizar este algoritmo aplicaremos lo siguiente:
Cada nodo x dispone de la siguiente información:
El coste c(x,v) desde x hasta al vecino v
Un vector de distancias de x al resto de los nodos: Dx(y)
Un vector de distancias del vecino v al resto de los nodos: Dv(y)
Como vimos, cada cierto tiempo cada nodo envía esta información de su vector distancia a sus vecinos. Y cuando el nodo x los recibe aplica la ecuación de Bellman-Ford para actualizar su propia tabla de vectores:
Dx y=minv {c x , vDv y}
- Si se modifica el vector de distancias de x o si cambian los costes de los enlaces hacia los vecinos entonces envía la nueva tabla a los vecinos.
*