El enrutamiento 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 redes de circuitos conmutados , como la red telefónica pública conmutada (PSTN), y 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 de reenvío de paquetes específicos. 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 uso general también reenvían paquetes y realizan enrutamiento, aunque no cuentan con hardware especialmente optimizado para esta tarea.
El proceso de enrutamiento generalmente dirige el reenvío basándose en tablas de enrutamiento . Las tablas de enrutamiento mantienen un registro de las rutas a varios destinos de la red. Un administrador puede especificar las tablas de enrutamiento, aprenderlas observando el tráfico de la red o crearlas 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 supone que las direcciones de red están estructuradas y que 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 (puente). El enrutamiento se ha convertido en la forma dominante de direccionamiento en Internet. El puente todavía se utiliza ampliamente en las redes de área local .
Los esquemas de enrutamiento difieren en cómo entregan los mensajes:
Unicast es la forma dominante de entrega de mensajes en Internet. Este artículo se centra en los algoritmos de enrutamiento de unidifusión.
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 alternativas si la ruta más directa se bloquea (ver enrutamiento en PSTN ).
El enrutamiento dinámico intenta resolver este problema construyendo tablas de enrutamiento automáticamente, 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. El enrutamiento dinámico domina Internet. 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).
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 resulta 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, 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í) constituye la tabla de enrutamiento o tabla de distancias ). Cada nodo, de forma regular, envía a cada nodo vecino su propia evaluación actual del coste 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 siguiente salto y el mejor coste total para todos los destinos.
Cuando un nodo de la red cae, cualquier nodo que lo haya utilizado como siguiente salto descarta la entrada y transmite 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 inactivo.
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 puede conectarse. Luego, cada nodo reúne de forma independiente esta información en un mapa. Usando este mapa, cada enrutador determina de forma independiente la ruta de menor costo desde sí mismo a 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 hacia ese nodo. Este árbol sirve luego 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 (OLSR) optimizado. [2] OLSR es proactivo; Utiliza mensajes de saludo y control de topología (TC) para descubrir y difundir información sobre el estado del enlace a través de la red móvil ad hoc. Al utilizar mensajes de saludo, 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 pueden usarse en 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 del estado del enlace necesita importantes recursos 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 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 llama nodo altavoz. El nodo altavoz crea una tabla de enrutamiento y la anuncia a los nodos altavoces vecinos en sistemas autónomos vecinos. La idea es la misma que el enrutamiento por vector de distancia, excepto que solo los nodos de altavoz en cada sistema autónomo pueden comunicarse entre sí. El nodo altavoz 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 fronterizo anuncia los destinos que puede alcanzar 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 lleva 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 hacia ese destino, de ahí el nombre, enrutamiento ruta-vector; 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 ruta a múltiples rutas para seleccionar (o predecir) la mejor ruta. La mayoría de los algoritmos de enrutamiento utilizan sólo una ruta de red a la vez. El enrutamiento de múltiples rutas y, específicamente, las técnicas de enrutamiento de múltiples rutas de igual costo permiten el uso de múltiples rutas alternativas.
En las redes de computadoras, la métrica se calcula mediante un algoritmo de enrutamiento y puede cubrir información como ancho de banda , retraso de la red , recuento de saltos , costo de la ruta, carga, unidad de transmisión máxima , 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 usar alguna heurística externa para seleccionar entre rutas aprendidas de diferentes protocolos de enrutamiento. Los enrutadores Cisco , por ejemplo, atribuyen un valor conocido como distancia administrativa a cada ruta, donde distancias administrativas más pequeñas indican rutas aprendidas de un protocolo que se supone es más confiable.
Un administrador local puede configurar rutas específicas del host que proporcionen más control sobre el uso de la red, permitan pruebas y mejor seguridad general. Esto es ú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 algunos otros sistemas pequeños, cualquier dispositivo periférico que inserte 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 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 abordaron esto con la conmutación de circuitos estableciendo una ruta una vez para el primer paquete entre un origen y un destino; Los paquetes posteriores entre ese mismo origen y ese mismo destino continúan siguiendo el mismo camino sin volver a calcular hasta que se desmonta el circuito . Posteriormente, los sistemas de alta velocidad inyectan paquetes en la red sin que ningún dispositivo calcule 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 siquiera cómo están conectados todos los dispositivos entre sí, y mucho menos calcular una ruta completa a través de ellos. Estos sistemas generalmente utilizan enrutamiento del 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 particular, ese dispositivo siempre elige la misma ruta hacia 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 origen original 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 encamina una ruta a un destino intermedio elegido aleatoriamente y desde allí a 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 varias etapas .
Dependiendo de la aplicación para la cual se realiza la selección de ruta, se pueden usar diferentes métricas. Por ejemplo, para solicitudes web se pueden utilizar 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 rutas 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. [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, múltiples entidades participan 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, que pueden entrar en conflicto con los objetivos de otros participantes.
Un ejemplo clásico es el del tráfico en un sistema de carreteras, en el que cada conductor elige un camino 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 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 guiados automáticamente (AGV) en una terminal, se hacen 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 sensible al 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 su red. El enrutamiento ocurre en múltiples niveles. Primero, las rutas de nivel AS se seleccionan mediante el protocolo BGP que produce una secuencia de AS a través de la cual fluyen los paquetes. Cada AS puede tener múltiples rutas, ofrecidas por los AS vecinos, entre 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 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 única a nivel de enrutador, es una práctica común que cada ISP emplee enrutamiento de patata caliente : 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 , conectado por un enlace rápido con latencia.5 ms , y cada uno tiene presencia en Londres conectado 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 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.
Además, se puede observar un desafío de enrutamiento similar en las redes celulares, donde diferentes paquetes están destinados 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, varias entidades independientes, una para cada estación base, desempeñan un papel crucial en la selección de rutas mientras se esfuerzan por optimizar el rendimiento general de la red. [11]
Un estudio de medición de rutas de Internet realizado en 2003 encontró que, entre pares de ISP vecinos, más del 30% de las rutas tienen una latencia inflada debido al enrutamiento de patatas calientes, 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 BGP de un mecanismo para optimizar directamente la latencia, en lugar de políticas de enrutamiento egoístas. También se sugirió que, si existiera un mecanismo apropiado, los ISP estarían dispuestos a cooperar para reducir la latencia en lugar de utilizar el enrutamiento de patatas calientes. [12] Este mecanismo fue publicado posteriormente por los mismos autores, 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 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 causan una degradación del rendimiento, fluctuaciones o tiempo de inactividad no deseados. El seguimiento del enrutamiento en una red se logra mediante herramientas y técnicas de análisis de rutas . [15]
En redes donde está disponible un control lógicamente centralizado sobre el estado de reenvío, por ejemplo, utilizando 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 Global WAN de Microsoft, [16] Express Backbone 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 posterior 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. [20]
Para eliminar 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 al azar;
desde el destino intermedio se reenvía hasta su destino final.
Este algoritmo, denominado enrutamiento universal, está diseñado para maximizar la capacidad y minimizar el retraso en condiciones de carga pesada.
