Модели систем массового обслуживания

Содержание.

Введение........................................................................................................................... 1

1 Модели систем массового обслуживания............................................................... 4

1.1 Предметная область теории телетрафика....................................................... 4

1.1.1 Информационные процессы и конфликты обслуживания......................... 4

1.1.2 Основные определения теории систем массового обслуживания............. 5

1.1.3 Модели потока требований............................................................................ 9

Нестационарный пуассоновский поток............................................................... 12

Примитивный поток.............................................................................................. 13

Поток с ограниченным последействием.............................................................. 13

Поток Эрланга........................................................................................................ 13

1.1.4 Поток освобождений серверов.................................................................... 14

1.2 Модели систем массового обслуживания..................................................... 15

1.2.1 Математическое введение в теорию цепей Маркова. (Markov’s chain).. 15

Непрерывные цепи Маркова................................................................................. 18

1.2.2 Классификация систем массового обслуживания..................................... 22

1.2.3 Формула Литтла. (Little)............................................................................... 22

1.3 Анализ систем массового обслуживания с марковскими потоками требований. 24

1.3.1 Система М/M/1. Анализ................................................................................ 24

1.3.2 Cистема с конечным накопителем: M/M/1:N............................................. 27

1.3.3 Система с несколькими серверами: M/M/m................................................ 29

1.3.4 Система обслуживания с m серверами явными потерями: M/M/m/Loss. 32

1.3.5 Система обслуживания M/M/m:K/M конечное число источников нагрузки, m серверов и конечный накопитель................................................................................... 33

1.3.6 Система типа M/M/m:m................................................................................. 35

1.4 Вероятность занятия серверов....................................................................... 36

1.5 Сравнительные характеристики моделей Эрланга и Энгсета................... 36

1.6 Примеры анализа систем связи...................................................................... 38

1.7 Системы с неполнодоступным включением серверов............................... 39

1.8 Основы марковской теории сетей массового обслуживания..................... 47

1.8.1 Анализ систем массового обслуживания без явных потерь..................... 47

1.8.2 Анализ сетей массового обслуживания с блокировками. Метод вероятностных графов Ли. 52

2 Анализ и оптимизация коммутационных систем................................................ 54

3 Анализ систем с произвольным законом распределения времени обслуживания 60

4 Сравнение характеристик качества обслуживания в сетях с коммутацией каналов и коммутацией пакетов............................................................................................................ 64

4.1 Анализ времени доставки сообщений в сети с коммутацией каналов..... 64

4.2 Анализ времени доставки сообщений в сетях с коммутацией пакетов.... 70

5 Анализ характеристик каналов с интеграцией речи и данных.......................... 75

5.1 Метод производящих функций...................................................................... 75

5.2 Модели интеграции речи и данных.............................................................. 77

5.2.1 Интеграция на основе обслуживания в порядке поступления................ 77

5.2.2 Интеграция с абсолютным приоритетом.................................................... 81

5.2.3 Интеграция на основе стратегии подвижной границы........................... 84

6 Система типа G/G/1................................................................................................. 89

7 Анализ систем массового обслуживания с приоритетами................................. 95

7.1 Дисциплины обслуживания. Модель с приоритетами............................... 95

7.2 Основная модель расчета среднего времени ожидания.............................. 96

7.3 Дисциплины обслуживания с приоритетами, зависящими от времени. 101

7.4 Оптимизация назначения приоритетов...................................................... 104

Список используемой литературы.......................................................................... 108

Введение

В курсе «Теория телетрафика» рассматриваются процессы обработки информации в телекоммуникационных сетях с точки зрения теории систем массового обслуживания. Основными понятиями системы массового обслуживания (СМО) являются заявки (требования) и серверы, называемые также обслуживающими приборами. Заявки образуют входной поток на входе СМО и работа системы состоит в обслуживании этих заявок, затрачивая на каждую некоторое время. Если число серверов недостаточно для обслуживания всех поступивших заявок, то возникает конфликт, разрешение которого состоит в том, что часть заявок отбрасывается или помещается в очередь. Поэтому в зарубежной литературе, обычно используется термин Queuing Theory (теория очередей).

