Algoritmo de Bellman-Ford
El Vector de distancias es un método de enrutamiento. Se trata de uno de los más importantes junto con el de estado de enlace. Utiliza el algoritmo de Bellman-Ford para calcular las rutas. Fue el algoritmo original de ARPANET. Se usó en DECNET, IPX y Appletalk. Lo usa el protocolo RIP (Routing Information Protocol), que hasta 1988 era el único utilizado en Internet. También se utiliza en los protocolos propietarios ampliamente extendidos IGRP y EIGRP de Cisco.El enrutamiento de un protocolo basado en vector de distancias requiere que un router informe a sus vecinos de los cambios en la topología periódicamente y en algunos casos cuando se detecta un cambio en la topología de la red. Comparado a los protocolos de estado de enlace, que necesitan que un router informe a todos los nodos de una red acerca de los cambios en su topología, los algoritmos de vector de distancias tienen mucha menos complejidad computacional.
El algoritmo es distribuido porque envuelve una serie de nodos (routers) dentro de un Sistema autónomo(AS), un conjunto de redes y dispositivos router IP administrados típicamente por un Proveedor de Servicio de Internet (ISP). Se compone de los siguientes pasos:
- Cada nodo calcula la distancia entre él mismo y todos los demás dentro de un AS y almacena esta información en una tabla.
- Cada nodo envía su tabla a todos los nodos vecinos.
- Cuando un nodo recibe las tablas de distancias de sus vecinos, éste calcula la ruta más corta a los demás nodos y actualiza su tabla para reflejar los cambios.
- No escala bien
- Los cambios en la topología de red no se reflejan rápidamente ya que las actualizaciones se distribuyen nodo por nodo.
- Contando hasta el infinito(si un fallo de enlace o nodo hace que un nodo sea inalcanzable desde un conjunto de otros nodos, éstos pueden estar siempre aumentando gradualmente sus cálculos de distancia a él, y mientras tanto puede haber bucles de enrutamiento).
Algoritmo de actualización difusa-DUAL
EIGRP utiliza DUAL para seleccionar y mantener la mejor ruta hacia cada red remota. Este algoritmo permite:
Determinar una ruta de respaldo si hay una disponible.
Soportar máscaras de subred de longitud variable (VLSM).
Recuperar rutas dinámicamente.
Enviar consultas por una ruta alterna si no puede encontrarse ninguna ruta. DUAL provee a EIGRP con el tiempo de convergencia más rápido.
La clave de una rápida convergencia está soportada en dos funciones: primero, los routers mantienen una copia de todas las rutas de los vecinos, las cuales utilizan para calcular su propio costo a cada red remota. Si la mejor ruta se cae, simplemente se examina el contenido de la tabla de topologías para seleccionar la mejor ruta de reemplazo. Segundo, si no hay una alternativa buena, los routers lanzan una consulta rápida a sus vecino para encontrar una.
Conceptos de DUAL
•Sucesor
–La mejor ruta con menor costo a un destino que se
encuentra en la tabla de enrutamiento
•Distancia factible:
–La métrica calculada más baja a lo largo de una ruta a la red de destino.
•FSM DUAL:
–Selecciona la mejor ruta sin bucles a un destino.
–Selecciona las rutas alternativas por medio de la información de las tablas de EIGRP.
Algoritmo de Dijkstra
Definición: El algoritmo de caminos mínimos o algoritmo de Dijkstra, es un algoritmo
para la determinación del camino más corto dado un vértice origen al
resto de vértices en un grafo dirigido y con pesos en cada arista.
Los algoritmos basados en el estado de enlace son muy utilizados en las redes actuales. Uno de los protocolos más importantes que lo usan es el OSPF.
Otro a destacar es el IS-IS (Intermediate System-Intermediate System o sistema intermedio-sistema intermedio) diseñado por DECnet y adoptado por la ISO. IS-IS se usa en varios backbone de Internet como el antiguo NSFNET.
A continuación vamos a enunciar el teorema sobre la complejidad
computacional que nos plantea el uso de este algoritmo: “El Algoritmo de
Dijkstra realiza O(n2) operaciones (sumas y comparaciones) para
determinar la longitud del camino más corto entre dos vértices de un
grafo ponderado simple, conexo y no dirigido con n vértices.”
Uso: La idea subyacente en este algoritmo consiste en ir
explorando todos los caminos más cortos que parten del vértice origen y
que llevan a todos los demás vértices; cuando se obtiene el camino más
corto desde el vértice origen, al resto de vértices que componen el
grafo, el algoritmo se detiene.
Este algoritmo es una especialización de la búsqueda de costo
uniforme, por tanto no funciona en grafos con aristas de costo con valor
negativo.
Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x
el nodo inicial, un vector V de tamaño N guardará al final del algoritmo
las distancias desde x al resto de los nodos.
- Inicializar todas las distancias en V con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
- Sea a = x (tomamos a como nodo actual).
- Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
- Si la distancia desde x hasta vi guardada en V es mayor que la
distancia desde x hasta a sumada a la distancia desde a hasta vi; esta
se sustituye con la segunda nombrada, esto es:
si (Vi > Va + d(a, vi)) entonces Vi = Va + d(a, vi) - Marcamos como completo el nodo a.
- Tomamos como próximo nodo actual el de menor valor en V (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, V estará completamente lleno.
