Jackson's Theorem 2.1 2002/10/07 2002/11/01 Bart Sinclair bs@rice.edu Charlet Reedstrom charlet@rice.edu Bart Sinclair bs@rice.edu Jackson's Theorem (Blank Abstract) Jackson's Theorem is the first significant development in the theory of networks of queues. It assumes an open queueing network of single-server queues with the following characteristics: M # of queues in the system, not counting queue 0 which represents the outside world μ i service rate at queue i λ j total rate at which jobs arrive at queue j i 1 i M ρ i utilization of at queue i λ i μ i 1 n i t # of jobs in queue i at time t n t n 1 t n 2 t … n M t the system state at time t P k 1 k 2 … k M t Pr n t k 1 k 2 … k M P k 1 k 2 … k M t P k 1 k 2 … k M t Arrivals from the outside world are Poisson. All queues have exponential service time distributions. Jackson's Theorem P k 1 k 2 … k M i 1 M 1 ρ i ρ i k i Let λ i , j rate at which jobs leaving queue i go to queue j q i , j probability that a job departing queue i goes directly to queue j During an interval of length Δ t , only four possible events may occur: a job arrives from the outside world a job departs to the outside world a job leaves on queue and enters another none of the above These four possibilities are incorporated into the following equation: P k 1 k 2 … k M t Δ t j 1 M P k 1 k 2 … k j - 1 k j 1 k j + 1 … k M t λ 0 , j Δ t i 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k M t u i q i , 0 Δ t i 1 M j 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k j - 1 k j 1 k j + 1 … k M t u i q i , j Δ t P k 1 k 2 … k M t 1 Δ t j 1 M λ 0 , j μ j Moving the P k 1 k 2 … k M t term to the left hand side of the equation, dividing both sides by Δ t , and taking the limit as Δ t 0 gives us t P k 1 k 2 … k M t j 1 M P k 1 k 2 … k j - 1 k j 1 k j + 1 … k M t λ 0 , j i 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k M t u i q i , 0 i 1 M j 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k j - 1 k j 1 k j + 1 … k M t u i q i , j j 1 M P k 1 k 2 … k M t λ 0 , j μ j 0 in steady state, which will exist as long as λ j μ j , 1 j M . Hence, j 1 M P k 1 k 2 … k M t λ 0 , j μ j j 1 M P k 1 k 2 … k j - 1 k j 1 k j + 1 … k M t λ 0 , j i 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k M t u i q i , 0 i 1 M j 1 M P k 1 k 2 … k i - 1 k i 1 k i + 1 … k j - 1 k j 1 k j + 1 … k M t u i q i , j Assume that the network of queues has a product-form solution; i.e., assume P k 1 k 2 … k M i 1 M 1 ρ i ρ i k i Substitute this solution into the steady state equation and cancel common terms: j 1 M λ 0 , j μ j j 1 M λ 0 , j ρ j i 1 M ρ i μ i q i , 0 i 1 M j 1 M ρ i ρ j μ i q i , j Looking at the individual terms, j 1 M λ 0 , j ρ j j 1 M λ 0 , j μ j λ j i 1 M ρ i μ i q i , 0 i 1 M λ i 1 i 1 M q i , j i 1 M λ i i 1 M j 1 M λ i q i , j j 1 M λ 0 , j i 1 M j 1 M ρ i ρ j μ i q i , j j 1 M μ j λ j i 1 M λ i q i , j j 1 M μ j λ j λ j λ 0 , j j 1 M μ j j 1 M μ j λ 0 , j λ j Substituting these terms back into the previous equation gives us j 1 M λ 0 , j j 1 M μ j j 1 M λ 0 , j μ j λ j j 1 M λ 0 , j j 1 M μ j j 1 M λ 0 , j μ j λ j proving the theorem. One consequence of this theorem is that a Jackson network satisfies local balance; i.e., μ i P k 1 k 2 … k i … k n λ i P k 1 k 2 … k i 1 … k n This can easily be verified: μ i j 1 M 1 ρ j ρ j k j λ i j 1 M j i 1 ρ j ρ j k j 1 ρ i ρ i k i 1 μ i 1 ρ i ρ i k j λ i 1 ρ i ρ i k i 1 μ i ρ i λ i