Backpressure routing

In queueing theory, a discipline within the mathematical theory of probability, the backpressure routing algorithm is a method for directing traffic around a queueing network that achieves maximum network throughput,^[1] which is established using concepts of Lyapunov drift. Backpressure routing considers the situation where each job can visit multiple service nodes in the network. It is an extension of max-weight scheduling where each job visits only a single service node.

Backpressure routing is an algorithm for dynamically routing traffic over a multi-hop network by using congestion gradients. The algorithm can be applied to wireless communication networks, including sensor networks, mobile ad hoc networks (MANETS), and heterogeneous networks with wireless and wireline components.^[2][3]

Backpressure principles can also be applied to other areas, such as to the study of product assembly systems and processing networks.^[4] This article focuses on communication networks, where packets from multiple data streams arrive and must be delivered to appropriate destinations. The backpressure algorithm operates in slotted time. Every time slot it seeks to route data in directions that maximize the differential backlog between neighboring nodes. This is similar to how water flows through a network of pipes via pressure gradients. However, the backpressure algorithm can be applied to multi-commodity networks (where different packets may have different destinations), and to networks where transmission rates can be selected from a set of (possibly time-varying) options. Attractive features of the backpressure algorithm are: (i) it leads to maximum network throughput, (ii) it is provably robust to time-varying network conditions, (iii) it can be implemented without knowing traffic arrival rates or channel state probabilities. However, the algorithm may introduce large delays, and may be difficult to implement exactly in networks with interference. Modifications of backpressure that reduce delay and simplify implementation are described below under Improving delay and Distributed backpressure.

El enrutamiento por contrapresión se ha estudiado principalmente en un contexto teórico. En la práctica, las redes inalámbricas ad hoc han implementado típicamente métodos de enrutamiento alternativos basados ​​en cálculos de ruta más corta o inundación de red, como el enrutamiento por vector de distancia ad hoc bajo demanda (AODV), el enrutamiento geográfico y el enrutamiento extremadamente oportunista (ExOR). Sin embargo, las propiedades matemáticas de optimalidad de la contrapresión han motivado recientes demostraciones experimentales 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 consistió en una etapa de selección de enlaces de peso máximo y una etapa de enrutamiento de backlog diferencial . Un algoritmo relacionado con la contrapresión, diseñado para calcular flujos de red de múltiples productos, fue desarrollado en Awerbuch y Leighton. ^[8] El algoritmo de contrapresión fue ampliado posteriormente 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 utilizar junto con mecanismos de control de flujo para proporcionar maximización de la utilidad de la red. ^{[10] [11] [3] [12] [13]} (véase también Contrapresión con optimización de la utilidad y minimización de penalizaciones).

El enrutamiento por contrapresión está diseñado para tomar decisiones que minimicen (aproximadamente) la suma de los cuadrados de los retrasos en la cola de la red de un intervalo de tiempo al siguiente. El desarrollo matemático preciso de esta técnica se describe en secciones posteriores. Esta sección describe el modelo general de red y el funcionamiento del enrutamiento por contrapresión con respecto a este modelo.

Considere una red de múltiples saltos con N nodos (vea la Fig. 1 para un ejemplo con N  = 6). La red opera en tiempo ranurado . En cada ranura, pueden llegar nuevos datos a la red, y se toman decisiones de enrutamiento y programación de transmisión en un esfuerzo por entregar todos los datos a su destino adecuado. Deje que los datos que están destinados al nodo se etiqueten como datos de producto c . Los datos en cada nodo se almacenan de acuerdo con su producto. Para y , sea la cantidad actual de datos de producto c en el nodo n , también llamado el backlog de la cola . Un primer plano de los backlogs de la cola dentro de un nodo se muestra en la Fig. 2. Las unidades de dependen del contexto del problema. Por ejemplo, el backlog puede tomar unidades enteras de paquetes , lo cual es útil en casos en que los datos se segmentan en paquetes de longitud fija. Alternativamente, puede tomar unidades de valor real de bits . Se supone que para todos y cada uno de los intervalos de tiempo t , porque ningún nodo almacena datos destinados a sí mismo. En cada intervalo de tiempo, los nodos pueden transmitir datos a otros. Los datos que se transmiten de un nodo a otro se eliminan de la cola del primer nodo y se agregan a la cola del segundo. Los datos que se transmiten a su destino se eliminan de la red. Los datos también pueden llegar de forma exógena a la red y se definen como la cantidad de datos nuevos que llegan al nodo n en la ranura t y que finalmente deben entregarse al nodo c . ${\displaystyle t\in \{0,1,2,\ldots \}}$${\displaystyle c\en \{1,\puntos ,N\}}$${\displaystyle n\en \{1,\ldots ,N\}}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$$Estilo de visualización A_{n}^{(c)}(t)}$

