Исследование систем стохастического поллинга и их применение для проектирования широкополосных беспроводных компьютерных сетей тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат наук Буй Зуи Тан

• Буй Зуи Тан
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Буй Зуи Тан

Введение

Глава 1. Состояние и тенденция исследования систем поллинга

1.1 Протокол централизованного управления доступа к среде абонентских станций IEEE 802.11 PCF

1.2 Основная модель поллинга и её применение для оценки производительности широкополосных беспроводных компьютерных сетей

1.3 Обзор работ по системам поллинга

1.4 Постановка задачи исследования систем стохастического поллинга

1.5 Основные результаты и выводы

Глава 2. Методы исследования систем адаптивного

динамического поллинга

2.1 Обзор существующих методов исследования систем стохастического поллинга

2.2 Математическая модель системы адаптивного динамического поллинга с шлюзовой дисциплиной

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

2.4 Метод имитационного моделирования для исследования характеристик производительности систем адаптивного динамического поллинга с коррелированным входящим потоком

2.5 Основные результаты и выводы

Глава 3. Пакет прикладных программ для исследования

систем стохастического поллинга

3.1 Архитектура и основные компоненты пакета прикладных

программ оценки характеристик систем стохастического поллинга

Стр.

3.2 Модуль программы аналитического расчета характеристик

систем поллинга

3.3 Модуль имитационного моделирования пакета прикладных программ

3.4 Программы исследования характеристик систем стохастического поллинга с коррелированным входным потоком типа MAP и некоторыми распределениями времени обслуживания

3.5 Основные результаты и выводы

Глава 4. Оценка эффективности использования механизма

адаптивного динамического поллинга

4.1 Численный расчет характеристик адаптивной динамической системы поллинга с шлюзовой и исчерпывающей дисциплиной с использованием пакета прикладных программ исследования

систем поллинга

4.2 Анализ характеристик производительности при различных порядках опроса очередей и дисциплинах их обслуживания

4.3 Чувствительность характеристик стохастических систем с динамическим адаптивным опросом к типу функции распределения времени обслуживания и коэффициента корреляции входных потоков

4.4 Оценка эффективности использования адаптивного динамического поллинга в беспроводных компьютерных сетях

IEEE 802.11 PCF

4.5 Основные результаты и выводы

Заключение

Список сокращений и условных обозначений

Список литературы

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Исследование систем стохастического поллинга и их применение для проектирования широкополосных беспроводных компьютерных сетей»

Введение

Актуальность темы исследования. Современные и перспективные протоколы широкополосных беспроводных компьютерных сетей предусматривают методы и алгоритмы по решению «проблемы скрытых станций». Указанная проблема возникает, когда абонентская станция (скрытая станция) по причине удаленности от базовой станции или наличия интерференции при прослушивании беспроводной среды не «видит» передачу/прием информации других станций сети, что приводит к возникновению коллизий и соответствующей потере производительности. Одним из эффективных алгоритмов борьбы с этим явлением является введение механизма поллинга циклического опроса базовой станцией очередей пакетов абонентских станций. Примером реализации таких алгоритмов является протокол централизованного управления (координации) PCF Point Coordination Function и его развитие метод НССА Controlled Channel Ассенн в стандарте IEEE 802.11-2016 а также протоколы перспективных сетей миллиметрового диапазона радиоволн (MM Wave), интернета вещей (1оТ) и радиочастотной идентификации транспортных средств. Базовая станция играет важную роль, осуществляя централизованное управление доступом всех абонентских станций к среде передачи данных. Таким образом, все узлы беспрводной сети опрашиваются последовательно согласно порядку опроса или следуя определенному приоритету и получают право на обмен пакетов данных между узлами. Важно отметить, что такой механизм опроса позволяет избегать коллизий, организовать неконкурентный доступ к среде передачи данных и обеспечить приоритетный доступ. Однако разработка и производство сетевых устройств, поддерживающих централизованное управление, является достаточно дорогим и сложным. Но, несмотря на это, использование таких устройств позволяет эффективно задействовать самые ценные ресурсы широкополосной беспроводной компьютерной сети: частотный ресурс и ресурс пропускной способности. Централизованное управление правом доступа станций к среде передачи данных позволяет устранить проблему «скрытых станций», а также позволяет четко планировать порядок доступа станций, гибко управлять всей работой радиосоты и менять ее параметры в зависимости от конкретных условий, настраивая только базовую станцию и не затрагивая оконечных. Широкое практическое применение сетей этого класса определяет

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

