BCMP network

<h2 id="definition-of-a-bcmp-network">Definition of a BCMP network</h2>
A network of m interconnected queues is known as a BCMP network if each of the queues is of one of the following four types:

<ol><li><a href="/facts/First-come,_first-served/8NDl56EM">FCFS</a> discipline where all customers have the same <a href="/facts/Exponential_distribution/yY3EdV0u">negative exponential</a> service time distribution. The service rate can be state dependent, so write 
 
 
 
 
 
 
 μ
 
 j
 
 
 
 
 
 
 {\displaystyle \scriptstyle {\mu _{j}}}
 
 for the service rate when the queue length is j.</li>
<li>Processor sharing queues</li>
<li>Infinite-server queues</li>
<li><a href="/facts/LIFO_(computing)/bj7l94v1">LCFS</a> with pre-emptive resume (work is not lost)</li></ol>
In the final three cases, service time distributions must have <a href="/facts/Rational_function/2nJGu0Ko">rational</a> <a href="/facts/Laplace_transform/0Ge4MIc9">Laplace transforms</a>. This means the Laplace transform must be of the form<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

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

Also, the following conditions must be met.

<ol><li>external arrivals to node i (if any) form a <a href="/facts/Poisson_process/8uphjAUc">Poisson process</a>,</li>
<li>a customer completing service at queue i will either move to some new queue j with (fixed) probability 
 
 
 
 
 P
 
 i
 j
 
 
 
 
 {\displaystyle P_{ij}}
 
 or leave the system with probability 
 
 
 
 1
 −
 
 ∑
 
 j
 =
 1
 
 
 m
 
 
 
 P
 
 i
 j
 
 
 
 
 {\displaystyle 1-\sum _{j=1}^{m}P_{ij}}
 
, which is non-zero for some subset of the queues.</li></ol>
<h2 id="theorem">Theorem</h2>
For a BCMP network of m queues which is open, closed or mixed in which each queue is of type 1, 2, 3 or 4, the equilibrium state probabilities are given by

π
        (
        
          x
          
            1
          
        
        ,
        
          x
          
            2
          
        
        ,
        …
        ,
        
          x
          
            m
          
        
        )
        =
        C
        
          π
          
            1
          
        
        (
        
          x
          
            1
          
        
        )
        
          π
          
            2
          
        
        (
        
          x
          
            2
          
        
        )
        ⋯
        
          π
          
            m
          
        
        (
        
          x
          
            m
          
        
        )
        ,
      
    
    {\displaystyle \pi (x_{1},x_{2},\ldots ,x_{m})=C\pi _{1}(x_{1})\pi _{2}(x_{2})\cdots \pi _{m}(x_{m}),}

where C is a normalizing constant chosen to make the equilibrium state probabilities sum to 1 and 
 
 
 
 
 
 
 π
 
 i
 
 
 (
 ⋅
 )
 
 
 
 
 {\displaystyle \scriptstyle {\pi _{i}(\cdot )}}
 
 represents the equilibrium distribution for queue i.

<h3>Proof</h3>
The original proof of the theorem was given by checking the <a href="/facts/Independent_balance_equation/wEWusuII">independent balance equations</a> were satisfied.
<a href="/facts/Peter_G._Harrison/Aa6I2djo">Peter G. Harrison</a> offered an alternative proof<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> by considering reversed processes.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. (1975). "Open, closed and mixed networks of queues with different classes of customers". Journal of the ACM. 22 (2): 248–260. doi:10.1145/321879.321887. S2CID 15204199. <a href="/wiki/K._Mani_Chandy" target="_blank">/wiki/K._Mani_Chandy</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Harrison, J.M.; Williams, R.J. (1990). "On the Quasireversibility of a Multiclass Brownian Service Station". The Annals of Probability. 18 (3). Institute of Mathematical Statistics: 1249–1268. doi:10.1214/aop/1176990745. JSTOR 2244425. <a href="/wiki/J._Michael_Harrison" target="_blank">/wiki/J._Michael_Harrison</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Sinclair, Bart. "BCMP Theorem". Connexions. Retrieved 2011-08-14. <a href="http://cnx.org/content/m10853/latest/" target="_blank">http://cnx.org/content/m10853/latest/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Harchol-Balter, M. (2012). "Networks with Time-Sharing (PS) Servers (BCMP)". Performance Modeling and Design of Computer Systems. pp. 380–394. doi:10.1017/CBO9781139226424.029. ISBN 9781139226424. <a href="9781139226424" target="_blank">9781139226424</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Harrison, P. G. (2004). "Reversed processes, product forms and a non-product form". Linear Algebra and Its Applications. 386: 359–381. doi:10.1016/j.laa.2004.02.020. <a href="/wiki/Peter_G._Harrison" target="_blank">/wiki/Peter_G._Harrison</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
</ol>

BCMP network open-in-new

BCMP network