Sea la tasa de transmisión utilizada por la red sobre el enlace ( a , b ) en la ranura t , que representa la cantidad de datos que puede transferir del nodo a al nodo b en la ranura actual. Sea la matriz de tasa de transmisión. Estas tasas de transmisión deben seleccionarse dentro de un conjunto de opciones que pueden variar en el tiempo. Específicamente, la red puede tener canales y movilidad de nodos que varían en el tiempo, y esto puede afectar sus capacidades de transmisión en cada ranura. Para modelar esto, sea S ( t ) el estado de topología de la red, que captura las propiedades de la red en la ranura t que afectan la transmisión. Sea el conjunto de opciones de matriz de tasa de transmisión disponibles en el estado de topología S ( t ). En cada ranura t , el controlador de red observa S ( t ) y elige tasas de transmisión dentro del conjunto . La elección de qué matriz seleccionar en cada ranura t se describe en la siguiente subsección. $Estilo de visualización: mu_ab(t)$${\displaystyle (\mu_{ab}(t))}$$Estilo de visualización: Gamma__{S(t)}$${\displaystyle (\mu_{ab}(t))}$$Estilo de visualización: Gamma__{S(t)}$${\displaystyle (\mu_{ab}(t))}$

Este modelo de red variable en el tiempo se desarrolló por primera vez para el caso en el que las tasas de transmisión en cada ranura t se determinaban mediante funciones generales de una matriz de estado del canal y una matriz de asignación de potencia. ^[9] El modelo también se puede utilizar cuando las tasas se determinan mediante otras decisiones de control, como la asignación de servidores, la selección de subbandas, el tipo de codificación, etc. Supone que se conocen las tasas de transmisión compatibles y que no hay errores de transmisión. Se pueden utilizar formulaciones extendidas de enrutamiento de contrapresión para redes con errores de canal probabilísticos, incluidas las redes que explotan la ventaja de la transmisión inalámbrica a través de la diversidad de múltiples receptores . ^[1]

En cada ranura t el controlador de contrapresión observa S ( t ) y realiza los 3 pasos siguientes:

• En primer lugar, para cada enlace ( a , b ), selecciona un producto óptimo para utilizar.$estilo de visualización c_{ab}^{opt}(t)}$
• A continuación, determina qué matriz utilizar.${\displaystyle (\mu_{ab}(t))}$$Estilo de visualización: Gamma__{S(t)}$
• Por último, determina la cantidad de mercancía que se transmitirá a través del enlace ( a , b ) (siendo como máximo , pero posiblemente sea menos en algunos casos).$estilo de visualización c_{ab}^{opt}(t)}$$Estilo de visualización: mu_ab(t)$

Cada nodo a observa sus propios retrasos en la cola y los retrasos en sus vecinos actuales. Un vecino actual del nodo a es un nodo b tal que es posible elegir una tasa de transmisión distinta de cero en la ranura actual. Por lo tanto, los vecinos están determinados por el conjunto . En el caso extremo, un nodo puede tener todos los N  − 1 otros nodos como vecinos. Sin embargo, es común usar conjuntos que excluyan las transmisiones entre nodos que están separados por más de una cierta distancia geográfica, o que tendrían una intensidad de señal propagada por debajo de un cierto umbral. Por lo tanto, es típico que el número de vecinos sea mucho menor que N  − 1. El ejemplo en la Fig. 1 ilustra vecinos por conexiones de enlace, de modo que el nodo 5 tiene vecinos 4 y 6. El ejemplo sugiere una relación simétrica entre vecinos (de modo que si 5 es un vecino de 4, entonces 4 es un vecino de 5), pero este no tiene por qué ser el caso en general. $Estilo de visualización: mu_ab(t)$$Estilo de visualización: Gamma__{S(t)}$$Estilo de visualización: Gamma__{S(t)}$

