Programación proporcional y justa

Algoritmo de programación de red de datos

La programación proporcional-justa es un algoritmo de programación basado en compromisos . Se basa en mantener un equilibrio entre dos intereses en competencia: tratar de maximizar el rendimiento total de la red (cableada o no) y, al mismo tiempo, permitir a todos los usuarios al menos un nivel mínimo de servicio. Esto se hace asignando a cada flujo de datos una velocidad de datos o una prioridad de programación (según la implementación) que es inversamente proporcional a su consumo de recursos previsto. ^{[1] [2]}

Colas justas ponderadas

La programación proporcionalmente justa se puede lograr mediante colas justas ponderadas (WFQ), estableciendo los pesos de programación para el flujo de datos en , donde el costo es la cantidad de recursos consumidos por bit de datos. Por ejemplo: ${\displaystyle i}$ ${\displaystyle w_{i}=1/c_{i}}$ ${\displaystyle c_{i}}$

• En las redes celulares de espectro ensanchado CDMA , el costo puede ser la energía requerida por bit en el control de potencia de transmisión (el mayor nivel de interferencia).
• En las comunicaciones inalámbricas con adaptación de enlaces , el coste puede ser el tiempo necesario para transmitir una determinada cantidad de bits utilizando el esquema de modulación y codificación de errores que esto requiere. Un ejemplo de esto son las redes EVDO , donde la relación señal/ruido informada se utiliza como el factor de coste principal.
• En redes inalámbricas con asignación dinámica de canales rápida , el costo puede ser la cantidad de estaciones base cercanas que no pueden usar el mismo canal de frecuencia simultáneamente, con el fin de evitar interferencias entre canales.

Priorización de usuarios

Otra forma de programar la transferencia de datos que conduce a resultados similares es mediante el uso de coeficientes de priorización. ^[3] Aquí programamos el canal para la estación que tiene el máximo de la función de prioridad:

${\displaystyle P={\frac {T^{\alpha }}{R^{\beta }}}}$

• ${\displaystyle T}$denota la velocidad de datos potencialmente alcanzable para la estación en el intervalo de tiempo actual.
• ${\displaystyle R}$es la tasa de datos promedio histórica de esta estación.
• ${\displaystyle \alpha }$y ajustar la "imparcialidad" del programador. ${\displaystyle \beta }$

Al ajustar la fórmula anterior, podemos ajustar el equilibrio entre servir a los mejores móviles (aquellos en las mejores condiciones del canal) con mayor frecuencia y servir a los móviles costosos con la suficiente frecuencia para que tengan un nivel de rendimiento aceptable. ${\displaystyle \alpha }$ ${\displaystyle \beta }$

En el caso extremo ( y ) el planificador actúa en un modo round-robin de "paquetes" y sirve a todos los móviles uno después del otro (pero no con la misma frecuencia en el tiempo), sin tener en cuenta el consumo de recursos, y de tal manera que cada usuario obtiene la misma cantidad de datos. El planificador ( y ) podría llamarse "planificador de máxima equidad" (para usarse para proporcionar igualdad en todo momento a los usuarios de voz, por ejemplo). Si y entonces el planificador siempre servirá al móvil con las mejores condiciones de canal. Esto maximizará el rendimiento del canal mientras que las estaciones con bajas no serán servidas en absoluto. El planificador ( y ) podría llamarse planificador de "velocidad máxima". ^[2] El uso de y producirá el algoritmo de programación equitativa proporcional utilizado en redes 3G. ^[3] El planificador ( y ) podría implementarse proporcionando la misma cantidad de tiempo y espectro para cada usuario, independientemente del tamaño de paquete deseado, la calidad del canal y la velocidad de datos (MCS) utilizada. El programador proporcional justo ( y ) podría llamarse "programador de esfuerzo igual" o "programador Round Robin de tiempo/espectro". ${\displaystyle \alpha =0}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =0}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =0}$ ${\displaystyle T}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =0}$ ${\displaystyle \alpha \approx 1}$ ${\displaystyle \beta \approx 1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =1}$ ${\displaystyle \alpha =1}$ ${\displaystyle \beta =1}$

Esta técnica se puede parametrizar aún más mediante el uso de una "constante de memoria" que determina el período de tiempo durante el cual se promedia la velocidad de datos de la estación utilizada para calcular la función de prioridad. Una constante mayor generalmente mejora el rendimiento a expensas de una menor equidad a corto plazo.

Véase también

• Programación (informática) : una introducción al tema general de la programación.
• Programación round-robin : un algoritmo de programación diferente.
• Regla proporcional-justa : una regla más general para seleccionar entre diferentes alternativas, basada en el mismo principio de equilibrio entre eficiencia y equidad.

Referencias

1. Kushner, HJ; Whiting, PA (julio de 2004), "Convergencia de algoritmos de reparto proporcional-justo en condiciones generales", IEEE Transactions on Wireless Communications , 3 (4): 1250–1259, CiteSeerX  10.1.1.8.6408 , doi :10.1109/TWC.2004.830826, S2CID  6780351.
2. Guowang Miao , Jens Zander, Ki Won Sung y Ben Slimane, Fundamentos de redes de datos móviles, Cambridge University Press, ISBN 1107143217 , 2016. 
3. Ji Yang; Zhang Yifan; Wang Ying; Zhang Ping (2004), "Mecanismo de actualización de la tasa promedio en el programador proporcional justo para HDR", IEEE Global Telecommunications Conference, 2004. GLOBECOM '04 , vol. 6, págs. 3464–3466, doi :10.1109/GLOCOM.2004.1379010, ISBN 0-7803-8794-5

Lectura adicional

• Andrews, Matthew (septiembre de 2004), "Inestabilidad del algoritmo de programación justa proporcional para HDR", IEEE Transactions on Wireless Communications , 3 (5): 1422–1426, CiteSeerX  10.1.1.73.4092 , doi :10.1109/TWC.2004.833419, S2CID  34595035.
• Andrews, Matthew ; Kumaran, K.; Ramanan, K.; Stoyar, A.; Whitting, Phil (febrero de 2001), "Cómo proporcionar calidad de servicio a través de un enlace inalámbrico compartido", IEEE Communications , 39 (2): 150–154, doi :10.1109/35.900644.
• Parruca, Donald; Grysla, Marius; Gortzen, Simon; Gross, James (2013), "Modelo analítico de programación proporcional justa en redes OFDMA/LTE con interferencias limitadas", 2013 IEEE 78th Vehicular Technology Conference (VTC Fall) , págs. 1–7, arXiv : 1303.1778 , Bibcode :2013arXiv1303.1778P, doi :10.1109/VTCFall.2013.6692106, ISBN 978-1-4673-6187-3, Número de identificación del sujeto  8236469