G-network

<h2 id="definition">Definition</h2>

A network of m interconnected queues is a G-network if

<ol><li>each queue has one server, who serves at rate μi,</li>
<li>external arrivals of positive customers or of triggers or resets form <a href="/facts/Poisson_processes/8uphjAUc">Poisson processes</a> of rate 
 
 
 
 
 
 
 Λ
 
 i
 
 
 
 
 
 
 {\displaystyle \scriptstyle {\Lambda _{i}}}
 
 for positive customers, while triggers and resets, including negative customers, form a Poisson process of rate 
 
 
 
 
 
 
 λ
 
 i
 
 
 
 
 
 
 {\displaystyle \scriptstyle {\lambda _{i}}}
 
,</li>
<li>on completing service a customer moves from queue i to queue j as a positive customer with probability 
 
 
 
 
 
 
 p
 
 i
 j
 
 
 +
 
 
 
 
 
 
 {\displaystyle \scriptstyle {p_{ij}^{+}}}
 
, as a trigger or reset with probability 
 
 
 
 
 
 
 p
 
 i
 j
 
 
 −
 
 
 
 
 
 
 {\displaystyle \scriptstyle {p_{ij}^{-}}}
 
 and departs the network with probability 
 
 
 
 
 
 
 d
 
 i
 
 
 
 
 
 
 {\displaystyle \scriptstyle {d_{i}}}
 
,</li>
<li>on arrival to a queue, a positive customer acts as usual and increases the queue length by 1,</li>
<li>on arrival to a queue, the negative customer reduces the length of the queue by some random number (if there is at least one positive customer present at the queue), while a trigger moves a customer probabilistically to another queue and a reset sets the state of the queue to its steady-state if the queue is empty when the reset arrives. All triggers, negative customers and resets disappear after they have taken their action, so that they are in fact "control" signals in the network,</li></ol>
<ul><li>note that normal customers leaving a queue can become triggers or resets and negative customers when they visit the next queue.</li></ul>
A queue in such a network is known as a G-queue.

<h2 id="stationary-distribution">Stationary distribution</h2>
Define the utilization at each node,

ρ
          
            i
          
        
        =
        
          
            
              λ
              
                i
              
              
                +
              
            
            
              
                μ
                
                  i
                
              
              +
              
                λ
                
                  i
                
                
                  −
                
              
            
          
        
      
    
    {\displaystyle \rho _{i}={\frac {\lambda _{i}^{+}}{\mu _{i}+\lambda _{i}^{-}}}}

where the 
 
 
 
 
 
 
 λ
 
 i
 
 
 +
 
 
 ,
 
 λ
 
 i
 
 
 −
 
 
 
 
 
 
 {\displaystyle \scriptstyle {\lambda _{i}^{+},\lambda _{i}^{-}}}
 
 for 
 
 
 
 
 
 i
 =
 1
 ,
 …
 ,
 m
 
 
 
 
 {\displaystyle \scriptstyle {i=1,\ldots ,m}}
 
 satisfy

<table><tbody><tr><td> λ i + = ∑ j ρ j μ j p j i + + Λ i {\displaystyle \lambda _{i}^{+}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{+}+\Lambda _{i}\,} </td> <td></td> <td>1</td></tr></tbody></table>
<table><tbody><tr><td> λ i − = ∑ j ρ j μ j p j i − + λ i . {\displaystyle \lambda _{i}^{-}=\sum _{j}\rho _{j}\mu _{j}p_{ji}^{-}+\lambda _{i}.\,} </td> <td></td> <td>2</td></tr></tbody></table>
Then writing (n1, ... ,nm) for the state of the network (with queue length ni at node i), if a unique non-negative solution 
 
 
 
 
 
 (
 
 λ
 
 i
 
 
 +
 
 
 ,
 
 λ
 
 i
 
 
 −
 
 
 )
 
 
 
 
 {\displaystyle \scriptstyle {(\lambda _{i}^{+},\lambda _{i}^{-})}}
 
 exists to the above equations (1) and (2) such that ρi for all i then the stationary probability distribution π exists and is given by

π
        (
        
          n
          
            1
          
        
        ,
        
          n
          
            2
          
        
        ,
        …
        ,
        
          n
          
            m
          
        
        )
        =
        
          ∏
          
            i
            =
            1
          
          
            m
          
        
        (
        1
        −
        
          ρ
          
            i
          
        
        )
        
          ρ
          
            i
          
          
            
              n
              
                i
              
            
          
        
        .
      
    
    {\displaystyle \pi (n_{1},n_{2},\ldots ,n_{m})=\prod _{i=1}^{m}(1-\rho _{i})\rho _{i}^{n_{i}}.}

<h3>Proof</h3>

It is sufficient to show 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 satisfies the <a href="/facts/Balance_equation/wEWusuII">global balance equations</a> which, quite differently from Jackson networks are non-linear. We note that the model also allows for multiple classes.
G-networks have been used in a wide range of applications, including to represent Gene Regulatory Networks, the mix of control and payload in packet networks, neural networks, and the representation of colour images and medical images such as Magnetic Resonance Images.

<h2 id="response-time-distribution">Response time distribution</h2>
The response time is the length of time a customer spends in the system. The response time distribution for a single G-queue is known<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> where customers are served using a <a href="/facts/First_come_first_served/8NDl56EM">FCFS</a> discipline at rate μ, with positive arrivals at rate λ+ and negative arrivals at rate λ− which kill customers from the end of the queue. The <a href="/facts/Laplace_transform/0Ge4MIc9">Laplace transform</a> of response time distribution in this situation is<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