El conjunto de vecinos de un nodo determinado determina el conjunto de enlaces salientes que puede utilizar para la transmisión en el intervalo actual. Para cada enlace saliente ( a , b ), el producto óptimo se define como el producto que maximiza la siguiente cantidad de retraso diferencial : $estilo de visualización c_{ab}^{opt}(t)}$${\displaystyle c\in \{1,\ldots ,N\}}$

${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$

Cualquier empate en la elección del producto óptimo se rompe arbitrariamente.

En la figura 2 se muestra un ejemplo. El ejemplo supone que cada cola tiene actualmente solo 3 productos: rojo , verde y azul , y estos se miden en unidades enteras de paquetes. Centrándose en el enlace dirigido (1,2), los retrasos diferenciales son:

${\displaystyle Q_{1}^{({\text{rojo}})}(t)-Q_{2}^{({\text{rojo}})}(t)=1}$

${\displaystyle Q_{1}^{({\text{verde}})}(t)-Q_{2}^{({\text{verde}})}(t)=2}$

${\displaystyle Q_{1}^{({\text{azul}})}(t)-Q_{2}^{({\text{azul}})}(t)=-1}$

Por lo tanto, el producto óptimo para enviar a través del enlace (1,2) en la ranura t es el producto verde. Por otro lado, el producto óptimo para enviar a través del enlace inverso (2,1) en la ranura t es el producto azul.

Una vez determinados los productos óptimos para cada enlace ( a , b ), el controlador de red calcula los siguientes pesos : $Estilo de visualización W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max \left[Q_{a}^{(c_{ab}^{\mathrm {opt} }(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0\right]}$

El peso es el valor del retraso diferencial asociado con el producto óptimo para el enlace ( a , b ), con un máximo de 0. Luego, el controlador elige las velocidades de transmisión como la solución al siguiente problema de peso máximo (deshaciendo los empates arbitrariamente): $Estilo de visualización W_{ab}(t)}$

${\displaystyle {\text{(Ec. 1)}}\qquad {\text{Maximizar: }}\sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle {\text{(Ec. 2)}}\qquad {\text{Sujeto a: }}(\mu _{ab}(t))\in \Gamma _{S(t)}}$

Como ejemplo de la decisión de peso máximo, supongamos que en la ranura actual t , los retrasos diferenciales en cada enlace de la red de 6 nodos conducen a pesos de enlace dados por: $Estilo de visualización W_{ab}(t)}$

${\displaystyle (W_{ab}(t))=\left[{\begin{array}{cccccc}0&2&1&1&6&0\\1&0&1&2&5&6\\0&7&0&0&0&0\\1&0&1&0&0&0\\1&0&7&5&0&0\\0&0&0&0&5&0\end{array}}\right]}$

Si bien el conjunto puede contener un número infinito e incontable de posibles matrices de velocidad de transmisión, supongamos, para simplificar, que el estado actual de la topología admite solo cuatro opciones posibles: $Estilo de visualización: Gamma__{S(t)}$

${\displaystyle \Gamma _{S(t)}=\{{\boldsymbol {\mu }}_{a},{\boldsymbol {\mu }}_{b},{\boldsymbol {\mu }}_{c},{\boldsymbol {\mu }}_{d}\}}$

Ilustración de las 4 posibles selecciones de velocidad de transmisión en el estado topológico actual S ( t ). La opción (a) activa el enlace único (1,5) con una velocidad de transmisión de . Todas las demás opciones utilizan dos enlaces, con velocidades de transmisión de 1 en cada uno de los enlaces activados. ${\displaystyle \mu_{15}=2}$

Estas cuatro posibilidades están representadas en forma matricial por:

${\displaystyle {\boldsymbol {\mu }}_{a}=\left[{\begin{array}{cccccc}0&0&0&0&2&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{b}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&1&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]}$

${\displaystyle {\boldsymbol {\mu }}_{c}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{d}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\end{array}}\right]}$

Observe que el nodo 6 no puede enviar ni recibir en ninguna de estas posibilidades. Esto puede deberse a que el nodo 6 se encuentra actualmente fuera del rango de comunicación. La suma ponderada de las velocidades para cada una de las 4 posibilidades es:

• Opción (a): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$
• Opción (b): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• Opción (c): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• Opción (d): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$

Como hay un empate por el peso máximo de 12, el controlador de red puede romper el empate arbitrariamente eligiendo la opción u opción . ${\displaystyle {\boldsymbol {\mu }}_{a}}$${\displaystyle {\boldsymbol {\mu }}_{d}}$

