El uso compartido de procesadores generalizados ( GPS ) es un algoritmo de programación ideal para programadores de procesos y programadores de red . Está relacionado con el principio de cola justa que agrupa los paquetes en clases y comparte la capacidad de servicio entre ellos. El GPS comparte esta capacidad según unos pesos fijos . [1]
En la programación de procesos, el GPS es "un algoritmo de programación idealizado que logra una equidad perfecta. Todos los programadores prácticos se aproximan al GPS y lo utilizan como referencia para medir la equidad". [2]
El uso compartido generalizado de procesadores asume que el tráfico es fluido ( tamaños de paquete infinitesimales ) y se puede dividir arbitrariamente. Hay varias disciplinas de servicios que rastrean el rendimiento del GPS bastante de cerca, como las colas equitativas ponderadas (WFQ), [3] también conocidas como uso compartido de procesador generalizado paquete por paquete (PGPS).
Justificación
En una red como Internet, los diferentes tipos de aplicaciones requieren diferentes niveles de rendimiento. Por ejemplo, el correo electrónico es un tipo de aplicación de almacenamiento y reenvío genuino , pero la videoconferencia no lo es, ya que requiere baja latencia . Cuando los paquetes se colocan en cola en un extremo de un enlace congestionado, el nodo generalmente tiene cierta libertad para decidir el orden en el que debe enviar los paquetes en cola. Un ejemplo de ordenación es simplemente por orden de llegada, que funciona bien si el tamaño de las colas es pequeño, pero puede generar problemas si hay paquetes sensibles a la latencia bloqueados por paquetes de aplicaciones con mayor ancho de banda y ráfagas.
Detalles
En GPS, un programador que maneja los flujos (también llamados "clases" o "sesiones") se configura con un peso para cada flujo. Entonces, el GPS asegura que, considerando un flujo, y algún intervalo de tiempo tal que el flujo está continuamente atrasada en este intervalo ( es decir, la cola nunca está vacía), luego, para cualquier otro flujo, la siguiente relación se cumple
dónde denota la cantidad de bits del flujo hizo salida en el intervalo .
Entonces, se puede probar que cada flujo recibirá al menos una tarifa
dónde es la tasa del servidor. [1]
Esta es una tarifa mínima. Si algún flujo no usa su ancho de banda durante algún período, esta capacidad restante es compartida por los flujos activos con respecto a sus respectivos pesos. Por ejemplo, considere un servidor GPS con. El primer flujo recibirá al menos la mitad de la capacidad, mientras que los otros dos solo obtendrán 1/4 . Sin embargo, si en algún intervalo de tiempo, solo el segundo y tercer flujo están activos, recibirán cada uno la mitad de la capacidad.
Implementaciones, parametrización y equidad
En GPS, y en todos los protocolos inspirados en GPS, la elección de los pesos se deja al administrador de la red.
El uso compartido de procesadores generalizado asume que el tráfico es fluido, es decir, infinitamente divisible, de modo que siempre que un tipo de aplicación tenga paquetes en la cola, recibirá exactamente la fracción del servidor dada por la fórmula anterior. Sin embargo, el tráfico no es fluido y consta de paquetes, posiblemente de tamaños variables. Por lo tanto, el GPS es principalmente una idea teórica, y se han desarrollado varios algoritmos de programación para aproximarse a este ideal de GPS: PGPS, también conocido como cola equitativa ponderada , es la implementación más conocida del GPS, pero tiene algunos inconvenientes, y se han propuesto varias otras implementaciones. , como Round Robin de Déficit o WF2Q. [4]
El GPS se considera un ideal justo y todas sus aproximaciones "lo utilizan como referencia para medir la equidad". [2] No obstante, existen varias medidas de equidad .
El GPS es insensible a los tamaños de los paquetes, ya que asume un modelo fluido.
Ver también
Referencias
- ^ a b Parekh, AK; Gallager, RG (1993). "Un enfoque de uso compartido de procesador generalizado para el control de flujo en redes de servicios integrados: el caso de un solo nodo" (PDF) . Transacciones IEEE / ACM sobre redes . 1 (3): 344. doi : 10.1109 / 90.234856 .
- ^ a b Iluminado.; Baumberger, D .; Hahn, S. (2009). "Programación justa de multiprocesador eficiente y escalable utilizando round robin ponderado distribuido" (PDF) . Avisos ACM SIGPLAN . 44 (4): 65. CiteSeerX 10.1.1.567.2170 . doi : 10.1145 / 1594835.1504188 .
- ^ Demers, A .; Keshav, S .; Shenker, S. (1989). "Análisis y simulación de un algoritmo de colas justas". Revisión de comunicación informática ACM SIGCOMM . 19 (4): 1. doi : 10.1145 / 75247.75248 .
- ^ Bennett, JCR; Hui Zhang (1996). "WF / sup 2 / Q: colas equitativas ponderadas en el peor de los casos". Actas de IEEE INFOCOM '96. Conferencia sobre Comunicaciones Informáticas . 1 . pag. 120. doi : 10.1109 / INFCOM.1996.497885 . ISBN 978-0-8186-7293-4.