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

...