Supongamos ahora que se han determinado los productos óptimos para cada enlace y también se han determinado las tasas de transmisión. Si el retraso diferencial para el producto óptimo en un enlace determinado ( a , b ) es negativo, entonces no se transfieren datos a través de este enlace en el intervalo actual. De lo contrario, la red ofrece enviar unidades de datos de productos a través de este enlace. Esto se hace definiendo variables de enrutamiento para cada enlace ( a , b ) y cada producto c , donde: ${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{\mathrm {opt} }(t)}$ ${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle \mu _{ab}^{(c)}(t)={\begin{cases}\mu _{ab}(t)&{\text{ if }}c=c_{ab}^{opt}(t){\text{ and }}Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t)\geq 0\\0&{\text{ otherwise}}\end{cases}}}$

El valor de representa la velocidad de transmisión ofrecida a los datos del producto c a través del enlace ( a , b ) en la ranura t . Sin embargo, los nodos podrían no tener suficiente cantidad de un determinado producto para soportar la transmisión a las velocidades ofrecidas en todos sus enlaces salientes. Esto se produce en la ranura t para el nodo n y el producto c si: ${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle Q_{n}^{(c)}(t)<\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)}$

En este caso, se envían todos los datos y se utilizan datos nulos para llenar las porciones no utilizadas de las tasas ofrecidas, asignando los datos reales y los datos nulos de manera arbitraria en los enlaces salientes correspondientes (según las tasas ofrecidas). Esto se denomina una situación de desbordamiento de cola . Estos desbordamientos no afectan las propiedades de rendimiento o estabilidad de la red. Intuitivamente, esto se debe a que los desbordamientos solo surgen cuando el nodo transmisor tiene una cantidad baja de trabajo atrasado, lo que significa que el nodo no corre peligro de inestabilidad. ${\displaystyle Q_{n}^{(c)}(t)}$

El algoritmo de contrapresión no utiliza ninguna ruta preestablecida. Las rutas se aprenden dinámicamente y pueden ser diferentes para distintos paquetes. El retraso puede ser muy grande, en particular cuando el sistema está ligeramente cargado, de modo que no hay suficiente presión para impulsar los datos hacia el destino. Como ejemplo, supongamos que un paquete ingresa a la red y nunca ingresa nada más. Este paquete puede dar un paseo en bucle por la red y nunca llegar a su destino porque no se acumulan gradientes de presión. Esto no contradice las propiedades de estabilidad o optimización del rendimiento de la contrapresión porque la red tiene como máximo un paquete en cualquier momento y, por lo tanto, es trivialmente estable (logra una tasa de entrega de 0, igual a la tasa de llegada).

También es posible implementar contrapresión en un conjunto de rutas preespecificadas. Esto puede restringir la región de capacidad, pero podría mejorar la entrega en orden y el retraso. Otra forma de mejorar el retraso, sin afectar la región de capacidad, es usar una versión mejorada que sesgue los pesos de los enlaces hacia las direcciones deseadas. ^[9] Las simulaciones de dicho sesgo han mostrado mejoras significativas en el retraso. ^{[1] [3]} Tenga en cuenta que la contrapresión no requiere el servicio Primero en entrar, primero en salir ( FIFO ) en las colas. Se ha observado que el servicio Último en entrar, primero en salir ( LIFO ) puede mejorar drásticamente el retraso para la gran mayoría de los paquetes, sin afectar el rendimiento. ^{[7] [14]}

Tenga en cuenta que una vez que se han seleccionado las tasas de transmisión, las variables de decisión de enrutamiento se pueden calcular de una manera distribuida simple, donde cada nodo solo requiere conocimiento de los diferenciales de acumulación de cola entre él mismo y sus vecinos. Sin embargo, la selección de las tasas de transmisión requiere una solución al problema de peso máximo en las ecuaciones (1)-(2). En el caso especial en que los canales son ortogonales, el algoritmo tiene una implementación distribuida natural y se reduce a decisiones separadas en cada nodo. Sin embargo, el problema de peso máximo es un problema de control centralizado para redes con interferencia entre canales. También puede ser muy difícil de resolver incluso de manera centralizada. ${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}^{(c)}(t)}$

