Curso de Redes. 7.4. Algoritmos de routing.

Summary

El video explica los principios detrás de los algoritmos de enrutamiento, comenzando con el principio de optimalidad y su aplicación en la búsqueda de rutas óptimas. Se destacan las diferencias entre algoritmos estáticos y dinámicos, siendo estos últimos los más utilizados en Internet. Además, se abordan conceptos como el número de saltos, la velocidad de los enlaces y otros criterios para determinar las mejores rutas. También se mencionan las redes malladas y no malladas, y cómo los algoritmos dinámicos juegan un papel clave en la optimización del enrutamiento en redes complejas.

Takeaways

• 😀 El principio de optimalidad establece que si una ciudad está en la ruta óptima entre dos puntos, el camino óptimo hacia un destino también pasará por esa ciudad.
• 😀 Las rutas óptimas forman un árbol de rutas sin bucles, conocido como un árbol de expansión (spanning tree), con la raíz en el destino final.
• 😀 Aunque algunos enlaces no sean parte de la ruta óptima, pueden servir como enlaces de respaldo en caso de fallos en las rutas principales.
• 😀 El concepto de ruta óptima puede basarse en diferentes criterios, como el tiempo mínimo, la distancia mínima, o el consumo de combustible, dependiendo de la aplicación.
• 😀 En redes de comunicación, el número de saltos es un criterio clásico para determinar la ruta más corta, aunque no siempre es el mejor cuando hay enlaces con diferente capacidad.
• 😀 La velocidad de los enlaces es otro criterio importante para determinar la ruta más óptima, maximizando la velocidad o minimizando el costo inverso de la velocidad.
• 😀 En redes dinámicas, el tráfico y la saturación de los enlaces son factores cambiantes que pueden afectar la elección de la ruta, lo que complica la toma de decisiones en tiempo real.
• 😀 Los algoritmos de enrutamiento pueden dividirse en estáticos (basados en cálculos preestablecidos) y dinámicos (que se ajustan a cambios en tiempo real).
• 😀 Los algoritmos estáticos se usan principalmente en el diseño de redes para determinar la topología de la red y decidir qué enlaces utilizar entre diferentes nodos.
• 😀 Los algoritmos dinámicos son esenciales para redes malladas, como Internet, donde la información de las rutas debe actualizarse constantemente debido a cambios en la red.

Q & A

¿Qué es el principio de optimalidad en los algoritmos de routing?

El principio de optimalidad establece que si un nodo (por ejemplo, Valencia) forma parte de la ruta óptima entre dos ciudades (Murcia y Barcelona), entonces la ruta óptima entre Valencia y Barcelona también está incluida en la ruta óptima global. Esto asegura que el camino más corto entre dos puntos es el mismo al considerar nodos intermedios.

¿Qué es un árbol de expansión o 'spanning tree' en el contexto de los algoritmos de routing?

Un árbol de expansión es un conjunto de rutas óptimas que conectan un nodo central (como Barcelona) con todos los demás nodos sin formar bucles. Estas rutas forman una estructura jerárquica que optimiza la conectividad entre los nodos.

¿Cómo se diferencian los algoritmos estáticos de los dinámicos?

Los algoritmos estáticos se basan en datos predefinidos como el número de saltos y la velocidad de los enlaces, y no cambian en tiempo real. Son útiles en la fase de diseño de la red. Los algoritmos dinámicos, en cambio, ajustan las rutas basándose en condiciones cambiantes, como el tráfico en la red, y son más adecuados para redes con alta variabilidad.

¿Por qué es difícil implementar criterios dinámicos en los algoritmos de routing?

Los criterios dinámicos, como el caudal y la fiabilidad, son difíciles de medir y comparar en tiempo real. Además, estos criterios pueden causar oscilaciones en la red, lo que complica la toma de decisiones, ya que los cambios continuos en las condiciones de la red pueden generar inestabilidad.

¿Qué criterio se utiliza con mayor frecuencia en la práctica para calcular las rutas óptimas?

En la práctica, los criterios más utilizados son el número de saltos (hops) y la velocidad de los enlaces. Aunque otros criterios como el caudal o la fiabilidad son relevantes en la teoría, no se implementan comúnmente debido a su complejidad y la dificultad para medirlos en tiempo real.

¿Qué significa optimizar la 'velocidad' en los algoritmos de routing?

Optimizar la velocidad en el contexto de los algoritmos de routing implica elegir el camino que tiene los enlaces más rápidos. Para calcular la ruta óptima, se toma en cuenta el coste inverso de la velocidad, es decir, un mayor coste se asigna a los enlaces más rápidos.

¿Qué papel juegan los enlaces 'inútiles' en una red mallada?

Los enlaces que no forman parte de la ruta óptima (considerados 'inútiles') pueden seguir siendo valiosos como enlaces de respaldo. En caso de que un enlace principal falle, estos enlaces alternativos pueden ser utilizados para asegurar la continuidad de la comunicación.

¿Qué tipo de decisiones se toman al utilizar algoritmos estáticos en el diseño de redes?

Los algoritmos estáticos ayudan a tomar decisiones sobre la topología de la red, como qué enlaces deben conectarse entre diferentes oficinas de una empresa. Por ejemplo, podrían determinar si es más eficiente conectar dos oficinas directamente o a través de un nodo central.

¿Por qué es importante la fiabilidad de los enlaces en los algoritmos de routing?

La fiabilidad es crucial porque garantiza que los enlaces seleccionados para la transmisión de datos tienen una tasa baja de errores. Si un enlace tiene una alta tasa de errores, puede afectar negativamente al rendimiento de la red, por lo que se prefieren enlaces más fiables, incluso si no son los más rápidos.

¿Cuál es la diferencia entre la optimización basada en el número de saltos y la optimización basada en la velocidad de los enlaces?

La optimización basada en el número de saltos busca minimizar la cantidad de nodos intermedios por los que pasa el paquete de datos, mientras que la optimización basada en la velocidad se enfoca en elegir los caminos con los enlaces más rápidos. La optimización por velocidad se calcula tomando en cuenta el coste inverso de la velocidad de los enlaces.