The software package and its application to study the polling systems.pdf Системы поллинга представляют собой системы массового обслуживания с несколькими очередями (или несколькими потоками заявок) [1, 2]. Обслуживающий прибор по определенному правилу посещает очереди и обслуживает находящиеся в них заявки. Системы поллинга эффективно используются для оценки производительности, проектирования и оптимизации структуры телекоммуникационных систем и сетей, транспортных систем и систем управления дорожным движением, производственных систем и систем управления запасами [3]. Для исследования математических моделей систем поллинга применяют различные методы: метод производящих функций, метод средних, метод ветвящихся процессов и другие [4] для получения точных формул вычисления характеристик производительности систем, а также различные эвристические методы для систем поллинга специального вида [5-8] и имитационное моделирование в случаях, когда проведение точного анализа системы не представляется возможным либо когда необходимо оценить точность приближенных результатов исследования. Разработка пакета прикладных программ для расчета характеристик и имитационного моделирования систем поллинга на данный момент становится весьма актуальной задачей, поскольку в литературе удается найти лишь одну работу [9], описывающую пакет программ имитационного моделирования для систем поллинга с несколькими обслуживающими устройствами (серверами), но порядок обслуживания очередей рассматривается лишь циклический. Представляемый же в данной работе пакет программ предполагает наличие только одного сервера в моделях, но рассматривается широкий класс типов опроса очередей в системах поллинга: циклический, адаптивный циклический, случайный. Пакет создан с помощью OMNeT++ Discrete Event Simulator, а также OMNeT++ Simulation Manual Version 4.6. OMNeT++ (Objective Modular Network Testbed на C++) - это модульная, основанная на компонентах библиотека моделирования и C++, в основном для создания сетевых симуляторов. 1. Модуль аналитических расчетов Разработанный пакет программ делится на два крупных модуля (рис. 1): модуль имитационного моделирования и модуль аналитических расчетов характеристик производительности систем поллинга, реализующий формулы их расчета. Модуль аналитических расчетов характеристик систем поллинга реализован с помощью Matlab 2013 на основе точных результатов анализа [1, 3], полученных для следующих систем поллинга: - Система циклического опроса с шлюзовой дисциплиной. - Система циклического опроса с исчерпывающей дисциплиной. - Система циклического опроса с глобально-шлюзовой дисциплиной. - Система адаптивного циклического опроса с шлюзовой дисциплиной. - Система адаптивного циклического опроса с исчерпывающей дисциплиной. Рис. 1. Схема пакета прикладных программ Fig. 1. The scheme of the application package Данный модуль позволяет получить следующие характеристики: - Вероятность опроса каждой очереди при адаптивном опросе. - Вероятность того, что сервер пропускает k очередей после завершения обслуживания i-й очереди (переходит в (i + kj-ю очередь), к = 1, N . - Первые и вторые моменты длины каждой очереди в момент ее опроса сервером. - Вторые моменты длины каждой очереди в момент опроса сервера. - Среднее время цикла для каждой очереди. - Среднее время пребывания заявок в системе адаптивного динамического поллинга с исчерпывающей и шлюзовой дисциплиной. 2. Модуль имитационного моделирования Для имитационного моделирования, был использован OMNeT++ Discrete Event Simulator, а также OMNeT++ Simulation Manual Version 4.6. OMNeT++ (Objective Modular Network Testbed на C++) - это модульная, компонентно-ориентированная C++ библиотека и фреймворк для дискретно-событийного моделирования, используемая прежде всего для создания сетевых симуляторов. OMNeT++ представляет архитектуру компонентов для моделей. Компоненты (модули) запрограммированы на C++, а затем собраны в более крупные компоненты и модели с использованием языка высокого уровня (NED). OMNeT++ имеет обширную поддержку графического интерфейса, и благодаря его модульной архитектуре ядро моделирования (и модели) может быть легко внедрено во многие приложения. В пакете имитационного моделирования реализованы следующие модели систем поллинга: циклический опрос с шлюзовой, исчерпывающей, глобально-шлюзовой, пороговой, k- и Т-ограни-ченными дисциплинами, адаптивный циклический опрос с шлюзовой, исчерпывающей и глобальношлюзовой дисциплиной, упорядоченный адаптивный динамический опрос с шлюзовой и исчерпывающей дисциплиной, циклический опрос с резервированием с множественным доступом, система циклического поллинга с пороговой исчерпывающей дисциплиной и простоями севера, система пол-линга с приоритетом, система поллинга со случайным порядком опроса при шлюзовой дисциплине, система поллинга со случайным порядком опроса при исчерпывающей или шлюзовой дисциплине, а также система циклического поллинга со случайной дисциплиной обслуживания очередей. Подробную информацию об этих дисциплинах опроса и обслуживания очередей, а также описание основной модели системы поллинга можно найти в [1, 3]. Структура пакета имитационного моделирования. Программа состоит из трех основных типов файлов (рис. 2): - Входные файлы: здесь задаются параметры модели системы поллинга: количество очередей, тип (простейший, фазового типа или MAP) и параметры входных потоков, тип и параметры процесса обслуживания заявок в каждой очереди, параметры процессов переключения сервера между очередями (табл. 1). Подробную информацию о МАР-потоках, их обобщении ВМАР-потоках и распределении фазового типа можно найти в [10]. Входные данные Поток поступления Генератор интервалов времени Обслуживание После обслуживания Стационарный режим Выходные данные Рис. 2. Основная структура программы Fig. 2. The basic structure of the program Т а б л и ц а 1 Пример входных и выходных данных Вход Выход 1. *.numQueues = 2: определение количества очередей. 2. *.generator[0].interAmvaffime = exponential(1/30): интенсивность поступления заявок для первой очереди. 3. *.generator[1].interAmvaffime = MAP(“MAP.txt”): тип поступления заявок для второй очереди. 4. * .threshold_gated_queue[ *]. serviceT ime = PhaseType(“Ph.txt”): тип обслуживания заявок для всех очередей. 5. **.switehing_time = "0.001 0.002": интенсивность переключения между очередями 1. Delay time in Queues i: среднее время пребывание заявок в очереди i 2. InterVisit time in Queues i: среднее время между последующими посещениями в очереди i 3. Number of cycle in Queues i: общее количество циклов в этой очереди (посещений сервером этой очереди) 4. Cycle_time: среднее время цикла 5. Ave_delay: среднее время пребывания заявок в системе 6. Number_of_packet: количество пакетов данных, прошедших сквозь систему в течение всего времени моделирования 7. График флуктуации среднего времени ожидания - Файлы алгоритмов: эти файлы содержат информацию о типе опроса очередей и дисциплинах их обслуживания, генерируют поток входных данных и процесс обслуживания для каждой очереди, а также генерируют случайное время переключения сервера между очередями. Далее в этих файлах производится расчет требуемых характеристик системы. - Выходные файлы: эти файлы содержат результаты работы программы: среднее время ожидания в очереди системы, среднее время цикла, среднее время между посещениями очереди сервером, а также другие характеристики производительности (см. табл. 1). Механизм работы пакета программ. На рис. 3 показан механизм работы пакета программ. После определения входных данных и запуска программы для каждой очереди отдельно генерируется момент времени, в который поступит следующая заявка. Сервер по выбранному правилу опроса в момент завершения обслуживания очередной очереди принимает решение, какая следующая очередь подлежит обслуживанию, и начинает к ней переключаться. Заявка, получившая обслуживание, отправляется в Sink, далее по моменту завершения обслуживания происходит перерасчет текущего среднего времени пребывания в системе и проверяется условие остановки моделирования. Рис. 3. Механизм работы пакета программ Fig. 3. The mechanism of the software package Задача остановки моделирования. Проблема остановки программного моделирования, когда поведение системы достигает режима, близкого к стационарному, является важной задачей для экономии ресурсов процессора и памяти. Рассмотрим следующий метод, который описан в работе [11]. Пусть Wi , i > 1 - последовательность значений среднего времени пребывания заявок после каждого обслуживания, n W Aw W(n) = Z W, Bi = =-, AWi - W-1,i > 1, i=i n W(n) где Bi - относительная точность доверительного интервала. Пусть вероятность P(|W(n) - W| < AWj) = 1 -а, где W - неизвестное среднее время пребывания заявок в системе. Критерием остановки моделирования является выполнение неравенства Bi

Скачать электронную версию публикации