El enrutamiento es el proceso de seleccionar una ruta para el tráfico en una red o entre varias redes. En términos generales, el enrutamiento se realiza en muchos tipos de redes, incluidas las redes conmutadas por 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 nivel superior 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 desde 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 uso general también reenvían paquetes y realizan el enrutamiento, aunque no tienen hardware especialmente optimizado para la tarea.
El proceso de enrutamiento generalmente dirige el reenvío en función de las 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 al observar 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 bridging . El enrutamiento IP supone que las direcciones de red están estructuradas y que las direcciones similares implican proximidad dentro de la red. Las direcciones estructuradas permiten que una sola entrada de 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 (bridging). El enrutamiento se ha convertido en la forma dominante de direccionamiento en Internet. El bridging todavía se usa ampliamente dentro de las redes de área local .
Los esquemas de enrutamiento difieren en cómo entregan los mensajes:
El unicast es la forma predominante de entrega de mensajes en Internet. Este artículo se centra en los algoritmos de enrutamiento unicast.
Con el enrutamiento estático , las redes pequeñas pueden utilizar tablas de enrutamiento configuradas manualmente. Las redes más grandes tienen topologías complejas que pueden cambiar rápidamente, lo que hace que la construcción manual de tablas de enrutamiento sea inviable. Sin embargo, la mayoría de las redes telefónicas públicas conmutadas (PSTN) utilizan tablas de enrutamiento calculadas previamente, con rutas de respaldo si la ruta más directa se bloquea (consulte enrutamiento en la PSTN ).
El enrutamiento dinámico intenta resolver este problema mediante la construcción automática de tablas de enrutamiento, en función de la información que llevan los protocolos de enrutamiento , lo que permite que la red actúe de forma casi autónoma para evitar fallos y bloqueos de la red. El enrutamiento dinámico domina Internet. Algunos ejemplos de protocolos y algoritmos de enrutamiento dinámico son el Protocolo de información de enrutamiento (RIP), el Protocolo de ruta más corta abierta primero (OSPF) y el Protocolo de enrutamiento de puerta de enlace interior mejorado (EIGRP).
Los algoritmos de vector de distancia utilizan el algoritmo 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 desde el punto A al punto B a través de la ruta que da como resultado 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, sólo conoce a sus vecinos inmediatos y el costo directo que implica llegar a ellos. (Esta información —la lista de destinos, el costo total para cada uno y el siguiente salto para enviar datos para llegar allí— conforma la tabla de enrutamiento o tabla de distancia ). 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; todo lo que representa una mejora de lo que ya tienen, lo insertan en su propia tabla. Con el tiempo, todos los nodos de la red descubren el mejor siguiente salto y el costo total para todos los destinos.
Cuando un nodo de la red deja de funcionar, todos los nodos que lo usaron como siguiente salto descartan la entrada y transmiten la información de enrutamiento actualizada a todos los nodos adyacentes, que a su vez repiten el proceso. Finalmente, todos los nodos de la red reciben las actualizaciones y descubren nuevas rutas a todos los destinos que no involucran al nodo que se encuentra inactivo.
Al aplicar algoritmos de estado de enlace, un mapa gráfico de la red es el dato fundamental que se utiliza 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 reúne esta información de forma independiente 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 utilizando 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 hasta ese nodo. Luego, este árbol sirve para construir la tabla de enrutamiento, que especifica el mejor siguiente salto para llegar desde el nodo actual a cualquier otro nodo.
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). [2] OLSR es proactivo; utiliza mensajes de Hola y Control de topología (TC) para descubrir y difundir información de estado de enlace a través de la red móvil ad hoc. Mediante mensajes de Hola, cada nodo descubre información de vecinos de 2 saltos y elige un conjunto de relés multipunto (MPR). Los MPR distinguen a OLSR de otros protocolos de enrutamiento de estado de enlace.
El enrutamiento por vector de distancia y por estado de enlace son protocolos de enrutamiento intradominio. 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 utilizar 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 por estado de enlace necesita recursos significativos para calcular las tablas de enrutamiento. También crea mucho tráfico debido a la inundación.
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 supone 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 hablante crea una tabla de enrutamiento y la anuncia a los nodos hablantes vecinos en los sistemas autónomos vecinos. La idea es la misma que el enrutamiento por vector de distancia, excepto que solo los nodos hablantes de 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 o en otros sistemas autónomos.
El algoritmo de enrutamiento por vector de ruta es similar al algoritmo por vector de distancia en el sentido de que cada enrutador de frontera anuncia los destinos a los que puede llegar a su enrutador vecino. Sin embargo, en lugar de anunciar 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, enrutamiento por vector de ruta; los enrutadores reciben un vector que contiene rutas a un conjunto de destinos. [3]
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 utilizan solo una ruta de red a la vez. El enrutamiento multitrayecto y, específicamente, las técnicas de enrutamiento multitrayecto de igual costo permiten el uso de múltiples rutas alternativas.
En redes de computadoras, la métrica se calcula mediante un algoritmo de enrutamiento y puede cubrir información como ancho de banda , retraso de red , conteo de saltos , costo de ruta, carga, unidad máxima de transmisión , confiabilidad y costo de comunicación. [4] 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 toda la demás 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:
Debido a que una métrica de enrutamiento es específica de un protocolo de enrutamiento determinado, los enrutadores multiprotocolo deben utilizar alguna heurística externa para seleccionar entre las rutas aprendidas de diferentes protocolos de enrutamiento. Los enrutadores 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 del host que brindan más control sobre el uso de la red, permiten realizar pruebas y brindan una mejor seguridad general. Esto resulta útil para depurar conexiones de red o tablas de enrutamiento.
En algunos sistemas pequeños, un único dispositivo central decide de antemano la ruta completa de cada paquete. En otros sistemas pequeños, el dispositivo de borde que inyecta 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 conocer 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 utilizar un algoritmo como el algoritmo de búsqueda A* para encontrar la mejor ruta.
En los sistemas de alta velocidad, se transmiten tantos paquetes por segundo que resulta imposible que un único dispositivo calcule la ruta completa de cada uno de ellos. Los primeros sistemas de alta velocidad se ocupaban de esto mediante la conmutación de circuitos , estableciendo una ruta una vez para el primer paquete entre una fuente y un destino; los paquetes posteriores entre esa misma fuente y ese mismo destino siguen la misma ruta sin volver a calcularla hasta que se desmonta 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 los sistemas grandes, hay tantas conexiones entre dispositivos y esas conexiones cambian con tanta frecuencia que resulta imposible que un dispositivo sepa cómo están conectados entre sí todos los dispositivos, y mucho menos calcular una ruta completa a través de ellos. Estos sistemas generalmente utilizan enrutamiento de siguiente salto .
La mayoría de los sistemas utilizan un algoritmo de enrutamiento dinámico determinista . Cuando un dispositivo elige una ruta hacia un destino final en particular, siempre elige la misma ruta 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 origen hasta su destino final. En cambio, para evitar puntos críticos de congestión en los sistemas de paquetes, algunos algoritmos utilizan un algoritmo aleatorio (el paradigma de Valiant) que enruta una ruta hacia un destino intermedio elegido aleatoriamente y, desde allí, hacia su verdadero destino final. [5] [6] En muchos de los primeros conmutadores telefónicos, a menudo se utilizaba un aleatorizador para seleccionar el inicio de una ruta a través de una estructura de conmutación de múltiples etapas .
Dependiendo de la aplicación para la que se realiza la selección de ruta, se pueden utilizar diferentes métricas. Por ejemplo, para las solicitudes web, se pueden utilizar rutas de latencia mínima para minimizar el tiempo de carga de la página web, o para las transferencias de datos en masa, 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 de finalización promedio 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 la cantidad total de bytes programados en los bordes por ruta como métrica de selección. [7] Se ha puesto a disposición un análisis empírico de varias métricas de selección de ruta, incluida esta nueva propuesta. [8]
En algunas redes, el enrutamiento se complica por el hecho de que ninguna entidad es responsable de seleccionar las rutas; en cambio, varias entidades participan en la selección de rutas o incluso partes de una sola ruta. Pueden surgir complicaciones o ineficiencias si estas entidades eligen rutas para optimizar sus propios objetivos, lo que puede entrar en conflicto con los objetivos de otros participantes.
Un ejemplo clásico es el del tráfico en un sistema vial, en el que cada conductor elige una ruta que minimiza su tiempo de viaje. Con este tipo de rutas, las rutas de equilibrio pueden ser más largas que las óptimas para todos los conductores. En particular, la paradoja de Braess muestra que añadir 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 guiados automáticamente (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. [9]
Internet está dividida en sistemas autónomos (AS), como los proveedores de servicios de Internet (ISP), cada uno de los cuales controla las rutas que involucran a su red. El enrutamiento se produce en múltiples niveles. En primer lugar, las rutas de nivel AS se seleccionan a través del protocolo BGP que produce una secuencia de AS a través de los cuales fluyen los paquetes. Cada AS puede tener múltiples rutas, ofrecidas por AS vecinos, de las cuales elegir. Estas decisiones de enrutamiento a menudo se correlacionan con las relaciones comerciales con estos AS vecinos, [10] que pueden no estar relacionadas con la calidad o la latencia de la ruta. En segundo lugar, una vez que se ha seleccionado una ruta de nivel AS, a menudo hay múltiples rutas correspondientes de nivel de enrutador 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 única de nivel de enrutador, 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 al destino.
Por ejemplo, considere dos ISP, A y B. Cada uno tiene presencia en Nueva York , conectados por un enlace rápido con latencia.5 ms —y cada uno tiene una presencia en Londres conectada por un enlace de 5 ms. Supongamos 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 una fuente 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.
Además, se puede observar un desafío de enrutamiento similar en las redes celulares, donde diferentes paquetes se destinan a varios puntos finales y cada enlace exhibe una eficiencia espectral variable. En este contexto, la selección de la ruta óptima implica considerar la latencia y la tasa de error de paquetes. Para abordar esto, múltiples entidades independientes, una para cada estación base, desempeñan un papel crucial en la selección de la ruta mientras se busca optimizar el rendimiento general de la red. [11]
Un estudio de medición de rutas de Internet realizado en 2003 descubrió 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 tienen un retraso de al menos 12 ms. La inflación debida a la selección de rutas a nivel de AS, aunque sustancial, se atribuyó principalmente a la falta de un mecanismo de BGP para optimizar directamente la latencia, en lugar de a políticas de enrutamiento egoístas. También se sugirió que, si hubiera un mecanismo adecuado, los ISP estarían dispuestos a cooperar para reducir la latencia en lugar de utilizar el enrutamiento hot-potato. [12] Los mismos autores publicaron posteriormente un mecanismo de este tipo, primero para el caso de dos ISP [13] y luego para el caso global. [14]
A medida que Internet y las redes IP se han convertido en herramientas empresariales de misión crítica , ha aumentado el interés en técnicas y métodos para supervisar la postura de enrutamiento de las redes. El enrutamiento incorrecto o los problemas de enrutamiento provocan una degradación del rendimiento no deseada, oscilaciones o tiempos de inactividad. El control del enrutamiento en una red se logra utilizando herramientas y técnicas de análisis de rutas . [15]
En redes donde se dispone de un control centralizado lógico sobre el estado de reenvío, por ejemplo, mediante 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 la WAN global de Microsoft, [16] la red troncal Express de Facebook, [17] y B4 de Google. [18]
Las métricas de rendimiento global para optimizar incluyen maximizar la utilización de la red, minimizar los tiempos de finalización del flujo de tráfico, maximizar el tráfico entregado antes de plazos específicos y reducir los tiempos de finalización de los flujos. [19] El trabajo sobre la WAN privada posterior analiza el modelado del enrutamiento como un problema de optimización de gráficos al empujar todas las colas a los puntos finales. Los autores también proponen una heurística para resolver el problema de manera eficiente mientras se sacrifica un rendimiento insignificante. [20]
Para eliminar los puntos calientes de la red, ... un algoritmo de enrutamiento de dos fases. Esto implica que cada paquete se envíe primero a un destino intermedio elegido aleatoriamente; desde el destino intermedio se reenvía a su destino final. Este algoritmo, conocido como enrutamiento universal, está diseñado para maximizar la capacidad y minimizar el retraso en condiciones de carga pesada.
