Group Gamma-Distribution and Neural Network in of the Latest Telecommunication Traffic Modeling

Full Text

Введение

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

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

В [1] показано, как групповой пуассоновский поток может использоваться в такого рода задачах. Его использование удобно, так как параметры потока, приближающие очередь, им создаваемую, к реальной очереди, могут быть найдены аналитическим путем. Однако, приближение может быть не слишком хорошим.

В данной работе мы предлагаем новый подход к решению такой задачи. В качестве модельного трафика предлагается использовать групповой поток, в котором интервал между прибытиями пачек заявок подчиняется принципу гамма-распределения. Экспоненциальное распределение интервала между прибытиями, при котором такой поток становится пуассоновским, является частным случаем гамма-распределения. Таким образом, модель группового гамма-потока оказывается шире по своим возможностям, чем групповой пуассоновский поток.

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

В данной работе мы предлагаем следующий подход к этой проблеме – обучить нейронную сеть оценивать параметры гамма-потока, создающего очередь, подавая ей на вход данные о зависимости средней очереди и дисперсии очереди от загрузки прибора (канала). После обучения на вход такой нейросети мы подадим данные об очереди, создаваемой реальным трафиком, и она оценит параметры гамма-потока, наиболее близкого к реальному.

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

Заметим, что применение нейросетей в задачах, относимых к теории очередей, пока не очень распространено. В [2] приведен обзор современного состояния при применении машинного обучения (в том числе нейросетей) для задач теории очередей, из которого видно, что до сего времени нейронные сети использовались только для оценки параметров самих систем массового обслуживания с известной структурой, когда им на вход подавался известный трафик. В данной же работе предлагается использование нейросетей для оценки параметров входного трафика в систему массового обслуживания, и такой вид использования представляется новым. В данной работе приведены результаты, демонстрирующие возможность применения такого подхода.

Модель группового гамма-потока. Постановка задачи

Рассматривается поток заявок, в котором заявки всегда приходят пачками по B штук, где B = const – параметр модели. Интервалы времени между прибытиями пачек заявок являются независимыми одинаково распределенными случайными величинами, подчиняющимися принципу гамма-распределения с плотностью:

