Optimización de Rutas y Algoritmos de Enrutamiento en Redes

Principio de Optimización en Redes

El principio de optimización es un postulado general sobre las rutas óptimas en una red, sin importar su topología o tráfico. Establece que si el enrutador J está en la ruta óptima del enrutador I al enrutador K, entonces la ruta óptima de J a K también está en la misma ruta.

El conjunto de rutas óptimas desde todos los orígenes a un destino dado forma un árbol sumidero con raíz en el destino. Este árbol no es necesariamente único; pueden existir otros árboles con las mismas longitudes de ruta. No contiene ciclos, por lo que cada paquete se entrega en un número de saltos finito y limitado. Los enlaces y enrutadores pueden fallar y reactivarse, por lo que distintos enrutadores pueden tener ideas diferentes sobre la topología actual.

La meta de todos los algoritmos de enrutamiento es descubrir y utilizar los árboles sumideros de todos los enrutadores.

Enrutamiento por la Ruta Más Corta

Existen varias formas de medir la longitud de una ruta (métrica): cantidad de saltos, distancia geográfica en kilómetros, retardo en tiempo, etc.

Algoritmo de Dijkstra: Cada nodo se etiqueta con su distancia al nodo de origen a través de la mejor ruta conocida. Inicialmente, todos los nodos tienen la etiqueta infinito. Las etiquetas pueden cambiar cuando reflejan mejores rutas. Se dividen en tentativas (inicialmente todas lo son) o permanentes (cuando una etiqueta representa la ruta más corta posible del origen a ese nodo, no cambian más).

Inundación

La inundación es un algoritmo estático en el que cada paquete de entrada se envía por cada una de las líneas de salida, excepto aquella por la que llegó.

Genera grandes cantidades de paquetes duplicados. Esto se puede solucionar integrando un contador de saltos en el encabezado de cada paquete, que disminuye con cada salto, y descartando el paquete cuando el contador llega a 0. Lo ideal es inicializar el contador de saltos a la longitud de la ruta entre el origen y el destino. Otra forma de solucionarlo es llevar un registro de los paquetes difundidos para evitar enviarlos una segunda vez. Para lograrlo, el enrutador de origen pone un número de secuencia en cada paquete que recibe de sus hosts. Cada enrutador necesita una lista por cada enrutador de origen que indique los números de secuencia originados en ese enrutador que ya vio.

Para evitar que la lista crezca sin límites, cada una debe tener un contador que indique que todos los números de secuencia hasta él mismo ya han sido vistos.

Usos de la inundación: aplicaciones militares (por su robustez), en aplicaciones de bases de datos, en redes inalámbricas o como métrica contra la que pueden compararse otros algoritmos de enrutamiento (siempre escoge la ruta más corta posible porque escoge en paralelo todas las rutas posibles; ningún otro algoritmo puede producir un retardo más corto).

Inundación selectiva: Variación de la inundación donde 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.

Enrutamiento por Vector de Distancia

El enrutamiento por vector de distancia es un algoritmo dinámico que opera haciendo que cada enrutador mantenga una tabla que da la mejor distancia conocida a cada destino y la línea que se puede usar para llegar ahí. Estas tablas se actualizan intercambiando información con los vecinos.

Cada enrutador mantiene una tabla de enrutamiento indexada por, y que contiene un registro de, cada enrutador de la subred. Esta entrada comprende dos partes: línea preferida de salida hacia ese destino y una estimación del tiempo o distancia a ese destino. La métrica puede ser la cantidad de saltos, el retardo de tiempo en milisegundos, el número total de paquetes encolados en la ruta o algo similar.

El Problema de la Cuenta hasta Infinito

Aunque llega la respuesta correcta, puede hacerlo lentamente. Ningún enrutador jamás tiene un valor mayor en más de una unidad que el mínimo de todos sus vecinos. Todos los enrutadores elevan la cuenta hacia el infinito, pero el número de intercambios requerido depende del valor numérico usado para el infinito. Es prudente hacer que el infinito sea igual a la ruta más larga, más 1. Si la métrica es el retardo de tiempo, no hay un límite superior bien definido, por lo que se necesita un valor alto para evitar que una ruta con un retardo grande sea tratada como si estuviera desactivada.

El problema en sí consiste en que cuando X indica a Y que tiene una ruta en algún lugar, Y no tiene forma de saber si él mismo está en la ruta.

Dos problemas: el algoritmo tarda demasiado en converger y no se tenía en cuenta el ancho de banda al escoger rutas, porque la métrica de retardo era la longitud de la cola.

Enrutamiento por Estado de Enlace

Cada enrutador debe:

