Algoritmos de enrutamiento fijo y de inundación

En la mayoría de las situaciones, los paquetes requieren múltiples saltos para hacer un viaje hacia el destino. El enrutamiento es uno de los aspectos más complejos y cruciales del diseño de redes de conmutación de paquetes. 

Propiedades deseables de los algoritmos de enrutamiento : –  

• Corrección y Simplicidad
• Robustez: Habilidad de la red para entregar paquetes a través de alguna ruta incluso ante fallas.
• Estabilidad: el algoritmo debe converger al equilibrio rápidamente frente a condiciones cambiantes en la red.
• Equidad y Optimalidad
• Eficiencia: gastos generales mínimos.

Parámetros de diseño de algoritmos de enrutamiento:  

• Criterios de rendimiento: número de saltos, costo (envío de paquetes con una ruta de ancho de banda alto ya que el costo es menor), retraso (tamaño de la cola), tiempo de rendimiento (número de paquetes entregados/tiempo).
• Tiempo de decisión: ¿Cuándo decidir enrutar un paquete? Por paquete (datagrama) o por sesión (circuito virtual).
• Lugar de decisión: ¿Quién decidirá sobre el enrutamiento? Cada Node (distribuido), Node Central (centralizado), Node Originado (fuente) .
• Fuente de información de red: ninguna, local, Node adyacente, Nodes a lo largo de la ruta, todos los Nodes.
• Tiempo de actualización de la información de la red: continuo, periódico, cambio de carga importante, cambio de topología.

Estrategias de enrutamiento:  

1. Enrutamiento fijo
2. Inundación
3. Enrutamiento dinámico
4. Enrutamiento aleatorio
5. Enrutamiento basado en flujo

Enrutamiento fijo –  

• Se selecciona una ruta para cada par de Nodes de origen y destino en la red.
• La ruta es fija; cambia sólo si cambia la topología de la red.

Enrutamiento fijo: ejemplo (1)  

Figura: una red de conmutación de paquetes simple con seis Nodes (enrutadores)  

Figura: tabla de enrutamiento central basada en el algoritmo de ruta de menor costo  

• Se crea una array de enrutamiento central basada en la ruta de menor costo que se almacena en el centro de control de la red.
• La array muestra para cada origen-destino de la ruta, la identidad del siguiente Node de la ruta.
• Inconveniente: si el centro de control de la red falla, todo colapsará. Por lo tanto, no es confiable.

Enrutamiento fijo: ejemplo (2)  

Figura – Tabla de enrutamiento almacenada en diferentes Nodes de la red 

• La tabla de enrutamiento se crea para cada Node. Esto se llama un algoritmo de enrutamiento distribuido.
• La tabla de enrutamiento se puede crear utilizando la ruta mínima mínima o el método de alcance de salto mínimo. Dos algoritmos de ruta famosos 
  1. Algoritmo de Dijkstra
  2. Algoritmo Bellman Ford

Ventajas –  

• Simple
• Funciona bien en una red confiable con carga estable en una red confiable
• Lo mismo para circuito virtual y datagrama.

Desventajas –  

• Falta de flexibilidad
• No reacciona ante fallas o congestión de la red.

Inundación –  

• No requiere información de red como topología, condición de carga, costo de diferencia. caminos
• Cada paquete entrante a un Node se envía en todos los salientes, excepto en el que llegó.
• Por ejemplo en la figura anterior
  • Un paquete entrante a (1) se envía a (2), (3)
  • de (2) se envía a (6),(4), y de (3) se envía a (4),(5)
  • de (4) se envía a (6),(5),(3), de (6) se envía a (2),(4),(5), de (5) se envía a (4) ),(3)

Características –  

• Se prueban todas las rutas posibles entre el origen y el destino. Un paquete siempre pasará si existe la ruta
• Como se intentan todas las rutas, habrá al menos una ruta que sea la más corta
• Se visitan todos los Nodes conectados directa o indirectamente

Limitaciones –  

• La inundación genera una gran cantidad de paquetes duplicados
• Se debe utilizar un mecanismo de amortiguación adecuado.

Número de saltos –  

• Un contador de saltos puede estar contenido en la cabecera del paquete que se decrementa en cada salto. 
  con el paquete siendo descartado cuando el contador llega a cero
• El remitente inicializa el contador de saltos. Si no se conoce ninguna estimación, se establece en el diámetro completo de la subred.
• Realice un seguimiento de los paquetes que son responsables de la inundación utilizando un número de secuencia. Evite enviarlos por segunda vez.

Inundación selectiva: los enrutadores no envían todos los paquetes entrantes en todas las líneas, solo en aquellas líneas que van aproximadamente en la dirección del destino. 

Ventajas de las inundaciones:  

• Se pueden enviar mensajes de emergencia o inmediatos altamente robustos (por ejemplo, aplicaciones militares)
• Configurar la ruta en circuito virtual
• Las inundaciones siempre eligen el camino más corto
• Transmitir mensajes a todos los Nodes.

Referencia –  
Comunicaciones de datos e informática 

Leer el siguiente artículo: conjunto de protocolos de enrutamiento 1 (enrutamiento por vector de distancia)