Red BCMP

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , una red BCMP es una clase de red de colas para la que existe una distribución de equilibrio en forma de producto . Recibe su nombre en honor a los autores del artículo donde se describió por primera vez la red: Baskett , Chandy , Muntz y Palacios. El teorema es una extensión significativa de una red de Jackson que permite distribuciones de enrutamiento de clientes y tiempos de servicio prácticamente arbitrarios, sujetos a disciplinas de servicio particulares. ^[1]

El artículo es muy conocido y el teorema fue descrito en 1990 como "uno de los logros fundamentales en la teoría de colas en los últimos 20 años" por J. Michael Harrison y Ruth J. Williams . ^[2]

Definición de una red BCMP

Una red de m colas interconectadas se conoce como red BCMP si cada una de las colas es de uno de los cuatro tipos siguientes:

1. Disciplina FCFS en la que todos los clientes tienen la misma distribución de tiempo de servicio exponencial negativa . La tasa de servicio puede depender del estado, por lo que se debe escribir para la tasa de servicio cuando la longitud de la cola es j . ${\displaystyle \scriptstyle {\mu _{j}}}$
2. Colas de uso compartido de procesadores
3. Colas de servidores infinitos
4. LCFS con currículum preventivo (no se pierde el trabajo)

En los tres últimos casos, las distribuciones de tiempo de servicio deben tener transformadas de Laplace racionales . Esto significa que la transformada de Laplace debe tener la forma ^[3]

${\displaystyle L(s)={\frac {N(s)}{D(s)}}.}$

Además, se deben cumplir las siguientes condiciones:

1. Las llegadas externas al nodo i (si las hay) forman un proceso de Poisson ,
2. un cliente que completa un servicio en la cola i se moverá a una nueva cola j con una probabilidad (fija) o abandonará el sistema con una probabilidad , que no es cero para algún subconjunto de las colas. ${\displaystyle P_{ij}}$ ${\displaystyle 1-\sum _{j=1}^{m}P_{ij}}$

Teorema

Para una red BCMP de m colas que es abierta, cerrada o mixta en la que cada cola es de tipo 1, 2, 3 o 4, las probabilidades del estado de equilibrio se dan por

${\displaystyle \pi (x_{1},x_{2},\ldots ,x_{m})=C\pi _{1}(x_{1})\pi _{2}(x_{2})\cdots \pi _{m}(x_{m}),}$

donde C es una constante normalizadora elegida para hacer que las probabilidades del estado de equilibrio sumen 1 y representa la distribución de equilibrio para la cola i . ${\displaystyle \scriptstyle {\pi _{i}(\cdot )}}$

Prueba

La prueba original del teorema se dio verificando que se cumplían las ecuaciones de equilibrio independientes .

Peter G. Harrison ofreció una prueba alternativa ^[4] al considerar procesos inversos. ^[5]

Referencias

1. Baskett, F.; Chandy, K. Mani ; Muntz, RR; Palacios, FG (1975). "Redes abiertas, cerradas y mixtas de colas con diferentes clases de clientes". Revista de la ACM . 22 (2): 248–260. doi : 10.1145/321879.321887 . S2CID  : 15204199.
2. Harrison, JM ; Williams, RJ (1990). "Sobre la cuasireversibilidad de una estación de servicio browniana multiclase". Anales de probabilidad . 18 (3). Instituto de Estadística Matemática: 1249–1268. doi : 10.1214/aop/1176990745 . JSTOR  2244425.
3. Sinclair, Bart. "Teorema BCMP". Connexions . Consultado el 14 de agosto de 2011 .
4. Harchol-Balter, M. (2012). "Redes con servidores de tiempo compartido (PS) (BCMP)". Modelado y diseño de rendimiento de sistemas informáticos . págs. 380–394. doi :10.1017/CBO9781139226424.029. ISBN . 9781139226424.
5. Harrison, PG (2004). "Procesos inversos, formas de producto y una forma de no producto". Álgebra lineal y sus aplicaciones . 386 : 359–381. doi : 10.1016/j.laa.2004.02.020 .