Análisis del valor medio

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , el análisis del valor medio ( MVA ) es una técnica recursiva para calcular las longitudes de cola esperadas , el tiempo de espera en los nodos de cola y el rendimiento en equilibrio para un sistema cerrado y separable de colas. Las primeras técnicas aproximadas fueron publicadas de forma independiente por Schweitzer ^[1] y Bard, ^{[2] [3]} seguidas más tarde por una versión exacta de Lavenberg y Reiser publicada en 1980. ^{[4] [5]}

Se basa en el teorema de llegada , que establece que cuando un cliente de un sistema cerrado con M clientes llega a una instalación de servicio, observa que el resto del sistema se encuentra en el estado de equilibrio correspondiente a un sistema con M  − 1 clientes.

Configuración del problema

Considere una red de colas cerrada de K M/M/1 colas , con M clientes circulando en el sistema. Suponga que los clientes son indistinguibles entre sí, de modo que la red tiene una sola clase de clientes. Para calcular la longitud media de la cola y el tiempo de espera en cada uno de los nodos y el rendimiento del sistema, utilizamos un algoritmo iterativo que comienza con una red con 0 clientes.

Escriba μ _i para la tasa de servicio en el nodo i y P para la matriz de enrutamiento de clientes, donde el elemento p _ij denota la probabilidad de que un cliente que finaliza el servicio en el nodo i se traslade al nodo j para recibir el servicio. Para utilizar el algoritmo, primero calculamos el vector de fila de la tasa de visitas v , un vector tal que v  =  v  P.

Ahora escriba L _i ( n ) para el número medio de clientes en la cola i cuando hay un total de n clientes en el sistema (esto incluye el trabajo que se está atendiendo actualmente en la cola i ) y W _j ( n ) para el tiempo medio que pasa un cliente en la cola i cuando hay un total de n clientes en el sistema. Denote el rendimiento de un sistema con m clientes por λ _m .

Algoritmo

El algoritmo ^[6] comienza con una red vacía (cero clientes), luego aumenta el número de clientes en 1 en cada iteración hasta que haya la cantidad requerida ( M ) de clientes en el sistema.

Para inicializar, establezca L _k (0) = 0 para k  = 1,..., K. (Esto establece la longitud promedio de la cola en un sistema sin clientes en cero en todos los nodos).

Repetir para m  = 1,..., M :

1. Para k  = 1, ..., K calcula el tiempo de espera en cada nodo utilizando el teorema de llegada:

${\displaystyle W_{k}(m)={\frac {1+L_{k}\left(m-1\right)}{\mu _{k}}}.}$

2. Luego calcule el rendimiento del sistema utilizando la ley de Little :

${\displaystyle \lambda _{m}={\frac {m}{\sum _{k=1}^{K}W_{k}(m)v_{k}}}.}$

3. Finalmente, utilice la ley de Little aplicada a cada cola para calcular las longitudes medias de las colas para k  = 1, ..., K:

${\displaystyle L_{k}(m)=v_{k}\lambda _{m}W_{k}(m).}$

Fin de repetición.

Método Bard-Schweitzer

La aproximación de Bard-Schweitzer estima que el número promedio de trabajos en el nodo k es: ^{[1] [7]}

${\displaystyle L_{k}(m-1)\approx {\frac {m-1}{m}}L_{k}(m)}$

que es una interpolación lineal. A partir de las fórmulas anteriores, esta aproximación produce relaciones de punto fijo que se pueden resolver numéricamente. Este enfoque iterativo a menudo se conoce con el nombre de MVA aproximado (AMVA) y suele ser más rápido que el enfoque recursivo de MVA. ^{[8] : 38}

Pseudocódigo

conjunto L _k ( m ) = M / K

repetir hasta la convergencia:

${\displaystyle \lambda _{m}={\frac {m}{\sum _{k=1}^{K}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}v_{k}}}}$

${\displaystyle L_{k}(m)=v_{k}\lambda _{m}{\frac {{\frac {m-1}{m}}L_{k}(m)+1}{\mu _{k}}}}$

Redes multiclase

En el caso de redes multiclase con R clases de clientes, cada cola k puede presentar diferentes tasas de servicio μ _k,r para cada clase de trabajo r=1,...,R , aunque existen ciertas restricciones en el caso de estaciones por orden de llegada debido a los supuestos del teorema BCMP en el caso multiclase.

El tiempo de espera W _k,r que experimentan los trabajos de clase r en la cola k todavía se puede relacionar con la longitud media total de la cola en el nodo k utilizando una generalización del teorema de llegada:

${\displaystyle W_{k,r}(\mathbb {m} )={\frac {1+L_{k}\left(\mathbb {m} -1_{r}\right)}{\mu _{k,r}}}.}$

donde es un vector de población de clientes para las clases R y resta uno del elemento r -ésimo de , asumiendo que . ${\displaystyle \mathbb {m} =(m_{1},\ldots ,m_{R})}$ ${\displaystyle 1_{r}}$ ${\displaystyle \mathbb {m} }$ ${\displaystyle m_{r}\geq 1}$

Para redes con una sola clase de cliente, el algoritmo MVA es muy rápido y el tiempo empleado crece linealmente con el número de clientes y el número de colas. Sin embargo, en modelos multiclase, el número de multiplicaciones y adiciones y los requisitos de almacenamiento para MVA crecen exponencialmente con el número de clases de clientes. En la práctica, el algoritmo funciona bien para 3 o 4 clases de clientes ^{[9], aunque esto generalmente depende de la implementación y la estructura del modelo. Por ejemplo, el método Tree-MVA puede escalar a modelos más grandes si la matriz de enrutamiento es dispersa [10]} .

