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.

Introducción

El enrutamiento de contrapresión es un algoritmo para enrutar dinámicamente el tráfico a través de una red de múltiples saltos mediante el uso de gradientes de congestión. El algoritmo se puede aplicar a redes de comunicación inalámbrica, 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 al 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 adecuados. El algoritmo de contrapresión funciona en un tiempo ranurado. En cada intervalo de tiempo busca enrutar los datos en direcciones que maximicen el retraso diferencial entre los nodos vecinos. Esto es similar a cómo el agua fluye a través de una red de tuberías mediante gradientes de presión. Sin embargo, el algoritmo de contrapresión se puede aplicar a redes de múltiples productos (donde diferentes paquetes pueden tener diferentes destinos) y a redes donde las velocidades de transmisión se pueden seleccionar entre un conjunto de opciones (posiblemente variables en el tiempo). Las características atractivas del algoritmo de contrapresión son: (i) conduce a un rendimiento máximo de la red, (ii) es demostrablemente robusto a las condiciones de la red que varían en el tiempo, (iii) se puede implementar sin conocer las tasas de llegada de tráfico o las probabilidades de estado del canal. Sin embargo, el algoritmo puede introducir grandes retrasos y puede resultar difícil de implementar exactamente en redes con interferencias. Las modificaciones de la contrapresión que reducen el retraso y simplifican la implementación se describen a continuación en Mejora del retraso y 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 ruta más corta o inundaciones de red, como el enrutamiento por vector de distancia bajo demanda (AODV) ad hoc, el enrutamiento geográfico y el enrutamiento extremadamente oportunista (ExOR). Sin embargo, las propiedades de optimización matemática 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]}

Orígenes

El algoritmo de contrapresión original fue desarrollado por Tassiulas y Efrémides. ^[2] Consideraron una red de radio de paquetes de múltiples saltos con llegadas de paquetes aleatorias y un conjunto fijo de opciones de selección de enlaces. Su algoritmo consistía en una etapa de selección de enlace de peso máximo y una etapa de enrutamiento diferencial del trabajo pendiente . En Awerbuch y Leighton se desarrolló un algoritmo relacionado con la contrapresión, diseñado para calcular flujos de redes de múltiples productos. ^[8] Neely, Modiano y Rohrs ampliaron posteriormente el algoritmo de contrapresión para tratar la programación de redes móviles. ^[9] La contrapresión se analiza matemáticamente mediante la teoría de la deriva de Lyapunov y se puede utilizar junto con mecanismos de control de flujo para maximizar la utilidad de la red. ^{[10] [11] [3] [12] [13]} (ver también Contrapresión con optimización de utilidad y minimización de penalizaciones).

Cómo funciona

El enrutamiento de contrapresión está diseñado para tomar decisiones que (aproximadamente) minimicen la suma de cuadrados de las colas atrasadas en 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 de red general y el funcionamiento del enrutamiento de contrapresión con respecto a este modelo.

El modelo de red de colas de múltiples saltos

Fig. 1: Una red multisalto de 6 nodos. Las flechas entre los nodos ilustran los vecinos actuales.

Considere una red de múltiples saltos con N nodos (consulte la Fig. 1 para ver un ejemplo con N  = 6). La red opera en horarios diferenciados . En cada ranura, pueden llegar nuevos datos a la red y se toman decisiones de programación de enrutamiento y transmisión en un esfuerzo por entregar todos los datos a su destino adecuado. Deje que los datos destinados al nodo se etiqueten como datos del producto c . Los datos en cada nodo se almacenan de acuerdo con su producto. Para y , sea la cantidad actual de datos del producto c en el nodo n , también llamado retraso en la cola . En la Fig. 2 se muestra un primer plano de los retrasos en la cola dentro de un nodo. Las unidades dependen del contexto del problema. Por ejemplo, el trabajo pendiente puede tomar unidades enteras de paquetes , lo cual resulta útil en casos en los que los datos se segmentan en paquetes de longitud fija. Alternativamente, puede tomar unidades de bits de valor real . 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 eventualmente deben entregarse al nodo c . ${\displaystyle t\in \{0,1,2,\ldots \}}$ ${\displaystyle c\in \{1,\dots ,N\}}$ ${\displaystyle n\in \{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\}}$ ${\displaystyle A_{n}^{(c)}(t)}$