W
          
            ∗
          
        
        (
        s
        )
        =
        
          
            
              μ
              (
              1
              −
              ρ
              )
            
            
              λ
              
                +
              
            
          
        
        
          
            
              s
              +
              λ
              +
              μ
              (
              1
              −
              ρ
              )
              −
              
                
                  [
                  s
                  +
                  λ
                  +
                  μ
                  (
                  1
                  −
                  ρ
                  )
                  
                    ]
                    
                      2
                    
                  
                  −
                  4
                  
                    λ
                    
                      +
                    
                  
                  
                    λ
                    
                      −
                    
                  
                
              
            
            
              
                λ
                
                  −
                
              
              −
              
                λ
                
                  +
                
              
              −
              μ
              (
              1
              −
              ρ
              )
              −
              s
              +
              
                
                  [
                  s
                  +
                  λ
                  +
                  μ
                  (
                  1
                  −
                  ρ
                  )
                  
                    ]
                    
                      2
                    
                  
                  −
                  4
                  
                    λ
                    
                      +
                    
                  
                  
                    λ
                    
                      −
                    
                  
                
              
            
          
        
      
    
    {\displaystyle W^{\ast }(s)={\frac {\mu (1-\rho )}{\lambda ^{+}}}{\frac {s+\lambda +\mu (1-\rho )-{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}{\lambda ^{-}-\lambda ^{+}-\mu (1-\rho )-s+{\sqrt {[s+\lambda +\mu (1-\rho )]^{2}-4\lambda ^{+}\lambda ^{-}}}}}}

where λ = λ+ + λ− and ρ = λ+/(λ− + μ), requiring ρ < 1 for stability.
The response time for a tandem pair of G-queues (where customers who finish service at the first node immediately move to the second, then leave the network) is also known, and it is thought extensions to larger networks will be intractable.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

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

<ol>
<li id="fn:1">Gelenbe, Erol (1991). "Product-form queueing networks with negative and positive customers" (PDF). Journal of Applied Probability. 28 (3): 656–663. doi:10.2307/3214499. <a href="https://www.di.ens.fr/~busic/mar/projets/G91.pdf" target="_blank">https://www.di.ens.fr/~busic/mar/projets/G91.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gelenbe, Erol (Sep 1993). "G-Networks with Triggered Customer Movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781. <a href="/wiki/Erol_Gelenbe" target="_blank">/wiki/Erol_Gelenbe</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gelenbe, Erol; Fourneau, Jean-Michel (2002). "G-networks with resets". Performance Evaluation. 49 (1/4): 179–191. doi:10.1016/S0166-5316(02)00127-X. <a href="/wiki/Erol_Gelenbe" target="_blank">/wiki/Erol_Gelenbe</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Gelenbe, Erol (1989). "Random neural networks with negative and positive signals and product form solution" (PDF). Neural Computation. 1 (4): 502–510. doi:10.1162/neco.1989.1.4.502. <a href="https://www.researchgate.net/profile/Erol-Gelenbe-2/publication/239294946_Random_Neural_Networks_with_Negative_and_Positive_Signals_and_Product_Form_Solution/links/60a3b1eb458515952dd4b706/Random-Neural-Networks-with-Negative-and-Positive-Signals-and-Product-Form-Solution.pdf" target="_blank">https://www.researchgate.net/profile/Erol-Gelenbe-2/publication/239294946_Random_Neural_Networks_with_Negative_and_Positive_Signals_and_Product_Form_Solution/links/60a3b1eb458515952dd4b706/Random-Neural-Networks-with-Negative-and-Positive-Signals-and-Product-Form-Solution.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Harrison, Peter (2009). "Turning Back Time – What Impact on Performance?". The Computer Journal. 53 (6): 860–868. CiteSeerX 10.1.1.574.9535. doi:10.1093/comjnl/bxp021. <a href="/wiki/Peter_G._Harrison" target="_blank">/wiki/Peter_G._Harrison</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Gelenbe, Erol (1993). "G-Networks with signals and batch removal". Probability in the Engineering and Informational Sciences. 7 (3): 335–342. doi:10.1017/s0269964800002953. <a href="/wiki/Erol_Gelenbe" target="_blank">/wiki/Erol_Gelenbe</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Artalejo, J.R. (Oct 2000). "G-networks: A versatile approach for work removal in queueing networks". European Journal of Operational Research. 126 (2): 233–249. doi:10.1016/S0377-2217(99)00476-2. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Gelenbe, Erol; Mao, Zhi-Hong; Da Li, Yan (1999). "Function approximation with spiked random networks". IEEE Transactions on Neural Networks. 10 (1): 3–9. CiteSeerX 10.1.1.46.7710. doi:10.1109/72.737488. PMID 18252498. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Harrison, P. G.; Pitel, E. (1993). "Sojourn Times in Single-Server Queues with Negative Customers". Journal of Applied Probability. 30 (4): 943–963. doi:10.2307/3214524. JSTOR 3214524. <a href="/wiki/Peter_G._Harrison" target="_blank">/wiki/Peter_G._Harrison</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Harrison, P. G.; Pitel, E. (1993). "Sojourn Times in Single-Server Queues with Negative Customers". Journal of Applied Probability. 30 (4): 943–963. doi:10.2307/3214524. JSTOR 3214524. <a href="/wiki/Peter_G._Harrison" target="_blank">/wiki/Peter_G._Harrison</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Harrison, Peter G. (1998). Response times in G-nets. 13th International Symposium on Computer and Information Sciences (ISCIS 1998). pp. 9–16. ISBN 9051994052. <a href="9051994052" target="_blank">9051994052</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Harrison, Peter G. (1998). Response times in G-nets. 13th International Symposium on Computer and Information Sciences (ISCIS 1998). pp. 9–16. ISBN 9051994052. <a href="9051994052" target="_blank">9051994052</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

G-network open-in-new

G-network