Сети Джексона: Теория массового обслуживания и продуктовые формы решений
Jackson network
Сети Джексона: математическая теория вероятностей, анализ очередей. Простое вычисление равновесного распределения, продукт-форма решения, интернет-технологии.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В теории очередей, разделе математической теории вероятностей, сеть Джексона (иногда Джексоновская сеть) — это класс сетей очередей, в которых равновесное распределение особенно просто вычислить, поскольку сеть имеет решение в виде произведения. Это было первым значительным достижением в теории сетей очередей, и обобщение и применение идей этой теоремы для поиска аналогичных решений в виде произведения в других сетях стало предметом многочисленных исследований, включая идеи, использованные при разработке Интернета. Сети были впервые описаны Джеймсом Р. Джексоном, а его работа была перепечатана в журнале Management Science в подборке «Десять самых влиятельных публикаций первых пятидесяти лет Management Science».
Mathematical disciplineIn 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 a product form solution. 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 and his paper was re printed in the journal Management Science’s ‘Ten Most Influential Titles of Management Sciences First Fifty Years.’
Джексон был вдохновлен работами Берка и Рейха, однако Жан Уолранд отмечает, что «результаты в виде произведения [являются] гораздо менее прямым следствием теоремы о выводе, чем, по-видимому, полагал сам Джексон в своей основополагающей работе». Ранее Р. Р. П. Джексон нашел решение в виде произведения для тандемных очередей (конечной цепочки очередей, в которой каждый клиент должен последовательно посещать каждую очередь) и циклических сетей (кольца очередей, в котором каждый клиент должен последовательно посещать каждую очередь). Сеть Джексона состоит из ряда узлов, каждый из которых представляет собой очередь, в которой интенсивность обслуживания может зависеть как от узла (разные узлы имеют разную интенсивность обслуживания), так и от состояния (интенсивность обслуживания меняется в зависимости от длины очереди). Задачи перемещаются между узлами в соответствии с фиксированной матрицей маршрутизации. Все задачи в каждом узле принадлежат к одному «классу» и подчиняются одному и тому же распределению времени обслуживания и одному и тому же механизму маршрутизации. Следовательно, понятие приоритета при обслуживании задач отсутствует: все задачи в каждом узле обслуживаются по принципу «первым пришел — первым обслужен». Сети Джексона, в которых конечное число задач циркулирует в замкнутой сети, также имеют решение в виде произведения, описанное теоремой Гордона — Ньюэлла.
Jackson was inspired by the work of Burke and Reich, though Jean Walrand notes "product form results [are] a 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 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.
Общая сеть Джексона
Обобщенная сеть Джексона допускает процессы поступления, имеющие свойства восстановления, которые не обязательно являются пуассоновскими, и независимые, одинаково распределенные времена обслуживания, не имеющие экспоненциального распределения. В общем случае, для такой сети не существует стационарного распределения в виде произведения, поэтому используются приближения.
A generalized Jackson network allows renewal arrival processes that need not be Poisson processes, and independent, identically distributed non exponential service times. In general, this network does not have a product form stationary distribution, so approximations are sought.