Editing Queueing theory (section)

== Queueing networks ==

Queue networks are systems in which multiple queues are connected by ''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''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''m''</sub>) where ''x''<sub>''i''</sub> represents the number of customers at each node.

The simplest non-trivial networks of queues are called [[Jackson network|tandem queues]].<ref>{{Cite web |url=http://www.stats.ox.ac.uk/~winkel/bs3a07l13-14.pdf#page=4 |title=Archived copy |access-date=2018-08-02 |archive-date=2017-03-29 |archive-url=https://web.archive.org/web/20170329085928/http://www.stats.ox.ac.uk/~winkel/bs3a07l13-14.pdf#page=4 |url-status=live }}</ref> The first significant results in this area were [[Jackson network]]s,<ref>{{Cite journal | last1 = Jackson | first1 = J. R. | author-link = James R. Jackson| title = Networks of Waiting Lines | doi = 10.1287/opre.5.4.518 | journal = Operations Research | volume = 5 | issue = 4 | pages = 518–521 | year = 1957 | jstor = 167249}}</ref><ref name="jackson">{{cite journal|title=Jobshop-like Queueing Systems|first=James R.|last=Jackson|journal=[[Management Science: A Journal of the Institute for Operations Research and the Management Sciences|Management Science]]|volume=10|number=1|date=Oct 1963|pages=131–142|doi=10.1287/mnsc.1040.0268|jstor=2627213}}</ref> for which an efficient [[product-form stationary distribution]] exists and the [[mean value analysis]]<ref>{{Cite journal | last1 = Reiser | first1 = M.| last2 = Lavenberg | first2 = S. S. | doi = 10.1145/322186.322195 | title = Mean-Value Analysis of Closed Multichain Queuing Networks | journal = [[Journal of the ACM]]| volume = 27 | issue = 2 | page = 313 | year = 1980 | s2cid = 8694947| doi-access = free }}</ref> (which allows average metrics such as throughput and sojourn times) can be computed.<ref>{{Cite journal | last1 = Van Dijk | first1 = N. M. | title = On the arrival theorem for communication networks | doi = 10.1016/0169-7552(93)90073-D | journal = Computer Networks and ISDN Systems | volume = 25 | issue = 10 | pages = 1135–2013 | year = 1993 | s2cid = 45218280 | url = https://research.vu.nl/ws/files/73611045/Scanjob%20199100081 | access-date = 2019-09-24 | archive-date = 2019-09-24 | archive-url = https://web.archive.org/web/20190924062816/https://research.vu.nl/ws/files/73611045/Scanjob%2520199100081 | url-status = live }}</ref> If the total number of customers in the network remains constant, the network is called a ''closed network'' and has been shown to also have a product–form stationary distribution by the [[Gordon–Newell theorem]].<ref>{{Cite journal | last1 = Gordon | first1 = W. J. | last2 = Newell | first2 = G. F. | author-link2 = Gordon F. Newell| doi = 10.1287/opre.15.2.254 | jstor = 168557| title = Closed Queuing Systems with Exponential Servers | journal = [[Operations Research (journal)|Operations Research]]| volume = 15 | issue = 2 | page = 254 | year = 1967 }}</ref> This result was extended to the [[BCMP network]],<ref>{{Cite journal | last1 = Baskett | first1 = F. | last2 = Chandy | first2 = K. Mani | author2-link = K. Mani Chandy | last3 = Muntz | first3 = R.R. | last4 = Palacios | first4 = F.G. | title = Open, closed and mixed networks of queues with different classes of customers | journal = Journal of the ACM | volume = 22 | issue = 2 | pages = 248&ndash;260 | year = 1975 | doi = 10.1145/321879.321887 | s2cid = 15204199 | doi-access = free }}</ref> 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]] can be calculated with the [[Buzen's algorithm]], proposed in 1973.<ref name="buzen-1973">{{Cite journal | last1 = Buzen | first1 = J. P. | author-link = Jeffrey P. Buzen | title = Computational algorithms for closed queueing networks with exponential servers | doi = 10.1145/362342.362345 | url = http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf | journal = Communications of the ACM | volume = 16 | issue = 9 | pages = 527–531 | year = 1973 | s2cid = 10702 | access-date = 2015-09-01 | archive-date = 2016-05-13 | archive-url = https://web.archive.org/web/20160513192804/http://www-unix.ecs.umass.edu/~krishna/ece673/buzen.pdf | url-status = live }}</ref>

Networks of customers have also been investigated, such as [[Kelly network]]s, where customers of different classes experience different priority levels at different service nodes.<ref>{{Cite journal | last1 = Kelly | first1 = F. P. | author-link1 = Frank Kelly (mathematician)| title = Networks of Queues with Customers of Different Types | journal = Journal of Applied Probability | volume = 12 | issue = 3 | pages = 542–554 | doi = 10.2307/3212869 | jstor = 3212869| year = 1975 | s2cid = 51917794 }}</ref> Another type of network are [[G-networks]], first proposed by [[Erol Gelenbe]] in 1993:<ref>{{cite journal | doi = 10.2307/3214781 | title = G-Networks with Triggered Customer Movement | first = Erol | last = Gelenbe | author-link = Erol Gelenbe | journal = Journal of Applied Probability | volume = 30 | issue = 3 | date = Sep 1993 | pages = 742–748 | jstor = 3214781 | s2cid = 121673725 }}</ref> these networks do not assume exponential time distributions like the classic Jackson network.

=== Routing algorithms ===
{{See also|Stochastic scheduling}}
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.<ref name="Manuel" /> In the more general case where jobs can visit more than one node, [[backpressure routing]] gives optimal throughput. A [[network scheduler]] must choose a [[queueing algorithm]], which affects the characteristics of the larger network.<ref>{{Cite journal |last=Newell |first=G. F. |date=1982 |title=Applications of Queueing Theory |url=https://doi.org/10.1007/978-94-009-5970-5 |journal=SpringerLink |language=en |doi=10.1007/978-94-009-5970-5|isbn=978-94-009-5972-9 }}</ref>

=== Mean-field limits ===

[[Mean-field model]]s consider the limiting behaviour of the [[empirical measure]] (proportion of queues in different states) as the number of queues ''m'' approaches 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.<ref>{{Cite book | last1 = Bobbio | first1 = A. | last2 = Gribaudo | first2 = M. | last3 = Telek | first3 = M. S. | doi = 10.1109/QEST.2008.47 | chapter = Analysis of Large Scale Interacting Systems by Mean Field Method | title = 2008 Fifth International Conference on Quantitative Evaluation of Systems | page = 215 | year = 2008 | isbn = 978-0-7695-3360-5 | s2cid = 2714909 }}</ref>

=== Heavy traffic/diffusion approximations ===
{{Main|Heavy traffic approximation}}
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]],<ref>{{Cite journal | last1 = Chen | first1 = H. | last2 = Whitt | first2 = W. | doi = 10.1007/BF01149260 | title = Diffusion approximations for open queueing networks with service interruptions | journal = [[Queueing Systems]]| volume = 13 | issue = 4 | page = 335 | year = 1993 | s2cid = 1180930 }}</ref> [[Ornstein–Uhlenbeck process]], or more general [[diffusion process]].<ref>{{Cite journal | last1 = Yamada | first1 = K. | title = Diffusion Approximation for Open State-Dependent Queueing Networks in the Heavy Traffic Situation | doi = 10.1214/aoap/1177004602 | journal = The Annals of Applied Probability | volume = 5 | issue = 4 | pages = 958–982 | year = 1995 | jstor = 2245101| doi-access = free }}</ref> 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]].