Степень разработанности темы. Исследованию протоколов централизованного управления на базе моделей стохастического поллинга посвящено значительное количество статьей отечественных ученых: Вишневский В.М., Гайдамака Ю.В., Моисеев А.Н., Рыков В.В., Семёнова О.В., Сонькин М.А., и др. а также зарубежных ученых: О.И. Боксма, С. Борет, У. Иехиали, X. Така-ги. В большинстве работ, в основном, были разработаны методы исследования систем циклического опроса, в частности, систем поллинга с исчерпывающей и шлюзовой дисциплиной. В данной работе рассматриваются слабоизучен-ные в мировой литературе системы стохастического адаптивного поллинга, которые адекватно описывают принципы работы широкополосных беспроводных компьютерных сетей с централизованным управлением. Такая система была впервые описана в статье: V.M.Vishnevsky, O.V.Semenova, A.N. Dudin, V.I.Klimenok. Approximate Method to Study M/G/l-Type Polling System with Adaptive Polling Mechanism. Quality Technology & Qnantitative Management (QTQM). 2012. Vol.9, № 2, pp.211-228., в которой предложен приближенный алгоритм расчета характеристик производительности систем поллинга с адаптивным опросом. В данном исследовании не только рассматривается задача анализа системы стохастического адаптивного поллинга для получения точных формул, но и имитационные модели других типов систем стохастического поллинга, которые до сих пор слабоизучены, например, системы циклического адаптивного поллинга типа МАР/РН/1 с шлюзовой и исчерпывающей дисциплиной и коррелированными входными потоками. Разработанный в диссертации пакет программ для расчета характеристик широкого класса моделей систем поллинга использован для проведения численного сравнительного анализа характеристик производительности беспроводных компьютерных сетей с централизованным механизмом управления.

Цели диссертационной работы. Целью диссертации является разработка и исследование новых методов повышения производительности широкополосных беспроводных компьютерных сетей с использованием моделей стохастического поллинга. Для реализации этой цели в рамках диссертации разработан комплекс новых моделей, методов и алгоритмов стохастических систем поллинга с динамическим адаптивным механизмом опроса очередей, включая:

— Анализ современного состояния исследований в области систем стохастического поллинга и их применения при проектировании широкополосных беспроводных компьютерных сетей.

— Разработка методов исследования стационарных характеристик систем адаптивного поллинга с использованием аппарата вложенных марковских процессов, производящих функций и преобразований Ла-пласа-Стилтьеса.

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

— Разработка и исследование моделей стохастических систем динамического поллинга с коррелированными входными потоками и алгоритмов расчета их основных характеристик.

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

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

— Разработка архитектуры пакета прикладных программ оценки характеристик производительности широкополосных беспроводных компьютерных сетей с централизованным механизмом управления.

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

— Проведение численного сравнительного анализа характеристик производительности беспроводных компьютерных сетей при различных

режимах оироеа абонентских станций с использованием разработанного пакета программ.

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

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

— методы исследования стационарных характеристик систем адаптивного поллинга с использованием аппарата вложенных марковских процессов и производящих функций;

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

— разработаны и исследованы модели стохастических систем динамического поллинга с коррелированными входными потоками и алгоритмы расчета их основных характеристик;

— проведен анализ чувствительности характеристик стохастических систем с динамическим адаптивным опросом к типу функции распределения времени обслуживания и коэффициента корреляции входных потоков;

— разработан комплекс программ имитационного моделирования, учитывающий особенности протоколов беспроводных компьютерных сетей с централизованным управлением. IEEE 802.11, Интернета Вещей (IEEE 802.15.4) и т.д.

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Математический метод исследования систем адаптивного поллиига с шлюзовой и исчерпывающей дисциплиной опроса абонентских станций.

2. Алгоритм исследования систем динамического адапитвного поллиига с входными коррелированными потоками.

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

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

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

Апробация работы. Основные результаты исследования по теме диссертации были доложены и обсуждены на следующих конференциях и совещаниях:

1. Международная конференция «Распределенные компьютерные и телекоммуникационные сети IEEE» (DCCN-2019, Москва).

2. Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (ИТТММ-2019, Москва, РУДН).

3. XIII Всероссийское совещание по проблемам управления (ВСПУ-2019, ИПУ РАН, Москва).

4. Международная конференция «Распределенные компьютерные и телекоммуникационные сети» (DCCN-2018, Москва).

5. 17th International Conference, ITMM 2018, Named After A.F. Terpugov, and 12th Workshop on Retrial Queues and Related Topics, WRQ 2018, Tomsk, Russia, 2018.

6. Всероссийская конференция с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (ИТТММ-2018, Москва, РУДН).

Результаты, полученные в диссертации, использованы при выполнении проекта Российского научного фонда № 16-49-02021 «Новый комплекс математических моделей, методов, алгоритмов и программ управляемых стохастических систем для оценки производительности и проектирования телекоммуникационных сетей следующего поколения» (2016-2018 г.).

Публикации. Основные результаты исследования по теме диссертации опубликованы в 11 печатных работах, 1 статьи из которых опубликованы в научных журналах, входящих в перечень ВАК, 3 статьи в научных изданиях, индексируемых системами Scopus и Web of Science, 1 свидетельство о государственной регистрации программ для ЭВМ, 6 тезисов докладов.

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и двух приложений. Полный объём диссертации составляет 115 страниц, включая 21 рисунок и 14 таблиц. Список литературы содержит 64 наименования.

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

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

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

В третьей главе «Пакет прикладных программ для исследования систем стохастического поллинга» проводится описание архитектуры пакета прикладных программ, состоящего из модуля расчета характеристик систем поллинга, полученных в диссертации и программно реализованных с использованием языка программирования МаЙаЬ, а также модуля имитационного моделирования, реализованного на базе пакете 01\ШеТ • • . Модуль имитационного моделирования включает модели систем, для которых не удается получить точные формулы расчета характеристик производительности, в том числе слабоизученных в настоящее время систем поллинга с коррелированными входными потоками.

В четвертой главе «Оценка эффективности использования механизма адаптивного динамического поллинга» проводится численный расчет характеристик систем стохастического поллинга с различными дис-

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

В заключении приводятся основные результаты диссертационного исследования.

Список сокращений и условных обозначений приведен на странице 104.

Глава 1. Состояние и тенденция исследования систем поллинга

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

Данная глава организована следующим образом. В разделе 1.1 приводится описание протокола централизованного управления доступа к среде абонентских станций, в разделе 1.2 рассматриваются основные модели систем поллинга и методы оценки широкополосных беспроводных компьютерных сетей и основные области применения систем опроса в разных областях, в том числе в широкополосных беспроводных компьютерных сетях связи, в разделе 1.3 приведен обзор работ по системам поллинга и в разделе 1.4 ставятся задачи исследования диссертации.

1.1 Протокол централизованного управления доступа к среде абонентских станций - IEEE 802.11 - PCF

Протокол централизованного управления PCF и его развитие метод НССА предполагает наличие точки доступа (сервера), определяющей какая станция в настоящее время имеет право передавать данные. По сути, это есть система циклического опроса с севером, который выполняет роль мастера опроса. Схема, представленная на рисунке 1.1, иллюстрирует реализацию режима централизованного опроса.

PIFS SIFS SIFS SIFS

Рисунок 1.1 Режим функции централизованной координации PCF

Точка доступа (АР - Access Point) пересылает кадры с данными (DATA), предназначенные станциями сети (если они есть), а также опрашивает все узлы сети о кадрах, которые стоят в их очередях на передачу, посылая им служебные кадры опроса CF-POLL (приглашение к передаче). Опрос станций сети точка доступа ведет согласно списку опроса, хранящемуся на ней. Способы формирования и поддержания списка опроса не регламентируются стандартом IEEE 802.11-2016 [30], поэтому разработчики устройств беспроводных компьютерных сетей имеют полную свободу в способах реализации этого списка. Если способ формирования и поддержания списка опроса циклический опрос, то осуществляются следующие шаги.

— Шаг 0: АР отправляет Beacon (сигнал широковещательного идентификатора сети) сразу после PIFS (PCF Interframe Space PCF межкадровый интервал). Это сообщение достигает каждой станции (устройства WLAN) без какого-либо риска коллизии. Beacon несет информацию о возможностях начала режима PCF.

