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.

**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,λ = λ _{1}^{outer}+ λ_{2}^{outer}+ ... = ∑_{k}λ_{k}^{outer}≡ X(1)

which simply says, everything that goes into the cloud must be equal to everything that comes out during any reasonable measurement interval.- Requests arriving at rates λ
**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}= λ_{k}^{outer}+ ∑_{k}P_{jk}λ_{j}≡ X_{k}(2) - Queueuing node k can receive flow λ

_{k}X

_{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.

## No comments:

Post a Comment