Enrutamiento de contrapresión
En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el algoritmo de enrutamiento de contrapresión es un método para dirigir el tráfico alrededor de una red de colas que logra el máximo rendimiento de la red, [1] que se establece utilizando conceptos de deriva de Lyapunov . El enrutamiento de contrapresión considera la situación en la que cada trabajo puede visitar múltiples nodos de servicio en la red. Es una extensión de la programación de peso máximo donde cada trabajo visita solo un nodo de servicio único.
El enrutamiento de contrapresión es un algoritmo para enrutar dinámicamente el tráfico a través de una red de saltos múltiples mediante el uso de gradientes de congestión. El algoritmo se puede aplicar a redes de comunicación inalámbricas, incluidas redes de sensores , redes móviles ad hoc ( MANETS ) y redes heterogéneas con componentes inalámbricos y alámbricos. [2] [3]
Los principios de contrapresión también se pueden aplicar a otras áreas, como el estudio de sistemas de ensamblaje de productos y redes de procesamiento. [4] Este artículo se centra en las redes de comunicación, donde llegan paquetes de múltiples flujos de datos y deben entregarse a los destinos apropiados. El algoritmo de contrapresión opera en tiempo ranurado. Cada intervalo de tiempo busca enrutar los datos en direcciones que maximicen la acumulación diferencialentre nodos vecinos. Esto es similar a cómo fluye el agua a través de una red de tuberías a través de gradientes de presión. Sin embargo, el algoritmo de contrapresión se puede aplicar a redes de productos múltiples (donde diferentes paquetes pueden tener diferentes destinos) y a redes donde las velocidades de transmisión se pueden seleccionar de un conjunto de opciones (posiblemente variables en el tiempo). Las características atractivas del algoritmo de contrapresión son: (i) conduce al máximo rendimiento de la red, (ii) es demostrablemente resistente a las condiciones de la red que varían en el tiempo, (iii) se puede implementar sin conocer las tasas de llegada del tráfico o las probabilidades del estado del canal. Sin embargo, el algoritmo puede introducir grandes retrasos y puede ser difícil de implementar exactamente en redes con interferencia. Las modificaciones de la contrapresión que reducen la demora y simplifican la implementación se describen a continuación enMejora del retardo y la contrapresión distribuida .
El enrutamiento de contrapresión se ha estudiado principalmente en un contexto teórico. En la práctica, las redes inalámbricas ad hoc generalmente han implementado métodos de enrutamiento alternativos basados en cálculos de la ruta más corta o inundación de la red, como enrutamiento de vector de distancia bajo demanda Ad Hoc (AODV), enrutamiento geográfico y enrutamiento extremadamente oportunista (ExOR). Sin embargo, las propiedades de optimización matemática de la contrapresión han motivado demostraciones experimentales recientes de su uso en bancos de pruebas inalámbricos en la Universidad del Sur de California y en la Universidad Estatal de Carolina del Norte. [5] [6] [7]
El algoritmo de contrapresión original fue desarrollado por Tassiulas y Ephremides. [2] Consideraron una red de radio por paquetes de múltiples saltos con llegadas aleatorias de paquetes y un conjunto fijo de opciones de selección de enlaces. Su algoritmo constaba de una etapa de selección de enlace de peso máximo y una etapa de enrutamiento de acumulación diferencial . En Awerbuch y Leighton se desarrolló un algoritmo relacionado con la contrapresión, diseñado para calcular flujos de red de múltiples productos básicos. [8] El algoritmo de contrapresión fue posteriormente ampliado por Neely, Modiano y Rohrs para tratar la programación de redes móviles. [9] La contrapresión se analiza matemáticamente a través de la teoría de la deriva de Lyapunov, y se puede usar junto con mecanismos de control de flujo para proporcionar la maximización de la utilidad de la red. [10] [11] [3] [12] [13] (ver también Contrapresión con optimización de utilidad y minimización de penalización ).
El enrutamiento de contrapresión está diseñado para tomar decisiones que (aproximadamente) minimizan la suma de los cuadrados de los retrasos en la cola en la red de un intervalo de tiempo al siguiente. El desarrollo matemático preciso de esta técnica se describe en secciones posteriores. En esta sección se describe el modelo de red general y el funcionamiento del enrutamiento de contrapresión con respecto a este modelo.