— Шаг 1: После SIFS (Short Interframe Space короткий межкадровый интервал) АР начинает опрашивать первую станцию, посылая CF-POLL (кадр опроса) и передает данные (DATA) первой станции, если АР имеет данные для первой станции. После SIFS, первая станция передает свои данные и CF-ACK (кадр подтверждения) на АР (при пустой очереди станция отвечает так называемым нулевым кадром NULL, состоящим только из заголовка и CF-ACK).

— Шаг 2: После SIFS сервер начинает опрашивать вторую станцию, посылая CF-POLL • CF-ACK и передает данные второй станции если АР имеет данные для второй станции. После SIFS вторая станция передает свои данные (если они имеются) и CF-ACK на АР.

— Шаг 3: После SIFS сервер начинает опрашивать третью станцию, посылая CF-POLL • CF-ACK и передает данные третьей станции если АР имеет данные для третьей станции. После SIFS, если третья станция не отвечает, АР ожидает один интервал времени (один интервал времени это есть Slot time a PIFS — Slot time • SIFS) и начинает опрашивать следующую станцию. И так далее. После того, что АР получил данные и CF-ACK от последней станции, АР ожидает SIFS и передает всем кадр CF-END и сообщает что это конец PCF режима. Если способ формирования и поддержания списка опроса адаптивный динамический опрос то АР не опрашивает только те станции, которые были пусты в прошлом режиме.

Для уменьшения накладных расходов точка доступа может совмещать кадр опроса с передачей данных (кадр DATA CF-POLL). Аналогично станции сети могут совмещать кадры подтверждения с передачей данных DATA • CF-ACK. Допускаются следующие типы кадров во время режима PCF: DATA кадр данных, CF-ACK кадр подтверждения, CF-POLL кадр опроса, DATA • CF-ACK комбинированный кадр данных и подтверждения, DATA • CF-POLL комбинированный кадр данных и опроса, DATA • CF-ACK • CF-POLL комбинированный кадр данных, подтверждения и опроса, CF-ACK • CF-POLL комбинированный кадр подтверждения и опроса.

1.2 Основная модель поллинга и её применение для оценки производительности широкополосных беспроводных компьютерных

сетей

1.2.1 Классификация систем поллинга

В данном разделе, следуя [40; 42], опишем классификацию систем поллинга согласно следующим критериям: количество очередей, порядок опроса очередей и дисциплина обслуживания очереди.

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

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

Пусть система поллинга состоит из N очередей, которые занумерованы от 1 до Ж. Обозначим через О,,, г-ю очередь системы.

Порядок опроса очередей модет быть следующим:

— Циклическим, при котором сервер опрашивает очереди циклически в

порядке Я\,Я2,..., Ям, Я\,Я2,..., Ям,.. .■

— Периодическим. При таком порядке опроса вводится таблица опроса вида (Т (1 ),Т (2),...,Т Щ) размер а Ь(Ь ^ N ),Т (г) е {1,...^ },г = 1Х,

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

— Случайным. При таком порядке следующая очередь, которая будет обслуживаться сервером (допустим, выбирается согласно закону распределения^, г = 1,Ы. Также возможен марковский порядок опроса очередей, при котором после обслуживания г-й очереди с вероятностью рг,^ сервер переключается к очереди Я^ г,] = При этом

Ргз = 1,г = 1^.

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

— Адаптивны,м динамическим. Сервер циклически посещает очереди, а в следующем цикле он пропускает (не посещает) те из них, в которых

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

— Упорядоченным адаптивным, динамическим Очереди системы в цикле опрашиваются сервером в порядке убывания их рангов. Ранг очереди динамически присваивается в каждом цикле, а процедура присвоения рангов определяется следующим образом. В первом цикле все очереди получают ранг ri = 0 i = 1,N. Если i-я очередь пуста при опросе, то ее ранг уменьшается на 1, т.е. ri = —1. В противном случае ранг увеличивается на единицу, т.е. ri = 1. Очереди с одинаковыми рангами в цикле опрашиваются сервером в порядке возрастания их номеров.

—1

1

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

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

Список литературы диссертационного исследования кандидат наук Буй Зуи Тан, 2021 год

Список литературы

1. Adaptive cyclic polling ну stems: analysis and application to the broadband wireless networks / V. Vishnevsky [et al.] // Lecture Notes in Computer Science. Distributed Computer and Communication Networks. Vol. 11965 / ed. by V. M. Vishnevskiy, К. E. Samouylov, D. V. Kozyrev. - Springer, 2019. - P. 30 - 42.

2. Analysis of Queueing System with Non-Preemptive Time Limited Service and Impatient Customers / C. Kim [et al.] // Methodology and Computing in Applied Probability. - 2019.

3. Chen, W.-L. Computing the Moments of Polling Models with Batch Poisson Arrivals by Transform Inversion / W.-L. Chen // INFORMS Journal on Computing. - 2019. - Vol. 31, no. 3. - P. 411 632.

4. Granville, K. On a 2-class polling model with reneging and fc-limited service / K. Granville, S. Drekic // Annals of Operations Research. - 2019. - Vol. 274, no. 1. P. 267 - 290.

5. Kim, B. Analysis of the waiting time distribution for polling systems with retrials and glue periods / B. Kim, J. Kim // Annals of Operations Research. -2019. - June. - Vol. 277, no. 2. - P. 197 212.

6. Performance Analysis of a Polling Model with BMAP and Across-Queue State-Dependent Service Discipline / J. Cao [et al.] // IEEE Access. 2019. -P. 127230 - 127253.

7. Performance evaluation of the broadband wireless networks with centralized control by means of the stochastic polling systems / O. Semenova [et al.] // Distributed Computer and Communication Networks: Control, Computation, Communications (DCCN-2019). - Moscow: RUDN, 2019. - P. 67 - 74.

8. Performance of large-scale polling systems with branching-type and limited service / T. Meyfroyt [et al.] // Performance Evaluation. - 2019. - Vol. 133. -P. 1 - 24.

9. Программный комплекс оценки характеристик систем стохастического поллинга : 2019614554 / В. М. Вишневский, О. В. Семёнова, 3. Т. Буй ; Ф. государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук (ИПУ РАН) (RU). заявл. 04.2019.

10. Семёнова, О. В. Адаптивное управление порядком опроса очередей в системах поллинга и его применение в широкополосных беспроводных сетях / О. В. Семёнова, 3. Т. Буй // Труды 13-го Всероссийского совещания по проблемам управления (ВСПУ XIII, Москва, ИПУ РАН). М.: ИПУ РАН, 2019. с. 3007 ЗОИ.

11. Семёнова, О. В. Пакет прикладных программ оценки характеристик систем стохастического поллинга / О. В. Семёнова, 3. Т. Буй // Материалы Всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (Москва, 2019). М.: РУДН, 2019.

с. 108 112.

12. Borst, S. Polling: past, present, and perspective / S. Borst, O. Boxma // TOP. 2018. - Oct. - Vol. 26, no. 3. P. 335 - 369.

13. Jolles, A. Alternating server with non-zero switch-over times and opposite-queue threshold-based switching policy / A. Jolles, E. Perel, U. Yechiali // Performance Evaluation. - 2018. - July. - Vol. 126. - P. 22 - 38.

14. Lee, T. Y. Analysis of Single Buffer Random Polling System With State-Dependent Input Process and Server/Station Breakdowns / T. Y. Lee // International Journal of Operations Research and Information Systems. -2018. - Vol. 9, no. 1. P. 22 50.

15. Saffer, Z. Fluid Polling System with Markov Modulated Load and Gated Discipline / Z. Saffer, M. Telek, G. Horvath // QTNA 2018: Queueing Theory and Network Applications. 2018. - P. 86 - 102.

16. Semenova, О. V. Method of Generating Functions for Performance Characteristic Analysis of the Polling Systems with Adaptive Polling and Gated Service / О. V. Semenova, D. T. Bui // Information Technologies and Mathematical Modelling. Queueing Theory and Applications / ed. by A. Dudin, A. Nazarov, A. Moiseev. Cham : Springer International Publishing, 2018. P. 348 359.

17. Богачев, Д. Г. Имитационная модель среды информационного обмена, включающая математическую модель резервирования ресурсов пакетной сети передачи данных с множественным доступом / Д. Г. Богачев // Вестник Евразийской науки. 2018. № 1. с. 1 8.

18. Буй, 3. Т. Исследование систем поллинга с использованием имитационного моделирования / 3. Т. Буй, О. В. Семёнова // Труды МФТИ. 2018.

т. 10, № 2. с. 95 98.

19. Вишневский, В. М. Стохастические системы с коррелированными потоками. Теория и применение в телекоммуникационных сетях, т. 1 / В. М. Вишневский, А. И. Дудин, В. И. Клименок. Москва : Рекламно-издательский центр "ТЕХНОСФЕРА", 2018. 564 с.

20. Семёнова, О. В. Адаптивные дисциплины опроса в системах поллинга и их имитационное моделирование / О. В. Семёнова, 3. Т. Буй // Материалы всероссийской конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» (ИТТММ-2018, Москва, РУДН). М.: РУДН, 2018. с. 69 71.

21. Семёнова, О. В. Об одной системе поллинга для оценки характеристик адаптивного циклического порядка опроса / О. В. Семёнова, 3. Т. Буй // Материалы 21-й Международной научной конференции «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь» (DCCN-2018, Москва). М.: РУДН, 2018. с. 13 20.

22. Сао, J. Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines / J. Cao, W. Xie // Queueing Systems. - 2017. - Vol. 85, no. 1. P. 117-147.

23. Jiang, T. Analysis of a Batch Service Polling System in a Multi-phase Random Environment / T. Jiang, L. Liu, Y. Zhu // Methodology and Computing in Applied Probability. - 2017. P. 1 - 20.

24. Kim, B. Sojourn time distribution in polling systems with processor-sharing policy / B. Kim, J. Kim // Performance Evaluation. - 2017. - Sept. -Vol. 114. - P. 97-112.

25. Liu, Z. On the three-queue priority polling system with threshold service policy / Z. Liu, Y. Chu, J. Wu // Journal of Applied Mathematics and Computing. - 2017. - Feb. - Vol. 53, no. 1. - P. 445 - 470.

26. Perel, E. Two-queue polling systems with switching policy based on the queue that is not being served / E. Perel, U. Yechiali // Stochastic Models. - 2017. -Vol. 33, no. 3. - P. 430 450.

27. Вишневский, В. M. Системы массового обслуживания с коррелированными входными потоками и их применение для моделирования телекоммуникационных сетей / В. М. Вишневский, А. Н. Дудин // Автоматика и телемеханика. 2017. № 8.

28. Вишневский, В. М. Системы адаптивного динамического поллинга с коррелированными входными потоками: препринт / В. М. Вишневский, О. В. Семёнова. М. : ИПУ РАН, 2017. 88 с.

29. Объектная модель приложения для имитационного моделирования циклических систем массового обслуживания / М. А. Сонькин [и др.] // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2017. септ. с. 71 80.

30. IEEE std 802.11-2016 IEEE standard for information technology telecommunications and information exchange between systems local and metropolitan area networks-specific requirements. 2016.

31. The impact of scheduling policies on the waiting-time distributions in polling systems / R. Bekker [et al.] // Queueing Systems. 2015. - Feb. - Vol. 79. -P. 145 - 172.

32. Approximate Method to Study M/G/1-Туре Polling System with Adaptive Polling Mechanism / V. M. Vishnevsky [et al.] // Quality Technology & Quantitative Management. 2012. - Vol. 9, no. 2. - P. 211 - 228.

33. Czerniak, O. Analysis of a TCP system under polling-type reduction-signal procedures / O. Czerniak, E. Altman, U. Yechiali // Performance Evaluation. -2012. - Vol. 69, no. 3/4. - P. 150 - 163.

34. Vishnevsky, V. Polling systems: Theory and applications for broadband wireless networks / V. Vishnevsky, O. Semenova. - LAP LAMBERT Academic Publishing, 2012. - 317 p.

35. Co,so,le, G. Building accurate workload models using Markovian arrival processes / G. Casale //. Vol. 39. - 06/2011. - P. 357 358.

36. Mei, R. Polling models with multi-phase gated service / R. Mei, A. Roubos // Annals of Operations Research - Annals OR. - 2011. - Jan. - Vol. 198.

P. 1 - 32.

37. Mei R.D., van der. Heavy traffic analysis of polling models by mean value analysis / van der Mei R.D., W. E. // Performance Evaluation. - 2008. Vol. 65, no. 6/7. - P. 400 -416.

38. Mei, R. D. van der. Towards a unifying theory on branching-type polling systems in heavy traffic / R. D. van der Mei // Queueing Systems. - 2007. Sept. Vol. 57, no. 1. - P. 29 46.