Un enfoque distribuido para redes de interferencia con tasas de enlace que están determinadas por la relación señal-ruido-más-interferencia (SINR) se puede llevar a cabo utilizando aleatorización. ^[9] Cada nodo decide aleatoriamente transmitir cada ranura t (transmitiendo un paquete "nulo" si actualmente no tiene un paquete para enviar). Las tasas de transmisión reales, y los paquetes reales correspondientes para enviar, se determinan mediante un protocolo de enlace de 2 pasos: En el primer paso, los nodos transmisores seleccionados aleatoriamente envían una señal piloto con una intensidad de señal proporcional a la de una transmisión real. En el segundo paso, todos los nodos receptores potenciales miden la interferencia resultante y envían esa información de vuelta a los transmisores. Los niveles de SINR para todos los enlaces salientes ( n , b ) son entonces conocidos por todos los nodos n , y cada nodo n puede decidir sus variables y en función de esta información. El rendimiento resultante no es necesariamente óptimo. Sin embargo, el proceso de transmisión aleatoria puede considerarse como parte del proceso de estado del canal (siempre que se envíen paquetes nulos en casos de desbordamiento, de modo que el proceso de estado del canal no dependa de decisiones anteriores). Por lo tanto, el rendimiento resultante de esta implementación distribuida es óptimo para la clase de todos los algoritmos de enrutamiento y programación que utilizan dichas transmisiones aleatorias. ${\displaystyle \mu _{nb}(t)}$${\displaystyle (\mu _{nb}^{(c)}(t))}$

Las implementaciones distribuidas alternativas se pueden agrupar en dos clases: la primera clase de algoritmos considera aproximaciones de factores multiplicativos constantes al problema de peso máximo y produce resultados de rendimiento de factores constantes. La segunda clase de algoritmos considera aproximaciones aditivas al problema de peso máximo, basadas en la actualización de soluciones al problema de peso máximo a lo largo del tiempo. Los algoritmos de esta segunda clase parecen requerir condiciones de canal estático y tiempos de convergencia más largos (a menudo no polinómicos), aunque pueden lograr un rendimiento máximo demostrable bajo supuestos apropiados. ^{[15] [4] [13]} Las aproximaciones aditivas suelen ser útiles para demostrar la optimalidad de la contrapresión cuando se implementan con información de la lista de espera de la cola desactualizada (consulte el Ejercicio 4.10 del texto de Neely). ^[13]

Esta sección muestra cómo el algoritmo de contrapresión surge como una consecuencia natural de minimizar con avidez un límite en el cambio en la suma de cuadrados de los retrasos en la cola de un espacio al siguiente. ^{[9] [3]}

Considere una red de múltiples saltos con N nodos, como se describe en la sección anterior. En cada intervalo t , el controlador de red observa el estado de la topología S ( t ) y elige las velocidades de transmisión y las variables de enrutamiento sujetas a las siguientes restricciones: ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 3)}}\qquad (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle {\text{(Eq. 4)}}\qquad 0\leq \mu _{ab}^{(c)}(t)\qquad \forall a,b,c,\forall t}$

${\displaystyle {\text{(Eq. 5)}}\qquad \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)\leq \mu _{ab}(t)\qquad \forall (a,b),\forall t}$

Una vez que se determinan estas variables de enrutamiento, se realizan transmisiones (utilizando relleno inactivo si es necesario) y las colas atrasadas resultantes satisfacen lo siguiente:

${\displaystyle {\text{(Eq. 6)}}\qquad Q_{n}^{(c)}(t+1)\leq \max \left[Q_{n}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t),0\right]+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)+A_{n}^{(c)}(t)}$

donde es la cantidad aleatoria de nuevos datos del producto c que llegan exógenamente al nodo n en la ranura t , y es la tasa de transmisión asignada al tráfico del producto c en el enlace ( n , b ) en la ranura t . Nótese que puede ser mayor que la cantidad de datos del producto c que se transmiten realmente en el enlace ( a , b ) en la ranura t . Esto se debe a que puede no haber suficiente retraso en el nodo n . Por esta misma razón, la ecuación (6) es una desigualdad, en lugar de una igualdad, porque puede ser mayor que las llegadas endógenas reales del producto c al nodo n en la ranura t . Una característica importante de la ecuación (6) es que se mantiene incluso si las variables de decisión se eligen independientemente de los retrasos en la cola. ${\displaystyle A_{n}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \sum _{a=1}^{N}\mu _{an}^{(c)}(t)}$${\displaystyle \mu _{ab}^{(c)}(t)}$

