Algoritmos de enrutamiento

Los algoritmos de enrutamiento calculan las rutas que siguen los paquetes a través de una red, típicamente encontrando las rutas de menor costo sobre un grafo de enrutadores y enlaces, utilizando una vista global del estado de los enlaces o un cálculo distribuido de vector de distancia de vecino a vecino.

Definition

Un algoritmo de enrutamiento es un procedimiento que determina las rutas de menor costo (o preferidas de otra manera) a través de una red modelada como un grafo ponderado, produciendo las decisiones de reenvío que los enrutadores utilizan para mover paquetes hacia sus destinos.

Scope

Este tema abarca los algoritmos que pueblan las tablas de reenvío: el modelo de grafo de una red con costos de enlace; el enrutamiento de estado de enlace utilizando el algoritmo de ruta más corta de Dijkstra con una topología compartida globalmente; el enrutamiento de vector de distancia utilizando el cálculo distribuido de Bellman-Ford con intercambios entre vecinos; su comportamiento de convergencia y patologías como el problema de "contar hasta el infinito"; y el enrutamiento jerárquico para la escalabilidad. Trata los algoritmos de forma abstracta, dejando los protocolos concretos (OSPF, RIP, BGP) y su organización intra/inter-dominio para el tema de protocolos de enrutamiento.

Core questions

• ¿Cómo se modela una red como un grafo ponderado para el enrutamiento?
• ¿Cómo calcula un algoritmo de estado de enlace las rutas más cortas a partir de una vista de topología completa?
• ¿Cómo converge un algoritmo de vector de distancia utilizando solo intercambios entre vecinos?
• ¿Cuáles son los problemas de convergencia y estabilidad, como el de "contar hasta el infinito", y cómo se mitigan?
• ¿Por qué se jerarquiza el enrutamiento y cómo afecta eso a la optimización de la ruta?

Key concepts

• grafo de red ponderado
• rutas de menor costo
• enrutamiento de estado de enlace
• algoritmo de Dijkstra
• enrutamiento de vector de distancia
• ecuación de Bellman-Ford
• problema de "contar hasta el infinito"
• horizonte dividido y "poisoned reverse"
• enrutamiento jerárquico

Key theories

Enrutamiento de estado de enlace (Dijkstra)

Cada enrutador inunda sus costos de enlace para que todos los enrutadores compartan la topología completa, luego ejecuta independientemente el algoritmo de Dijkstra para calcular las rutas más cortas; esto converge rápida y predeciblemente, pero requiere un intercambio de información global.

Enrutamiento de vector de distancia (Bellman-Ford)

Los enrutadores intercambian sus estimaciones actuales de menor costo a cada destino con sus vecinos y actualizan a través de la ecuación de Bellman-Ford; el cálculo es distribuido y utiliza solo información local, pero puede converger lentamente y sufrir el problema de "contar hasta el infinito".

Enrutamiento jerárquico

Debido a que el enrutamiento plano no escala a toda la Internet, los enrutadores se agrupan en regiones (sistemas autónomos) con el enrutamiento manejado localmente dentro de cada región y resumido entre ellas, sacrificando cierta optimización de la ruta por escalabilidad y autonomía administrativa.

Clinical relevance

Los algoritmos de enrutamiento determinan la eficiencia y fiabilidad del flujo de tráfico: los algoritmos de estado de enlace subyacen a protocolos internos como OSPF que convergen rápidamente después de fallos, mientras que las ideas de vector de distancia aparecen en RIP y en el enfoque de vector de ruta de BGP. Comprender su comportamiento de convergencia es esencial para diseñar redes estables y diagnosticar bucles de enrutamiento y la recuperación lenta después de fallos de enlace o enrutador.

History

Los algoritmos de ruta más corta, que son el corazón del enrutamiento, son anteriores a las redes informáticas: el trabajo de Bellman y Ford sobre problemas de enrutamiento a finales de la década de 1950 y el algoritmo de ruta más corta de Dijkstra de 1959. A medida que las redes de paquetes crecieron, estos se adaptaron al enrutamiento de vector de distancia y de estado de enlace, y la estructuración jerárquica en sistemas autónomos hizo que el enrutamiento escalara a la Internet global.

Debates

Enrutamiento de estado de enlace versus vector de distancia

El enrutamiento de estado de enlace converge rápidamente y evita el problema de "contar hasta el infinito", pero requiere que cada enrutador mantenga la topología completa y realice más cálculos, mientras que el vector de distancia es más simple y local, pero puede converger lentamente y formar bucles transitorios; las redes reales combinan ambas ideas a diferentes escalas.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

¿Qué es el problema de "contar hasta el infinito"?

Es una patología del vector de distancia en la que, después de que un enlace falla, los enrutadores aumentan lentamente sus estimaciones de distancia a un destino inalcanzable al intercambiar información obsoleta, creyendo erróneamente que todavía existe una ruta a través de ellos. Las mitigaciones incluyen el horizonte dividido, el "poisoned reverse" y la limitación de la distancia máxima.

¿Por qué se utilizan tanto el estado de enlace como el vector de distancia?

Se adaptan a diferentes alcances. Los protocolos de estado de enlace como OSPF proporcionan una convergencia rápida y sin bucles dentro de un único dominio administrativo donde compartir la topología completa es aceptable. Los enfoques de vector de distancia y vector de ruta escalan mejor y revelan menos detalles internos entre dominios, por lo que BGP utiliza un diseño de vector de ruta entre redes.