In
queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
, a discipline within the mathematical
theory of probability
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
, a Jackson network (sometimes Jacksonian network) is a class of queueing network where the
equilibrium distribution is particularly simple to compute as the network has a
product-form solution
In probability theory, a product-form solution is a particularly efficient form of solution for determining some metric of a system with distinct sub-components, where the metric for the collection of components can be written as a product of the ...
. It was the first significant development in the theory of
networks of queues, and generalising and applying the ideas of the theorem to search for similar product-form solutions in other networks has been the subject of much research, including ideas used in the development of the Internet. The networks were first identified by
James R. Jackson
James Richard "Jim" Jackson (May 16, 1924 – March 20, 2011) was an American mathematician, well known for his contribution to queueing theory.
Jackson was born in Denver and raised in Beverly Hills. He served in the United States Air Force duri ...
[ A version from January 1963 is available at http://www.dtic.mil/dtic/tr/fulltext/u2/296776.pdf ] and his paper was re-printed in the journal ''
Management Science
Management science (or managerial science) is a wide and interdisciplinary study of solving complex problems and making strategic decisions as it pertains to institutions, corporations, governments and other types of organizational entities. It is ...
’s'' ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’
Jackson was inspired by the work of
Burke
Burke is an Anglo-Norman Irish surname, deriving from the ancient Anglo-Norman and Hiberno-Norman noble dynasty, the House of Burgh. In Ireland, the descendants of William de Burgh (–1206) had the surname ''de Burgh'' which was gaelicised ...
and Reich, though
Jean Walrand
Jean Camille Walrand is a professor of Computer Science at UC Berkeley. He received his Ph.D. from the Department of Electrical Engineering and Computer Sciences department at the University of California, Berkeley, and has been on the faculty of ...
notes "product-form results …
rea much less immediate result of the output theorem than Jackson himself appeared to believe in his fundamental paper".
An earlier product-form solution was found by R. R. P. Jackson for tandem queues (a finite chain of queues where each customer must visit each queue in order) and cyclic networks (a loop of queues where each customer must visit each queue in order).
A Jackson network consists of a number of nodes, where each node represents a queue in which the service rate can be both node-dependent (different nodes have different service rates) and state-dependent (service rates change depending on queue lengths). Jobs travel among the nodes following a fixed routing matrix. All jobs at each node belong to a single "class" and jobs follow the same service-time distribution and the same routing mechanism. Consequently, there is no notion of priority in serving the jobs: all jobs at each node are served on a
first-come, first-served
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
basis.
Jackson networks where a finite population of jobs travel around a closed network also have a product-form solution described by the
Gordon–Newell theorem In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers where customers cannot l ...
.
Necessary conditions for a Jackson network
A network of ''m'' interconnected queues is known as a Jackson network or Jacksonian network if it meets the following conditions:
# if the network is open, any external arrivals to node ''i'' form a
Poisson process
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
,
# All service times are exponentially distributed and the service discipline at all queues is
first-come, first-served
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
,
# a customer completing service at queue ''i'' will either move to some new queue ''j'' with probability
or leave the system with probability
, which, for an open network, is non-zero for some subset of the queues,
# the
utilization of all of the queues is less than one.
Theorem
In an open Jackson network of ''m''
M/M/1 queues where the
utilization is less than 1 at every queue, the equilibrium state probability distribution exists and for state
is given by the product of the individual queue equilibrium distributions
:
The result
also holds for
M/M/c model
In queueing theory, a discipline within , the queue (or Erlang–T model) is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a , there are servers, and job service t ...
stations with ''c''
''i'' servers at the
station, with utilization requirement
.
Definition
In an open network, jobs arrive from outside following a
Poisson process
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
with rate
. Each arrival is independently routed to node ''j'' with probability
and
. Upon service completion at node ''i'', a job may go to another node ''j'' with probability
or leave the network with probability
.
Hence we have the overall arrival rate to node ''i'',
, including both external arrivals and internal transitions:
:
(Since the utilisation at each node is less than 1, and we are looking at the equilibrium distribution i.e. the long-run-average behaviour, the rate of jobs transitioning from ''j'' to ''i'' is bounded by a fraction of the ''arrival'' rate at ''j'' and we ignore the service rate
in the above.)
Define
, then we can solve
.
All jobs leave each node also following Poisson process, and define
as the service rate of node ''i'' when there are
jobs at node ''i''.
Let
denote the number of jobs at node ''i'' at time ''t'', and
. Then the
equilibrium distribution of
,
is determined by the following system of balance equations:
:
where
denote the
unit vector
In mathematics, a unit vector in a normed vector space is a vector (often a spatial vector) of length 1. A unit vector is often denoted by a lowercase letter with a circumflex, or "hat", as in \hat (pronounced "v-hat").
The term ''direction vecto ...
.
Theorem
Suppose a vector of independent random variables
with each
having a
probability mass function
In probability and statistics, a probability mass function is a function that gives the probability that a discrete random variable is exactly equal to some value. Sometimes it is also known as the discrete density function. The probability mass ...
as
:
where
. If
i.e.
is well defined, then the equilibrium distribution of the open Jackson network has the following product form:
:
for all
.⟩
It suffices to verify equation
is satisfied. By the product form and formula (3), we have:
: