Algoritmos de protocolos de enrutamiento vector distancia y estado enlace.

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:

1. 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.
2. Cada nodo envía su tabla a todos los nodos vecinos.
3. 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.

Las desventajas principales del algoritmo de Bellman-Ford en este ajuste son:

• 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.

1. 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.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. 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)
5. Marcamos como completo el nodo a.
6. 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.