eng
Выпуск #3/2017
В.Зайцев
Оценка точности результатов моделирования систем массового обслуживания
Оценка точности результатов моделирования систем массового обслуживания
Просмотры: 2255
Задача статьи – оценить точность результатов моделирования различных систем массового обслуживания, полученных при помощи пакета имитационного моделирования AnyLogic.
DOI: 10.22184/2070-8963.2017.64.3.70.73
УДК 621.395.31
DOI: 10.22184/2070-8963.2017.64.3.70.73
УДК 621.395.31
Теги: anylogic software quantile queuing system simulation modeling имитационное моделирование квантиль пакет имитационного моделирования anylogic система массового обслуживания
Введение
В данной работе рассматривается возможность использования пакета имитационного моделирования AnyLogic для оценки параметров систем массового обслуживания (СМО) как первого этапа работы, посвященной исследованию потоков в узлах коммутации мультисервисных сетей. Возможность использования средств моделирования в значительной мере определяется точностью получаемых результатов, которая оценивается относительной ошибкой в расчете исследуемых характеристик.
Обслуживание пакетного трафика в современных сетях связи осуществляется с дисциплиной, предусматривающей возможность ожидания в очереди [1], когда следует рассматривать модели в виде СМО с ожиданием. Международный союз электросвязи (МСЭ) в своих рекомендациях обычно нормирует среднее значение времени задержки и квантиль соответствующего распределения tp. Чаще всего p = 0,95, но в ряде рекомендаций МСЭ используются и другие значения p. Точность оценки величины , как правило, не вызывает проблем. Более того, для широкого ряда моделей среднее значение времени задержки может быть получено аналитическими методами. Оценка квантиля представляет собой более сложную задачу. Для расчета квантиля выбран пакет AnyLogic [2], позволяющий моделировать широкий класс СМО.
Для оценки точности средств моделирования необходимо сравнить полученные данные с результатами аналитического расчета, дающими истинные значения квантиля. Для получения точных значений необходимо выбрать модели в виде СМО, позволяющие аналитически найти квантиль функции распределения для времени задержки заявок. Под заявкой в современных сетях связи понимается IP-пакет, который должен быть передан или обработан.
Выбор моделей
В качестве семейства моделей, позволяющих аналитически найти квантиль tp, уместно выбрать СМО вида G/M/1 [1]. Данная нотация, называемая классификацией Кендалла, означает следующее:
• на вход СМО с интенсивностью λ поступает поток заявок с произвольной функцией распределения времени длительности интервалов между заявками A(t);
• длительность облуживания заявок – случайная величина, распределенная по экспоненциальному закону с интенсивностью μ;
• обслуживание заявок (передача или обработка IP-пакетов) осуществляется одним устройством.
Для получения характеристик модели G/M/1 необходимо сначала найти величину υ, которая в области 0< υ <1 является единственным корнем уравнения
. (1)
Функция α(s) представляет собой преобразование Лапласа – Стилтьеса от распределения A(t). Для решения уравнения (1) вместо переменной s необходимо подставить выражение, приведенное в круглых скобках. После получения значения υ квантиль tp и его нормированное значение на основании соотношений, приведенных в [1], определяются следующим образом:
.
Нормированное значение квантиля не зависит от величин λ и μ, что заметно упрощает проведение дальнейших исследований выбранного класса моделей. Среди видов СМО, для которых проводилось моделирование, в данной статье представлены результаты, полученные для трех законов распределения A(t): экспоненциального (M), Эрланга второго порядка (E2), гиперэкспоненциального второго порядка (H2). Если распределение A(t) подчиняется экспоненциальному закону, то величина υ равна нагрузке СМО ρ, определяемой отношением λ к μ.
Выражение для нормированного значения квантиля свидетельствует, что оно не зависит от нагрузки ρ. Результаты моделирования показывают наличие этой зависимости, что характеризует уровень погрешности пакета AnyLogic. Исследование трех выбранных моделей заключается в оценке относительной ошибки δ как функции нагрузки ρ, то есть в построении функции δ(ρ).
Исследование модели M/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками (Kv) равен единице [3]. В других моделях, рассматриваемых ниже, величина коэффициента вариации меньше и больше единицы соответственно.
Функция δ(ρ), полученная в процессе моделирования, приведена на рис.1 для диапазона 0,1 ≤ ρ ≤ 0,9. Выбор такого диапазона изменения нагрузки обусловлен двумя соображениями. Во-первых, поведение модели с низким уровнем нагрузки (ρ < 0,1) не представляется интересным с практической точки зрения, так как нормируемые показатели качества обслуживания трафика будут соблюдены. Во-вторых, в условиях высокой нагрузки (ρ > 0,9) используются алгоритмы управления сетью и ограничения интенсивности потока заявок, выбор которых является самостоятельной задачей.
Поведение функции δ(ρ) позволяет сделать вывод, что применение пакета AnyLogic дает возможность оценить квантиль t0,95 с относительной ошибкой в диапазоне 0,1 ≤ ρ ≤ 0,9 не более 10%. Причем для ρ ≤ 0,8 относительная ошибка не превышает 3%. Подобный уровень точности обычно вполне приемлем для задач планирования сети [4].
Исследование модели E2/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками меньше единицы [3]; он равен 2–0,5. Функция δ(ρ), полученная в процессе моделирования, приведена на рис.2 для выбранного ранее диапазона изменений нагрузки СМО.
Сравнение кривых, изображенных на рис.1 и 2, позволяет сделать вывод о том, что они очень похожи. Относительная ошибка в оценке квантиля t0,95 находится для исследуемой СМО примерно в тех же пределах, что и для модели M/M/1.
Исследование модели H2/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками – больше единицы [3]. Были использованы два его значения. Одно из них было выбрано так, чтобы коэффициент вариации превышал единицу примерно на такую же величину, на которую коэффициент вариации для модели E2/M/1 – меньше единицы. В качестве второго значения была взята величина коэффициента вариации, равная 10. На рис.3 показано поведение двух функций δ(ρ) для исследуемой СМО.
Очевидно, что функция δ(ρ) похожа на кривые, приведенные на двух предыдущих графиках. Подобная картина наблюдается и для других моделей с экспоненциальным законом распределения времени обслуживания. Для ряда таких моделей соотношения, позволяющие рассчитать величину υ, приведены в [5]. Для сложных распределений A(t) величину υ приходится находить численно, путем решения уравнения, приведенного выше.
Анализ полученных результатов
Полученные оценки относительной ошибки в расчете квантиля t0,95 не учитывают дополнительную погрешность, обусловленную тем, что результаты моделирования представимы с доверительными интервалами, определяемыми для выбранного уровня значимости [6]. Можно также вычислить уровень значимости для выбранных значений доверительных интервалов. В любом случае дополнительная погрешность не должна быть соизмеримой с величинами полученных выше значений относительной ошибки δ(ρ).
Добиться этого условия можно за счет корректного выбора величины N, равной количеству генерируемых IP-пакетов, которыми с точки зрения теории массового обслуживания являются заявки. В справочнике [6] приведена методика оценки уровня значимости для квантиля. Использование этой методики позволяет сделать вывод, что при N ≥ 105 дополнительная погрешность при оценке квантиля t0,95 становится как минимум на порядок меньше величины δ(ρ).
Задача, которая была поставлена в данной статье, заключалась в оценке квантиля tp для диапазона нагрузки 0,1 ≤ ρ ≤ 0,9. Тем не менее, пакет AnyLogic позволяет получить оценки квантиля и при ρ > 0,9. Правда, такая возможность связана с заметным увеличением величины N. Рост количества генерируемых заявок составляет два порядка. Следует отметить, что при ρ > 0,9 поведение функции δ(ρ) весьма специфично – оно выражается в ее заметных колебаниях. Примерно до уровня нагрузки 0,97 относительная ошибка не превышает 20%, но при дальнейшем увеличении ρ функция δ(ρ) резко возрастает.
Заключение
Результаты исследования дают возможность сделать три основных вывода.
Во-первых, пакет AnyLogic позволяет с приемлемой точностью оценивать квантиль распределения времени задержки в диапазоне изменения нагрузки от 0,1 до 0,9. Данный диапазон изменения нагрузки интересен для решения практических задач планирования сетей связи.
Во-вторых, можно считать, что величина относительной ошибки в оценке квантиля распределения времени задержки не зависит от коэффициента вариации длительности интервалов между IP-пакетами, формирующими входящий поток заявок.
В-третьих, для минимизации относительной ошибки в оценке квантиля и других характеристик модели необходимо генерировать не менее 105 заявок. Для исследования диапазона изменений нагрузки свыше 0,9 численность генерируемых заявок следует увеличить на два порядка. При использовании современного персонального компьютера эта процедура не приводит к чрезмерному росту времени проведения моделирования.
ЛИТЕРАТУРА
1. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979. 600 с.
2. Карпов Ю. Имитационное моделирование систем. Введение в моделирование с AnyLogic. – СПб: БХВ-Петербург, 2005. 403 с.
3. Вадзинский Р.Н. Справочник по вероятностным распределениям. – СПб: Наука, 2001. 294 с.
4. Бесслер Р., Дойч А. Проектирование сетей связи. – М.: Радио и связь, 1988. 272 с.
5. Соколов А.Н., Соколов Н.А. Однолинейные системы массового обслуживания. Учебное пособие. – СПб: Теледом, 2010. 112 с.
6. Справочник по прикладной статистике. Т. 1 / Под ред. Э.Ллойд и У. Ледерман. – М.: Финансы и статистика, 1989. 510 с.
В данной работе рассматривается возможность использования пакета имитационного моделирования AnyLogic для оценки параметров систем массового обслуживания (СМО) как первого этапа работы, посвященной исследованию потоков в узлах коммутации мультисервисных сетей. Возможность использования средств моделирования в значительной мере определяется точностью получаемых результатов, которая оценивается относительной ошибкой в расчете исследуемых характеристик.
Обслуживание пакетного трафика в современных сетях связи осуществляется с дисциплиной, предусматривающей возможность ожидания в очереди [1], когда следует рассматривать модели в виде СМО с ожиданием. Международный союз электросвязи (МСЭ) в своих рекомендациях обычно нормирует среднее значение времени задержки и квантиль соответствующего распределения tp. Чаще всего p = 0,95, но в ряде рекомендаций МСЭ используются и другие значения p. Точность оценки величины , как правило, не вызывает проблем. Более того, для широкого ряда моделей среднее значение времени задержки может быть получено аналитическими методами. Оценка квантиля представляет собой более сложную задачу. Для расчета квантиля выбран пакет AnyLogic [2], позволяющий моделировать широкий класс СМО.
Для оценки точности средств моделирования необходимо сравнить полученные данные с результатами аналитического расчета, дающими истинные значения квантиля. Для получения точных значений необходимо выбрать модели в виде СМО, позволяющие аналитически найти квантиль функции распределения для времени задержки заявок. Под заявкой в современных сетях связи понимается IP-пакет, который должен быть передан или обработан.
Выбор моделей
В качестве семейства моделей, позволяющих аналитически найти квантиль tp, уместно выбрать СМО вида G/M/1 [1]. Данная нотация, называемая классификацией Кендалла, означает следующее:
• на вход СМО с интенсивностью λ поступает поток заявок с произвольной функцией распределения времени длительности интервалов между заявками A(t);
• длительность облуживания заявок – случайная величина, распределенная по экспоненциальному закону с интенсивностью μ;
• обслуживание заявок (передача или обработка IP-пакетов) осуществляется одним устройством.
Для получения характеристик модели G/M/1 необходимо сначала найти величину υ, которая в области 0< υ <1 является единственным корнем уравнения
. (1)
Функция α(s) представляет собой преобразование Лапласа – Стилтьеса от распределения A(t). Для решения уравнения (1) вместо переменной s необходимо подставить выражение, приведенное в круглых скобках. После получения значения υ квантиль tp и его нормированное значение на основании соотношений, приведенных в [1], определяются следующим образом:
.
Нормированное значение квантиля не зависит от величин λ и μ, что заметно упрощает проведение дальнейших исследований выбранного класса моделей. Среди видов СМО, для которых проводилось моделирование, в данной статье представлены результаты, полученные для трех законов распределения A(t): экспоненциального (M), Эрланга второго порядка (E2), гиперэкспоненциального второго порядка (H2). Если распределение A(t) подчиняется экспоненциальному закону, то величина υ равна нагрузке СМО ρ, определяемой отношением λ к μ.
Выражение для нормированного значения квантиля свидетельствует, что оно не зависит от нагрузки ρ. Результаты моделирования показывают наличие этой зависимости, что характеризует уровень погрешности пакета AnyLogic. Исследование трех выбранных моделей заключается в оценке относительной ошибки δ как функции нагрузки ρ, то есть в построении функции δ(ρ).
Исследование модели M/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками (Kv) равен единице [3]. В других моделях, рассматриваемых ниже, величина коэффициента вариации меньше и больше единицы соответственно.
Функция δ(ρ), полученная в процессе моделирования, приведена на рис.1 для диапазона 0,1 ≤ ρ ≤ 0,9. Выбор такого диапазона изменения нагрузки обусловлен двумя соображениями. Во-первых, поведение модели с низким уровнем нагрузки (ρ < 0,1) не представляется интересным с практической точки зрения, так как нормируемые показатели качества обслуживания трафика будут соблюдены. Во-вторых, в условиях высокой нагрузки (ρ > 0,9) используются алгоритмы управления сетью и ограничения интенсивности потока заявок, выбор которых является самостоятельной задачей.
Поведение функции δ(ρ) позволяет сделать вывод, что применение пакета AnyLogic дает возможность оценить квантиль t0,95 с относительной ошибкой в диапазоне 0,1 ≤ ρ ≤ 0,9 не более 10%. Причем для ρ ≤ 0,8 относительная ошибка не превышает 3%. Подобный уровень точности обычно вполне приемлем для задач планирования сети [4].
Исследование модели E2/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками меньше единицы [3]; он равен 2–0,5. Функция δ(ρ), полученная в процессе моделирования, приведена на рис.2 для выбранного ранее диапазона изменений нагрузки СМО.
Сравнение кривых, изображенных на рис.1 и 2, позволяет сделать вывод о том, что они очень похожи. Относительная ошибка в оценке квантиля t0,95 находится для исследуемой СМО примерно в тех же пределах, что и для модели M/M/1.
Исследование модели H2/M/1
Для этой модели коэффициент вариации длительности интервалов между заявками – больше единицы [3]. Были использованы два его значения. Одно из них было выбрано так, чтобы коэффициент вариации превышал единицу примерно на такую же величину, на которую коэффициент вариации для модели E2/M/1 – меньше единицы. В качестве второго значения была взята величина коэффициента вариации, равная 10. На рис.3 показано поведение двух функций δ(ρ) для исследуемой СМО.
Очевидно, что функция δ(ρ) похожа на кривые, приведенные на двух предыдущих графиках. Подобная картина наблюдается и для других моделей с экспоненциальным законом распределения времени обслуживания. Для ряда таких моделей соотношения, позволяющие рассчитать величину υ, приведены в [5]. Для сложных распределений A(t) величину υ приходится находить численно, путем решения уравнения, приведенного выше.
Анализ полученных результатов
Полученные оценки относительной ошибки в расчете квантиля t0,95 не учитывают дополнительную погрешность, обусловленную тем, что результаты моделирования представимы с доверительными интервалами, определяемыми для выбранного уровня значимости [6]. Можно также вычислить уровень значимости для выбранных значений доверительных интервалов. В любом случае дополнительная погрешность не должна быть соизмеримой с величинами полученных выше значений относительной ошибки δ(ρ).
Добиться этого условия можно за счет корректного выбора величины N, равной количеству генерируемых IP-пакетов, которыми с точки зрения теории массового обслуживания являются заявки. В справочнике [6] приведена методика оценки уровня значимости для квантиля. Использование этой методики позволяет сделать вывод, что при N ≥ 105 дополнительная погрешность при оценке квантиля t0,95 становится как минимум на порядок меньше величины δ(ρ).
Задача, которая была поставлена в данной статье, заключалась в оценке квантиля tp для диапазона нагрузки 0,1 ≤ ρ ≤ 0,9. Тем не менее, пакет AnyLogic позволяет получить оценки квантиля и при ρ > 0,9. Правда, такая возможность связана с заметным увеличением величины N. Рост количества генерируемых заявок составляет два порядка. Следует отметить, что при ρ > 0,9 поведение функции δ(ρ) весьма специфично – оно выражается в ее заметных колебаниях. Примерно до уровня нагрузки 0,97 относительная ошибка не превышает 20%, но при дальнейшем увеличении ρ функция δ(ρ) резко возрастает.
Заключение
Результаты исследования дают возможность сделать три основных вывода.
Во-первых, пакет AnyLogic позволяет с приемлемой точностью оценивать квантиль распределения времени задержки в диапазоне изменения нагрузки от 0,1 до 0,9. Данный диапазон изменения нагрузки интересен для решения практических задач планирования сетей связи.
Во-вторых, можно считать, что величина относительной ошибки в оценке квантиля распределения времени задержки не зависит от коэффициента вариации длительности интервалов между IP-пакетами, формирующими входящий поток заявок.
В-третьих, для минимизации относительной ошибки в оценке квантиля и других характеристик модели необходимо генерировать не менее 105 заявок. Для исследования диапазона изменений нагрузки свыше 0,9 численность генерируемых заявок следует увеличить на два порядка. При использовании современного персонального компьютера эта процедура не приводит к чрезмерному росту времени проведения моделирования.
ЛИТЕРАТУРА
1. Клейнрок Л. Вычислительные системы с очередями. – М.: Мир, 1979. 600 с.
2. Карпов Ю. Имитационное моделирование систем. Введение в моделирование с AnyLogic. – СПб: БХВ-Петербург, 2005. 403 с.
3. Вадзинский Р.Н. Справочник по вероятностным распределениям. – СПб: Наука, 2001. 294 с.
4. Бесслер Р., Дойч А. Проектирование сетей связи. – М.: Радио и связь, 1988. 272 с.
5. Соколов А.Н., Соколов Н.А. Однолинейные системы массового обслуживания. Учебное пособие. – СПб: Теледом, 2010. 112 с.
6. Справочник по прикладной статистике. Т. 1 / Под ред. Э.Ллойд и У. Ледерман. – М.: Финансы и статистика, 1989. 510 с.
Отзывы читателей
