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 da como resultado 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áximo-mínimo sobre FCFS es que da como resultado una configuración del tráfico , lo que significa que un flujo con mal comportamiento, que consiste en grandes paquetes de datos 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 equitativa es un ejemplo de un algoritmo de programación de paquetes equitativos máximo-mínimo para multiplexación estadística y redes de conmutación de paquetes de mejor esfuerzo , ya que otorga prioridad de programación a los usuarios que han logrado la velocidad de datos más baja desde que se activaron. En el caso de paquetes de datos de igual tamaño, la programación por turnos es justa como máximo-mínimo.
Comparación con otras políticas para compartir recursos
Generalmente, las políticas para compartir recursos que se caracterizan por un bajo nivel de equidad (ver medidas de equidad ) proporcionan un rendimiento promedio alto 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 severa, puede resultar en usuarios insatisfechos que elegirán otro servicio de comunicación más estable.
El intercambio justo de recursos máximo-mínimo da como resultado un rendimiento promedio más alto (o eficiencia espectral del sistema en redes inalámbricas) y una mejor utilización de los recursos que una política de intercambio equitativo de los recursos que conserva el trabajo . [ se necesita más explicación ] En el intercambio equitativo, es posible que algunos flujos de datos no puedan utilizar su "parte justa" de los recursos. Una política para el intercambio equitativo evitaría que un flujo de datos obtenga más recursos que cualquier otro flujo y utilice recursos gratuitos en la red.
Por otro lado, la equidad máxima-mínima proporciona un rendimiento promedio más bajo que la gestión de recursos de rendimiento máximo , donde a los flujos menos costosos se les asigna toda la capacidad que pueden usar y es posible que no quede capacidad para los flujos más costosos. En una red inalámbrica, un usuario caro es típicamente una estación móvil a una 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 flujos costosos y podría resultar en menos "clientes satisfechos".
Un compromiso entre la equidad máxima y mínima y la programación de rendimiento máximo 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 más baja que otros en equidad proporcional, pero no sufren hambre. La equidad máximo-mínimo da como resultado una calidad de servicio más estable y, por lo tanto, quizás, más "clientes satisfechos".
Asignación previa de capacidad de enlace equitativa máxima-mínima
La equidad máxima-mínima en las redes de comunicación asume que los recursos (capacidades de los enlaces de comunicación) se asignan a los flujos por adelantado, a diferencia de las redes de mejor esfuerzo .
Considere i los 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 i -ésima coordenada 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 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 justa máximo-mínimo puede existir o no. Sin embargo, si existe, es único.
El nombre "max-min" proviene de la idea de que es la tasa de los flujos más pequeños (o mínimos) la que se hace tan grande como sea posible (maximizada) por el algoritmo. Por lo tanto, damos una mayor prioridad relativa a los flujos pequeños. Solo cuando un flujo solicita consumir más de 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 en su totalidad (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 del significado común de cuello de botella . También tenga en cuenta 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 máxima-mínima justa 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 la equidad máxima-mínima mediante el uso de un algoritmo de llenado progresivo. Comienza con todas las tasas iguales a 0 y aumenta todas las tasas juntas al mismo ritmo, hasta que se alcanzan uno o varios límites de capacidad de enlace. Las tarifas para las fuentes que usan estos enlaces ya no aumentan y usted continúa aumentando las tarifas 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 máximo-mínimo.
Ver también
- Medida de equidad
- Programación en sistemas operativos multitarea.
Referencias
- ^ http://ica1www.epfl.ch/PS_files/LEB3132.pdf#search=%22max-min%20fairness%22 Jean-Yves Le Boudec (EPFL Lausanne) "Adaptación de tarifas, control de congestión y equidad: un tutorial", noviembre de 2005