Enrutamiento

El enrutamiento, ruteo o routing es el proceso de seleccionar una ruta para el tráfico en una red o entre múltiples redes. En términos generales, el enrutamiento se realiza en muchos tipos de redes, incluidas las redes de conmutación de circuitos, como la red telefónica pública conmutada (PSTN), y las redes informáticas, como Internet.

En las redes de conmutación de paquetes, el enrutamiento es la toma de decisiones de alto nivel que dirige los paquetes de red desde su origen hacia su destino a través de nodos de red intermedios mediante mecanismos específicos de reenvío de paquetes. El reenvío de paquetes es el tránsito de paquetes de red de una interfaz de red a otra. Los nodos intermedios suelen ser dispositivos de hardware de red, como enrutadores, puertas de enlace, cortafuegos o conmutadores. Las computadoras de propósito general también reenvían paquetes y realizan enrutamiento, aunque no tienen hardware especialmente optimizado para la tarea.

El proceso de enrutamiento generalmente dirige el reenvío sobre la base de tablas de enrutamiento. Las tablas de enrutamiento mantienen un registro de las rutas a varios destinos de la red. Las tablas de enrutamiento pueden ser especificadas por un administrador, aprendidas observando el tráfico de la red o construidas con la ayuda de protocolos de enrutamiento.

El enrutamiento, en un sentido más estricto del término, a menudo se refiere al enrutamiento IP y se contrasta con el puente. El enrutamiento IP asume que las direcciones de red están estructuradas y que direcciones similares implican proximidad dentro de la red. Las direcciones estructuradas permiten que una única entrada en la tabla de enrutamiento represente la ruta a un grupo de dispositivos. En redes grandes, el direccionamiento estructurado (enrutamiento, en sentido estricto) supera al direccionamiento no estructurado (puente). El enrutamiento se ha convertido en la forma dominante de direccionamiento en Internet. El puente todavía se usa ampliamente dentro de las redes de área local.

Esquemas de entrega

Esquemas de enrutamiento
unidifusión
Transmisión
multidifusión
Anycast

Los esquemas de enrutamiento difieren en la forma en que entregan los mensajes:

• Unicast entrega un mensaje a un solo nodo específico mediante una asociación uno a uno entre un remitente y un destino: cada dirección de destino identifica de manera única un único punto final del receptor.
• La difusión entrega un mensaje a todos los nodos de la red utilizando una asociación de uno a todos; un solo datagrama (o paquete) de un remitente se enruta a todos los puntos finales posiblemente múltiples asociados con la dirección de transmisión. La red replica automáticamente los datagramas según sea necesario para llegar a todos los destinatarios dentro del alcance de la transmisión, que generalmente es una subred de red completa.
• Multicast entrega un mensaje a un grupo de nodos que han expresado interés en recibir el mensaje utilizando una asociación de uno a muchos de muchos o de muchos a muchos de muchos; los datagramas se enrutan simultáneamente en una sola transmisión a muchos destinatarios. La multidifusión se diferencia de la difusión en que la dirección de destino designa un subconjunto, no necesariamente todos, de los nodos accesibles.
• Anycast entrega un mensaje a cualquiera de un grupo de nodos, generalmente el más cercano a la fuente utilizando una asociación de uno a uno de muchos donde los datagramas se enrutan a cualquier miembro de un grupo de receptores potenciales que son todos identificados por la misma dirección de destino. El algoritmo de enrutamiento selecciona el único receptor del grupo en función de cuál es el más cercano según alguna distancia o medida de costo.

Unicast es la forma dominante de entrega de mensajes en Internet. Este artículo se centra en los algoritmos de enrutamiento de unidifusión.

Distribución de topología

Con el enrutamiento estático, las redes pequeñas pueden usar tablas de enrutamiento configuradas manualmente. Las redes más grandes tienen topologías complejas que pueden cambiar rápidamente, lo que hace inviable la construcción manual de tablas de enrutamiento. Sin embargo, la mayor parte de la red telefónica pública conmutada (PSTN) utiliza tablas de enrutamiento precalculadas, con rutas de respaldo si la ruta más directa se bloquea (ver enrutamiento en la PSTN).

