Сети очередей разделяются на закрытые и открытые сети. В закрытых сетях очередей число клиентов постоянно, тогда как в открытых сетях очередей число клиентов изменяется. В принципе, открытая сеть может быть преобразована в закрытую сеть добавлением дополнительного узла.
Классическая система ожидания Эрланга, $$M/M/n$$, является примером открытой системы организации очереди, тогда как модель восстановления машин Пальма с $$S$$ терминалами - закрытая сеть. Если есть более чем один тип клиентов, сеть может быть смешанной закрытой и открытой сетью. Так как процесс выхода из обслуживания от одного узла обычно вызывает процесс поступления вызовов на другой узел, мы обратим особое внимание на процесс выхода из обслуживания, в особенности, когда он может быть отображен как Пуассоновский процесс. Такие системы исследуются в секции, посвященной симметричным системам организации очереди (секция 14.2).
Состояние сети очередей определяется как одновременное распределение числа клиентов на каждом узле. Если $$K$$ обозначает общее количество узлов, то состояние отображается вектором $$p(i_1, i_2, \dots, i_K) $$, где $$i_k$$ - число клиентов на узле $$k (k = 1, 2, \dots, K) $$.
Часто пространство состояний является очень большим и, решая уравнения равновесия узла, трудно вычислить вероятности состояния. Если каждый узел - симметричная система организации очереди, например, сеть Джексона (секция 14.3), тогда мы будем иметь мультипликативную форму. Вероятности состояния сетей с мультипликативной формой могут быть объединены и получены, используя алгоритм свертывания (секция 14.4.1) с помощью
Сети Джексона могут быть обобщены к BCMP-сети (секция 14.5), где есть $$N$$ типов клиентов. Клиенты одного заданного типа принадлежат так называемой цепочке. Pис.14.1 иллюстрирует пример сети организации очереди с четырьмя цепочками. Когда число цепочек увеличивается, пространство состояний увеличивается соответственно, и точно могут быть вычислены только системы с небольшим количеством цепочек. В случае из многих цепочек сети состояние каждого узла становится многомерным (секция 14.6). Применение мультипликативной формы между узлами, свертывание и
(рис 14.1) Пример сети организации очереди с четырьмя открытыми цепочками.Чтобы анализировать системы организации очереди, важно знать, является ли процесс выхода из системы организации очереди Пуассоновским процессом.
Четыре модели организации очереди обладают этим свойством.
$$M/M/n$$. По теореме Берка (Burke, 1956 [12]), процесс освобождения $$M/M/n$$ -системы - это Пуассоновский процесс. Вероятности пространства состояний были приведены в (12.2):
$$p(i)=\begin{cases} \frac{A^i}{i!}*p(0), 0 \le i \le n,\\ (\frac An)^{i-n}*p(n), i \ge n. \end {cases}$$.$$M/G/\infty$$. Эта система соответствует Пуассоновскому процессу (секция 7.2). Из секции 6.3 мы знаем, что случайный переход событий Пуассоновского процесса дает новый Пуассоновский процесс.
Эта модель иногда обозначается как система с дисциплиной организации очереди с бесконечным числом обслуживающих приборов. Вероятности состояния отображаются
$$M/G/1-PS$$. Это система организации очереди с одним обслуживающим прибором с общим распределением времени обслуживания и совместным использованием процессора. Вероятности состояния такие же, как и для случая $$M/M/1$$ (13.81):
$$p(i)=(1-A)*A^i, i=0,1,2, \dots$$.В теории сети очередей обычно рассматривают только эти четыре дис-циплины организации очереди. Хотя, например, для системы с потерями Эрланга процесс освобождения будет также Пуассоновский процесс, если мы рассматриваем и блокированных клиентов. Вышеупомянутые четыре системы организации очереди названы симметричными системами организации очереди, так как они симметричны по времени: процесс поступления вызовов и процесс освобождения - оба Пуассоновские процессы, а системы - обратимы (Kelly, 1979 [60]). Процесс называется обратимым, потому что он дает одну и ту же картину диаграмм состояний, когда мы полностью изменяем ход времени.
Кроме $$M/M/n$$ все эти симметричные системы организации очереди имеют общую особенность: клиент обслуживается немедленно по прибытию. Далее мы главным образом рассматриваем узлы $$M/M/n$$, Однако модель $$M/M/1$$ также включает $$M/G/1-PS$$ и $$M/G/1-LCFS-PS$$.
В 1957 г. Джексон, который работал над планированием производственных систем, издал статью с теоремой, теперь её называют теоремой Джексона (1957). Он показал, что $$M/M/n$$ -узлы сети очередей имеют мультипликативную форму. При использовании основной теоремы Burke (1956 [12]) результат Джексона очевиден. Исторически, первая статья о системах последовательной организации очередей была опубликована Джексоном (1954 [45]).
Теорема 14.1 Джексона. Рассмотрим открытую сеть очередей с $$K$$ узлами, удовлетворяющую следующим условиям.
Клиент, который только что освободился при обслуживании на узле $$j$$, немедленно переходит на обслуживание узлом $$k$$ с вероятностью $$p_{jk}$$ или оставляет сеть с вероятностью:
$$1-\sum_{k=1}^k p_{jk}.$$Клиент может посетить тот же самый узел несколько раз, если $$p_{kk} > 0$$. Средняя интенсивность прибытия $$\Lambda_k$$ в узле $$k$$ получена с использованием уравнений равновесия потока:
$$\Lambda_k=\lambda_k + \sum_{j=1}^k \Lambda_j*p_{jk}$$.Пусть $$p(i_1, i_2 \dots, i_К) $$ обозначает пространство вероятностей состояний, согласно предположению о статистическом равновесии, то есть вероятности, что есть $$i_k$$ клиентов на узле $$k$$. Кроме того, мы принимаем, что:
$$\frac{\Lambda_k}{\mu_k}=A_k < n_k.$$Тогда пространство вероятностей состояний может быть получено в мультипликативной форме:
$$p(i_1, i_2, \dots , i_K)=\Pi_{k=1}^K p_k(i_k).$$Для узла $$k$$ здесь $$p_k(i_k) $$ - вероятности состояния системы организации очереди $$M/M/n$$ с интенсивностью прибытия $$\Lambda_k$$ и скоростью обслуживания $$\mu_k$$ (14.1). Предложенная нагрузка $$\Lambda_k /\mu_k$$ к узлу $$k$$ должна быть меньше, чем емкость $$n$$ узла, чтобы получить статистическое равновесие (14.6).
Ключевая точка теоремы Джексона: каждый узел можно рассматривать независимо от всех других узлов и что вероятности состояний можно определить, используя C-формулу Эрланга. Это значительно упрощает вычисление вероятностей пространства состояний. Доказательство теоремы было получено Джексоном в 1957 г., и там показано, что решение удовлетворяет уравнениям равновесия для статистического равновесия.
Первая модель Джексона, таким образом, имеет дело только с открытыми сетями очередей.
Во второй модели Джексона (Джексон, 1963) интенсивность прибытия извне:
$$\lambda=\sum_{j=1}^k \lambda_j.$$Может зависеть от текущего числа клиентов в сети. Кроме того, \ik может зависеть от числа клиентов в узле $$k$$. Таким способом, мы можем моделировать закрытые, открытые или смешанные сети очередей. Во всех трех случаях вероятности состояния имеют мультипликативную форму.
Модель Gordon Newell (1967 [31]), которая часто цитируется в литературе, может рассматриваться как специальный случай второй модели Джексона.
(рис 14.2) Диаграмма переходов состояний открытой сети очередей, состоящей из двух последовательных M/M/1-систем.Pис.14.2 показывает открытую сеть очередей из двух последовательных M/M/1-узлов. Соответствующая диаграмма переходов состояний дается на рис.14.3. Ясно, что диаграмма переходов состояний необратима: между двумя соседними состояниями поток двигается только в одном направлении, (см. секцию 10.2). Очевидно, что мультипликативной формы здесь нет. Однако если мы решаем уравнения равновесия, чтобы получить вероятности состояний, то находим решение, которое может быть написано в мультипликативной форме:
$$p(i,j)=p(i)*p(j),\\ p(i,j)=\{(1-A_1)*A_1^i\}*\{(1-A_2)*A_2^j\},$$где $$A_1 = \lambda / \mu_1$$ и $$A_2 = \lambda / \mu_2.$$ Вероятности состояния могут быть выражены в мультипликативной форме $$p(i, j) = p(i)*p(j) $$, где $$p(i) $$ - вероятности состояния для $$M/M/1$$ -системы с предложенной нагрузкой $$A_1$$ и вероятностью состояния $$p(j) $$ для системы $$M/M/1$$ с предложенной нагрузкой $$A_2$$. Вероятности состояния рис. 14.3 идентичны соответствующим вероятностям на рис.14.4, имеющим местное равновесие и мультипликативную форму.
(рис 14.3) Диаграмма переходов состояний для открытой сети очередей, показанной в рис. 14.2. Диаграмма необратима.Таким образом, можно найти систему, которая является обратимой и имеет такие же вероятности состояния, что и необратимая система. На рис.14.3. мы имеем региональное, но не местное равновесие. Если рассматривать квадрат из четырех состояний, то по отношению к внешнему миру будет существовать равновесие, но внутренне процесс будет циркулировать с помощью диагонального сдвига состояний.
При обслуживании заявок клиентов на сетях очередей часто будет возникать "зацикливание", когда заявка клиента посещает один и тот же узел несколько раз. Если мы имеем сеть очередей с заявками зацикливания, где узлы - системы $$M/M/n,$$ то процессы поступления вызовов к отдельным узлам не будут Пуассоновскими процессами. Так или иначе, мы можем вычислить вероятности состояния, как будто это отдельные независимые узлы $$M/M/n$$ -системы. Это объясняется на следующем примере.
(рис 14.4) Диаграмма переходов состояний для двух независимых M/M/1-систем организации очереди с идентичной интенсивностью прибытия, но различными средними временами обслуживания. Диаграмма обратима.
Прохождение информации с обратной связью приведено в Примере 14.3.1. В этом примере клиенту, который только что закончил свое обслуживание на узле 2, разрешается возвращение к узлу 1 с вероятностью $$p_{21}$$.
С вероятностью клиент покидает систему. Уравнения равновесия потока (14.5) дают полную интенсивность прибытия к каждому узлу, и $$p_{21}$$ должен быть выбран таким, чтобы $$A_1 /\mu_1$$ и $$A_2 /\mu_2$$ были меньше, чем единица. Предполагая, что $$\lambda_1 \to 0$$ и $$p_{ 21} \to 1$$,, мы понимаем, что реализуемые процессы поступления вызовов не Пуассоновские процессы. Новая заявка от клиента поступает редко, но если поступает и будет введена в систему, то она будет циркулировать относительно долгое время. Число обращений будет геометрически распределено, и интервал поступления - сумма этих двух времен обслуживания. То есть когда в системе есть один (или больше) клиент, интенсивность поступления к каждому узлу будет относительно высока, тогда как если нет никаких клиентов, то интенсивность поступления будет очень низка. Процесс поступления вызовов будет взрывной.
Ситуация похожа на разложение экспоненциального распределения во взвешенную сумму Эрланговского распределения k - ого порядка, с геометрическими коэффициентами веса (секция 4.4). Вместо того, чтобы рассматривать единственное экспоненциальное распределение интервала, мы можем анализировать k фаз (рис.4.9) и рассматривать каждую фазу как поступление. Следовательно, процесс поступления вызовов преобразуется из Пуассоновского процесса в процесс с взрывным поступлением.
В реальной сети передачи данных пакеты будут иметь одну и ту же постоянную длину и поэтому одно и то же время обслуживания на всех линиях связи и узлах с равной скоростью обслуживания. Теория сети очередей принимает, что пакет (клиент) производит выбор нового времени обслуживания на каждом узле. Это - необходимое предположение для мультипликативной формы. Такое предположение было впервые исследовано Клейнроком (1964 [65] ), и, оказывается, оно дает хорошее приближение к практике.
Мы интересуемся вероятностями состояния, определенными $$p(i_1, i_2,, \dots, i_k \dots, i_K) $$, где $$i_K$$ - число клиентов в узле $$k(1 \le k \le K) $$.
Расчет открытых сетей прост. Сначала мы решаем уравнение равновесия потока (14.5) и получаем объединенную интенсивность прибытия к каждому узлу ( $$A_k$$ ). Комбинируя интенсивности прибытия с распределением времени обслуживания ( $$A_k$$ ), получаем предложенную нагрузку $$A_k$$ на каждом узле и затем, рассматривая Эрланговскую систему с ожиданием, находим вероятности состояния для каждого узла.
Исследование закрытых сетей с очередями намного сложнее, чем открытых. Мы знаем только относительную нагрузку на каждом узле, а не абсолютную нагрузку, то есть c $$\Lambda_j$$ получена, но $$c$$ неизвестно. Можно получить относительную нормализованную вероятность состояния. Наконец, нормализуя, мы получим нормализованные вероятности состояния. К сожалению, нормализация подразумевает, что необходимо суммировать все вероятности состояний, то есть вычислить каждую (нормализованную) вероятность состояния. Число состояний увеличивается быстро с увеличением числа клиентов и/или узлов. В общем случае, можно рассматривать только маленькие системы. Сложность этой задачи подобна сложности задачи многоразмерных систем с потерями (Лекция 10).
Мы покажем, как алгоритм свертывания может быть применен к сетям очередей. Алгоритм соответствует алгоритму свертывания для систем с потерями (Лекция 10). Рассмотрим сеть очередей с $$K$$ узлами и единственной цепочкой очередей с $$S$$ клиентами. Принимаем условие, что системы организации очереди на каждом узле симметричны (секция 14.2). Алгоритм имеет три шага.
где:
$$q_{12}(i)=\sum_{x=0}^i q_1(x)*q_2(i-x), \quad i=0,1, \dots S$$Когда для всех узлов получены свертки, получаем:
$$q_{1,2, \dots, K}=q_{1,2,\dots, K-1}*q_K.$$Так как общее количество клиентов задано ( $$S$$ ), существует только состояние одной объединенной системы - $$q_{1,2, \dots , K(S)} ,$$ и поэтому это макросостояние должно иметь вероятность появления, равную единице. Мы может тогда нормализовать все микровероятности состояний.
Когда выполняется последнее свертывание, можно получить критерии качества работы для последнего узла. Изменяя порядок свертывания узлов, получим критерии качества работы всех узлов.
Мы рассматриваем модель восстановления машин Пальма, введенную в секции 12.5, как закрытую сеть организации очередей (рис.14.5). Есть $$S$$ клиентов и терминалов. Среднее время раздумья равно $$\mu^{-1}$$, и среднее время обслуживания центральным процессором - $$\mu_2^{-1}$$. В терминологии сети очередей есть два узла: первый узел является терминалом, то есть $$M/G/\infty$$ (фактически, это $$M/G/S$$ - система, но так как число клиентов ограничено S, которое может быть достаточно большим, это соответствует системе M/G/oo), и второй узел - центральный процессор, то есть $$M/M/1$$ - система с сервисной интенсивностью $$\mu_2$$.
Потоки к узлам равны ( $$\Lambda_1 = \Lambda_2 = \Lambda$$ ), относительная нагрузка в узле 1 узле 2
$$\alpha_1=\Lambda / \mu_1$$и
$$\alpha_2=\Lambda / \mu_2,$$соответственно.
Если рассматривать каждый узел как изолированный, мы получаем вероятности состояния каждого узла, $$q_1(i) $$ и $$q_2(j) $$. Свертывая $$q_1(i) $$ и $$q_2( j) $$, получаем $$q_{12}(x) $$, $$(0 \le x \le S) $$, как показано в Таблице 14.1.
Последний элемент с $$S$$ клиентами (не нормализованная вероятность) $$q_{12}(S) $$ состоит из:
$$q_{12}(S)=\alpha_2^S*1+\alpha_2^{S-1}*\alpha_1+\alpha_2^{S-2}*\frac{\alpha_1^2}{2!}+ \dots +1*\frac{\alpha_1^S}{S!}$$Где:
$$\varrho=\frac{\alpha_1}{\alpha_2}=\frac{\mu_2}{\mu_1}$$
(рис 14.5) Модель восстановления машин сети очередей с двумя узлами. Терминалы соответствуют одному узлу, где задачи всегда находят свободный терминал, в то время как центральный процессор, обрабатывающий заявки терминала - M/M/1-узел| Состояние $$i$$ | Узел 1 $$q_1(i)$$ | Узел 2 $$q_2(i) $$ | Сеть очередей $$q_{12}=q_1*q_2$$ |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | $$\alpha_1$$ | $$\alpha_2$$ | $$\alpha_1+\alpha_2$$ |
| 2 | $$\frac{\alpha_1^2}{2!}$$ | $$\alpha_2^2$$ | $$\alpha_2^2+\alpha_1*\alpha_2+\frac{\alpha_1^2}{2!}$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ |
| $$i$$ | $$\frac{\alpha_1^i}{i!}$$ | $$\alpha_2^i$$ | $$\vdots$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ |
| $$S$$ | $$\frac{\alpha_1^S}{S!}$$ | $$\alpha_2^S$$ | $$q_{12}(S)$$ |
Вероятность, что все терминалы находятся в режиме " раздумья ", отображается последним элементом (нормализованной суммы) (S терминалы в узле 1, нулевые терминалы в узле 2):
$$\frac{\frac{\varrho^S}{S!}}{1+\varrho+\frac{\varrho^2}{2!}+\frac{\varrho^3}{3!}+\dots +\frac{\varrho^S}{S!}}=E_{1,S}(\varrho)$$Это B- формула Эрланга. Таким образом, результат соответствует результату, полученному в секции 12.5. Заметим, что $$\lambda$$ появляется в той же самой степени во всех элементах $$q_{1,2} (S) $$ и поэтому сокращается, когда мы нормализуем вероятности состояний.
В 1971 г. Бузен (J. P. Buzen) ввел модель с центральным сервером (рис.14.6), чтобы рассмотреть мультипрограммную компьютерную систему с одним центральным процессором и множеством каналов ввода-вывода (периферийные модули).
(рис 14.6) Система организации очереди с центральным сервером, состоящая из одного центрального сервера и (K-1) каналов ввода-вывода. В системе циркулирует фиксированное число задач - S.Число периферийных модулей обозначено $$K-1$$, как это можно видеть на рис.14.6, который также показывает
Бузен (Buzen) составил схему оценки этой системы. Схема - специальный случай алгоритма свертывания. Проиллюстрируем это для случая $$S 4$$ клиента, $$K 3$$ узла и:
$$\mu_1=\frac{1}{28}, \quad \mu_2=\frac{1}{40}, \quad \mu_3=\frac{1}{280},\\ p_{11}=0.1, \quad p_{12}=0.7, \quad p_{13}=0.2.$$Относительные нагрузки равны:
$$\alpha_1=1,\\ \alpha_2=1,\\ \alpha_3=2.$$Если мы применяем алгоритм свертывания, то получаем результаты, показанные в Таблице 14.2. Элемент $$q_{123}(4) $$ состоит из:
$$q_{123}(4)=1*16+2*8+3*4+4*2+5*1=57.$$Узел 3 обслуживает клиентов во всех состояниях, кроме состояния $$q_3 (0) \times q_{12} (4) = 5$$. Поэтому степень использования узла 3 равна $$a_3 = 52/57$$. На основании относительных нагрузок получаем точные нагрузки:
$$a_1=\frac{26}{57},\\ a_2=\frac{26}{57},\\ a_3=\frac{52}{57}$$Среднее число клиентов в узле 3:
$$L_3=\{1*(4*2)+2*(3*4)+3*(2*8)+4*(1*16)\}/57,\\ L_3=\frac{144}{57}.$$Изменяя порядок свертывания, получаем
| Сост. | Узел 1 | Узел 2 | Узел 1*2 | Узел 3 | Сеть очередей |
|---|---|---|---|---|---|
| $$i$$ | $$q_1(i)$$ | $$q_2(i)$$ | $$q_{12}=q_1*q_2$$ | $$q_3$$ | $$q_{123}=(Q_1*q_2)*q_3$$ |
| 0 | 1 | 1 | 2 | 2 | 4 |
| 1 | 1 | 1 | 3 | 4 | 11 |
| 2 | 1 | 1 | 3 | 4 | 11 |
| 3 | 1 | 1 | 4 | 8 | 26 |
| 4 | 1 | 1 | 5 | 16 | 57 |
Сумма всех
Применяя формулу Литтла, получаем среднее время пребывания $$W_k = L_k / k:$$
$$W_1=45.23,\\ W_2=64.62,\\ W_3=775.38$$Мы рассматриваем сеть организации очереди с $$K$$ узлами и $$S$$ клиентами (все принадлежат одной цепочке). Относительные нагрузки узлов обозначены $$\alpha_k(k = 1, 2, \dots , K) $$. Алгоритм рекурсивный по числу заявок от клиентов сети, то есть сеть с $$x + 1$$ заявкой от клиентов получается из сети, обслуживающей $$x$$ заявок.
Примем, что среднее число заявок оот клиентов в узле $$k$$ равно $$L_k (x) $$, где $$x$$ - общее количество клиентов в сети. Очевидно, что:
$$\sum_{k=1}^KL_k(x)=x.$$Алгоритм выполняется рекурсивно за два шага.
Шаг 1.
Увеличьте число заявок от клиентов от $$x$$ до $$(x+1) $$. Согласно теореме прибытия, $$(x+ 1) $$ -ый клиент поступит в систему, когда система с $$x$$ клиентами находится в статистическом равновесии. Следовательно, среднее время пребывания (время ожидания + время обслуживания) в узле $$k$$:
для M/M/1, M/G/1-PS M/G/1-LCFS-PR
для $$M/G/\infty$$:
$$W_k(x+1)=s_k.$$где $$s_k-$$ среднее время обслуживания в узле $$k$$, который имеет $$n_k$$ приборов. Для вычисления средних времен ожидания мы можем принять $$FCFS$$ -дисциплину организации очереди.
Шаг 2.
Используя формулу Литтла ( $$L = \lambda W$$ ), которая применима для всех систем в статистическом равновесии, для узла $$k$$ мы получим:
$$L_k(x+1)=c*\lambda_k*W_k(x+1),$$где $$\lambda_k$$ - относительная интенсивность поступления заявок к узлу $$k$$. Константа нормализации c получена, исходя из общего количества клиентов:
$$\sum_{k=1}^KL+k(x+1)=x+1.$$За эти два шага мы выполнили рекурсию от $$x$$ до $$(x + 1) $$ заявок. Для $$x = 1$$ нет никакого времени ожидания в системе, и $$W_k (1) $$ равняется среднему времени обслуживания $$s_k$$. Ниже был показан $$MVA$$ -алгоритм для одного узла обслуживания, но довольно просто делать вывод для узлов или с несколькими обслуживающими приборами или с бесконечным числом обслуживающих приборов.
Применим
| Узел 1 | Узел 2 | Узел 3 | |
|---|---|---|---|
| $$S=1$$ | $$W_1(1)=28$$ | $$W_2(1)=40$$ | $$W_3(1)=280$$ |
| $$L_1(1)=c*1*28$$ | $$L_2(1)=c*0.7*40$$ | $$L_3(1)=c*0.2*280$$ | |
| $$L_1(1)=0.25$$ | $$L_2(1)=0.25$$ | $$L_3(1)=0.50$$ | |
| $$S=2$$ | $$W_1(2)=1.25*28$$ | $$W_2(2)=1.25*40$$ | $$W_3(2)=1.50*280$$ |
| $$L_1(2)-c*1*1.25*28$$ | $$L_2(2)c*0.7*1.25*40$$ | $$L_3(2)=c*0.2*1.50*280$$ | |
| $$L_1(2)=0.4545$$ | $$L_2(2)=0.4545$$ | $$L_3(2)=1.0909$$ | |
| $$S=3$$ | $$W_1(3)=1.4545*28$$ | $$W_2(3)=1.4545*40$$ | $$W_3(3)=2.0909*280$$ |
| $$L_1(3)=c*1*1.4545*28$$ | $$L_2(3)=c*0.7*1.4545*40$$ | $$L_3(3)=c*0.2*2.0909*280$$ | |
| $$L_1(3)=0.6154$$ | $$L_2(3)=0.6154$$ | $$L_3(3)=1.7692$$ | |
| $$S=4$$ | $$W_1(4)=1.6154*28$$ | $$W_2(4)=1.6154*40$$ | $$W_3(4)=2.7692*280$$ |
| $$L_1(4)=c*1*1.6154*28$$ | $$L_2(4)=c*0.7*1.6154*40$$ | $$L_3(4)=c*0.2*2.7692*280$$ | |
| $$L_1(4)=0.7368$$ | $$L_2(4)=0.7368$$ | $$L_3(4)=2.5263$$ |
Естественно, что результат идентичен тому, который получен при применении алгоритма свертывания. Время пребывания на каждом узле (выраженное через единицу времени):
$$W_1(4)=1.6154*28=45.23\\ W_2(4)=1.6154*40=64.62,\\ W_3(4)=2.7693*280=775.38$$Мы рассматриваем модель Пальма восстановления машин с $$S$$ источниками, конечным временем раздумья и центральным процессором (время обслуживания равняется одной единице времени). Как было упомянуто в секции 12.5.2, эта модель
| Узел 1 | Узел 2 | |
|---|---|---|
| $$S=1$$ | $$W_1(1)=A$$ | $$W_2(1)=1$$ |
| $$L_1(1)=c*1*A$$ | $$L_2(1)=c*1*1$$ | |
| $$L_1(1)=\frac{1}{1+A}$$ | $$L_2(1)=\frac{1}{1+A}$$ | |
| $$S=2$$ | $$W_1(2)=A$$ | $$W_2(2)=1+\frac{1}{1+A}$$ |
| $$L_1(2)=c*1*A$$ | $$L_2(2)=c*1*(1+\frac{1}{1+A})$$ | |
| $$L_1(2)=A*\frac{1+A}{1+A+\frac{a^2}{2!}}$$ | $$L_2(2)=2-A*\frac{1+A}{1+A+\frac{a^2}{2!}}$$ |
Мы знаем, что длина очереди в терминалах (узел 1) равна обслуженной нагрузке, измеренной в Эрлангах - в системе, и что все другие заявки клиенты находятся в центральном процессоре (узел 2). Мы, таким образом, имеем:
| Узел 1 | Узел 2 | |
|---|---|---|
| $$S=x$$ | $$W_1(x)=A$$ | $$W_2(x)=1+L_2(x-1)$$ |
| $$L_1(x)=c*A$$ | $$L_2(x)=c*\{1+L_2(x-1)\}$$ | |
| $$L_1(x)=A*\{1-E_x(A)\}$$ | $$L_2(x)=x-A*\{1-E_x(A)\}$$ |
Из этого получаем нормировочную константу $$c=1-E_x(A) $$ и находим для $$(x+1) $$ того клиента:
$$L_1(x+1)+L_2(x+1)=c*A+c\{1+L_2(x)\},\\ =c*A+c*\{1+x-A*(1-E_x)\}\\ =x+1,\\ E_{x+1}=\frac{A*E_x}{x+1+A*E_x},$$потому что $$c=1-E_{x+1}$$. Это рекурсивная формула для системы B-Эрланга.
В 1975 г. вторая модель Джексона была далее обобщена Baskett, Chandy, Muntz и Palacios (1975 [4]). Они показали, что сети очередей с более чем одним типом клиентов также имеют мультипликативную форму, при условии, что:
BCMP -сети могут быть рассчитаны с помощью многомерного алгоритма свертывания и многомерного
Смешанные сети очередей (открытые и закрытые) рассчитываются сначала путем вычисления нагрузки от открытых цепочек в каждом узле. Эту нагрузку нужно обслуживать так, чтобы соблюдалось статистическое равновесие.
Производительность этих узлов уменьшается на эту нагрузку, и закрытая сеть очередей рассчитывается уже с меньшей производительностью. Так что главная проблема состоит в расчете закрытых сетей. Для этого мы можем использовать много алгоритмов, среди которых самыми важными являются алгоритмы свертывании и Алгоритм Средней величины (
В этой секции мы рассматриваем сети очередей с более чем одним типом клиентов. Клиенты одного и того же типа принадлежат заданному классу или цепочке. В Лекции 10 мы рассматривали системы с потерями, обслуживающие несколько типов клиентов (услуг), и замечали, что может быть получена мультипликативная форма и может быть применен алгоритм свертывания.
Pис.14.7 иллюстрирует систему организации очереди с одним обслуживающим прибором и с $$N = 2$$ типа заявок от клиентов (цепочек). Заявки от клиентов прибывают в систему согласно Пуассоновскому потоку вызовов с интенсивностью $$\lambda_j ( j = 1, 2) $$. Состояние $$(i, j) $$ определено как состояние $$i$$ заявок клиента типа 1 и $$j$$ заявок от клиента типа 2. Интенсивность обслуживания $$\mu_{i,j}$$ в состоянии $$(i, j) $$ может быть выбрана зависящей от состояния, например:
$$\mu_{ij}=\frac{i}{i+j}*\mu_1+\frac{j}{i+j}*\mu_2.$$Интенсивности обслуживания могут интерпретироваться несколькими способами, но они должны соответствовать симметричной системе организации очереди при наличии одного обслуживающего прибора.
Одна из интерпретаций соответствует совместному использованию процессора, то есть все $$(i+j) $$ клиентов совместно используют обслуживающий прибор, а производительность сервера является постоянной. Зависимость состояния от типа клиента происходит из-за разности в интенсивности обслуживания двух типов клиентов. То есть число заявок от клиентов, покидающих систему, в единицу времени зависит от типа клиентов, обслуживаемых в настоящее время.
Можно показать, что обслуживаемая заявка с вероятностью $$i/(i+j) $$ принадлежит к типу 1 и с вероятностью $$j/(i+j) $$ - к типу 2 независимо от дисциплины обслуживания.
Pис.14.8 дает часть диаграммы переходов состояний. Диаграмма обратима, так как поток по часовой стрелке равняется потоку против часовой стрелки. Следовательно, есть местное равновесие, и все вероятности состояния могут быть выражены с помощью $$p(0, 0) $$:
(рис 14.8) M/M/1-система организации очереди с двумя типами (цепочками) клиентов.(рис 14.7) Диаграмма переходов состояний для многомерной системы M/M/1 с совместным использованием процессора.$$p(i,j)=\frac{A_1^i}{i!}*\frac{A_2^j}{j!}*(i+j)!*p(0,0).$$Используя нормализацию, получаем $$p(0, 0) $$:
$$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty} p(i,j)=1$$По сравнению с многомерной B-формулой Эрланга, здесь существует дополнительный коэффициент $$(i+j)$$!. Мультипликативная форма выражения между цепочками (на узле) потеряна, но мультипликативная форма между узлами все еще поддерживается.
Примем, что есть $$N$$ различных типов клиентов (цепочек) вероятности состояния для единственного узла, и получаем:
$$p(i)=p(i_1, i_2, \dots, i_N)=\left \{ \Pi_{j=1}^N A_j^{i_j} \right \}* \frac{\left \{ \sum_{j=1}^Ni_j \right \}}{\left \{ \Pi_{j=1}^N i_j! \right \}}*p(0).$$Это может быть выражено полиномиальным распределением (4.37):
$$p(i)=\left \Pi_{j=1}^N A_{j^{i_j} \right \}* {i_1+i_2 +\dots +i_n\choose i_1, i_2, \dots, i_n}*p(0).$$Для бесконечного числа мест ожидания вероятности состояния общего количества клиентов:
$$p(j)=p\{i_1+i_2+\dots +i_N=j\}.$$Если $$\mu_i = \mu$$, то система идентична $$M/M/1$$ - системе с интенсивностью поступления $$\lambda=\sum_i \lambda_i$$:
$$p(j)=(A_1+A_2+ \dots +A_N)^j*p(0)\\ =A^j*(1-A) $$Чтобы получить этот результат, используется биноминальное разложение. Диаграмма переходов состояний на рис.14.8 может также интерпретироваться как диаграмма переходов состояний системы M/G/1-LCFS-PR (приоритетное возвращение к работе). Очевидно, что M/G/1-LCFS-PR обратимо, потому что процесс в диаграмме переходов состояний проходит одинаково как вперед из нуля, так и назад, чтобы вернуться в нуль.
Можно показать, что диаграмма переходов состояний нечувствительна к распределению времени обслуживания, так что она справедлива для системы организации очереди $$M/G/1$$. Pис.14.8 соответствует диаграмме переходов состояний для системы организации очереди с одним обслуживающим прибором и гиперэкспоненциально распределенными временами обслуживания (см. (10.7)), например. $$M/H_2 /1-LCFS-PR$$ или $$PS$$.
Заметим, что для $$M/M/1 (FCFS, LCFS, SIRO) $$ необходимо, чтобы все клиенты имели одно и то же среднее время обслуживания, которое должно быть экспоненциально распределенным. Другими словами, обслуживаемый клиент не будет случайным клиентом среди $$(i+j) $$ клиентов в системе.
В заключение заметим, что системы организации очереди c одним обслуживающим прибором и большим количеством типов клиентов будут иметь мультипликативную форму только тогда, когда узел имеет симметричную систему организации очереди: $$M/G/1-PS, M/G/1-LCFS -PR$$ или $$M/M/1$$ с одним и тем же временем обслуживания для всех клиентов.
Мы можем также получить рассмотренные выше результаты для системы с $$n$$ обслуживающими приборами. Для $$(i+j) \le n$$
получаем ту же самую вероятность относительного состояния, что и для многоразмерной B-формулы Эрланга. Для $$(i+j)>n$$ получаем решение только для простого случая, когда $$\mu_i=\mu$$ то есть когда все типы (цепочки) клиентов имеют одно и то же среднее время пребывания в системе. Мы тогда находим вероятности состояния, данные в (10.9), и система имеет мультипликативную форму. $$M/M/1$$ можно рассматривать как частный случай $$M/M/n$$ и по аналогии с системами с потерями (Лекция 12).
Рассмотрение сетей очередей, имеющих много цепочек, аналогично случаю с единственной цепочкой. Основное различие состоит в том, что классическая формула и алгоритмы заменены соответствующей многомерной формулой.
Алгоритм по существу такой же, как и в случае единственной цепочки.
Шаг 1. Рассмотрим каждую цепочку так, как будто она является единственной в сети. Найдите относительную нагрузку в каждом узле, решая уравнения равновесия потока (14.5). В произвольном опорном узле принимаем, что нагрузка равна единице. Для каждой цепочки мы можем выбрать в качестве опорного узла свой узел. Для цепочки $$j$$ в узле $$k$$ относительная интенсивность прибытия $$\lambda_k^j$$ (используем верхний индекс, чтобы указать номер цепочки) получается из:
$$\lambda_k^j=\sum_{i=1}^Kp_{ik}^j*\lambda_i^j, \quad j=1, \dots, N$$где:
$$K$$ - число узлов,
$$N$$ - число цепочек,
$$p_{ik}^j$$ - вероятность, что клиент цепочки $$j$$ перейдет с узла $$i$$ к узлу $$k$$.
Мы выбираем произвольный узел как
где $$s+k^j$$ - среднее время обслуживания в узле $$k$$ для клиентов цепочки $$j$$. Обратите внимание, что j - индекс, а не степень.
Шаг 2. На основе значений относительных нагрузок, найденных на шаге 1, мы получаем многомерные вероятности состояния для каждого узла. Каждый узел рассматривается отдельно. Далее, усекаем пространство состояний согласно числу клиентов в каждой цепочке. Например, для узла $$k (1 \le k \le K) $$:
$$p_k=p_k(i_1, i_2, \dots, i_N), \quad 0 \le i_j \le S_j, \quad j=1,2,\dots, N,$$где $$S_j$$ - число заявок от клиентов в цепочке $$j$$.
Шаг 3. Чтобы найти вероятности состояния полной сети, сверты ваем вероятности состояния каждого узла подобно случаю единственной цепочки, - разница в том, что в данном случае свертывание многомерно. Когда выполним последнее свертывание, получим критерии качества работы последнего узла. Снова изменяя порядок узлов, мы можем получить критерии качества работы всех узлов.
Общее количество состояний увеличивается быстро. Например, если цепочка $$j$$ имеет $$S$$ заявок клиентов, то общее количество состояния в каждом узле становится:
$$\Pi_{j=1}^N(S_j+1)$$Пути $$N$$ цепей с $$S_j$$ заявками в цепи $$j$$ могут быть распределены в сети очередей с $$K$$ узлами:
$$C=\Pi_{j=1}^NC(S_j,k_j$$где $$k_j (1 \le k_j < K) $$ - номер узлов, посещенных клиентом в цепи $$j$$, и:
$$C(S_j, k_j)={S_j+k_j-1\choose k_j-1}={S_j+k_j-1\choose S_j}.$$Алгоритм лучше всего проиллюстрировать примером.
Уже отмечалось в Примере 14.4.1, что эта система может быть смоделирована как сеть очередей с двумя узлами.
Узел 1 соответствует терминалам (машинам), в то время как узел 2 - центральному процессору (ремонтником). Узел 2 - система с одним обслуживающим прибором, тогда как узел 1 смоделирован как система с бесконечным числом обслуживающих приборов. Число клиентов в цепочках - ( $$S_1 = 2, S_2 = 3$$ ) и среднее время обслуживания в узле $$k - s_k^j.$$
Относительная нагрузка цепочки 1 обозначена $$\alpha_1$$ в узле 1 и $$\alpha_2$$ в узле 2. Точно так же нагрузка в цепочке 2 обозначена $$\beta_1$$ и соответственно $$\beta_2$$. Применяя алгоритм свертывания, получаем:
Шаг 1.
Цепочка 1: $$S_1 = 2$$ клиента
Относительная нагрузка: $$\alpha_1=\lambda_1*s_1^1, \quad \alpha_2=\lambda_1*s_2^1$$.
Цепочка 2: $$S_2 = 3$$ клиента
Относительная нагрузка: $$\beta_1=\lambda_1*s_1^2, \quad \beta_2=\lambda_2*s_2^2$$.
Шаг 2.
Для узла 1 ( IS ) вероятность относительного состояния (см10.9):
Для узла 2 (обслуживающий прибор) (см.14.15) мы имеем:
$$q_2(0,0)1 \qquad q_2(0,2)=\beta_2^2\\ q_2(1,0)=\alpha_2 \qquad q_2(1,2)=3*\alpha_2*\beta_2^2\\ q_2(2,0)=\alpha_2^2 \qquad q_2(2,2)=6*\alpha_2^2*\beta_2^2\\ q_2(0,1)=\beta_2 \qquad q_2(0,3)=\beta_2^3\\ q_2(1,1)=2*\alpha_2*\beta_2 \qquad q_2(1,3)=4*\alpha_2*\beta_2^3\\ q_2(2,1)=3*\alpha_2^2*\beta_2 \qquad q_2(2,3)=10*\alpha_2^2*\beta_2^3$$Шаг 3.
Затем мы делаем свертку. Мы знаем, что общее количество клиентов - (2,3), то есть нас интересуют только состояния (2, 3):
$$q_[12}(2,3)=q_1(0,0)*q_2(2,3)+q_1(1,0)*q_2(1,3)\\ +q_1(2,0)*q_2(0,3)+q_1(0,1)*q_2(2,2)\\ +q-1(1,1)*q_2(1,2)+q_2(2,1)*q_2(0,2)\\ +q_1(2,2)*q_2(2,1)+q_1(1,2)*q_2(1,1\\ +q_1(2,2)*q_2(0,1)+q-1(0,3)*q_2(2,0)\\ +q_1(1,3)*q_2(1,0)+q_1(2,3)*q_2(0,0)$$Использование полученных значений дает:
$$q_{12}(2,3)=+1*10*\alpha_2^2*\beta_2^3+\alpha_1*4*\alpha_2*\beta_2^3\\ +\frac{\alpha_1^2}{2}*\beta_2^3+\beta_1*6*\alpha_2^2*\beta_2^2\\ +\alpha_1*\beta_1*3*\alpha_2*\beta_2^2+\frac{\alpha_1*\beta_1^2}{2}*\beta_2^2\\ +\frac{\beta_1^2}{2}*3*\alpha_2^2*\beta_2+\frac{\alpha_1*\beta_1^2}{2}*2*\alpha_2*\beta_2\\ +\frac{\alpha_1^2*\beta_1^2}{4}*\beta_2+\frac{\beta_1^3}{6}*\alpha_2^2\\ +\frac{\alpha_1*\beta_1^3}{6}*\alpha_2+\frac{\alpha_1^2*\beta_1^3}{12}*1$$Обратите внимание, что $$\alpha_1$$ и $$\alpha_2$$ (цепочка 1) появляются во второй степени, тогда как $$\beta_1$$ и $$\beta_2$$ (цепочка 2) - в третьей степени, что соответствует числу клиентов в каждой цепочке. Из-за этого существенны только относительные нагрузки, а абсолютные вероятности получают нормализацией, делением всех элементов $$q_{12}(2, 3) $$. Теперь достаточно просто получить детальные вероятности состояния. Только в состоянии с элементами $$(\alpha_1^2 * \beta_1^3)/12$$ центральный процессор (ремонтник) свободен. Если два типа клиентов идентичны, модель упрощается и сводится к модели Пальма восстановления машин с 5-ю терминалами.
В этом случае мы имеем:
$$E_{1,5}(x)=\frac{\frac{1}{12}*\alpha_1^2*\beta_1^3}{q_{12}(2,3)}.$$Выбирая, $$\alpha_1 \beta_1 \alpha$$ и $$\alpha_2 \beta_2 1$$, получаем:
$$\frac{\frac{1}{12}*\alpha_1^2*\beta_1^3}{q_{12}(2,3)}=\frac{\frac{\alpha^5}{2}}{10+4 \alpha +\frac 12 \alpha^2+6 \alpha +3 \alpha^2+\frac 12 \alpha^3+\frac 32 \alpha^2+ \alpha^3+\frac 14 \alpha^4+\frac 16 \alpha^3+\frac 16 \alpha^4+\frac{1}{12} \alpha^5}=\\ =\frac{\frac{\alpha^5}{5!}}{1+ \alpha+\frac{\alpha^2}{2}+\frac{\alpha^3}{3!}+\frac{\alpha^4}{4!}+\frac{\alpha^5}{5!}},$$то есть, как и ожидалось, B- формулу Эрланга.
Сети очередей имеют такую же сложность, что и сети с коммутацией каналов и прямой маршрутизацией (секция 11.5 и табл. 11.2). Пространство состояний сети, показанной в таблице 14.3, имеет следующее число состояния для каждого узла:
$$\Pi_{i=0}^N(S_i+1)$$Худший случай - тот, когда каждая цепочка состоит из одного клиента. Тогда число состояний становится $$2^S$$, где $$S$$ - число клиентов.
| Цепочка | Узел $$\begin{matrix}12\dots K \end{matrix}$$ | Число клиентов |
|---|---|---|
| 1 | $$\begin{matrix} \alpha_{11} \alpha_{21} \dots \alpha_{K1} \end{matrix}$$ | $$S_1$$ |
| 2 | $$\begin{matrix} \alpha_{12} \alpha_{22} \dots \alpha_{K2} \end{matrix}$$ | $$S_2$$ |
| $$\dots$$ | $$\dots$$ | $$\dots$$ |
| $$N$$ | $$\begin{matrix} \alpha_{1N} \alpha_{2N} \dots \alpha_{KN} \end{matrix}$$ | $$S_N$$ |
Рассмотрим систему передачи данных с $$K$$ узлами, которые являются независимыми узлами системы организации очереди с одним обслуживающим прибором $$M/M/1$$ (Эрланговская система с ожиданием с одним обслуживающим прибором). Процесс поступления вызовов к узлу $$k$$ - Пуассоновский процесс с интенсивностью $$\lambda_k$$ сообщений (клиентов) в единицу времени. Размер сообщения - экспоненциально распределенное значение со средней величиной $$1/\mu_k$$ [бит]. Пропускная способность узла $$k$$ - равна $$\varphi_k$$ [бит в единицу времени]. Среднее время обслуживания равно:
$$s=\frac{1/\mu_k}{\varphi_k}=\frac{1}{\mu_k \varphi_k}$$Так что средняя скорость обслуживания - $$\mu_k * \varphi_k,$$ а среднее время пребывания определяется (12.34):
$$m_{1,k}=\frac{1}{\mu_k \varphi_k - \lambda_k}$$Вводим следующее линейное ограничение на полную производительность:
$$F=\sum_{k=1}^K \varphi_k$$Для каждого распределения производительности, которая удовлетворяет (14.21), получаем следующее среднее время пребывания для всех сообщений (математическое ожидание вызова):
$$m_1=\sum_{k=1}^K \frac{\lambda_k}{\lambda}*\frac{1}{\mu_k* \varphi_k - \lambda_k}$$где
$$\lambda=\sum_{k=1}^K \lambda_k$$Применяя (13.14), получаем полное среднее время обслуживания:
$$\frac{1}{\mu}=\sum_{k=1}^K \frac{\lambda_k}{\lambda}*\frac{1}{\mu_k}$$Полная предложенная нагрузка тогда:
$$A=\frac{\lambda}{\mu*F}$$Закон Клейнрока для оптимального распределения производительности (Kleinrock, 1964 [65]) сформулирован следующим образом.
Теорема 14.2. Закон квадратного корня Закон квадратного корня (закон Клейнрока): оптимальное распределение производительности ( $$\varphi_k$$ ), которое минимизирует $$m_1$$ (и таким образом общее количество сообщений во всех узлах):
$$\varphi_k=\frac{\lambda_k}{\mu+k}+F*(1-A)\frac{\sqrt{\lambda_k \mu_k}}{\sum_{i=1}^K \sqrt{\lambda_i \mu_i}},$$при условии, что:
$$F > \sum_{k=1}^K \frac{\lambda_k}{\mu_k}$$Доказательство. Вводя множитель $$\vartheta$$ Лагранжа и рассматривая:
$$G=m_1- \vartheta \left \{ \sum_{k=1}^K \varphi_k -F \right \}.$$Минимум $$G$$ получен, если выбирать $$\varphi_k,$$ как приведено в (14.26). С этим оптимальным распределением находим среднее время пребывания:
$$m_1=\frac{\left \{\sum_{k=1}^K \sqrt{\lambda_k/ \mu_k} \right \}^2}{\lambda*F*(1-A)}$$Это оптимальное распределение соответствует тому случаю, когда необходимая минимальная производительность $$\lambda_k/ \mu_j$$ сначала распределена между всеми узлами. Остающаяся производительность (14.24):
$$F-\sum_{k=1}^K=F*(1-A)$$Данная производительность распределена между узлами пропорционально квадратному корню из среднего потока $$\lambda_k/ \mu_k$$.
Если все сообщения имеют одинаковую среднюю величину $$(\mu_k= \mu)$$ то мы можем рассчитать различные затраты в узлах, согласно ограничению, которое фиксирует количество доступных узлов (Kleinrock,1964 [65]).
MVA Закон квадратного корня (закон Клейнрока): оптимальное распределение производительности (, которое минимизирует m1 (и таким образом общее количество сообщений во всех узлах):
$$\varphi_k=\frac{\lambda_k}{\mu+k}+F*(1-A)\frac{\sqrt{\lambda_k \mu_k}}{\sum_{i=1}^K \sqrt{\lambda_i \mu_i}}$$,Сети очередей разделяются на закрытые и открытые сети. В закрытых сетях очередей число клиентов постоянно, тогда как в открытых сетях очередей число клиентов изменяется. В принципе, открытая сеть может быть преобразована в закрытую сеть добавлением дополнительного узла.
Классическая система ожидания Эрланга, $$M/M/n$$, является примером открытой системы организации очереди, тогда как модель восстановления машин Пальма с $$S$$ терминалами - закрытая сеть. Если есть более чем один тип клиентов, сеть может быть смешанной закрытой и открытой сетью. Так как процесс выхода из обслуживания от одного узла обычно вызывает процесс поступления вызовов на другой узел, мы обратим особое внимание на процесс выхода из обслуживания, в особенности, когда он может быть отображен как Пуассоновский процесс. Такие системы исследуются в секции, посвященной симметричным системам организации очереди (секция 14.2).
Состояние сети очередей определяется как одновременное распределение числа клиентов на каждом узле. Если $$K$$ обозначает общее количество узлов, то состояние отображается вектором $$p(i_1, i_2, \dots, i_K) $$, где $$i_k$$ - число клиентов на узле $$k (k = 1, 2, \dots, K) $$.
Часто пространство состояний является очень большим и, решая уравнения равновесия узла, трудно вычислить вероятности состояния. Если каждый узел - симметричная система организации очереди, например, сеть Джексона (секция 14.3), тогда мы будем иметь мультипликативную форму. Вероятности состояния сетей с мультипликативной формой могут быть объединены и получены, используя алгоритм свертывания (секция 14.4.1) с помощью
Сети Джексона могут быть обобщены к BCMP-сети (секция 14.5), где есть $$N$$ типов клиентов. Клиенты одного заданного типа принадлежат так называемой цепочке. Pис.14.1 иллюстрирует пример сети организации очереди с четырьмя цепочками. Когда число цепочек увеличивается, пространство состояний увеличивается соответственно, и точно могут быть вычислены только системы с небольшим количеством цепочек. В случае из многих цепочек сети состояние каждого узла становится многомерным (секция 14.6). Применение мультипликативной формы между узлами, свертывание и
(рис 14.1) Пример сети организации очереди с четырьмя открытыми цепочками.Чтобы анализировать системы организации очереди, важно знать, является ли процесс выхода из системы организации очереди Пуассоновским процессом.
Четыре модели организации очереди обладают этим свойством.
$$M/M/n$$. По теореме Берка (Burke, 1956 [12]), процесс освобождения $$M/M/n$$ -системы - это Пуассоновский процесс. Вероятности пространства состояний были приведены в (12.2):
$$p(i)=\begin{cases} \frac{A^i}{i!}*p(0), 0 \le i \le n,\\ (\frac An)^{i-n}*p(n), i \ge n. \end {cases}$$.$$M/G/\infty$$. Эта система соответствует Пуассоновскому процессу (секция 7.2). Из секции 6.3 мы знаем, что случайный переход событий Пуассоновского процесса дает новый Пуассоновский процесс.
Эта модель иногда обозначается как система с дисциплиной организации очереди с бесконечным числом обслуживающих приборов. Вероятности состояния отображаются
$$M/G/1-PS$$. Это система организации очереди с одним обслуживающим прибором с общим распределением времени обслуживания и совместным использованием процессора. Вероятности состояния такие же, как и для случая $$M/M/1$$ (13.81):
$$p(i)=(1-A)*A^i, i=0,1,2, \dots$$.В теории сети очередей обычно рассматривают только эти четыре дис-циплины организации очереди. Хотя, например, для системы с потерями Эрланга процесс освобождения будет также Пуассоновский процесс, если мы рассматриваем и блокированных клиентов. Вышеупомянутые четыре системы организации очереди названы симметричными системами организации очереди, так как они симметричны по времени: процесс поступления вызовов и процесс освобождения - оба Пуассоновские процессы, а системы - обратимы (Kelly, 1979 [60]). Процесс называется обратимым, потому что он дает одну и ту же картину диаграмм состояний, когда мы полностью изменяем ход времени.
Кроме $$M/M/n$$ все эти симметричные системы организации очереди имеют общую особенность: клиент обслуживается немедленно по прибытию. Далее мы главным образом рассматриваем узлы $$M/M/n$$, Однако модель $$M/M/1$$ также включает $$M/G/1-PS$$ и $$M/G/1-LCFS-PS$$.
В 1957 г. Джексон, который работал над планированием производственных систем, издал статью с теоремой, теперь её называют теоремой Джексона (1957). Он показал, что $$M/M/n$$ -узлы сети очередей имеют мультипликативную форму. При использовании основной теоремы Burke (1956 [12]) результат Джексона очевиден. Исторически, первая статья о системах последовательной организации очередей была опубликована Джексоном (1954 [45]).
Теорема 14.1 Джексона. Рассмотрим открытую сеть очередей с $$K$$ узлами, удовлетворяющую следующим условиям.
Клиент, который только что освободился при обслуживании на узле $$j$$, немедленно переходит на обслуживание узлом $$k$$ с вероятностью $$p_{jk}$$ или оставляет сеть с вероятностью:
$$1-\sum_{k=1}^k p_{jk}.$$Клиент может посетить тот же самый узел несколько раз, если $$p_{kk} > 0$$. Средняя интенсивность прибытия $$\Lambda_k$$ в узле $$k$$ получена с использованием уравнений равновесия потока:
$$\Lambda_k=\lambda_k + \sum_{j=1}^k \Lambda_j*p_{jk}$$.Пусть $$p(i_1, i_2 \dots, i_К) $$ обозначает пространство вероятностей состояний, согласно предположению о статистическом равновесии, то есть вероятности, что есть $$i_k$$ клиентов на узле $$k$$. Кроме того, мы принимаем, что:
$$\frac{\Lambda_k}{\mu_k}=A_k < n_k.$$Тогда пространство вероятностей состояний может быть получено в мультипликативной форме:
$$p(i_1, i_2, \dots , i_K)=\Pi_{k=1}^K p_k(i_k).$$Для узла $$k$$ здесь $$p_k(i_k) $$ - вероятности состояния системы организации очереди $$M/M/n$$ с интенсивностью прибытия $$\Lambda_k$$ и скоростью обслуживания $$\mu_k$$ (14.1). Предложенная нагрузка $$\Lambda_k /\mu_k$$ к узлу $$k$$ должна быть меньше, чем емкость $$n$$ узла, чтобы получить статистическое равновесие (14.6).
Ключевая точка теоремы Джексона: каждый узел можно рассматривать независимо от всех других узлов и что вероятности состояний можно определить, используя C-формулу Эрланга. Это значительно упрощает вычисление вероятностей пространства состояний. Доказательство теоремы было получено Джексоном в 1957 г., и там показано, что решение удовлетворяет уравнениям равновесия для статистического равновесия.
Первая модель Джексона, таким образом, имеет дело только с открытыми сетями очередей.
Во второй модели Джексона (Джексон, 1963) интенсивность прибытия извне:
$$\lambda=\sum_{j=1}^k \lambda_j.$$Может зависеть от текущего числа клиентов в сети. Кроме того, \ik может зависеть от числа клиентов в узле $$k$$. Таким способом, мы можем моделировать закрытые, открытые или смешанные сети очередей. Во всех трех случаях вероятности состояния имеют мультипликативную форму.
Модель Gordon Newell (1967 [31]), которая часто цитируется в литературе, может рассматриваться как специальный случай второй модели Джексона.
(рис 14.2) Диаграмма переходов состояний открытой сети очередей, состоящей из двух последовательных M/M/1-систем.Pис.14.2 показывает открытую сеть очередей из двух последовательных M/M/1-узлов. Соответствующая диаграмма переходов состояний дается на рис.14.3. Ясно, что диаграмма переходов состояний необратима: между двумя соседними состояниями поток двигается только в одном направлении, (см. секцию 10.2). Очевидно, что мультипликативной формы здесь нет. Однако если мы решаем уравнения равновесия, чтобы получить вероятности состояний, то находим решение, которое может быть написано в мультипликативной форме:
$$p(i,j)=p(i)*p(j),\\ p(i,j)=\{(1-A_1)*A_1^i\}*\{(1-A_2)*A_2^j\},$$где $$A_1 = \lambda / \mu_1$$ и $$A_2 = \lambda / \mu_2.$$ Вероятности состояния могут быть выражены в мультипликативной форме $$p(i, j) = p(i)*p(j) $$, где $$p(i) $$ - вероятности состояния для $$M/M/1$$ -системы с предложенной нагрузкой $$A_1$$ и вероятностью состояния $$p(j) $$ для системы $$M/M/1$$ с предложенной нагрузкой $$A_2$$. Вероятности состояния рис. 14.3 идентичны соответствующим вероятностям на рис.14.4, имеющим местное равновесие и мультипликативную форму.
(рис 14.3) Диаграмма переходов состояний для открытой сети очередей, показанной в рис. 14.2. Диаграмма необратима.Таким образом, можно найти систему, которая является обратимой и имеет такие же вероятности состояния, что и необратимая система. На рис.14.3. мы имеем региональное, но не местное равновесие. Если рассматривать квадрат из четырех состояний, то по отношению к внешнему миру будет существовать равновесие, но внутренне процесс будет циркулировать с помощью диагонального сдвига состояний.
При обслуживании заявок клиентов на сетях очередей часто будет возникать "зацикливание", когда заявка клиента посещает один и тот же узел несколько раз. Если мы имеем сеть очередей с заявками зацикливания, где узлы - системы $$M/M/n,$$ то процессы поступления вызовов к отдельным узлам не будут Пуассоновскими процессами. Так или иначе, мы можем вычислить вероятности состояния, как будто это отдельные независимые узлы $$M/M/n$$ -системы. Это объясняется на следующем примере.
(рис 14.4) Диаграмма переходов состояний для двух независимых M/M/1-систем организации очереди с идентичной интенсивностью прибытия, но различными средними временами обслуживания. Диаграмма обратима.
Прохождение информации с обратной связью приведено в Примере 14.3.1. В этом примере клиенту, который только что закончил свое обслуживание на узле 2, разрешается возвращение к узлу 1 с вероятностью $$p_{21}$$.
С вероятностью клиент покидает систему. Уравнения равновесия потока (14.5) дают полную интенсивность прибытия к каждому узлу, и $$p_{21}$$ должен быть выбран таким, чтобы $$A_1 /\mu_1$$ и $$A_2 /\mu_2$$ были меньше, чем единица. Предполагая, что $$\lambda_1 \to 0$$ и $$p_{ 21} \to 1$$,, мы понимаем, что реализуемые процессы поступления вызовов не Пуассоновские процессы. Новая заявка от клиента поступает редко, но если поступает и будет введена в систему, то она будет циркулировать относительно долгое время. Число обращений будет геометрически распределено, и интервал поступления - сумма этих двух времен обслуживания. То есть когда в системе есть один (или больше) клиент, интенсивность поступления к каждому узлу будет относительно высока, тогда как если нет никаких клиентов, то интенсивность поступления будет очень низка. Процесс поступления вызовов будет взрывной.
Ситуация похожа на разложение экспоненциального распределения во взвешенную сумму Эрланговского распределения k - ого порядка, с геометрическими коэффициентами веса (секция 4.4). Вместо того, чтобы рассматривать единственное экспоненциальное распределение интервала, мы можем анализировать k фаз (рис.4.9) и рассматривать каждую фазу как поступление. Следовательно, процесс поступления вызовов преобразуется из Пуассоновского процесса в процесс с взрывным поступлением.
В реальной сети передачи данных пакеты будут иметь одну и ту же постоянную длину и поэтому одно и то же время обслуживания на всех линиях связи и узлах с равной скоростью обслуживания. Теория сети очередей принимает, что пакет (клиент) производит выбор нового времени обслуживания на каждом узле. Это - необходимое предположение для мультипликативной формы. Такое предположение было впервые исследовано Клейнроком (1964 [65] ), и, оказывается, оно дает хорошее приближение к практике.
Мы интересуемся вероятностями состояния, определенными $$p(i_1, i_2,, \dots, i_k \dots, i_K) $$, где $$i_K$$ - число клиентов в узле $$k(1 \le k \le K) $$.
Расчет открытых сетей прост. Сначала мы решаем уравнение равновесия потока (14.5) и получаем объединенную интенсивность прибытия к каждому узлу ( $$A_k$$ ). Комбинируя интенсивности прибытия с распределением времени обслуживания ( $$A_k$$ ), получаем предложенную нагрузку $$A_k$$ на каждом узле и затем, рассматривая Эрланговскую систему с ожиданием, находим вероятности состояния для каждого узла.
Исследование закрытых сетей с очередями намного сложнее, чем открытых. Мы знаем только относительную нагрузку на каждом узле, а не абсолютную нагрузку, то есть c $$\Lambda_j$$ получена, но $$c$$ неизвестно. Можно получить относительную нормализованную вероятность состояния. Наконец, нормализуя, мы получим нормализованные вероятности состояния. К сожалению, нормализация подразумевает, что необходимо суммировать все вероятности состояний, то есть вычислить каждую (нормализованную) вероятность состояния. Число состояний увеличивается быстро с увеличением числа клиентов и/или узлов. В общем случае, можно рассматривать только маленькие системы. Сложность этой задачи подобна сложности задачи многоразмерных систем с потерями (Лекция 10).
Мы покажем, как алгоритм свертывания может быть применен к сетям очередей. Алгоритм соответствует алгоритму свертывания для систем с потерями (Лекция 10). Рассмотрим сеть очередей с $$K$$ узлами и единственной цепочкой очередей с $$S$$ клиентами. Принимаем условие, что системы организации очереди на каждом узле симметричны (секция 14.2). Алгоритм имеет три шага.
где:
$$q_{12}(i)=\sum_{x=0}^i q_1(x)*q_2(i-x), \quad i=0,1, \dots S$$Когда для всех узлов получены свертки, получаем:
$$q_{1,2, \dots, K}=q_{1,2,\dots, K-1}*q_K.$$Так как общее количество клиентов задано ( $$S$$ ), существует только состояние одной объединенной системы - $$q_{1,2, \dots , K(S)} ,$$ и поэтому это макросостояние должно иметь вероятность появления, равную единице. Мы может тогда нормализовать все микровероятности состояний.
Когда выполняется последнее свертывание, можно получить критерии качества работы для последнего узла. Изменяя порядок свертывания узлов, получим критерии качества работы всех узлов.
Мы рассматриваем модель восстановления машин Пальма, введенную в секции 12.5, как закрытую сеть организации очередей (рис.14.5). Есть $$S$$ клиентов и терминалов. Среднее время раздумья равно $$\mu^{-1}$$, и среднее время обслуживания центральным процессором - $$\mu_2^{-1}$$. В терминологии сети очередей есть два узла: первый узел является терминалом, то есть $$M/G/\infty$$ (фактически, это $$M/G/S$$ - система, но так как число клиентов ограничено S, которое может быть достаточно большим, это соответствует системе M/G/oo), и второй узел - центральный процессор, то есть $$M/M/1$$ - система с сервисной интенсивностью $$\mu_2$$.
Потоки к узлам равны ( $$\Lambda_1 = \Lambda_2 = \Lambda$$ ), относительная нагрузка в узле 1 узле 2
$$\alpha_1=\Lambda / \mu_1$$и
$$\alpha_2=\Lambda / \mu_2,$$соответственно.
Если рассматривать каждый узел как изолированный, мы получаем вероятности состояния каждого узла, $$q_1(i) $$ и $$q_2(j) $$. Свертывая $$q_1(i) $$ и $$q_2( j) $$, получаем $$q_{12}(x) $$, $$(0 \le x \le S) $$, как показано в Таблице 14.1.
Последний элемент с $$S$$ клиентами (не нормализованная вероятность) $$q_{12}(S) $$ состоит из:
$$q_{12}(S)=\alpha_2^S*1+\alpha_2^{S-1}*\alpha_1+\alpha_2^{S-2}*\frac{\alpha_1^2}{2!}+ \dots +1*\frac{\alpha_1^S}{S!}$$Где:
$$\varrho=\frac{\alpha_1}{\alpha_2}=\frac{\mu_2}{\mu_1}$$(рис 14.5) Модель восстановления машин сети очередей с двумя узлами. Терминалы соответствуют одному узлу, где задачи всегда находят свободный терминал, в то время как центральный процессор, обрабатывающий заявки терминала - M/M/1-узел| Состояние $$i$$ | Узел 1 $$q_1(i)$$ | Узел 2 $$q_2(i) $$ | Сеть очередей $$q_{12}=q_1*q_2$$ |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | $$\alpha_1$$ | $$\alpha_2$$ | $$\alpha_1+\alpha_2$$ |
| 2 | $$\frac{\alpha_1^2}{2!}$$ | $$\alpha_2^2$$ | $$\alpha_2^2+\alpha_1*\alpha_2+\frac{\alpha_1^2}{2!}$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ |
| $$i$$ | $$\frac{\alpha_1^i}{i!}$$ | $$\alpha_2^i$$ | $$\vdots$$ |
| $$\vdots$$ | $$\vdots$$ | $$\vdots$$ | $$\vdots$$ |
| $$S$$ | $$\frac{\alpha_1^S}{S!}$$ | $$\alpha_2^S$$ | $$q_{12}(S)$$ |
Вероятность, что все терминалы находятся в режиме " раздумья ", отображается последним элементом (нормализованной суммы) (S терминалы в узле 1, нулевые терминалы в узле 2):
$$\frac{\frac{\varrho^S}{S!}}{1+\varrho+\frac{\varrho^2}{2!}+\frac{\varrho^3}{3!}+\dots +\frac{\varrho^S}{S!}}=E_{1,S}(\varrho)$$Это B- формула Эрланга. Таким образом, результат соответствует результату, полученному в секции 12.5. Заметим, что $$\lambda$$ появляется в той же самой степени во всех элементах $$q_{1,2} (S) $$ и поэтому сокращается, когда мы нормализуем вероятности состояний.
В 1971 г. Бузен (J. P. Buzen) ввел модель с центральным сервером (рис.14.6), чтобы рассмотреть мультипрограммную компьютерную систему с одним центральным процессором и множеством каналов ввода-вывода (периферийные модули).
(рис 14.6) Система организации очереди с центральным сервером, состоящая из одного центрального сервера и (K-1) каналов ввода-вывода. В системе циркулирует фиксированное число задач - S.Число периферийных модулей обозначено $$K-1$$, как это можно видеть на рис.14.6, который также показывает
Бузен (Buzen) составил схему оценки этой системы. Схема - специальный случай алгоритма свертывания. Проиллюстрируем это для случая $$S 4$$ клиента, $$K 3$$ узла и:
$$\mu_1=\frac{1}{28}, \quad \mu_2=\frac{1}{40}, \quad \mu_3=\frac{1}{280},\\ p_{11}=0.1, \quad p_{12}=0.7, \quad p_{13}=0.2.$$Относительные нагрузки равны:
$$\alpha_1=1,\\ \alpha_2=1,\\ \alpha_3=2.$$Если мы применяем алгоритм свертывания, то получаем результаты, показанные в Таблице 14.2. Элемент $$q_{123}(4) $$ состоит из:
$$q_{123}(4)=1*16+2*8+3*4+4*2+5*1=57.$$Узел 3 обслуживает клиентов во всех состояниях, кроме состояния $$q_3 (0) \times q_{12} (4) = 5$$. Поэтому степень использования узла 3 равна $$a_3 = 52/57$$. На основании относительных нагрузок получаем точные нагрузки:
$$a_1=\frac{26}{57},\\ a_2=\frac{26}{57},\\ a_3=\frac{52}{57}$$Среднее число клиентов в узле 3:
$$L_3=\{1*(4*2)+2*(3*4)+3*(2*8)+4*(1*16)\}/57,\\ L_3=\frac{144}{57}.$$Изменяя порядок свертывания, получаем
| Сост. | Узел 1 | Узел 2 | Узел 1*2 | Узел 3 | Сеть очередей |
|---|---|---|---|---|---|
| $$i$$ | $$q_1(i)$$ | $$q_2(i)$$ | $$q_{12}=q_1*q_2$$ | $$q_3$$ | $$q_{123}=(Q_1*q_2)*q_3$$ |
| 0 | 1 | 1 | 2 | 2 | 4 |
| 1 | 1 | 1 | 3 | 4 | 11 |
| 2 | 1 | 1 | 3 | 4 | 11 |
| 3 | 1 | 1 | 4 | 8 | 26 |
| 4 | 1 | 1 | 5 | 16 | 57 |
Сумма всех
Применяя формулу Литтла, получаем среднее время пребывания $$W_k = L_k / k:$$
$$W_1=45.23,\\ W_2=64.62,\\ W_3=775.38$$Мы рассматриваем сеть организации очереди с $$K$$ узлами и $$S$$ клиентами (все принадлежат одной цепочке). Относительные нагрузки узлов обозначены $$\alpha_k(k = 1, 2, \dots , K) $$. Алгоритм рекурсивный по числу заявок от клиентов сети, то есть сеть с $$x + 1$$ заявкой от клиентов получается из сети, обслуживающей $$x$$ заявок.
Примем, что среднее число заявок оот клиентов в узле $$k$$ равно $$L_k (x) $$, где $$x$$ - общее количество клиентов в сети. Очевидно, что:
$$\sum_{k=1}^KL_k(x)=x.$$Алгоритм выполняется рекурсивно за два шага.
Шаг 1.
Увеличьте число заявок от клиентов от $$x$$ до $$(x+1) $$. Согласно теореме прибытия, $$(x+ 1) $$ -ый клиент поступит в систему, когда система с $$x$$ клиентами находится в статистическом равновесии. Следовательно, среднее время пребывания (время ожидания + время обслуживания) в узле $$k$$:
для M/M/1, M/G/1-PS M/G/1-LCFS-PR
для $$M/G/\infty$$:
$$W_k(x+1)=s_k.$$где $$s_k-$$ среднее время обслуживания в узле $$k$$, который имеет $$n_k$$ приборов. Для вычисления средних времен ожидания мы можем принять $$FCFS$$ -дисциплину организации очереди.
Шаг 2.
Используя формулу Литтла ( $$L = \lambda W$$ ), которая применима для всех систем в статистическом равновесии, для узла $$k$$ мы получим:
$$L_k(x+1)=c*\lambda_k*W_k(x+1),$$где $$\lambda_k$$ - относительная интенсивность поступления заявок к узлу $$k$$. Константа нормализации c получена, исходя из общего количества клиентов:
$$\sum_{k=1}^KL+k(x+1)=x+1.$$За эти два шага мы выполнили рекурсию от $$x$$ до $$(x + 1) $$ заявок. Для $$x = 1$$ нет никакого времени ожидания в системе, и $$W_k (1) $$ равняется среднему времени обслуживания $$s_k$$. Ниже был показан $$MVA$$ -алгоритм для одного узла обслуживания, но довольно просто делать вывод для узлов или с несколькими обслуживающими приборами или с бесконечным числом обслуживающих приборов.
Применим
| Узел 1 | Узел 2 | Узел 3 | |
|---|---|---|---|
| $$S=1$$ | $$W_1(1)=28$$ | $$W_2(1)=40$$ | $$W_3(1)=280$$ |
| $$L_1(1)=c*1*28$$ | $$L_2(1)=c*0.7*40$$ | $$L_3(1)=c*0.2*280$$ | |
| $$L_1(1)=0.25$$ | $$L_2(1)=0.25$$ | $$L_3(1)=0.50$$ | |
| $$S=2$$ | $$W_1(2)=1.25*28$$ | $$W_2(2)=1.25*40$$ | $$W_3(2)=1.50*280$$ |
| $$L_1(2)-c*1*1.25*28$$ | $$L_2(2)c*0.7*1.25*40$$ | $$L_3(2)=c*0.2*1.50*280$$ | |
| $$L_1(2)=0.4545$$ | $$L_2(2)=0.4545$$ | $$L_3(2)=1.0909$$ | |
| $$S=3$$ | $$W_1(3)=1.4545*28$$ | $$W_2(3)=1.4545*40$$ | $$W_3(3)=2.0909*280$$ |
| $$L_1(3)=c*1*1.4545*28$$ | $$L_2(3)=c*0.7*1.4545*40$$ | $$L_3(3)=c*0.2*2.0909*280$$ | |
| $$L_1(3)=0.6154$$ | $$L_2(3)=0.6154$$ | $$L_3(3)=1.7692$$ | |
| $$S=4$$ | $$W_1(4)=1.6154*28$$ | $$W_2(4)=1.6154*40$$ | $$W_3(4)=2.7692*280$$ |
| $$L_1(4)=c*1*1.6154*28$$ | $$L_2(4)=c*0.7*1.6154*40$$ | $$L_3(4)=c*0.2*2.7692*280$$ | |
| $$L_1(4)=0.7368$$ | $$L_2(4)=0.7368$$ | $$L_3(4)=2.5263$$ |
Естественно, что результат идентичен тому, который получен при применении алгоритма свертывания. Время пребывания на каждом узле (выраженное через единицу времени):
$$W_1(4)=1.6154*28=45.23\\ W_2(4)=1.6154*40=64.62,\\ W_3(4)=2.7693*280=775.38$$Мы рассматриваем модель Пальма восстановления машин с $$S$$ источниками, конечным временем раздумья и центральным процессором (время обслуживания равняется одной единице времени). Как было упомянуто в секции 12.5.2, эта модель
| Узел 1 | Узел 2 | |
|---|---|---|
| $$S=1$$ | $$W_1(1)=A$$ | $$W_2(1)=1$$ |
| $$L_1(1)=c*1*A$$ | $$L_2(1)=c*1*1$$ | |
| $$L_1(1)=\frac{1}{1+A}$$ | $$L_2(1)=\frac{1}{1+A}$$ | |
| $$S=2$$ | $$W_1(2)=A$$ | $$W_2(2)=1+\frac{1}{1+A}$$ |
| $$L_1(2)=c*1*A$$ | $$L_2(2)=c*1*(1+\frac{1}{1+A})$$ | |
| $$L_1(2)=A*\frac{1+A}{1+A+\frac{a^2}{2!}}$$ | $$L_2(2)=2-A*\frac{1+A}{1+A+\frac{a^2}{2!}}$$ |
Мы знаем, что длина очереди в терминалах (узел 1) равна обслуженной нагрузке, измеренной в Эрлангах - в системе, и что все другие заявки клиенты находятся в центральном процессоре (узел 2). Мы, таким образом, имеем:
| Узел 1 | Узел 2 | |
|---|---|---|
| $$S=x$$ | $$W_1(x)=A$$ | $$W_2(x)=1+L_2(x-1)$$ |
| $$L_1(x)=c*A$$ | $$L_2(x)=c*\{1+L_2(x-1)\}$$ | |
| $$L_1(x)=A*\{1-E_x(A)\}$$ | $$L_2(x)=x-A*\{1-E_x(A)\}$$ |
Из этого получаем нормировочную константу $$c=1-E_x(A) $$ и находим для $$(x+1) $$ того клиента:
$$L_1(x+1)+L_2(x+1)=c*A+c\{1+L_2(x)\},\\ =c*A+c*\{1+x-A*(1-E_x)\}\\ =x+1,\\ E_{x+1}=\frac{A*E_x}{x+1+A*E_x},$$потому что $$c=1-E_{x+1}$$. Это рекурсивная формула для системы B-Эрланга.
В 1975 г. вторая модель Джексона была далее обобщена Baskett, Chandy, Muntz и Palacios (1975 [4]). Они показали, что сети очередей с более чем одним типом клиентов также имеют мультипликативную форму, при условии, что:
BCMP -сети могут быть рассчитаны с помощью многомерного алгоритма свертывания и многомерного
Смешанные сети очередей (открытые и закрытые) рассчитываются сначала путем вычисления нагрузки от открытых цепочек в каждом узле. Эту нагрузку нужно обслуживать так, чтобы соблюдалось статистическое равновесие.
Производительность этих узлов уменьшается на эту нагрузку, и закрытая сеть очередей рассчитывается уже с меньшей производительностью. Так что главная проблема состоит в расчете закрытых сетей. Для этого мы можем использовать много алгоритмов, среди которых самыми важными являются алгоритмы свертывании и Алгоритм Средней величины (
В этой секции мы рассматриваем сети очередей с более чем одним типом клиентов. Клиенты одного и того же типа принадлежат заданному классу или цепочке. В Лекции 10 мы рассматривали системы с потерями, обслуживающие несколько типов клиентов (услуг), и замечали, что может быть получена мультипликативная форма и может быть применен алгоритм свертывания.
Pис.14.7 иллюстрирует систему организации очереди с одним обслуживающим прибором и с $$N = 2$$ типа заявок от клиентов (цепочек). Заявки от клиентов прибывают в систему согласно Пуассоновскому потоку вызовов с интенсивностью $$\lambda_j ( j = 1, 2) $$. Состояние $$(i, j) $$ определено как состояние $$i$$ заявок клиента типа 1 и $$j$$ заявок от клиента типа 2. Интенсивность обслуживания $$\mu_{i,j}$$ в состоянии $$(i, j) $$ может быть выбрана зависящей от состояния, например:
$$\mu_{ij}=\frac{i}{i+j}*\mu_1+\frac{j}{i+j}*\mu_2.$$Интенсивности обслуживания могут интерпретироваться несколькими способами, но они должны соответствовать симметричной системе организации очереди при наличии одного обслуживающего прибора.
Одна из интерпретаций соответствует совместному использованию процессора, то есть все $$(i+j) $$ клиентов совместно используют обслуживающий прибор, а производительность сервера является постоянной. Зависимость состояния от типа клиента происходит из-за разности в интенсивности обслуживания двух типов клиентов. То есть число заявок от клиентов, покидающих систему, в единицу времени зависит от типа клиентов, обслуживаемых в настоящее время.
Можно показать, что обслуживаемая заявка с вероятностью $$i/(i+j) $$ принадлежит к типу 1 и с вероятностью $$j/(i+j) $$ - к типу 2 независимо от дисциплины обслуживания.
Pис.14.8 дает часть диаграммы переходов состояний. Диаграмма обратима, так как поток по часовой стрелке равняется потоку против часовой стрелки. Следовательно, есть местное равновесие, и все вероятности состояния могут быть выражены с помощью $$p(0, 0) $$:
(рис 14.8) M/M/1-система организации очереди с двумя типами (цепочками) клиентов.(рис 14.7) Диаграмма переходов состояний для многомерной системы M/M/1 с совместным использованием процессора.$$p(i,j)=\frac{A_1^i}{i!}*\frac{A_2^j}{j!}*(i+j)!*p(0,0).$$Используя нормализацию, получаем $$p(0, 0) $$:
$$\sum_{i=0}^{\infty}\sum_{j=0}^{\infty} p(i,j)=1$$По сравнению с многомерной B-формулой Эрланга, здесь существует дополнительный коэффициент $$(i+j)$$!. Мультипликативная форма выражения между цепочками (на узле) потеряна, но мультипликативная форма между узлами все еще поддерживается.
Примем, что есть $$N$$ различных типов клиентов (цепочек) вероятности состояния для единственного узла, и получаем:
$$p(i)=p(i_1, i_2, \dots, i_N)=\left \{ \Pi_{j=1}^N A_j^{i_j} \right \}* \frac{\left \{ \sum_{j=1}^Ni_j \right \}}{\left \{ \Pi_{j=1}^N i_j! \right \}}*p(0).$$Это может быть выражено полиномиальным распределением (4.37):
$$p(i)=\left \Pi_{j=1}^N A_{j^{i_j} \right \}* {i_1+i_2 +\dots +i_n\choose i_1, i_2, \dots, i_n}*p(0).$$Для бесконечного числа мест ожидания вероятности состояния общего количества клиентов:
$$p(j)=p\{i_1+i_2+\dots +i_N=j\}.$$Если $$\mu_i = \mu$$, то система идентична $$M/M/1$$ - системе с интенсивностью поступления $$\lambda=\sum_i \lambda_i$$:
$$p(j)=(A_1+A_2+ \dots +A_N)^j*p(0)\\ =A^j*(1-A) $$Чтобы получить этот результат, используется биноминальное разложение. Диаграмма переходов состояний на рис.14.8 может также интерпретироваться как диаграмма переходов состояний системы M/G/1-LCFS-PR (приоритетное возвращение к работе). Очевидно, что M/G/1-LCFS-PR обратимо, потому что процесс в диаграмме переходов состояний проходит одинаково как вперед из нуля, так и назад, чтобы вернуться в нуль.
Можно показать, что диаграмма переходов состояний нечувствительна к распределению времени обслуживания, так что она справедлива для системы организации очереди $$M/G/1$$. Pис.14.8 соответствует диаграмме переходов состояний для системы организации очереди с одним обслуживающим прибором и гиперэкспоненциально распределенными временами обслуживания (см. (10.7)), например. $$M/H_2 /1-LCFS-PR$$ или $$PS$$.
Заметим, что для $$M/M/1 (FCFS, LCFS, SIRO) $$ необходимо, чтобы все клиенты имели одно и то же среднее время обслуживания, которое должно быть экспоненциально распределенным. Другими словами, обслуживаемый клиент не будет случайным клиентом среди $$(i+j) $$ клиентов в системе.
В заключение заметим, что системы организации очереди c одним обслуживающим прибором и большим количеством типов клиентов будут иметь мультипликативную форму только тогда, когда узел имеет симметричную систему организации очереди: $$M/G/1-PS, M/G/1-LCFS -PR$$ или $$M/M/1$$ с одним и тем же временем обслуживания для всех клиентов.
Мы можем также получить рассмотренные выше результаты для системы с $$n$$ обслуживающими приборами. Для $$(i+j) \le n$$
получаем ту же самую вероятность относительного состояния, что и для многоразмерной B-формулы Эрланга. Для $$(i+j)>n$$ получаем решение только для простого случая, когда $$\mu_i=\mu$$ то есть когда все типы (цепочки) клиентов имеют одно и то же среднее время пребывания в системе. Мы тогда находим вероятности состояния, данные в (10.9), и система имеет мультипликативную форму. $$M/M/1$$ можно рассматривать как частный случай $$M/M/n$$ и по аналогии с системами с потерями (Лекция 12).
Рассмотрение сетей очередей, имеющих много цепочек, аналогично случаю с единственной цепочкой. Основное различие состоит в том, что классическая формула и алгоритмы заменены соответствующей многомерной формулой.
Алгоритм по существу такой же, как и в случае единственной цепочки.
Шаг 1. Рассмотрим каждую цепочку так, как будто она является единственной в сети. Найдите относительную нагрузку в каждом узле, решая уравнения равновесия потока (14.5). В произвольном опорном узле принимаем, что нагрузка равна единице. Для каждой цепочки мы можем выбрать в качестве опорного узла свой узел. Для цепочки $$j$$ в узле $$k$$ относительная интенсивность прибытия $$\lambda_k^j$$ (используем верхний индекс, чтобы указать номер цепочки) получается из:
$$\lambda_k^j=\sum_{i=1}^Kp_{ik}^j*\lambda_i^j, \quad j=1, \dots, N$$где:
$$K$$ - число узлов,
$$N$$ - число цепочек,
$$p_{ik}^j$$ - вероятность, что клиент цепочки $$j$$ перейдет с узла $$i$$ к узлу $$k$$.
Мы выбираем произвольный узел как
где $$s+k^j$$ - среднее время обслуживания в узле $$k$$ для клиентов цепочки $$j$$. Обратите внимание, что j - индекс, а не степень.
Шаг 2. На основе значений относительных нагрузок, найденных на шаге 1, мы получаем многомерные вероятности состояния для каждого узла. Каждый узел рассматривается отдельно. Далее, усекаем пространство состояний согласно числу клиентов в каждой цепочке. Например, для узла $$k (1 \le k \le K) $$:
$$p_k=p_k(i_1, i_2, \dots, i_N), \quad 0 \le i_j \le S_j, \quad j=1,2,\dots, N,$$где $$S_j$$ - число заявок от клиентов в цепочке $$j$$.
Шаг 3. Чтобы найти вероятности состояния полной сети, сверты ваем вероятности состояния каждого узла подобно случаю единственной цепочки, - разница в том, что в данном случае свертывание многомерно. Когда выполним последнее свертывание, получим критерии качества работы последнего узла. Снова изменяя порядок узлов, мы можем получить критерии качества работы всех узлов.
Общее количество состояний увеличивается быстро. Например, если цепочка $$j$$ имеет $$S$$ заявок клиентов, то общее количество состояния в каждом узле становится:
$$\Pi_{j=1}^N(S_j+1)$$Пути $$N$$ цепей с $$S_j$$ заявками в цепи $$j$$ могут быть распределены в сети очередей с $$K$$ узлами:
$$C=\Pi_{j=1}^NC(S_j,k_j$$где $$k_j (1 \le k_j < K) $$ - номер узлов, посещенных клиентом в цепи $$j$$, и:
$$C(S_j, k_j)={S_j+k_j-1\choose k_j-1}={S_j+k_j-1\choose S_j}.$$Алгоритм лучше всего проиллюстрировать примером.
Уже отмечалось в Примере 14.4.1, что эта система может быть смоделирована как сеть очередей с двумя узлами.
Узел 1 соответствует терминалам (машинам), в то время как узел 2 - центральному процессору (ремонтником). Узел 2 - система с одним обслуживающим прибором, тогда как узел 1 смоделирован как система с бесконечным числом обслуживающих приборов. Число клиентов в цепочках - ( $$S_1 = 2, S_2 = 3$$ ) и среднее время обслуживания в узле $$k - s_k^j.$$
Относительная нагрузка цепочки 1 обозначена $$\alpha_1$$ в узле 1 и $$\alpha_2$$ в узле 2. Точно так же нагрузка в цепочке 2 обозначена $$\beta_1$$ и соответственно $$\beta_2$$. Применяя алгоритм свертывания, получаем:
Шаг 1.
Цепочка 1: $$S_1 = 2$$ клиента
Относительная нагрузка: $$\alpha_1=\lambda_1*s_1^1, \quad \alpha_2=\lambda_1*s_2^1$$.
Цепочка 2: $$S_2 = 3$$ клиента
Относительная нагрузка: $$\beta_1=\lambda_1*s_1^2, \quad \beta_2=\lambda_2*s_2^2$$.
Шаг 2.
Для узла 1 ( IS ) вероятность относительного состояния (см10.9):
Для узла 2 (обслуживающий прибор) (см.14.15) мы имеем:
$$q_2(0,0)1 \qquad q_2(0,2)=\beta_2^2\\ q_2(1,0)=\alpha_2 \qquad q_2(1,2)=3*\alpha_2*\beta_2^2\\ q_2(2,0)=\alpha_2^2 \qquad q_2(2,2)=6*\alpha_2^2*\beta_2^2\\ q_2(0,1)=\beta_2 \qquad q_2(0,3)=\beta_2^3\\ q_2(1,1)=2*\alpha_2*\beta_2 \qquad q_2(1,3)=4*\alpha_2*\beta_2^3\\ q_2(2,1)=3*\alpha_2^2*\beta_2 \qquad q_2(2,3)=10*\alpha_2^2*\beta_2^3$$Шаг 3.
Затем мы делаем свертку. Мы знаем, что общее количество клиентов - (2,3), то есть нас интересуют только состояния (2, 3):
$$q_[12}(2,3)=q_1(0,0)*q_2(2,3)+q_1(1,0)*q_2(1,3)\\ +q_1(2,0)*q_2(0,3)+q_1(0,1)*q_2(2,2)\\ +q-1(1,1)*q_2(1,2)+q_2(2,1)*q_2(0,2)\\ +q_1(2,2)*q_2(2,1)+q_1(1,2)*q_2(1,1\\ +q_1(2,2)*q_2(0,1)+q-1(0,3)*q_2(2,0)\\ +q_1(1,3)*q_2(1,0)+q_1(2,3)*q_2(0,0)$$Использование полученных значений дает:
$$q_{12}(2,3)=+1*10*\alpha_2^2*\beta_2^3+\alpha_1*4*\alpha_2*\beta_2^3\\ +\frac{\alpha_1^2}{2}*\beta_2^3+\beta_1*6*\alpha_2^2*\beta_2^2\\ +\alpha_1*\beta_1*3*\alpha_2*\beta_2^2+\frac{\alpha_1*\beta_1^2}{2}*\beta_2^2\\ +\frac{\beta_1^2}{2}*3*\alpha_2^2*\beta_2+\frac{\alpha_1*\beta_1^2}{2}*2*\alpha_2*\beta_2\\ +\frac{\alpha_1^2*\beta_1^2}{4}*\beta_2+\frac{\beta_1^3}{6}*\alpha_2^2\\ +\frac{\alpha_1*\beta_1^3}{6}*\alpha_2+\frac{\alpha_1^2*\beta_1^3}{12}*1$$Обратите внимание, что $$\alpha_1$$ и $$\alpha_2$$ (цепочка 1) появляются во второй степени, тогда как $$\beta_1$$ и $$\beta_2$$ (цепочка 2) - в третьей степени, что соответствует числу клиентов в каждой цепочке. Из-за этого существенны только относительные нагрузки, а абсолютные вероятности получают нормализацией, делением всех элементов $$q_{12}(2, 3) $$. Теперь достаточно просто получить детальные вероятности состояния. Только в состоянии с элементами $$(\alpha_1^2 * \beta_1^3)/12$$ центральный процессор (ремонтник) свободен. Если два типа клиентов идентичны, модель упрощается и сводится к модели Пальма восстановления машин с 5-ю терминалами.
В этом случае мы имеем:
$$E_{1,5}(x)=\frac{\frac{1}{12}*\alpha_1^2*\beta_1^3}{q_{12}(2,3)}.$$Выбирая, $$\alpha_1 \beta_1 \alpha$$ и $$\alpha_2 \beta_2 1$$, получаем:
$$\frac{\frac{1}{12}*\alpha_1^2*\beta_1^3}{q_{12}(2,3)}=\frac{\frac{\alpha^5}{2}}{10+4 \alpha +\frac 12 \alpha^2+6 \alpha +3 \alpha^2+\frac 12 \alpha^3+\frac 32 \alpha^2+ \alpha^3+\frac 14 \alpha^4+\frac 16 \alpha^3+\frac 16 \alpha^4+\frac{1}{12} \alpha^5}=\\ =\frac{\frac{\alpha^5}{5!}}{1+ \alpha+\frac{\alpha^2}{2}+\frac{\alpha^3}{3!}+\frac{\alpha^4}{4!}+\frac{\alpha^5}{5!}},$$то есть, как и ожидалось, B- формулу Эрланга.
Сети очередей имеют такую же сложность, что и сети с коммутацией каналов и прямой маршрутизацией (секция 11.5 и табл. 11.2). Пространство состояний сети, показанной в таблице 14.3, имеет следующее число состояния для каждого узла:
$$\Pi_{i=0}^N(S_i+1)$$Худший случай - тот, когда каждая цепочка состоит из одного клиента. Тогда число состояний становится $$2^S$$, где $$S$$ - число клиентов.
| Цепочка | Узел $$\begin{matrix}12\dots K \end{matrix}$$ | Число клиентов |
|---|---|---|
| 1 | $$\begin{matrix} \alpha_{11} \alpha_{21} \dots \alpha_{K1} \end{matrix}$$ | $$S_1$$ |
| 2 | $$\begin{matrix} \alpha_{12} \alpha_{22} \dots \alpha_{K2} \end{matrix}$$ | $$S_2$$ |
| $$\dots$$ | $$\dots$$ | $$\dots$$ |
| $$N$$ | $$\begin{matrix} \alpha_{1N} \alpha_{2N} \dots \alpha_{KN} \end{matrix}$$ | $$S_N$$ |
Рассмотрим систему передачи данных с $$K$$ узлами, которые являются независимыми узлами системы организации очереди с одним обслуживающим прибором $$M/M/1$$ (Эрланговская система с ожиданием с одним обслуживающим прибором). Процесс поступления вызовов к узлу $$k$$ - Пуассоновский процесс с интенсивностью $$\lambda_k$$ сообщений (клиентов) в единицу времени. Размер сообщения - экспоненциально распределенное значение со средней величиной $$1/\mu_k$$ [бит]. Пропускная способность узла $$k$$ - равна $$\varphi_k$$ [бит в единицу времени]. Среднее время обслуживания равно:
$$s=\frac{1/\mu_k}{\varphi_k}=\frac{1}{\mu_k \varphi_k}$$Так что средняя скорость обслуживания - $$\mu_k * \varphi_k,$$ а среднее время пребывания определяется (12.34):
$$m_{1,k}=\frac{1}{\mu_k \varphi_k - \lambda_k}$$Вводим следующее линейное ограничение на полную производительность:
$$F=\sum_{k=1}^K \varphi_k$$Для каждого распределения производительности, которая удовлетворяет (14.21), получаем следующее среднее время пребывания для всех сообщений (математическое ожидание вызова):
$$m_1=\sum_{k=1}^K \frac{\lambda_k}{\lambda}*\frac{1}{\mu_k* \varphi_k - \lambda_k}$$где
$$\lambda=\sum_{k=1}^K \lambda_k$$Применяя (13.14), получаем полное среднее время обслуживания:
$$\frac{1}{\mu}=\sum_{k=1}^K \frac{\lambda_k}{\lambda}*\frac{1}{\mu_k}$$Полная предложенная нагрузка тогда:
$$A=\frac{\lambda}{\mu*F}$$Закон Клейнрока для оптимального распределения производительности (Kleinrock, 1964 [65]) сформулирован следующим образом.
Теорема 14.2. Закон квадратного корня Закон квадратного корня (закон Клейнрока): оптимальное распределение производительности ( $$\varphi_k$$ ), которое минимизирует $$m_1$$ (и таким образом общее количество сообщений во всех узлах):
$$\varphi_k=\frac{\lambda_k}{\mu+k}+F*(1-A)\frac{\sqrt{\lambda_k \mu_k}}{\sum_{i=1}^K \sqrt{\lambda_i \mu_i}},$$при условии, что:
$$F > \sum_{k=1}^K \frac{\lambda_k}{\mu_k}$$Доказательство. Вводя множитель $$\vartheta$$ Лагранжа и рассматривая:
$$G=m_1- \vartheta \left \{ \sum_{k=1}^K \varphi_k -F \right \}.$$Минимум $$G$$ получен, если выбирать $$\varphi_k,$$ как приведено в (14.26). С этим оптимальным распределением находим среднее время пребывания:
$$m_1=\frac{\left \{\sum_{k=1}^K \sqrt{\lambda_k/ \mu_k} \right \}^2}{\lambda*F*(1-A)}$$Это оптимальное распределение соответствует тому случаю, когда необходимая минимальная производительность $$\lambda_k/ \mu_j$$ сначала распределена между всеми узлами. Остающаяся производительность (14.24):
$$F-\sum_{k=1}^K=F*(1-A)$$Данная производительность распределена между узлами пропорционально квадратному корню из среднего потока $$\lambda_k/ \mu_k$$.
Если все сообщения имеют одинаковую среднюю величину $$(\mu_k= \mu)$$ то мы можем рассчитать различные затраты в узлах, согласно ограничению, которое фиксирует количество доступных узлов (Kleinrock,1964 [65]).
MVA Закон квадратного корня (закон Клейнрока): оптимальное распределение производительности (, которое минимизирует m1 (и таким образом общее количество сообщений во всех узлах):
$$\varphi_k=\frac{\lambda_k}{\mu+k}+F*(1-A)\frac{\sqrt{\lambda_k \mu_k}}{\sum_{i=1}^K \sqrt{\lambda_i \mu_i}}$$,
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.