В телекоммуникационных системах заявка ассоциируется, прежде всего, с попыткой абонента получить доступ к ресурсам системы для передачи или приема сообщений. Например, снимая трубку телефонного аппарата, абонент телефонной сети порождает сигнал, который является заявкой на обслуживание его этой сетью. Если аппарат включен через блокиратор, и снявший трубку не услышит ничего – то сеть отказывает ему в обслуживании, заявка отбрасывается. Наличие гудка означает, что заявка принята и абонент получает обслуживание. Абонент телефонной сети порождает заявки и другого типа – набор номера вызываемого абонента. Эта заявка также может быть удовлетворена, если ресурсы сети позволят установить соединение между всеми телефонными станциями, которые обеспечивают передачу речевого сигнала от телефона вызывающего до телефона вызываемого абонента. Однако, это произойдет не всегда. Заявка на установление соединения может быть не удовлетворена. Вероятность такого события для абонентов телефонной сети рассматривается как характеристика качества обслуживания этой сети и расчет вероятности отказа в обслуживании является одной из важнейших задач теории телетрафика. Рассмотрим теперь пользователей другой, компьютерной сети, например Internet. Здесь качество сети ассоциируется с другой характеристикой – временем доступа к тому или иному ресурсу. Причиной замедления работы являются образующиеся в маршрутизаторах очереди, состоящие из пакетов, в которые упакована вся передающаяся по сети информация. В компьютерных сетях заявка на передачу информации от одного узла к другому даже в случае нехватки ресурса, как правило, не отбрасывается, а помещается в очередь на ожидание освобождения необходимого ресурса. Поэтому характеристикой качества обслуживания в этом случае считают время нахождения заявки в очереди на обслуживание. Задача расчета времени ожидания также решается в теории телетрафика.

Таким образом, изучив основные методы теории телетрафика, вы сможете рассчитать характеристики качества обслуживания в телекоммуникационных системах, управлять основными параметрами качества обслуживания реальных сетей и систем и измерять их, а также предложить оптимальные с точки зрения качества обслуживания технические решения при проектировании новых сетей и систем. Вопросы построения сетей с гарантированным качеством услуг являются предметом внимания ITU-International Telecommunication Union (Международного Союза Электросвязи) особенно в связи с развертывание работ по созданию глобальных сетей третьего и четвертого поколений в третьем тысячелетии.

ITU выделяет Traffic Engineering в явном и неявном виде как одно из важнейших направлений деятельности специалистов по телекоммуникациям и посвящает ему целый ряд рекомендаций, определения и методики из которых будут использованы далее в настоящем пособии. В этом отношении наш взгляд на теорию телетрафика не всегда совпадает с классическим изложением, принятым в отечественной литературе. В прекрасном учебнике по теории телетрафика [1] вы найдете при необходимости терминологию и подходы к решению задач, относящихся к классической телефонии.

Изложенный ниже курс лекций был впервые прочитан автором для студентов специальности «Сети связи и системы коммутации» Нижегородского государственного технического университета в 1998/1999 учебном году. С текстом лекций были ознакомлены многие преподаватели и специалисты. Всем им автор выражает глубокую благодарность. Особенно признателен автор профессорам МТУСИ А.П.Пшеничникову и Ю.В. Лазареву, доцентам НГТУ А.Б. Зуеву и А.А. Кочеткову за ценные замечания, существенно способствующие улучшению рукописи. Автор благодарит также всех своих студентов, кому пришлось воспринимать изложенный курс на слух и внесших вклад в появление его письменной реализации.

Модели систем массового обслуживания

Первый раздел включает в себя изложение основного математического аппарата, необходимого для решения задач, составляющих предмет теории телетрафика. Основной материал здесь заимствован в [2]. Некоторая кажущаяся сложность уравнений при более практичном взгляде оказывается преодолимой, если рассматривать сразу при прочтении простые и очевидные примеры.

Дата добавления: 2015-08-02