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:
- 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 .
- Colas de uso compartido de procesadores
- Colas de servidores infinitos
- 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]
Además, se deben cumplir las siguientes condiciones:
- Las llegadas externas al nodo i (si las hay) forman un proceso de Poisson ,
- 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.
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
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 .
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
- ^ 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.
- ^ 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.
- ^ Sinclair, Bart. "Teorema BCMP". Connexions . Consultado el 14 de agosto de 2011 .
- ^ 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.
- ^ 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 .