Bellman-Ford es uno de los protocolos más fáciles de entender, ya que generalmente se implementa comparando la información recién obtenida sobre un destino con la información existente sobre el mismo destino. Si la ruta recién descubierta es mejor que la ruta actualmente conocida, la ruta de mayor costo simplemente se reemplaza en la lista de rutas, de acuerdo con la regla del camino más corto para encontrar rutas sin bucles en la red.

Por lo tanto, al iterar a través de toda la topología, se puede encontrar un conjunto de rutas más cortas a cada destino. La Figura se utiliza para ilustrar este proceso.

Nota: Aunque Bellman-Ford es principalmente conocido por su variante distribuida, implementada en protocolos ampliamente utilizados como el Protocolo de información de enrutamiento (RIP), fue diseñado originalmente como un algoritmo de búsqueda ejecutado en una sola estructura que describe la topología de nodos y bordes. Aquí, Bellman-Ford se considera como un algoritmo.

El Algoritmo Bellman-Ford

Bellman-Ford calcula el árbol de camino más corto (Shortest Path Tree – SPT) a cada destino alcanzable en el peor de los casos O(V * E), donde V es el número de nodos (vértices) en la red y E es el número de canales (bordes). Esencialmente, esto significa que el tiempo que tarda Bellman-Ford en funcionar con la topología y calcular el SPT depende linealmente de la cantidad de dispositivos y canales. Duplicar la cantidad de cualquiera de ellos duplicará el tiempo necesario para la ejecución. Duplicar ambos al mismo tiempo aumentará el tiempo de ejecución 4 veces.

Por lo tanto, el algoritmo Bellman-Ford es moderadamente lento cuando se utiliza contra topologías más grandes, donde los nodos en la tabla de topología comienzan en orden desde el más alejado de la raíz hasta el más cercano a la raíz. Si la tabla de topología está ordenada del más cercano a la raíz al más alejado, Bellman-Ford puede completarse en O(E), lo cual es mucho más rápido. En el mundo real, es difícil asegurar cualquier orden, por lo que el tiempo real necesario para construir el SPT generalmente se encuentra entre O(V * E) y O(E).

Bellman-Ford es un algoritmo voraz (greedy) que asume que cada nodo en la red, excepto el local, solo es accesible a costos infinitos, y reemplaza estos costos infinitos con los costos reales a medida que atraviesa la topología. La suposición de que todos los nodos están infinitamente lejos se llama relajación del cálculo, ya que utiliza una distancia aproximada para todos los destinos desconocidos en la red, reemplazándolos con el costo real una vez que se calcula.

El tiempo de ejecución real de cualquier algoritmo utilizado para calcular el SPT generalmente está limitado por la cantidad de tiempo requerido para transmitir información sobre los cambios de topología a través de la red. Las implementaciones de todos estos protocolos, especialmente en su forma distribuida, contendrán una serie de optimizaciones para reducir su tiempo de ejecución a un nivel mucho menor que el peor de los casos, por lo que, aunque el peor de los casos se da como punto de referencia, a menudo tiene poca influencia en el rendimiento de cada algoritmo en redes implementadas reales.

Ejecución y Pseudocódigo

Para ejecutar el algoritmo Bellman-Ford en esta topología, primero debe convertirse en un conjunto de vectores y distancias y almacenarse en una estructura de datos como la que se muestra en la Tabla 1.

En esta tabla hay nueve entradas porque hay nueve enlaces (bordes) en la red. Los algoritmos de ruta más corta calculan un árbol unidireccional (en una dirección a lo largo del gráfico). En la red de la Figura, se muestra que el SPT se origina en el nodo 1, y el cálculo se muestra lejos del nodo 1, que será el punto desde el cual se realizarán los cálculos. El algoritmo en pseudocódigo es el siguiente:

// Creamos un conjunto para almacenar la respuesta, una entrada por cada nodo.
// El primer espacio en la estructura resultante representará el nodo 1,
// el segundo el nodo 2, etc.
define route[nodes] {
  predecessor // como un nodo
  cost // como un entero
}
// Establecemos el origen (yo) a 0
// La posición 1 en el array es la entrada del punto de origen.
route[1].predecessor = NULL
route[1].cost = 0
// La Tabla 1, mostrada arriba, está contenida en un array llamado topo
// Iteramos a través de la tabla de vértices (aristas) una vez por cada entrada en la ruta
// (resultados) tabla, reemplazando las entradas más largas por las más cortas.
i = nodes
while i > 0 {
  j = 1
  while j <= nodes { // Itera sobre cada fila en la tabla de topología
    source_router = topo[j].s
    destination_router = topo[j].d
    link_cost = topo[j].cost
    if route[source_router].cost == NULL {
      source_router_cost = INFINITY
    } else {
      source_router_cost = route[source_router].cost
    }
    if route[destination_router].cost == NULL {
      destination_router_cost = INFINITY
    } else {
      destination_router_cost = route[destination_router].cost
    }
    if source_router_cost + link_cost <= destination_router_cost {
      route[destination_router].cost = source_router_cost + link_cost
      route[destination_router].predecessor = source_router
    }
    j = j + 1 // o j++ dependiendo del pseudocódigo que se esté representando
  }
  i = i - 1
}

Este código parece engañosamente más complejo de lo que realmente es. La línea clave es la comparación if route[topo[j].s].cost + topo[j].cost <= route[topo[j].d].cost. Es útil centrarse en esta línea en el ejemplo. En la primera pasada del bucle externo (que se ejecuta una vez para cada entrada en la tabla de resultados, aquí llamada route):

Para la primera fila de la tabla topo:

