Algoritmos De Enrutamiento

Introducción.

La capa de Red proporciona la dirección lógica que permite que dos sistemas dispares que se encuentran en redes lógicas diferentes determinen una posible ruta para comunicarse.

En la capa de red es donde residen los algoritmos que implementan los protocolos de enrutamiento. En la mayoría de las subredes, los paquetes requerirán varias escalas para completar el viaje. La excepción serían las redes de difusión, pero aún aquí es importante el enrutamiento, ya que el origen y el destino pueden no estar en la misma red.

El algoritmo de enrutamiento es la parte del software de la capa de red encargada de decidir la línea de salida por la que se transmitirá un paquete de entrada.

Si la subred usa datagramas entonces esta decisión debe hacerse cada vez que llega un paquete de datos de entrada, debido a que la mejor ruta podría haber cambiado desde la última vez. Si la subred utiliza circuitos virtuales internamente, las decisiones de enrutamiento se tomarán sólo al establecerse el circuito y los paquetes seguirán la ruta previamente establecida.

Meta de los algoritmos de enrutamiento es descubrir y utilizar los árboles sumideros de todos los enrutadores. El algoritmo de enrutamiento debe ser capaz de manejar cambios de topología y tráfico en funcionamiento. Necesitamos un punto medio entre eficiencia global y equidad hacia las conexiones individuales.

Podemos optimizar:

• Retardo medio de los paquetes.

• Máximo de velocidad de la red.

• Nº de saltos, etc.

Para lograr su cometido, la capa de red debe conocer la topología de la subred de comunicación (es decir, el grupo de enrutadores) y elegir las rutas adecuadas a través de ella; también debe tener cuidado al escoger las rutas para no sobrecargar algunas de las líneas de comunicación y los enrutadores y dejar inactivos a otros.

Conceptos básicos.

• Enrutamiento: es tomar la decisión de qué rutas seguir (entrenar tablas de enrutamiento).

• Reenvío: acción que se toma al llegar un paquete.

• Árbol de descenso o sumidero: es el conjunto de rutas óptimas para un nodo.

• Métrica: suele ser el número de saltos.

• El enrutador hace enrutamiento y reenvío.

• Host:

Agrupación de los Algoritmos de Enrutamiento.

Algoritmos Adaptativos:

En contraste con los algoritmos no adaptables, éstos cambian sus decisiones de enrutamiento para reflejar los cambios de topología y de tráfico. Difieren de los algoritmos estáticos en el lugar de obtención de su información (ej. localmente, en los routers adyacentes o de todos), el momento del cambio de sus rutas (ej. cada Dt seg., o cuando cambia la carga) y la métrica usada para la optimalidad (ej. distancia, nº de escalas, tiempo estimado del tránsito).

Este tipo de algoritmos no pueden ser demasiado complejos ya que son implementados en los routers y deben ejecutarse en tiempo real con recursos de CPU y la memoria con que el router dispone.

Algoritmos No Adaptativos:

No basan sus decisiones de enrutamiento en mediciones o estimaciones del tráfico ni en la topología. La decisión de qué ruta tomar de I a J se calcula por adelantado, fuera de línea y se cargan en los routers al iniciar la red. Éste procedimiento se llama enrutamiento estáticos.

La desventaja de este tipo de algoritmos es que no es posible responder a situaciones cambiantes como por ejemplo saturación, exceso de tráfico o fallo en una línea.

En un conjunto de redes complejas, se necesita cierto grado de cooperación “dinámica” entre los dispositivos de encaminamiento. En particular se deben evitar aquellas porciones de red que sufren congestión, entendiéndose esto como aquella situación donde hay demasiados paquetes en alguna parte de la subred, y como consecuencia el rendimiento de ésta baja.

Para poder tomar estas decisiones de encaminamiento dinámicas, los dispositivos involucrados en el ruteo deben intercambiar información usando algoritmos de encaminamiento especiales para este propósito. La información que se necesita sobre el estado del conjunto de redes tiene que venir expresada en términos de qué redes son accesibles a través de qué dispositivos y en términos de las características de retardo de varias rutas.

