ANALYSIS OF GENERAL QUEUING SYSTEM BY SELECTION FUNCTIONS

Full Text

Введение Анализ характеристик сетевых узлов при обработке трафика, обладающего распределениями с тяжелыми хвостами [1- 2; 7;, 9] для интервалов времени между поступлениями пакетов и интервалов времени обработки пакетов, связан с решением интегрального уравнения Линдли [3] для систем массового обслуживания типа G/G/1. При этом для упрощения вычислительной процедуры решения уравнения Линдли спектральным методом часто прибегают к аппроксимации плотностей вероятностей гиперэкспоненциальными распределениями, моделируемыми суммами затухающих экспонент [5; 7-8; 10]. Предложенный в [5] метод аппроксимации распределения суммой затухающих экспонент даёт неудовлетворительные результаты по точности аппроксимации на «восходящих» ветвях распределений. Кроме того, аппроксимация «восходящих» ветвей распределений приводит к появлению в сумме затухающих экспонент слагаемых с отрицательными коэффициентами, что нивелирует вычислительные преимущества спектрального метода, обусловленные использованием гиперэкспоненциальных распределений. Аппроксимация распределения Вейбулла Для иллюстрации данного утверждения рассмотрим задачу аппроксимации распределения Вейбулла, принадлежащего к классу распределений с тяжелыми хвостами, методом, изложенным в [5]. Например, для распределения Вейбулла (1) с параметрами и , представленного на рис. 1 пунктиром, аппроксимирующая сумма будет иметь вид (2) при некоторых значениях коэффициентов , отличающихся друг от друга на несколько порядков [5]. Результат аппроксимации представлен на рис. 1 сплошной линией. Рис. 1. Аппроксимация распределения Вейбулла: и Как следует из рис. 1, аппроксимация «восходящей» ветви распределения осуществляется с недопустимо большой ошибкой. Заметим, что для распределений, в которых отсутствует «восходящая» ветвь, например, распределение Парето [4], данная проблема не возникает и число слагаемых в аппроксимирующей сумме (2), как правило, может быть выбрано существенно меньше 10 при сохранении достаточной точности аппроксимации. Метод селектирующих функций Повысить точность аппроксимации в рассмотренном примере можно с использованием селектирующих функций [6], суть применения которых состоит в том, что аппроксимация разных участков распределения осуществляется разными методами, а результаты объединяются для адекватного представления аппроксимации распределения в целом (суть данного метода была представлена в докладе на конференции Problems of Infocommunications Science and Technology (PIC S&T), 2016. Third International Scientific-Practical Conference). Для рассмотренного распределения Вейбулла выделим два интервала аппроксимации - и , где может быть выбрано, например, как . Теперь представим в виде «сшитой» функции через кусочно-нелинейные и (3) и используем соответственно аппроксимации , (4) . (5) В (4)-(5) коэффициенты аппроксимации определяются соответствующими вычислительными процедурами. Для «сшитой» функции должно выполняться условие нормировки . Основным инструментом «сшивания» является селектирующая функция , определяемая как (6) с учетом сопряжения в точках «сшивания» в виде: . Очевидно, что выражение (3) теперь может быть представлено в виде , (7) а требуемое для решения уравнения Линдли спектральным методом преобразование Лапласа запишется как (8) где . Если ввести в рассмотрение функции (9) то можно показать [5-6], что при произвольной интегрируемой функции для интеграла справедливо соотношение (10) Используя (10) и (8), получаем (11) Вычисляя все интегралы в (11) на основе известных соотношений , , , , , , для преобразования Лапласа получим (12) Используем (12) в задаче анализа системы массового обслуживания G/G/1 путем решения интегрального уравнения Линдли спектральным методом [3]. Суть метода заключается в представлении выражения в виде , где и - преобразование Лапласа плотностей вероятностей промежутков времени между поступлениями заявок на обслуживание в систему и времени обслуживания заявок в системе, соответственно. При этом функции и должны удовлетворять условиям: - - аналитическая функция без нулей в области ; - - аналитическая функция без нулей в области для некоторого ; - для ; - для . Если функция найдена, то характеристическая функция времени ожидания заявки в очереди может быть определена в виде , (13) время ожидание в очереди . Аппроксимация распределений для анализа системы G/G/1 Рассмотрим применение рассмотренного метода аппроксимации распределений для анализа системы G/G/1. Пусть плотность вероятностей времени обслуживания заявок в системе определяется распределением Вейбулла с параметрами и . Методом селектирующих функций заменим на , а для плотности вероятностей интервалов времени между поступлениями заявок выберем распределение Парето , с параметрами и . Пусть плотность на интервале аппроксимируется полиномом третьей степени согласно (4) при и суммой затухающих экспонент согласно процедуре [5] на интервале с параметрами и . Результат данной аппроксимации представлен на рис. 2. Абсолютная погрешность аппроксимации при этом есть . Рис. 2. Аппроксимация распределения Вейбулла: и Плотность при и аппроксимируем суммой затухающих экспонент в виде с параметрами; . Результат аппроксимации представлен на рис. 3. Погрешность аппроксимации . Рис.3. Аппроксимация распределения Парето: и Преобразование Лапласа для будет иметь вид , и соответственно . Осуществив простые, но достаточно объемные преобразования, для выражения при выбранных значениях параметров аппроксимации распределений, можно получить (14) где , и - коэффициенты, зависящие от параметров используемых распределений, причем эти коэффициенты зависят также от величины , что делает характеристическое уравнение выражения в квадратных скобках нелинейным и, соответственно, усложняет нахождение его корней. Например, численное значение коэффициента определяется как . Аналогично выглядят и остальные коэффициенты . Наличие множителя в каждом коэффициенте является следствием использования полиномиальной аппроксимации «восходящего» участка распределения Вейбулла. Так как структура всех коэффициентов одинакова, используя разложение экспоненты в ряд в виде нетрудно свести нелинейное уравнение (13) к линейному виду, решая которое численно, можно получить представление в виде . Такая возможность сохраняется всегда при использовании полиномиальной аппроксимации «восходящего» участка любого распределения. В рассматриваемой задаче в силу равенства нулю коэффициента нелинейное уравнение 10 порядка, при использовании трех членов разложения экспоненты в ряд, можно свести к линейному уравнению 9 порядка. При выбранных значениях параметров используемых распределений данное уравнение имеет вид Обозначая корни характеристического уравнения через , для можно записать (15) Выделяя в (15) по вышеизложенным условиям функции и и формируя согласно (13), получаем значение среднего времени ожидания заявки в очереди с (размерность определяется размерностью величин и ). Точность полученного решения определяется точностью аппроксимации распределений при решении уравнения Линдли спектральным методом. Метод селектирующих функций позволил заменить распределение Вейбулла «сшитым» распределением , состоящим из двух участков: «восходящий участок (с положительным значением производной), который допускает простую аппроксимацию в виде полинома невысокой степени, и «нисходящий» участок (с отрицательным значением производной), аппроксимация которого осуществляется суммой затухающих экспонент с малым числом слагаемых в сумме. Такая аппроксимация обладает, как показано в работе, существенно меньшей погрешность по сравнению со случаем, когда используется единая аппроксимация распределения суммой затухающих экспонент. Полученное «сшитое» распределение позволяет легко получить его преобразование Лапласа, что в конечном итоге сводит решение задачи к определению корней линейного алгебраического уравнения численным методом.

About the authors

Marina Anatolievna Buranova

Povolzhskiy State University of Telecommunications and Informatics

Email: buranova-ma@psuti.ru

Vyacheslav Grigorievich Kartashevskiy

Povolzhskiy State University of Telecommunications and Informatics

Email: kartash@psati.ru

Natalia Valerievna Kireeva

Povolzhskiy State University of Telecommunications and Informatics

Email: zeppelinSN@yandex.ru

Liliia Ravilevna Chupakhina

Povolzhskiy State University of Telecommunications and Informatics

Email: garip4ik555@mail.ru

References

Supplementary files