Анализ характеристик систем массового обслуживания при передаче непуассоновского трафика методом аппроксимации функций распределения тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Чупахина, Лилия Равилевна
- Специальность ВАК РФ05.12.13
- Количество страниц 268
Оглавление диссертации кандидат наук Чупахина, Лилия Равилевна
СОДЕРЖАНИЕ
Перечень сокращений
Введение
Глава 1. Мультисервисные сети, основные понятия
1.1. Общая характеристика системы массового обслуживания
1.2. Структура и классификации систем массового обслуживания
1.3. Поток событий. Простейший поток и его свойства
1.4. Дисциплина обслуживания
1.5. Модели систем массового обслуживания
1.5.1 Простейшие случаи систем массового обслуживания
1.6. Аппроксимация функций распределений, методы аппроксимации.. 26 Выводы по главе 1
Глава 2. Исследование функций плотности распределения
вероятностей
2.1 Кумулянтный анализ
2.1.1 Аппроксимация функций плотности распределения
вероятностей с помощью ряда Эджворта
2.2 Метод Прони
2.2.1 Алгоритм аппроксимации функции плотности распределения
с помощью метода Прони
Выводы по главе 2
Глава 3. Аппроксимация функций распределения вероятностей
3.1. Метод аппроксимации функции плотности распределения вероятностей с «тяжелым» хвостом суммами экспонент
3.1.1 Алгоритм аппроксимации функции плотности распределения
вероятностей суммами экспонент
3.2. Метод аппроксимации произвольной функции плотности
распределения вероятностей суммами экспонент
Выводы по главе 3
Глава 4. Интегральное уравнение Линдли
4.1 Решение интегрального уравнения Линдли
4.2 Решение интегрального уравнения Линдли для системы массового обслуживания типа G/G/1
4.3 Решение интегрального уравнения Линдли для системы массового
обслуживания типа G/G/1 для частных случаев
Выводы по главе 4
Заключение
Список использованных источников
Акты внедрения
Перечень основных сокращений
ИУ - интегральное уравнение
МНК - метод наименьших квадратов
МСС - мультисервисная сеть связи
ОУ - обрабатывающее устройство
РТХ - распределение с «тяжелыми хвостами»
СЛАУ - система линейных алгебраических уравнений
СМО - система массового обслуживания
ТМО - теория массового обслуживания
FIFO (first-in, first-out) - алгоритм обработки очередей - «первый пришёл -первый вышел»
G/G/1 - СМО с одной обслуживающей линией, произвольным входящим потоком, произвольным распределением времени обслуживания
G/G/n - СМО с п обслуживающими линиями, интервалы времени между пакетами распределены произвольно, произвольным распределением времени обслуживания
G/M/1 - СМО с одной обслуживающей линией, интервалы времени между пакетами распределены произвольно, время обслуживания распределено экспоненциально
GOF (Goodness of fit) - критерий согласия
IPTV (Internet Protocol Television) - интерактивное телевидение LIFO (last-in, first-out) - алгоритм обработки очередей - «последний пришёл —первый вышел»
M/D/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, детерминированным распределением времени обслуживания
M/G/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, произвольным распределением времени обслуживания
M/M/l - СМО с одной обслуживающей линией, пуассоновским входящим потоком, экспоненциальным распределением времени обслуживания
MLE (maximum-likelihood estimation) - Метод максимального правдоподобия
NGN (Next Generation Network ) - сети следующего поколения
QoS (Quality of Service) - качество обслуживания
Рекомендованный список диссертаций по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК
Разработка метода численного анализа характеристик узлов обработки трафика мультисервисной сети2013 год, кандидат наук Козырева, Надежда Ивановна
Анализ вероятностно-временных характеристик узлов обработки непуассоновского мультимедийного трафика мультисервисных сетей связи2015 год, кандидат наук Самойлов Михаил Сергеевич
Разработка и исследование методов анализа качества обслуживания коррелированного трафика в телекоммуникационных сетях2020 год, доктор наук Карташевский Игорь Вячеславович
Исследование влияния статистических свойств мультимедийного IP-трафика на характеристики качества обслуживания2013 год, кандидат технических наук Буранова, Марина Анатольевна
Разработка методов исследования математических моделей немарковских систем обслуживания с неограниченным числом приборов и непуассоновскими входящими потоками2014 год, кандидат наук Моисеева, Светлана Петровна
Введение диссертации (часть автореферата) на тему «Анализ характеристик систем массового обслуживания при передаче непуассоновского трафика методом аппроксимации функций распределения»
Введение
Современные телекоммуникационные системы характеризуются значительной сложностью происходящих в них процессов. Марковская классическая модель системы массового обслуживания (СМО) [11, 40, 41, 87] не может полностью описать параметры современных телекоммуникационных систем, что в свою очередь порождает серьезную недооценку реальной нагрузки и значительное ухудшению качества обслуживания (С^оБ) при реализации услуг разного вида. Стандартные методы моделирования СМО для анализа и прогнозирования процессов, происходящих в обслуживающем устройстве, зачастую приводят к неудовлетворительным оценкам результатов его работы. Следовательно, непуассоновский характер трафика современной телекоммуникационной системы требует применения новых математических методов его исследования.
Бурное развитие мультисервисных сетей связи (МСС), которые определенным образом характеризуют структуру и поведение пакетов в ней, рост объема передаваемой информации, привели к новому восприятию современной телекоммуникационной инфраструктуры. В связи с этим построение моделей МСС и их исследование от частного случая к общему, является актуальной задачей, и в настоящее время привлекают внимание многих исследователей [4, 5, 6, 28, 43, 49, 90, 97, 102, 106, 108, 110].
В последнее время все больше исследований посвящается вопросу анализа непуассоновского трафика МСС, обладающего самоподобием [37, 40, 51, 54, 73, 103]. Математическая теория самоподобных процессов изучена довольно хорошо, однако практическая реализация все еще оставляет ряд нерешенных вопросов, особенно при передаче информационного потока в МСС. Существует большое количество исследований, посвященных имитационному моделированию работы сетевого устройства при передаче самоподобного потока. Однако теоретическая база процесса передачи
информации в основном применима только для некоторого рассматриваемого коммуникационного оборудования. Алгоритмы прогнозирования и методы мониторинга для анализа трафика МСС важны и интересны как с точки зрения использования при проектировании, так и на практике, например во время большой загрузки системы на сети оператора связи.
В силу непуассоновского характера поведения реального трафика в качестве модели целесообразнее использовать СМО типа G/G/l (G/G/n), так как на практике, при исследовании реальных систем, редко бывают, известны законы распределения и обслуживания поступающего на вход системы трафика.
Существенный вклад в решение задач анализа и проектирования сетей внесли российские ученые Б. С. Цыбаков, В. И. Нейман, В. М. Вишневский, С. Н. Степанов, О. И. Шелухин, Г. П. Башарин, А. Е. Кучерявый, К. Е. Самуйлов, Г. Г. Яновский и др., а также зарубежные ученые К. Park, W. Willinger, P. Abry, M. S. Taqqu, I. Norros и др. исследователи.
На данный момент анализ СМО типа G/G/1 не решен, с точки зрения того, чтобы можно было описать эту систему с помощью любого математического аппарата, либо любого другого программно-аппаратного комплекса для решения данной задачи.
Чтобы управлять всплесками трафика, необходимо решить задачу определения функции плотности вероятности распределения интенсивностей. В случае произвольных потоков расчет средних значений характеристик обслуживания заявок обычно проводится на основе аппроксимации закона распределения интервалов времени между пакетами в потоке и распределения длительности обслуживания пакетов.
Методы для расчета характеристик звена при поступлении непуассоновского трафика пока мало изучены, что очередной раз доказывает актуальность темы диссертации.
Содержание диссертации соответствует пунктам 4 и 14 паспорта специальности 05.12.13 - «Исследование путей совершенствования управления информационными потоками», «Разработка методов исследования, моделирования и проектирования сетей, систем и устройств телекоммуникаций».
Цель и задачи работы. Целью диссертационной работы является анализ характеристик СМО при обработке непуассоновского трафика МСС на основе аппроксимации законов распределения интервалов времени между пакетами и длительностей обслуживания пакетов.
Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:
— исследование математических моделей, описывающих непуассоновский трафик МСС и не марковский характер обслуживания;
— использование методов аппроксимации для моделирования плотностей распределения вероятностей интервалов времени между поступлениями пакетов и распределения вероятностей длительностей обслуживания пакетов, с учетом самоподобных свойств процессов поступления и обслуживания;
— разработка метода аппроксимации функций плотностей распределения суммой затухающих экспонент;
— анализ функций распределений с «тяжелыми хвостами» (РТХ) для получения аппроксимирующих выражений в виде суммы затухающих экспонент;
— анализ статистических данных, собранных с реальной сети, построение моделей функций плотностей распределения интервалов времени между пакетами и длительности обслуживания пакетов;
— разработка алгоритма решения интегрального уравнения (ИУ) Линдли для СМО типа вЛл/! с помощью спектрального метода.
Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов математического анализа, математической статистики, теории вероятностей, статистической обработки данных и вычислительных методов, реализованных в пакете Matlab и Matead.
Научная новизна исследований, проведенных в диссертации, состоит в следующем:
— разработан метод аппроксимации гиперэкспоненциальных функций плотности распределения вероятностей суммой затухающих экспонент для анализа входящего и обслуживаемого трафика МСС;
— получена аппроксимация функций плотности распределения вероятностей для реального входящего и обслуживаемого в узле МСС трафика;
— получено решение ИУ Линдли для СМО типа G/G/1 для гиперэкспоненциальных распределений.
Практическая ценность диссертации.
Полученный в данной работе метод решения ИУ Линдли позволяет использовать в качестве математической модели СМО типа G/G/1. На основе разработанных методов аппроксимации можно проанализировать работу СМО типа G/G/1 спектральным методом.
Результаты работы внедрены в ОАО «Концерн «Автоматика», в курсах «Основы теории массового обслуживания», «Сетевые технологии высокоскоростной передачи данных» ФГОБУ ВПО ПГУТИ, что подтверждается актами внедрения.
Основные положения и результаты, выносимые на защиту:
— последовательности интервалов времени между пакетами и длительностей пакетов для трафика МСС обладают свойством самоподобия и могут быть описаны РТХ;
— аппроксимацию распределений вероятностей характеристик реального трафика целесообразно проводить с использованием методов кумулянтного анализа;
— используемые РТХ могут быть аппроксимированы суммой затухающих экспонент, при условии, что коэффициенты аппроксимации должны быть вещественными и отрицательными при положительных значениях аргумента;
— для решения ИУ Линдли при применении предложенных методов аппроксимации может быть использован алгоритмически простой спектральный метод.
Личный вклад автора. Все основные научные результаты, теоретических и прикладных исследований, выводы, изложенные в диссертации, получены автором самостоятельно. В работах, опубликованных в соавторстве, соискателю принадлежит часть, связанная с постановкой задач и проведением экспериментальных исследований.
Обоснованность и достоверность результатов работы. Обоснованность и достоверность результатов обеспечиваются адекватной постановкой задач, решаемых в диссертационной работе; корректностью использования математического аппарата. Достоверность результатов подтверждается экспериментальными данными, полученными в процессе исследования и анализа трафика МСС.
Внедрение результатов работы. Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» г. Москва и в учебный процесс кафедры «Мультисервисных сетей и информационной безопасности» ФГОБУ ВПО ПГУТИ, что подтверждено актами внедрения.
Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на 7-й Отраслевой научно-технической конференции-форуме «Технологии информационного общества», (г. Москва, 2013), на XII, XIII Международной научно-
технической конференции «Проблемы техники и технологий телекоммуникаций» (г. Уфа, 2010, г. Казань, 2011), на 14-й и 15-й Международной Конференции «Цифровая обработка сигналов и ее применение» (г. Москва, 2012-2013 гг.), на XXXIX Международной научно-практической конференции «Физико-математические и технические науки как постиндустриальный фундамент эволюции информационного общества», (г. Лондон, 2013), на X Международная научно-техническая конференция «Физика и технические приложения волновых процессов» (г. Самара, 2011), на Международной научно-практической Интернет-конференции «Современные направления теоретических и прикладных исследований'2013», (г. Одесса, 2013), на Международной научно-практической Интернет-конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2013», (г. Одесса, 2013), на Всероссийской научно-практической конференции «Проблемы передачи информации в инфокоммуникационных системах» (г. Волгоград, 2013), на Первой Международной научно-практической конференции «Проблемы инфокоммуникаций. Наука и технологии» (Р1С8&Т-2013) (г. Харьков, 2013), на XVII, XVIII, XIX, XX Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов (ФГОБУ ВПО ПГУТИ, г. Самара, 2010-2013 гг.).
Публикации результатов. По результатам исследования опубликовано 18 печатных работ, 4 из них в изданиях из перечня ВАК, 9 публикаций международных научных конференций, 5 тезисов докладов.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 134 страниц машинописного текста, 100 рисунков, 23 таблицы. В списке литературы 113 наименований.
Глава 1. Мультисервисные сети, основные понятия
Появление новых сетевых технологий привело к появлению новых терминов, обеспечивающих: мультимедиа телекоммуникации, услуги широкополосного доступа, услуги с гарантией времени доставки трафика и т.п. [30].
В современной телекоммуникационной сети прослеживается конвергенция различных услуг и видов трафика, объединение их в единую
мсс.
Мультисервиная сеть - это единая телекоммуникационная инфраструктура для переноса трафика произвольного типа, порождаемого взаимодействием потребителей и поставщиков услуг связи с контролируемыми и гарантированными параметрами трафика, уровня качества и конфиденциальности, свойственными каждому виду услуг [30].
Основные услуги, предоставляемые МСС:
— передача традиционного телефонного трафика;
— передача трафика данных (например, данных Интернет);
— передача трафика данных корпоративной сети;
— передача трафика мобильных сетей;
— доступ в Интернет;
— доступ к сетям передачи данных.
Одним из математических методов исследования сложных телекоммуникационных систем является ТМО, занимающаяся анализом эффективности функционирования СМО [82].
Система массового обслуживания - динамическая система, предназначенная для эффективного обслуживания случайного потока заявок при ограниченных ресурсах сети. Случайных характер поступления заявок и случайных характер промежутков времени подразумевает, что СМО работает
по определенной дисциплине ожидания и обслуживания поступившего на вход системы требования [82].
При исследовании МСС лучше рассматривать основной элемент системы - узел (канал, линия связи). Свойства узла МСС можно описать моделями элементарных СМО, например, взяв за основу классическую марковскую теорию. А ТМО используется как математический аппарат для исследования и установления взаимосвязи между характеристиками потока пакетов, числом каналов, их производительностью [82]. Поэтому как объект исследования целесообразно рассматривать узел МСС, канальный ресурс которой используется п потоками сообщений [49].
Исследуя МСС, необходимо помнить, что концепция развития сетей следующего поколения (NGN) подразумевает предоставление неограниченного набора услуг с заданными характеристиками качества. Сети строятся на основе пакетных технологий. Проектирование современной сети связи подразумевает обслуживание трафика различных коммуникационных приложений (речь, видео, данные) [17, 73]. Структурная схема исследуемой
МСС представлена на рис. 1.1. fi,, v
Рис. 1.1. Структурная схема: 1 - поток управляющей информации, 2 — поток голосовых сообщений, 3 - поток видеоинформации, 4 - поток данных, 5 - узел МСС, 6 - МСС
Перечислим требования, которым должна удовлетворять МСС:
— гарантированное (^оБ пользователей;
— доставка информации, чувствительной к задержке, в реальном
масштабе времени;
— обеспечение передачи данных с требуемой скоростью;
— централизованное управление сетью.
Информационные потоки, передаваемые по линии связи, по своим свойствам значительно отличаются от потоков речевых сообщений. Поэтому применение методов анализа и оценки характеристик сети, развитых в классической теории телетрафика, нужно использовать с рядом оговорок, и в некоторых случаях неприемлемы.
В работах [43, 52, 64, 81, 86, 89] отмечено, что повсеместное развитие МСС сдерживает один недостаток сетей с коммутацией пакетов - плохая приспособленность к передаче трафика реального времени. Множество работ [13, 15, 16, 22, 28, 30, 43, 50, 88] посвящено обеспечению должного (^оБ, так как существует проблема чувствительности параметров трафика при передаче в реальном времени (видеоконференцсвязь, 1РТУ и др.).
Постоянное развитие и модернизация телекоммуникационных сетей определяется тремя факторами: ростом трафика, потребностью общества в новых услугах и достижениями в области технологий. Данные факторы не являются независимыми, однако каждый из них определяет идеологию развития электросвязи. Достижение рынка современной телекоммуникационной системы и конкуренция среди поставщиков оборудования ведет к снижению стоимости оборудования и стимулированию роста трафика, разработке новых услуг [73, 74].
Исследуемая математическая модель должна представлять собой МСС, и иметь свойства и параметры близкие к реальной телекоммуникационной сети связи.
Современные методы и модели анализа производительности компьютерных сетей явно можно разделить на два направления: аналитическое вероятностное моделирование на основе ТМО и имитационное (дискретно-событийное) моделирование. Методы первого направления, основанные на последних результатах ТМО, ограничиваются только пуассоновскими потоками в сетях СМО типа М/М/1, М/Е)/1, МЛл/1 и др. [2, 6, 8, 67,91,93,94].
Ограниченность пуассоновских моделей подтверждают публикации о самоподобных процессах как моделях трафика с РТХ [6, 112,113, 84, 85, 95, 96, 103]. В этих работах утверждается, что трафик МСС не может адекватно описываться пуассоновскими моделями, так как они приводят к слишком оптимистичным результатам по задержкам [6].
1.1 Общая характеристика системы массового обслуживания
Характерным для описания процессов передачи данных пакетным трафиком являются обнаруженные на практике свойства самоподобия или масштабной инвариантности статистических характеристик. В современной научной литературе эти свойства связывают с особым классом физических процессов - фрактальными процессами. В связи с этим, разработка новых сетевых технологий и повышение эффективности работы современных телекоммуникационных систем требует создания математических моделей, наиболее полно отражающих отмеченные свойства сетевых процессов [29].
Для случая самоподобного трафика методов расчета характеристик С)о8 неизвестно. Причиной этому является непредсказуемость самоподобных потоков, вследствие чего и невозможно получить аналитически обоснованные результаты для характеристик СМО, в которых обслуживаются данные потоки. Несмотря на популярность модели самоподобного трафика, до сих пор ряд задач оценки С>о8 СМО остается
нерешенными. В частности, из-за отсутствия строгой теоретической базы, способной дополнить классическую ТМО при проектировании СМО с самоподобным трафиком, не существует достоверной и признанной методики расчета параметров и показателей качества систем распределения информации в условиях «пачечного» эффекта. Очевиден и тот факт, что на характеристики (^о8 влияют и вероятностные законы распределения длительности обслуживания [54]. Поэтому вопросы исследования трафика с непуассоновкими функциями распределениями вероятностей длительностей поступления и обслуживания остается актуальным.
1.2 Структура и классификации систем массового обслуживания
Структуру простейшей СМО можно представить в виде (рис.1.2.):
Рис. 1.2. Структура простейшей СМО: И - источник пакетов, Я -накопитель (буфер), К ■ - у -й канал обслуживания
В современной технической литературе для описания сложных СМО используется классификация Кендалла-Башарина, основанная на пяти символах А/ В / т / К / N, где А - обозначает распределение интервалов во входном потоке, В - распределение времени обслуживания, т— число обслуживающих приборов в системе (каналов, линий), К — число мест в накопителе, N — количество источников нагрузки. Символы А и В могут принимать следующие значения: М- экспоненциальное распределение,
Ек - распределение Эрланга, И - детерминированная величина, -
произвольное распределение [42, 75].
Для СМО разработана стандартная классификация за разными признаками, среди которых наиболее важными являются:
— структура системы;
— функция распределения вероятностей потоков требований, которые поступают в системе;
— функция распределения вероятностей времени обслуживания, порядок (дисциплина) обслуживания;
— допустимая длина очереди перед обслуживающими приборами. Любая система характеризуется своей структурой, то есть составом ее
основных частей и функциональными связками между ними. Основной частью для СМО такими являются обслуживающие приборы (каналы). Если система содержит только один канал, такая система называется одноканальной. Если система имеет несколько каналов, предназначенных для одновременного (параллельного) обслуживания требований, которые поступают в систему, то ее называют многоканальной.
Для анализа процесса обслуживания потоков требований необходимо учитывать характеристики узла МСС и поведения системы в различных случаях: перегрузка системы, резервное или аварийное обслуживание.
Рассматривая МСС от одной системы к целой совокупности систем, на основе модели СМО, упрощает громоздкость вычислений, позволяет расширить и более детально изучить происходящие процессы. СМО делятся на типы (или классы) по ряду признаков. Первое деление: СМО с отказами и СМО с очередью. В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует. Примеры СМО с отказами встречаются в телефонии: заявка на разговор, пришедшая в момент, когда все каналы связи заняты, получает отказ и
покидает СМО необслуженной. В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной. На практике чаще встречаются (и имеют большее значение) СМО с очередью [61].
В свою очередь, СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь - ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания.
При анализе СМО должна учитываться также и «дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления, либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом - некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным - когда заявка с более высоким приоритетом «вытесняет» с обслуживания заявку с низшим, так и относительным - когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди [61].
Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок Я,, производительность каждого канала (среднее число заявок, обслуживаемых непрерывно занятым каналом в единицу времени), условия образования очереди (ограничения, если они есть). Следует отметить, что существуют СМО с многофазовым обслуживанием, состоящим из нескольких последовательных этапов, которые тоже представляют большой интерес в исследовательской работе [61].
При этом физическая модель должна быть составлена, таким образом, чтобы (^оБ оставалось в допустимых пределах. Ее алгоритм и полученные в результате исследований параметры должны удовлетворять заданным
условиям работы обслуживающего устройства (ОУ) и позволять получить значения в пределах допустимой погрешности.
ТМО получила широкое применение в современной жизни общества, начиная с бытового обслуживания до космических исследований, так как позволяет строить необходимую модель и учитывать различные необходимые требования. Однако все-таки определяющую роль в развитии ТМО продолжает играть одна из ее ветвей теория телетрафика.
1.3 Поток событий. Простейший поток и его свойства
При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто бывает удобно представить себе процесс так, как будто переходы системы из состояния в состояние происходят под действием каких-то потоков событий.
Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то, вообще говоря, случайные моменты времени. Положение каждой точки на оси случайно.
1. Поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени, что редко встречается на практике.
2. Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной т зависит только от длины участка и не зависит от того, где именно на оси времени расположен этот участок (однородность по времени) -вероятностные характеристики такого потока не должны меняться от времени. В частности, так называемая интенсивность (или плотность) потока событий (среднее число событий в единицу времени) постоянна.
3. Поток событий называется потоком без последствия, если для любых непересекающихся участков времени число событий, попадающих на один из
них, не зависит от того, сколько событий попало на другой (или другие, если рассматривается больше двух участков). Отсутствие последствия в потоке означает, что события, образующие поток, появляются в последовательные моменты времени независимо друг от друга.
4. Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежительно мала по сравнению с вероятностью попадания одного события (события в потоке приходят поодиночке, а не парами, тройками и т.д.).
Поток событий, обладающий всеми тремя свойствами, называется простейшим (или стационарным пуассоновским). Нестационарный пуассоновский поток обладает только свойствами 2 и 3 [24, 40, 41, 70, 72].
1.4 Дисциплина обслуживания
Дисциплиной обслуживания называется правило, по которому выбираются на обслуживание требования из очереди. Различают следующие виды дисциплин обслуживания:
— обслуживание в порядке поступления или дисциплина FIFO (First Input, First Output — первым пришел, первым ушел);
— обслуживание в обратном порядке или дисциплина LIFO (Last Input, First Output — последним пришел, первым ушел);
— обслуживание в случайном порядке, когда заявка на обслуживание выбирается случайно среди ожидающих заявок.
1.5 Модели систем массового обслуживания
СМО можно представить моделью. Математическая модель системы распределения информации включает следующие три основных элемента:
входящий поток заявок (требований на обслуживание), схему системы распределения информации, дисциплину обслуживания потока заявок.
Среди аналитических вероятностных математических моделей систем одним из наиболее востребованных классов является класс непрерывно-стохастических моделей. Эти модели характерны для ТМО, рассматривающей абстрактные процессы обслуживания требований, которые помимо всего прочего могут образовывать очереди [39].
В моделях СМО рассматривают следующие объекты:
— требования на обслуживание (транзакты);
— обслуживающие приборы.
Практическая задача ТМО связана с исследованием операций этими объектами и состоит из отдельных элементов, на которые влияют случайные факторы [39].
Модели СМО используются для исследования процессов, происходящих в системе, при подаче на входы потоков требований, данные процессы представляют собой последовательность событий [39].
Одними из важных свойств являются выходные параметры сети:
— производительность;
Похожие диссертационные работы по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК
Методы асимптотического и диффузионного анализа математических моделей систем случайного множественного доступа2022 год, доктор наук Пауль Светлана Владимировна
Математические модели и методы анализа немарковских сетей массового обслуживания на основе гиперэкспоненциальных распределений2021 год, кандидат наук Липилина Людмила Владимировна
Математические модели и методы исследования систем параллельного обслуживания сдвоенных заявок случайных потоков2013 год, кандидат физико-математических наук Синякова, Ирина Анатольевна
Системы массового обслуживания поликомпонентных потоков с произвольным количеством источников и ограничений по длине очереди2020 год, доктор наук Титовцев Антон Сергеевич
Математические модели гетерогенных бесконечнолинейных СМО с параметрами, зависящими от состояния случайной среды2024 год, кандидат наук Полин Евгений Павлович
Список литературы диссертационного исследования кандидат наук Чупахина, Лилия Равилевна, 2013 год
Список использованных источников
1. Алиев, Т. И. Основы моделирования дискретных систем / Т. И. Алиев. - СПб: СПбГУ ИТМО, 2009. - 21 с.
2. Алиев, Т. И., Кругликов, В. К., Муравьева, Л. А. Анализ сетей передачи данных с неоднородными сообщениями / Т. И Алиев, В. К. Кругликов, Л. А. Муравьева // Изв. вузов СССР. Приборостроение. - 1989. - № 1. -с.
3. Аппроксимация функций [Электронный ресурс]. - Режим доступа: http://physics.herzen.spb.ru/library/01/01/nm_labs/approximation.htm, свободный. - Загл. с экрана. (27.08.2013).
4. Баскаков, С. И. Радиотехнические цепи и сигналы: учеб. для вузов / С. И. Баскаков. - 2-е изд. - М.: Финансы и статистика, 2000. - 304 е.: ил.
5. Бахарева, Н. Ф., Карташевский, И.В., Тарасов, В.Н. Анализ и расчет непуассоновских моделей трафика в сетях ЭВМ/ Н. Ф. Бахарева, И. В. Карташевский, В.Н.Тарасов // Инфокоммуникационные технологии. -2009,- Т. 7, №4.-С. 61-66.
6. Бахарева, Н.Ф. Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей: автореф. дис. ... док. техн. наук : 05.13.15 / Бахарева Надежда Федоровна. - Пенза. 2011. -36 с.
7. Бахвалов, Н. С., Жидков, Н. П., Кобельков, Г. Н. Численные методы / Н. С. Бахвалов, Н. П. Жидков, Г. Н Кобельков. - М.: Лаборатория Базовых Знаний, 2003. - 632 с.
8. Башарин, Г.П. Лекции по математической теории телетрафика / Г. П. Башарин. - М.: РУДН, 2009. - 342 с.
9. Бендат, Дж., Пирсол, А. Прикладной анализ случайных данных / Дж. Бендат, А. Пирсол. - Мир, 1989. - 540 с.
10. Бердышев, В. И., Петрах, Л. В. Аппроксимация функции, сжатие численной информации, приложения / В. И. Бердышев, Л. В. Петрак. -Екатеринбург: УрО РАН, 1999. - 295 с.
П.Берсенев, Г. Б. Приближенная формула для фазы обслуживания в замкнутой стохастической сети / Г. Б. Берсенев // Автоматические системы оптимального управления технологическими процессами. -Тула, ТПИ, 1980.-С. 108-116.
12. Боровков, А. А. Вероятностные процессы в теории массового обслуживания: учеб. для вузов / А. А. Боровков. - М.: Наука, 1971. -368 с.
13. Бочаров, П. П., Павлова, О. И. Анализ очереди с распределением фазового типа и инверсионной дисциплиной обслуживания с прерываниями / П. П. Бочаров, О. И. Павлова. // Автоматика и телемеханика. - № 11? 1992. - С.53-59.
14. Бронштейн, И. Н., Семендяев, К. А. Справочник по математике для инженеров и учащихся втузов / И. Н. Бронштейн, К. А. Семендяев. -М.: Наука, 1986.-544 с.
15. Бурлаков, Е. О., Касибин, С. В. Оценка эффективности обслуживания заявок в сетях связи на конечных интервалах времени / Е. О. Бурлаков, С. В. Касибин. // Радиотехника. - 2007. - № 6. - С.3-9.
16. Бычков, Е. Д., Коваленко, О. Н. Алгоритм оценки состояния пучка каналов мультисервисной сети / Е. Д. Бычков, О. Н. Коваленко. // Математика и информатика, наука и образование. - ОмГПУ. - 2007. -С.78-80.
17. Введение в управление инфокоммуникациями / Самуйлов К. Е., Серебренникова Н. В., Чукарин А. В., Яркина Н. В.// Учеб.пособие. -М.:РУДН, 2008.-87 с. :ил.
18. Вентцель, Е. С. Теория вероятностей / Е. С. Вентцель. - М., Физматгиз, 1962.-564 с.
19. Вентцель, Е. С., Овчаров, Л. А. Теория случайных процессов и ее инженерные применения / Е. С. Вентцель, Л. А. Овчаров. - М.: Высшая школа, 2000. - 284 с.
20. Вероятность и математическая статистика: энцикл. / под ред. Ю.В. Прохорова. - М. : Большая Российская энциклопедия, 2003. - 912 с. -Репр. изд.
21. Верстаков, Е. В. Аппроксимация двумерных сигналов с помощью метода Прони / Е. В. Верстаков // Радиолокация, радионавигация, связь: Материалы XVI международной НТК. - Воронеж: Изд. НПФ «САКВОЕЕ» ООО. - 2010. - Т. 1. - С. 22-28.
22. Вишневский, В.М., Семенова, О. В. Математические методы исследования систем поллинга / В. М Вишневский, О. В. Семенова // Автоматика и телемеханика. - 2006. - № 2. - С. 3-18.
23.Гарипова, Л.Р., Киреева, Н.В. Кумулянтный подход к исследованию системы ОЛЗ/1 / Л. Р. Гарипова, Н. В. Киреева / XIV Международная Конференция и Выставка, «Цифровая обработка сигналов и ее применение» : сб. тр. науч. конф. - Москва, 2012. - С. 159-164.
24. Гмурман, В. Е. Теория вероятностей и математическая статистика / В. Е. Гмурман. - М.: Высш. шк., 2002. - 479 с.
25. Гнеденко, Б. В. Курс теории вероятностей / Б. В. Гнеденко. - М: Физматгиз, 1961. - 406 с.
26. Гнеденко, Б. В., Коваленко, И.Н. Введение в теорию массового обслуживания. / Б. В. Гнеденко, И. Н. Коваленко. - М.: Наука. - 1966. -301 с.
27. Голубинский, А. Н. Методы аппроксимации экспериментальных данных и построения моделей / А. Н. Голубинский // Вестник ВИ МВД России. - 2007. - № 2. - С. 138-143.
28. Голышко, А. В., Ершов, В. Е., Цыбаков, В. И. Оценка эффективности интеграции разных видов обслуживания на корпоративной
мультисервисной сети / А. В. Голышко, В. Е. Ершов, В. И. Цыбаков // Электросвязь. - 2000. - №12. - С. 16-19.
29. Городецкий, А. Я. Информатика. Фрактальные процессы в компьютерных сетях: учеб. пособие. / А. Я. Городецкий, В. С. Заборовский. - СПб.: Изд-во СПбГТУ, 2000. - 102 с.
30. Гургенидзе, А. Т., Кореш, В. И. Мультисервисные сети и услуги широкополосного доступа: монография / А. Т Гургенидзе, В. И. Кореш. - М. : Наука и техника, 2003. - 400 с.
31. Демидович, Б. П. Основы вычислительной математики / Б. П. Демидович, И. А. Марон. - М. : Физматлит, 1970. - 664 с.
32. Дьяконов, В. МАТЬАВ. Анализ, идентификация и моделирование систем. Специальный справочник / В. Дьяконов, В. Круглов. - СПб, Питер, 2002. - 448 с.
33. Задирака, В. К. Теория вычисления преобразования Фурье / В. К. Задирака- Киев: Наук, думка, 1983. - 216 с.
34. Зельдович, Я. Б. Элементы прикладной математики. / Я. Б. Зельдович, А. Д. Мышкис. - М.: Наука, гл. ред. физ-мат. лит., 1965. - 592 с.
35. Иванов, М. Т., Сергиенко, А. Б., Ушаков, В. Н. Теоретические основы радиотехники: Учебное пособие. / Под. ред. Ушакова В. Н. - М.: Высш. шк., 2002, - 306 с.
36. Ивченко, Г. И., Каштанов, В. А., Коваленко, И. Н. Теория массового обслуживания: учеб. пособие для вузов / Г. И. Ивченко, В. А. Каштанов, И. Н. Коваленко. - М.: Высшая школа, 1982. - 256 с.
37. Карташевский, В. Г. Основы теории массового обслуживания / В. Г. Карташевский. - М.: Радио и связь, 2006. - 107 с.
38. Кёниг, Д. Методы теории массового обслуживания / Д. Кёниг, Д. Штойян. - М.: Радио и связь, 1981. - 127 с.
39. Кириличев, Б.В. Моделирование систем: Учебное пособие / Б. В. Кириличев. - М. : МГИУ, 2009. - 274 с.
40. Клейнрок, Jl. Теория массового обслуживания. Перевод с англ. /Пер. И. И. Грушко; ред. В. И. Нейман / Л. Клейнрок. - М.: Машиностроение, 1979.-432 с.
41. Клейнрок, Л., Вычислительные системы с очередями. / Л. Клейнрок. Пер. с англ. - М.: Мир. - 1979.
42. Коваленко, H.H. Теория массового обслуживания / И.Н. Коваленко // Итоги науки, сер. теор. вероятн. - 1963, ВИНИТИ, - М., 1965, - С. 73125.
43. Коваленко, О.Н. Совершенствование метода оперативного распределения пропускной способности каналов мультисервисной сети с целью повышения эффективности их использования: дис. ... канд. техн. наук : 05.12.13 / Коваленко Ольга Николаевна. - Омск. 2009. -155 с.
44. Кожевников, Н. И., Краснощекова, Т. И., Шишкин, Н. Е. Ряды и интегралы Фурье. Теория поля. Аналитические и специальные функции. Преобразования Лапласа / Н. И. Кожевников, Т. И. Краснощекова, Н. Е. Шишкин. - М. : Наука, 1964. - 184 с.
45. Корн, Г., Корн, Т. Справочник по математике (для научных работников и инженеров / Г. Корн, Т. Корн. - М. : Наука, 1973. - 832 с.
46. Королюк, В. С., Портенко, Н. И., Скороход, А. В., Справочник по теории вероятностей и математической статистике / В. С/ Королюк,, Н. И. Портенко, А. В. Скороход. Изд-во Наука. - М., 1985. - 640 с.
47. Крамер, Г. Математические методы статистики Текст. / Пер. с англ. A.C. Монина и A.A. Петрова, под ред. академика А.Н. Колмогорова Изд. 2-е, стереотипное. - М: Мир, 1975. - 648 с.
48. Крылов, В. В., Самохвалова, С. С. Теория телетрафика и ее приложения/ В. В. Крылов, С. С. Самохвалова, БХВ-Санкт-Петербург. -2005-288 с.
49. Кузнецов, О.И. Звено мультисервисной сети связи с повторными вызовами/ О.И. Кузнецов // Электросвязь. - 2006. - № 9 - С. 43-45.
50. Кучерявый, А. Е., Гильченок, JI. 3., Иванов, А. Ю. Пакетная сеть связи общего пользования / А. Е. Кучерявый, JI. 3. Гильченок, А. Ю. Иванов. - СПб: Наука и Техника, 2004. - 274 с.
51. Лагутин, В. С., Степанов, С. Н. Телетрафик мультисервисных сетей связи. / B.C. Лагутин, С. Н. Степанов. - М. : Радио и связь, 2000. - 320 с.
52. Лагутин, В. С. Анализ эффективности совместного обслуживания новых информационных потоков на ГТС большой емкости / В. С. Лагутин // Электросвязь. - 1999. - № 3 - С. 28-32.
53. Лившиц, Б. С., Пшеничников, А. П., Харкевич, А. Д. Теория телетрафика. Учебник для вузов. / Б. С. Лившиц, А. П. Пшеничников, А. Д. Харкевич. - М. : Связь, 1979. - 224 с.
54. Ложковский, А. Г., Ганифаев, Р. А. Влияние закона распределения длительности обслуживания в условиях самоподобного трафика на параметры QoS / А. Г. Ложковский, Р. А. Ганифаев // Восточноевропейский журнал передовых технологий. - 2008. - № 4/3 (34). -С.46-50.
55. Лоу, А. М., Кельтон, В. Д. Имитационное моделирование. Классика CS. / А. М. Лоу, В. Д. Кельтон. - 3-е изд. - СПб.: Питер, 2004, - 848 с.
56. Малахов А.Н. Кумулянтный анализ случайных негауссовских процессов и их преобразований / А.Н. Малахов. - М., Советское радио, 1978.-376 с.
57. Марпл-мл. С.Л. Цифровой спектральный анализ и его приложения / С.Л. Марпл-мл. - М. : Мир, 1990. - 584 с.
58. Математика, статистика и анализ данных: русский блог Wolfram|Alpha Режим доступа: http://www.wolframalpha-ru.com/2011/11/wolframalpha 11.html, свободный. — Загл. с экрана.
59. Метод аппроксимации произвольной плотности распределения суммами экспонент / Блатов И. А., Карташевский В. Г., Киреева Н. В., Л. Р. // Вестник ВГУ. - 2013. - № 2. - С. 53-57.
60. Метрология и радиоизмерения: Учеб. для вузов / В.И. Нефедов, A.C. Сигов, В.К. Битюков, В.И. Хахин. - М: Высш. шк., 2006. - 526 с.
61. Моделирование систем. Режим доступа: http://sardismusic.com/topics/t9r2partl.html, свободный. - Загл. с экрана.
62. Муравьева-Витковская, Л.А. Оценка влияния параметров трафика на качество функционирования компьютерной сети с использованием СМО-моделей / Л. А. Муравьева-Витковская // Имитационное моделирование. Теория и практика: сб. докл. четвертой всероссийской науч. техн. конф. ИММОД-2009. Т. 2. - СПб.: ОАО «ЦТСС». - 2009. -С. 178-181.
63. Нейман, В. И. Самоподобные процессы и их применение в теории телетрафика / В.И. Нейман // Труды Международной академии связи. -1999.- № 3. - С.11-15.
64. Нечеткие множества в моделях управления и искусственного интеллекта / под ред. Д.А. Поспелова. - М.: Наука, 1986. - 311 с.
65. Овчаров, Л. А. Прикладные задачи теории массового обслуживания / Л. А. Овчаров. - М.: Машиностроение, 1969. - 324 с.
66. Ортогональные многочлены [Электронный ресурс]. Режим доступа: http://lseti.ru/matsoft6/uhebn2.htm, свободный. - Загл. с экрана.
67. Печинкин, А. В., Характеристики обслуживания в системе GI/GI/1/oo при дисциплине LCFS с прерыванием / А. В. Печинкин, Автомат, и телемех.- 1993.-№6.-С. 130-141.
68. Программа-снифер сетевого трафика. Режим доступа: http://www.wireshark.org/, свободный.. - Загл. с экрана.
69. Прохоров, С. А. Аппроксимативный анализ случайных процессов / С. А. Прохоров. - Самара: СГАУ, 2001. - 329 е.: ил.
70. Прохоров, Ю. В., Розанов, Ю. А., Теория вероятностей / Ю. В. Прохоров, Ю. А. Розанов. - 2-е изд. - М., 1973. - с.
71. Радиотехнические цепи и сигналы. Задачи и задания / В. Я. Баскей, В. Н. Васюков, Л. Г. Зотов и др. - М. : ИНФРА-М, 2003. - 348 с.
72. Саати, Т. Л. Элементы теории массового обслуживания и ее приложения: монография / Т. Л Саати. - М.: Сов. радио, 1971. - 520 с.
73. Степанов, С. Н. Основы телетрафика мультисервисных сетей / С. Н. Степанов. - М.: Эко-Трендз, 2010. - 392 с.
74. Телекоммуникационные системы и сети / Величко В. В., Субботин Е.
A., Шувалов В. П., Ярославцев А. Ф.; под ред. профессора Шувалова
B.П.; Т. 3 - М: Горячая линия - Телеком, 2005. - 592 е.: ил.
75. Труб И. И. Объектно-ориентированное моделирование на С++: Учебный курс. / И. И. Труб - СПб.: Питер, 2006. - 411 е.: ил.
76. Тюрин, Ю. Н., Макаров, А. А. Анализ данных на компьютере / под ред. В.Э. Фигурнова. Изд. 3-е, перераб. и доп. - М.: ИНФРА - М, 2002. -528 е., ил.
77. Фирсова, С. А. Алгоритмы оптимизации временной сложности кусочно-полиномиальной аппроксимации функций в применении к быстрому преобразованию Фурье на основе параллельного вычисления элементов базиса : автореф. дис. ... канд. техн. наук: 05.13.17, 05.13.18 / Фирсова Светлана Александровна. - Таганрог. - 2004. - 21 с.
78. Хинчин, А. Я. Работы по математической теории массового обслуживания / А. Я. Хинчин. - М.: Физматгиз, 1963. - 390 с.
79. Чупахина, Л.Р. Исследование системы 0/0/1 с помощью метода Прони / Н.В. Киреева, Л.Р. Чупахина // Сбор. докл. и тез. Всеросс. научно-практ. конф. «Проблемы передачи информации в инфокоммуникационных системах». - Волгоград, 2013. - С. 41-44.
80. Чупахина, Л. Р., Киреева, Н. В. Построение функций распределения реального трафика с помощью кумулянтного анализа / Л. Р. Чупахина,
Н. В. Киреева // Инфокоммуникационные технологии. - 2013. - Т. 11, № 1.-С. 33-36.
81. Шедоева, С. В. Исследование и разработка методов оценки пропускной способности элементов мультисервисных сетей на этапе установления соединений : дис. ... канд. техн. наук: 05.12.13/ Шедоева Светлана Васильевна. - Новосибирск. - 2004. - 127 с.
82. Шелухин, О. И, Тенякшев, А. М, Осин, А. В. Моделирование информационных систем / Под ред. О.И. Шелухина. Учебное пособие. - М. : Радиотехника, 2005. - 368 с.
83. Шелухин, О. И., Осин, А. В., Урьев, Г. А. Результаты экспериментальных исследований сетевого трафика телекоммуникационной сети / О. И Шелухин, А. В Осин, Г. А. Урьев // Теоретические и прикладные проблемы сервиса. - М.: МГУС, 2005. -№ 4. - С. 90-95.
84. Шелухин, О. И., Осин, А. В., Смольский, С. М. Самоподобие и фракталы. Телекоммуникационные приложения / О. И. Шелухин, А. В. Осин, С. М. Смольский. - М: Физматгиз, 2008. - 368 с.
85. Шелухин, О. И., Тенякшев, А. М., Осин, А. В. Фрактальные процессы в телекоммуникациях / Под ред. О.И.Шелухина. - М. : Радиотехника, 2003.-480 с.
86. Широков, В. Л. Разработка моделей и методов для оценки и выбора коэффициентов мультисервисных систем обмена информацией : автореф. дис. ... канд. техн. наук: 05.13.13/ Широков Владимир Леонидович. - М., 2006. - 20 с.
87. Штоян, Д. Качественные свойства и оценки стохастических моделей / Д. Штоян. - М.: Мир, 1979. - 268 с.
88. Шур, Ю. Б., Лесин, Л. М., Гольдштейн, Б. С. Новые технологии для технологических сетей / Ю. Б. Шур, Л. М. Лесин, Б. С. Гольдштейн, // Автоматика, связь и информатика. - 2006. - № 7. - С. 18-20.
89. Якубович, Д. Оптимизация сетевого трафика / Д. Якубович // Сети и системы связи. - 2001. - № 10. - С. 92-97.
90. Яновский, Г. Г. IP Multimedia Subsystem: принципы, стандарты и архитектура / Г. Г. Яновский, М. А. Бонч-Бруевич// Вестник связи. -2006.-№3.-С. 71-76.
91. Adán, I. Stochastic Models for Design and Planning [Электронный ресурс] /1. Adan, 2002. - Режим доступа : http://www.win.tue.nl/~iadan/sdp/.
92. ALGLIB Project [Электронный ресурс]. - Режим доступа : Ьйр://а^ЬЬ.8оигсе8.т/т1ефо1айоп/ро1упогша1.р11р, свободный. - Загл. с экрана.
93. Вохта, О. J. On the longest service time in a busy period of the M/G/l queue / O. J. Boxma // Stochastic Processes and their Applications. - Vol. 8, - 1978. - № 1 - P. 93 -100.
94. Cohen J.W. The single server queue / J.W. Cohen. North Holland Publishing Company, Amsterdam / London. - 1969.
95. Crovella, M., Lipsky, L. Simulations with heavy-tailed workloads. In Kihong Park and Walter Willinger, editors, Self-Similar Network Traffic and Performance Evaluation. Wiley / Wiley Interscience, New York, 1999.
96. Crovella, M., Taqqu, M., Bestavros, A. Heavy-Tailed Probability Distribution in World Wide Web / M. Crovella, M. Taqqu, A. Bestavros // A Practical Guide to Heavy Tails: Statistical techniques and Applications, 1998.
97. Daley, D.J. Bounds on mean waiting times in GI/G/1 queues / D.J. Daley// Z. Wahrscheinlichkeitstheorie verw. Geb. - 1969. - № 10. - P. 305-317.
98. Heyman, D. P., Lakshman, Т. V. Long-range dependence and queueing effects for VBR video. In Kihong Park and Walter Willinger, editors, Self-Similar Network Traffic and Performance Evaluation. Wiley / Wiley Interscience, New York, 1999.
99. Heyman, D. P., Lakshman, Т. V., Source models for VBR broadcastvideo traffic / D. P. Heyman, Т. V. Lakshman // IEEE/ACM Transactions on Networking. - 1996. - Vol. 4. - P. 40-48.
100. Karlen, D. Using projections and correlations to approximate probability distributions / D. Karlen // Comput.Phys. - 1998 - Vol.12. - № 4. - P. 380-384.
101. Kilpi J., Norros I. Testing the Gaussian approximation of aggregate traffic / J. Kilpi, I. Norros // In Proceedings of the 2nd Internet Measurement Workshop. - 2002. - P. 49-61.
102. Kramer W., Langenbach-Belz M. Approximation for the delay in the queueing systems GI/GI/1 // Congressbook, 8-th Internat. Teletraf. Congr., Melbourne, 1976.
103. Leland, W. E. On the self-similar nature of Ethernet traffic / W. E. Leland, M. S Taqqu, W. Willinger, D.V. Wilson // IEEE Transactions of Networking. - 1994. - Vol. 2, № 1. - P. 1 -15.
104. Mathcad [Электронный ресурс]. Режим доступа: http://ru.wikipedia.Org/wiki/Mathcad#Mathcad_14 , свободный. - Загл. с экрана.
105. Math Wave Technologies. Режим доступа: http://www.mathwave.com/easyfit-distribution-fitting.html ,свободный. -Загл. с экрана.
106. Mondragon, R. J. Chaotic maps for traffic modelling and queueing performance analysis Text. / R. J. Mondragon, D. K. Arrowsmith and J. M. Pitts // Performance Evaluation. -Netherlands. - 2001. - P. 223-240.
107. Park K., Willinger W. Self-Similar Network Traffic: An Overview. Self-Similar Network Traffic and Performance Evaluation (ed.), Wiley-Interscience, 2000.
108. Paxson, V. Wide-Area Traffic: The Failure of Poisson Modeling Text. / V. Paxon, S. Floyd // IEEE ACM Transactions on Networking, 3(3). NJ, -June 1995.-P. 226-244.
109. Prony G.R.B. Essai experemenal et analytique: sur les lois de la dilitabilite de fluids elastques et sur celles de la force expansive de la vapeure de l'eau et la vapeure de l'alkool, a différentes temperatures/ G.R.B. Prony //J. de L'Ecole Polytechnique. -1795. - Vol.l. - P. 24-76.
110. Roughan, M., Veitch, D., Abry, P. Real-time estimation of the parameters of long-range dependence / M. Roughan, D. Veitch, P. Abry // IEEE/ACM Transactions on Networking (TON). - 2000. - Vol. 8. - № 4.
111. Ryu, B. K. Point process models for self-similar network traffic, with applications Text. / B.K. Ryu, S.B. Lowen // Stochastic models. - 1998. -P. 1468-1475.
112. Tsybakov, B. Self-similar processes in communications network Text. / B. Tsybakov, N.D. Georganas // IEEE Trans. On Information Theory, № 44(5). - September 1998. - P. 1713-1725.
113. Norros, I. A storage model with self-similar input /1. Norros // Queueing Systems And Their Applications, 16. - 1994. - P. 387-396.
УТВЕРЖДАЮ
Заместитель генерального директора по науке
ОАО «Концерн «Автоматика»,
АКТ
внедрения результатов диссертационной работы Чупахиной Лилии Равилевны на соискание ученой степени кандидата технических наук на тему: «Анализ характеристик систем массового обслуживания при передаче непуассоновского трафика методом аппроксимации функции
Настоящим Актом подтверждается, что основные результаты диссертационного исследования Чупахиной Л.Р. использованы при решении актуальных задач по созданию новых и модернизации существующих систем специальной радиосвязи следующим образом.
Разработанный в рамках диссертационного исследования метод решения интегрального уравнения Линдли, основанный на аппроксимации функций распределения временных характеристик непуассоновского трафика применялся при решении отдельных задач моделирования трафика в рамках работ по обоснованию архитектуры перспективных сетей специальной связи.
Использование результатов диссертационной работы Чупахиной Л.Р. позволило существенно повысить эффективность алгоритма анализа и оптимизации архитектуры сстсй по заданным критериям.
распределения»
Начальник НИО-2, к.т.н.
Заместитель начальника НИО-2
Акт
о внедрении результатов диссертационной работы Чупахиной Л.Р.
«Анализ характеристик систем массового обслуживания при передаче непуассоновского трафика методом аппроксимации функций распределения»
Комиссия ФГОБУ ВПО ПГУТИ в составе: председателя комиссии к.т.н., доц. Кустовой М.Н. - начальника управления организации учебного процесса, и членов комиссии - д.т.н., проф. Карташевского В.Г.. - заведующего кафедрой МСИБ, к.т.н., доц. Пугина В.В. -доцента кафедры МСИБ, составили настоящий акт о том, что в университете внедрены в учебный процесс на кафедре МСИБ следующие результаты диссертационной работы Чупахиной Л.Р.:
1. В курсе лекций по дисциплине «Сетевые технологии высокоскоростной передачи данных» раздел «Особенности обработки разнородного трафика в современных телекоммуникационных сетях».
2. В цикле лабораторных работ по дисциплине «Основы теории массового обслуживания» лабораторная работа «Исследование методов аппроксимации функций распределения вероятностей в системах массового обслуживания».
Председатель комиссии начальник управления организации
учебного процесса, к.т.н., доц.
Кустова М.Н.
Члены комиссии: Заведующий кафедрой МСИБ д.т.н., проф.
Карташевский В.Г.
доцент кафедры МСИБ, к.т.н., доц.
Пугин В.В.
Федеральное агентство связи
Федеральное государственное образовательное бюджетное учреждение высшего
профессионального образования ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
На правах рукописи
Чупахина Лилия Равилевна
АНАЛИЗ ХАРАКТЕРИСТИК СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ ПРИ ПЕРЕДАЧЕ НЕПУАССОНОВСКОГО ТРАФИКА МЕТОДОМ АППРОКСИМАЦИИ ФУНКЦИЙ
РАСПРЕДЕЛЕНИЯ
Специальность 05.12.13 - Системы, сети и устройства телекоммуникаций
Диссертация на соискание учёной степени кандидата технических наук
Научный руководитель: Кандидат технических наук, доцент Киреева Н.В.
Самара - 2013
СОДЕРЖАНИЕ
Перечень сокращений................................................................................................................................4
Введение....................................................................................................................................................................6
Глава 1. Мультисервисные сети, основные понятия..............................................................12
1.1. Общая характеристика системы массового обслуживания....................15
1.2. Структура и классификации систем массового обслуживания................16
1.3. Поток событий. Простейший поток и его свойства..........................................19
1.4. Дисциплина обслуживания......................................................................................................20
1.5. Модели систем массового обслуживания....................................................................20
1.5.1 Простейшие случаи систем массового обслуживания..........................22
1.6. Аппроксимация функций распределений, методы аппроксимации.. 26 Выводы по главе 1......................................................................................................................................30
Глава 2. Исследование функций плотности распределения
вероятностей........................................................................................................................................................32
2.1 Кумулянтный анализ........................................................................................................................35
2.1.1 Аппроксимация функций плотности распределения
вероятностей с помощью ряда Эджворта..............................................................................37
2.2 Метод Прони........................................................................................................................................56
2.2.1 Алгоритм аппроксимации функции плотности распределения
с помощью метода Прони............................................................................................................................58
Выводы по главе 2....................................................................................................................................66
Глава 3. Аппроксимация функций распределения вероятностей........................68
3.1. Метод аппроксимации функции плотности распределения вероятностей с «тяжелым» хвостом суммами экспонент............................................68
3.1.1 Алгоритм аппроксимации функции плотности распределения
вероятностей суммами экспонент................................................................................................70
3.2. Метод аппроксимации произвольной функции плотности
распределения вероятностей суммами экспонент........................................................81
Выводы по главе 3......................................................................................................................................99
Глава 4. Интегральное уравнение Линдли....................................................................................101
4.1 Решение интегрального уравнения Линдли..............................................................103
4.2 Решение интегрального уравнения Линдли для системы массового обслуживания типа G/G/1......................................................................................................................107
4.3 Решение интегрального уравнения Линдли для системы массового
обслуживания типа G/G/1 для частных случаев..............................................................109
Выводы по главе 4......................................................................................................................................119
Заключение................................................................................................................................................................120
Список использованных источников..................................................................................................121
Акты внедрения......................................................................................................................................................133
Перечень основных сокращений
ИУ - интегральное уравнение
МНК - метод наименьших квадратов
МСС - мультисервисная сеть связи
ОУ - обрабатывающее устройство
РТХ - распределение с «тяжелыми хвостами»
СЛАУ - система линейных алгебраических уравнений
СМО - система массового обслуживания
ТМО - теория массового обслуживания
FIFO (first-in, first-out) - алгоритм обработки очередей - «первый пришёл -первый вышел»
G/G/1 - СМО с одной обслуживающей линией, произвольным входящим потоком, произвольным распределением времени обслуживания
G/G/n - СМО с п обслуживающими линиями, интервалы времени между пакетами распределены произвольно, произвольным распределением времени обслуживания
G/M/1 - СМО с одной обслуживающей линией, интервалы времени между пакетами распределены произвольно, время обслуживания распределено экспоненциально
GOF (Goodness of fit) - критерий согласия
IPTV (Internet Protocol Television) - интерактивное телевидение LIFO (last-in, first-out) - алгоритм обработки очередей - «последний пришёл —первый вышел»
M/D/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, детерминированным распределением времени обслуживания
M/G/1 - СМО с одной обслуживающей линией, пуассоновским входящим потоком, произвольным распределением времени обслуживания
M/M/l - СМО с одной обслуживающей линией, пуассоновским входящим потоком, экспоненциальным распределением времени обслуживания
MLE (maximum-likelihood estimation) - Метод максимального правдоподобия
NGN (Next Generation Network ) - сети следующего поколения
QoS (Quality of Service) - качество обслуживания
Введение
Современные телекоммуникационные системы характеризуются значительной сложностью происходящих в них процессов. Марковская классическая модель системы массового обслуживания (СМО) [11, 40, 41, 87] не может полностью описать параметры современных телекоммуникационных систем, что в свою очередь порождает серьезную недооценку реальной нагрузки и значительное ухудшению качества обслуживания (С^оБ) при реализации услуг разного вида. Стандартные методы моделирования СМО для анализа и прогнозирования процессов, происходящих в обслуживающем устройстве, зачастую приводят к неудовлетворительным оценкам результатов его работы. Следовательно, непуассоновский характер трафика современной телекоммуникационной системы требует применения новых математических методов его исследования.
Бурное развитие мультисервисных сетей связи (МСС), которые определенным образом характеризуют структуру и поведение пакетов в ней, рост объема передаваемой информации, привели к новому восприятию современной телекоммуникационной инфраструктуры. В связи с этим построение моделей МСС и их исследование от частного случая к общему, является актуальной задачей, и в настоящее время привлекают внимание многих исследователей [4, 5, 6, 28, 43, 49, 90, 97, 102, 106, 108, 110].
В последнее время все больше исследований посвящается вопросу анализа непуассоновского трафика МСС, обладающего самоподобием [37, 40, 51, 54, 73, 103]. Математическая теория самоподобных процессов изучена довольно хорошо, однако практическая реализация все еще оставляет ряд нерешенных вопросов, особенно при передаче информационного потока в МСС. Существует большое количество исследований, посвященных имитационному моделированию работы сетевого устройства при передаче самоподобного потока. Однако теоретическая база процесса передачи
информации в основном применима только для некоторого рассматриваемого коммуникационного оборудования. Алгоритмы прогнозирования и методы мониторинга для анализа трафика МСС важны и интересны как с точки зрения использования при проектировании, так и на практике, например во время большой загрузки системы на сети оператора связи.
В силу непуассоновского характера поведения реального трафика в качестве модели целесообразнее использовать СМО типа G/G/l (G/G/n), так как на практике, при исследовании реальных систем, редко бывают, известны законы распределения и обслуживания поступающего на вход системы трафика.
Существенный вклад в решение задач анализа и проектирования сетей внесли российские ученые Б. С. Цыбаков, В. И. Нейман, В. М. Вишневский, С. Н. Степанов, О. И. Шелухин, Г. П. Башарин, А. Е. Кучерявый, К. Е. Самуйлов, Г. Г. Яновский и др., а также зарубежные ученые К. Park, W. Willinger, P. Abry, M. S. Taqqu, I. Norros и др. исследователи.
На данный момент анализ СМО типа G/G/1 не решен, с точки зрения того, чтобы можно было описать эту систему с помощью любого математического аппарата, либо любого другого программно-аппаратного комплекса для решения данной задачи.
Чтобы управлять всплесками трафика, необходимо решить задачу определения функции плотности вероятности распределения интенсивностей. В случае произвольных потоков расчет средних значений характеристик обслуживания заявок обычно проводится на основе аппроксимации закона распределения интервалов времени между пакетами в потоке и распределения длительности обслуживания пакетов.
Методы для расчета характеристик звена при поступлении непуассоновского трафика пока мало изучены, что очередной раз доказывает актуальность темы диссертации.
Содержание диссертации соответствует пунктам 4 и 14 паспорта специальности 05.12.13 - «Исследование путей совершенствования управления информационными потоками», «Разработка методов исследования, моделирования и проектирования сетей, систем и устройств телекоммуникаций».
Цель и задачи работы. Целью диссертационной работы является анализ характеристик СМО при обработке непуассоновского трафика МСС на основе аппроксимации законов распределения интервалов времени между пакетами и длительностей обслуживания пакетов.
Для достижения поставленной цели в диссертационной работе были сформулированы и решены следующие основные задачи:
— исследование математических моделей, описывающих непуассоновский трафик МСС и не марковский характер обслуживания;
— использование методов аппроксимации для моделирования плотностей распределения вероятностей интервалов времени между поступлениями пакетов и распределения вероятностей длительностей обслуживания пакетов, с учетом самоподобных свойств процессов поступления и обслуживания;
— разработка метода аппроксимации функций плотностей распределения суммой затухающих экспонент;
— анализ функций распределений с «тяжелыми хвостами» (РТХ) для получения аппроксимирующих выражений в виде суммы затухающих экспонент;
— анализ статистических данных, собранных с реальной сети, построение моделей функций плотностей распределения интервалов времени между пакетами и длительности обслуживания пакетов;
— разработка алгоритма решения интегрального уравнения (ИУ) Линдли для СМО типа вЛл/! с помощью спектрального метода.
Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов математического анализа, математической статистики, теории вероятностей, статистической обработки данных и вычислительных методов, реализованных в пакете Matlab и Matead.
Научная новизна исследований, проведенных в диссертации, состоит в следующем:
— разработан метод аппроксимации гиперэкспоненциальных функций плотности распределения вероятностей суммой затухающих экспонент для анализа входящего и обслуживаемого трафика МСС;
— получена аппроксимация функций плотности распределения вероятностей для реального входящего и обслуживаемого в узле МСС трафика;
— получено решение ИУ Линдли для СМО типа G/G/1 для гиперэкспоненциальных распределений.
Практическая ценность диссертации.
Полученный в данной работе метод решения ИУ Линдли позволяет использовать в качестве математической модели СМО типа G/G/1. На основе разработанных методов аппроксимации можно проанализировать работу СМО типа G/G/1 спектральным методом.
Результаты работы внедрены в ОАО «Концерн «Автоматика», в курсах «Основы теории массового обслуживания», «Сетевые технологии высокоскоростной передачи данных» ФГОБУ ВПО ПГУТИ, что подтверждается актами внедрения.
Основные положения и результаты, выносимые на защиту:
— последовательности интервалов времени между пакетами и длительностей пакетов для трафика МСС обладают свойством самоподобия и могут быть описаны РТХ;
— аппроксимацию распределений вероятностей характеристик реального трафика целесообразно проводить с использованием методов кумулянтного анализа;
— используемые РТХ могут быть аппроксимированы суммой затухающих экспонент, при условии, что коэффициенты аппроксимации должны быть вещественными и отрицательными при положительных значениях аргумента;
— для решения ИУ Линдли при применении предложенных методов аппроксимации может быть использован алгоритмически простой спектральный метод.
Личный вклад автора. Все основные научные результаты, теоретических и прикладных исследований, выводы, изложенные в диссертации, получены автором самостоятельно. В работах, опубликованных в соавторстве, соискателю принадлежит часть, связанная с постановкой задач и проведением экспериментальных исследований.
Обоснованность и достоверность результатов работы. Обоснованность и достоверность результатов обеспечиваются адекватной постановкой задач, решаемых в диссертационной работе; корректностью использования математического аппарата. Достоверность результатов подтверждается экспериментальными данными, полученными в процессе исследования и анализа трафика МСС.
Внедрение результатов работы. Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» г. Москва и в учебный процесс кафедры «Мультисервисных сетей и информационной безопасности» ФГОБУ ВПО ПГУТИ, что подтверждено актами внедрения.
Апробация работы. Основные научные и практические результаты диссертации докладывались и обсуждались на 7-й Отраслевой научно-технической конференции-форуме «Технологии информационного общества», (г. Москва, 2013), на XII, XIII Международной научно-
технической конференции «Проблемы техники и технологий телекоммуникаций» (г. Уфа, 2010, г. Казань, 2011), на 14-й и 15-й Международной Конференции «Цифровая обработка сигналов и ее применение» (г. Москва, 2012-2013 гг.), на XXXIX Международной научно-практической конференции «Физико-математические и технические науки как постиндустриальный фундамент эволюции информационного общества», (г. Лондон, 2013), на X Международная научно-техническая конференция «Физика и технические приложения волновых процессов» (г. Самара, 2011), на Международной научно-практической Интернет-конференции «Современные направления теоретических и прикладных исследований'2013», (г. Одесса, 2013), на Международной научно-практической Интернет-конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании'2013», (г. Одесса, 2013), на Всероссийской научно-практической конференции «Проблемы передачи информации в инфокоммуникационных системах» (г. Волгоград, 2013), на Первой Международной научно-практической конференции «Проблемы инфокоммуникаций. Наука и технологии» (Р1С8&Т-2013) (г. Харьков, 2013), на XVII, XVIII, XIX, XX Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов (ФГОБУ ВПО ПГУТИ, г. Самара, 2010-2013 гг.).
Публикации результатов. По результатам исследования опубликовано 18 печатных работ, 4 из них в изданиях из перечня ВАК, 9 публикаций международных научных конференций, 5 тезисов докладов.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 134 страниц машинописного текста, 100 рисунков, 23 таблицы. В списке литературы 113 наименований.
Глава 1. Мультисервисные сети, основные понятия
Появление новых сетевых технологий привело к появлению новых терминов, обеспечивающих: мультимедиа телекоммуникации, услуги широкополосного доступа, услуги с гарантией времени доставки трафика и т.п. [30].
В современной телекоммуникационной сети прослеживается конвергенция различных услуг и видов трафика, объединение их в единую
мсс.
Мультисервиная сеть - это единая телекоммуникационная инфраструктура для переноса трафика произвольного типа, порождаемого взаимодействием потребителей и поставщиков услуг связи с контролируемыми и гарантированными параметрами трафика, уровня качества и конфиденциальности, свойственными каждому виду услуг [30].
Основные услуги, предоставляемые МСС:
— передача традиционного телефонного трафика;
— передача трафика данных (например, данных Интернет);
— передача трафика данных корпоративной сети;
— передача трафика мобильных сетей;
— доступ в Интернет;
— доступ к сетям передачи данных.
Одним из математических методов исследования сложных телекоммуникационных систем является ТМО, занимающаяся анализом эффективности функционирования СМО [82].
Система массового обслуживания - динамическая система, предназначенная для эффективного обслуживания случайного потока заявок при ограниченных ресурсах сети. Случайных характер поступления заявок и случайных характер промежутков времени подразумевает, что СМО работает
по определенной дисциплине ожидания и обслуживания поступившего на вход системы требования [82].
При исследовании МСС лучше рассматривать основной элемент системы - узел (канал, линия связи). Свойства узла МСС можно описать моделями элементарных СМО, например, взяв за основу классическую марковскую теорию. А ТМО используется как математический аппарат для исследования и установления взаимосвязи между характеристиками потока пакетов, числом каналов, их производительностью [82]. Поэтому как объект исследования целесообразно рассматривать узел МСС, канальный ресурс которой используется п потоками сообщений [49].
Исследуя МСС, необходимо помнить, что концепция развития сетей следующего поколения (NGN) подразумевает предоставление неограниченного набора услуг с заданными характеристиками качества. Сети строятся на основе пакетных технологий. Проектирование современной сети связи подразумевает обслуживание трафика различных коммуникационных приложений (речь, видео, данные) [17, 73]. Структурная схема исследуемой
МСС представлена на рис. 1.1. fi,, v
Рис. 1.1. Структурная схема: 1 - поток управляющей информации, 2 — поток голосовых сообщений, 3 - поток видеоинформации, 4 - поток данных, 5 - узел МСС, 6 - МСС
Перечислим требования, которым должна удовлетворять МСС:
— гарантированное (^оБ пользователей;
— доставка информации, чувствительной к задержке, в реальном
масштабе времени;
— обеспечение передачи данных с требуемой скоростью;
— централизованное управление сетью.
Информационные потоки, передаваемые по линии связи, по своим свойствам значительно отличаются от потоков речевых сообщений. Поэтому применение методов анализа и оценки характеристик сети, развитых в классической теории телетрафика, нужно использовать с рядом оговорок, и в некоторых случаях неприемлемы.
В работах [43, 52, 64, 81, 86, 89] отмечено, что повсеместное развитие МСС сдерживает один недостаток сетей с коммутацией пакетов - плохая приспособленность к передаче трафика реального времени. Множество работ [13, 15, 16, 22, 28, 30, 43, 50, 88] посвящено обеспечению должного (^оБ, так как существует проблема чувствительности параметров трафика при передаче в реальном времени (видеоконференцсвязь, 1РТУ и др.).
Постоянное развитие и модернизация телекоммуникационных сетей определяется тремя факторами: ростом трафика, потребностью общества в новых услугах и достижениями в области технологий. Данные факторы не являются независимыми, однако каждый из них определяет идеологию развития электросвязи. Достижение рынка современной телекоммуникационной системы и конкуренция среди поставщиков оборудования ведет к снижению стоимости оборудования и стимулированию роста трафика, разработке новых услуг [73, 74].
Исследуемая математическая модель должна представлять собой МСС, и иметь свойства и параметры близкие к реальной телекоммуникационной сети связи.
Современные методы и модели анализа производительности компьютерных сетей явно можно разделить на два направления: аналитическое вероятностное моделирование на основе ТМО и имитационное (дискретно-событийное) моделирование. Методы первого направления, основанные на последних результатах ТМО, ограничиваются только пуассоновскими потоками в сетях СМО типа М/М/1, М/Е)/1, МЛл/1 и др. [2, 6, 8, 67,91,93,94].
Ограниченность пуассоновских моделей подтверждают публикации о самоподобных процессах как моделях трафика с РТХ [6, 112,113, 84, 85, 95, 96, 103]. В этих работах утверждается, что трафик МСС не может адекватно описываться пуассоновскими моделями, так как они приводят к слишком оптимистичным результатам по задержкам [6].
1.1 Общая характеристика системы массового обслуживания
Характерным для описания процессов передачи данных пакетным трафиком являются обнаруженные на практике свойства самоподобия или масштабной инвариантности статистических характеристик. В современной научной литературе эти свойства связывают с особым классом физических процессов - фрактальными процессами. В связи с этим, разработка новых сетевых технологий и повышение эффективности работы современных телекоммуникационных систем требует создания математических моделей, наиболее полно отражающих отмеченные свойства сетевых процессов [29].
Для случая самоподобного трафика методов расчета характеристик С)о8 неизвестно. Причиной этому является непредсказуемость самоподобных потоков, вследствие чего и невозможно получить аналитически обоснованные результаты для характеристик СМО, в которых обслуживаются данные потоки. Несмотря на популярность модели самоподобного трафика, до сих пор ряд задач оценки С>о8 СМО остается
нерешенными. В частности, из-за отсутствия строгой теоретической базы, способной дополнить классическую ТМО при проектировании СМО с самоподобным трафиком, не существует достоверной и признанной методики расчета параметров и показателей качества систем распределения информации в условиях «пачечного» эффекта. Очевиден и тот факт, что на характеристики (^о8 влияют и вероятностные законы распределения длительности обслуживания [54]. Поэтому вопросы исследования трафика с непуассоновкими функциями распределениями вероятностей длительностей поступления и обслуживания остается актуальным.
1.2 Структура и классификации систем массового обслуживания
Структуру простейшей СМО можно представить в виде (рис.1.2.):
Рис. 1.2. Структура простейшей СМО: И - источник пакетов, Я -накопитель (буфер), К ■ - у -й канал обслуживания
В современной технической литературе для описания сложных СМО используется классификация Кендалла-Башарина, основанная на пяти символах А! В / т / К / N, где А - обозначает распределение интервалов во входном потоке, В - распределение времени обслуживания, т— число обслуживающих приборов в системе (каналов, линий), К — число мест в накопителе, N — количество источников нагрузки. Символы А и В могут принимать следующие значения: М- экспоненциальное распределение,
Ек - распределение Эрланга, И - детерминированная величина, -
произвольное распределение [42, 75].
Для СМО разработана стандартная классификация за разными признаками, среди которых наиболее важными являются:
— структура системы;
— функция распределения вероятностей потоков требований, которые поступают в системе;
— функция распределения вероятностей времени обслуживания, порядок (дисциплина) обслуживания;
— допустимая длина очереди перед обслуживающими приборами. Любая система характеризуется своей структурой, то есть составом ее
основных частей и функциональными связками между ними. Основной частью для СМО такими являются обслуживающие приборы (каналы). Если система содержит только один канал, такая система называется одноканальной. Если система имеет несколько каналов, предназначенных для одновременного (параллельного) обслуживания требований, которые поступают в систему, то ее называют многоканальной.
Для анализа процесса обслуживания потоков требований необходимо учитывать характеристики узла МСС и поведения системы в различных случаях: перегрузка системы, резервное или аварийное обслуживание.
Рассматривая МСС от одной системы к целой совокупности систем, на основе модели СМО, упрощает громоздкость вычислений, позволяет расширить и более детально изучить происходящие процессы. СМО делятся на типы (или классы) по ряду признаков. Первое деление: СМО с отказами и СМО с очередью. В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует. Примеры СМО с отказами встречаются в телефонии: заявка на разговор, пришедшая в момент, когда все каналы связи заняты, получает отказ и
покидает СМО необслуженной. В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной. На практике чаще встречаются (и имеют большее значение) СМО с очередью [61].
В свою очередь, СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь - ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания.
При анализе СМО должна учитываться также и «дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления, либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом - некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным - когда заявка с более высоким приоритетом «вытесняет» с обслуживания заявку с низшим, так и относительным - когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди [61].
Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок Я,, производительность каждого канала (среднее число заявок, обслуживаемых непрерывно занятым каналом в единицу времени), условия образования очереди (ограничения, если они есть). Следует отметить, что существуют СМО с многофазовым обслуживанием, состоящим из нескольких последовательных этапов, которые тоже представляют большой интерес в исследовательской работе [61].
При этом физическая модель должна быть составлена, таким образом, чтобы (^оБ оставалось в допустимых пределах. Ее алгоритм и полученные в результате исследований параметры должны удовлетворять заданным
условиям работы обслуживающего устройства (ОУ) и позволять получить значения в пределах допустимой погрешности.
ТМО получила широкое применение в современной жизни общества, начиная с бытового обслуживания до космических исследований, так как позволяет строить необходимую модель и учитывать различные необходимые требования. Однако все-таки определяющую роль в развитии ТМО продолжает играть одна из ее ветвей теория телетрафика.
1.3 Поток событий. Простейший поток и его свойства
При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто бывает удобно представить себе процесс так, как будто переходы системы из состояния в состояние происходят под действием каких-то потоков событий.
Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то, вообще говоря, случайные моменты времени. Положение каждой точки на оси случайно.
1. Поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени, что редко встречается на практике.
2. Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной т зависит только от длины участка и не зависит от того, где именно на оси времени расположен этот участок (однородность по времени) -вероятностные характеристики такого потока не должны меняться от времени. В частности, так называемая интенсивность (или плотность) потока событий (среднее число событий в единицу времени) постоянна.
3. Поток событий называется потоком без последствия, если для любых непересекающихся участков времени число событий, попадающих на один из
них, не зависит от того, сколько событий попало на другой (или другие, если рассматривается больше двух участков). Отсутствие последствия в потоке означает, что события, образующие поток, появляются в последовательные моменты времени независимо друг от друга.
4. Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежительно мала по сравнению с вероятностью попадания одного события (события в потоке приходят поодиночке, а не парами, тройками и т.д.).
Поток событий, обладающий всеми тремя свойствами, называется простейшим (или стационарным пуассоновским). Нестационарный пуассоновский поток обладает только свойствами 2 и 3 [24, 40, 41, 70, 72].
1.4 Дисциплина обслуживания
Дисциплиной обслуживания называется правило, по которому выбираются на обслуживание требования из очереди. Различают следующие виды дисциплин обслуживания:
— обслуживание в порядке поступления или дисциплина FIFO (First Input, First Output — первым пришел, первым ушел);
— обслуживание в обратном порядке или дисциплина LIFO (Last Input, First Output — последним пришел, первым ушел);
— обслуживание в случайном порядке, когда заявка на обслуживание выбирается случайно среди ожидающих заявок.
1.5 Модели систем массового обслуживания
СМО можно представить моделью. Математическая модель системы распределения информации включает следующие три основных элемента:
входящий поток заявок (требований на обслуживание), схему системы распределения информации, дисциплину обслуживания потока заявок.
Среди аналитических вероятностных математических моделей систем одним из наиболее востребованных классов является класс непрерывно-стохастических моделей. Эти модели характерны для ТМО, рассматривающей абстрактные процессы обслуживания требований, которые помимо всего прочего могут образовывать очереди [39].
В моделях СМО рассматривают следующие объекты:
— требования на обслуживание (транзакты);
— обслуживающие приборы.
Практическая задача ТМО связана с исследованием операций этими объектами и состоит из отдельных элементов, на которые влияют случайные факторы [39].
Модели СМО используются для исследования процессов, происходящих в системе, при подаче на входы потоков требований, данные процессы представляют собой последовательность событий [39].
Одними из важных свойств являются выходные параметры сети:
— производительность;
— пропускная способность;
— вероятность отказа в обслуживании;
— среднее время обслуживания;
— коэффициент загрузки.
Нужно заметить, что параметры заявок, поступающих на обслуживание, являются случайными величинами, и при исследовании или проектировании могут быть известны только функции распределения вероятностей.
В связи с этим анализ систем сводится к статистическому исследованию. В качестве математического аппарата моделирования удобно принять ТМО, а в качестве моделей систем использовать СМО [39].
Таким образом, для описания СМО необходимо задать:
1. Функцию распределения вероятностей А(т) интервалов времени между пакетами или длительности поступления т1.
2. Функцию распределения вероятностей В(<^) длительности обслуживания (общий случай) или длительности обслуживания ^.
3. Дисциплина обслуживания.
1.5.1 Простейшие случаи систем массового обслуживания
Рассмотрим различные модели простейших СМО.
з
Рис. 1.3. Модель СМО с отказами: И - источник пакетов; ОУ - обслуживающее устройство; 1 - входной поток; 2 - выходной поток; 3 - поток не обслуженных пакетов
В этой модели (рис. 1.3.) отсутствует накопитель заявок на входе ОУ. Если заявка приходит от источника в момент времени, когда ОУ занят обслуживанием предыдущей заявки, то вновь прибывшая заявка выходит из системы и теряется.
и
2
И
Рис. 1.4. Модель СМО с ожиданием: И - источник пакетов; Н - накопитель (буфер); ОУ - обслуживающее устройство; 1 - входной поток; ^ -I) - количество заявок, которые могут
В этой модели (рис. 1.4.) имеется накопитель заявок на входе ОУ. Если заявка приходит от источника в момент времени, когда ОУ занят обслуживанием предыдущей заявки, то вновь пришедшая заявка попадает в накопитель, где неограниченно долго ожидает, пока освободится ОУ.
И - источник пакетов; Н — накопитель (буфер); ОУ -обслуживающее устройство; 1 - входной поток; ^ - поток заявок, покидающих систему при превышении времени ожидания; (ТУ -1) - количество заявок, которые могут поместиться в накопителе;
2 - выходной поток
В этой модели (рис. 1.5.) имеется накопитель заявок на входе ОУ, но время нахождения заявки в накопителе ограничено некоторой величиной.
И — источник пакетов; ОУ - обслуживающее устройство;
1 - входной поток; 2 - выходной поток
В этой модели (рис. 1.6.) имеется не один ОУ, а несколько. Заявки могут поступать к любому свободному ОУ. Накопителя нет, поэтому отказ в обслуживании заявки означает ее безвозвратную потерю, и т — количество одинаковых ОУ.
и
Рис. 1.7. Многоканальная модель СМО с ограниченным временем ожидания: И - источник пакетов; Н - накопитель (буфер); ОУ - обслуживающее устройство (т- количество одинаковых ОУ)\ 1 - входной поток; d - поток заявок, покидающих систему при превышении времени ожидания; {N -1) - количество заявок, которые могут поместиться в накопителе; 2 - выходной поток
Модель СМО, представленная на рис. 1.7., объединяет свойства моделей представленных выше.
Рис. 1.8. Многоканальная модель СМО с ожиданием и восстановлением: И - источник пакетов; Н — накопитель (буфер); ОУ - обслуживающее устройство (т- количество одинаковых ОУ); 1 - входной поток; d — поток заявок, покидающих систему при превышении времени ожидания; ^ -1) - количество заявок, которые могут поместиться в накопителе; РБ — ремонтный блок; / - ОУ, вышедшие из строя; с — восстановленные ОУ; 2 — выходной поток
Данная модель (рис. 1.8.) позволяет учитывать возможные случайные отказы ОУ, которые поступают на РБ, где пребывают в течение случайных промежутков времени, затрачиваемых на их восстановление, а затем вновь возвращаются в ОУ.
Рис. 1.9. Многоканальная модель СМО с ограниченным временем ожидания и восстановления: И - источник пакетов; Н — накопитель (буфер); ОУ - обслуживающее устройство (т - количество одинаковых
ОУ); 1 - входной поток; (ТУ -1) - количество заявок, которые могут поместиться в накопителе; РБ - ремонтный блок; / - ОУ, вышедшие из строя; с - восстановленные ОУ; 2 - выходной поток
Данная модель (рис. 1.9.) является сложной, потому что объединяет в себе свойства вышеупомянутых моделей.
Наиболее изученной является простейшая модель СМО типа М/М/1 с простейшим потоком на входе и экспоненциально распределенной длительностью обслуживания заявок в приборе (один). Для данной системы определены функции распределения вероятностей и характеристики сети в явном аналитическом виде [12, 25, 36, 40, 41, 47, 48, 53, 65, 72, 78].
Модели СМО типа М/О/1 и О/М/1 также исследованы в работах [26, 40, 41], где в вместо произвольного распределения взяты детерминированное, гиперэкспоненциальное и РТХ, получены соответствующие результаты. Однако применение данного типа СМО к исследованию реальной сети не
и
всегда является возможным в силу самоподобного характера трафика и неограниченности сетевых ресурсов ОУ или буфера.
1.6 Аппроксимация функций распределений, методы аппроксимации
В работах [63, 84, 85, 98, 99, 107, 111] показано, что исследование данной проблемы представляется важным, поскольку при наличии самоподобного трафика в системах передачи QoS, как правило, ухудшается по сравнению с тем, что наблюдалось бы, например, в случае пуассоновского трафика.
При решении задач в современных телекоммуникационных сетях трафик МСС описывается с помощью РТХ, которые приводят к самоподобным процессам [63, 84]. Выбирая часто встречающиеся РТХ Вейбулла, Парето, логнормальное, можно смоделировать в качестве СМО типа G/G/1, наиболее адекватно описывающую работу любого сетевого элемента, обрабатывающего самоподобный трафик. Если доказать и получить, необходимое решение и представление с помощью алгоритмов функций плотностей распределения вероятностей длительностей поступления и обслуживания, можно исследовать характеристики реального трафика.
Поэтому одной из целей исследования является аппроксимация неизвестной функции плотности распределения вероятностей, описывающей закон длительности поступления пакетов и обслуживания в узле МСС. Поиск метода аппроксимации функции, приближающая кривая которой полностью будет удовлетворять и описывать с наименьшей погрешностью фиксированные параметры трафика МСС, является актуальной задачей.
Аппроксимация, или приближение — научный метод, состоящий в замене одних объектов другими, в том или ином смысле близкими к
исходным, но более простыми. Иными словами, аппроксимация некоторой функции у = /(х) заключается в замене другой функцией g(x,a0,al,...,an)
так, чтобы отклонение g от /(х) удовлетворяло в некоторой области (на множестве X) определенному условию [3].
Важным является построение математической модели, удовлетворяющей гипотетической модели, то есть выяснение вопроса о том, согласуются ли результаты наблюдений с теоретическими следствиями модели в пределах точности наблюдений.
Условно аппроксимации можно разделить на два вида [27]:
— строгая теория математической аппроксимации;
— физическая (техническая) аппроксимация.
Строгая теория математической аппроксимации включает следующие методы аппроксимации [14, 27, 20, 34, 45]:
— полиномами (многочленами);
— сплайнами;
— отрезками ряда Фурье;
— полиномами по ортогональным многочленам;
— собственными функциями краевых задач. Полиномиальная интерполяция является наиболее известным из
методов одномерной интерполяции. Её достоинствами являются простота реализации и хорошее качество получаемых интерполянтов. Впрочем, она не лишена недостатков, и в последнее время испытывает сильное давление со стороны альтернативных методов интерполяции: сплайнов и рациональных функций. Но, несмотря на это, полиномиальная интерполяция по-прежнему остается одним из главных инструментов численного анализа [92].
В основе сплайн-интерполяции лежит следующий принцип. Интервал интерполяции разбивается на небольшие отрезки, на каждом из которых функция задается полиномом третьей степени. Коэффициенты полинома
подбираются таким образом, чтобы выполнялись определенные условия (какие именно, зависит от способа интерполяции). Основными достоинствами сплайн-интерполяции являются её устойчивость и малая трудоемкость. Системы линейных уравнений, которые требуется решать для построения сплайнов, очень хорошо обусловлены, что позволяет получать коэффициенты полиномов с высокой точностью [92].
Аппроксимация отрезками ряда Фурье подразумевает вычисление функций, которые представляются посредством разложения в ряд Фурье. При каждом конкретном количестве отсчетов и конкретном числе элементов базиса как функцию можно рассматривать любую разновидность преобразования Фурье. Вычисление функций, непосредственно представимых рядом Фурье, возникает при построении математических моделей объектов управления, при этом большое внимание уделяется определению их динамических и вероятностных характеристик [33, 77].
Одними из широко распространенных специальных функций являются ортогональные многочлены (полиномы), такие как полином Чебышева, полином Эрмита, полином Лежандра и др. Все ортогональные полиномы имеют простые рекуррентные представления. Поэтому приведенные выше функции вычисляются по ним довольно быстро и точно. Они находят широкое применение в технике интерполяции и аппроксимации функций [66].
Как сказано в работе [20, 27], приближение функций с помощью полиномов получило развитие в силу хорошего приближения к искомой функции, а в дальнейшем было выявлено, что для ряда периодических функций наилучшее приближение достигается аппроксимация тригонометрическими полиномами.
Также в работе [27] указано, что с помощью аппроксимации оперативно решается широкий круг задач, актуальных на данный момент
времени, связанных с конкретными проблемами и вопросами прикладного (технического) характера.
Экспериментальные данные, представленные в форме1 таблиц и графиков, оказывается неудобным, и данные стремятся описать с помощью достаточно простых аналитических соотношений, хотя бы качественно отражающих характер рассматриваемых зависимостей [27]. В данном случае необходимо решить задачу аппроксимации, т.е. заменить сложную функцию (построенную по экспериментальным данным) приближенными аналитическими выражениями.
Таким образом, если исследование должно проводиться не численными, а аналитическими методами, то требуется подобрать такую аппроксимирующую функцию, которая, будучи довольно простой, отражала бы все важнейшие особенности экспериментально снятой характеристики с достаточной степенью точности [4, 27].
В радиотехнике для аппроксимации характеристики наиболее часто используют следующие функции [4, 27, 35, 71]:
— степенной полином (степенная или полиномиальная аппроксимация);
— экспоненциальный полином (частным случаем которого является показательная или экспоненциальная аппроксимация);
— кусочно-линейная функция (аппроксимация);
— кусочно-нелинейная функция (аппроксимация);
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.