Algoritmos dinámicos


Enrutamiento vector de distancia


Los algoritmos de enrutamiento por vector de distancia operan haciendo que cada enrutador mantenga una tabla (por ejemplo, un vector) que da la mejor distancia conocida a cada destino y la línea a usar para llegar ahí. Estas tablas se actualizan intercambiando información con vecinos.
Algoritmo de enrutamiento Bellman-Ford distribuido y el algoritmo Ford-Fullkerson.
Cada enrutador mantiene una tabla de enrutamiento que contiene el registro de la subred y el enrutador de la subred. Esta entrada comprende dos partes: la línea preferida de salida hacia ese destino y una estimación del tiempo o distancia a ese destino. La métrica usada podría ser la cantidad de escalas, el retardo de tiempo en milisegundos, el número total de paquetes en cola por la trayectoria.
Los protocolos de vector de distancia más nuevos, como EIGRP y RIP-2, introducen el concepto de actualizaciones desencadenadas.
Una actualización desencadenada es una nueva tabla de enrutamiento que se envía de forma inmediata, en respuesta a un cambio.
Los paquetes que contienen el mensaje de actualización podrían ser descartados o dañados por algún enlace de la red.
Las actualizaciones desencadenadas no suceden de forma instantánea. Es posible que un router que no haya recibido aún la actualización desencadenada genere una actualización regular que cause que la ruta defectuosa sea insertada en un vecino que hubiese recibido ya la actualización.
Se supone que cada enrutador conoce la “distancia” a cada uno de sus vecinos.
Si la métrica es el retardo, ECHO.


(a) Subred (b) Entrada de A, I, H, K, y la nueva tabla de enrutamiento de J.


El problema del conteo a infinito


Reacciona con rapidez a las buenas noticias, pero con lentitud ante las malas.




Enrutamiento por estado de enlace

Se describe en cinco partes. Cada enrutador debe:

1. Descubrir a sus vecinos y conocer sus direcciones de red.
Al ponerse en operación un enrutador, su primera tarea es averiguar quiénes son sus vecinos; esto se logra enviando un paquete especial de HOLA (HELLO) por cada línea punto a punto. Se espera que el enrutador del otro extremo envíe de regreso su dirección única.

(a) Nueve enrutadores y una LAN (b) Modelo de grafo (a)

2. Medición del costo de la línea.
Se mide el tiempo de ida y vuelta que demora el ECHO y lo divide entre dos, el enrutador transmisor puede tener una idea razonable del retardo. Se realizan varias pruebas para promediar y así tener mejor resultado.

3. Construcción de los paquetes de estado de enlace.
Cada enrutador construye un paquete con todos los datos. 
Este paquete comienza con la identidad del transmisor, seguida de un número de secuencia, una edad y una lista de vecinos.
Es fácil construir los paquetes de estado de enlace. La parte difícil es determinar cuándo construirlos. Una posibilidad es construirlos periódicamente, a intervalos regulares.  Otra posibilidad es al ocurrir un evento significativo, como la caída o reactivación de una línea o de un vecino, o el cambio apreciable de sus propiedades.


(a) Subred (b) Paquete de estado de enlace para esta subred 

4. Distribución de los paquetes de estado de enlace.
La parte mas complicada del algoritmo es la distribución confiable de los paquetes de estado de enlace. A medida que se distribuyen e instalan los paquetes los enrutadores que reciban los primeros cambiarán sus rutas. En consecuencia, los distintos enrutadores podrían estar usando versiones diferentes de la topología, lo que puede conducir a inconsistencias, ciclos, máquinas inalcanzables, y otros problemas.
Inundación.

5. Cálculo de nuevas rutas.
Se usa ampliamente en redes actuales, algunos protocolos que lo usan son: el protocolo OSPF, que se emplea cada vez con mayor frecuencia en Internet, el IS-IS (sistema intermedio - sistema intermedio), diseñado por DECnet y el NetWare de Novell usa una variante menor del IS-IS (NLSP) para el enrutamiento de paquetes IPX.