algoritmo enrutamiento

Si has leído nuestra sección sobre lo que es un router, entonces sabrás que un router se usa para gestionar el tráfico de red y encontrar la mejor ruta para el envío de paquetes. Pero, ¿has pensado como lo hacen los routers? Estos dispositivos necesitan algo de información sobre el estado de la red para poder tomar decisiones de cómo hacer el envío de los paquetes a su destino. Intentaremos explicar como recopilan esta información tan importante.

Conceptos básicos

Los routers o enrutadores usan algoritmos de routing para encontrar el mejor camino a un destino. Cuando decimos “la mejor ruta”, se consideran parámetros como el número de saltos (los equipos por donde pasa el paquete de un punto a otro de la red), el tiempo de retardo, y el coste de comunicación de un paquete transmitido. Basándonos en como los routers recopilan información sobre la estructura de red y su análisis para especificar la ruta ideal, tenemos dos algoritmos principales: Algoritmos de routing globales y algoritmos de routing descentralizados.

En los algoritmos descentralizados, cada router tiene información sobre el router al que está directamente conectado, y no tiene conocimiento de los otros routers en la red. Estos algoritmos son conocidos como de vector de distancia.

En los algoritmos globales, cada uno de los router tiene una completa información sobre todos los demás routers en la red y el estado del tráfico. Estos algoritmos son conocidos como de estado de enlace.

Algoritmos de vector de estado de enlace

En este tipo de algoritmos, los routers dentro de una red deben seguir estos pasos:

1 – Identificar los routers que están físicamente conectados a ellos y conseguir  sus direcciones IP. Cuando un router empieza a funcionar, manda un paquete llamado “hello” sobre la red. Cada router que recibe dicho paquete responde con un mensaje que contiene su dirección IP.

2 – Medir el tiempo de retardo (o cualquier otro parámetro importante de la red) para los router vecinos. Para hacer esto, los router envían los paquetes eco (echo packets) sobre la red. Los routers que reciben este paquete responden a su vez con otro eco. Sabiendo el tiempo que se tarda en llegar y volver de un router a otro, se puede sacar una valoración del retardo producido.

3 – Difundir (broadcast) la información del router por la red para otros routers y recibir la información de otros routers. En este paso, todos los routers reciben comparten su conocimiento entre ellos, y distribuyen la información que tienen sobre la red. De este modo, todos los routers saben la estructura y estado de la red.

4 – Usando un algoritmo apropiado, hay que identificar la mejor ruta entre dos nodos en la red. En este paso, los routers eligen el mejor camino a cada uno de los nodos. Para poner un ejemplo, en el algoritmo Dijkstra, un router basándose en la información almacenada de otros routers, construye un gráfico de la red. Este gráfico muestra la localización de los routers en la red y los enlaces entre cada uno de ellos.

Cada enlace es etiquetado con un número llamado coste o peso. Este número es una combinación del tiempo de retardo, promedio de tráfico, y en ocasiones simplemente el número de saltos entre nodos. Por ejemplo, si hay dos enlaces entre un nodo y un destino, el router elige el enlace con menor coste.

Algoritmos de vector de distancia

Este tipo de algoritmos son también conocidos como los algoritmos de routing Bellman-Ford. En estos algoritmos, cada uno de los router tiene una tabla de routing que muestra la mejor ruta para cualquier camino. En un algoritmo de vector de distancia, cada router tiene que seguir unos pasos determinados:

1 – Cuanta el coste de los enlaces directamente conectados a el y salva la información a su tabla de routing.

2 – En un tiempo determinado, envía esta tabla a sus router vecinos (no a todos los router) y al mismo tiempo recibe la tabla de routing sus propios vecinos.

3 – Basándose en la información de las tablas de enrutamiento de sus vecinos, actualiza su propia tabla de rutas.

Routing jerárquico

Como has podido ver, en ambos algoritmos, todos los router tienen que salvar y almacenar alguna información sobre otros router. Cuando el tamaño de la red crece, el número de routers también crece. De forma consecutiva, el tamaño de las tablas de rutas crece y los router no pueden manejar el tráfico de red tan eficientemente. Para esto se usa el routing jerárquico. En este modelo de routing, los enrutadores se clasifican en grupos conocidos como regiones.

Cada uno de los router solo tiene la información de los routers de su región y no tiene información de equipos de otras regiones. Uno o más de los router tiene comunicación directa con otros routers en otras regiones y envía cuando es necesario a su gateway de destino.

Dejar respuesta

Please enter your comment!
Please enter your name here

El periodo de verificación de reCAPTCHA ha caducado. Por favor, recarga la página.