Algoritmos Estáticos

Algoritmos Estáticos

Enrutamiento por trayectoria 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 trayectoria 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 trayectoria 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 trayectoria conocida. Inicialmente no se conocen

trayectorias, por lo que todos los nodos tienen la etiqueta infinito. A medida que

avanza el algoritmo y se encuentran trayectorias, pueden cambiar las etiquetas,

reflejando mejores trayectorias. Una etiqueta puede ser tentativa o permanente.

Inicialmente todas las etiquetas son tentativas. Al descubrirse que una etiqueta

representa la trayectoria 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 es práctica en la mayoría de las aplicaciones, pero tiene algunos

usos. Por ejemplo, en aplicaciones militares y en las aplicaciones de bases de datos

distribuidas a veces es necesario actualizar concurrentemente todas las bases de datos,

en cuyo caso puede ser útil la inundación.

Enrutamiento basado en flujo

Los algoritmos vistos hasta ahora sólo toman en cuenta la topología; no consideran la carga. Si por ejemplo, siempre hay una gran cantidad de tráfico entre un nodo A y un nodo B, ambos adyacentes, podría ser mejor enrutar el tráfico de ambos por caminos alternativos un poco más largos tal vez. Seguidamente veremos un algoritmo estático; el enrutamiento basado en flujo usa tanto la topología como la carga para el enrutamiento.

La idea en que se basa el análisis es que, para una línea dada, si se conocen la

capacidad y el flujo promedio, es posible calcular el retardo promedio de los paquetes

en esa línea a partir de la teoría de colas. De los retardos promedio de todas las líneas,

es directo el cálculo de un promedio ponderado

...