Se supone que para todas las ranuras t y todas , ninguna cola almacena datos destinados a sí misma. ${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$

Defina como la matriz de los retrasos actuales en la cola la siguiente función no negativa, denominada función de Lyapunov : ${\displaystyle {\boldsymbol {Q}}(t)=(Q_{n}^{(c)}(t))}$

${\displaystyle L(t)={\frac {1}{2}}\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)^{2}}$

Esta es una suma de los cuadrados de los retrasos en la cola (multiplicada por 1/2 solo para conveniencia en análisis posteriores). La suma anterior es lo mismo que sumar todos los n , c de manera que porque para todos y todas las ranuras${\displaystyle n\neq c}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$ t .

La deriva de Lyapunov condicional se define: ${\displaystyle \Delta (t)}$

${\displaystyle \Delta (t)=E\left[L(t+1)-L(t)\mid {\boldsymbol {Q}}(t)\right]}$

Nótese que la siguiente desigualdad se cumple para todos los , , : ${\displaystyle q\geq 0}$${\displaystyle a\geq 0}$${\displaystyle b\geq 0}$

${\displaystyle (\max[q-b,0]+a)^{2}\leq q^{2}+b^{2}+a^{2}+2q(a-b)}$

Al elevar al cuadrado la ecuación de actualización de cola (Ec. (6)) y usar la desigualdad anterior, no es difícil demostrar que para todas las ranuras t y bajo cualquier algoritmo para elegir variables de transmisión y enrutamiento y : ^[3]${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 7)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

donde B es una constante finita que depende de los segundos momentos de llegada y de los segundos momentos máximos posibles de las tasas de transmisión.

El algoritmo de contrapresión está diseñado para observar y S ( t ) cada ranura t y elegir y minimizar el lado derecho del límite de deriva de la ecuación (7). Debido a que B es una constante y son constantes, esto equivale a maximizar: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$${\displaystyle \lambda _{n}^{(c)}}$

${\displaystyle E\left[\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]|{\boldsymbol {Q}}(t)\right]}$

donde las sumas finitas se han introducido a través de las expectativas para iluminar la decisión de maximización. Por el principio de maximizar oportunistamente una expectativa , la expectativa anterior se maximiza maximizando la función dentro de ella (dada la observada , ). Por lo tanto, se elige y se sujeta a las restricciones de las ecuaciones (3)-(5) para maximizar: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle S(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]}$

No resulta inmediatamente evidente qué decisiones maximizan lo anterior. Esto se puede aclarar cambiando las sumas. De hecho, la expresión anterior es la misma que la siguiente:

${\displaystyle \sum _{a=1}^{N}\sum _{b=1}^{N}\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]}$

El peso se denomina diferencial actual de atraso del producto c entre los nodos a y b . La idea es elegir las variables de decisión de modo de maximizar la suma ponderada anterior, donde los pesos son diferenciales de atraso. Intuitivamente, esto significa asignar tasas más altas en direcciones de mayor diferencial de atraso. ${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

Claramente, se debe elegir siempre que . Además, dado para un enlace particular , no es difícil demostrar que las selecciones óptimas, sujetas a las ecuaciones (3)-(5), se determinan de la siguiente manera: primero, encuentre el producto que maximiza el atraso diferencial para el enlace ( a , b ). Si el atraso diferencial maximizador es negativo para el enlace ( a , b ), asigne para todos los productos en el enlace ( a , b ). De lo contrario, asigne la tasa completa del enlace al producto , y la tasa cero a todos los demás productos en este enlace. Con esta elección, se deduce que: ${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)<0}$${\displaystyle \mu _{ab}(t)}$${\displaystyle (a,b)}$${\displaystyle \mu _{ab}^{(c)}(t)}$${\displaystyle c_{ab}^{opt}(t)\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{opt}(t)}$

${\displaystyle \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]=\mu _{ab}(t)W_{ab}(t)}$

¿Dónde está el atraso diferencial del producto óptimo para el enlace ( a , b ) en la ranura t (maximizado con 0): ${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max[Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0]}$