$fx\left(x\right)=\left\{\begin{array}{cc}\frac{x{\text{}}^{k-1}{e}^{-x/\theta }}{{\theta }^{\kappa }\Gamma \left(k\right)},& x\ge 0;\\ \mathrm{0,}& x<0.\end{array}\right.$

где k и θ – параметры распределения. В такой параметризации θ – это параметр масштаба, и в нашем случае его можно приравнять к 1. Таким образом, поток заявок задается двумя параметрами – k и B.

Этот поток является входным для системы массового обслуживания (СМО) G/D/1. Постоянное время обслуживания заявки τ задается таким образом, чтобы коэффициент загрузки прибора ρ был бы равен заданному: $\tau =\rho {\rm M}\left(X\right)=\rho k$ (так как M(X) = θ).

Обозначим через $Q_t\left(\rho \right),t\ge 0$ очередь в данной СМО с коэффициентом загрузки прибора ρ в момент времени t, а через $\overline{Q\left(\rho \right)}$ и $DQ\left(\rho \right)$ – эмпирические математическое ожидание и дисперсию очереди, полученные по достаточно продолжительной реализации $Q_t\left(\rho \right)$.

Для каждого значения ${\left\{{\rho }_n\right\}}_{n=\mathrm{1,}\dots ,N}$ из некоторого набора, рассмотрим соответствующие множества ${\left\{\overline{Q\left({\rho }_n\right)}\right\}}_{n=1\dots ,N}$.

Задача состоит в том, чтобы оценить параметры k и B, при которых оба этих множества значений были бы близки к значениям ${\left\{\overline{Q*\left({\rho }_n\right)}\right\}}_{n=1\dots ,N}$ и ${\left\{DQ\ast \left({\rho }_n\right)\right\}}_{n=1\dots ,N}$ для очереди в данной СМО, полученной при подаче на вход достаточно длинной трассы реального трафика.

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

Описание используемой нейросети

Для демонстрации возможности такого подхода обучим достаточно простую нейросеть (рисунок 1), где приведено стандартное графическое представление нейросети, генерируемое библиотекой Keras языка Python, использовавшейся в данной работе. Для эксперимента возьмем 9 значений ρ, минимальное - 0,1, максимальное - 0,9, и, учитывая, что, таким образом, входных значений у нейронной сети получится 18 (9 математических ожиданий и 9 дисперсий), обозначим их как ${\left\{x_n\right\}}_{n=\mathrm{0,}\dots 17}$ согласно принятой в области нейросетей традиции нумерации с нуля. При этом

$\left\{\begin{array}{c}{x}_n=\frac{\overline{Q\left({\rho }_{n+1}\right)}-C_{n+1}}{S_{n+1}},n=\mathrm{0,}\dots \mathrm{,8};\\ x_n=\frac{DQ\left({\rho }_{n-8}\right)-C_{n+1}}{S_{n+1}},n=\mathrm{9,}\dots \mathrm{,17.}\end{array}\right.$,

где ${\left\{{\rho }_n\right\}}_{n=\mathrm{1,}\dots \mathrm{,9}}$, а ${\left\{{С}_n\right\}}_{n=\mathrm{1,}\dots \mathrm{,18}}$ и ${\left\{S_n\right\}}_{n=\mathrm{1,}\dots \mathrm{,18}}$ – центрирующие и нормирующие по соответствующему входу величины, вычисляемые по множеству обучающих примеров объемом M по следующим формулам:

$\left\{\begin{array}{c}{С}_n=\frac{1}{M}{\sum }_{i=o}^{M-1}{x}_{n-\mathrm{1,}i},n=\mathrm{1,}\dots 18;\\ x_n=\sqrt{\frac{1}{M}{\sum }_{i=o}^{M-1}{x}_{n-\mathrm{1,}i}^2-C_n^2},n=\mathrm{1,}\dots 18.\end{array}\right.$,

где $x_{n,i}$ – значение на входе n обучающего примера i. Такая нормировка производится для того, чтобы на всех входах данные лежали примерно в одинаковом диапазоне, что повышает качество работы нейросети.

После входа идут два полносвязанных слоя нейросети, в каждом из которых по 16 нейронов, у каждого на выходе функция активации ReLu, а далее – два выходных нейрона – один оценивает параметр k гамма-потока, а второй - размер пачки B. У выходных нейронов функция активации отсутствует. Это одна из типичных архитектур нейросети для решения задачи регрессии параметров входных данных.

В качестве функции потерь, минимизируемой при обучении нейросети, использовалось среднеквадратическое отклонение.

Для повышения точности важным является вопрос выбора значений ${\left\{{\rho }_n\right\}}_{n=1\dots \mathrm{,9}}$. Равномерный шаг по ρ от 0,1 до 0,9 не является оптимальным решением, так как входные данные приближаются с одинаковой относительной погрешностью, что при больших ρ, приводит к большой абсолютной погрешности приближения $\left\{\overline{Q\left({\rho }_n\right)}\right\}$ и $\left\{DQ\left({\rho }_n\right)\right\},n=\mathrm{1,}\dots N.$

 

Рисунок 1. Архитектура нейронной сети

 

Заметно большую точность дает разделение интервала [0, 1; 0, 9] на 8 интервалов так, чтобы для самой быстрорастущей зависимости $\overline{Q\left({\rho }_n\right)}$ из рассматриваемого семейства, для каждого интервала $\left[{\rho }_n,{\rho }_{n+1}\right)$ выполнялось условие:

$\left({\rho }_{n+1}-{\rho }_n\right)\left(\overline{Q\left({\rho }_{n+1}\right)}-\overline{Q\left({\rho }_n\right)}\right)=const{\forall }_{\text{n}}=\mathrm{1,}\dots \mathrm{,8}$.

Определить нужные величины ρ_n можно численно, приняв ρ₁=0,1, ρ₉=0,9, и подобрав сначала такое значение ρ₅, что $\left({\rho }_5-{\rho }_1\right)\left(\overline{Q\left({\rho }_5\right)}-\overline{Q\left({\rho }_1\right)}\right)=\left({\rho }_9-{\rho }_5\right)\left(\overline{Q({\rho }_9})-\overline{Q\left({\rho }_5\right)}\right)$, а потом аналогичным образом найти ρ₃, используя известные ρ₁ и ρ₅, ρ₇ и известные ρ₅ и ρ₉ и т. д.

Для обучающей и контрольной выборки методом имитационного моделирования было сгенерировано 3000 трасс гамма-потоков со случайными параметрами, длина каждой трассы 200000. 2500 трасс составляли обучающую выборку, 500 трасс ‒ контрольную. Для каждой трассы были посчитаны величины ${\left\{\overline{Q\left({\rho }_n\right)}\right\}}_{n=\mathrm{1,}\dots ,N}и{\left\{DQ\left({\rho }_n\right)\right\}}_{n=\mathrm{1,}\dots ,N}$, подаваемые на вход нейросети. Соответствующие каждой трассе параметры использовались для обучения с учителем и для тестового контроля.

 

Рисунок 2. Результаты для приближения гамма-потоков с использованием нейросети: а) Средняя очередь пакетов в потоке; б) Дисперсия очереди пакетов в потоке

 

Именно генерация методом имитационного моделирования всех примеров занимает более 99% времени проведения такого эксперимента.

Оценка с применением аналитических выражений для сравнения

Для того, чтобы сравнить качество полученных результатов, попробуем приблизить статистические характеристики очереди реального трафика с помощью групповых пуассоновских потоков, для которых мы можем использовать обобщение формул Поллачека-Хинчина, полученных в [3] для СМО G/D/1 интервальным методом. Приведем их здесь в упрощенном виде для постоянного размера пачки B.

$\overline{Q}\left(\rho \right)=\frac{\rho B}{2(1-\rho )}-\frac{\rho }{2}$. (1)

 

Рисунок 3. Результаты для приближения пуассоновским потоком: а) Средняя очередь пакетов в потоке; б) Дисперсия очереди пакетов в потоке

 