=== Fluid limits ===
{{main|Fluid limit}}
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.<ref>{{Cite journal | last1 = Bramson | first1 = M. | title = A stable queueing network with unstable fluid model | doi = 10.1214/aoap/1029962815 | journal = The Annals of Applied Probability | volume = 9 | issue = 3 | pages = 818–853 | year = 1999 | jstor = 2667284| doi-access = free }}</ref>

=== Queueing Applications ===
Queueing theory finds widespread application in computer science and information technology. In networking, for instance, queues are integral to routers and switches, where packets queue up for transmission. By applying queueing theory principles, designers can optimize these systems, ensuring responsive performance and efficient resource utilization.

Beyond the technological realm, queueing theory is relevant to everyday experiences. Whether waiting in line at a supermarket or for public transportation, understanding the principles of queueing theory provides valuable insights into optimizing these systems for enhanced user satisfaction. At some point, everyone will be involved in an aspect of queuing. What some may view to be an inconvenience could possibly be the most effective method.
Queueing theory, a discipline rooted in applied mathematics and computer science, is a field dedicated to the study and analysis of queues, or waiting lines, and their implications across a diverse range of applications. This theoretical framework has proven instrumental in understanding and optimizing the efficiency of systems characterized by the presence of queues. The study of queues is essential in contexts such as traffic systems, computer networks, telecommunications, and service operations.

Queueing theory delves into various foundational concepts, with the arrival process and service process being central. The arrival process describes the manner in which entities join the queue over time, often modeled using stochastic processes like Poisson processes. The efficiency of queueing systems is gauged through key performance metrics. These include the average queue length, average wait time, and system throughput. These metrics provide insights into the system's functionality, guiding decisions aimed at enhancing performance and reducing wait times.<ref>Gross, D., & Harris, C. M. (1998). ''Fundamentals of Queueing Theory''. John Wiley & Sons.</ref><ref>Kleinrock, L. (1976). ''Queueing Systems: Volume I - Theory''. Wiley.</ref><ref>Cooper, B. F., & Mitrani, I. (1985). ''Queueing Networks: A Fundamental Approach''. John Wiley & Sons.</ref>