1. Descubrir a sus vecinos y conocer sus direcciones de red: Su primera tarea es averiguar quiénes son sus vecinos, para lo que envía un paquete HELLO especial a cada línea punto a punto. El enrutador del otro extremo regresa una respuesta indicando quién es. Estos nombres deben ser globalmente únicos porque si un enrutador distante escucha después de que tres enrutadores están conectados a F, es indispensable que pueda determinar si los tres se refieren al mismo F.
2. Medición del costo de línea: El algoritmo requiere que cada enrutador sepa el retardo a cada uno de sus vecinos. Para esto envía un paquete ECHO especial a través de la línea y una vez que llega al otro extremo, éste debe regresarlo inmediatamente. Si se mide el tiempo de ida y vuelta, y se divide en dos, se puede tener una idea razonable del retardo. Este método asume que los retardos son simétricos, y no siempre es así.
   
   Si se tiene en cuenta la carga, el temporizador debe iniciarse cuando el paquete ECHO se pone en cola. Cuando un enrutador puede escoger entre dos líneas con el mismo ancho de banda, una con carga alta continua y la otra sin ella, considerará como ruta más corta a la carga sin línea. El problema es que las tablas pueden oscilar sin control, provocando un enrutamiento errático y muchos problemas
   
   potenciales. Para evitar oscilaciones, en la selección de la mejor ruta, podría ser adecuado dividir las cargas entre múltiples líneas, con una fracción (carga viajando sobre cada una de ellas). Si se ignora la carga, el problema descrito no ocurre. El temporizador debe iniciarse cuando el paquete ECHO alcance el frente de la cola.
3. Construcción de los paquetes de estado del enlace: Cada enrutador debe construir un paquete que contenga todos los datos. El paquete comienza con la identidad del emisor, seguida de un número de secuencia, una edad y una lista de vecinos. Se da el retardo del vecino. Cuándo construirlos, dos opciones: de manera periódica (a intervalos regulares) o cuando ocurra un evento significativo (como la caída o reactivación de una línea o de un vecino, o el cambio apreciable en sus propiedades).
4. Distribución de los paquetes de estado del enlace: A medida que se distribuyen los paquetes, los enrutadores que reciban los primeros cambiarán sus rutas. Los distintos enrutadores podrían estar utilizando versiones diferentes de la topología, lo que puede conducir a inconsistencias.
   
   La idea del algoritmo es utilizar inundación para distribuir los paquetes del estado del enlace. Para controlarla, cada paquete contiene un número de secuencia que se incrementa con cada paquete nuevo enviado. Los enrutadores llevan el registro de todos los pares que ven. Cuando llega un paquete de estado del enlace, se verifica contra la lista de paquetes ya vistos. Si es nuevo, se reenvía a través de todas las líneas, excepto aquella que lo envió. Si es un duplicado, se descarta. Si llega un paquete con un número de secuencia menor, se rechaza como obsoleto ya que el enrutador tiene datos más recientes
   
   Problemas: si los números de secuencia vuelven a comenzar (ocurre cada 137 años), si llega a caerse un enrutador pierde el registro de su número de secuencia, si llega a corromperse un número de secuencia por un bit. La solución a estos problemas es incluir la edad de cada paquete después del número de secuencia y disminuirla una vez cada segundo. Cuando la edad llega a 0 se descarta la información de ese enrutador. Los mismos también decrementan el campo de edad durante el proceso inicial de inundación para asegurarse de no perder ningún paquete.
5. Cálculo de las nuevas rutas: Una vez que un enrutador ha acumulado un grupo completo de paquetes puede construir el grafo de la subred completa. Luego se ejecuta localmente el algoritmo de Dijkstra. Si una subred tiene n enrutadores y k vecinos la memoria requiere para almacenar los datos de entrada es proporcional a kn, es decir si la subred es muy grande puede ser un problema también el tiempo de cómputo, pero funciona bien. Los verdaderos problemas son si un enrutador afirma tener una línea que no tiene, u olvida una línea que si tiene, deja de reenviar paquetes o los corrompe al hacerlo, si se acaba la memoria o se ejecuta mal el algoritmo . Mientras la subred crezca la probabilidad de falla ocasional aumentará.

Enrutamiento Jerárquico

A medida que crece el tamaño de las redes, lo hacen de forma proporcional las tablas de enrutamiento del enrutador. Al crecer consumen más memoria del enrutador y necesitan más tiempo de CPU para examinarlas y más ancho de banda para enviar informes de estado entre enrutadores. Puede llegar a pasar que ya no sea

factible que cada enrutador tenga una entrada para cada uno de los demás enrutadores, lo que se soluciona con enrutamiento jerárquico. Cuando se lo utiliza, los enrutadores se dividen en regiones, donde cada enrutador conoce todos los detalles para enrutar paquetes a destinos dentro de su propia región, pero no sabe nada de la estructura interna de las otras regiones. Las ganancias de espacio del enrutamiento jerárquico no son gratuitas, sino que generan una longitud de ruta mayor.

El número óptimo de niveles para una subred de N enrutadores es ln N, y se requieren un total de e ln N entradas por enrutador. El aumento de la longitud media efectiva de ruta causado por el enrutamiento jerárquico es tan pequeño que por lo general es aceptable.