Мы рассматриваем группу n пучков каналов (каналы, слоты), которым предлагают два независимых
Обозначим состояние системы $$(i, j)$$, где $$i$$ - число вызовов от потока 1, а $$j$$ - число вызовов от потока 2. Выполняются следующие ограничения:
$$0 \le i \le n,\\ 0 \le j \le n,\\ 0 \le i+j \le n.$$Диаграмма переходов состояний показана на рис.10.1. Согласно предположению о статистическом равновесии, вероятности состояний могут быть получены решением глобальных уравнений равновесия для каждого узла (уравнения узла), всего $$(n + 1) (n + 2)/2$$ уравнения.
(рис 10.1) Двухмерная диаграмма переходов состояний для системы с потерями с n каналами, которым предлагают два PCT- I потока нагрузки.Это эквивалентно диаграмме переходов состояний для
Как мы увидим в следующей секции, эта диаграмма соответствует обратимому марковскому процессу, который имеет локальное равновесие и, кроме того, решение имеет форму произведения ( product form ). Мы можем легко показать, что глобальные уравнения равновесия удовлетворяют следующим вероятностям состояния, которые могут быть записаны в форме произведения:
$$p(i,j)=p(i)*p(j),\\ =Q*\frac{A_i^1}{i!}*\frac{A_2^j}{j!},$$где $$p (i)$$ и $$p (j)$$ - одномерные усеченные Q - нормировочные константы, и $$(i, j)$$ выполняют вышеупомянутые ограничения (10.1). Поскольку рассматриваются Пуассоновские потоки вызовов, которые обладают свойством PASTA (Пуассоновское поступление вызовов, наблюдаемое за среднее время), потери по времени, потери по вызовам и потери по нагрузке равны между собой для обоих потоков нагрузки, и они равняются $$P (i + j = n)$$.
Биноминальным разложением или сверткой двух Пуассоновских распределений мы находим следующие объединенные вероятности состояний, где $$Q$$ получено нормализацией:
$$p(i+j=x)=Q*\frac{(A_1+A_2)^x}{x!},$$ $$Q^{-1}=\sum_{v=0}^n\frac{(A_1+A_2)^v}{v!}.$$Это усеченное Пуассоновское распределение (7.9) с предложенной нагрузкой:
$$A=A_1+A_2$$Мы можем также интерпретировать эту модель как систему Эрланга с потерями с одним Пуассоновским потоком вызовов и гиперраспределенными временами пребывания в системе следующим образом. Полный процесс поступления вызовов - суперпозиция двух Пуассоновских процессов с полной интенсивностью поступления:
$$\lambda=\lambda_1+\lambda_2,$$и распределение времени пребывания в системе является гиперраспределенным:
$$f(t)=\frac{\lambda_1}{\lambda_1+\lambda_2}*\mu_1*e^{-\mu_1t}+\frac{\lambda_2}{\lambda_1+\lambda_2}*\mu_2*e^{-\mu_2t}.$$Мы присваиваем веса эти двум экспоненциальным распределениям согласно относительному числу вызовов в единицу времени. Среднее время обслуживания и распределение времени пребывания в системе является гиперраспределенным:
$$m_1=\frac{\lambda_1}{\lambda_1+\lambda_2}*\frac{1}{\mu_1}+\frac{\lambda_2}{\lambda_1 +\lambda_2}*\frac{1}{\mu_2}=\frac{A_1+A_2}{\lambda_1+ \lambda_2},\\ m_1=\frac{A}{\lambda}$$и соответствует предложенной нагрузке.
Таким образом, мы показали, что
Можно обобщить вышеупомянутую модель на $$N$$ потоков нагрузки:
$$p(i_1, i_2, \dots, i_N)=Q*\frac{A_1^{i_1}}{i_1!}*\frac{A_2^{i_2}}{i_2!} \dots \frac{A_N^{i_N}}{i_N!}, 0 \le i_j \le n, \sum_{j=1}^Ni_j \le n,$$Данная модель является общей многомерной B-формулой Эрланга. Обобщая (10.3), мы замечаем, что глобальные вероятности состояния могут быть вычислены следующей рекурсией, где q(x) обозначает вероятность относительного состояния, и $$p(x)$$ - абсолютные вероятности состояния:
Если использовать рекурсию с нормированием (секция 7.4), то мы получаем рекурсивную формулу B- Эрланга. Формула (10.10) подобна уравнениям равновесия для Пуассоновского случая, когда:
$$A=\sum_{j=1}^NA_j$$Потери по времени - $$E = p(n)$$, и в соответствии со свойствами потока PASTA, потери по времени также равны потерям по вызовам и по нагрузке. Числовые оценки мы рассмотрим в секции 10.4. Многомерные системы были сначала упомянуты Эрлангом и более тщательно рассмотрены Иенсоном в Erlangbook (Jensen, 1948 ).
В предыдущей секции мы рассматривали двухмерную диаграмму переходов состояний. Для увеличивающегося числа потоков нагрузки число состояний (и следовательно уравнений) увеличивается очень быстро. Однако, можно упростить проблему, используя структуру диаграммы переходов состояний. Рассмотрим двухмерную диаграмму переходов состояний, показанную в рис. 10.2. Для четырех соседних состояний поток в направлении по часовой стрелке должен равняться потоку в противоположном направлении (Kingman, 1969 [64]), (Sutton, 1980 [95]). Взглянем на рис. 10.2.
(рис 10.2) Критерии Колмогорова - необходимое и достаточное условие для обратимости двухмерного марковского процесса: циркулирующий поток среди четырех соседних состояний в этом квадрате равняется нулю. Поток по часовой стрелке равняется потоку против часовой стрелки (10.12).По часовой стрелке:
$$[i,j] \to [i ,j+1]: p((i ,j)* \lambda_2 (i ,j)\\ [i ,j +1] \to [i+1 ,j+1]: p(i ,j +1)*\lambda_1(i ,j +1)\\ [i+1 ,j+1] \to [i+1 ,j]: p(i+1 ,j+1)*\mu_2(i+1 ,j+1)\\ [i+1 ,j] \to [i ,j]: p(i+1,j)*\mu_1(i+1,j),$$Против часовой стрелки:
$$[i,j] \to [i+1 ,j]: \qquad p(i ,j)* \lambda_1 (i ,j)\\ [i+1 ,j ] \to [i+1 ,j+1]: \qquad p(i+1 ,j)*\lambda_2(i+1 ,j )\\ [i+1 ,j+1] \to [i ,j+1]: \qquad p(i+1 ,j+1)*\mu_1(i+1 ,j+1)\\ [i ,j+1] \to [i ,j]: \qquad p(i,j+1)*\mu_2(i,j+1)$$Мы можем сократить оба выражения на вероятности состояния и затем получить условие (10.12). Необходимое и достаточное условие для обратимости - что следующие два выражения являются равными.
По часовой стрелке:
$$\lambda_2(i ,j)*\lambda_1(i ,j+1)*\mu_2(i+1,j+1)*\mu_1(i+1,j)$$Против часовой стрелки:
$$\lambda_1(i ,j)*\lambda_2(i+1,j)*\mu_1(i+1,j+1)*\mu_2(i,j+1).$$Если эти два выражения равны, то имеется локальное или частичное равновесие. Таким образом, необходимым условием для обратимости является то, что если есть поток (стрелка) от состояния i к состоянию j, тогда должен также быть поток (стрелка) от состояния j до состояния i. Мы можем применить уравнения сечения между любыми двумя подключенными состояниями. Итак, из рисунка 10.2 мы получаем:
Мы можем выразить любую вероятность состояния $$p(i, j)$$ с помощью вероятности состояния $$p(0, 0)$$, выбирая любой путь между этими двумя состояниями ( критерии Колмогорова ). Мы можем, например, выбрать путь:
$$(0,0),(1,0),\dots,(i,0),(i,1),\dots,( i ,j),$$Тогда получаем следующее уравнение равновесия:
$$p(i ,j)=\frac{\lambda_1(0,0)}{\mu_1(1,0)}*\frac{\lambda_1(1,0)}{\mu_1(2,0)} \dots \frac{\lambda_1(i-1,0)}{\mu_1(i,0)}*\frac{\lambda_2(i,0)}{\mu_2(i,1)}*\frac{\lambda_2(i,1)}{\mu_2(i,2)} \dots \frac{\lambda_2(i,j-1)}{\mu_2(i ,j)}*p(0,0)$$Мы находим $$p(0, 0)$$ нормировкой полной вероятности событий. Условие для обратимости будет выполнено во многих случаях, например, для:
$$\lambda_1(i ,j)=\lambda_1(i), \qquad \mu_1(i ,j)=i*\mu_1,$$ $$\lambda_2(i ,j)=\lambda_2(j), \qquad \mu_2(i ,j)=j*\mu_2.$$Если мы рассматриваем многомерную систему с потерями, имеющую N потоков нагрузки, то любым потоком нагрузки может быть зависимый от состояния Пуассоновский процесс. В конкретном потоке могут быть нагрузки типа N - мерных систем условия обратимости аналогичны (10.12). Критерий Колмогорова должен выполняться для всех возможных путей. Практически, мы не испытываем никаких проблем, потому что решение, полученное согласно предположению об обратимости, будет правильным решением тогда и только тогда, когда выполнены уравнения равновесия узла. В следующей секции мы используем это как основание, чтобы ввести общую многомерную модель нагрузки.
В этой секции мы рассматриваем обобщения классической теории телетрафика для систем, которые состоят из нескольких типов потоков нагрузки, поступающих на единственный канал или группу каналов или пучков каналов. Каждый поток нагрузки может иметь отдельные параметры и может быть зависимыми от состояния Пуассоновскими потоками вызовов с ограниченными классами и мультислотовым трафиком. Этот общий класс моделей нечувствителен к распределению времени пребывания в системе, которое может быть классом. Мы вводим обобщения по одному и представляем маленькое социологическое исследование, чтобы проиллюстрировать основные идеи.
По сравнению со случаем, который рассматривают в секции 10.1, мы теперь ограничим число одновременных запросов для каждого потока нагрузки (класса). Таким образом, не будет полной доступности, но в отличие от систем перегрузки, где физически существует доступ только к заданным каналам, теперь возможно использование всех каналов, но в любой момент мы можем занять только ограниченное их число. Это обеспечивает сервисная защита (защита числа виртуальных каналов = ограничение на класс обслуживания = приоритетная пороговая стратегия). Таким образом, мы вводим ограничения числа одновременных вызовов в классе j следующим образом:
где
$$\sum_{j=1}^N n_j > n.$$Если последнее ограничение не выполнено, то мы получаем отдельные группы, соответствующие N обычным независимым одномерным
(рис 10.3) Структура диаграммы переходов состояний для двухмерной нагрузки, обрабатываемая с ограничениями класса (см. 10.18). При вычислении вероятностей равновесия состояние (i, j) может быть выражено состоянием (i, j-1), рекурсивно состоянием (1, 0), (i-1, 0) и, наконец (0, 0) (см.10.15)Заметим, что усеченная диаграмма переходов состояний все еще является обратимой и что значение p(i, j) относительно значения $$p(0,0)$$ при усечении не изменяется. Изменяется только нормировочная константа. Фактически, из-за локального свойства равновесия мы можем удалить любое состояние, не изменяя вышеупомянутые свойства. Можно рассмотреть больше общих ограничений класса к наборам потоков нагрузки так, чтобы любой поток нагрузки имел минимум (гарантируемый) числа распределенных каналов.
Мы можем рассматривать
Система удовлетворяет условиям обратимости, см. (10.12). Таким образом, форма произведения также существует для
В системах с интеграцией служб требуемая пропускная способность может зависеть от типа обслуживания. Например, для обслуживания телефонного соединения с передачей только речи требуется один канал (слот), тогда как, например, для передачи видеоизображения может потребоваться $$d$$ каналов одновременно. Мы получаем дополнительные ограничения:
$$0 \le d_j*i_j \le n_j \le n, j=1,2, \dots, N,$$и
$$0 \le \sum_{j=1}^N d_j*i_j \le n,$$где $$i_j$$ - фактическое число вызовов типа $$j$$. Результирующая диаграмма переходов состояний будет обратима, и будет иметь форму произведения.
Ограничения соответствуют, например, физической модели, показанной в рис.10.5.
Предложенная нагрузка $$A_j$$ обычно определяется как среднее число попыток вызова на среднее время пребывания в системе. Если мы измеряем обслуженную нагрузку $$Y_j$$ как среднее число занятых каналов, то потерянная нагрузка, измеренная в каналах, получается:
$$A_l=\sum_{j=1}^NA_jd_j-\sum_{j=1}^NY_j$$| Поток 1: Нагрузка |
Поток 2: Нагрузка РСТ-П |
|---|---|
| $$\lambda_1=2$$ вызова/единица времени | $$S-2=4$$ источника |
| $$\gamma_2=1/3$$ вызова / в единицу времени / свободный источник | |
| $$\mu_1=1(\mbox {единица времени}^{-1})$$ | $$\mu_2=1 \mbox{ единица времени }^{-1}$$ |
| $$\beta_2=\gamma_2/\mu_2=1/3$$ Эрл./свободный источник | |
| $$Z_1=1$$ (пиковость) | $$Z_21/(1+\beta_2)=3/4$$ (пиковость) |
| $$d_1=1$$ канал/вызов | $$d_2=2$$ канал/вызов |
| $$A_1=\lambda_1/\mu_1=2$$ Эрл | $$A_2=S_2*\beta_2/(1+\beta_2)=1$$ Эрл |
| $$n_1=6=n$$ | $$n_2=6=n$$ |
Первый пример модели мультислотового трафика был опубликован Роннбломом (1958 [92]). Статья рассматривает внешнюю нагрузку (исходящую и входящую) и внутреннюю нагрузку в учрежденческой телефонной станции (
Проиллюстрируем вышеупомянутые модели маленьким исследованием. Мы рассматриваем пучок из 6 каналов, на который поступают два потока нагрузки, указанные в таблице 10.1. Пусть второй поток нагрузки - поток мультислотового трафика. Пусть в нашей системе может быть не более трех вызовов типа 2.
Мы должны определить только предложенную нагрузку, не определяя абсолютные значения интенсивности поступления и скорости обслуживания. Предложенная нагрузка, как обычно, определяется как нагрузка, которую несет пучок из бесконечного числа каналов.
На рис.10.4 показана двухмерная диаграмма переходов состояний. Полная сумма всех вероятностей состояний равняется 20,1704. После нормализации мы находим $$p(0, 0) = 0,0496$$ а также следующие вероятности состояния и безусловные вероятности состояний $$p(i,\cdot) $$ и $$p(\cdot, j) $$.
(рис 10.4) Пример 10.3.2: на шесть каналов поступает два Пуассоновских потока нагрузки (PCT-I) (горизонтальные линии состояний) и энгсетовский поток нагрузки (PCT-II) (вертикальные линии состояний). Параметры определены в Таблице 10.1. Если мы определим условную вероятность состояния (0, 0) равной единице, тогда, используя локальное равновесие вероятностей состояний, мы сможем найти условное состояние q(i, j), показанное ниже| $$p(i,j)$$ | $$i=0$$ | $$i=1$$ | $$i=2$$ | $$i=3$$ | $$i=4$$ | $$i=5$$ | $$i=6$$ | $$p(\cdot, j)$$ |
|---|---|---|---|---|---|---|---|---|
| j=6 | 0.0073 | 0.0073 | ||||||
| j=4 | 0.0331 | 0.0661 | 0.0661 | 0.1653 | ||||
| j=2 | 0.0661 | 0.1322 | 0.1322 | 0.0881 | 0.0441 | 0.4627 | ||
| j=0 | 0.0496 | 0.0992 | 0.0992 | 0.0661 | 0.0331 | 0.0132 | 0.0044 | 0.3647 |
| $$p(i,\cdot)$$ | 0.1561 | 0.2975 | 0.2975 | 0.1542 | 0.0771 | 0.0132 | 0.0044 | 1.0000 |
Глобальные вероятности состояния получаются:
$$p(0)=p(0,0)=0.0496\\ p(1)=p(1,0)=0.0992\\ p(2)=p(0,1)+p(2,0)=0.1653\\ p(3)=p(1,2)+p(3,0)=0.1983\\ p(4)=p(0,4)+p(2,2)+p(4,0)=0.1983\\ p(5)=p(1,4)+p(3,2)+p(5,0)=0.1675\\ p(6)=p(0,6)+p(2,4)+p(4,2)+p(6,0)=0.1219$$Критерии качества работы для потока 1
В соответствии со свойствами потока PASTA потери по времени ( $$E_1$$ ), потери по вызовам ( $$B_1$$ ) и по нагрузке ( $$C_1$$ ) - равны. Мы найдем потери по времени $$E_1$$:
Критерии качества работы для потока 2
Потери по времени $$E_2$$ (соотношение времени блокировки системы для потока 2):
$$E_2=p(0,6)+p(1,4)+p(2,4)+p(3,2)+p(4,2)+p(5,0)+p(6,0)\\ =p(5)+p(6),\\ E_2=0,2894$$Потери по вызовам $$B_2$$ (соотношение попыток вызова, блокированных для потока 2):
Общее количество попыток вызова в единицу времени получено из безусловного (одномерного) распределения:
$$x_t=\frac 43*0.3647+\frac 33*0.4627+\frac 23*0.1653+\frac 13*0.0073=1.0616$$Число блокированных попыток вызова в единицу времени получается:
$$x_l=\frac 43*\{p(5,0)+p(6,0)\}+\frac 33*\{p(3,2)+p(4,2)\}+\frac 23*\{p(1,4)+p(2,4)\}+\frac 13*p(0,6)=0.2462$$Следовательно,
$$B_2=\frac{x_l}{x_t}=0.2320.$$Потери по нагрузке $$C_2$$ (соотношение блокированной и предложенной нагрузки):
Обслуженная нагрузка, измеренная для канала, получена из безусловного (одномерного) распределения:
$$Y_2=\sum_{j=0}^6 j*p(\cdot, j),\\ Y_2=2*0.4627+4*0.1653+6*0.0073,\\ Y_2=1.6306 Эрл.$$Предложенная нагрузка, измеренная на канал, равна $$d_2 \times A_2=2$$ Эрл. (Таблица. 10.1). Следовательно, мы имеем:
$$C_2=\frac{2-1.6306}{2}=0.1848.$$Рассмотренный выше пример имеет только 2 потока и 6 каналов, и общее количество состояний равняется 16 (рис.10.4). Когда число потоков нагрузки и каналов увеличивается, число состояний очень быстро увеличивается, и невозможно оценить систему, вычисляя отдельные вероятности состояния. В следующей секции мы вводим алгоритм свертки для систем с потерями, который устраняет эту проблему увеличения состояний.
Теперь рассмотрим группу пучков каналов с общим количеством n гомогенных пучков каналов. Гомогенными мы в данном случае называем каналы, имеющие одну ту же скорость. На группу пучков каналов поступают N различных типов вызовов, называемых потоками, или классами. Вызов типа i требует $$d_i$$ пучков каналов (каналы, слоты) в течение всего времени обслуживания, то есть занятия и освобождения одновременно всех каналов $$d_i$$.
Процессы поступления вызовов - общие зависимые от состояния Пуассоновские процессы. Для i -того процесса поступления вызовов интенсивность прибытия в состоянии $$x_i \times d_i,$$ то есть когда вызовы $$x_i$$ типа i обслуживаются, интенсивность равна $$\lambda_i (x_i)$$. Мы можем ограничить число xi одновременных вызовов типа i так, чтобы:
Будет естественно потребовать, чтобы $$n_i$$ было составным числом, кратным $$d_i.$$ Эта модель описывает, например, систему, показанную на рис.10.5.
(рис 10.5) Обобщение классического телетрафика показывает нагрузку
Упомянутая выше система может быть оценена эффективным способом - алгоритмом свертки, впервые введенным в (Iversen, 1987 [40]). Сначала опишем алгоритм, а затем объясним на примере дальнейшие детали. Алгоритм свертки близко связан с формой произведения.
Алгоритм представлен следующими тремя шагами.
Шаг 1. Вычислите вероятности состояния каждого потока нагрузки, как будто он является единственным в системе, то есть мы рассматриваем классические i мы находим:
Важны только условные значения $$p_i (x)$$, так что мы можем выбрать $$q_i (0) = 1$$ и вычислить значения $$q_i (x)$$ относительно $$q_i (0)$$. Если элемент $$q_i (x)$$ становится больше, чем K (например $$10^{10}$$ ), тогда мы можем разделить все значения $$q_i(j); 0 \le j \le x$$, на K. Чтобы избежать любых проблем вычислений, в дальнейшем желательно нормировать условные вероятности состояний так, чтобы:
Шаг 2. Последовательным свертыванием (оператор свертывания *) мы вычисляем совокупную вероятность состояния для полной системы за исключением потока нагрузки i:
Сначала свертываем $$P_1$$ и $$P_2$$ и получаем $$P_{12}$$ который свертывается с $$P_3,$$ и т.д. Оба закона - коммутативный и ассоциативный - справедливы для оператора свертывания и определены обычным способом (секция 3.2):
$$P_i*P_j=\{p_i(0)*p_j(0), \sum_{x=0}^1p_i(x)*p_j(1-x), \dots , \sum_{x=0}^up_i(x)*p_j(u-x)\},$$где
$$u=min\{n_i+n_j,n\}.$$Заметьте, что производится усечение пространства состояний к $$n$$ состояниям. Даже если $$P_i$$ и $$P_j$$ нормированы, результат свертки в общем случае не нормирован из-за усечения. Его рекомендуется нормировать после каждого свертывания, чтобы избежать любых проблем при вычислении в течение этого шага и на следующем.
Шаг 3. Вычислите потери по времени $$E_i,$$ потери по вызовам $$B_i $$ и потери по нагрузке $$C_i$$ потока $$i$$. Это может быть сделано в процессе свертки:
$$Q_N=Q_{N/i}*P_i.$$Свертка заканчивается:
$$Q_N(j)=\sum_{x=0}^jQ_{N/i}(j-x)*p_i(x)=\sum_{x=0}^jp_x^i(j),$$где для $$p_x^i(j)i$$ обозначает поток нагрузки, $$j$$ - общее количество занятых каналов и $$x$$ - число каналов, занятых потоком $$i$$. Шаги 2-3 повторяются для каждого потока нагрузки.
Далее мы получаем формулы для $$E_i , B_i,$$ и $$C_i.$$
Потери по времени $$E_i$$ для нагрузки потока i получаются:
$$E_i=\sum_{j \in S_{E^i}}p_x^i(j)/Q$$где
$$S_E^i=\{(x,j)|x \le j \le n \wedge (x > n_i-d_i) \vee (j > n-d_i)\},$$Суммирование по всем $$S_{E^i}$$ расширенным состояниям, где вызовы, принадлежащие классу $$i$$, блокированы: набор $$(x > n_i - d_i) $$ соответствует состоянию, в котором поток нагрузки, $$i$$ использовал свою квоту, и соответственно число состояний с меньше чем $$d_i$$ свободных каналов. $$Q$$ - нормировочная константа:
$$Q=\sum_{j=0}Q_N(j).$$(На этом этапе мы обычно нормируем вероятности состояния так, чтобы $$Q=1$$ )
$$B_i$$ потери по вызовам для нагрузки потока $$i$$ - это отношение числа блокированных попыток вызова к общему числу попыток вызовов (оба числа берутся для потока нагрузки $$i$$ в единицу времени). Мы находим:
$$B_i=\frac{\sum_{S_{E^i}}\lambda_i(x)*p_x^i(j)}{\sum_{j-0}^{n_j}\sum_{x=0}^j\lambda_i(x)*p_x^i(j)}.$$Потери по нагрузке $$C_i.$$ Мы определяем их, как обычно предложенную нагрузку, которую обслуживает бесконечная группа пучков каналов. Обслуженная нагрузка для нагрузки потока $$i$$:
$$Y_i=\sum_{j=0}^{n_j}\sum_{x=0}^jx*p_x^i(j).$$Таким образом, мы находим:
$$C_i=\frac{A_i-Y_i}{A_i}.$$Алгоритм реализован в программном обеспечении ATMOS (Листов, Сааби, Иверсен (Listov, Saabye и Iversen, 1989 [74]). Требование к памяти (накопителю) пропорционально $$n$$. Она используется для вычисления вероятности состояния потока нагрузки, когда это необходимо. Практически мы используем память, пропорциональную $$n \times N$$, потому что сохраняем промежуточные результаты свертывания для более позднего повторного использования. Можно показать (Иверсен и Степанов, 1997 [42]), что нам необходимо ( $$4 \times N - 6$$ ) свертывания, когда мы вычисляем характеристики нагрузки для всех $$N$$ потоков нагрузки. Таким образом, время вычисления подчиняется линейной зависимости от $$N$$ и квадратичной для $$n$$.
В принципе мы можем получить $$Q_{N/i}$$ из $$Q_N$$ разверткой и затем в течение повторной свертки $$P_i$$ вычислить критерии качества работы. При этом способе мы не должны повторять все свертки (10.23) для каждого потока нагрузки. Но при осуществлении этого подхода имеются проблемы вычислений. Свертка, с точки зрения вычисления, очень устойчива, а развертка вычисляется не всегда. Однако мы можем применить развертку в некоторых случаях, например, когда источники нагрузки имеют два состояния - вкл\выкл.
| Поток 3: Нагрузка с распределением Паскаля (Отрицательное |
|---|
| $$S_3=-2$$ источника |
| $$\gamma_3=-1/3$$ вызова/единица времени |
| $$\mu_3=1$$ (единица времени -1) |
| $$\beta_3=\gamma_3/\mu_3=-1/3$$ Эрл. на свободный источник |
| $$Z_3=1/(1+ \beta_3)=3/2$$ |
| $$d_3=1$$ канал/вызов |
| $$A_3=S_3*(1-Z_3)=1 Эрл $$ |
| $$n_3=4$$ (максимальное # одновременные вызовы) |
Мы сначала проиллюстрируем алгоритм небольшим примером, где детально покажем вычисления. Рассмотрим систему с 6 каналами и 3 потоками нагрузки. В дополнение к двум потокам в Примере 10.3.2 складываем поток Паскаля с ограничением класса, как показано в Таблице 10.2 (см. Пример 8.7.2). Мы хотим вычислить критерии качества работы потока нагрузки 3.
Шаг 1. Вычисляем $$p_i$$ вероятностей состояния $$(j) $$ каждого потока нагрузки $$i=1,2,3, j=(1,2,\dots, B_j) $$, как будто он существут один. Результаты даются в Таблице 10.3.
Шаг 2. Оцениваем свертывание $$p_1(J)с p_2 (k), p_1* p_2$$, усекаем пространство состояний до $$n = 6$$, нормализуем вероятности так, чтобы мы получить $$p_{12}$$, показанное в Таблице 10.3. Заметим, что это - результат, полученный в Примере 10.3.2.
Шаг 3. Свертываем $$p_{12} (J)сp_3 (k) $$, усекаем в $$n$$ и получаем $$q_{123}(j) $$, как показано в Таблице 10.3. Потери по времени $$E_3$$ получены из детальных вероятностей состояния.
В потоке нагрузки 3 (единственный слот) потери по времени возникают, по опыту, в двух случаях: либо когда все шесть каналов заняты, либо когда поток нагрузки занимает 4 канала (максимальное распределение). Из детальных вероятностей состояния мы получаем:
$$E_3=\frac{q_{123}(6)+p_3(4)*\{p_{12}(0)+p_{12}(1)\}}{0.8678}\\ =\frac{0.1535+0.0279*\{0.0496+0.0992\}}{0.8678},\\ E_3=0.1817$$| Состояние | Вероятности | $$q_{12}(j)$$ | Нормализованная | Вероятности | $$q_{123}(j)$$ | Нормализованная | |
|---|---|---|---|---|---|---|---|
| $$j$$ | $$p_1(j)$$ | $$p_2(j)$$ | $$p_1*p_2$$ | $$p_{12}(j)$$ | $$p_3(j)$$ | $$p_{12}*p_3$$ | $$p_{123}(j)$$ |
| 0 | 0.1360 | 0.3176 | 0.0432 | 0.0496 | 0.4525 | 0.0224 | 0.0259 |
| 1 | 0.2719 | 0.0000 | 0.0864 | 0.0992 | 0.3017 | 0.0599 | 0.0689 |
| 2 | 0.2719 | 0.4235 | 0.1440 | 0.1653 | 0.1508 | 0.1122 | 0.1293 |
| 3 | 0.1813 | 0.0000 | 0.1727 | 0.1983 | 0.0670 | 0.1579 | 0.1819 |
| 4 | 0.0906 | 0.2118 | 0.1727 | 0.1983 | 0.0279 | 0.1825 | 0.2104 |
| 5 | 0.0363 | 0.0000 | 0.1459 | 0.1675 | 0.0000 | 0.1794 | 0.2067 |
| 6 | 0.0121 | 0.0471 | 0.1062 | 0.1219 | 0.0000 | 0.1535 | 0.1769 |
| Всего | 1.0000 | 1.0000 | 0.8711 | 1.0000 | 1.0000 | 0.8678 | 1.0000 |
Заметим, что состояния $$\{p_3 (4) * p_{12} (2)\} $$, включены в состояние $$q_{123} (6) $$. Обслуженная нагрузка для потока нагрузки 3 получена в процессе свертывания $$p_3 (i) $$ и $$p_12} (j) $$ и равна:
$$Y_3=\frac{1}{0.8678}\left \{ \sum_{i=1}^4i*p_3(i) \sum_{j=0}^{6-i}p_{12}(j) \right \},\\ Y_3=\frac{0.6174}{0.8678}=0.7115.$$Потери по нагрузке:
$$C_3=\frac{1-0.7115}{1},\\ C_3=0.2885.$$Потери по вызовам равны:
$$B_3=\frac{x_l}{x_t},$$где $$x_l'$$ является числом вызовов, потерянных в единицу времени, и $$x_t $$ - общее количество попыток вызова в единицу времени. Используя нормализованные вероятности, из Таблицы 10.3 мы получаем:
$$\{\lambda_3(i)=(S_3-i)\lambda_3\}\\ x_l=\lambda_3(0)*\{p_3(0)*p_{12}(6)\}\\ \qquad +\lambda_3(1)*\{p_3(1)*p_{12}(5)\}\\ \qquad +\lambda_3(2)*\{p_3(2)*p_{12}(4)\}\\ \qquad +\lambda_3(3)*\{p_3(3)*p_{12}(3)\}\\ \qquad +\lambda_3(4)*p_3(4)*\{p_{12}(2)+p_{12}(1)+p_{12}(0)\},\\ x_l=0.2503.\\ x_t=\lambda_3(0)*p_3(0)*\sum_{j=0}^5p_{12}(j)\\ \qquad +\lambda_3(1)*p_3(1)*\sum_{j=0}^5p_{12}(j)\\ \qquad +\lambda_3(2)*p_3(2)*\sum_{j=0}^4 p_{12}(j)\\ \qquad +\lambda_3(3)*p_3(3)*\sum_{j=0}^3 p_{12}(j)\\ \qquad +\lambda_3(4)*p_3(4)*\sum_{j=0}^2p_{12}(j),\\ x_t=1.1763$$Тем же способом, обмениваясь результатом свертки нагрузки потока, находим критерии качества работы потока 1 и 2. Общее количество микросостояний в этом примере - 47. Методом свертки уменьшаем число состояния так, чтобы нам никогда не понадобилось более, чем два вектора по $$п +1$$ состоянию каждый, то есть 14 состояний.
Используя программу расчета -ATMOS, получаем следующие результаты, показанные в Таблице 10.4 и Таблице 10.5. Полные потери могут быть разбиты на потери из-за ограничения класса ( $$n_i$$ ) и потери из-за ограниченного числа каналов ( $$n$$ ).
| Вход | Общее число каналов $$n=6$$ | |||||||
|---|---|---|---|---|---|---|---|---|
| Предложенная нагрузка | Пиковость | Максимальное размещение | Размер слота | Среднее время пребывания в системе | Источники | Бета | ||
| $$i$$ | $$A_i$$ | $$Z_i$$ | $$n_i$$ | $$d_i$$ | $$\mu_i^{-1}$$ | $$S_i$$ | $$\beta_i$$ | |
| 1 | 2.0000 | 1.00 | 6 | 1 | 1.00 | $$\infty$$ | 0 | |
| 2 | 2.0000 | 0.75 | 6 | 2 | 1.00 | 4 | 0.3333 | |
| 3 | 1.0000 | 1.50 | 4 | 1 | 1.00 | -2 | -0.3333 | |
Потери по времени, потери по нагрузке, обслуженная нагрузка на выходе:
| Выход | Потери по вызовам | Потери по нагрузке | Потери по времени | Обслуженная нагрузка |
|---|---|---|---|---|
| $$i$$ | $$B_i$$ | $$C_i$$ | $$E_i$$ | $$Y_i$$ |
| 1 | 1.769 200E-01 | 1.769 200E-01 | 1.769 200E-01 | 1.646 160 |
| 2 | 3.346 853E-01 | 2.739 344E-01 | 3.836 316E-01 | 1.452 131 |
| 3 | 2.127 890E-01 | 2.884 898E-01 | 1.817 079E-01 | 0.711 510 |
| Итого | 2.380 397E-01 | 3.809 801 |
Чтобы проиллюстрировать программу расчета ATMOS, рассмотрим в Таблице 10.6 и Таблице 10.7 пример с 1536 пучками каналов и 24 потоками нагрузки. Заметим, что потери по времени независимы от пиковости $$Z_i$$ и пропорциональны размеру слота $$d_i$$, поэтому мы часто имеем:
| Вход | Общее число # $$n=1536$$ | ||||||
|---|---|---|---|---|---|---|---|
| Предложенная нагрузка | Пиковость | Допустимый максимум | Канал/вызов | Среднее время пребывания в системе | Источники | ||
| $$i$$ | $$A_i$$ | $$Z_i$$ | $$n_i$$ | $$d_i$$ | $$\mu_i$$ | $$S$$ | $$\beta$$ |
| 1 | 64.000 | 0.200 | 1536 | 1 | 1.000 | 80.000 | 4.000 |
| 2 | 64.000 | 0.500 | 15.36 | 1 | 1.000 | 128.000 | 1.000 |
| 3 | 64.000 | 1.000 | 1536 | 1 | 1.000 | $$\infty$$ | 0.000 |
| 4 | 64.000 | 2.000 | 1536 | 1 | 1.000 | -64.000 | -0.500 |
| 5 | 64.000 | 4.000 | 1536 | 1 | 1.000 | -21.333 | -0.750 |
| 6 | 64.000 | 8.000 | 1536 | 1 | 1.000 | -9.143 | -0.875 |
| 7 | 32.000 | 0.200 | 1536 | 2 | 1.000 | 40.000 | 4.000 |
| 8 | 32.000 | 0.500 | 1536 | 2 | 1.000 | 64.000 | 1.000 |
| 9 | 32.000 | 1.000 | 1536 | 2 | 1.000 | $$\infty$$ | 0.000 |
| 10 | 32.000 | 2.000 | 1536 | 2 | 1.000 | -32.000 | -0.500 |
| 11 | 32.000 | 4.000 | 1536 | 2 | 1.000 | -10.667 | -0.750 |
| 12 | 32.000 | 8.000 | 1536 | 2 | 1.000 | -4.571 | -0.875 |
| 13 | 16.000 | 0.200 | 1536 | 4 | 1.000 | 20.000 | 4.000 |
| 14 | 16.000 | 0.500 | 1536 | 4 | 1.000 | 32.000 | 1.000 |
| 15 | 16.000 | 1.000 | 1536 | 4 | 1.000 | $$\infty$$ | 0.000 |
| 16 | 16.000 | 2.000 | 1536 | 4 | 1.000 | -16.000 | -0.500 |
| 17 | 16.000 | 4.000 | 1536 | 4 | 1.000 | -5.333 | -0.750 |
| 18 | 16.000 | 8.000 | 1536 | 4 | 1.000 | -2.286 | -0.875 |
| 19 | 8.000 | 0.200 | 1536 | 8 | 1.000 | 10.000 | 4.000 |
| 20 | 8.000 | 0.500 | 1536 | 8 | 1.000 | 16.000 | 1.000 |
| 21 | 8.000 | 1.000 | 1536 | 8 | 1.000 | $$\infty$$ | 0.000 |
| 22 | 8.000 | 2.000 | 1536 | 8 | 1.000 | -8.000 | -0.500 |
| 23 | 8.000 | 4.000 | 1536 | 8 | 1.000 | -2.667 | -0.750 |
| 24 | 8.000 | 8.000 | 1536 | 8 | 1.000 | -1.143 | -0.875 |
Очевидно, что потери по времени зависят только от глобальных вероятностей состояния. Потери по вызовам почти равны потерям по времени. Они мало зависят от размера слота. Можно также ожидать, что потери по вызовам равны потерям по времени с одним удаленным источником ( теорема прибытия ). В таблице с выходными данными в самом правом столбце приведены относительные потери по нагрузке, разделенные на ( $$d_i \times Z_i$$ ), с использованием для нагрузки Пуассона единственного слота ( $$d_i = Z_i = 1$$ ). Заметим, что потери по нагрузке пропорциональны $$d_i \times Z_i,$$ - это является обычным предположением при использовании метода эквивалентной случайной нагрузки ( ERT - Equivalent Random Traffic) (см. Лекция 9). Средняя величина предложенной нагрузки увеличивается линейно с размером слота, тогда как дисперсия увеличивается пропорционально квадрату размера слота. Пиковость (дисперсия/математическое ожидание) - отношение для мультислотового трафика, п
оэтому увеличивается линейно с размером слота. Мы, таким образом, отмечаем, что потери по нагрузке намного более существенны, чем потери по времени и потери по вызовам, для того, чтобы характеризовать рабочие характеристики системы. Если вычислять полную перегрузку по нагрузке, используя метод Фредерикса и Хэйварда (секция 9.3), то мы устанавливаем, что полные потери по нагрузке равняются 6.114 % (см. Пример 9.3.2 и таблицу 10.7). Точное значение - 5.950 %.
| Выход | Потери по вызовам | Потери по нагрузке | Потери по времени | Обслуженная нагрузка | Значение |
|---|---|---|---|---|---|
| $$i$$ | $$B_i$$ | $$C_i$$ | $$E_i$$ | $$Y_i$$ | $$C_i/(d_iZ_i)$$ |
| 1 | 6.187744E-0.3 | 1.243705E-03 | 6.227392E-03 | 63.920403 | 0.9986 |
| 2 | 6.202616E-03 | 3.110956E-03 | 6.227392E-03 | 63.800899 | 0.9991 |
| 3 | 6.227392E-03 | 6.227392E-03 | 6.227392E-03 | 63.601447 | 1.0000 |
| 4 | 6.276886E-03 | 1.247546E-02 | 6.227392E-03 | 63.201570 | 1.0017 |
| 5 | 6.375517E-03 | 2.502346E-02 | 6.227392E-03 | 62.398499 | 1.0046 |
| 6 | 6.570378E-03 | 5.025181E-02 | 6.227392E-03 | 60.783884 | 1.0087 |
| 7 | 1.230795E-02 | 2.486068E-03 | 1.246554E-02 | 63.840892 | 0.9980 |
| 8 | 1.236708E-02 | 6.222014E-03 | 1.246554E-02 | 63.601791 | 0.9991 |
| 9 | 1.246554E-02 | 1.246554E-02 | 1.246554E-02 | 63.202205 | 1.0009 |
| 10 | 1.266184E-02 | 2.500705E-02 | 1.246554E-02 | 62.399549 | 1.0039 |
| 11 | 1.305003E-02 | 5.023347E-02 | 1.246554E-02 | 60.785058 | 1.0083 |
| 12 | 1.379446E-02 | 1.006379E-01 | 1.246554E-02 | 57.559172 | 1.0100 |
| 13 | 2.434998E-02 | 4.966747E-03 | 2.497245E-02 | 63.682128 | 0.9970 |
| 14 | 2.458374E-02 | 1.244484E-02 | 2.497245E-02 | 63.203530 | 0.9992 |
| 15 | 2.497245E-02 | 2.497245E-02 | 2.497245E-02 | 62.401763 | 1.0025 |
| 16 | 2.574255E-02 | 5.019301E-02 | 2.497245E-02 | 60.787647 | 1.0075 |
| 17 | 2.722449E-02 | 1.006755E-01 | 2.497245E-02 | 57556771 | 1.0104 |
| 18 | 2.980277E-02 | 1.972682E-01 | 2.497245E-02 | 51.374835 | 0.9899 |
| 19 | 4.766901E-02 | 9.911790E-03 | 5.009699E-02 | 63.365645 | 0.9948 |
| 20 | 4.858283E-02 | 2.489618E-02 | 5.009699E-02 | 62.406645 | 0.9995 |
| 21 | 5.009699E-02 | 5.009699E-02 | 5.009699E-02 | 60.793792 | 1.0056 |
| 22 | 5.303142E-02 | 1.007214E-01 | 5.009699E-02 | 57.553828 | 1.0109 |
| 23 | 5.818489E-02 | 1.981513E-01 | 5.009699E-02 | 51.318316 | 0.9942 |
| 24 | 6.525455E-02 | 3.583491E-01 | 5.009699E-02 | 41.065660 | 0.8991 |
| Итого | 5.950135E-02 | 1444.605 |
Алгоритм свертки основан на соединении потоков нагрузки, где мы заканчиваем потоком нагрузки, который является сборкой всех потоков нагрузки, кроме того, которым мы интересуемся. Другой подход состоит в том, чтобы собрать пространство состояний в глобальную вероятность состояния.
В случае Пуассоновских потоков вызовов, обобщая (10.10), можно упростить алгоритм. Обозначим $$p_i (x) $$ вклад потока в глобальную вероятность состояния $$p(x) $$:
$$p(x)=\sum_{i=1}^Np_i(x).$$Тогда среднее число каналов, занятых потоком $$i$$, когда система находится в глобальном состоянии $$x$$, равно $$x \times p_i (x) $$. Пусть поток нагрузки i имеет размер слота $$d_i.$$ Из-за обратимости мы получим локальное равновесие для каждого типа нагрузки. Уравнение локального равновесия:
$$\frac{xp_i(x)}{d_i}\mu_i=\lambda_i*p(x-d_i), \qquad x=d_i, d_i+1, \dots, n.$$Левая сторона - поток поступления заявок типа $$i$$ из состояния $$[x] $$ к состоянию $$[x- d_i] $$. Правая сторона - поток убывающих заявок типа $$i$$ от глобального состояния $$[x -d_i ] $$ к состоянию $$[x] $$. Не имеет значения, является ли $$x$$ кратным числом целого числа $$d_i,$$ так как мы рассматриваем только средние значения. Из (10.32) мы получаем:
$$p_i(x)=\frac 1x d_iA_i*p(x-d_i).$$Полная вероятность состояния $$p(x) $$ получена суммированием по всем потокам нагрузки (10.31):
$$p(x)=\frac 1x \sum_{i=1}^N d_iA_ip(x-d_i), \qquad p(x)=0 \qquad for \qquad x < 0$$Вышеупомянутая модель может легко быть обобщена на BPP-нагрузку (Iversen, 2005 [44] ):
$$\frac{xp_i(x)}{d_i}*\mu_i=p(x-d_i)*S_i \gamma_i \qquad p_i(x-d_i)*\frac{x-d_i}{d_i}*\gamma_i.$$С правой стороны первый элемент предполагает, что все источники типа $$i$$ свободны в течение единицы времени.
Чтобы получить значение $$p(x) $$, делим правую и левую часть на
$$\frac{x \mu_i}{d_i}$$Таким образом, мы получаем:
$$p(x)=\begin{cases} 0 x <\\ p(0) x=0\\ \sum_{i=1}^Np_i(x) x=1,2,\dots, n \end{cases}$$где
$$p_i(x)=\frac{d_i}{x}*\frac{S_i \gamma_i}{\mu_i}*p(x-d_i)-\frac{x-d_i}{x}*\frac{\gamma_i}{\mu_i}*p_i(x-d_i)$$ $$p_i(x)=0 \qquad x < d_i.$$Вероятность состояния $$p(0) $$ получена из условия нормировки:
$$\sum_{j=0}^np(j)=\sum_{j=0}^n \sum_{i=1}^N p_i(j)=1$$Выше мы использовали параметры $$(S_i ;\beta_i) $$, чтобы характеризовать потоки нагрузки. Альтернативно можно также использовать $$(A_i , Z_i ) $$, связанные с $$(S_i , \beta_i) $$ ) формулами (8.20) {(8.23). Тогда (10.37) получается:
$$p_i(x)=\frac{d_i}{x}*\frac{A_i}{Z_i}*p(x-d_i)-\frac{x-d_i}{x}*\frac{1-Z_I}{Z_i}*p_i(x-d_I)$$Потери по времени. Для Пуассоновского процесса поступления вызовов мы имеем (10.34). Для практической оценки формулы будем использовать нормализацию на каждом шаге, как это показано в секции 7.4.1. Она заканчивается очень точным и эффективным алгоритмом. При этом способе требуется малое число операций, требуемых объемов и конфигураций памяти, так как мы должны хранить только $$d_i$$ предыдущих вероятностей состояний потока нагрузки $$i$$ и $$max \{d_i\}$$ предыдущих значений глобальных вероятностей состояния. Число операций линейно зависит от числа каналов.
Критерии качества работы
С помощью этого алгоритма мы способны получить критерии качества работы для каждого отдельного потока нагрузки.
Попытки вызова потока $$i$$ требуют $$d_i$$ свободных каналов и будут блокированы с вероятностью:
$$E_i=\sum_{x=n-d_i+1}^n p(i)$$Потери по нагрузке
Из вероятностей состояний $$p_i(x) $$ мы получаем полную обслуженную нагрузку потока $$i$$:
$$Y_i=\sum_{j=1}^N xp_i(x).$$Тогда потери по нагрузке потока $$i$$ получаются:
$$C_i=\frac{A_i*d_i-Y_i}{A_i*d_i}.$$Полная обслуженная нагрузка:
$$Y=\sum_{j=1}^NY_i,$$так что полные потери по нагрузке равны:
$$C=\frac{A-Y}{A},$$где $$A$$ - полная предложенная нагрузка, измеряемая в каналах:
$$A=\sum_{j=1}^N d_iA_i.$$Потери по вызовам
Они могут быть получены из потерь по нагрузке с использованием (8.47):
$$B_i=\frac{(1+\beta_i)C_i}{1+\beta_i C_i}.$$Полные потери по вызовам не могут быть получены по этой формуле, так как мы не имеем глобального значения $$\beta$$.
Имея значение отдельной обслуженной нагрузки и потерь по вызовам по каждому потоку, мы можем найти общее количество предлагаемых вызовов и принятых каждым потоком запросов и определить полные потери по вызовам.
Применим обобщенный алгоритм для Примера 10.3.2. Таблица 10.8 показывает ненормирование вероятности состояния, когда мы принимаем, что нулевое состояние равняется единице. Таблица 10.9 показывает нормированные вероятности состояния и обслуженную нагрузку для каждого
| Состояние | Пуассон | Энгсет | Всего |
|---|---|---|---|
| $$x$$ | $$q_1(x)$$ | $$q_2(x)$$ | $$q(x)$$ |
| 0 | 0 | 0 | 1 |
| 1 | $$\frac 21*2=2$$ | 0 | 2 |
| 2 | $$\frac 22*2=2$$ | $$\frac 22*\frac 43*1-0=\frac 43$$ | $$\frac{10}{3}$$ |
| 3 | $$\frac 23*\frac{10}{3}=\frac{20}{9}$$ | $$\frac 23*\frac 43*2-0=\frac{16}{9}$$ | 4 |
| 4 | $$\frac 24*4=2$$ | $$\frac 24*\frac 43*\frac{10}{3}-\frac 24 *\frac 13*\frac 43=2$$ | 4 |
| 5 | $$\frac 25*4=\frac 85$$ | $$\frac 25*\frac 43*4-\frac 35*\frac 13*\frac{16}{9}=\frac{16}{9}$$ | $$\frac{152}{45}$$ |
| 6 | $$\frac 25*\frac{152}{45}=\frac{152}{135}$$ | $$\frac26* \frac 43*4-\frac 46*\frac 13*2=\frac{180}{135}$$ | $$\frac{332}{135}$$ |
| Всего | $$\frac{2723}{135}$$ |
| Состояние | Пуассон | Энгсет | Всего | |||
|---|---|---|---|---|---|---|
| $$x$$ | $$p_1(x)$$ | $$x*p_1(x)$$ | $$p_2(x)$$ | $$x*p_2(x)$$ | $$p(x)$$ | $$y-x*p(x)$$ |
| 0 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0496 | 0.0000 |
| 1 | 0.0992 | 0.0992 | 0.0000 | 0.0000 | 0.0992 | 0.0992 |
| 2 | 0.0992 | 0.1983 | 0.0661 | 0.1322 | 0.1653 | 0.3305 |
| 3 | 0.1102 | 0.3305 | 0.0881 | 0.2644 | 0.1983 | 0.5949 |
| 4 | 0.0992 | 0.3966 | 0.0992 | 0.3966 | 0.1983 | 0.7932 |
| 5 | 0.0793 | 0.3966 | 0.0881 | 0.4407 | 0.1675 | 0.8373 |
| 6 | 0.0558 | 0.3349 | 0.0661 | 0.3966 | 0.1219 | 0.7315 |
| Всего | 1.7562 | 1.6306 | 1.0000 | 3.3867 |
потока в каждом состоянии. В компьютерной программе мы нормализовали бы вероятности состояния после каждой итерации (увеличивая число линий на единицу) и вычислили бы объединенную полную нагрузку для каждого потока. Это значение нагрузки должно быть, конечно, также быть нормализовано на каждом шаге. Поэтому мы должны хранить только предыдущие значения $$d_i$$ и обслуженную нагрузку каждого потока нагрузки.
Мы получаем следующие критерии качества работы, которые, естественно, совпадают с уже полученным результатом алгоритма свертки.
$$E_1=p(6)=0.1219\\ E_2=p(5)+p(6)=0.2894\\ C_1=\frac{2*1-1.7562}{2*1}=0.1219\\ C_2=\frac{1*2-1.6306}{1*2}=0.1847\\ B_1=\frac{(1+0)*0.1219}{1+0*0.1219}=0.1219\\ B_1=\frac{(1+1/3)*0.1847}{1+(1/3)*0.1847}=0.2320$$Алгоритм свертки для систем с потерями был сначала издан в (Iversen, 1987 [40]). Подобный подход к менее общей модели был издан в двух статьях Россом и Цангом (1990 [90]), (1990 [91]) независимо от первоначальной статьи 1987 г., даже притом, что она была известна авторам.
Обобщенный алгоритм в секции 10.5.2 новый, и включает алгоритм Делброука (Делброук, 1983 [22]), который более сложен для проведения оценок. По сравнению со всеми другими алгоритмами обобщенный алгоритм требует намного меньше памяти и операций. Нормализуя вероятности состояния в каждой итерации, мы получаем очень точный и простой алгоритм. В принципе, можно применить обобщенный алгоритм для нагрузки
Алгоритм свертки - более общий инструмент, чем обобщенный алгоритм, поскольку учитывает минимальное и максимальное распределение каналов для каждого потока нагрузки. Обобщенный алгоритм не сохраняет запись фактического числа запросов для каждого потока. Алгоритм свертывания, кроме того, учитывает зависимые от состояния произвольные процессы поступления вызовов.
является общей многомерной B-формулой Эрланга.
Мы рассматриваем группу n пучков каналов (каналы, слоты), которым предлагают два независимых
Обозначим состояние системы $$(i, j)$$, где $$i$$ - число вызовов от потока 1, а $$j$$ - число вызовов от потока 2. Выполняются следующие ограничения:
$$0 \le i \le n,\\ 0 \le j \le n,\\ 0 \le i+j \le n.$$Диаграмма переходов состояний показана на рис.10.1. Согласно предположению о статистическом равновесии, вероятности состояний могут быть получены решением глобальных уравнений равновесия для каждого узла (уравнения узла), всего $$(n + 1) (n + 2)/2$$ уравнения.
(рис 10.1) Двухмерная диаграмма переходов состояний для системы с потерями с n каналами, которым предлагают два PCT- I потока нагрузки.Это эквивалентно диаграмме переходов состояний для
Как мы увидим в следующей секции, эта диаграмма соответствует обратимому марковскому процессу, который имеет локальное равновесие и, кроме того, решение имеет форму произведения ( product form ). Мы можем легко показать, что глобальные уравнения равновесия удовлетворяют следующим вероятностям состояния, которые могут быть записаны в форме произведения:
$$p(i,j)=p(i)*p(j),\\ =Q*\frac{A_i^1}{i!}*\frac{A_2^j}{j!},$$где $$p (i)$$ и $$p (j)$$ - одномерные усеченные Q - нормировочные константы, и $$(i, j)$$ выполняют вышеупомянутые ограничения (10.1). Поскольку рассматриваются Пуассоновские потоки вызовов, которые обладают свойством PASTA (Пуассоновское поступление вызовов, наблюдаемое за среднее время), потери по времени, потери по вызовам и потери по нагрузке равны между собой для обоих потоков нагрузки, и они равняются $$P (i + j = n)$$.
Биноминальным разложением или сверткой двух Пуассоновских распределений мы находим следующие объединенные вероятности состояний, где $$Q$$ получено нормализацией:
$$p(i+j=x)=Q*\frac{(A_1+A_2)^x}{x!},$$ $$Q^{-1}=\sum_{v=0}^n\frac{(A_1+A_2)^v}{v!}.$$Это усеченное Пуассоновское распределение (7.9) с предложенной нагрузкой:
$$A=A_1+A_2$$Мы можем также интерпретировать эту модель как систему Эрланга с потерями с одним Пуассоновским потоком вызовов и гиперраспределенными временами пребывания в системе следующим образом. Полный процесс поступления вызовов - суперпозиция двух Пуассоновских процессов с полной интенсивностью поступления:
$$\lambda=\lambda_1+\lambda_2,$$и распределение времени пребывания в системе является гиперраспределенным:
$$f(t)=\frac{\lambda_1}{\lambda_1+\lambda_2}*\mu_1*e^{-\mu_1t}+\frac{\lambda_2}{\lambda_1+\lambda_2}*\mu_2*e^{-\mu_2t}.$$Мы присваиваем веса эти двум экспоненциальным распределениям согласно относительному числу вызовов в единицу времени. Среднее время обслуживания и распределение времени пребывания в системе является гиперраспределенным:
$$m_1=\frac{\lambda_1}{\lambda_1+\lambda_2}*\frac{1}{\mu_1}+\frac{\lambda_2}{\lambda_1 +\lambda_2}*\frac{1}{\mu_2}=\frac{A_1+A_2}{\lambda_1+ \lambda_2},\\ m_1=\frac{A}{\lambda}$$и соответствует предложенной нагрузке.
Таким образом, мы показали, что
Можно обобщить вышеупомянутую модель на $$N$$ потоков нагрузки:
$$p(i_1, i_2, \dots, i_N)=Q*\frac{A_1^{i_1}}{i_1!}*\frac{A_2^{i_2}}{i_2!} \dots \frac{A_N^{i_N}}{i_N!}, 0 \le i_j \le n, \sum_{j=1}^Ni_j \le n,$$Данная модель является общей многомерной B-формулой Эрланга. Обобщая (10.3), мы замечаем, что глобальные вероятности состояния могут быть вычислены следующей рекурсией, где q(x) обозначает вероятность относительного состояния, и $$p(x)$$ - абсолютные вероятности состояния:
Если использовать рекурсию с нормированием (секция 7.4), то мы получаем рекурсивную формулу B- Эрланга. Формула (10.10) подобна уравнениям равновесия для Пуассоновского случая, когда:
$$A=\sum_{j=1}^NA_j$$Потери по времени - $$E = p(n)$$, и в соответствии со свойствами потока PASTA, потери по времени также равны потерям по вызовам и по нагрузке. Числовые оценки мы рассмотрим в секции 10.4. Многомерные системы были сначала упомянуты Эрлангом и более тщательно рассмотрены Иенсоном в Erlangbook (Jensen, 1948 ).
В предыдущей секции мы рассматривали двухмерную диаграмму переходов состояний. Для увеличивающегося числа потоков нагрузки число состояний (и следовательно уравнений) увеличивается очень быстро. Однако, можно упростить проблему, используя структуру диаграммы переходов состояний. Рассмотрим двухмерную диаграмму переходов состояний, показанную в рис. 10.2. Для четырех соседних состояний поток в направлении по часовой стрелке должен равняться потоку в противоположном направлении (Kingman, 1969 [64]), (Sutton, 1980 [95]). Взглянем на рис. 10.2.
(рис 10.2) Критерии Колмогорова - необходимое и достаточное условие для обратимости двухмерного марковского процесса: циркулирующий поток среди четырех соседних состояний в этом квадрате равняется нулю. Поток по часовой стрелке равняется потоку против часовой стрелки (10.12).По часовой стрелке:
$$[i,j] \to [i ,j+1]: p((i ,j)* \lambda_2 (i ,j)\\ [i ,j +1] \to [i+1 ,j+1]: p(i ,j +1)*\lambda_1(i ,j +1)\\ [i+1 ,j+1] \to [i+1 ,j]: p(i+1 ,j+1)*\mu_2(i+1 ,j+1)\\ [i+1 ,j] \to [i ,j]: p(i+1,j)*\mu_1(i+1,j),$$Против часовой стрелки:
$$[i,j] \to [i+1 ,j]: \qquad p(i ,j)* \lambda_1 (i ,j)\\ [i+1 ,j ] \to [i+1 ,j+1]: \qquad p(i+1 ,j)*\lambda_2(i+1 ,j )\\ [i+1 ,j+1] \to [i ,j+1]: \qquad p(i+1 ,j+1)*\mu_1(i+1 ,j+1)\\ [i ,j+1] \to [i ,j]: \qquad p(i,j+1)*\mu_2(i,j+1)$$Мы можем сократить оба выражения на вероятности состояния и затем получить условие (10.12). Необходимое и достаточное условие для обратимости - что следующие два выражения являются равными.
По часовой стрелке:
$$\lambda_2(i ,j)*\lambda_1(i ,j+1)*\mu_2(i+1,j+1)*\mu_1(i+1,j)$$Против часовой стрелки:
$$\lambda_1(i ,j)*\lambda_2(i+1,j)*\mu_1(i+1,j+1)*\mu_2(i,j+1).$$Если эти два выражения равны, то имеется локальное или частичное равновесие. Таким образом, необходимым условием для обратимости является то, что если есть поток (стрелка) от состояния i к состоянию j, тогда должен также быть поток (стрелка) от состояния j до состояния i. Мы можем применить уравнения сечения между любыми двумя подключенными состояниями. Итак, из рисунка 10.2 мы получаем:
Мы можем выразить любую вероятность состояния $$p(i, j)$$ с помощью вероятности состояния $$p(0, 0)$$, выбирая любой путь между этими двумя состояниями ( критерии Колмогорова ). Мы можем, например, выбрать путь:
$$(0,0),(1,0),\dots,(i,0),(i,1),\dots,( i ,j),$$Тогда получаем следующее уравнение равновесия:
$$p(i ,j)=\frac{\lambda_1(0,0)}{\mu_1(1,0)}*\frac{\lambda_1(1,0)}{\mu_1(2,0)} \dots \frac{\lambda_1(i-1,0)}{\mu_1(i,0)}*\frac{\lambda_2(i,0)}{\mu_2(i,1)}*\frac{\lambda_2(i,1)}{\mu_2(i,2)} \dots \frac{\lambda_2(i,j-1)}{\mu_2(i ,j)}*p(0,0)$$Мы находим $$p(0, 0)$$ нормировкой полной вероятности событий. Условие для обратимости будет выполнено во многих случаях, например, для:
$$\lambda_1(i ,j)=\lambda_1(i), \qquad \mu_1(i ,j)=i*\mu_1,$$ $$\lambda_2(i ,j)=\lambda_2(j), \qquad \mu_2(i ,j)=j*\mu_2.$$Если мы рассматриваем многомерную систему с потерями, имеющую N потоков нагрузки, то любым потоком нагрузки может быть зависимый от состояния Пуассоновский процесс. В конкретном потоке могут быть нагрузки типа N - мерных систем условия обратимости аналогичны (10.12). Критерий Колмогорова должен выполняться для всех возможных путей. Практически, мы не испытываем никаких проблем, потому что решение, полученное согласно предположению об обратимости, будет правильным решением тогда и только тогда, когда выполнены уравнения равновесия узла. В следующей секции мы используем это как основание, чтобы ввести общую многомерную модель нагрузки.
В этой секции мы рассматриваем обобщения классической теории телетрафика для систем, которые состоят из нескольких типов потоков нагрузки, поступающих на единственный канал или группу каналов или пучков каналов. Каждый поток нагрузки может иметь отдельные параметры и может быть зависимыми от состояния Пуассоновскими потоками вызовов с ограниченными классами и мультислотовым трафиком. Этот общий класс моделей нечувствителен к распределению времени пребывания в системе, которое может быть классом. Мы вводим обобщения по одному и представляем маленькое социологическое исследование, чтобы проиллюстрировать основные идеи.
По сравнению со случаем, который рассматривают в секции 10.1, мы теперь ограничим число одновременных запросов для каждого потока нагрузки (класса). Таким образом, не будет полной доступности, но в отличие от систем перегрузки, где физически существует доступ только к заданным каналам, теперь возможно использование всех каналов, но в любой момент мы можем занять только ограниченное их число. Это обеспечивает сервисная защита (защита числа виртуальных каналов = ограничение на класс обслуживания = приоритетная пороговая стратегия). Таким образом, мы вводим ограничения числа одновременных вызовов в классе j следующим образом:
где
$$\sum_{j=1}^N n_j > n.$$Если последнее ограничение не выполнено, то мы получаем отдельные группы, соответствующие N обычным независимым одномерным
(рис 10.3) Структура диаграммы переходов состояний для двухмерной нагрузки, обрабатываемая с ограничениями класса (см. 10.18). При вычислении вероятностей равновесия состояние (i, j) может быть выражено состоянием (i, j-1), рекурсивно состоянием (1, 0), (i-1, 0) и, наконец (0, 0) (см.10.15)Заметим, что усеченная диаграмма переходов состояний все еще является обратимой и что значение p(i, j) относительно значения $$p(0,0)$$ при усечении не изменяется. Изменяется только нормировочная константа. Фактически, из-за локального свойства равновесия мы можем удалить любое состояние, не изменяя вышеупомянутые свойства. Можно рассмотреть больше общих ограничений класса к наборам потоков нагрузки так, чтобы любой поток нагрузки имел минимум (гарантируемый) числа распределенных каналов.
Мы можем рассматривать
Система удовлетворяет условиям обратимости, см. (10.12). Таким образом, форма произведения также существует для
В системах с интеграцией служб требуемая пропускная способность может зависеть от типа обслуживания. Например, для обслуживания телефонного соединения с передачей только речи требуется один канал (слот), тогда как, например, для передачи видеоизображения может потребоваться $$d$$ каналов одновременно. Мы получаем дополнительные ограничения:
$$0 \le d_j*i_j \le n_j \le n, j=1,2, \dots, N,$$и
$$0 \le \sum_{j=1}^N d_j*i_j \le n,$$где $$i_j$$ - фактическое число вызовов типа $$j$$. Результирующая диаграмма переходов состояний будет обратима, и будет иметь форму произведения.
Ограничения соответствуют, например, физической модели, показанной в рис.10.5.
Предложенная нагрузка $$A_j$$ обычно определяется как среднее число попыток вызова на среднее время пребывания в системе. Если мы измеряем обслуженную нагрузку $$Y_j$$ как среднее число занятых каналов, то потерянная нагрузка, измеренная в каналах, получается:
$$A_l=\sum_{j=1}^NA_jd_j-\sum_{j=1}^NY_j$$| Поток 1: Нагрузка |
Поток 2: Нагрузка РСТ-П |
|---|---|
| $$\lambda_1=2$$ вызова/единица времени | $$S-2=4$$ источника |
| $$\gamma_2=1/3$$ вызова / в единицу времени / свободный источник | |
| $$\mu_1=1(\mbox {единица времени}^{-1})$$ | $$\mu_2=1 \mbox{ единица времени }^{-1}$$ |
| $$\beta_2=\gamma_2/\mu_2=1/3$$ Эрл./свободный источник | |
| $$Z_1=1$$ (пиковость) | $$Z_21/(1+\beta_2)=3/4$$ (пиковость) |
| $$d_1=1$$ канал/вызов | $$d_2=2$$ канал/вызов |
| $$A_1=\lambda_1/\mu_1=2$$ Эрл | $$A_2=S_2*\beta_2/(1+\beta_2)=1$$ Эрл |
| $$n_1=6=n$$ | $$n_2=6=n$$ |
Первый пример модели мультислотового трафика был опубликован Роннбломом (1958 [92]). Статья рассматривает внешнюю нагрузку (исходящую и входящую) и внутреннюю нагрузку в учрежденческой телефонной станции (
Проиллюстрируем вышеупомянутые модели маленьким исследованием. Мы рассматриваем пучок из 6 каналов, на который поступают два потока нагрузки, указанные в таблице 10.1. Пусть второй поток нагрузки - поток мультислотового трафика. Пусть в нашей системе может быть не более трех вызовов типа 2.
Мы должны определить только предложенную нагрузку, не определяя абсолютные значения интенсивности поступления и скорости обслуживания. Предложенная нагрузка, как обычно, определяется как нагрузка, которую несет пучок из бесконечного числа каналов.
На рис.10.4 показана двухмерная диаграмма переходов состояний. Полная сумма всех вероятностей состояний равняется 20,1704. После нормализации мы находим $$p(0, 0) = 0,0496$$ а также следующие вероятности состояния и безусловные вероятности состояний $$p(i,\cdot) $$ и $$p(\cdot, j) $$.
(рис 10.4) Пример 10.3.2: на шесть каналов поступает два Пуассоновских потока нагрузки (PCT-I) (горизонтальные линии состояний) и энгсетовский поток нагрузки (PCT-II) (вертикальные линии состояний). Параметры определены в Таблице 10.1. Если мы определим условную вероятность состояния (0, 0) равной единице, тогда, используя локальное равновесие вероятностей состояний, мы сможем найти условное состояние q(i, j), показанное ниже| $$p(i,j)$$ | $$i=0$$ | $$i=1$$ | $$i=2$$ | $$i=3$$ | $$i=4$$ | $$i=5$$ | $$i=6$$ | $$p(\cdot, j)$$ |
|---|---|---|---|---|---|---|---|---|
| j=6 | 0.0073 | 0.0073 | ||||||
| j=4 | 0.0331 | 0.0661 | 0.0661 | 0.1653 | ||||
| j=2 | 0.0661 | 0.1322 | 0.1322 | 0.0881 | 0.0441 | 0.4627 | ||
| j=0 | 0.0496 | 0.0992 | 0.0992 | 0.0661 | 0.0331 | 0.0132 | 0.0044 | 0.3647 |
| $$p(i,\cdot)$$ | 0.1561 | 0.2975 | 0.2975 | 0.1542 | 0.0771 | 0.0132 | 0.0044 | 1.0000 |
Глобальные вероятности состояния получаются:
$$p(0)=p(0,0)=0.0496\\ p(1)=p(1,0)=0.0992\\ p(2)=p(0,1)+p(2,0)=0.1653\\ p(3)=p(1,2)+p(3,0)=0.1983\\ p(4)=p(0,4)+p(2,2)+p(4,0)=0.1983\\ p(5)=p(1,4)+p(3,2)+p(5,0)=0.1675\\ p(6)=p(0,6)+p(2,4)+p(4,2)+p(6,0)=0.1219$$Критерии качества работы для потока 1
В соответствии со свойствами потока PASTA потери по времени ( $$E_1$$ ), потери по вызовам ( $$B_1$$ ) и по нагрузке ( $$C_1$$ ) - равны. Мы найдем потери по времени $$E_1$$:
Критерии качества работы для потока 2
Потери по времени $$E_2$$ (соотношение времени блокировки системы для потока 2):
$$E_2=p(0,6)+p(1,4)+p(2,4)+p(3,2)+p(4,2)+p(5,0)+p(6,0)\\ =p(5)+p(6),\\ E_2=0,2894$$Потери по вызовам $$B_2$$ (соотношение попыток вызова, блокированных для потока 2):
Общее количество попыток вызова в единицу времени получено из безусловного (одномерного) распределения:
$$x_t=\frac 43*0.3647+\frac 33*0.4627+\frac 23*0.1653+\frac 13*0.0073=1.0616$$Число блокированных попыток вызова в единицу времени получается:
$$x_l=\frac 43*\{p(5,0)+p(6,0)\}+\frac 33*\{p(3,2)+p(4,2)\}+\frac 23*\{p(1,4)+p(2,4)\}+\frac 13*p(0,6)=0.2462$$Следовательно,
$$B_2=\frac{x_l}{x_t}=0.2320.$$Потери по нагрузке $$C_2$$ (соотношение блокированной и предложенной нагрузки):
Обслуженная нагрузка, измеренная для канала, получена из безусловного (одномерного) распределения:
$$Y_2=\sum_{j=0}^6 j*p(\cdot, j),\\ Y_2=2*0.4627+4*0.1653+6*0.0073,\\ Y_2=1.6306 Эрл.$$Предложенная нагрузка, измеренная на канал, равна $$d_2 \times A_2=2$$ Эрл. (Таблица. 10.1). Следовательно, мы имеем:
$$C_2=\frac{2-1.6306}{2}=0.1848.$$Рассмотренный выше пример имеет только 2 потока и 6 каналов, и общее количество состояний равняется 16 (рис.10.4). Когда число потоков нагрузки и каналов увеличивается, число состояний очень быстро увеличивается, и невозможно оценить систему, вычисляя отдельные вероятности состояния. В следующей секции мы вводим алгоритм свертки для систем с потерями, который устраняет эту проблему увеличения состояний.
Теперь рассмотрим группу пучков каналов с общим количеством n гомогенных пучков каналов. Гомогенными мы в данном случае называем каналы, имеющие одну ту же скорость. На группу пучков каналов поступают N различных типов вызовов, называемых потоками, или классами. Вызов типа i требует $$d_i$$ пучков каналов (каналы, слоты) в течение всего времени обслуживания, то есть занятия и освобождения одновременно всех каналов $$d_i$$.
Процессы поступления вызовов - общие зависимые от состояния Пуассоновские процессы. Для i -того процесса поступления вызовов интенсивность прибытия в состоянии $$x_i \times d_i,$$ то есть когда вызовы $$x_i$$ типа i обслуживаются, интенсивность равна $$\lambda_i (x_i)$$. Мы можем ограничить число xi одновременных вызовов типа i так, чтобы:
Будет естественно потребовать, чтобы $$n_i$$ было составным числом, кратным $$d_i.$$ Эта модель описывает, например, систему, показанную на рис.10.5.
(рис 10.5) Обобщение классического телетрафика показывает нагрузку
Упомянутая выше система может быть оценена эффективным способом - алгоритмом свертки, впервые введенным в (Iversen, 1987 [40]). Сначала опишем алгоритм, а затем объясним на примере дальнейшие детали. Алгоритм свертки близко связан с формой произведения.
Алгоритм представлен следующими тремя шагами.
Шаг 1. Вычислите вероятности состояния каждого потока нагрузки, как будто он является единственным в системе, то есть мы рассматриваем классические i мы находим:
Важны только условные значения $$p_i (x)$$, так что мы можем выбрать $$q_i (0) = 1$$ и вычислить значения $$q_i (x)$$ относительно $$q_i (0)$$. Если элемент $$q_i (x)$$ становится больше, чем K (например $$10^{10}$$ ), тогда мы можем разделить все значения $$q_i(j); 0 \le j \le x$$, на K. Чтобы избежать любых проблем вычислений, в дальнейшем желательно нормировать условные вероятности состояний так, чтобы:
Шаг 2. Последовательным свертыванием (оператор свертывания *) мы вычисляем совокупную вероятность состояния для полной системы за исключением потока нагрузки i:
Сначала свертываем $$P_1$$ и $$P_2$$ и получаем $$P_{12}$$ который свертывается с $$P_3,$$ и т.д. Оба закона - коммутативный и ассоциативный - справедливы для оператора свертывания и определены обычным способом (секция 3.2):
$$P_i*P_j=\{p_i(0)*p_j(0), \sum_{x=0}^1p_i(x)*p_j(1-x), \dots , \sum_{x=0}^up_i(x)*p_j(u-x)\},$$где
$$u=min\{n_i+n_j,n\}.$$Заметьте, что производится усечение пространства состояний к $$n$$ состояниям. Даже если $$P_i$$ и $$P_j$$ нормированы, результат свертки в общем случае не нормирован из-за усечения. Его рекомендуется нормировать после каждого свертывания, чтобы избежать любых проблем при вычислении в течение этого шага и на следующем.
Шаг 3. Вычислите потери по времени $$E_i,$$ потери по вызовам $$B_i $$ и потери по нагрузке $$C_i$$ потока $$i$$. Это может быть сделано в процессе свертки:
$$Q_N=Q_{N/i}*P_i.$$Свертка заканчивается:
$$Q_N(j)=\sum_{x=0}^jQ_{N/i}(j-x)*p_i(x)=\sum_{x=0}^jp_x^i(j),$$где для $$p_x^i(j)i$$ обозначает поток нагрузки, $$j$$ - общее количество занятых каналов и $$x$$ - число каналов, занятых потоком $$i$$. Шаги 2-3 повторяются для каждого потока нагрузки.
Далее мы получаем формулы для $$E_i , B_i,$$ и $$C_i.$$
Потери по времени $$E_i$$ для нагрузки потока i получаются:
$$E_i=\sum_{j \in S_{E^i}}p_x^i(j)/Q$$где
$$S_E^i=\{(x,j)|x \le j \le n \wedge (x > n_i-d_i) \vee (j > n-d_i)\},$$Суммирование по всем $$S_{E^i}$$ расширенным состояниям, где вызовы, принадлежащие классу $$i$$, блокированы: набор $$(x > n_i - d_i) $$ соответствует состоянию, в котором поток нагрузки, $$i$$ использовал свою квоту, и соответственно число состояний с меньше чем $$d_i$$ свободных каналов. $$Q$$ - нормировочная константа:
$$Q=\sum_{j=0}Q_N(j).$$(На этом этапе мы обычно нормируем вероятности состояния так, чтобы $$Q=1$$ )
$$B_i$$ потери по вызовам для нагрузки потока $$i$$ - это отношение числа блокированных попыток вызова к общему числу попыток вызовов (оба числа берутся для потока нагрузки $$i$$ в единицу времени). Мы находим:
$$B_i=\frac{\sum_{S_{E^i}}\lambda_i(x)*p_x^i(j)}{\sum_{j-0}^{n_j}\sum_{x=0}^j\lambda_i(x)*p_x^i(j)}.$$Потери по нагрузке $$C_i.$$ Мы определяем их, как обычно предложенную нагрузку, которую обслуживает бесконечная группа пучков каналов. Обслуженная нагрузка для нагрузки потока $$i$$:
$$Y_i=\sum_{j=0}^{n_j}\sum_{x=0}^jx*p_x^i(j).$$Таким образом, мы находим:
$$C_i=\frac{A_i-Y_i}{A_i}.$$Алгоритм реализован в программном обеспечении ATMOS (Листов, Сааби, Иверсен (Listov, Saabye и Iversen, 1989 [74]). Требование к памяти (накопителю) пропорционально $$n$$. Она используется для вычисления вероятности состояния потока нагрузки, когда это необходимо. Практически мы используем память, пропорциональную $$n \times N$$, потому что сохраняем промежуточные результаты свертывания для более позднего повторного использования. Можно показать (Иверсен и Степанов, 1997 [42]), что нам необходимо ( $$4 \times N - 6$$ ) свертывания, когда мы вычисляем характеристики нагрузки для всех $$N$$ потоков нагрузки. Таким образом, время вычисления подчиняется линейной зависимости от $$N$$ и квадратичной для $$n$$.
В принципе мы можем получить $$Q_{N/i}$$ из $$Q_N$$ разверткой и затем в течение повторной свертки $$P_i$$ вычислить критерии качества работы. При этом способе мы не должны повторять все свертки (10.23) для каждого потока нагрузки. Но при осуществлении этого подхода имеются проблемы вычислений. Свертка, с точки зрения вычисления, очень устойчива, а развертка вычисляется не всегда. Однако мы можем применить развертку в некоторых случаях, например, когда источники нагрузки имеют два состояния - вкл\выкл.
| Поток 3: Нагрузка с распределением Паскаля (Отрицательное |
|---|
| $$S_3=-2$$ источника |
| $$\gamma_3=-1/3$$ вызова/единица времени |
| $$\mu_3=1$$ (единица времени -1) |
| $$\beta_3=\gamma_3/\mu_3=-1/3$$ Эрл. на свободный источник |
| $$Z_3=1/(1+ \beta_3)=3/2$$ |
| $$d_3=1$$ канал/вызов |
| $$A_3=S_3*(1-Z_3)=1 Эрл $$ |
| $$n_3=4$$ (максимальное # одновременные вызовы) |
Мы сначала проиллюстрируем алгоритм небольшим примером, где детально покажем вычисления. Рассмотрим систему с 6 каналами и 3 потоками нагрузки. В дополнение к двум потокам в Примере 10.3.2 складываем поток Паскаля с ограничением класса, как показано в Таблице 10.2 (см. Пример 8.7.2). Мы хотим вычислить критерии качества работы потока нагрузки 3.
Шаг 1. Вычисляем $$p_i$$ вероятностей состояния $$(j) $$ каждого потока нагрузки $$i=1,2,3, j=(1,2,\dots, B_j) $$, как будто он существут один. Результаты даются в Таблице 10.3.
Шаг 2. Оцениваем свертывание $$p_1(J)с p_2 (k), p_1* p_2$$, усекаем пространство состояний до $$n = 6$$, нормализуем вероятности так, чтобы мы получить $$p_{12}$$, показанное в Таблице 10.3. Заметим, что это - результат, полученный в Примере 10.3.2.
Шаг 3. Свертываем $$p_{12} (J)сp_3 (k) $$, усекаем в $$n$$ и получаем $$q_{123}(j) $$, как показано в Таблице 10.3. Потери по времени $$E_3$$ получены из детальных вероятностей состояния.
В потоке нагрузки 3 (единственный слот) потери по времени возникают, по опыту, в двух случаях: либо когда все шесть каналов заняты, либо когда поток нагрузки занимает 4 канала (максимальное распределение). Из детальных вероятностей состояния мы получаем:
$$E_3=\frac{q_{123}(6)+p_3(4)*\{p_{12}(0)+p_{12}(1)\}}{0.8678}\\ =\frac{0.1535+0.0279*\{0.0496+0.0992\}}{0.8678},\\ E_3=0.1817$$| Состояние | Вероятности | $$q_{12}(j)$$ | Нормализованная | Вероятности | $$q_{123}(j)$$ | Нормализованная | |
|---|---|---|---|---|---|---|---|
| $$j$$ | $$p_1(j)$$ | $$p_2(j)$$ | $$p_1*p_2$$ | $$p_{12}(j)$$ | $$p_3(j)$$ | $$p_{12}*p_3$$ | $$p_{123}(j)$$ |
| 0 | 0.1360 | 0.3176 | 0.0432 | 0.0496 | 0.4525 | 0.0224 | 0.0259 |
| 1 | 0.2719 | 0.0000 | 0.0864 | 0.0992 | 0.3017 | 0.0599 | 0.0689 |
| 2 | 0.2719 | 0.4235 | 0.1440 | 0.1653 | 0.1508 | 0.1122 | 0.1293 |
| 3 | 0.1813 | 0.0000 | 0.1727 | 0.1983 | 0.0670 | 0.1579 | 0.1819 |
| 4 | 0.0906 | 0.2118 | 0.1727 | 0.1983 | 0.0279 | 0.1825 | 0.2104 |
| 5 | 0.0363 | 0.0000 | 0.1459 | 0.1675 | 0.0000 | 0.1794 | 0.2067 |
| 6 | 0.0121 | 0.0471 | 0.1062 | 0.1219 | 0.0000 | 0.1535 | 0.1769 |
| Всего | 1.0000 | 1.0000 | 0.8711 | 1.0000 | 1.0000 | 0.8678 | 1.0000 |
Заметим, что состояния $$\{p_3 (4) * p_{12} (2)\} $$, включены в состояние $$q_{123} (6) $$. Обслуженная нагрузка для потока нагрузки 3 получена в процессе свертывания $$p_3 (i) $$ и $$p_12} (j) $$ и равна:
$$Y_3=\frac{1}{0.8678}\left \{ \sum_{i=1}^4i*p_3(i) \sum_{j=0}^{6-i}p_{12}(j) \right \},\\ Y_3=\frac{0.6174}{0.8678}=0.7115.$$Потери по нагрузке:
$$C_3=\frac{1-0.7115}{1},\\ C_3=0.2885.$$Потери по вызовам равны:
$$B_3=\frac{x_l}{x_t},$$где $$x_l'$$ является числом вызовов, потерянных в единицу времени, и $$x_t $$ - общее количество попыток вызова в единицу времени. Используя нормализованные вероятности, из Таблицы 10.3 мы получаем:
$$\{\lambda_3(i)=(S_3-i)\lambda_3\}\\ x_l=\lambda_3(0)*\{p_3(0)*p_{12}(6)\}\\ \qquad +\lambda_3(1)*\{p_3(1)*p_{12}(5)\}\\ \qquad +\lambda_3(2)*\{p_3(2)*p_{12}(4)\}\\ \qquad +\lambda_3(3)*\{p_3(3)*p_{12}(3)\}\\ \qquad +\lambda_3(4)*p_3(4)*\{p_{12}(2)+p_{12}(1)+p_{12}(0)\},\\ x_l=0.2503.\\ x_t=\lambda_3(0)*p_3(0)*\sum_{j=0}^5p_{12}(j)\\ \qquad +\lambda_3(1)*p_3(1)*\sum_{j=0}^5p_{12}(j)\\ \qquad +\lambda_3(2)*p_3(2)*\sum_{j=0}^4 p_{12}(j)\\ \qquad +\lambda_3(3)*p_3(3)*\sum_{j=0}^3 p_{12}(j)\\ \qquad +\lambda_3(4)*p_3(4)*\sum_{j=0}^2p_{12}(j),\\ x_t=1.1763$$Тем же способом, обмениваясь результатом свертки нагрузки потока, находим критерии качества работы потока 1 и 2. Общее количество микросостояний в этом примере - 47. Методом свертки уменьшаем число состояния так, чтобы нам никогда не понадобилось более, чем два вектора по $$п +1$$ состоянию каждый, то есть 14 состояний.
Используя программу расчета -ATMOS, получаем следующие результаты, показанные в Таблице 10.4 и Таблице 10.5. Полные потери могут быть разбиты на потери из-за ограничения класса ( $$n_i$$ ) и потери из-за ограниченного числа каналов ( $$n$$ ).
| Вход | Общее число каналов $$n=6$$ | |||||||
|---|---|---|---|---|---|---|---|---|
| Предложенная нагрузка | Пиковость | Максимальное размещение | Размер слота | Среднее время пребывания в системе | Источники | Бета | ||
| $$i$$ | $$A_i$$ | $$Z_i$$ | $$n_i$$ | $$d_i$$ | $$\mu_i^{-1}$$ | $$S_i$$ | $$\beta_i$$ | |
| 1 | 2.0000 | 1.00 | 6 | 1 | 1.00 | $$\infty$$ | 0 | |
| 2 | 2.0000 | 0.75 | 6 | 2 | 1.00 | 4 | 0.3333 | |
| 3 | 1.0000 | 1.50 | 4 | 1 | 1.00 | -2 | -0.3333 | |
Потери по времени, потери по нагрузке, обслуженная нагрузка на выходе:
| Выход | Потери по вызовам | Потери по нагрузке | Потери по времени | Обслуженная нагрузка |
|---|---|---|---|---|
| $$i$$ | $$B_i$$ | $$C_i$$ | $$E_i$$ | $$Y_i$$ |
| 1 | 1.769 200E-01 | 1.769 200E-01 | 1.769 200E-01 | 1.646 160 |
| 2 | 3.346 853E-01 | 2.739 344E-01 | 3.836 316E-01 | 1.452 131 |
| 3 | 2.127 890E-01 | 2.884 898E-01 | 1.817 079E-01 | 0.711 510 |
| Итого | 2.380 397E-01 | 3.809 801 |
Чтобы проиллюстрировать программу расчета ATMOS, рассмотрим в Таблице 10.6 и Таблице 10.7 пример с 1536 пучками каналов и 24 потоками нагрузки. Заметим, что потери по времени независимы от пиковости $$Z_i$$ и пропорциональны размеру слота $$d_i$$, поэтому мы часто имеем:
| Вход | Общее число # $$n=1536$$ | ||||||
|---|---|---|---|---|---|---|---|
| Предложенная нагрузка | Пиковость | Допустимый максимум | Канал/вызов | Среднее время пребывания в системе | Источники | ||
| $$i$$ | $$A_i$$ | $$Z_i$$ | $$n_i$$ | $$d_i$$ | $$\mu_i$$ | $$S$$ | $$\beta$$ |
| 1 | 64.000 | 0.200 | 1536 | 1 | 1.000 | 80.000 | 4.000 |
| 2 | 64.000 | 0.500 | 15.36 | 1 | 1.000 | 128.000 | 1.000 |
| 3 | 64.000 | 1.000 | 1536 | 1 | 1.000 | $$\infty$$ | 0.000 |
| 4 | 64.000 | 2.000 | 1536 | 1 | 1.000 | -64.000 | -0.500 |
| 5 | 64.000 | 4.000 | 1536 | 1 | 1.000 | -21.333 | -0.750 |
| 6 | 64.000 | 8.000 | 1536 | 1 | 1.000 | -9.143 | -0.875 |
| 7 | 32.000 | 0.200 | 1536 | 2 | 1.000 | 40.000 | 4.000 |
| 8 | 32.000 | 0.500 | 1536 | 2 | 1.000 | 64.000 | 1.000 |
| 9 | 32.000 | 1.000 | 1536 | 2 | 1.000 | $$\infty$$ | 0.000 |
| 10 | 32.000 | 2.000 | 1536 | 2 | 1.000 | -32.000 | -0.500 |
| 11 | 32.000 | 4.000 | 1536 | 2 | 1.000 | -10.667 | -0.750 |
| 12 | 32.000 | 8.000 | 1536 | 2 | 1.000 | -4.571 | -0.875 |
| 13 | 16.000 | 0.200 | 1536 | 4 | 1.000 | 20.000 | 4.000 |
| 14 | 16.000 | 0.500 | 1536 | 4 | 1.000 | 32.000 | 1.000 |
| 15 | 16.000 | 1.000 | 1536 | 4 | 1.000 | $$\infty$$ | 0.000 |
| 16 | 16.000 | 2.000 | 1536 | 4 | 1.000 | -16.000 | -0.500 |
| 17 | 16.000 | 4.000 | 1536 | 4 | 1.000 | -5.333 | -0.750 |
| 18 | 16.000 | 8.000 | 1536 | 4 | 1.000 | -2.286 | -0.875 |
| 19 | 8.000 | 0.200 | 1536 | 8 | 1.000 | 10.000 | 4.000 |
| 20 | 8.000 | 0.500 | 1536 | 8 | 1.000 | 16.000 | 1.000 |
| 21 | 8.000 | 1.000 | 1536 | 8 | 1.000 | $$\infty$$ | 0.000 |
| 22 | 8.000 | 2.000 | 1536 | 8 | 1.000 | -8.000 | -0.500 |
| 23 | 8.000 | 4.000 | 1536 | 8 | 1.000 | -2.667 | -0.750 |
| 24 | 8.000 | 8.000 | 1536 | 8 | 1.000 | -1.143 | -0.875 |
Очевидно, что потери по времени зависят только от глобальных вероятностей состояния. Потери по вызовам почти равны потерям по времени. Они мало зависят от размера слота. Можно также ожидать, что потери по вызовам равны потерям по времени с одним удаленным источником ( теорема прибытия ). В таблице с выходными данными в самом правом столбце приведены относительные потери по нагрузке, разделенные на ( $$d_i \times Z_i$$ ), с использованием для нагрузки Пуассона единственного слота ( $$d_i = Z_i = 1$$ ). Заметим, что потери по нагрузке пропорциональны $$d_i \times Z_i,$$ - это является обычным предположением при использовании метода эквивалентной случайной нагрузки ( ERT - Equivalent Random Traffic) (см. Лекция 9). Средняя величина предложенной нагрузки увеличивается линейно с размером слота, тогда как дисперсия увеличивается пропорционально квадрату размера слота. Пиковость (дисперсия/математическое ожидание) - отношение для мультислотового трафика, п
оэтому увеличивается линейно с размером слота. Мы, таким образом, отмечаем, что потери по нагрузке намного более существенны, чем потери по времени и потери по вызовам, для того, чтобы характеризовать рабочие характеристики системы. Если вычислять полную перегрузку по нагрузке, используя метод Фредерикса и Хэйварда (секция 9.3), то мы устанавливаем, что полные потери по нагрузке равняются 6.114 % (см. Пример 9.3.2 и таблицу 10.7). Точное значение - 5.950 %.
| Выход | Потери по вызовам | Потери по нагрузке | Потери по времени | Обслуженная нагрузка | Значение |
|---|---|---|---|---|---|
| $$i$$ | $$B_i$$ | $$C_i$$ | $$E_i$$ | $$Y_i$$ | $$C_i/(d_iZ_i)$$ |
| 1 | 6.187744E-0.3 | 1.243705E-03 | 6.227392E-03 | 63.920403 | 0.9986 |
| 2 | 6.202616E-03 | 3.110956E-03 | 6.227392E-03 | 63.800899 | 0.9991 |
| 3 | 6.227392E-03 | 6.227392E-03 | 6.227392E-03 | 63.601447 | 1.0000 |
| 4 | 6.276886E-03 | 1.247546E-02 | 6.227392E-03 | 63.201570 | 1.0017 |
| 5 | 6.375517E-03 | 2.502346E-02 | 6.227392E-03 | 62.398499 | 1.0046 |
| 6 | 6.570378E-03 | 5.025181E-02 | 6.227392E-03 | 60.783884 | 1.0087 |
| 7 | 1.230795E-02 | 2.486068E-03 | 1.246554E-02 | 63.840892 | 0.9980 |
| 8 | 1.236708E-02 | 6.222014E-03 | 1.246554E-02 | 63.601791 | 0.9991 |
| 9 | 1.246554E-02 | 1.246554E-02 | 1.246554E-02 | 63.202205 | 1.0009 |
| 10 | 1.266184E-02 | 2.500705E-02 | 1.246554E-02 | 62.399549 | 1.0039 |
| 11 | 1.305003E-02 | 5.023347E-02 | 1.246554E-02 | 60.785058 | 1.0083 |
| 12 | 1.379446E-02 | 1.006379E-01 | 1.246554E-02 | 57.559172 | 1.0100 |
| 13 | 2.434998E-02 | 4.966747E-03 | 2.497245E-02 | 63.682128 | 0.9970 |
| 14 | 2.458374E-02 | 1.244484E-02 | 2.497245E-02 | 63.203530 | 0.9992 |
| 15 | 2.497245E-02 | 2.497245E-02 | 2.497245E-02 | 62.401763 | 1.0025 |
| 16 | 2.574255E-02 | 5.019301E-02 | 2.497245E-02 | 60.787647 | 1.0075 |
| 17 | 2.722449E-02 | 1.006755E-01 | 2.497245E-02 | 57556771 | 1.0104 |
| 18 | 2.980277E-02 | 1.972682E-01 | 2.497245E-02 | 51.374835 | 0.9899 |
| 19 | 4.766901E-02 | 9.911790E-03 | 5.009699E-02 | 63.365645 | 0.9948 |
| 20 | 4.858283E-02 | 2.489618E-02 | 5.009699E-02 | 62.406645 | 0.9995 |
| 21 | 5.009699E-02 | 5.009699E-02 | 5.009699E-02 | 60.793792 | 1.0056 |
| 22 | 5.303142E-02 | 1.007214E-01 | 5.009699E-02 | 57.553828 | 1.0109 |
| 23 | 5.818489E-02 | 1.981513E-01 | 5.009699E-02 | 51.318316 | 0.9942 |
| 24 | 6.525455E-02 | 3.583491E-01 | 5.009699E-02 | 41.065660 | 0.8991 |
| Итого | 5.950135E-02 | 1444.605 |
Алгоритм свертки основан на соединении потоков нагрузки, где мы заканчиваем потоком нагрузки, который является сборкой всех потоков нагрузки, кроме того, которым мы интересуемся. Другой подход состоит в том, чтобы собрать пространство состояний в глобальную вероятность состояния.
В случае Пуассоновских потоков вызовов, обобщая (10.10), можно упростить алгоритм. Обозначим $$p_i (x) $$ вклад потока в глобальную вероятность состояния $$p(x) $$:
$$p(x)=\sum_{i=1}^Np_i(x).$$Тогда среднее число каналов, занятых потоком $$i$$, когда система находится в глобальном состоянии $$x$$, равно $$x \times p_i (x) $$. Пусть поток нагрузки i имеет размер слота $$d_i.$$ Из-за обратимости мы получим локальное равновесие для каждого типа нагрузки. Уравнение локального равновесия:
$$\frac{xp_i(x)}{d_i}\mu_i=\lambda_i*p(x-d_i), \qquad x=d_i, d_i+1, \dots, n.$$Левая сторона - поток поступления заявок типа $$i$$ из состояния $$[x] $$ к состоянию $$[x- d_i] $$. Правая сторона - поток убывающих заявок типа $$i$$ от глобального состояния $$[x -d_i ] $$ к состоянию $$[x] $$. Не имеет значения, является ли $$x$$ кратным числом целого числа $$d_i,$$ так как мы рассматриваем только средние значения. Из (10.32) мы получаем:
$$p_i(x)=\frac 1x d_iA_i*p(x-d_i).$$Полная вероятность состояния $$p(x) $$ получена суммированием по всем потокам нагрузки (10.31):
$$p(x)=\frac 1x \sum_{i=1}^N d_iA_ip(x-d_i), \qquad p(x)=0 \qquad for \qquad x < 0$$Вышеупомянутая модель может легко быть обобщена на BPP-нагрузку (Iversen, 2005 [44] ):
$$\frac{xp_i(x)}{d_i}*\mu_i=p(x-d_i)*S_i \gamma_i \qquad p_i(x-d_i)*\frac{x-d_i}{d_i}*\gamma_i.$$С правой стороны первый элемент предполагает, что все источники типа $$i$$ свободны в течение единицы времени.
Чтобы получить значение $$p(x) $$, делим правую и левую часть на
$$\frac{x \mu_i}{d_i}$$Таким образом, мы получаем:
$$p(x)=\begin{cases} 0 x <\\ p(0) x=0\\ \sum_{i=1}^Np_i(x) x=1,2,\dots, n \end{cases}$$где
$$p_i(x)=\frac{d_i}{x}*\frac{S_i \gamma_i}{\mu_i}*p(x-d_i)-\frac{x-d_i}{x}*\frac{\gamma_i}{\mu_i}*p_i(x-d_i)$$ $$p_i(x)=0 \qquad x < d_i.$$Вероятность состояния $$p(0) $$ получена из условия нормировки:
$$\sum_{j=0}^np(j)=\sum_{j=0}^n \sum_{i=1}^N p_i(j)=1$$Выше мы использовали параметры $$(S_i ;\beta_i) $$, чтобы характеризовать потоки нагрузки. Альтернативно можно также использовать $$(A_i , Z_i ) $$, связанные с $$(S_i , \beta_i) $$ ) формулами (8.20) {(8.23). Тогда (10.37) получается:
$$p_i(x)=\frac{d_i}{x}*\frac{A_i}{Z_i}*p(x-d_i)-\frac{x-d_i}{x}*\frac{1-Z_I}{Z_i}*p_i(x-d_I)$$Потери по времени. Для Пуассоновского процесса поступления вызовов мы имеем (10.34). Для практической оценки формулы будем использовать нормализацию на каждом шаге, как это показано в секции 7.4.1. Она заканчивается очень точным и эффективным алгоритмом. При этом способе требуется малое число операций, требуемых объемов и конфигураций памяти, так как мы должны хранить только $$d_i$$ предыдущих вероятностей состояний потока нагрузки $$i$$ и $$max \{d_i\}$$ предыдущих значений глобальных вероятностей состояния. Число операций линейно зависит от числа каналов.
Критерии качества работы
С помощью этого алгоритма мы способны получить критерии качества работы для каждого отдельного потока нагрузки.
Попытки вызова потока $$i$$ требуют $$d_i$$ свободных каналов и будут блокированы с вероятностью:
$$E_i=\sum_{x=n-d_i+1}^n p(i)$$Потери по нагрузке
Из вероятностей состояний $$p_i(x) $$ мы получаем полную обслуженную нагрузку потока $$i$$:
$$Y_i=\sum_{j=1}^N xp_i(x).$$Тогда потери по нагрузке потока $$i$$ получаются:
$$C_i=\frac{A_i*d_i-Y_i}{A_i*d_i}.$$Полная обслуженная нагрузка:
$$Y=\sum_{j=1}^NY_i,$$так что полные потери по нагрузке равны:
$$C=\frac{A-Y}{A},$$где $$A$$ - полная предложенная нагрузка, измеряемая в каналах:
$$A=\sum_{j=1}^N d_iA_i.$$Потери по вызовам
Они могут быть получены из потерь по нагрузке с использованием (8.47):
$$B_i=\frac{(1+\beta_i)C_i}{1+\beta_i C_i}.$$Полные потери по вызовам не могут быть получены по этой формуле, так как мы не имеем глобального значения $$\beta$$.
Имея значение отдельной обслуженной нагрузки и потерь по вызовам по каждому потоку, мы можем найти общее количество предлагаемых вызовов и принятых каждым потоком запросов и определить полные потери по вызовам.
Применим обобщенный алгоритм для Примера 10.3.2. Таблица 10.8 показывает ненормирование вероятности состояния, когда мы принимаем, что нулевое состояние равняется единице. Таблица 10.9 показывает нормированные вероятности состояния и обслуженную нагрузку для каждого
| Состояние | Пуассон | Энгсет | Всего |
|---|---|---|---|
| $$x$$ | $$q_1(x)$$ | $$q_2(x)$$ | $$q(x)$$ |
| 0 | 0 | 0 | 1 |
| 1 | $$\frac 21*2=2$$ | 0 | 2 |
| 2 | $$\frac 22*2=2$$ | $$\frac 22*\frac 43*1-0=\frac 43$$ | $$\frac{10}{3}$$ |
| 3 | $$\frac 23*\frac{10}{3}=\frac{20}{9}$$ | $$\frac 23*\frac 43*2-0=\frac{16}{9}$$ | 4 |
| 4 | $$\frac 24*4=2$$ | $$\frac 24*\frac 43*\frac{10}{3}-\frac 24 *\frac 13*\frac 43=2$$ | 4 |
| 5 | $$\frac 25*4=\frac 85$$ | $$\frac 25*\frac 43*4-\frac 35*\frac 13*\frac{16}{9}=\frac{16}{9}$$ | $$\frac{152}{45}$$ |
| 6 | $$\frac 25*\frac{152}{45}=\frac{152}{135}$$ | $$\frac26* \frac 43*4-\frac 46*\frac 13*2=\frac{180}{135}$$ | $$\frac{332}{135}$$ |
| Всего | $$\frac{2723}{135}$$ |
| Состояние | Пуассон | Энгсет | Всего | |||
|---|---|---|---|---|---|---|
| $$x$$ | $$p_1(x)$$ | $$x*p_1(x)$$ | $$p_2(x)$$ | $$x*p_2(x)$$ | $$p(x)$$ | $$y-x*p(x)$$ |
| 0 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0496 | 0.0000 |
| 1 | 0.0992 | 0.0992 | 0.0000 | 0.0000 | 0.0992 | 0.0992 |
| 2 | 0.0992 | 0.1983 | 0.0661 | 0.1322 | 0.1653 | 0.3305 |
| 3 | 0.1102 | 0.3305 | 0.0881 | 0.2644 | 0.1983 | 0.5949 |
| 4 | 0.0992 | 0.3966 | 0.0992 | 0.3966 | 0.1983 | 0.7932 |
| 5 | 0.0793 | 0.3966 | 0.0881 | 0.4407 | 0.1675 | 0.8373 |
| 6 | 0.0558 | 0.3349 | 0.0661 | 0.3966 | 0.1219 | 0.7315 |
| Всего | 1.7562 | 1.6306 | 1.0000 | 3.3867 |
потока в каждом состоянии. В компьютерной программе мы нормализовали бы вероятности состояния после каждой итерации (увеличивая число линий на единицу) и вычислили бы объединенную полную нагрузку для каждого потока. Это значение нагрузки должно быть, конечно, также быть нормализовано на каждом шаге. Поэтому мы должны хранить только предыдущие значения $$d_i$$ и обслуженную нагрузку каждого потока нагрузки.
Мы получаем следующие критерии качества работы, которые, естественно, совпадают с уже полученным результатом алгоритма свертки.
$$E_1=p(6)=0.1219\\ E_2=p(5)+p(6)=0.2894\\ C_1=\frac{2*1-1.7562}{2*1}=0.1219\\ C_2=\frac{1*2-1.6306}{1*2}=0.1847\\ B_1=\frac{(1+0)*0.1219}{1+0*0.1219}=0.1219\\ B_1=\frac{(1+1/3)*0.1847}{1+(1/3)*0.1847}=0.2320$$Алгоритм свертки для систем с потерями был сначала издан в (Iversen, 1987 [40]). Подобный подход к менее общей модели был издан в двух статьях Россом и Цангом (1990 [90]), (1990 [91]) независимо от первоначальной статьи 1987 г., даже притом, что она была известна авторам.
Обобщенный алгоритм в секции 10.5.2 новый, и включает алгоритм Делброука (Делброук, 1983 [22]), который более сложен для проведения оценок. По сравнению со всеми другими алгоритмами обобщенный алгоритм требует намного меньше памяти и операций. Нормализуя вероятности состояния в каждой итерации, мы получаем очень точный и простой алгоритм. В принципе, можно применить обобщенный алгоритм для нагрузки
Алгоритм свертки - более общий инструмент, чем обобщенный алгоритм, поскольку учитывает минимальное и максимальное распределение каналов для каждого потока нагрузки. Обобщенный алгоритм не сохраняет запись фактического числа запросов для каждого потока. Алгоритм свертывания, кроме того, учитывает зависимые от состояния произвольные процессы поступления вызовов.
является общей многомерной B-формулой Эрланга.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.