Solo queda elegir . Esto se hace resolviendo lo siguiente: ${\displaystyle (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle \mathrm {Maximize:} \sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle \mathrm {Subjectto:} (\mu _{ab}(t))\in \Gamma _{S(t)}}$

El problema anterior es idéntico al problema de peso máximo de las ecuaciones (1)-(2). El algoritmo de contrapresión utiliza las decisiones de peso máximo para y luego elige las variables de enrutamiento a través del retraso diferencial máximo como se describió anteriormente. ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

Una propiedad notable del algoritmo de contrapresión es que actúa con avidez cada ranura t basándose únicamente en el estado de topología observado S ( t ) y en los retrasos en la cola para esa ranura. Por lo tanto, no requiere conocimiento de las tasas de llegada ni de las probabilidades del estado de topología . ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \pi _{S}=Pr[S(t)=S]}$

Esta sección demuestra la optimización del rendimiento del algoritmo de contrapresión. ^{[3] [13]} Para simplificar, se considera el escenario en el que los eventos son independientes y se distribuyen de manera idéntica (iid) en los intervalos, aunque se puede demostrar que el mismo algoritmo funciona en escenarios no iid (consulte a continuación Operación no iid y programación universal).

Sea la matriz de llegadas exógenas en la ranura t . Supongamos que esta matriz es independiente y está distribuida de manera idéntica (iid) sobre ranuras con segundos momentos finitos y con medias: ${\displaystyle (A_{n}^{(c)}(t))}$

${\displaystyle \lambda _{n}^{(c)}=E\left[A_{n}^{(c)}(t)\right]}$

Se supone que para todo , como no llegan datos que estén destinados a sí mismos, la matriz de tasas de llegada es, por tanto, una matriz de números reales no negativos, con ceros en la diagonal. ${\displaystyle \lambda _{c}^{(c)}=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle N\times N}$

Supongamos que el estado de topología S ( t ) es iid sobre ranuras con probabilidades (si S ( t ) toma valores en un conjunto incontablemente infinito de vectores con entradas de valor real, entonces es una distribución de probabilidad, no una función de masa de probabilidad). Un algoritmo general para la red observa S ( t ) cada ranura t y elige las tasas de transmisión y las variables de enrutamiento de acuerdo con las restricciones de las ecuaciones (3)-(5). La región de capacidad de la red es el cierre del conjunto de todas las matrices de tasa de llegada para las que existe un algoritmo que estabiliza la red. La estabilidad de todas las colas implica que la tasa total de entrada de tráfico a la red es la misma que la tasa total de datos entregados a su destino. Se puede demostrar que para cualquier matriz de tasa de llegada en la región de capacidad , hay un algoritmo estacionario y aleatorio que elige las variables de decisión y cada ranura t basándose únicamente en S ( t ) (y, por lo tanto, independientemente de los retrasos en la cola) que produce lo siguiente para todos : ^{[9] [13]}${\displaystyle \pi _{S}=Pr[S(t)=S]}$${\displaystyle \pi _{S}}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$ ${\displaystyle \Lambda }$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 8)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq 0}$

Un algoritmo estacionario y aleatorio de este tipo que basa las decisiones únicamente en S ( t ) se denomina algoritmo S-only . A menudo es útil suponer que es interior a , de modo que existe un tal que , donde es 1 si , y cero en caso contrario. En ese caso, existe un algoritmo S -only que produce lo siguiente para todos los : ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$${\displaystyle (\lambda _{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda }$${\displaystyle 1_{n}^{(c)}}$${\displaystyle n\neq c}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 9)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq -\epsilon }$

Como requisito técnico, se supone que los segundos momentos de las tasas de transmisión son finitos bajo cualquier algoritmo para elegir estas tasas. Esto se cumple trivialmente si hay una tasa máxima finita . ${\displaystyle \mu _{ab}(t)}$${\displaystyle \mu _{max}}$

Como el algoritmo de contrapresión observa y S ( t ) cada ranura t y elige decisiones para minimizar el lado derecho del límite de deriva de la ecuación (7), tenemos: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 10)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

