Batch arrival flow generation algorithms

Full Text

Введение

Недостаточная эффективность представления трафика мультисервисных сетей моделями «самоподобных» процессов привела к созданию класса моделей потоков, управляемых цепью Маркова. Этапы развития указанных моделей представлены в [1]. В нашей стране они были названы МС-потоками, а в США эволюционировали от «разносторонних (versatile) потоков», через «N-потоки (потоки Ньютса) [2] до марковских входных потоков (MАP – Markovian Arival Process) и их обобщений – групповых Марковских входных потоков (BMАP – Batch Markovian Arival Process) [3–5]. На ранних стадиях указанных моделей интервалы поступления стационарного пуассоновского потока чередовались с интервалами, имеющими показательное распределение, где этот поток отсутствовал. (IPP-потоки). Затем перешли к рассмотрению SPP-потоков, где чередовались между собою интервалы поступления нескольких стационарных пуассоновских потоков различной интенсивности. Особое место среди рассмотренных потоков занимают групповые пуассоновские потоки.

Групповые пуассоновские потоки

Под групповым пуассоновским потоком случайных событий будем понимать поток случайных событий, распределенных по закону пуассона с параметром $\lambda$. Каждое из событий заключается в поступлении группы заявок. Частным случаем такого потока является неординарный пуассоновский поток, когда событие заключается в одновременном поступплении нескольких заявок [6; 7; 8].

Нами показано [6], что дисперсию $D_m\left(\rho \right)$ числа заявок на интервалах $\tau$ для такого потока можно определить, как

$D_m\left(\rho \right)==\rho \overline{k}(1+{\nu }_k^2)$ ,

где $\overline{k}$ – среднее число заявок в «пачке», $\rho =\lambda \tau \overline{k}$ – общий коэффициент загрузки, а ${\nu }_k^2=\frac{D_k}{{\left(\overline{k}\right)}^2}$ – квадрат коэффициента вариации чисел заявок в пачках. Дисперсия $D_m\left(\rho \right)$ линейно зависит от коэффициента загрузки так же, как это бывает в обычном пуассоновском потоке, где $D_m\left(\rho \right)=\rho$.

Нами также была получена формула, для определения средних значений очередей в системах массового обслуживания (СМО) с коррелированными потокамми заявок [8–10]. Эта формула обобщает известную формулу Хинчина-Поллачека, которая пригодна лишь для Пуассоновских потоков. Для рассматриваемых потоков обобщенная формула определения среднего значения очереди $\overline{q\left(\rho \right)}$ имеет весьма простой вид:

$q\left(\stackrel{}{\overline{\rho }}\right)=\frac{\rho \overline{k}(1+{\nu }_k^2)}{2(1-\rho )}-\frac{\rho }{2}.$

И, в частном случае, для обычного пуассоновского потока, когда каждая пачка имеет по одной заявке, $\overline{k}=\mathrm{1,}{\nu }_k^2=0$, получим формулу Хинчина-Поллачека в ее обычном виде $\overline{k}=\text{k}$, ${\text{ν}}_{\text{k}}^2=0$.

Распределение заявок внутри пачек

Заявки могут поступать не одновременно, а быть распределены на некоторых временных интервалах, образуя пачки заявок.

Заявки внутри каждой пачки могут быть распределены произвольно, согласно принятому алгоритму. Рассмотрим следующие примеры распределения заявок на заданном постоянном интервале Т.