Principio de Optimización

Establece que es posible hacer un postulado general sobre las rutas óptimas sin importar la topología o el tráfico de la red.

Este postulado establece que, si el enrutador J está en la trayectoria óptima del enrutador I al enrutador K, entonces la trayectoria óptima de J a K también está en la misma ruta. Haciendo referencia a la figura 1, llamemos r1 a la parte de la ruta de I a J, y r2 al resto de la ruta. Si existiera una ruta mejor que r2 entre J y K, podría concatenarse con r1 para mejorar la ruta entre I y K, contradiciendo nuestra aseveración de que r1 y r2 es óptima.

Como consecuencia directa del principio de optimalidad, podemos ver que el grupo de trayectorias óptimas de todas las de orígenes a un destino dado forma un árbol con raíz en el destino. Ese árbol que se forma, se llama árbol de descenso, donde la métrica de distancia es el número de escalas. El árbol de descenso puede no ser único, pueden existir otros árboles con las mismas longitudes de trayectoria.

La meta de todos los algoritmos de enrutamiento es descubrir y usar los árboles de descenso para todos los enrutadores.

Figura 1. (a) Subred. (b) Árbol descendente para el ruteador B.

Dado que un árbol de descenso ciertamente es un árbol, no contiene ciclos, por lo que cada paquete será entregado con un número de escalas finito y limitado.

En la práctica, no siempre sucede esto, los enlaces y los enrutadores pueden caerse y reactivarse durante la operación, por lo que diferentes enrutadores pueden tener ideas distintas sobre la topología actual de la subred. El fin último de los algoritmos de ruteo es descubrir y usar los árboles de descenso de todos los enrutadores.

Clasificación de los Algoritmos de Enrutamiento.

Algoritmos Estáticos

Enrutamiento por la ruta más corta

Esta es una técnica de amplio uso en muchas formas, ya que es sencilla y fácil de entender. La idea es armar un grafo de la subred en el que cada nodo representa un enrutador y cada arco del grafo una línea de comunicación (enlace). Para seleccionar la ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el grafo la trayectoria más corta entre ellos.

El concepto de ruta más corta se debe a que la forma de medir la longitud de la ruta es usando alguna métrica, entendiéndose por métrica al peso relativo que se da a cada uno de los factores que intervienen en el cálculo de la distancia en una red, los cuales podrían ser el número de saltos, la distancia física, el retraso de transmisión por un paquete de prueba, el ancho de banda, el tráfico promedio, el costo de comunicación, etc.

Se conocen varios algoritmos de cálculo de la ruta más corta entre dos nodos de un grafo. Cada nodo se etiqueta (entre paréntesis) con su distancia al nodo de origen a través de la mejor ruta conocida. Inicialmente no se conocen rutas, por lo que todos los nodos tienen la etiqueta infinito. A medida que avanza el algoritmo y se encuentran rutas, pueden cambiar las etiquetas, reflejando mejores rutas. Una etiqueta puede ser tentativa o permanente.

Inicialmente todas las etiquetas son tentativas. Al descubrirse que una etiqueta representa la ruta más corta posible del origen a ese nodo, se vuelve permanente y no cambia más.

Inundación

Otro algoritmo estático es la inundación, en la que cada paquete de entrada se envía por cada una de las líneas de salida, excepto aquella por la que llegó. La inundación evidentemente genera grandes cantidades de paquetes duplicados, de hecho, una cantidad infinita a menos que se tomen algunas medidas para limitar ese proceso. Una de tales medidas puede ser un contador de escalas contenido en la cabecera de cada paquete, el cual disminuye en cada escala, descartándose al llegar el contador a cero.

Idealmente el contador debe inicializarse a la longitud de la trayectoria; puede inicializar el contador en el peor de los casos, es decir, el diámetro de la subred.

Una variación de la inundación, un poco más práctica es la inundación selectiva. En este algoritmo, los enrutadores no envían cada paquete de entrada por todas las líneas, sino sólo por aquellas que van aproximadamente en la dirección correcta.

La inundación no

...