donde y son todas las decisiones alternativas que satisfacen las ecuaciones (3)-(5), incluidas las decisiones aleatorias. ${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$

Supongamos ahora que existe un algoritmo S -only que satisface la ecuación (8). Si introducimos esto en el lado derecho de la ecuación (10) y observamos que la expectativa condicional dada en este algoritmo S -only es la misma que la expectativa incondicional (porque S ( t ) es iid sobre ranuras y el algoritmo S -only es independiente de los retrasos actuales en la cola), obtenemos: ${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$${\displaystyle {\boldsymbol {Q}}(t)}$

${\displaystyle \Delta (t)\leq B\,}$

Por lo tanto, la deriva de una función de Lyapunov cuadrática es menor o igual a una constante B para todos los intervalos t . Este hecho, junto con el supuesto de que las llegadas a la cola tienen segundos momentos acotados, implica lo siguiente para todas las colas de la red: ^[16]

${\displaystyle \lim _{t\rightarrow \infty }{\frac {Q_{n}^{(c)}(t)}{t}}=0{\text{ with probability 1}}}$

Para una mejor comprensión del tamaño promedio de la cola, se puede suponer que las tasas de llegada son interiores a , por lo que existe un tal que la ecuación (9) se cumple para algún algoritmo alternativo de solo S. Al introducir la ecuación (9) en el lado derecho de la ecuación (10), se obtiene: ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$

${\displaystyle \Delta (t)\leq B-\epsilon \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)}$

de lo cual se obtiene inmediatamente (ver ^{[3] [13]} ):

${\displaystyle \limsup _{t\rightarrow \infty }{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{n=1}^{N}\sum _{c=1}^{N}E\left[Q_{n}^{(c)}(\tau )\right]\leq {\frac {B}{\epsilon }}}$

Este límite de tamaño de cola promedio aumenta a medida que la distancia hasta el límite de la región de capacidad se acerca a cero. Este es el mismo rendimiento cualitativo que una cola única M/M/1 con una tasa de llegada y una tasa de servicio , donde el tamaño de cola promedio es proporcional a , donde . ${\displaystyle \epsilon }$${\displaystyle \Lambda }$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle 1/\epsilon }$${\displaystyle \epsilon =\mu -\lambda }$

El análisis anterior asume propiedades iid para simplificar. Sin embargo, se puede demostrar que el mismo algoritmo de contrapresión funciona de manera robusta en situaciones que no son iid. Cuando los procesos de llegada y los estados de topología son ergódicos pero no necesariamente iid, la contrapresión aún estabiliza el sistema siempre que . ^[9] De manera más general, utilizando un enfoque de programación universal , se ha demostrado que ofrece propiedades de estabilidad y optimalidad para trayectorias de muestra arbitrarias (posiblemente no ergódicas). ^[17]${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$

Se ha demostrado que la contrapresión funciona junto con el control de flujo a través de una técnica de deriva más penalización . ^{[10] [11] [3]} Esta técnica maximiza con avidez una suma de deriva y una expresión de penalización ponderada. La penalización se pondera mediante un parámetro V que determina una compensación de rendimiento. Esta técnica garantiza que la utilidad de rendimiento esté dentro de O (1/ V ) de la optimalidad mientras que el retraso promedio es O ( V ). Por lo tanto, la utilidad se puede empujar arbitrariamente cerca de la optimalidad, con una compensación correspondiente en el retraso promedio. Se pueden mostrar propiedades similares para la minimización de potencia promedio ^[18] y para la optimización de atributos de red más generales. ^[13]

Se han desarrollado algoritmos alternativos para estabilizar colas mientras se maximiza la utilidad de una red utilizando análisis de modelos de fluidos, ^[12] análisis de fluidos conjuntos y análisis de multiplicadores de Lagrange, ^[19] optimización convexa, ^[20] y gradientes estocásticos. ^[21] Estos enfoques no proporcionan los resultados de utilidad-retardo O (1/ V ), O ( V ).

• AODV
• Enrutamiento por contrapresión de diversidad (DIVBAR) ^[1]
• Deriva más penalización
• ExOR
• Enrutamiento geográfico
• Lista de protocolos de enrutamiento ad hoc
• Optimización de Lyapunov

• L. Tassiulas y A. Ephremides, "Propiedades de estabilidad de sistemas de colas restringidas y políticas de programación para un rendimiento máximo en redes de radio de múltiples saltos", IEEE Transactions on Automatic Control , vol. 37, núm. 12, págs. 1936–1948, diciembre de 1992.
• L. Georgiadis, MJ Neely y L. Tassiulas, "Asignación de recursos y control entre capas en redes inalámbricas", Foundations and Trends in Networking , vol. 1, núm. 1, págs. 1–149, 2006.
• MJ Neely. Optimización de redes estocásticas con aplicación a sistemas de comunicación y colas , Morgan & Claypool, 2010.