![ServidorParalelo](https://upload.wikimedia.org/wikipedia/commons/2/2b/ServidorParalelo.jpg)
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
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
because the results are often used when making business decisions about the resources needed to provide a service.
Queueing theory has its origins in research by
Agner Krarup Erlang
Agner Krarup Erlang (1 January 1878 – 3 February 1929) was a Denmark, Danish mathematician, statistician and engineer, who invented the fields of teletraffic engineering, traffic engineering and queueing theory.
By the time of his relatively ...
when he created models to describe the system of Copenhagen Telephone Exchange company, a Danish company.
The ideas have since seen applications including
telecommunication
Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...
,
traffic engineering,
computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
and, particularly in
industrial engineering
Industrial engineering is an engineering profession that is concerned with the optimization of complex process (engineering), processes, systems, or organizations by developing, improving and implementing integrated systems of people, money, kno ...
, in the design of factories, shops, offices and hospitals, as well as in project management.
Spelling
The spelling "queueing" over "queuing" is typically encountered in the academic research field. In fact, one of the flagship journals of the field is ''
Queueing Systems
''Queueing Systems'' is a peer-reviewed scientific journal covering queueing theory. It is published by Springer Science+Business Media. The current editor-in-chief is Sergey Foss. According to the ''Journal Citation Reports'', the journal has a ...
''.
Single queueing nodes
A queue, or queueing node can be thought of as nearly a
black box
In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
. Jobs or "customers" arrive to the queue, possibly wait some time, take some time being processed, and then depart from the queue.
![Black box queue diagram](https://upload.wikimedia.org/wikipedia/commons/a/a8/Black_box_queue_diagram.png)
The queueing node is not quite a pure black box, however, since some information is needed about the inside of the queuing node. The queue has one or more "servers" which can each be paired with an arriving job until it departs, after which that server will be free to be paired with another arriving job.
![Queueing node service digram](https://upload.wikimedia.org/wikipedia/commons/0/06/Queueing_node_service_digram.png)
An analogy often used is that of the cashier at a supermarket. There are other models, but this is one commonly encountered in the literature. Customers arrive, are processed by the cashier, and depart. Each cashier processes one customer at a time, and hence this is a queueing node with only one server. A setting where a customer will leave immediately if the cashier is busy when the customer arrives, is referred to as a queue with no buffer (or no "waiting area", or similar terms). A setting with a waiting zone for up to ''n'' customers is called a queue with a buffer of size ''n''.
Birth-death process
The behaviour of a single queue (also called a "queueing node") can be described by a
birth–death process
The birth–death process (or birth-and-death process) is a special case of continuous-time Markov process where the state transitions are of only two types: "births", which increase the state variable by one and "deaths", which decrease the state ...
, which describes the arrivals and departures from the queue, along with the number of jobs (also called "customers" or "requests", or any number of other things, depending on the field) currently in the system. An arrival increases the number of jobs (''k'') by 1, and a departure (a job completing its service) decreases ''k'' by 1.
Balance equations
The
steady state
In systems theory, a system or a Process theory, process is in a steady state if the variables (called state variables) which define the behavior of the system or the process are unchanging in time. In continuous time, this means that for those p ...
equations for the birth-and-death process, known as the
balance equation
In probability theory, a balance equation is an equation that describes the probability flux associated with a Markov chain in and out of states or set of states.
Global balance
The global balance equations (also known as full balance equation ...
s, are as follows. Here
denotes the steady state probability to be in state ''n''.
:
:
:
The first two equations imply
:
and
:
By mathematical induction,
:
The condition
leads to:
:
which, together with the equation for
, fully describes the required steady state probabilities.
Kendall's notation
Single queueing nodes are usually described using
Kendall's notation
In queueing theory, a discipline within the mathematical theory of probability, Kendall's notation (or sometimes Kendall notation) is the standard system used to describe and classify a queueing node. D. G. Kendall proposed describing queueing mod ...
in the form A/S/''c'' where ''A'' describes the distribution of durations between each arrival to the queue, ''S'' the distribution of service times for jobs and ''c'' the number of servers at the node.
[Tijms, H.C, ''Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003] For an example of the notation, the
M/M/1 queue
In queueing theory, a discipline within the mathematical theory of probability, an M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an expon ...
is a simple model where a single server serves jobs that arrive according to 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 ...
(where inter-arrival durations are
exponentially distributed
In probability theory and statistics, the exponential distribution is the probability distribution of the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant averag ...
) and have exponentially distributed service times (the M denotes a
Markov process
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
). In an
M/G/1 queue
In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian (modulated by a Poisson process), service times have a General distribution and there is a single server. ...
, the G stands for "general" and indicates an arbitrary
probability distribution
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon i ...
for service times.
Example analysis of an M/M/1 queue
Consider a queue with one server and the following characteristics:
* ''λ'': the arrival rate (the reciprocal of the expected time between each customer arriving, e.g. 10 customers per second);
* ''μ'': the reciprocal of the mean service time (the expected number of consecutive service completions per the same unit time, e.g. per 30 seconds);
* ''n'': the parameter characterizing the number of customers in the system;
* ''P''
''n'': the probability of there being ''n'' customers in the system in steady state.
Further, let ''E''
''n'' represent the number of times the system enters state ''n'', and ''L''
''n'' represent the number of times the system leaves state ''n''. Then for all ''n'', , ''E''
''n'' − ''L''
''n'', ∈ . That is, the number of times the system leaves a state differs by at most 1 from the number of times it enters that state, since it will either return into that state at some time in the future (''E''
''n'' = ''L''
''n'') or not (, ''E''
''n'' − ''L''
''n'', = 1).
When the system arrives at a steady state, the arrival rate should be equal to the departure rate.
Thus the balance equations
:
:
:
imply
:
The fact that
leads to the
geometric distribution
In probability theory and statistics, the geometric distribution is either one of two discrete probability distributions:
* The probability distribution of the number ''X'' of Bernoulli trials needed to get one success, supported on the set \;
* ...
formula
:
where
Simple two-equation queue
A common basic queuing system is attributed to
Erlang, and is a modification of
Little's Law. Given an arrival rate ''λ'', a dropout rate ''σ'', and a departure rate ''μ'', length of the queue ''L'' is defined as:
:
Assuming an exponential distribution for the rates, the waiting time ''W'' can be defined as the proportion of arrivals that are served. This is equal to the exponential survival rate of those who do not drop out over the waiting period, giving:
:
The second equation is commonly rewritten as:
:
The two-stage one-box model is common in epidemiology.
Overview of the development of the theory
In 1909,
Agner Krarup Erlang
Agner Krarup Erlang (1 January 1878 – 3 February 1929) was a Denmark, Danish mathematician, statistician and engineer, who invented the fields of teletraffic engineering, traffic engineering and queueing theory.
By the time of his relatively ...
, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on what would now be called queueing theory. He modeled the number of telephone calls arriving at an exchange by 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 ...
and solved the
M/D/1 queue In queueing theory, a discipline within the mathematical theory of probability, an M/D/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times are fixed (determ ...
in 1917 and
M/D/''k'' queueing model in 1920.
In Kendall's notation:
* M stands for Markov or memoryless and means arrivals occur according to a Poisson process;
* D stands for deterministic and means jobs arriving at the queue which require a fixed amount of service;
* ''k'' describes the number of servers at the queueing node (''k'' = 1, 2, ...).
If there are more jobs at the node than there are servers, then jobs will queue and wait for service
The
M/G/1 queue
In queueing theory, a discipline within the mathematical theory of probability, an M/G/1 queue is a queue model where arrivals are Markovian (modulated by a Poisson process), service times have a General distribution and there is a single server. ...
was solved by
Felix Pollaczek
Felix may refer to:
* Felix (name), people and fictional characters with the name
Places
* Arabia Felix is the ancient Latin name of Yemen
* Felix, Spain, a municipality of the province Almería, in the autonomous community of Andalusia, ...
in 1930, a solution later recast in probabilistic terms by
Aleksandr Khinchin
Aleksandr Yakovlevich Khinchin (russian: Алекса́ндр Я́ковлевич Хи́нчин, french: Alexandre Khintchine; July 19, 1894 – November 18, 1959) was a Soviet mathematician and one of the most significant contributors to th ...
and now known as the
Pollaczek–Khinchine formula In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula states a relationship between the queue length and service time distribution Laplace transforms for an M/G/1 queue (where jobs arrive a ...
.
After the 1940s queueing theory became an area of research interest to mathematicians.
In 1953
David George Kendall
David George Kendall FRS (15 January 1918 – 23 October 2007) was an English statistician and mathematician, known for his work on probability, statistical shape analysis, ley lines and queueing theory. He spent most of his academic life ...
solved the GI/M/''k'' queue and introduced the modern notation for queues, now known as
Kendall's notation
In queueing theory, a discipline within the mathematical theory of probability, Kendall's notation (or sometimes Kendall notation) is the standard system used to describe and classify a queueing node. D. G. Kendall proposed describing queueing mod ...
. In 1957 Pollaczek studied the GI/G/1 using an
integral equation
In mathematics, integral equations are equations in which an unknown Function (mathematics), function appears under an integral sign. In mathematical notation, integral equations may thus be expressed as being of the form: f(x_1,x_2,x_3,...,x_n ; ...
.
John Kingman
__NOTOC__
Sir John Frank Charles Kingman (born 28 August 1939) is a British mathematician. He served as N. M. Rothschild and Sons Professor of Mathematical Sciences and Director of the Isaac Newton Institute at the University of Cambridge from ...
gave a formula for the
mean waiting time in a
G/G/1 queue In queueing theory, a discipline within the mathematical theory of probability, the G/G/1 queue represents the queue length in a system with a single server where interarrival times have a general (meaning arbitrary) distribution and service times h ...
:
Kingman's formula In queueing theory, a discipline within the mathematical theory of probability, Kingman's formula also known as the VUT equation, is an approximation for the mean waiting time in a G/G/1 queue. The formula is the product of three terms which depend ...
.
Leonard Kleinrock
Leonard Kleinrock (born June 13, 1934) is an American computer scientist and a long-tenured professor at UCLA's Henry Samueli School of Engineering and Applied Science.
In the early 1960s, Kleinrock pioneered the application of queueing theory ...
worked on the application of queueing theory to
message switching In telecommunications, message switching involves messages routed in their entirety, one hop at a time. It evolved from circuit switching and was the precursor of packet switching.
History
Western Union operated a message switching system, Plan ...
in the early 1960s and
packet switching
In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
in the early 1970s. His initial contribution to this field was his doctoral thesis at the
Massachusetts Institute of Technology
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...
in 1962, published in book form in 1964. His theoretical work published in the early 1970s underpinned the use of packet switching in the
ARPANET
The Advanced Research Projects Agency Network (ARPANET) was the first wide-area packet-switched network with distributed control and one of the first networks to implement the TCP/IP protocol suite. Both technologies became the technical fou ...
, a forerunner to the Internet.
The
matrix geometric method In probability theory, the matrix geometric method is a method for the analysis of quasi-birth–death processes, continuous-time Markov chain whose transition rate matrices with a repetitive block structure. The method was developed "largely by ...
and
matrix analytic methods have allowed queues with
phase-type distributed inter-arrival and service time distributions to be considered.
Systems with coupled orbits are an important part in queueing theory in the application to wireless networks and signal processing.
Problems such as performance metrics for the
M/G/''k'' queue remain an open problem.
Service disciplines
![Fifo queue](https://upload.wikimedia.org/wikipedia/commons/d/d3/Fifo_queue.png)
Various scheduling policies can be used at queuing nodes:
;
First in first out: Also called ''first-come, first-served'' (FCFS),
this principle states that customers are served one at a time and that the customer that has been waiting the longest is served first.
[Penttinen A., ''Chapter 8 – Queueing Systems'', Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.]
;
Last in first out: This principle also serves customers one at a time, but the customer with the shortest
waiting time will be served first.
Also known as a
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
.
;
Processor sharing
Processor sharing or egalitarian processor sharing is a service policy where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available. In such a system all jobs start service ...
: Service capacity is shared equally between customers.
; Priority: Customers with high priority are served first.
Priority queues can be of two types, non-preemptive (where a job in service cannot be interrupted) and preemptive (where a job in service can be interrupted by a higher-priority job). No work is lost in either model.
;
Shortest job first
Shortest job next (SJN), also known as shortest job first (SJF) or shortest process next (SPN), is a scheduling policy that selects for execution the waiting process with the smallest execution time. SJN is a non- preemptive algorithm. Shortest r ...
: The next job to be served is the one with the smallest size
; Preemptive shortest job first: The next job to be served is the one with the original smallest size
;
Shortest remaining processing time: The next job to serve is the one with the smallest remaining processing requirement.
; Service facility
* Single server: customers line up and there is only one server
* Several parallel servers–Single queue: customers line up and there are several servers
* Several servers–Several queues: there are many counters and customers can decide going where to queue
; Unreliable server
Server failures occur according to a stochastic process (usually Poisson) and are followed by the setup periods during which the server is unavailable. The interrupted customer remains in the service area until server is fixed.
; Customer's behavior of waiting
* Balking: customers deciding not to join the queue if it is too long
* Jockeying: customers switch between queues if they think they will get served faster by doing so
* Reneging: customers leave the queue if they have waited too long for service
Arriving customers not served (either due to the queue having no buffer, or due to balking or reneging by the customer) are also known as dropouts and the average rate of dropouts is a significant parameter describing a queue.
Queueing networks
Networks of queues are systems in which a number of queues are connected by what's known as customer routing. When a customer is serviced at one node it can join another node and queue for service, or leave the network.
For networks of ''m'' nodes, the state of the system can be described by an ''m''–dimensional vector (''x''
1, ''x''
2, ..., ''x''
''m'') where ''x''
''i'' represents the number of customers at each node.
The simplest non-trivial network of queues is called
tandem queues. The first significant results in this area were
Jackson network In queueing theory, a discipline within the mathematical theory of probability, 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 ...
s,
for which an efficient
product-form stationary distribution
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 ...
exists and the
mean value analysis In queueing theory, a discipline within the mathematical theory of probability, mean value analysis (MVA) is a recursive technique for computing expected queue lengths, waiting time at queueing nodes and throughput in equilibrium for a closed separ ...
which allows average metrics such as throughput and sojourn times to be computed. If the total number of customers in the network remains constant the network is called a closed network and has also been shown to have a product–form stationary distribution in 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 ...
. This result was extended to the
BCMP network In queueing theory, a discipline within the mathematical theory of probability, a BCMP network is a class of queueing network for which a product-form equilibrium distribution exists. It is named after the authors of the paper where the network was ...
where a network with very general service time, regimes and customer routing is shown to also exhibit a product-form stationary distribution. The
normalizing constant
The concept of a normalizing constant arises in probability theory and a variety of other areas of mathematics. The normalizing constant is used to reduce any probability function to a probability density function with total probability of one.
...
can be calculated with the
Buzen's algorithm In queueing theory, a discipline within the mathematical theory of probability, Buzen's algorithm (or convolution algorithm) is an algorithm for calculating the normalization constant G(''N'') in the Gordon–Newell theorem. This method was first p ...
, proposed in 1973.
Networks of customers have also been investigated,
Kelly network In queueing theory, a discipline within the mathematical theory of probability, a Kelly network is a general multiclass queueing network. In the network each node is quasireversible and the network has a product-form stationary distribution, much ...
s where customers of different classes experience different priority levels at different service nodes. Another type of network are
G-networks
In queueing theory, a discipline within the mathematical theory of probability, a G-network (generalized queueing network, often called a Gelenbe network) is an open network of G-queues first introduced by Erol Gelenbe as a model for queueing syst ...
first proposed by
Erol Gelenbe
Sami Erol Gelenbe (born 22 August 1945, in Istanbul, Turkey) is a Turkish and French computer scientist, electronic engineer and applied mathematician who pioneered the field of Computer System and Network Performance in Europe, and is active i ...
in 1993: these networks do not assume exponential time distributions like the classic Jackson Network.
Routing algorithms
In discrete time networks where there is a constraint on which service nodes can be active at any time, the max-weight scheduling algorithm chooses a service policy to give optimal throughput in the case that each job visits only a single-person service node.
In the more general case where jobs can visit more than one node,
backpressure routing
In queueing theory, a discipline within the mathematical theory of probability, the backpressure routing algorithm is a method for directing traffic around a queueing network that achieves maximum network throughput, which is established using con ...
gives optimal throughput. A
network scheduler
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
must choose a
queueing algorithm
A network scheduler, also called packet scheduler, queueing discipline (qdisc) or queueing algorithm, is an arbiter on a node in a packet switching communication network. It manages the sequence of network packets in the transmit and receive q ...
, which affects the characteristics of the larger network. See also
Stochastic scheduling
Stochastic scheduling concerns scheduling problems involving random attributes, such as random processing times, random due dates, random weights, and stochastic machine breakdowns. Major applications arise in manufacturing systems, computer system ...
for more about scheduling of queueing systems.
Mean-field limits
Mean-field model
In physics and probability theory, Mean-field theory (MFT) or Self-consistent field theory studies the behavior of high-dimensional random (stochastic) models by studying a simpler model that approximates the original by averaging over degrees of ...
s consider the limiting behaviour of the
empirical measure
In probability theory, an empirical measure is a random measure arising from a particular realization of a (usually finite) sequence of random variables. The precise definition is found below. Empirical measures are relevant to mathematical stat ...
(proportion of queues in different states) as the number of queues (''m'' above) goes to infinity. The impact of other queues on any given queue in the network is approximated by a differential equation. The deterministic model converges to the same stationary distribution as the original model.
Heavy traffic/diffusion approximations
In a system with high occupancy rates (utilisation near 1) a heavy traffic approximation can be used to approximate the queueing length process by a
reflected Brownian motion
In probability theory, reflected Brownian motion (or regulated Brownian motion, both with the acronym RBM) is a Wiener process in a space with reflecting boundaries. In the physical literature, this process describes diffusion in a confined spac ...
,
Ornstein–Uhlenbeck process
In mathematics, the Ornstein–Uhlenbeck process is a stochastic process with applications in financial mathematics and the physical sciences. Its original application in physics was as a model for the velocity of a massive Brownian particle ...
, or more general
diffusion process
In probability theory and statistics, diffusion processes are a class of continuous-time Markov process with almost surely continuous sample paths. Brownian motion, reflected Brownian motion and Ornstein–Uhlenbeck processes are examples of diff ...
. The number of dimensions of the Brownian process is equal to the number of queueing nodes, with the diffusion restricted to the non-negative
orthant
In geometry, an orthant or hyperoctant is the analogue in ''n''-dimensional Euclidean space of a quadrant in the plane or an octant in three dimensions.
In general an orthant in ''n''-dimensions can be considered the intersection of ''n'' mutua ...
.
Fluid limits
Fluid models are continuous deterministic analogs of queueing networks obtained by taking the limit when the process is scaled in time and space, allowing heterogeneous objects. This scaled trajectory converges to a deterministic equation which allows the stability of the system to be proven. It is known that a queueing network can be stable, but have an unstable fluid limit.
See also
*
Ehrenfest model The Ehrenfest model (or dog–flea model) of diffusion was proposed by Tatiana and Paul Ehrenfest to explain the second law of thermodynamics. The model considers ''N'' particles in two containers. Particles independently change container at a rate& ...
*
Erlang unit
The erlang (symbol E) is a dimensionless unit that is used in telephony as a measure of offered load or carried load on service-providing elements such as telephone circuits or telephone switching equipment. A single cord circuit has the capaci ...
*
Network simulation
In computer network research, network simulation is a technique whereby a software program replicates the behavior of a real network. This is achieved by calculating the interactions between the different network entities such as routers, switche ...
*
Project production management
Project production management (PPM) is the application of operations managementA Guide to the Project Management Body of Knowledge, Fifth Edition, Project Management Institute
Sec 1.5.1.1, p13
http://www.pmi.org/pmbok-guide-standards/foundational ...
*
Queue area
Queue areas are places in which people queue (first-come, first-served) for goods or services. Such a group of people is known as a ''queue'' (British usage) or ''line'' (American usage), and the people are said to be waiting or standing ''in ...
*
Queueing delay
In telecommunication and computer engineering, the queuing delay or queueing delay is the time a job waits in a queue until it can be executed. It is a key component of network delay. In a switched network, queuing delay is the time between the c ...
*
Queue management system How does the queue management system work?
Queue management is the process of managing the experiences of customers waiting in the queue to improve business.This system quantifies queuing demand for your business, such that your staff can be mad ...
*
Queuing Rule of Thumb
The Queuing Rule of Thumb (QROT) is a mathematical formula, known as the queuing constraint equation when it is used to find an approximation of servers required to service a queue. The formula is written as an inequality relating the number of ser ...
*
Random early detection
Random early detection (RED), also known as random early discard or random early drop is a queuing discipline for a network scheduler suited for congestion avoidance.
In the conventional tail drop algorithm, a router or other network component b ...
*
Renewal theory
Renewal theory is the branch of probability theory that generalizes the Poisson process for arbitrary holding times. Instead of exponentially distributed holding times, a renewal process may have any independent and identically distributed (IID) ho ...
*
Throughput
Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...
*
Scheduling (computing)
In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows.
The scheduling activity is c ...
*
Traffic jam
Traffic congestion is a condition in transport that is characterized by slower speeds, longer trip times, and increased vehicular queueing. Traffic congestion on urban road networks has increased substantially since the 1950s. When traffic de ...
*
Traffic generation model
A traffic generation model is a stochastic model of the traffic flows or data sources in a communication network, for example a cellular network or a computer network. A packet generation model is a traffic generation model of the packet flows or ...
*
Flow network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations res ...
References
Further reading
*
Online*
* chap.15, pp. 380–412
*
*
* Leonard Kleinrock
(MIT, Cambridge, May 31, 1961) Proposal for a Ph.D. Thesis
* Leonard Kleinrock. ''Information Flow in Large Communication Nets'' (RLE Quarterly Progress Report, July 1961)
* Leonard Kleinrock. ''Communication Nets: Stochastic Message Flow and Delay'' (McGraw-Hill, New York, 1964)
*
*
*
*
External links
*
Virtamo's Queueing Theory CourseQueueing Theory BasicsA free online tool to solve some classical queueing systemsJMT: an open source graphical environment for queueing theoryLINE: a general-purpose engine to solve queueing models by Seth Stevenson, ''Slate'', 2012 – popular introduction
{{Authority control
Stochastic processes
Production planning
Customer experience
Operations research
Formal sciences
Rationing
Network performance
Markov models
Markov processes