Sea la velocidad de transmisión utilizada por la red a través del 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 tasas de transmisión. Estas velocidades de transmisión deben seleccionarse dentro de un conjunto de opciones que posiblemente varían en el tiempo. Específicamente, la red puede tener canales variables en el tiempo y movilidad de nodos, y esto puede afectar sus capacidades de transmisión en cada intervalo. 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. Representemos el conjunto de opciones de matriz de velocidad 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 las velocidades de transmisión dentro del conjunto . La elección de qué matriz seleccionar en cada ranura t se describe en la siguiente subsección. ${\displaystyle \mu _{ab}(t)}$ ${\displaystyle (\mu _{ab}(t))}$ ${\displaystyle \Gamma _{S(t)}}$ ${\displaystyle (\mu _{ab}(t))}$ ${\displaystyle \Gamma _{S(t)}}$ ${\displaystyle (\mu _{ab}(t))}$

Este modelo de red variable en el tiempo se desarrolló por primera vez para el caso en que las velocidades de transmisión en cada ranura t estaban determinadas por funciones generales de una matriz de estado de canal y una matriz de asignación de potencia. ^[9] El modelo también se puede utilizar cuando las tarifas están determinadas por otras decisiones de control, como la asignación de servidores, la selección de subbandas, el tipo de codificación, etc. Se supone que se conocen las velocidades de transmisión soportables 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 redes que explotan la ventaja de la transmisión inalámbrica a través de la diversidad de múltiples receptores . ^[1]

Las decisiones de control de contrapresión.

Cada ranura t del controlador de contrapresión observa S ( t ) y realiza los siguientes 3 pasos:

• Primero, para cada enlace ( a , b ), selecciona un producto óptimo para usar. ${\displaystyle c_{ab}^{opt}(t)}$
• A continuación, determina qué matriz utilizar. ${\displaystyle (\mu _{ab}(t))}$ ${\displaystyle \Gamma _{S(t)}}$
• Finalmente, determina la cantidad de producto que transmitirá a través del enlace ( a , b ) (siendo como máximo , pero posiblemente menos en algunos casos). ${\displaystyle c_{ab}^{opt}(t)}$ ${\displaystyle \mu _{ab}(t)}$