39. Vuuren, M. van. Iterative approximation of fc-limited polling systems / M. van Vuuren, E. M. M. Winands // Queueing Systems. - 2007. Mar. -Vol. 55, no. 3. - P. 161 178.

40. Вишневский, В. M. Системы поллинга: теория и применение в широкополосных беспроводных сетях / В. М. Вишневский, О. В. Семёнова. М. : Техносфера, 2007. 312 с.

41. Winands, Е. М. М. Mean value analysis for polling systems / E. M. M. Winands, I. J. B. F. Adán, H. G. J. Van // Queueing Systems. -2006. - Vol. 54. - P. 35 44.

42. Вишневский, В. M. Математические методы исследования систем поллинга / В. М. Вишневский, О. В. Семёнова // Автоматика и телемеханика. 2006. вып. 2. с. 3 56.

43. Бочаров, П. П. Однолинейная система массового обслуживания конечной емкости с марковским потоком и обслуживанием в дискретном времени / П. П. Бочаров, Е. В. Вискова // Автоматика и телемеханика. 2005.

№ 2. с. 233 248.

44. Hirayama, Т. A New Approach to Analysis of Polling Systems / T. Hirayama, S. J. Hong, M. M. Krunz // Queueing Systems. 2004. Sept. - Vol. 48, no. 1. P. 135 - 158.

45. Kramer, G. Interleaved Polling with Adaptive Cycle Time (IPACT): A Dynamic Bandwidth Distribution Scheme in an Optical Access Network /

G. Kramer, B. Mukherjee, G. Pesavento // Photonic Network Communications. - 2002. - Apr. Vol. 4. - P. 89 - 107.

46. Supporting differentiated classes of service in Ethernet passive optical networks / G. Kramer [et al.] // Journal of Optical Networking. - 2002. -Aug. - Vol. 1. P. 280 - 290.

47. Mei, R. Web Server Performance Modeling / R. Mei, R. Hariharan, P. Reeser // Telecommunication Systems. - 2001. - Jan. Vol. 16. - P. 361 - 378.

48. Performance of Web servers in a distributed computing environment / R. Mei [et al] // Teletraffic Science and Engineering. 2001. - Dec. - Vol. 8.

P. 125 - 134.

49. Blanc, H. The Power-Series Algorithm for Polling Systems with Time Limits /

H. Blanc // Probability in the Engineering and Informational Sciences. 1998. - Apr. Vol. 12. - P. 221 237.

50. Borst, S. Polling systems / S. Borst. - Amsterdam: Stichting Mathematisch Centrum, 1996.

51. Srinivasan, M. M. The individual station technique for the analysis of cyclic polling systems / M. M. Srinivasan, H. Levy, A. G. Konheim // Naval Research Logistics (NRL). - 1996. Vol. 43, no. 1. P. 79 101.

52. Borst, S. C. Polling Systems with Multiple Coupled Servers / S. C. Borst // Queuing Syst. - 1995. - Vol. 20, no. 3/4. P. 369 - 394.

53. Yechiali U. Analysis and Control of Polling Systems / U. Yechiali // Performance Evaluation of Computer and Communication Systems / ed. by L. Donatiello, R. Nelson. Berlin : Springer, 1993. - P. 630 650.

54. Blanc, H. The power-series algorithm applied to cyclic polling systems / H. Blanc//Stochastic Models. - 1991. Jan. - Vol.7. - P. 527- 545.

55. Takagi H. Queueing analysis : a foundation of performance evaluation / Hideaki Takagi. Vol. 3 / H. Takagi. - North-Holland ; Distributors for the U.S., Canada, Elsevier Science Pub. Co Amsterdam, New York, 1991. - 546 p.

56. Levy, H. Polling systems: Applications, modeling, and optimization / H. Levy, M. Sidi // IEEE Transactions on Communications. - 1990. - Nov. -Vol. 38. - P. 1750 1760.

57. Nassehi, M. CRMA: an access scheme for high-speed LANs and MANs / M. Nassehi // Communications, 1990. ICC '90, Including Supercomm Technical Sessions. SUPERCOMM/ICC '90. Vol. 4. - 05/1990. - P. 1697 1702.