$\begin{array}{l}DQ\left(\rho \right)=\frac{\rho B-\rho (1-\rho )}{4{(1-\rho )}^2}(\rho B+{\rho }^2-3\rho +2)+\\ \frac{{\rho }^3+\rho B^2+3{\rho }^{2}B-3\rho B-3{\rho }^2+2\rho }{3(1-\rho )}\end{array}$, (2)

где $\rho =\lambda \tau B,\lambda$ – интенсивность потока, τ – постоянное время обслуживания одной заявки.

Имея значения ${\left\{\overline{Q*\left({\rho }_n\right)}\right\}}_{n=1\dots ,N}$ и ${\left\{DQ\ast \left({\rho }_n\right)\right\}}_{n=1\dots ,N}$ статистических характеристик очереди реального трафика  и , мы можем методом наименьших квадратов минимизировать по параметру B отклонение аналитических кривых (1), (2) от реальных значений при соответствующих нагрузках, и это даст нам приближение реального трафика групповым пуассоновским потоком в смысле порождаемой очереди. Заметим, что в описанных ниже экспериментах мы использовали метод наименьших взвешенных квадратов с весами, обратно пропорциональными значениям соответствующих ${\left\{\overline{Q*\left({\rho }_n\right)}\right\}}_{n=1\dots ,N}$ и ${\left\{DQ\ast \left({\rho }_n\right)\right\}}_{n=1\dots ,N}$, так как они сильно различаются по величине. То есть, по параметру B минимизировалась следующая величина:

$J=\sum _{n=1}^N\left(\frac{(\overline{Q*\left({\rho }_n\right)}-\overline{Q\left({\rho }_n\right){)}^2}}{\overline{Q*\left({\rho }_n\right)}}\right)+\frac{{(DQ*({\rho }_n)-DQ({\rho }_n\left)\right)}^2}{DQ*\left({\rho }_n\right)}$,

где $\overline{Q*\left({\rho }_n\right)}$ и $DQ*\left({\rho }_n\right)$ – константы, найденные в результате имитационного моделирования очереди реального трафика, а $\overline{Q\left({\rho }_n\right)}$ и $DQ\left({\rho }_n\right)$ вычисляются по формулам (1, 2).

Заключение

Эксперименты проводились на трассах видеотрафика стандарта H264 с различными значениями параметра кодирования (размером видеобуфера). Результаты, представленные на рисунках 2 и 3, с очевидностью демонстрируют большее приближение при использовании гамма-потоков, параметры которых оцениваются с помощью нейросети.

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

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

Alexander Yu. Privalov

Samara National Research University

Email: privalov.ayu@ssau.ru

Head of Applied Mathematics and Physics Department, Doctor of Technical Science, Professor

Russian Federation, Samara

Tatiana D. Maksimova

Povolzhskiy State University of Telecommunications and Informatics

Email: td.pavlova@psuti.ru

Assistant to the vice-rector for administrative and economic work

Russian Federation, Samara

References

Supplementary files