Elegir el producto óptimo

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 velocidad de transmisión distinta de cero en la ranura actual. Por 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 utilizar conjuntos que impiden transmisiones entre nodos que están separados por más de una determinada 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 de la Fig. 1 ilustra los vecinos por conexiones de enlace, de modo que el nodo 5 tiene los vecinos 4 y 6. El ejemplo sugiere una relación simétrica entre vecinos ( de modo que si 5 es vecino de 4, entonces 4 es vecino de 5), pero este no tiene por qué ser el caso en general. ${\displaystyle \mu _{ab}(t)}$ ${\displaystyle \Gamma _{S(t)}}$ ${\displaystyle \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 la ranura actual. Para cada enlace saliente ( a , b ), el producto óptimo se define como el producto que maximiza la siguiente cantidad diferencial de cartera de pedidos : ${\displaystyle c_{ab}^{opt}(t)}$ ${\displaystyle c\in \{1,\ldots ,N\}}$

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

Cualquier vínculo en la elección del producto óptimo se rompe arbitrariamente.

Fig. 2: Un primer plano de los nodos 1 y 2. El producto óptimo para enviar a través del enlace (1,2) es el producto verde. El producto óptimo para enviar en la otra dirección (a través del enlace (2,1)) es el producto azul.

En la Fig. 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ándonos en el enlace dirigido (1,2), los backlogs diferenciales son:

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

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

${\displaystyle Q_{1}^{({\text{blue}})}(t)-Q_{2}^{({\text{blue}})}(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.

Elección de la matriz μ _ab ( t )

Una vez que se han determinado los productos óptimos para cada enlace ( a , b ), el controlador de red calcula los siguientes pesos : ${\displaystyle 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 ), máximo con 0. Luego, el controlador elige las velocidades de transmisión como solución al siguiente problema de peso máximo (rompiendo vínculos arbitrariamente): ${\displaystyle W_{ab}(t)}$

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

${\displaystyle {\text{(Eq. 2)}}\qquad {\text{Subject to: }}(\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: ${\displaystyle 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 por simplicidad que el estado actual de la topología admite solo 4 opciones posibles: ${\displaystyle \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 bajo el estado de topología 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 bajo ninguna de estas posibilidades. Esto podría deberse a que el nodo 6 se encuentra actualmente fuera del alcance de comunicación. La suma ponderada de tarifas 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}$

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

Finalizando las variables de enrutamiento

Supongamos ahora que se han determinado los productos óptimos para cada enlace y que también se han determinado las velocidades 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 la ranura actual. De lo contrario, la red ofrece enviar unidades de datos sobre productos básicos 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, es posible que los nodos no tengan suficiente cantidad de un determinado producto para soportar la transmisión a las tarifas ofrecidas en todos sus enlaces salientes. Esto surge 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 los datos nulos se utilizan para completar las partes no utilizadas de las tarifas ofrecidas, asignando los datos reales y los datos nulos de forma arbitraria entre los enlaces salientes correspondientes (según las tarifas ofrecidas). Esto se denomina situación de desbordamiento de cola . Estos desbordamientos no afectan el rendimiento ni las propiedades de estabilidad de la red. Intuitivamente, esto se debe a que los desbordamientos solo surgen cuando el nodo transmisor tiene una cantidad baja de atrasos, lo que significa que el nodo no está en peligro de inestabilidad. ${\displaystyle Q_{n}^{(c)}(t)}$

Mejorando el retraso

El algoritmo de contrapresión no utiliza rutas preespecificadas. Las rutas se aprenden dinámicamente y pueden ser diferentes para distintos paquetes. El retraso puede ser muy grande, particularmente cuando el sistema tiene poca carga, por lo que no hay suficiente presión para enviar datos hacia el destino. Como ejemplo, supongamos que un paquete ingresa a la red y nunca ingresa nada más. Este paquete puede realizar un recorrido sinuoso a través de la red y nunca llegar a su destino porque no se acumulan gradientes de presión. Esto no contradice la optimización del rendimiento o las propiedades de estabilidad de la contrapresión porque la red tiene como máximo un paquete en cualquier momento y, por lo tanto, es trivialmente estable (logrando 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 de pedidos y los retrasos. Otra forma de mejorar el retraso, sin afectar la región de capacidad, es utilizar una versión mejorada que sesgue las ponderaciones de los enlaces hacia direcciones deseables. ^[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 de la gran mayoría de los paquetes, sin afectar el rendimiento. ^{[7] [14]}

Contrapresión distribuida

Tenga en cuenta que una vez que se han seleccionado las velocidades 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 velocidades de transmisión requiere una solución al problema del peso máximo en las Ecs. (1)-(2). En el caso especial en el 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 del peso máximo es un problema de control centralizado para redes con interferencia entre canales. También puede resultar muy difícil de resolver incluso de forma centralizada. ${\displaystyle (\mu _{ab}(t))}$ ${\displaystyle \mu _{ab}^{(c)}(t)}$

Se puede llevar a cabo mediante aleatorización un enfoque distribuido para redes de interferencia con velocidades de enlace determinadas por la relación señal-ruido más interferencia (SINR). ^[9] Cada nodo decide aleatoriamente transmitir cada ranura t (transmitiendo un paquete "nulo" si actualmente no tiene un paquete para enviar). Las velocidades de transmisión reales y los paquetes reales correspondientes a 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 a los transmisores. Los niveles SINR para todos los enlaces salientes ( n , b ) son 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 verse como parte del proceso de estado del canal (siempre que se envíen paquetes nulos en casos de desbordamiento insuficiente, de modo que el proceso de estado del canal no dependa de decisiones pasadas). Por lo tanto, el rendimiento resultante de esta implementación distribuida es óptimo sobre 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 aproximadamente en dos clases: la primera clase de algoritmos considera aproximaciones de factor multiplicativo constante al problema de peso máximo y produce resultados de rendimiento de factor constante. La segunda clase de algoritmos considera aproximaciones aditivas al problema de peso máximo, basadas en la actualización de las 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 polinomiales), aunque es probable que puedan alcanzar el máximo rendimiento bajo los supuestos apropiados. ^{[15] [4] [13]} Las aproximaciones aditivas suelen ser útiles para demostrar la optimización de la contrapresión cuando se implementan con información desactualizada de la acumulación de colas (consulte el ejercicio 4.10 del texto de Neely). ^[13]

Construcción matemática mediante la deriva de Lyapunov

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]}

Controlar las restricciones de decisión y la ecuación de actualización de la cola.

Considere una red de múltiples saltos con N nodos, como se describe en la sección anterior. En cada ranura t , el controlador de red observa el estado de topología S ( t ) y elige velocidades de transmisión y 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 las transmisiones (utilizando el relleno inactivo si es necesario) y los retrasos en la cola 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 velocidad de transmisión asignada al tráfico del producto c en el enlace ( n , b ) en la ranura t . Tenga en cuenta que puede ser mayor que la cantidad de datos del producto c que realmente se transmiten en el enlace ( a , b ) en la ranura t . Esto se debe a que es posible que no haya suficiente trabajo pendiente en el nodo n . Por esta misma razón, la Ec. (6) es una desigualdad, más que una igualdad, porque puede ser mayor que las llegadas endógenas reales del bien c al nodo n en la ranura t . Una característica importante de la ecuación. (6) es que se cumple 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 all , ya que ninguna cola almacena datos destinados a sí misma. ${\displaystyle Q_{c}^{(c)}(t)=0}$ ${\displaystyle c\in \{1,\ldots ,N\}}$

Deriva de Lyapunov

Definir como la matriz de los retrasos en la cola actuales. Defina la siguiente función no negativa, llamada 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 las colas (multiplicada por 1/2 solo por conveniencia en análisis posteriores). La suma anterior es lo mismo que sumar todos los n , c tales 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 condicional de Lyapunov se define: ${\displaystyle \Delta (t)}$

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

Tenga en cuenta que la siguiente desigualdad es válida para todos , , : ${\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 la 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 llegadas y de los segundos segundos máximos posibles de velocidades de transmisión.

Minimizar el límite de deriva cambiando las sumas

El algoritmo de contrapresión está diseñado para observar y S ( t ) cada ranura t y elegir y minimizar el lado derecho de la ecuación límite de deriva. (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 han sido empujadas a través de las expectativas para iluminar la decisión maximizadora. Según el principio de maximizar oportunistamente una expectativa , la expectativa anterior se maximiza maximizando la función dentro de ella (dado lo observado , ). Por lo tanto, se elige y sujeto a las restricciones de las Ecs. (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 es inmediatamente obvio qué decisiones maximizan lo anterior. Esto se puede iluminar 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 acumulación diferencial actual del producto c entre los nodos a y b . La idea es elegir variables de decisión para maximizar la suma ponderada anterior, donde las ponderaciones son atrasos diferenciales. Intuitivamente, esto significa asignar tasas más altas en direcciones de mayor cartera diferencial de cartera. ${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$ ${\displaystyle (\mu _{ab}^{(c)}(t))}$

Es evidente que uno debe elegir cuando sea . Además, dado un vínculo particular , no es difícil demostrar que las selecciones óptimas, sujetas a las Ecs. (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 de maximización es negativo para el enlace ( a , b ), asigne para todos los productos en el enlace ( a , b ). De lo contrario, asigne la tasa de enlace completa al producto básico 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]}$

Sólo 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 del peso máximo en las Ecs. (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 describe anteriormente. ${\displaystyle (\mu _{ab}(t))}$ ${\displaystyle (\mu _{ab}^{(c)}(t))}$

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

Análisis de rendimiento

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

Llegadas dinámicas

Sea la matriz de llegadas exógenas en la ranura t . Supongamos que esta matriz es independiente y está distribuida idénticamente (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 todos , ya que no llega ningún dato que esté destinado a sí mismo. Por tanto, la matriz de tasas de llegada es 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}$

Región de capacidad de red

Suponga que el estado de topología S ( t ) es iid sobre ranuras con probabilidades (si S ( t ) toma valores en un conjunto infinito e incontable de vectores con entradas de valores reales, entonces es una distribución de probabilidad, no una función de masa de probabilidad). Un algoritmo general para la red observa S ( t ) en cada ranura t y elige velocidades de transmisión y 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 tasas 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 , existe un algoritmo estacionario y aleatorio que elige 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 que basa las decisiones únicamente en S ( t ) se denomina algoritmo solo S. A menudo es útil suponer que es interior a , de modo que existe tal que , donde es 1 si y cero en caso contrario. En ese caso, existe un algoritmo solo S que produce lo siguiente para todos : ${\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 velocidades de transmisión son finitos bajo cualquier algoritmo para elegir estas velocidades. Esto se cumple trivialmente si existe una tasa máxima finita . ${\displaystyle \mu _{ab}(t)}$ ${\displaystyle \mu _{max}}$

Comparando con algoritmos solo S

Debido a que el algoritmo de contrapresión observa y S ( t ) cada ranura t y elige decisiones y para minimizar el lado derecho del límite de deriva, 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 decisiones alternativas que satisfagan las ecuaciones. (3)-(5), incluidas decisiones aleatorias. ${\displaystyle (\mu _{ab}^{*}(t))}$ ${\displaystyle (\mu _{ab}^{*(c)}(t))}$

Ahora supongamos . Entonces existe un algoritmo sólo S que satisface la ecuación. (8). Conectando esto al lado derecho de la Ec. (10) y observando que la expectativa condicional dada bajo este algoritmo solo S es la misma que la expectativa incondicional (porque S ( t ) es iid sobre ranuras, y el algoritmo solo S es independiente de los retrasos en la cola actuales) produce: ${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$ ${\displaystyle {\boldsymbol {Q}}(t)}$

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

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

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

Para comprender mejor el tamaño promedio de la cola, se puede suponer que las tasas de llegada son interiores a , por lo que existe una ecuación tal que (9) es válido para algún algoritmo alternativo sólo S. Ecuación de conexión. (9) en el lado derecho de la ecuación. (10) produce: ${\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 donde 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 al límite de la región de capacidad llega a cero. Este es el mismo rendimiento cualitativo que una única cola M/M/1 con tasa de llegada y tasa de servicio , donde el tamaño promedio de la cola es proporcional a , donde . ${\displaystyle \epsilon }$ ${\displaystyle \Lambda }$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle 1/\epsilon }$ ${\displaystyle \epsilon =\mu -\lambda }$

Extensiones de la formulación anterior.

Operación no iid y programación universal

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

Contrapresión con optimización de utilidad y minimización de penalizaciones.

Se ha demostrado que la contrapresión funciona junto con el control de flujo mediante 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 está ponderada por un parámetro V que determina una compensación de desempeño. Esta técnica garantiza que el rendimiento de la utilidad esté dentro de O (1/ V ) del nivel óptimo, mientras que el retraso promedio es O ( V ). Por lo tanto, la utilidad puede llevarse arbitrariamente cerca de la optimización, con la correspondiente contrapartida en el retraso promedio. Se pueden mostrar propiedades similares para la minimización de la potencia promedio ^[18] y para la optimización de atributos de red más generales. ^[13]

Se han desarrollado algoritmos alternativos para estabilizar colas y maximizar la utilidad de la 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 retardo de la utilidad O (1/ V ), O ( V ).

Ver también

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

Referencias

1. MJ Neely y R. Urgaonkar, "Enrutamiento óptimo de contrapresión en redes inalámbricas con diversidad de receptores múltiples", Ad Hoc Networks (Elsevier), vol. 7, núm. 5, págs. 862-881, julio de 2009.
2. 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, no. 12, págs. 1936-1948, diciembre. 1992.
3. L. Georgiadis, MJ Neely y L. Tassiulas, "Asignación de recursos y control entre capas en redes inalámbricas", Fundamentos y tendencias en redes , vol. 1, núm. 1, págs. 1-149, 2006.
4. L. Jiang y J. Walrand. Programación y control de congestión para redes inalámbricas y de procesamiento , Morgan & Claypool, 2010.
5. A. Sridharan, S. Moeller y B. Krishnamachari, "Hacer del control de velocidad distribuida utilizando Lyapunov Drifts una realidad en las redes de sensores inalámbricos", 6th Intl. Simposio sobre modelado y optimización en redes móviles, ad hoc e inalámbricas (WiOpt), abril de 2008.
6. A. Warrier, S. Janakiraman, S. Ha e I. Rhee, "DiffQ: control práctico de congestión diferencial para redes inalámbricas", Proc. IEEE INFOCOM, Río de Janeiro, Brasil, 2009.
7. S. Moeller, A. Sridharan, B. Krishnamachari y O. Gnawali, "Enrutamiento sin rutas: el protocolo de recolección de contrapresión", Proc. 9.° ACM/IEEE Internacional. Conf. sobre procesamiento de información en redes de sensores (IPSN) , abril de 2010.
8. B. Awerbuch y T. Leighton, "Un algoritmo de aproximación de control local simple para el flujo de múltiples productos", Proc. 34ª Conferencia IEEE. sobre Fundamentos de la Informática, octubre de 1993.
9. MJ Neely, E. Modiano y CE Rohrs, "Asignación dinámica de energía y enrutamiento para redes inalámbricas que varían en el tiempo", IEEE Journal on Selected Areas in Communications , vol. 23, núm. 1, págs. 89-103, enero de 2005.
10. MJ Neely. Asignación dinámica de energía y enrutamiento para redes satelitales e inalámbricas con canales variables en el tiempo. Doctor. Disertación, Instituto de Tecnología de Massachusetts, LIDS. Noviembre de 2003.
11. MJ Neely, E. Modiano y C. Li, "Equidad y control estocástico óptimo para redes heterogéneas", Proc. IEEE INFOCOM, marzo de 2005.
12. A. Stolyar, "Maximización de la utilidad de la red de colas sujeta a la estabilidad: algoritmo dual primario codicioso", Sistemas de colas , vol. 50, núm. 4, págs. 401-457, 2005.
13. MJ Neely. Optimización estocástica de redes con aplicación a sistemas de comunicación y colas, Morgan & Claypool, 2010.
14. L. Huang, S. Moeller, MJ Neely y B. Krishnamachari, "La contrapresión LIFO logra una compensación casi óptima entre la utilidad y el retraso", Proc. WiOpt, mayo de 2011.
15. E. Modiano, D. Shah y G. Zussman, "Maximizar el rendimiento en redes inalámbricas mediante chismes", Proc. ACM SIGMETRICA, 2006.
16. MJ Neely, "Convergencia de estabilidad y probabilidad de cola 1 mediante optimización de Lyapunov", Journal of Applied Mathematics, vol. 2012, doi :10.1155/2012/831909.
17. MJ Neely, "Programación universal para redes con tráfico, canales y movilidad arbitrarios", Proc. Conferencia IEEE. sobre Decisión y Control (CDC) , Atlanta, GA, diciembre de 2010.
18. MJ Neely, "Control óptimo de energía para redes inalámbricas que varían en el tiempo", IEEE Transactions on Information Theory , vol. 52, núm. 7, págs. 2915-2934, julio de 2006
19. A. Eryilmaz y R. Srikant, "Asignación justa de recursos en redes inalámbricas mediante programación basada en la longitud de la cola y control de congestión", Proc. IEEE INFOCOM, marzo de 2005.
20. X. Lin y NB Shroff, "Programación y control de velocidad conjunta en redes inalámbricas de múltiples saltos", Proc. de la 43ª Conferencia IEEE. sobre Decisión y Control, Paradise Island, Bahamas, diciembre de 2004.
21. JW Lee, RR Mazumdar y NB Shroff, "Programación de energía oportunista para sistemas inalámbricos dinámicos multiservidor", IEEE Transactions on Wireless Communications , vol. 5, núm. 6, págs. 1506-1515, junio de 2006.

Fuentes primarias

• 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", Fundamentos y tendencias en redes , vol. 1, núm. 1, págs. 1–149, 2006.
• MJ Neely. Optimización estocástica de redes con aplicación a sistemas de comunicación y colas , Morgan & Claypool, 2010.