2. Algoritmos y Métricas de enrutaiento.

2.1. Algoritmos (informativo)

Algorítmo Dijkstra.

El algoritmo de Dijkstra es un algoritmo eficiente que sirve para encontrar el camino de coste mínimo desde un nodo origen a todos los demás nodos del grafo. Fue diseñado por el holandés Edsger Wybe Dijkstra en 1959. Se lo conoce también como algoritmo de caminos mínimos, (SPF (Shortest Path First) Ruta mas Corta Primero) es un algoritmo para la determinación del camino mas corto.
Se puede enunciar como sigue: encontrar las rutas más cortas entre un nodo origen dado y todos los demás nodos, desarrollando los caminos en orden creciente de longitud.
El la figura los vínculos entre los Nodos (1,2,3...5) tienen un Costo indicado por un nro. Este costo puede representar:
  • Retardo.
  • Ancho de banda.
  • Costo por Mbps.
  • Entre otros.
Este modelo se ingresa al Algoritmo de Dijkstra el cual resuelve encontrando el menor "costo" donde recalcamos, el costo indicado en los vínculos puede representar no solo el costo económico. El proceso concluiría obteniendo la siguiente solución:

Bellman-Ford

El algoritmo de Bellman-Ford se puede enunciar así: encontrar los caminos más cortos desde un nodo origen dado con la condición de que éstos contengan a lo sumo un enlace; a continuación encontrar los caminos más cortos con la condición de que contengan dos enlaces como máximo, y así sucesivamente. Este algoritmo presenta mayor overhead que el anterior.
El algoritmo de Dijkstra resuelve un mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo.
Un peso negativo mas allá de ser un tema matemático podría ser como una penalización, en Inteligencia Artificial hay conceptos parecidos.
NOTA:
Mayores detalles sobre estos algoritmos escapan a nuestra materia.