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 de forma de producto . Lleva el nombre de 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 Jackson que permite distribuciones de tiempo de servicio y enrutamiento de clientes virtualmente arbitrarias, sujeto a disciplinas de servicio particulares. [1]
El artículo es bien conocido y el teorema fue descrito en 1990 como "uno de los logros fundamentales en la teoría de las 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 siguientes cuatro tipos:
- Disciplina FCFS donde todos los clientes tienen la misma distribución exponencial negativa del tiempo de servicio. La tarifa del servicio puede depender del estado, así que escribapara la tarifa de servicio cuando la longitud de la cola es j .
- Colas de intercambio de procesadores
- Colas de servidor infinitas
- LCFS con curriculum vitae preventivo (el trabajo no se pierde)
En los últimos tres casos, las distribuciones del tiempo de servicio deben tener transformadas racionales de Laplace . 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 el servicio en la cola i me moveré a una nueva cola j con probabilidad (fija) o dejar el sistema con probabilidad , que es distinto de cero para algún subconjunto de las colas.
Teorema
Para una red BCMP de m colas abierta, cerrada o mixta en la que cada cola es de tipo 1, 2, 3 o 4, las probabilidades del estado de equilibrio están dadas por
donde C es una constante de normalización elegida para hacer que las probabilidades del estado de equilibrio sumen 1 yrepresenta la distribución de equilibrio para la cola i .
Prueba
La prueba original del teorema se dio comprobando que se cumplieron las ecuaciones de equilibrio independientes .
Peter G. Harrison ofreció una prueba alternativa [4] al considerar procesos invertidos. [5]
Referencias
- ^ Baskett, F .; Chandy, K. Mani ; Muntz, RR; Palacios, FG (1975). "Redes de colas abiertas, cerradas y mixtas con diferentes clases de clientes". Revista de la ACM . 22 (2): 248–260. doi : 10.1145 / 321879.321887 .
- ^ Harrison, JM ; Williams, RJ (1990). "Sobre la cuasireversibilidad de una estación de servicio browniana multiclase" . Los anales de la probabilidad . Instituto de Estadística Matemática. 18 (3): 1249-1268. doi : 10.1214 / aop / 1176990745 . JSTOR 2244425 .
- ^ Sinclair, Bart. "Teorema de BCMP" . Conexiones . Consultado el 14 de agosto de 2011 .
- ^ Harchol-Balter, M. (2012). "Redes con servidores de tiempo compartido (PS) (BCMP)". Modelado y Diseño de Performance de Sistemas Computacionales . págs. 380–394. doi : 10.1017 / CBO9781139226424.029 . ISBN 9781139226424.
- ^ Harrison, PG (2004). "Procesos invertidos, 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 . Archivado desde el original el 3 de marzo de 2016 . Consultado el 4 de septiembre de 2015 .