1. Заявки каждой пачки распределены равномерно (интервалы между соседними заявками внутри пачки одинаковы.
2. Интервалы между соседнии заявками внутри пачки независимы и распределены экспоненциально.
3. Интервалы между соседними заявками внутри пачки подчиняютя Гамма-распределению.

Нетрудно показать, что первые два вида распределения заявок являются частными случаеми третьего (в первом случае коэффициент вариации Гамма-распределения стремится к нулю, а во втором случае – к единице).

Обозначим через ${\lambda }_m$ – условную среднюю интенсивность потока заявок внутри пачки. Тогда, среднее число заявок $\overline{k}$ в пачке длительностью Т определится соотношением $\overline{k}={\lambda }_{m}T$. Будем поддерживать указанное среднее значение постоянным (увеличивая ${\lambda }_m$ при уменьшении интервала Т).

Рассмотрим второй случай, когда интервалы между соседнии заявками внутри пачки независиы и распределены экспоненциально. Распределение числа заявок на интервале Т при этом удовлетворяет закону Пуассона

$P_k\left(\overline{k}\right)=\frac{{\overline{k}}^k}{k!}{e}^{-\overline{k}}$.

При уменьшении значения Т, все заявки пачки поступают одновременно и рассматриваемый пачечный поток стремится к неординарному групповому потоку с пуассоновским распределением числа заявок в каждой пачке. При увеличении значения Т до значения $T=\frac{1}{\lambda }$, приходим к обычному пуассоновскому потоку, с параметром $\lambda \overline{k}$.

Подготовка данных

Для генерации групповых потоков случайных событий программным образом необходимо спроектировать блок подготовки данных, предлагаемый алгоритм которого представлен на рисунке 1.

 

Рисунок 1. Блок подготовки данных

 

Прежде всего, необходимо указать тип распределения интервалов генерируемого потока событий («экспоненциальный» или «Гамма»). Затем, следует указать тип распределения размеров пачки («постоянный», «экспоненциальный», «пуассоновский»), распределение интервалов между заявками внутри пачки («постоянный», «экспоненциальный», «пуассоновский»), а также указать параметры распределений ${\lambda }_1,{\eta }_1,m_1,p_1$. Необходимо задать требуемый объем выборки «targеtN», и инициализировать генераторы случайных чисел: «genUniform» – генератор равномерного распределения, «genExp» – генератор экспоненциального распределения или «genPoison» – генератор распределения Пуассона. Затем, следует установить начальные значения счетчика заявок «totalN = 0» и текущее время «T1 = 0». Определяется длина временного интервала, на котором распределены заявки в пачках.

Все указанные действия могут быть объединены в один блок, который назовем «Блок подготовки данных».

Генерация потоков

После блока подготовки, следующим этапом необходимо предусмотреть блок «алгоритмов генерации потоков заявок». Рассмотрим блок – схему предлагаемых алгоритмов генерации трех возможных типов распределения размеров пачек (рисунок 2), с учетом следующих условных обозначений: «Пост» – постоянный размер ( ) пачки заявок; «Эксп» – экспоненциальное распределение; «Пуасс» – пуассоновское распределение, со средним значением, равным . Выбирается один из указанных типов распределений. Затем, выбирается одно из возможных распределений интервалов между заявками в пачке:

 

Рисунок 2. Блок-схема алгоритмов генерации потоков заявок

 

• все заявки сосредоточены в одной начальной точке интервала;
• заявки в пачке распределены равномерно по интервалу;
• интервалы между соседними заявками независимы и имеют экспоненциальное распределение.

Для всех типов генерации устанавливается размер цикла, равный М и выполняется указанный цикл генерации.

В первом случае, когда все заявки пачки сосредоточены во времени в одной точке, при выводе происходит многократное повторение одного и того же значения .

Во втором случае, когда интервалы между соседними заявками постоянны, то заявки распределены равномерно,

$T^1=\frac{dt}{M}$,

а каждый очередной момент времени Т определяется по формуле $T:=T+T^1$.

При экспоненциальном распределении интервалов между соседними заявками вначале генерируются случайные значения Te[i], производится их суммирование, а затем, в новом цикле, производится масштабирование всех временных отрезков с масштабом s.

Все рассмотренные схемы объединяются в одну блок-схему конвертора потоков заявок, представленную на рисунке 3.

 

Рисунок 3. Блок-схема алгоритмов работы конвертора потоков заявок

 

Конвертор генерации потоков заявок

По рассмотренным выше алгоритмам был создан конвертор генерации групповых потоков заявок. Конвертор воспроизводит последовательности чисел, отражающих моменты времени появления каждой из заявок. Если поток не ординарный, и одновременно появляется несколько заявок, то число, отображающее указанный момент времени, повторяется столько раз, сколько заявок поступило в этот момент.

Программа позволяет генерировать два независимых потока заявок от процессов №1 и №2 и суммировать их (наложить один на другой).

Внешний процесс – порождение события

Процесс №1 может порождать события по Гамма или Экспоненциальному распределению с параметрами λ₁ и η.

Процесс №2 порождает только экспоненциальные интервалы с параметром λ₂.

У каждого потока задается вероятность наступления события – P₁ и P₂ (1 – событие всегда наступает, 0 – никогда не наступает).

Внутренний процесс – порождение пачки

Оба потока, при наступлении события генерируют сразу пачку заявок.

Размер пачки Потока №1 определяется по одному из трех вариантов:

• всегда фиксированный размер пачки (m₁);
• размер пачки определяется согласно распределению Пуассона со средним m₁;
• размер пачки определяется по экспоненциальному распределению со средним m₁ (округленно до целого).

Размер пачки Потока №2 определяется всегда по закону Пуассона со средним m₂.

Распределение пачки по интервалу

Интервалы между заявками внутри пачки генерируются в одном из нескольких режимов. Поток №1 может работать в четырех режимах:

1. Все заявки пачки в одной точке. Генерируется количество заявок m_i в очередной пачке из распределения емкости пачки (фиксировано, экспоненциально или по Пуассону) с параметром m₁. Все эти заявки записываются с одинаковым текущим временем. Пример для набора параметров {λ₁=50, m₁=10, P₁=1, ρ=0.1} и Пуассоновского распределения размеров пачек показан на рисунке 4 (здесь и далее приведены скриншоты из программного комплекса АМС [9]). На графике – число заявок на интервале обслуживания.

 

Рисунок 4. Пуассоновское распределение чисел заявок в пачках

 

2. Постоянные интервалы между заявками внутри пачки. Генерируется количество заявок m_i в очередной пачке из распределения емкости пачки (фиксировано, экспоненциально или по Пуассону) с параметром m₁. Задается интервал распределения – $dt= \frac{1}{{\lambda }_1{m}_1}$ (исходя из среднего m₁). По интервалу dt равномерно распределяются заявки текущей пачки. Пример для набора параметров {λ₁=50, m₁=10, P₁=1, ρ=0.05} показан на рисунке 5.

 

Рисунок 5. Одинаковые числа заявок в пачках

 

3. Экспоненциальные интервалы между заявками внутри пачки. Генерируется количество заявок m_i в очередной пачке из распределения емкости пачки (фиксировано, экспоненциально или по Пуассону) с параметром m₁. Задается интервал размазывания – $dt=\frac{1}{{\text{λ}}_1{m}_1}$ (исходя из среднего m₁). Интервал dt делится на m_i штук экспоненциальных микроинтервалов. В начале каждого микроинтервала вписывается заявка.

Пример для набора параметров {λ₁=50, m₁=10, P₁=1, ρ=0.1} и экспоненциального распределения размера пачек показан на рисунке 6.

 

Рисунок 6. Экспоненциальное распределение чисел заявок в пачках

 

 Размножение пачки. Дополнительно задается:

• количество микропечек на одно событие – K (столько раз будет повторена микропачка);
• коэффициент заполнения интервала R, который может принимать значения от 0 до 1 (при R=0 – все микропачки в одной точке; при R=1 – микропачки распределены по всему интервалу до следующего события).

Между двумя соседними событиями основного потока t_i и t_i-1 определяется интервал распределения, пропорционально коэффициенту заполнения:

$dt=\left(t_i-t_{i-1}\right)*R$.

На этом интервале dt отмечаются K экспоненциальных микроинтервалов. При прохождении всех экспоненциальных микроинтервалов, для каждого из них генерируется количество заявок m_i в очередной пачке по распределению емкости пачки (фиксировано, экспоненциально или по Пуассону) с параметром m₁. В каждой микропачке эти m_i заявок размещаются в начало своего микроинтервала.

Пример для набора параметров {λ₁=50, m₁=10, P1=1, K=10, R=0,1, ρ=0,1} в режиме размножения пачек показан на рисунке 7.

 

Рисунок 7. Режим размножения пачек

 

Поток №2 работает аналогично, но только в первых трех режимах и только с Пауссоновскими интервалами.

Оба потока могут суммироваться (накладываются друг на друга), образуя общий единый поток и сохраняются в файл.

В потоках, изображенных на рисунках
4–7 использованы одинаковые параметры потока, при различных значениях коэффициента загрузки ρ.

На рисунке 8 показан экран взаимодействия системы с пользователем. На экране расположены окна управления процессами. «Вид распределения интервалов процесса 1» позволяет установить экспоненциальное или Гамма-распределения интервалов между групповыми событиями. Окно «Вид распределения емкости пачки» позволяет установить равномерное, экспоненциальное или пуассоновское распределение числа заявок в пачках. Окно «Вероятность пачки» позволяет установить вероятность возникновения пачки в момент наступления очередного группового события, а окно «Лямбда1» служит для установки значения интенсивности возникновения групповых событий. Окно «размножение пачки К раз» предназначено для установления числа повторений пачки между двумя соседними групповыми событиями. Окно «Коэффициент заполнения интервалов» устанавливает эквивалентный коэффициент загрузки (соответствующее значение интервала времени обработки одной заявки). Средний размер пачки и количество заявок также могут быть установлены в соответствующих окнах.

 

Рисунок 8. Экран взаимодействия с пользователем

 

Вид интервалов между заявками в пачках устанавливается отметкой в одном из окон.

Всего может быть три вида установки:

• все заявки в одной точке;
• постоянные интервалы;
• экспоненциальное распределение.

Параметры второго потока устанавливаются аналогично.

Заключение

Аналитическая теория, справедливая для пуассоновских потоков, для пачечных потоков становится непригодной. Анализ СМО таких потоков все чаще производится средствами имитационного моделирования. Алгоритмический анализ предшествует созданию программных продуктов и обеспечивает программную реализацию имитационных моделей. Модели групповых пуассоновских потоков представляют особый интерес при анализе пачечного трафика телекоммуникационных сетей. Конвертор групповых пуассоновских потоков позволяет получить потоки заявок, аналогичные по своим характеристикам потокам пачечного трафика телекоммуникационных сетей.

About the authors

Boris Ya. Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Author for correspondence.
Email: lixt@psuti.ru

Professor of Networks and Communication Systems Department, Doctor of Technical Science, Professor

Russian Federation, Samara

Victor I. Moiseev

Perm State University

Email: vim@psu.ru

Associate Professor at Radioelectronics and Information Security Department, PhD in Technical Sciences

Russian Federation, Perm

References

Supplementary files