• j es igual a 1, por lo que topo[j].s es el nodo 6 (F), el origen del vector en la tabla de bordes.
• j es igual a 1, por lo que topo[j].d es el nodo 7 (G), el destino del vector en la tabla de bordes.
• route[6].cost = infinity, topo[1].cost = 1, y route[7].cost = infinity (donde infinity representa infinito).
• infinity + 1 == infinity, por lo que la condición no se cumple y no ocurre nada más.”

Cualquier entrada en la tabla topo con un costo de origen de infinito dará el mismo resultado, ya que infinito + cualquier cosa siempre será igual a infinito. El resto de las filas que contienen un origen con un costo de infinito se omitirán.

Para la octava fila de la tabla topo (el octavo borde):

• j es igual a 8, por lo que topo[j].s es el nodo 1 (A), el origen del vector en la tabla de bordes.
• j es igual a 8, por lo que topo[j].d es el nodo 2 (B), el destino del vector en la tabla de bordes.
• route[1].cost = 0, topo[8].cost = 2 y route[2].cost = infinity.
• 0 + 2 <= infinity, por lo que la condición se cumple.
• route[2].predecessor se establece en 1, y route[2].cost se establece en 2.

Para la novena fila de la tabla topo (el noveno borde):

• j es igual a 9, por lo que topo[j].s es el nodo 1 (A), el origen del vector en la tabla de bordes.
• j es igual a 9, por lo que topo[j].d es el nodo 3 (C), el destino del vector en la tabla de bordes.
• route[1].cost = 0, topo[9].cost = 1 y route[3].cost = infinity.
• 0 + 1 <= infinity, por lo que la condición se cumple.
• route[3].predecessor se establece en 1, y route[3].cost se establece en 1.

En la segunda pasada del bucle externo:

Para la quinta fila de la tabla topo (el quinto borde):

• j es igual a 5, por lo que topo[j].s es el nodo 2 (B), el origen del vector en la tabla de bordes.
• j es igual a 5, por lo que topo[j].d es el nodo 6 (F), el destino del vector en la tabla de bordes.
• route[2].cost = 2, topo[5].cost = 1 y  route[6].cost = infinity.
• 2 + 1 <= infinity, por lo que la condición se cumple.
• route[6].predecessor se establece en 2, y route[6].cost se establece en 3.

Ver también

Blog CCNA

SIP vs. PRI: Comparación y Ventajas

Para la sexta fila de la tabla topo (el sexto borde):

• j es igual a 5, por lo que topo[j].s es el nodo 2 (B), el origen del vector en la tabla de bordes.
• j es igual a 5, por lo que topo[j].d es el nodo 6 (F), el destino del vector en la tabla de bordes.
• route[2].cost = 2, topo[5].cost = 1 y  route[6].cost = infinity.
• 2 + 1 <= infinity, por lo que la condición se cumple.
• route[6].predecessor se establece en 2, y route[6].cost se establece en 3.

El final de esta pasada se muestra en la Tabla 2.

En la tercera pasada del bucle externo, el nodo 8 es de particular interés, ya que hay dos rutas a este destino. Para la segunda fila de la tabla topo (el segundo borde):

• j es igual a 2, por lo que topo[j].s es el nodo 5 (E), el origen del vector en la tabla de bordes
• j es igual a 2, por lo que topo[j].d es el nodo 8 (H), el destino del vector en la tabla de bordes
• route[5].cost = 4, topo[2].cost = 1 y route[8].cost = infinity.
• 4 + 1 <= infinity, por lo que la condición se cumple
• route[8].predecessor se establece en 5, y route[8].cost se establece en 5

Para la tercera fila de la tabla topo (el tercer borde):

• j es igual a 3, por lo que topo[j].s es el nodo 4 (D), el origen del vector en la tabla de bordes.
• j es igual a 3, por lo que topo[j].d es el nodo 8 (H), el destino del vector en la tabla de bordes.
• route[4].cost = 2, topo[3].cost = 2 y route[8].cost = 5.
• 2 + 2 <= 5, por lo que la condición se cumple.
• route[8].predecessor se establece en 4, y route[8].cost se establece en 4.

El punto interesante en el tercer ciclo en la tabla topo es que la entrada para el borde [5,8] se procesa primero, lo que establece el remitente 8 (H) en 5 y el costo en 5. Sin embargo, cuando se procesa la siguiente fila en la tabla topo [4,8], el algoritmo descubre una ruta más corta al nodo 8 y reemplaza la existente. La Tabla 2 muestra el estado de la tabla de rutas en cada pasada a través de la tabla topo.

En la Tabla 2, la fila superior representa la entrada en la tabla de enrutamiento y el nodo al que se puede acceder en la red. Por ejemplo, A(1) representa la mejor ruta a A, B(2) representa la mejor ruta a B, etc. La columna P representa el predecesor, o el nodo a través del cual A debe pasar para llegar al destino especificado. C representa el costo para llegar a ese destino. El ejemplo de red considerado puede completarse en tres ciclos si el algoritmo está configurado para detectar la finalización del árbol. El pseudocódigo, como se muestra, no tiene ninguna prueba para esta finalización y, en cualquier caso, realizará los 8 ciclos completos (uno para cada nodo).

Palabras Finales

El algoritmo Bellman-Ford ofrece una forma robusta y comprensible de calcular las rutas más cortas en una red, incluso con la presencia de pesos negativos en las aristas (siempre que no existan bucles negativos). Si bien su eficiencia puede ser menor en comparación con otros algoritmos para grafos sin pesos negativos, su capacidad para detectar bucles negativos lo convierte en una herramienta valiosa en ciertas situaciones.