El enrutamiento dinámico intenta resolver este problema mediante la construcción automática de tablas de enrutamiento, basadas en la información transportada por los protocolos de enrutamiento, lo que permite que la red actúe de manera casi autónoma para evitar fallas y bloqueos en la red. El enrutamiento dinámico domina Internet. Los ejemplos de protocolos y algoritmos de enrutamiento dinámico incluyen el Protocolo de información de enrutamiento (RIP), Abrir primero la ruta más corta (OSPF) y el Protocolo de enrutamiento de puerta de enlace interior mejorado (EIGRP).

Algoritmos de vector de distancia

Los algoritmos de vector de distancia utilizan el algoritmo de Bellman-Ford. Este enfoque asigna un número de costo a cada uno de los enlaces entre cada nodo de la red. Los nodos envían información del punto A al punto B a través de la ruta que resulte en el costo total más bajo (es decir, la suma de los costos de los enlaces entre los nodos utilizados).

Cuando un nodo se inicia por primera vez, solo conoce a sus vecinos inmediatos y el costo directo que implica llegar a ellos. (Esta información, la lista de destinos, el costo total de cada uno y el siguiente salto para enviar datos para llegar allí, constituye la tabla de enrutamiento o tabla de distancias). Cada nodo, de manera regular, envía a cada nodo vecino su propia evaluación actual del costo total para llegar a todos los destinos que conoce. Los nodos vecinos examinan esta información y la comparan con lo que ya saben; cualquier cosa que represente una mejora sobre lo que ya tienen, lo insertan en su propia tabla. Con el tiempo, todos los nodos de la red descubren el mejor próximo salto y el costo total para todos los destinos.

Cuando un nodo de red deja de funcionar, los nodos que lo usaron como su próximo salto descartan la entrada y transmiten la información de enrutamiento actualizada a todos los nodos adyacentes, que a su vez repiten el proceso. Eventualmente, todos los nodos en la red reciben las actualizaciones y descubren nuevas rutas a todos los destinos que no involucran al nodo inactivo.

Algoritmos de estado de enlace

Al aplicar algoritmos de estado de enlace, un mapa gráfico de la red es el dato fundamental utilizado para cada nodo. Para producir su mapa, cada nodo inunda toda la red con información sobre los otros nodos a los que se puede conectar. Luego, cada nodo ensambla de forma independiente esta información en un mapa. Con este mapa, cada enrutador determina de forma independiente la ruta de menor costo desde sí mismo hasta todos los demás nodos mediante un algoritmo estándar de rutas más cortas, como el algoritmo de Dijkstra. El resultado es un gráfico de árbol con raíz en el nodo actual, de modo que la ruta a través del árbol desde la raíz hasta cualquier otro nodo es la ruta de menor costo a ese nodo. Este árbol luego sirve para construir la tabla de enrutamiento, que especifica el mejor próximo salto para llegar desde el nodo actual a cualquier otro nodo.

Algoritmo de enrutamiento de estado de enlace optimizado

Un algoritmo de enrutamiento de estado de enlace optimizado para redes móviles ad hoc es el Protocolo de enrutamiento de estado de enlace optimizado (OLSR). OLSR es proactivo; utiliza mensajes Hello y Topology Control (TC) para descubrir y difundir información de estado de enlace a través de la red móvil ad hoc. Usando mensajes de saludo, cada nodo descubre información de vecinos de 2 saltos y elige un conjunto de retransmisiones multipunto (MPR). Los MPR distinguen a OLSR de otros protocolos de enrutamiento de estado de enlace.

Protocolo de vector de ruta

El vector de distancia y el enrutamiento de estado de enlace son protocolos de enrutamiento dentro del dominio. Se utilizan dentro de un sistema autónomo, pero no entre sistemas autónomos. Ambos protocolos de enrutamiento se vuelven intratables en redes grandes y no se pueden usar en el enrutamiento entre dominios. El enrutamiento por vector de distancia está sujeto a inestabilidad si hay más de unos pocos saltos en el dominio. El enrutamiento de estado de enlace necesita recursos significativos para calcular las tablas de enrutamiento. También genera mucho tráfico debido a las inundaciones.