58. Pawlikowski, K. Steady-State Simulation of Queuing Processes: A Survey of Problems and Solutions. / K. Pawlikowski // ACM Comput. Sur v. - 1990. -June. - Vol. 22. P. 123 - 170.

59. Kleinrock, L. Performance Evaluation of Distributed Computer-Communication Systems / L. Kleinrock. - 1988. Oct.

60. Takagi, H. Queuing analysis of polling models / H. Takagi // ACM Computing Surveys (CSUR). - 1988. - Vol. 20.1. - P. 5 - 28.

61. Takagi, H. Analysis of Polling Systems / H. Takagi. - Cambridge, MA, USA : MIT Press, 1986. - 175 p.

62. M an field, D. R. Analysis of a Priority Polling System for Two-Way Traffic / D. R. Manfield // Communications, IEEE Transactions on. - 1985. Oct. -Vol. Com 33. - P. 1001 - 1006.

63. В их, W. Local-Area Subnetworks: A Performance Comparison / W. Bux // IEEE Transactions on Communications. - 1981. - Oct. - Vol. 29, no. 10. -P. 1465 - 1473.

64. Климов, Г. П. Системы обслуживания с разделением времени. 1 / Г. П. Климов // Теория вероятн. и ее примен. 1974. т. 19, № 3.

с. 558 576.

Список рисунков

1.1 Режим функции централизованной координации PCF......... 13

3.1 Схема пакета прикладных программ ....................................51

3.2 Пример модели имитационного моделирования для системы адаптивного поллинга с исчерпывающей дисциплиной ................53

3.3 Основная структура программы..........................................57

3.4 Механизм работы программного пакета..................................59

3.5 График флуктуации среднего времени пребывания в системе циклического опроса с шлюзовой дисциплиной при ¿тах = 10-4 ... 60

3.6 График флуктуации среднего времени пребывания в системе циклического опроса с шлюзовой дисциплиной при етах = 10-10 . . 61

4.1 Среднее время пребывания для системы адаптивного динамического поллинга с шлюзовой и исчерпывающей дисциплиной 84

4.2 Среднее время пребывания для системы с упорядоченым адаптивным динамическим опросом с шлюзовой и исчерпывающей дисциплиной................................ 85

4.3 Среднее время пребывания в системе циклического опроса с шлюзовой и исчерпывающей дисциплиной............... 86

4.4 Зависимость среднего времени пребывания от интенсивности входного потока при шлюзовой дисциплине............... 87

4.5 Зависимость среднего времени пребывания от интенсивности при исчерпывающей дисциплине....................... 88

4.6 Зависимость V от А при исчерпывающем, шлюзовом, 1-ограниченном и 2-ограниченном исчерпывающем обслуживании . . 93

4.7 Зависимость V от А при 1-ограниченном, 2-ограниченном

1

4.8 Зависимость V от А при 1-уменыпающем и шлюзовом обслуживании 94

4.9 Зависимость V от А при исчерпывающем, шлюзовом, 12

обслуживании ............................... 95

4.10 Зависимость V от Л при 1-ограниченном, 2-ограниченном исчерпывающем, 1-уменыпающем, исчерпывающем и адаптивном обслуживании ............................... 96

4.11 Зависимость V от Л при 1-уменыпающем, шлюзовом и адаптивном обслуживании ............................... 96

4.12 График зависимости среднего времени пребывания при различных типах входных потоков и распределения времени обслуживания ... 98

4.13 Зависимость V от Л при адаптивном и циклическом опросе ..... 99

4.14 Зависимость V от Л при циклическом и адаптивном опросе в случае большого среднего времени переключения...............100

Список таблиц

1 Описание фазового распределения........................................56

2 Описание МАР-потока ....................................................56

3 Пример входных и выходных данных....................................58

4 Реализованные модели систем поллинга..................................61

5 Случай в = 0................................................................89

6 Случай в = 0.002 ..........................................................89

7 Случай в = 0.002 ..........................................................89

в = 0.002

опросом и N = 3............................................................90

в=0

10 Случай в = 0.002 ..........................................................91

И Случай в = 0.002, N =2..................................................91

12 Случай в = 0.002, N =3..................................................92

13 Зависимость среднего времени пребывания от дисциплины обслуживания ..............................................................93

14 Зависимость среднего времени пребывания от дисциплины обслуживания в системе с адаптивным обслуживанием................95