TCP/IP (9): Algoritmos de rutado

Richard Bellman

Lester R. Ford

Rutado por vector-distancia (Bellman-Ford)

El algoritmo de vector-distancia, también conocido como Ford Fulkerson o Bellman-Ford, define una forma sencilla de mantener las pasarelas actualizadas.

Cuando una pasarela arranca, inicia su tabla de rutas para que contenga una entrada por cada red conectada directamente, indicando para cada una de ellas la distancia hacia ella, por lo general medida en saltos (que será cero pues están conectadas directamente).

Periódicamente, la pasarela J envía una copia de su tabla a cualquier otro que pueda alcanzar de manera directa (por ejemplo, K). Éste utilizará esta información para actualizar su propia tabla, en tres casos:

* Si J tiene una ruta más corta para un determinado destino.

* Si J lista un destino que K no tiene en su tabla.

* Si ha cambiado la distancia hacia algún destino hacia donde K ruta actualmente a través de J.Como es lógico, K tendrá que añadir una unidad a cada distancia que le reporte J.

En este tipo de diseño, todos las pasarelas han de participar en el intercambio de información para que las rutas sean consistentes.
El nombre vector-distancia proviene de que la información intercambiada es una lista de pares de destinos (o vectores) y distancias hacia ellos.

El protocolo GGP (Gateway-to-Gateway Protocol) se utilizó originalmente para el intercambio de rutas en el sistema central de pasarelas núcleo del INOC, y hace uso del algoritmo de vector-distancia.

Se transporta en datagramas IP igual que los protocolos UDP o TCP, con un encabezado de formato fijo que indica el formato del resto del mensaje.

El contenido consiste en un conjunto de pares de direcciones de red IP (netid) y distancias medidas en saltos (hops). Cero saltos indica que la red en cuestión está accesible directamente; es decir, el número representa la cantidad de pasarelas que un datagrama se encontrará en su camino hacia dicha red.

El punto débil de este planteamiento es que no siempre un número de saltos menor ha de producir menor retardo, pues las redes son heterogéneas, y tienen diferentes velocidades. Muchas pasarelas suman artificialmente varios saltos para trayectorias que cruzan redes lentas.

Para mantener los mensajes lo más cortos posible, se agrupan las entradas por distancias, enviándose para cada grupo un valor de distancia (8 bits), el número de redes que están a esa distancia (8 bits), seguidos por la lista de los netid de todas ellas.

En el mensaje puede también el emisor indicarle al receptor, mediante un campo de la cabecera, que necesita a su vez una actualización de él.

Este tipo de mensaje GGP se llama UPDATE (actualización). Otros tipos son los acuses de recibo positivos y negativos, las solicitudes de eco y sus respuestas. Un campo de 8 bits al principio de la cabecera identifica el tipo de mensaje.

Algoritmo de enlace-estado o SPF

El mítico Edsger Dijkstra inventó el SPF.

La principal desventaja de los algoritmos de vector-distancia es que no se extienden con la suficiente rapidez ante los cambios en la red. Además, requiere del intercambio de mensajes largos, cuyo tamaño es proporcional al número de redes. Esto, unido a la necesaria participación de todas las pasarelas, hace que la cantidad de información a intercambiar sea enorme.

La alternativa más aceptada es el algoritmo de enlace-estado, también conocido como SPF (Shortest Path First, primero el camino más corto), el cual hace que cada pasarela tenga una idea de la topología completa en forma de un grafo de nodos y arcos.

Cada pasarela prueba periódicamente el estado de sus vecinos en el grafo, o sea, aquellos a los que está conectado directamente, difundiendo esta información hacia otras pasarelas.

Para localizar los vecinos activos (up) o inactivos (down), se usa la regla k-out-of-n (k-de-n), que significa que el enlace se considera activo si un porcentaje significativo de solicitudes de eco tiene réplica.

Periódicamente, cada pasarela difunde el estado en que está cada uno de sus enlaces. El software del protocolo se encarga de hacer llegar a cada pasarela participante una copia sin modificación alguna de dicho mensaje. No hay en él información de rutado, sólo indica la disponibilidad de líneas y, en todo caso, la métrica hacia las pasarelas directamente conectadas a ella.

Cuando un mensaje de este tipo llega a una pasarela, éste actualiza su grafo y recomputa las rutas usando en conocido algoritmo del camino más corto de Dijkstra.

Como todos los participantes usan idéntica información de base para recomputar las rutas de manera local, la convergencia entre ellas está asegurada y los problemas de depuración son fáciles de resolver. Cada pasarela mantiene una base de datos completa, la misma para todas.

Simulación animada del SPF (fuente: Wikipedia)

La aplicación del algoritmo en cada pasarela lleva a la computación de un árbol de caminos óptimos distinto en cada una, tomándose a sí misma como raíz del árbol.

Entre los años 1989 y 1994 el IETF desarrolló un protocolo muy usado, basado en este algoritmo, que se denomina OSPF.