El enrutamiento por vector de ruta se utiliza para el enrutamiento entre dominios. Es similar al enrutamiento por vector de distancia. El enrutamiento por vector de ruta asume que un nodo (puede haber muchos) en cada sistema autónomo actúa en nombre de todo el sistema autónomo. Este nodo se denomina nodo hablante. El nodo de altavoz crea una tabla de enrutamiento y la anuncia a los nodos de altavoz vecinos en los sistemas autónomos vecinos. La idea es la misma que la del enrutamiento por vector de distancia, excepto que solo los nodos de altavoces en cada sistema autónomo pueden comunicarse entre sí. El nodo hablante anuncia la ruta, no la métrica, de los nodos en su sistema autónomo u otros sistemas autónomos.

El algoritmo de enrutamiento de vector de ruta es similar al algoritmo de vector de distancia en el sentido de que cada enrutador de borde anuncia los destinos que puede alcanzar a su enrutador vecino. Sin embargo, en lugar de anunciar las redes en términos de un destino y la distancia a ese destino, las redes se anuncian como direcciones de destino y descripciones de rutas para llegar a esos destinos. La ruta, expresada en términos de los dominios (o confederaciones) atravesados ​​hasta el momento, se transporta en un atributo de ruta especial que registra la secuencia de dominios de enrutamiento a través de los cuales ha pasado la información de accesibilidad. Una ruta se define como un emparejamiento entre un destino y los atributos de la ruta a ese destino, de ahí el nombre ruta-vector de enrutamiento; Los enrutadores reciben un vector que contiene rutas a un conjunto de destinos.

Selección de camino

La selección de ruta implica aplicar una métrica de enrutamiento a múltiples rutas para seleccionar (o predecir) la mejor ruta. La mayoría de los algoritmos de enrutamiento usan solo una ruta de red a la vez. El enrutamiento de rutas múltiples y específicamente las técnicas de enrutamiento de rutas múltiples de igual costo permiten el uso de múltiples rutas alternativas.

En las redes informáticas, la métrica se calcula mediante un algoritmo de enrutamiento y puede cubrir información como el ancho de banda, el retraso de la red, el conteo de saltos, el costo de la ruta, la carga, la unidad de transmisión máxima, la confiabilidad y el costo de la comunicación. La tabla de enrutamiento almacena solo las mejores rutas posibles, mientras que las bases de datos topológicas o de estado de enlace también pueden almacenar el resto de la información.

En caso de rutas superpuestas o iguales, los algoritmos consideran los siguientes elementos en orden de prioridad para decidir qué rutas instalar en la tabla de enrutamiento:

1. Longitud del prefijo: siempre se prefiere una entrada de la tabla de rutas coincidente con una máscara de subred más larga, ya que especifica el destino con mayor precisión.
2. Métrica: cuando se comparan rutas aprendidas a través del mismo protocolo de enrutamiento, se prefiere una métrica más baja. Las métricas no se pueden comparar entre rutas aprendidas de diferentes protocolos de enrutamiento.
3. Distancia administrativa: al comparar las entradas de la tabla de rutas de diferentes fuentes, como diferentes protocolos de enrutamiento y configuración estática, una distancia administrativa más baja indica una fuente más confiable y, por lo tanto, una ruta preferida.

Debido a que una métrica de enrutamiento es específica de un protocolo de enrutamiento dado, los enrutadores multiprotocolo deben usar alguna heurística externa para seleccionar entre rutas aprendidas de diferentes protocolos de enrutamiento. Los enrutadores de Cisco, por ejemplo, atribuyen un valor conocido como distancia administrativa a cada ruta, donde las distancias administrativas más pequeñas indican rutas aprendidas de un protocolo que se supone que es más confiable.

Un administrador local puede configurar rutas específicas de host que brinden más control sobre el uso de la red, permitan realizar pruebas y mejoren la seguridad general. Esto es útil para depurar conexiones de red o tablas de enrutamiento.

