Programación proporcionalmente 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: intentar 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 (dependiendo de la implementación) que es inversamente proporcional a su consumo de recursos previsto. ^{[1] [2]}

Cola justa ponderada

Se puede lograr una programación proporcionalmente justa 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 la comunicación inalámbrica con adaptación de enlace , el costo puede ser el tiempo requerido para transmitir una cierta 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 SNR informada se utiliza como factor de coste principal.
• En redes inalámbricas con asignación dinámica de canales rápida , el costo puede ser la cantidad de sitios de estaciones base cercanas que no pueden usar el mismo canal de frecuencia simultáneamente, con el fin de evitar interferencias cocanal.

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 velocidad de datos promedio histórica de esta estación.
• ${\displaystyle \alpha }$y ajustar la "imparcialidad" del programador. ${\displaystyle \beta }$

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

En el caso extremo ( y ), el programador actúa en forma de "paquetes" y sirve a todos los móviles uno tras otro (pero no con la misma frecuencia en el tiempo), sin tener en cuenta el consumo de recursos, y de manera que cada usuario obtenga el misma cantidad de datos. El programador ( y ) podría denominarse "programador de máxima equidad" (que se utilizará para proporcionar igualdad en todo momento a los usuarios de voz, por ejemplo). En ese caso, el programador siempre servirá al móvil con las mejores condiciones de canal. Esto maximizará el rendimiento del canal mientras que las estaciones con bajo nivel no recibirán ningún servicio. El programador ( y ) podría denominarse programador de "tasa máxima". ^[2] El uso de y producirá el algoritmo de programación justa proporcional utilizado en las 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) utilizados. El programador proporcional justo ( y ) podría denominarse "programador de igual esfuerzo" 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 utilizando 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.

Ver también

• Programación (informática) : una introducción al tema general de la programación.
• Programación por turnos : 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 equilibrar la eficiencia y la equidad.

Referencias

1. Kushner, HJ; Whiting, PA (julio de 2004), "Convergencia de algoritmos de reparto proporcional y 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 las 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 tasa promedio en el programador justo proporcional para HDR", Conferencia Global de Telecomunicaciones IEEE, 2004. GLOBECOM '04 , vol. 6, págs. 3464–3466, doi :10.1109/GLOCOM.2004.1379010, ISBN 0-7803-8794-5

Otras lecturas

• 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.
• Andrés, Mateo ; Kumaran, K.; Ramanan, K.; Stoyar, A.; Whitting, Phil (febrero de 2001), "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, Simón; Gross, James (2013), "Modelo analítico de programación justa proporcional en redes OFDMA/LTE con interferencia limitada", 78.ª Conferencia de tecnología vehicular del IEEE de 2013 (otoño de VTC) , págs. 1 a 7, arXiv : 1303.1778 , Bibcode : 2013arXiv1303.1778P , doi :10.1109/VTCFall.2013.6692106, ISBN 978-1-4673-6187-3, S2CID  8236469