Jackson's Theorem for the Cloud

Queueing theory, as a distinct discipline, just turned 100 last year. Compared with mathematics and physics, it's a relative youngster. Some seminal results include: Erlang's original solution for the M/D/1 queue (1909), his solutions for a multiserver queue without a waiting line M/M/m/m and with a waiting line M/M/m/∞; AKA "call waiting" (1917), the Pollaczek–Khinchine formula for the M/G/1 queue (1930) and Little's proof (1961). These results were established in the context of individual queueing facilities.

Modern packet networks and web applications, however, involve multiple queueing resources or tiers, and multiple flows of requests between them. In queue-theoretic parlance, this arrangement is called a open queueing network (in the sense of graph theory), but we can think of it as a cloud of queueing resources. That such a cloud of queues can also be solved analytically, was not formally established until the advent of Jackson's theorem in 1957; some 40 years after Erlang's M/M/m results.

A Jackson network can include any number of M/M/m queues, each having a different number (m) of service resources. In addition, the multiserver queues may involve feedback (like time-slicing) where the request is put back into the same waiting line for future service, and arrivals from multiple sources can flow into the network from outside, as long as the following conditions are met.

1. Network Traffic:
   
   
   • Requests arriving at rates λ_k^outer go to M/M/m queueuing node k.
     
   • Serviced requests can depart the network from any M/M/m queueing node k.
     
   • In steady state, the sum of all the arrivals into the network equals the total rate λ.
     
   • The total departure rate λ is equivalent to the global throughput X of the network.
     
   
   Hence,
   
   

   λ = λ1outer + λ2outer + ... = ∑k λkouter ≡ X

   (1)

   
   which simply says, everything that goes into the cloud must be equal to everything that comes out during any reasonable measurement interval.
   
   
2. Node Traffic: Everything that goes into a particular queueing node within the cloud must come out.
   
   
   
   • Queueuing node k can receive flow λ_k^outer from outside the network.
     
   • Queueuing node k can also receive requests λ_j from another M/M/m node j within the network.
     
   • The mean service time S_k is identical for all requests at node k.
     
   • The fraction arriving from each node j is given by its routing probability P_jk to depart node j and arrive at node k.
     
   • By definition the routing probabilities must add up to one.
     
   • The total departure rate from node k is the same as its local throughput X_k in steady state.
     
   
   Hence,
   
   

   λk = λkouter + ∑k Pjk λj ≡ Xk

   (2)

   
   

Analogous to eqn.(1), eqn.(2) states that number of requests going into a queueing node (within the cloud network) must be equal to the number of requests coming out during any reasonable measurement interval. Clearly, it follows that ∑_kX_k = X.

Equations (1) and (2) are called the traffic equations for the Jackson network.

Jackson's theorem states that such a cloud of queues can be solved as if each node was operating like an independent M/M/m queue with arrivals and departures as defined by the overall network. This result is not obvious because the assumption of Poisson arrivals for M/M/m solutions (like Erlang assumed for M/M/1), appears to be violated by the possibility of feedback into the waiting line. Remarkably, the average values of the queue performance metrics are the same as if things were Poisson.

Example: A Jackson network, representing a computer communications system, is solved using PyDQ together with the NumPy numerical package.

Incidentally, Jim Jackson was not considering either computers or packet networks when he derived his theorem, because computers weren't connected back then and it was still more than 10 years until the creation of the ARPANET (later, the Internet). Like Prof. John Little, Jackson was in the business of business management. In particular, he was in the Business School at UCLA and analyzing a scheduling problem where people are contracted out for relatively short-term projects known as job shopping.