En algunos sistemas pequeños, un solo dispositivo central decide de antemano la ruta completa de cada paquete. En algunos otros sistemas pequeños, cualquier dispositivo de borde que inyecte un paquete en la red decide de antemano la ruta completa de ese paquete en particular. En cualquier caso, el dispositivo de planificación de rutas necesita saber mucha información sobre qué dispositivos están conectados a la red y cómo están conectados entre sí. Una vez que tiene esta información, puede usar un algoritmo como el algoritmo de búsqueda A* para encontrar la mejor ruta.

En los sistemas de alta velocidad, se transmiten tantos paquetes cada segundo que es inviable que un solo dispositivo calcule la ruta completa para todos y cada uno de los paquetes. Los primeros sistemas de alta velocidad se ocuparon de esto con la conmutación de circuitos estableciendo una ruta una vez para el primer paquete entre alguna fuente y algún destino; los paquetes posteriores entre esa misma fuente y ese mismo destino continúan siguiendo la misma ruta sin volver a calcular hasta que se interrumpe el circuito. Los sistemas de alta velocidad posteriores inyectan paquetes en la red sin que ningún dispositivo calcule nunca una ruta completa para los paquetes.

En sistemas grandes, hay tantas conexiones entre dispositivos, y esas conexiones cambian con tanta frecuencia, que es inviable para cualquier dispositivo saber cómo están conectados entre sí todos los dispositivos, y mucho menos calcular una ruta completa a través de ellos. Dichos sistemas generalmente utilizan el enrutamiento del siguiente salto.

La mayoría de los sistemas utilizan un algoritmo de enrutamiento dinámico determinista. Cuando un dispositivo elige una ruta a un destino final en particular, ese dispositivo siempre elige la misma ruta a ese destino hasta que recibe información que le hace pensar que otra ruta es mejor.

Algunos algoritmos de enrutamiento no utilizan un algoritmo determinista para encontrar el mejor enlace para que un paquete llegue desde su fuente original hasta su destino final. En cambio, para evitar puntos calientes de congestión en los sistemas de paquetes, algunos algoritmos utilizan un algoritmo aleatorio, el paradigma de Valiant, que enruta una ruta a un destino intermedio elegido al azar y desde allí a su verdadero destino final. En muchos de los primeros conmutadores telefónicos, a menudo se usaba un aleatorizador para seleccionar el inicio de una ruta a través de una estructura de conmutación de varias etapas.

Dependiendo de la aplicación para la que se realice la selección de ruta, se pueden utilizar diferentes métricas. Por ejemplo, para solicitudes web, se pueden usar rutas de latencia mínima para minimizar el tiempo de carga de la página web, o para transferencias masivas de datos, se puede elegir la ruta menos utilizada para equilibrar la carga en la red y aumentar el rendimiento. Un objetivo popular de selección de ruta es reducir los tiempos promedio de finalización de los flujos de tráfico y el consumo total de ancho de banda de la red. Recientemente, se propuso una métrica de selección de ruta que calcula el número total de bytes programados en los bordes por ruta como métrica de selección. Se ha puesto a disposición un análisis empírico de varias métricas de selección de rutas, incluida esta nueva propuesta.

Múltiples agentes

En algunas redes, el enrutamiento se complica por el hecho de que ninguna entidad individual es responsable de seleccionar las rutas; en cambio, múltiples entidades están involucradas en la selección de rutas o incluso partes de una sola ruta. Pueden surgir complicaciones o ineficiencia si estas entidades eligen caminos para optimizar sus propios objetivos, lo que puede entrar en conflicto con los objetivos de otros participantes.

Un ejemplo clásico implica el tráfico en un sistema de carreteras, en el que cada conductor elige un camino que minimiza su tiempo de viaje. Con tal enrutamiento, las rutas de equilibrio pueden ser más largas que las óptimas para todos los conductores. En particular, la paradoja de Braess muestra que agregar una nueva carretera puede alargar los tiempos de viaje para todos los conductores.

En un modelo de agente único utilizado, por ejemplo, para enrutar vehículos de guiado automático (AGV) en una terminal, se realizan reservas para cada vehículo para evitar el uso simultáneo de la misma parte de una infraestructura. Este enfoque también se conoce como enrutamiento consciente del contexto.