Se pueden obtener valores exactos para las métricas de rendimiento medio en modelos grandes utilizando el método de momentos , que requiere tiempo logarítmico-cuadrático. El método de momentos puede resolver en la práctica modelos con hasta 10 clases de clientes o, a veces, más grandes, que normalmente son inaccesibles mediante MVA exacto. ^{[9] [11]} Sin embargo, esta técnica no utiliza el teorema de llegada y se basa en la resolución de sistemas de ecuaciones lineales que involucran la constante normalizadora de probabilidades de estado para la red de colas.

Los algoritmos de MVA aproximados (AMVA), como el método Bard-Schweitzer, ofrecen en cambio una técnica de solución alternativa que proporciona baja complejidad también en redes multiclase y generalmente ofrece resultados muy precisos. ^[12]

Extensiones

El algoritmo de análisis de valor medio se ha aplicado a una clase de modelos PEPA que describen redes de colas y el rendimiento de un centro de distribución clave . ^[13]

Software

• JMVA, una herramienta escrita en Java que implementa MVA. ^[14]
• queueing, una biblioteca para GNU Octave que incluye MVA. ^[15]
• Line, una caja de herramientas de MATLAB que incluye algoritmos MVA exactos y aproximados.

Véase también

• Teoría de colas

Referencias

1. Schweitzer, PJ; Serazzi, G.; Broglia, M. (1993). "Un estudio del análisis de cuellos de botella en redes cerradas de colas". Evaluación del rendimiento de sistemas informáticos y de comunicación . Apuntes de clase en informática. Vol. 729. pág. 491. doi :10.1007/BFb0013865. ISBN 978-3-540-57297-8.
2. Bard, Yonathan (1979). "Algunas extensiones al análisis de redes de colas multiclase". Actas del Tercer Simposio Internacional sobre Modelado y Evaluación del Rendimiento de Sistemas Informáticos: Rendimiento de los Sistemas Informáticos . North-Holland Publishing Co., págs. 51–62. ISBN 978-0-444-85332-5.
3. Adan, I.; Wal, J. (2011). "Técnicas de valores medios". Redes de colas . Serie internacional en investigación de operaciones y ciencia de la gestión. Vol. 154. págs. 561–586. doi :10.1007/978-1-4419-6472-4_13. ISBN 978-1-4419-6471-7.
4. Reiser, M.; Lavenberg, SS (1980). "Análisis de valor medio de redes de colas multicadena cerradas". Revista de la ACM . 27 (2): 313. doi : 10.1145/322186.322195 . S2CID  8694947.
5. Reiser, M. (2000). "Análisis del valor medio: una explicación personal". Evaluación del desempeño: orígenes y direcciones . Apuntes de clase en informática. Vol. 1769. págs. 491–504. doi :10.1007/3-540-46506-5_22. ISBN 978-3-540-67193-0.
6. Bose, Sanjay K. (2001). Introducción a los sistemas de colas. Springer. pág. 174. ISBN 978-0-306-46734-9.
7. Schweitzer, Paul (1979). "Análisis aproximado de redes cerradas de colas multiclase". Actas de la Conferencia internacional sobre control y optimización estocástica .
8. Tay, YC (2010). "Modelado analítico del rendimiento de los sistemas informáticos". Síntesis de conferencias sobre informática . 2 : 1–116. doi :10.2200/S00282ED1V01Y201005CSL002. S2CID  207318911.
9. Casale, G. (2011). "Análisis exacto de modelos de rendimiento mediante el método de momentos" (PDF) . Evaluación del rendimiento . 68 (6): 487–506. CiteSeerX 10.1.1.302.1139 . doi :10.1016/j.peva.2010.12.009. 
10. Hoyme, KP; Bruell, SC; Afshari, PV; Kain, RY (1986). "Un algoritmo de análisis de valor medio estructurado en árbol". ACM Transactions on Computer Systems . 4 (2): 178–185. doi : 10.1145/214419.214423 .
11. Casale, G. (2008). "CoMoM: Un algoritmo orientado a clases para la evaluación probabilística de redes de colas multiclase". IEEE Transactions on Software Engineering . 35 (2): 162–177. CiteSeerX 10.1.1.302.1139 . doi :10.1016/j.peva.2010.12.009. 
12. Zahorjan, John; Eager, Derek L.; Sweillam, Hisham M. (1988). "Exactitud, velocidad y convergencia del análisis del valor medio aproximado". Evaluación del rendimiento . 8 (4): 255–270. doi :10.1016/0166-5316(88)90028-4.
13. Thomas, N.; Zhao, Y. (2010). "Análisis del valor medio para una clase de modelos PEPA". Comput. J. 54 (5): 643–652. doi :10.1093/comjnl/bxq064. S2CID  12824669.
14. Bertoli, M.; Casale, G.; Serazzi, G. (2009). "JMT: herramientas de ingeniería de rendimiento para el modelado de sistemas" (PDF) . ACM SIGMETRICS Performance Evaluation Review . 36 (4): 10. doi :10.1145/1530873.1530877. S2CID  6920559.
15. Marzolla, M. (2014). "El paquete de colas de octava". Evaluación cuantitativa de sistemas . Apuntes de clase en informática. Vol. 8657. págs. 174-177. doi :10.1007/978-3-319-10696-0_14. ISBN 978-3-319-10695-3.S2CID 4978676  .

Enlaces externos

• J. Virtamo: Redes de colas. El material de Helsinki Tech ofrece una buena descripción general del teorema de Jackson y el MVA.
• Simon Lam: Una derivación simple del algoritmo MVA. Muestra la relación entre el algoritmo de Buzen y MVA.