stringtranslate.com

Equidad máxima y mínima

En las redes de comunicación , la multiplexación y la división de recursos escasos, se dice que la equidad máxima-mínima se logra mediante una asignación si y solo si la asignación es factible y un intento de aumentar la asignación de cualquier participante necesariamente resulta en la disminución de la asignación de algún otro participante con una asignación igual o menor.

En la multiplexación estadística de mejor esfuerzo , a menudo se utiliza una política de programación por orden de llegada (FCFS). La ventaja de la equidad máxima-mínima sobre la FCFS es que da como resultado la modelación del tráfico , lo que significa que un flujo con mal comportamiento, que consiste en paquetes de datos grandes o ráfagas de muchos paquetes, solo se castigará a sí mismo y no a otros flujos. En consecuencia, se evita en cierta medida la congestión de la red .

La cola justa es un ejemplo de un algoritmo de programación justa de paquetes con un máximo y un mínimo para multiplexación estadística y redes de máximo esfuerzo, ya que otorga prioridad de programación a los usuarios que han alcanzado la tasa de datos más baja desde que se activaron. En el caso de paquetes de datos de igual tamaño, la programación round-robin es justa con un máximo y un mínimo.

Comparación con otras políticas de compartición de recursos

En general, las políticas de compartición de recursos que se caracterizan por un bajo nivel de equidad (ver medidas de equidad ) proporcionan un alto rendimiento promedio pero una baja estabilidad en la calidad del servicio, lo que significa que la calidad del servicio lograda varía en el tiempo dependiendo del comportamiento de otros usuarios. Si esta inestabilidad es grave, puede generar usuarios insatisfechos que elegirán otro servicio de comunicación más estable.

La distribución justa de recursos con un máximo y un mínimo da como resultado un mayor rendimiento promedio (o eficiencia espectral del sistema en redes inalámbricas) y una mejor utilización de los recursos que una política de distribución equitativa que conserve el trabajo . [ se necesita más explicación ] En la distribución equitativa, algunos flujos de datos pueden no ser capaces de utilizar su "participación justa" de los recursos. Una política de distribución equitativa impediría que un flujo de datos obtenga más recursos que cualquier otro flujo y que utilice recursos libres en la red.

Por otra parte, la equidad máxima-mínima proporciona un rendimiento medio menor que la gestión de recursos de rendimiento máximo , donde a los flujos menos costosos se les asigna toda la capacidad que pueden utilizar, y puede que no quede capacidad para los flujos más costosos. En una red inalámbrica, un usuario costoso suele ser una estación móvil a gran distancia de la estación base, expuesta a una alta atenuación de la señal. Sin embargo, una política de rendimiento máximo daría lugar a la inanición de los flujos costosos y podría dar lugar a menos "clientes satisfechos".

Un compromiso entre la equidad máxima-mínima y la programación de máximo rendimiento es la equidad proporcional , donde los recursos se dividen con el objetivo de lograr el mismo costo para cada usuario o minimizar el costo máximo por unidad que alcanza un flujo de datos. Los flujos de datos costosos logran una calidad de servicio inferior a otros en la equidad proporcional, pero no sufren de inanición. La equidad máxima-mínima da como resultado una calidad de servicio más estable y, por lo tanto, tal vez, más "clientes satisfechos".

Preasignación de capacidad de enlace justa máxima y mínima

La equidad máxima-mínima en las redes de comunicación supone que los recursos (capacidades de los enlaces de comunicación) se asignan a los flujos con antelación, a diferencia de las redes de mejor esfuerzo .

Consideremos flujos de datos , a veces denominados usuarios o fuentes . Cada flujo de datos tiene un nodo inicial definido, un nodo de destino y una velocidad de datos deseada. Un flujo en su camino a través de la red puede dividirse entre enlaces "paralelos", en un esquema de equilibrio de carga .

Un vector de asignación x cuya coordenada i -ésima es la asignación para el flujo i , es decir, la velocidad a la que el usuario i puede emitir datos.

Una asignación de una tasa x es “máxima-mínima justa” si y solo si un aumento de cualquier tasa dentro del dominio de asignaciones factibles debe ser a costa de una disminución de alguna tasa ya menor. Dependiendo del problema, una asignación máxima-mínima justa puede o no existir. Sin embargo, si existe, es única.

El nombre “max-min” proviene de la idea de que es la tasa de flujos más pequeños (o mínimos) que el algoritmo hace lo más grande posible (maximiza). Por lo tanto, damos mayor prioridad relativa a los flujos pequeños. Solo cuando un flujo solicita consumir más que C/N (capacidad de enlace/número de flujos) corre el riesgo de que el algoritmo limite su ancho de banda.

Enlaces de cuello de botella

Un enlace de cuello de botella para un flujo de datos i es un enlace que se utiliza por completo (está saturado ) y, de todos los flujos que comparten este enlace, el flujo de datos i alcanza la velocidad de datos máxima general. [1] Tenga en cuenta que esta definición es sustancialmente diferente de un significado común de un cuello de botella . Tenga en cuenta también que esta definición no prohíbe que un único enlace de cuello de botella se comparta entre varios flujos.

Una asignación de velocidad de datos es justa en términos máximos y mínimos si y solo si un flujo de datos entre dos nodos tiene al menos un enlace de cuello de botella.

Algoritmo de llenado progresivo

Si los recursos se asignan por adelantado en los nodos de la red, se puede obtener una equidad máxima-mínima utilizando un algoritmo de llenado progresivo. Se comienza con todas las tasas iguales a 0 y se aumentan todas las tasas juntas al mismo ritmo, hasta que se alcanzan uno o varios límites de capacidad de enlace. Las tasas para las fuentes que utilizan estos enlaces ya no se aumentan, y se continúa aumentando las tasas para otras fuentes. Todas las fuentes que se detienen tienen un enlace de cuello de botella. Esto se debe a que utilizan un enlace saturado, y todas las demás fuentes que utilizan el enlace saturado se detienen al mismo tiempo, o se detuvieron antes, por lo que tienen una tasa menor o igual. El algoritmo continúa hasta que no es posible aumentar. Por último, cuando el algoritmo termina, todas las fuentes se han detenido en algún momento y, por lo tanto, tienen un enlace de cuello de botella. Esta asignación es justa en términos máximos y mínimos.

Véase también

Referencias

  1. ^ https://web.archive.org/web/20230422115954/https://ica1www.epfl.ch/PS_files/LEB3132.pdf Jean-Yves Le Boudec (EPFL Lausana) "Adaptación de tarifas, control de la congestión y equidad: un tutorial" noviembre de 2005

Enlaces externos