Приложения теории массового обслуживания. Учебник для студентов высших учебных заведений, обучаемых по направлениею
 Скачать 1.27 Mb.
|
|
Министерство образования и науки, молодежи и спорта Украины ОДЕССКАЯ НАЦИОНАЛЬНАЯ АКАДЕМИЯ СВЯЗИ им. А.С. ПОПОВА А. Г. Ложковский ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ В ТЕЛЕКОММУНИКАЦИЯХ Учебник Утвержден Министерством транспорта и связи Украины как учебник для студентов высших учебных заведений, обучаемых по направлениею „Телекоммуникации” Одесса – 2012 2 План УМИ 2012 г. УДК 621.39 ББК 32.81 Л71 Утверждено Министерством транспорта и связи Украины (Письмо № 6778/23/14-08 от 22.09.2008 г.) Рецензент – Захарченко Н. В. Ложковский А.Г. Л71 Теория массового обслуживания в телекоммуникациях: учебник / А.Г. Ложковский. – Одесса: ОНАС им. А. С. Попова, 2012. – 112 с.: ил. ISBN 978-966-7595-43-3 Изложены основные положения и методы анализа теории массового обслуживания в телекоммуникациях (теории телетрафика), на которых базируются процедуры проектирования телекоммуникационных систем и сетей. Рассмотрены математические модели систем распределения информации с потерями, с очередью и с приоритетами. Приведены исследовательские приемы этих систем в условиях идеализированной модели пуассоновского потока и реальных потоков требований мультисервисных сетей связи. Учебник предназначен для студентов и аспирантов, обучаемых по направлению „Телекоммуникации”, а также для специалистов, занимающихся практическим применением теории телетрафика. РЕКОМЕНДОВАН к изданию ученым советом ОНАС им. А. С. Попова. Протокол №10 от 30 мая 2008 г. ISBN 978-966-7595-43-3 © Ложковский А.Г., 2010 (укр) © Ложковский А.Г., 2012 (рус) 3 СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ .................................................................................................... 5 1 ЭЛЕМЕНТЫ ТЕОРИИ ВЕРОЯТНОСТЕЙ .................................................... 9 1.1 Случайные величины и вероятностные распределения................................ 9 1.2 Математическое ожидание и моменты распределения............................... 11 2 ОБЩИЕ ПОЛОЖЕНИЯ ТЕОРИИ ТЕЛЕТРАФИКА ................................. 13 3 МОДЕЛИ СИСТЕМ РАСПРЕДЕЛЕНИЯ ИНФОРМАЦИИ...................... 16 4 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ПОТОКА ТРЕБОВАНИЙ .................... 20 5 НАГРУЗКА И ЕЁ ВИДЫ ................................................................................. 24 5.1 Определение и интенсивность нагрузки...................................................... 24 5.2 Дисперсия и скученность нагрузки.............................................................. 27 6 ХАРАКТЕРИСТИКИ КАЧЕСТВА ОБСЛУЖИВАНИЯ ............................ 28 6.1 Системы с потерями...................................................................................... 28 6.2 Системы с очередями.................................................................................... 29 6.3 Комбинированные системы (с очередями и потерями) .............................. 30 6.4 Приоритетные системы................................................................................. 30 6.5 Пропускная способность и производительность......................................... 31 7 АНАЛИЗ СМО С ПУАССОНОВСКИМ ПОТОКОМ ТРЕБОВАНИЙ ..... 32 7.1 Система с потерями M/M/m .......................................................................... 34 7.2 Система с неограниченной очередью M/M/m/∞ .......................................... 38 7.3 Система с ограниченной очередью M/M/m/r ............................................... 44 7.4 Система с неограниченной очередью M/D/m/∞ .......................................... 48 7.5 Система с неограниченной очередью M/G/1/∞ ........................................... 52 7.6 Система с приоритетами M/G/1/∞................................................................ 58 7.6.1 Относительный приоритет ..................................................................... 58 7.6.2 Абсолютный приоритет с дообслуживанием ........................................ 60 7.7 Система с потерями M B /M/m – мультисервисный узел доступа ................. 61 7.8 Модель обслуживания мультисервисного трафика ................................... 67 7.8.1 Аппроксимация Хейворда ...................................................................... 69 7.8.2 Пример расчета вероятности потерь ...................................................... 70 4 8 АНАЛИЗ СМО В УСЛОВИЯХ РЕАЛЬНОГО ПОТОКА ТРЕБОВАНИЙ ... 71 8.1 Функция распределения состояний системы с потерями HM/D/m ............ 72 8.2 Вероятность потерь системы HM/D/m ......................................................... 76 8.3 Система с неограниченной очередью HM/D/m/∞........................................ 78 8.4 Система с неограниченной очередью fBM/D/1/∞ ........................................ 81 8.5 Система с неограниченной очередью G/M/1/∞ ........................................... 88 8.6 Система с неограниченной очередью G/D/1/∞............................................ 91 9 ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СМО ......................................... 94 9.1 Метод статистических испытаний ............................................................... 94 9.2 Синтез моделирующих алгоритмов ............................................................. 95 9.3 Моделирование марковского процесса........................................................ 97 9.4 Моделирования вложенной цепи Маркова.................................................. 98 9.5 Моделирование реального процесса обслуживания ................................... 99 Контрольные вопросы и задачи .......................................................................... 105 Список литературы .............................................................................................. 107 Дополнительная литература ................................................................................ 108 Список обозначений и сокращений .................................................................... 109 Предметный указатель......................................................................................... 110 ПРИЛОЖЕНИЕ.................................................................................................... 111 5 ПРЕДИСЛОВИЕ С возникновением телефонной связи появилась необходимость в специальных математических методах оценки качества функционирования телефонных систем, вследствие чего научными работами датского ученого Агнера Крарупа Эрланга (1878-1929) в начале ХХ века заложены основы теории телетрафика. Шведский ученый К. Пальм обобщил исследования А. К. Эрланга и в своей докторской диссертации привел важные результаты по изучению изменяемости телефонной нагрузки.Дальнейшее развитие этой работы позволило в середине ХХ века русскому математику А.Я. Хинчину начать новое научное направление прикладной математики, которая кроме телекоммуникаций охватывает еще и процессы в системах производства, обслуживания, управления и т.п. Данное направление названо теорией массового обслуживания (ТМО). Эта теория, «выросшая» из теории телетрафика, рассматривает более широкий круг вопросов количественной оценки процессов массового обслуживания. Таким образом, теория телетрафика является отдельным разделом ТМО, а теория массового обслуживания в телекоммуникациях – и есть теория телетрафика. Содержание теории телетрафика состоит в исследовании пропускной способности телекоммуникационных систем (ТКС). Методами этой теории разрабатываются новые научно обоснованные методы оценки характеристик качества обслуживания. Теория телетрафика обеспечивает оценку всех параметров ТКС и, прежде всего, учитывается стохастический (случайный) характер потоков требований, поступающих в систему на обслуживание. Оценка прогнозируемой пропускной способности и качества обслужи- вания очень важный этап проектирования ТКС и сетей. Здесь аналитические расчеты строятся на математическом описании реакции системы на внешние воздействия. Под реакцией системы понимается ее состояние (количество занятых серверов или мест ожидания, время задержки и др.), а под внешними воздействиями – потоки требований, сбои, отказы из-за ненадежности и т.п. Внешний фактор влияния в мультисервисных сетях связи – это разнородность информации, передаваемой в рамках единой сети: данные, речь, видео. Потоки этой информации существенно отличаются между собой по приоритетам, механизмам обслуживания, особенностями протоколов и т.д., и адекватной здесь будет многомерная модель. Поэтому, для сложных систем аналитические расчеты, выполняются с ограничением внешних факторов, раздельно для каждого типа (группы) влияний или с применением многопоточных моделей. Описание реакции системы на совокупность всех внешних воздействий – чрезвычайно трудная задача, которая в общем виде не всегда решаема. Количество внешних влияний может быть велико и каждое влияние не всегда однозначно описывается простыми формулами, дающими конечный результат с понятным физическим содержанием, а также описание внешних влияний не всегда адекватно реальным процессам, происходящим в системе. В математических моделях теории телетрафика учтены вид входного потока, схема системы и дисциплина обслуживания. 6 Научно обоснованное планирование и оптимизация телекоммуни- кационных систем и сетей, обеспечивающих предоставление запрашиваемых услуг с заданными показателями качества обслуживания, является очень сложной научно-технической и экономической проблемой, без решения которой невозможно создание информационной инфраструктуры, отвечающей потребностям развитого общества. В развитии бизнеса отдельных телекоммуникационных компаний этот фактор является важнейшим при обосновании действий администрации, направленных на повышение эффективности работы сети и качества обслуживания пользователей. Решение данной проблемы базируется на решении задач анализа и синтеза ТКС. Комплексное решение этих задач позволяет оптимизировать структуру сети на продолжительную перспективу. В условиях развития телекоммуникаций в соответствии с основными положениями концепции сетей следующего поколения NGN, обеспечивающих предоставление неограниченного набора услуг с заданными характеристиками качества обслуживания QoS, указанные вопросы становятся еще более актуальными. Избранная технология распределения информации в NGN определяет степень сложности узлов коммутации, которая, безусловно, влияет на качество обслуживания обмена информацией между терминалами пользователей. Кроме того, качество обслуживания потоков информации влияет и на сами характеристики передачи информации (например, задержки пакетов IP- телефонии приводят к снижению качества телефонной связи). Таким образом, расширение спектра предоставляемых услуг и возрастающая сложность ТКС и сетей требует решения проблемы разработки адекватных методов анализа и синтеза этих систем с целью получения достоверных оценок их характеристик, реализации задач их оптимизации относительно избранного критерия качества обслуживания и разработки соответствующих алгоритмов управления ними. Процессы функционирования сетей и систем связи можно представить некоторой совокупностью систем массового обслуживания (СМО), для которых определяются характеристики QoS. Одним из классов СМО в телекоммуни- кациях есть системы распределения информации (СРИ), к которым принад- лежат сети связи в целом или отдельные коммутационные узлы, например, пакетные коммутаторы, обслуживающие по определенным алгоритмам сообщения телекоммуникационных служб. Количественная сторона процессов обслуживания потоков сообщений (трафика) в СРИ является предметом теории телетрафика. Эта теория, как самостоятельная научная дисциплина, содержит набор вероятностных методов решения проблем проектирования новых и эксплуатации действующих систем телекоммуникаций. Создание теории телетрафика начато научными работами Эрланга А.К. (выдающиеся B- и C-формула Эрланга). Ее развивали такие ученые, как Burce P.J, Crommelin C. D., Kleinrock L., О'Dеll G.F., Palm C., Pollaczek F., Wilkinson R.I. Существенный вклад в развитие теории телетрафика внесли представители русской научной школы: Хинчин А. Я., Башарин Г.П., Лившиц Б.С., Харкевич А.Д., Севастьянов Б.А., Нейман В.И, Степанов С.Н. и академики АН Украины 7 Гниденко Б.В., Коваленко И.Н., Королюк В.В. Достижением теории являются учебники и научные работы Шнепса М.А., Корнышева Ю.Н. и других. Пропускная способность СМО тесно связана с оценкой показателей качества обслуживания трафика, что требует учета многих факторов для построения адекватных, научно обоснованных методов их расчета. Методы оценки характеристик качества обслуживания базируются на математических моделях СРИ. Многообразие видов и топологий сетей, структур систем и способов выделения сетевого ресурса для обслуживания трафика требует разработки моделей, которые учитывают еще и реальный характер потоков сообщений и детали обслуживания мультисервисного трафика разных коммуникационных приложений (речь, видео, данные). Поэтому невозможно построить единую модель, которая бы давала ответы на все вопросы относительно функционирования новых сетей связи. Именно на основе применяемых моделей СРИ разрабатываются методы оценки характеристик QoS, достоверность которых зависит от адекватности модели реальной ситуации, которая может возникнуть при проектировании и эксплуатации. Оценка качества обслуживания трафика является одним из важнейших научных направлений в исследованиях телекоммуникационных сетей. На этом базируется продуманная и целенаправленная стратегия модернизации современных сетей на этапе их конвергенции и замены технологии коммутации каналов на коммутацию пакетов. Принципы функционирования сети обусловлены режимами переноса информации, а качество обслуживания – реальным характером трафика. При этих обстоятельствах необходима разработка новых методов анализа и синтеза СРИ, которые адекватно отображают реальные процессы обмена информацией в сети. Это даст дальнейшее развитие теории телетрафика и обогатит практический инструментарий среды проектирования инфокоммуникационных сетей, что, в свою очередь, позволит обеспечить ощутимую экономию затрат на строительство и эксплуатацию сетей связи. Благодаря более точным расчетам повысится качество обслуживания и пропускная способность СРИ. Новые методы оценки характеристик QoS необходимы в системах динамического управления сетями для перераспределения их ресурсов и оптимизации трафика и сети в целом на основе заданного (нормированного) качества обслуживания. Таким образом, при системном подходе к проблеме планирования и оптимизации ТКС и сетей невозможно обойтись без математических методов анализа, синтеза и оценки качества предоставления информационных услуг в условиях реальных потоков сообщений. Отсутствие таких методов приводит к принятию неоптимальных решений в процессе разработки, проектирования и эксплуатации ТКС и сетей, поскольку возникает резкое несоответствие между ожидаемыми (проектными) показателями и реальным качеством обслуживания. Телетрафик – это не только классические телефонные сообщения, но и потоки сообщений в новых инфокоммуникационных сетях. Специфические особенности разных СРИ увеличивают проблемы разработки универсальных методов их анализа и синтеза. Особенно сложна эта проблема для таких 8 моделей трафика, которые адекватны реальным процессам формирования его потоков в сети. Природа поступления потоков и их обслуживания зависит от конкретного вида системы и сети, структурного состава абонентов, спектра предоставляемых услуг и других факторов. В теории телетрафика разработан ряд математических моделей и методов решения задач анализа и синтеза СРИ для условий идеализированной пуассоновской модели трафика. Однако, набор этих методов пока недостаточно полон с точки зрения структурных особенностей реальных СРИ, дисциплин обслуживания и в особенности характера трафика. Реальному трафику современных мультисервисных сетей связи присущий значительно больший уровень неравномерности интенсивности нагрузки, чем это предусмотрено классической моделью пуассоновского потока. Для таких моделей трафика теория телетрафика не имеет соответствующих методов расчета и на практике оценка характеристик качества обслуживания мультисервисных сетей связи ведется приближенными методами и средствами имитационного моделирования. „Нерезультативность” существующих методов определяется тем, что они ориентированы на использование лишь первых моментов распределений случайных величин, определяющих интенсивность трафика и функционирование СРИ. При обслуживании реального трафика на характерис- тики QoS оказывают влияние и высшие моменты распределений названных величин, которые определяют характер и степень неравномерности трафика. Анализ научных публикаций показывает, что много теоретических разработок нельзя использовать практически. Это связано с такими недостатками теоретических исследований, как: применение математического аппарата, не адекватно отображающего процессы в телекоммуникационных сетях; неудачный выбор показателей и критериев оценки предлагаемых решений; попытка получения аналитических зависимостей характеристик телекоммуникационных сетей в границах, где аналитический аппарат не работает; разработка методов, которые, улучшая один из параметров телекоммуникационной системы, в конце концов, снижают эффективность функционирования всей системы в целом; определение закономерностей, в составе которых есть начальные данные, получить которые невозможно. С учетом значимости данной научной проблемы можно констатировать, что проблема развития теории телетрафика путем ее обогащения новыми методами анализа и синтеза систем распределения информации, которые функционируют в условиях обслуживания реальных потоков трафика, является в особенности актуальной в современных условиях конвергенции сетей и построения на этой основе сетей нового поколения NGN. Такая постановка задачи отвечает общему подходу, принятому в международной практике и сформулированному в рекомендациях ITU. 9 |