Internet se divide en sistemas autónomos (AS), como proveedores de servicios de Internet (ISP), cada uno de los cuales controla las rutas que involucran su red. El enrutamiento se produce en múltiples niveles. Primero, las rutas de nivel de AS se seleccionan a través del protocolo BGP que produce una secuencia de AS a través de la cual fluyen los paquetes. Cada AS puede tener varias rutas, ofrecidas por los AS vecinos, entre las que elegir. Estas decisiones de enrutamiento a menudo se correlacionan con las relaciones comerciales con estos AS vecinos,que puede no estar relacionado con la calidad de la ruta o la latencia. En segundo lugar, una vez que se ha seleccionado una ruta de nivel de AS, a menudo hay varias rutas de nivel de enrutador correspondientes para elegir. Esto se debe, en parte, a que dos ISP pueden estar conectados a través de múltiples conexiones. Al elegir la ruta a nivel de enrutador único, es una práctica común que cada ISP emplee el enrutamiento hot-potato: enviar tráfico a lo largo de la ruta que minimiza la distancia a través de la propia red del ISP, incluso si esa ruta alarga la distancia total hasta el destino.

Por ejemplo, considere dos ISP, A y B. Cada uno tiene presencia en Nueva York, conectados por un enlace rápido con latencia5 ms, y cada uno tiene una presencia en Londres conectada por un enlace de 5 ms. Suponga que ambos ISP tienen enlaces transatlánticos que conectan sus dos redes, pero el enlace de A tiene una latencia de 100 ms y el de B tiene una latencia de 120 ms. Al enrutar un mensaje desde un origen en la red de Londres de A a un destino en la red de Nueva York de B, A puede optar por enviar inmediatamente el mensaje a B en Londres. Esto le ahorra a A el trabajo de enviarlo a través de un costoso enlace transatlántico, pero hace que el mensaje experimente una latencia de 125 ms cuando la otra ruta habría sido 20 ms más rápida.

Un estudio de medición de rutas de Internet de 2003 encontró que, entre pares de ISP vecinos, más del 30 % de las rutas tienen una latencia inflada debido al enrutamiento hot-potato, y el 5 % de las rutas se retrasan al menos 12 ms. La inflación debida a la selección de ruta de nivel AS, aunque sustancial, se atribuyó principalmente a la falta de un mecanismo de BGP para optimizar directamente la latencia, en lugar de políticas de enrutamiento egoístas. También se sugirió que, si se implementara un mecanismo apropiado, los ISP estarían dispuestos a cooperar para reducir la latencia en lugar de utilizar el enrutamiento de patata caliente. Dicho mecanismo fue publicado posteriormente por los mismos autores, primero para el caso de dos ISP y luego para el caso global.

Análisis de rutas

A medida que Internet y las redes IP se han convertido en herramientas comerciales de misión crítica, ha aumentado el interés en técnicas y métodos para monitorear la postura de enrutamiento de las redes. El enrutamiento incorrecto o los problemas de enrutamiento provocan una degradación del rendimiento, fluctuaciones o tiempos de inactividad no deseados. El enrutamiento de monitoreo en una red se logra utilizando herramientas y técnicas de análisis de rutas.

Enrutamiento centralizado

En las redes en las que se dispone de un control lógicamente centralizado sobre el estado de reenvío, por ejemplo, mediante el uso de redes definidas por software, se pueden utilizar técnicas de enrutamiento que apuntan a optimizar las métricas de rendimiento globales y de toda la red. Esto ha sido utilizado por grandes empresas de Internet que operan muchos centros de datos en diferentes ubicaciones geográficas conectados mediante enlaces ópticos privados, ejemplos de los cuales incluyen WAN global de Microsoft, Express Backbone de Facebook y B4 de Google.

Las métricas de rendimiento global para optimizar incluyen la maximización de la utilización de la red, la minimización de los tiempos de finalización del flujo de tráfico, la maximización del tráfico entregado antes de los plazos específicos y la reducción de los tiempos de finalización de los flujos. El trabajo en la última sobre WAN privada analiza el modelado de enrutamiento como un problema de optimización de gráficos al llevar todas las colas a los puntos finales. Los autores también proponen una heurística para resolver el problema de manera eficiente sacrificando un rendimiento insignificante.