Сети массового обслуживания и их применение. Моделирование вс на основе систем и сетей массового обслуживания

1. ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ МУЛЬТИМЕДИЙНОГО ВИДЕОТРАФИКА ПРИ ЕГО ПЕРЕДАЧЕ ПО ПАКЕТНЫМ СЕТЯМ

1.1. Основные типы мультимедийного трафика реального времени.

1.2. Общий подход к описанию мультимедийного трафика реального времени.

1.3. Параметры качества обслуживания при передаче мультимедийного трафика в пакетных сетях передачи данных.

1.4. Технологии и стандарты кодирования и передачи видеотрафика.

1.5. Аппроксимация видеотрафика марковскими процессами.

2. АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ МОДЕЛИРОВАНИЯ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ ПЕРЕДАЧИ МУЛЬТИМЕДИЙНЫХ ВИДЕОТРАФИКОВ.

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

2.2. Сети массового обслуживания как модели телекоммуникационных систем.

2.2.1. Параметры сетей массового обслуживания.

2.2.2. Характеристики стационарного режима функционирования сети массового обслуживания.

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

2.4. Вычисление характеристик сетей массового обслуживания, производных от метода анализа средних.

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

3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПЕРЕДАЧИ ВИДЕОТРАФИКА В

ПАКЕТНЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

3.1. Общие принципы организации мультимедийных сервисов в пакетных телекоммуникационных сетях.

3.2. Концептуальная модель задержек передачи видеотрафика.

3.3. Математическая модель задержек передачи видеопотока.

3.4. Вероятностно- временные характеристики модели оценки задержек передачи видеопотока.

3.5. Результаты моделирования.

4. ОЦЕНКА ДЖИТТЕРА ПЕРЕДАЧИ ВИДЕОПОТОКОВ В ПАКЕТНЫХ

СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.

4.1. Общая постановка задачи.

4.2. Оценка дисперсии задержки передачи видеотрафика в пакетной сети, достоверность результатов.

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

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

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

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

Традиционно для предоставления информационных услуг использовались синхронные методы передачи данных, при которых на первичной сети выделялись телекоммуникационные ресурсы в расчете на максимальную нагрузку, которые монопольно занимались потребителями и поставщиками соответствующих информационных услуг. В этом случае телекоммуникационные ресурсы сети ис-® пользовались неэффективно, а общая производительность сети была низкой .

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

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

Более высокую эффективность использования ресурсов звена передачи данных за счет статистического мультиплексирования трафиков пакетов многих приложений;

Значительно более низкую вероятность потери пакетов передаваемого трафика при повышении нагрузки на сеть, хотя при этом имеют место значительные непредсказуемые транзитные задержки;

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

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

Эта задача особенно актуальна в случае предоставления мультимедийного сервиса, который в значительной степени чувствителен к задержкам передачи его ^ трафика .

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

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

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

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

1. Оценка параметров трафиков, генерируемых информационными серви-ф сами определенного типа.

2. Собственно оценка параметров задержек передачи мультимедийного трафика, передаваемого в пакетной сети с заданной архитектурой и топологией.

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

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

Для решения второй задачи в работе предлагаются различные методы совпадения импульсных потоков для отыскания необходимых параметров суммарного трафика, передаваемого по телекоммуникационной сети с заданными архитектурой и топологией. Применение методов теории совпадения импульсных потоков для расчета трафиков нагрузки в широкополосных интегральных сетях ATM предлагалось в . Цыбаков В. И. в работе утверждает, что традиционные методы проектирования телефонных сетей оказываются неприемлемы для оценки параметров мультимедийных сетей, так как традиционные методы учитывают только лишь одномерный трафик, который к тому же является однородным. Мультимедийная сеть представляет собой интегрированную сеть с представлением широкого спектра услуг (речи, данных, видео), т. е. является сетью, обеспечивающей многомерный и неоднородный трафик.

Для решения задачи оценки джиттера задержки (задача 3) применяются математические модели различных классов. Наиболее распространенными являются аналитические и имитационные модели. Содержание этих методов более подробно рассмотрено в главе 2. Выбор используемого класса моделей определяется многими факторами, среди которых можно выделить следующие: цели моделирования, возможность адекватного описания исследуемых параметров в соответствующих классах математических моделей, трудоемкость разработки этих моделей и др - .

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

Рекомендации ITU-T Е.430, Е.800 и концепция соответствия качества услуг представленного информационного сервиса. Эту модель предлагается использовать для проектирования, инсталляции и эксплуатации как существующих, так и вновь разрабатываемых информационных услуг современных телекоммуникационных сетей.

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

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

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

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

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

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

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

В работе рассматривается пример А ГМ-сети, которая предоставляет услугу передачи мультимедийного трафика ABR, в соответствии с которой гарантируется минимальная скорость передачи, и не производится синхронизации приемника и передатчика. Передаваемый видеопоток в данной системе имеет низкий приоритет, а число абонентов этой сети является ограниченным.

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

В работе анализируется процесс цифровой передачи видеотрафика, который предъявляет строгие требования к ширине полосы пропускания, задержке и потере. Сети с коммутацией пакетов не могут гарантировать качество обслуживания, особенно при многоадресной (широковещательной) передаче видео. Для обеспечения большей гибкости и эффективности в этих сетях применяются различные механизмы управления потоками, позволяющие, с одной стороны, повысить эффективность, а с другой стороны, обеспечить требуемое качество предоставляемого сервиса. Сравнительный анализ приводится в на примере передачи мультимедийного трафика стандарта MPEG. Сравниваются два механизма управления потоками: IntServ и DiffServ. Отдается предпочтение механизму Diff-Serv с приоритетами и разбиением мультимедийного передаваемого потока на ряд потоков с различными уровнями приоритетов.

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

Для достижения этих целей решены следующие основные задачи диссертационной работы:

1) Исследование особенностей мультимедийных трафиков, их классификация и параметризация.

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

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

4) Разработка аналитических моделей задержек передачи видеотрафика в IP-сети и оценка джиттера и дисперсии этих задержек.

Научная новизна результатов:

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

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

3. Разработана модель процесса передачи видеотрафика в TCP/IP сети с типичной звездообразной топологией, обеспечивающая оценивание широкого спектра вероятностно-временных характеристик её процессов функционирования.

4. На базе разработанной модели получены оценки основных параметров качества представляемого мультимедийного видеосервиса (транзитная задержка и её джиггер).

Практическая ценность результатов работы.

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

Разработано программное обеспечение анализа приоритетных замкнутых неоднородных сетей массового обслуживания большой размерности (до 200 систем обслуживания, 3000 классов требований и 10 000 требований);

Предложенные модели использовались ООО "Первая миля" (Компьютерные сети Академгородка) при проектировании и развитии мультисервисной сети Академгородка.

Результаты проведенных исследований внедрены в учебный процесс Сибирского Государственного Университета Телекоммуникаций и Информатики.

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

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

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

3. Аналитическая модель процессов передачи видеотрафика в локальной сети с использованием стека протоколов ТСРЯР для оценки параметров качества (транзитная задержка и джиггер) предоставленных мультимедийных сервисов - видео по требованию.

Апробация работы. Основные положения и результаты диссертационной $ работы докладывались и обсуждались на: Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (г. Новосибирск, 1997г); Российских научно-технических конференциях (г. Новосибирск, 1996, 2004 гг); Международной научно-практической конференции «Связь-2004»; научно-технических семинарах кафедры ТС и ВС Сибирского государственного университета телекоммуникаций и информатики (г. Новосибирск, 1996 - 2004гг).

Публикации: Основные результаты диссертационной работы опубликованы с 1996 по 2004 г. в 6 работах.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Общий объем работы составляет 145 страниц машинописного текста и включает: 23 рисунка, 18 таблиц, список литературы из 130 наименований и 2 приложения.

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Аль-Днебат Саид Али

Предложен метод оценки джиттсра доставки мультимедийного видеотрафика. Он учитывает топологию исследуемой телекоммуникационной системы, структуру передаваемого видеопотока и маршрута его доставки.

Данный метод основан на оценке задержек передачи видеокадров сетями массового обслуживания и аппроксимации дисперсии задержек в компонентах телекоммуникационной системы дисперсиями задержек в СМО М/М/1. Эта СМО эквивалентна соответствующей СМО сети по интенсивности входного потока требований и их среднему времени пребывания в ней.

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

ЗАКЛЮЧЕНИЕ

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

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

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

3) Модифицирован метод "анализ средних" - расчета сетей обслуживания, с учетом большой размерности сети (L = 200 систем обслуживания, и К = 3000 классов требований) и наличия приоритетных потоков требований.

4) В системе Mathcad разработана программа расчета замкнутой неоднородной сети массового обслуживания с числом узлов до 200, числом классов требований до 3000 и суммарным числом требований всех классов до 10 000.

5) Разработана аналитическая модель процесса передачи трафика мультимедийного сервиса «цифровое видео по запросу» по локальной TCP/IP сети конкретной топологии. Данная модель обеспечивает оценку следующих вероятностно-временных характеристик используемой телекоммуникационной системы: коэффициент использования различного телекоммуникационного оборудования, время доставки пакетов мультимедийного трафика до абонентов, дисперсия времени доставки, задержка пакетов в различных компонентах телекоммуникационной сети, дисперсия и джиггер этой задержки.

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

7) Разработанные методики математического моделирования были внедрены в учебный процесс Сибирского Государственного Университета Телекоммуникаций и информатики.

8) Предложенные модели использовались ООО " Первая миля" при проектировании и развитии мультисервисной сети Академгородка города Новосибирска.

9) Достоверность предложенных методов подтверждается результатами моделирования, а также реальными измерениями подобных телекоммуникационных систем. Результаты представлены на рис. 18 в гл.З и рис.23 в гл.4.

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

Список литературы диссертационного исследования кандидат технических наук Аль-Днебат Саид Али, 2004 год

1. Мархасин А.Б. Резервы роста российского рынка услуг мобильной связи: дифференциация и динамическое управление качеством услуг (QoS) и тарифа-ми//Электросвязь № 3 - 2001.

2. Шехтман Л. И. Системы телекоммуникаций: проблемы и перспективы. Опыт системного исследования. М.: Радио и Связь, 1998.

3. Marchese М. Study and performance evaluation of TCP modifications and tuning over satellite links//ICC 2000.

4. Аль-Днебат С., Аль-Касасбех Б. Вопросы развития перспективных широкополосных телекоммуникационных сетей в Иордании//Информатика и проблемы телекоммуникаций. Тезисы докладов Российской научно-технической конференции Новосибирск: СибГУТИ, 1996 - С.73-74.

5. Altmann J., Rupp В., Varaiya P. The Case for Quality of Service on Demand. ISQE"99//Workshop on Internet Service Quality Economics 1999.

6. Guirguis R.M., Mahmoud S. Transmission of real-time multi layered MPEG-4 over ATM/ABR service/ЛСС 2000 - PP.259-263.

7. Dubrovsky A., Gerla M., Lee S. S., Cavendish D., Internet QoS Routing with IP Telephony and TCP Traffic//IEEE, JUNE 18-22, 2000 New Orleans.

8. Ma Q., Steenkiste P. Routing Traffic with Quality-of-Service Guarantees in Integrated Services Networks//Workshop on Network and Operating Systems Support for Digital Audio and Video, Cambridge, England, July 1998.

10. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер: с англ.-М.:Мир. 1989, 544 с.

11. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети с коммутацией пакетов. М.: Радио и связь, 1986, 408 с.

12. Лагутин В.С.Использование сетей с коммутации пакетов для реализации услуг мультимедиа / Системы управления сетями телекоммуникаций. МТУ СИ. М., 2002, С 210. в ЦНТИ "Информсвязь" 2002, №2205-св2002.

13. Попова А.Г., Панов А.Е. Сравнительный анализ способов коммутации для обеспечения услуг мультимедиа. Системы управления сетями телекоммуни-каций//МТУСИ. М., 2002, С.69-75.

14. Крук Б.И., Попантонопуло В.Н., Шувалов В.П. Телекоммуникационные системы и сети, современные технологии. Том 1 М. горячая линия-телеком, 2003г, - С.647.

15. Башарин Г.П., Самуйлов К.Е. Современный этап развития теории телеграфи-ка//Информационные материалы -2110-№1- С. 153-166.

16. Pippas J.B., Venieris I.S. A red variation for delay control/ЛЕЕЕ June 18-22, 2000- New Orleans.

17. S. Kapoor S. Raghavan. Improved multicast routing with delay and delay variation constraints. GLOBECOM 00 IEEE. San Francisc. 27 November -1 December 2000.

18. Chili-Jen C., Nilsson A.A. Queuing networks modeling for a packet router architecture using the DTM technology//IEEE June 18-22, 2000 New Orleans.

19. T.M. Trang, N. Boukhatem, G. Pujolle. COPS-SLS usage for dynamic policy-based QoS management over heterogeneous IP networks/ЯЕЕЕ network. May/June, 2003, PP 44-50.

20. Мархасин А.Б. Анализ интегрального телетрафика и проектирование мобильных сетей ЗС//Электросвязь 2002 - № 12 - С.3-9.

21. Демьянов А.И. Оценка параметров скачков нагрузки в сотовых сетях подвижной связи//Электросвязь 2002 - № 5.

22. Bahl P. Supporting digital video in a managed wireless network//IEEE Communications Magazine vol. 36 - June 1998 - PP.94-102.

23. Davies N., Finney J., Friday A., Scott A. Supporting adaptive video applications in mobile environments//IEEE Communications Magazine vol. 36 - June 1998 -PP. 138-143.

24. Седякин H.M. Элементы теории случайных импульсных потоков. М.: Советское радио, 1965, С.260.

25. Цыбаков В.И., Численные исследования дисперсионных свойств нагруз-ки//Вести связи 2002 - № 12 - С.55-58.

26. Шеннон Р. Имитационное моделирования систем, искусство и наука. Пер: с англ. М.: Мир, 1978, - С.420.

27. Аврамчук Е.Ф., Вавилов А.А., Емельянов С В. и др. Технология системного моделирования. Машиностроение. Берлин: Техник, 1988, - С.520.

28. Максимей И.В. Имитационное моделирование на ЭВМ. М.: Радио и мир. 1988, С. 232.

29. Иванов А.Б., Соколов И.В., От сквозного контроля сети к контролю качества услуг//Элекгросвязь 2001 - № 2.

30. Молчанов Д.А. Разработка модели и анализ характеристик обслуживания видеоинформации в узле сети АТМ//автореферат диссертационной работы на соискание ученой степени кандидата технических наук ГУТ - Санкт-Петербург - 2002 - С. 180.

31. Швецов В.П., Цирик И.А. Модель сети радиодоступа с разнородными потоками информации//Информсвязь 2001 - № 2195 - С. 18-25.

32. Casetti С. De Martin J.C. Meo M. A framework for the analysis of adaptive voice over IP//IEEE June 18-22, 2000 New Orleans.

33. Михалевич И.Ф., Сычёв К.И. Моделирование процессов функционирования и управления трафиком в системах мобильной связи//Элекгросвязь-2002 № 1.

34. Голышко А.В., Ершов В.А., Цыбаков В.И. Оценка качества обслуживания пользователей Интернет, включенных в электромеханические АТС//Вестник связи 2000 - № 12 - С.70.

35. Ершов В.А., Ершова Э.Б., Щека А.Ю., Метод оценки качества обслуживания на мультисервисной сети с учетом числа пользователей услуг//Электросвязь-2001 №8-С.5-8.

36. Cohen R., Radha Н., Streaming fine-grained scalable video over packet-based net-work//IEEE Global Telecommunications Conference San Francisco -27 November-1 December - 2000.

37. Lee M.J., Kim J.K. Video frame rate control for non-guaranteed network services with explicit rate feedback Visual Communications Lab//Dept. of Electrical Engineering Kusongdong Yusonggu Taejon - PP 305-701.

38. Wong W.K., Qian Y., Leung V.C. Scheduling for heterogeneous traffic in next generation wireless network//GLOBECOM IEEE-San Francisco 2000 - PP .283-287.

39. ElAarag H., Bassiouni M. Simulation of transport protocols over wireless communication networks//Proceedings of the 2000 Winter Simulation Conference -PP 235-1241.

40. Dapeng W., Yiwei H. Streaming video over the Internet Approaches and direc-tions/ЛЕЕЕ Trans / Circuits and Syst. Video Technol 2001 - № 3 - PP.282-300.

41. Zhao H., Ansari N., Shi Yun Q. Transmission of real-time video over IP differentiated services//Electron. Lett. 2002 - № 19 - PP.1151-1153.

42. Baskett F., Chandy K.M., Muntz R.R., Polacias F.G. Open, closed and mixednet-works of queues with different classes of customers//Journal of the ACM v.22, №2 - 1975 - PP.248-260.

43. Konstantopoulos Т., Zazanis M., De Veciana G. Conservation laws and reflection mappings with an application to multiclass mean value analysis for stochastic fluid queues//Stochastic Process vol. 65, №. 1 - 1996 - PP. 139-146.

44. Marchese M. Study and performance evaluation of TCP modifications and tuning over satellite links//IEEE ICC JUNE 18-22 2000- NEW ORLEANS.

45. Chen J.C, Agrawal P. Active techniques for real time video transmission and play-Ьаск/ЛЕЕЕ ICC 2000 - New Orleans - PP.239-243.

46. Lixin W. Hamdi M. Analysis of Multimedia Access Protocols for Shared Medium Networks//IEEE 2000 Global Telecommunications Conference - San Francisco.

47. Фоминов О. Мультимедиа и сети. Мультимедиа. Цифровое видео, № 5 1997.

48. Bodamer S., A New Scheduling Mechanism to Provide Relative Differentiation for Real-Time IP Traffic/ЛЕЕЕ 2000 GTC - San Francisco.

49. Bandara J., Shen X., Nurmohamed Z. A Fuzzy Resource Controller for Non-RealTime Traffic in Wireless Networks//IEEE ICC june 18-22, 2000 - New Orleans.

50. Jiang J. Lai Т. H., An Efficient Approach to Support QoS and Bandwidth Efficiency in High-Speed Mobile Networks//IEEE ICC june 18-22, 2000 - New Orleans.

51. Barryl M., Andrew T. Distributed Control Algorithms for Service Differentiation in Wireless Packet Networks//IEEE INFOCOM 2001.

52. Mansour J. Karam F. Tobagi A. On Traffic Types and Service Classes in the Internet//IEEE Global Telecommunications Conference 2000 - San Francisco.

53. Mercado A., Ray K. J. Adaptive QoS for Mobile Multimedia Applications Using Power Control and Smart Antennas//IEEE ICC june 18-22,2000 - New Orleans.

54. Kuzmanovic A. Edward W Measuring Service in Multi-Class Networks//IEEE INFOCOM 2001.

55. Lombardo A., Morabito G., Schembra G., An Accurate and Treatable Markov Model of MPEG-Video Traffic//IEEE Proc. Infocom April 1998 - USA, San Francisco.

56. ITU-T Recommendation 1.363.2: B-ISDN ATM Adaptation Layer 2 Specifications, Sep 1997.

57. ITU-T Recommendation H.323 Version 3, Packet Based Multimedia Communication Systems, 1998.

58. Capurro M., Ravaglia R., Giuli D. Users, Services and Traffic Modeling for Broadband Telecommunications Planning/TVol. 2- № 4 Jul.-Aug. 1991.

59. Bonatti M., Gaivoronski A., Lemonche P., Polese P. Summary of Some Traffic Engineering Studies Carried out Within RACE Project R1044//Vol. 5, № 2 Mar. Apr. 1994.

60. Maniatis S.I., Nikolouzou E.G., Venieris I.S. QoS issues in the converged 3G wireless and wired networks//IEEE Communications Magazine V.40, № 8 -2002 - PP.44-53.

61. Олифер В.Г., Олифер H.A. Компьютерные сети, принципы, технологии, протоколы. СП.: Питер, 2001, С.668.

62. Markopoulou P., Tobagi A., Karam J. Assessment of VoIP Quality over Internet Backbones//IEEE INFOCOM 2002.

63. Voran S. Speech quality of G.723.1 coding with added temporal discontinuity im-pairments//Proc. of ICASSP May 2001.

64. Ramjee R., Kurose J., Schulzrinne H. Adaptive play out mechanisms for pack-etized audio applications in wide-area networks/ЯЕЕЕ INFOCOM June 1994.

65. Rosenberg J., Qiu L., Schttlrinne H., Integrating packet FEC into adaptive voice playout buffer algorithms on the lnternet/ЛЕЕЕ INFOCOM March 2000.

66. Carle G., Biersack E. W., Survey of Error Recoveiy Techniques for IP-Based Audio-Visual Multicast Applications//IEEE Network vol. 11 - November-December 1997 - PP.24-36.

67. Perkins C., Hodson O., Hardman V. A Survey of Packet-Loss Recovery Techniques for Streaming Audio//IEEE Network vol.12, №. 5 - Sept-Oct 1998 -PP.40-48.

68. Erdol N., Castelluccia C., Zilouchian A. Recoveiy of Missing Speech Packets Using the Short-Time Energy and Zero-Crossing Measurements//IEEE Transactions on Speech and Audio Processing vol.1, №.3 - July 1993 - PP.295-303.

69. Chen Y. L., Chen B. S. Model-Based Multirate Representation of Speech Signals and Its Application to Recovery of Missing Speech Packets//IEEE Transactions on Speech and Audio Processing vol. 5, №. 3 - May 1997 - PP.220-231.

70. Hardman V., Sasse M.A., Handley M., Watson A. Reliable Audio for Use over the Intemet//Int. Proceedings of INET"95 1995.

71. Советов Б.Я., Яковлев С.А. Построение сетей интегрального обслуживания. -Л.: Машиностроение, 1990. С.332.

72. ISO/IEC JTC1/SC29/WG11 № 2459 Overview of the MPEG-4 standard. 1998.

73. Srivastava A., Kumar A., Singru A., Design and Analysis of a Video-on-Demand Served/Multimedia Systems Vol.5, No.4 - July 1997 - PP.238-254.

74. Wu D., Hou Y., Zhu W., Zhang Y., Peha M. Streaming video over the Internet Approaches and directions//IEEE Trans. Circuits and Syst. / Video Technol. 2001 -№ 3 - PP.282-300.

75. Conklin G., Greenbaum G., Lillevold K., Lippman A., Reznik Y. Video coding for streaming media delivery on the Internrt/ЯЕЕЕ Trans. Circuits and Syst. Video Technol. - 2001 - № 3 - PP.269-281.

76. Lee J. On a unified architecture for video-on-demand services/ЛЕЕЕ Trans. Multimedia 2002 - № 1 - PP.38-47.

77. Pornavalai C., Chakraborty G., Shiratori N. QoS Based Routing Algorithm in Integrated Services Packet NetwoTks//Intemational Conference on Network Protocols Atlanta, Georgia - PP. 167-175.

78. Rabbat R. Traffic Engineering Algorithms Using MPLS for Service Differentia-tion//IEEE JUNE 18-22, 2000 - NEW ORLEANS.

79. Toukourou M., Orozco-Barbosa L. Performance of MPEG-2 video-on-demand over RSVP//Proc. SPIE 2000 - PP. 13-24.

80. Furey S. The place of modeling tools in network planning//EDP Perform. Revio (USA) 1989 - V.17 - №6 - PP. 1-4.

81. Frost V.S., Melamed В., Traffic modeling for telecommunications net-works//IEEE Communications Magazine Mar. 1994 - PP.70-81.

82. Loeve W. Construction of programs for simulation//Informatie (Netherlands) -1993,- V.35, № 7-8 PP.485-492.

83. Shannon R.E., Introduction to simulation//IEEE Winter Simulations Conference Proceedings New York, USA - 1992 - PP.65-73.

84. Barton R.R., Fishman G.S., Kalos M.H., Kelton W.D., Kleijnen J.P. Experimental design issues for large simulation models//IEEE Winter Simulations Conference Proceedings San Diego, USA - 1989 - PP.411-418.

85. Henriksen J.O. The integrated simulation environment. Simulation software of the 1990s//0peration Res. (USA) 1983 - V.31, .№6 - PP. 1053-1073.

86. Radiya A., Fishwick P.A., Nance R.E., Rothenberg J., Sargent R.G. Discrete event simulation modeling, directions for the 1990s. 1992

87. Розанов Ю.А. Случайные процессы. M.: Наука, 1979г. С. 112.

88. Казаков В.А. Введение в теорию марковских процессов и некоторые радиотехнические задачи. -М.: Советское радио, 1973.

89. Гнеденко Б.В. Курс теории вероятностей. М.: Наука. 1969

90. Феллер В. Ведение в теорию вероятностей и ее приложения. Т.1, 2. М.: Мир, 1984.

91. Кемин Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука. 1970.

92. Карлин С.Осноы теории случайных процессов. М.: Мир, 1971.

93. Krunz, М.М. Makowski A.M., Modeling Video Traffic Using M/G/l Input Processes: A Compromise Between Markovian and LRD Models//IEEE Journalon Selected Areas in Communications 16 (5) PP.733-748.

94. Poon, W. Lo K., A refined version of M/G/ос processes for modeling VBR video traffic//Computer Communications PP. 1105-1114.

95. Кофман А., Крюон P. Массовое обслуживание. Теория и приложения. М.: Мир, 1965.

96. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчёта. М.: Наука, 1989. С. 336.

97. Штойян Д. Качественные свойства и оценки стохастических моделей. М.: Мир, 1979.

98. Кениг Д., Штойян Д. Методы теории массового обслуживания. М.: Радио и связь, 1981.

99. Jackson J.R. Networks of waiting Iines//Operation Research 1957 - №5 -PP.518-521.

100. Gordon W.G., Newell G.F. Closed queueing systems with exponential serv-ers//Operation Research V.15, №2 - 1967 - PP.254-265.

101. Митрофанов Ю.И., Беляков В.Г., Курбангулов B.X. Методы и программные средства аналитического моделирования сетевых систем//Препринт, М.: Научный совет по комплексной проблеме Кибернетика, 1982. с 67.

102. ChandyK.M., Howard J.H., TowsIeyD.F., Product form and local balance in queueing networks//Journal of the ACM v.24, №2 - 1977 - PP.250-263.

103. Беляков В.Г., Митрофанов Ю.И., Ярославцев А. Ф. Пакет прикладных программ для математического моделирования сетевых систем. 1986. С. 145150.

104. Гурьянов А.И., Митрофанов Ю.И. Определение параметров замкнутых линейных сетей систем массового обслуживания. 1970. С.39-49.

105. Chandy К.М. Neuse D., a heuristic algorithm for queueing network models for communications of the ACM. v.25, №2, PP. 126-141.

106. Reiser M., Lavenberg S.S. Mean-value analysis of closed multichain queueing networks//J. ACM vol. 27, № 2 - April 1980 - PP 313-322.

107. Reiser M. Mean-value analysis and convolution method for queue-dependentservers in closed queueing networks//Performance evaluation vol. 1 - 1981 -PP 7-18.

108. Жожикашвили В.А., Вишневский B.M. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. С. 192.

109. Xu Y., Chang Y., Liu Z. Calculation and analysis of compensation buffer size in multimedia systems//IEEE Commun. Lett. 2001 - № 8 - PP.355-357.

110. Xie J., Jiang S., Jiang Y. A dynamic bandwidth allocation scheme for differentiated services in EPONs//IEEE Communications Magazine august 2004, vol. 42 №. 8, PP.32-39.

111. Derong L., Endre S., Wei S. Nested auto-regressive processes for MPEG-encoded video traffic modeling/ЛЕЕЕ Trans. Circuits and syst / Video Technol -2001 -№2-PP 169-183.

112. Митрофанов Ю.И. Синтез сетей массового обслуживания. Саратов: Изд-во ГуНЦ "Колледж", 1995. С. 168.

113. Uttam K.S., Ramakrishnan S., Dilip S. Segmenting full-length VBR video into shots for modeling with Markov-modulated gamma-based framework//Proc. SPIE-2001 PP. 191-202.

114. Ярославцев А.Ф., Аль-Днебат С.А. Моделирование процессов передачи мультимедийного трафика в 1Р-сети//Информатика и проблемы телекоммуникаций. Тезисы докладов Российской научно-технической конференции. Новосибирск: СибГУТИ, 2003 - С.77-80.

115. Ярославцев А.Ф., Аль-Днебат С. А. Применение структурированных сетей обслуживания для оценки параметров качества сервиса телекоммуникационных сетей. Материалы международной научно-практической конференции «Связь 2004». 22-29 августа 2004 г. С.329-335.

116. CCIE, Cisco Certified internetworking Expert. Учебное руководство, Экзамен 350-001, М, 2002.

117. Schulzrinne Н., Casner S., Frederick R., Jacobson V. A Transport Protocol for Real-Time Applications//Audio-Video Transport Working Group January 1996.

118. Braden R., Clark D., Shenker S. Integrated Services in the Internet Architecture:an Overview / Internet RFC 1633, June 1994.

119. Zhao W. Tripathi S. K. Routing Guaranteed Quality of Service Connections in Integrated Services Packet Networks//International Conference on Network Protocols Atlanta, Georgia - PP. 175-182.

120. Balakrishnan H., Padmanabhan V., Seshan S., Katz R. A Comparison of Mechanisms for Improving TCP Performance over Wireless Links//IEEE ACM Trans, on Networking December 1997.

121. He E., Hughes H.D. Experimental Evaluation of TCP Performance over Wireless Networks//Symposium on Performance Evaluation of Computer and Telecommunication Systems 1999.

122. Schulzrinne H., Casner S., Frederick R., Jacobson V. RTP: A Transport Protocol for Real-Time Applications//RFC 1889 January 1996.

123. Spiridon В., Li V. Maximizing the number of users in an interactive video-on-demand system//IEEE Trans. Broadcast 2002 - № 4 - PP.281-292.

124. Hartanto F., Tiohardi L. Effects of interaction between error control and media synchronization on application-level performances//GLOBECOM"00. IEEE San Francisco - 2000 - PP.283-287.

125. Chatzimisios P., Boucouvalas A.C. Vitsas V. Performance Analysis of IEEE 802.11 DCF in Presence of Transmission Errors//2004 IEEE International Conference on Communications 2004.

126. Ярославцев А.Ф., Аль-Днебат С.А., Аналитическая модель передачи мультимедийного трафика по TCP/IP сети. Материалы международной научно-практической конференции «Связь 2004». 22-29 августа 2004 г. С.323-328.

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

Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).

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

Примерами систем массового обслуживания могут служить:

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

	Узлы	Требования

Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

Рассмотрим схему работы СМО (рис. 1). Система состоит из генератора заявок, диспетчера и узла обслуживания, узла учета отказов (терминатора, уничтожителя заявок). Узел обслуживания в общем случае может иметь несколько каналов обслуживания.

Рис. 1

Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

Очередь – накопитель заявок. Очередь может отсутствовать.
Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

СМО с отказами;
СМО с очередью.

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.

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

СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь, – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».

Итак, например, рассматриваются следующие СМО:

СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.

Типы ограничения очереди могут быть комбинированными.

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

Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.

Пример замкнутой системы: выдача кассиром зарплаты на предприятии.

По количеству каналов СМО делятся на:

одноканальные;
многоканальные.

Характеристики системы массового обслуживания

Основными характеристиками системы массового обслуживания любого вида являются:

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

Входной поток требований

Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.

А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

Очередь – совокупность требований, ожидающих обслуживания.

Очередь имеет имя.

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

первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

случайный отбор заявок;
отбор заявок по критерию приоритетности.

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

Характеристики очереди

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
длина очереди.

Механизм обслуживания

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

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода из строя обслуживающего канала по истечении некоторого ограниченного интервала времени. Эту характеристику можно моделировать как поток отказов, поступающий в СМО и имеющий приоритет перед всеми другими заявками.

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

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

Основные критерии эффективности функционирования СМО

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

вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

абсолютная пропускная способность системы – А=Р обсл *λ;
относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

4 – Основы теории массового обслуживания.

Определение 1. Пусть имеется некоторая физическая система S , которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс.

Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.

Пример. S – техническое устройство, состоящее из ряда узлов, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в системе, – случайный. Вообще, если подумать, труднее привести пример «неслучайного» процесса, чем случайного. Даже процесс хода часов – классический пример точной, строго выверенной работы («работают как часы») подвержен случайным изменениям (уход вперед, отставание, остановка).

Определение 2. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы наблюдаем процесс со стороны и в момент t 0 знаем состояние системы S 0 и всю предысторию процесса, все, что было при t < t 0 . Нас, естественно. Интересует будущее: t > t 0 . Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S 1 или сохранит состояние S 0 и т.д.

Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S 0 и забыв о его «предыстории» (поведение системы при t < t 0 ). Само состояние S 0 , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее» .

Пример. Система S – счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счетчика – числом частиц, пришедших до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в в момент t > t 0 счетчик покажет то или другое число частиц S 1 (или менее S 1 ) зависит от S 0 , но не зависит от того, в какие именно моменты приходили частицы до момента t 0 .

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S – группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» – x и «синих» – y , сохранившихся (не сбитых) к какому-то моменту. В момент t 0 нам известны численности сторон x 0 и y 0 . Нас интересует вероятность того, что в какой-то момент времени t 0 + t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента времени t 0 самолеты.

В сущности любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», перенести в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент времени t 0 оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t . Если за настоящее время считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность, что она не откажет за время t , зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.

Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S 1 , S 2 ,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

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

Пример. Техническое устройство S состоит из двух узлов. Каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.

Рис.4.1

Возможные состояния системы:

S 0 – оба узла исправны;

S 1 – первый узел ремонтируется, второй исправен;

S 2 – второй узел ремонтируется, первый исправен;

S 3 – оба узла ремонтируются.

Стрелка, направленная из S 0 в S 1 означает момент отказа первого узла и т. д. На рисунке нет стрелки из состояния S 0 в состояние S 3 , поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.

Определение 5. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток сбоев на ЭВМ, поток вызовов на телефонной станции).

Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. интенсивность потока может быть постоянной (l = const ), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.

Определение 6. Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени.

Определение 7. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность l стационарного потока должна быть постоянной. Это отнюдь не означает, что фактическое число событий, появляющееся в единицу времени, постоянно, – нет, поток неизбежно (если только он не регулярный) имеет какие-то случайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на один участок длины 1 может попасть больше, а на другой – меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.

Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.

Определение 8. Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты независимо друг от друга, вызванные каждое своими собственными причинами.

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

Определение 9. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами сразу.

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

Определение 10. Поток событий называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия, а сам входной поток распределен по закону Пуассона ().

Для описания случайного процесса, протекающего в системе с дискретными состояниями S 1 , S 2 , ..., S n часто пользуются вероятностями состояний p 1 ( t ),..., p n ( t ) , где p k ( t ) – вероятность того, что в момент времени t система находится в состоянии S k . Вероятности p k ( t ) удовлетворяют условию: .

Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем является марковским, то для вероятностей состояний p 1 ( t ), ..., p n ( t ) можно составить систему линейных дифференциальных уравнений. При составлении этих уравнений удобно пользоваться графом состояний системы, на котором против каждой стрелки, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему по стрелке (рис.4.2):

Рис.4.2

l ij – интенсивность потока событий, переводящего систему из состояния S i в состояние S j .

Правило создания системы линейных дифференциальный уравнений для нахождения вероятностей состояний.

Для каждого состояния выписывается собственное уравнение. В левой части каждого уравнения стоит производная , а в правой – столько членов, сколько стрелок связано непосредственно с данным состоянием; если стрелка ведет в данное состояние, то член имеет знак «+», иначе - знак «–». Каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого стрелка выходит.

Т.о. система линейных дифференциальных уравнений в нашем случае имеет вид:

Начальные условия для интегрирования такой системы отражают состояние системы в начальный момент времени. Если, например, система при t =0 была в состоянии S k , то . Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трех). В случае, когда уравнений оказывается больше, применяют численные методы.

Что будет происходить с вероятностями состояний при ? Будут ли p 1 ( t ), ..., p n ( t ) стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: . p i – среднее относительное время пребывания системы в i -ом состоянии.

Как найти финальные вероятности? Поскольку все p i = const , то производные, стоящие в левой части каждого уравнения равны нулю. Т.о. мы получили систему линейных алгебраических уравнений. Поскольку ни одно уравнение в этой системе не имеет свободного члена, то система является вырожденной (т.е. все переменные будут выражены через одну). Чтобы этот избежать, необходимо воспользоваться нормировочным условием (), при этом любое уравнение можно отбросить.

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

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

Также СМО подразделяются на системы без ожидания и с ожиданием. В первых заявка покидает очередь, если к моменту её прихода отсутствует хотя бы один канал, способный немедленно приступить к обслуживанию данной заявки. Вторые, в свою очередь, делятся на системы без ограничения и с ограничениями по длине очереди.

Также СМО делятся на системы с приоритетами и без них. В свою очередь системы с приоритетом делятся на СМО с прерыванием и без.

Одноканальная СМО с неограниченной очередью

Рис.4.3

Найдем вероятности p k :

Для состояния S 0 : , отсюда ;

Для состояния S 1 n : , подставляем полученное значение для p 1 : . Аналогично, .

Вероятность p 0 найдем из нормировочного условия :

, – геометрическая прогрессия, при r <1 сходится. – вероятность того, что нет заявок.

– вероятность того, что прибор занят обслуживанием заявки. r = l / m – мера загрузки одноканальной СМО.

В текущий момент времени в системе может быть 0, 1, 2, ..., k , ... заявок с вероятностями p 0 , p 1 p 2 , ... Математическое ожидание количества заявок:

учитывая, что , получим:

Средняя длина очереди равна разности между средним числом заявок в системе и средним числом заявок, находящихся под обслуживанием: .

Формулы Литтла

Рис.4.4

Первая формула Литтла позволяет определить время реакции СМО (время пребывания заявки в системе).

Пусть X ( t ) – число заявок, поступивших в СМО до момента времени t , Y ( t ) – покинувших СМО до t . Обе функции случайны и увеличиваются скачком на единицу в моменты прихода и ухода заявок. Тогда число заявок в системе в момент времени t можно определить как: . Рассмотрим очень большой промежуток времени T и вычислим среднее число заявок в системе:

Интеграл равен площади ступенчатой фигуры, ограниченной функциями X ( t ) и Y ( t ) , эта сумма состоит из прямоугольников, ширина которых равна единице, а длина – времени пребывания i -ой заявки в системе. Сумма распространяется на все заявки, поступившие в систему за время T . Правую часть домножим и разделим на l : . T l – среднее количество заявок, пришедших за время T . Поделив сумму всех времен t i на среднее число заявок, получим среднее время пребывания заявки в системе: .

Совершенно аналогично можно получить среднее время пребывания заявки в очереди: .

Многоканальная СМО с неограниченной очередью

Рис.4.5

Найдем вероятности p k :

Для состояния S 0 : ;

Для состояний S 1 – S n : ;

Для S n +1 : ; ...

Для S n+s-1 : ;

Для S n+s : .

Из первых n +1 уравнений получаем:

Из последнего уравнения выражаем: и подставляем в предпоследнее: , . Тогда .

Продолжая аналогию: .

Теперь найдем p 0 , подставив полученные выражения в нормировочное условие (): . Отсюда .

Показатели эффективности СМО

– Вероятность потери требования в СМО. Особенно часто ею пользуются при исследовании военных вопросов. Например, при оценке эффективности противовоздушной обороны объекта она характеризует вероятность прорыва воздушных целей к объекту. Применительно к СМО с потерями она равна вероятности занятости обслуживанием требований всех n приборов системы. Чаще всего эту вероятность обозначают p n или p отк .

– Вероятность того, что обслуживанием требований в системе занято k приборов, равна p k .

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

– Среднее число свободных от обслуживания приборов:.

– Коэффициент простоя приборов: .

– Коэффициент занятости оборудования: .

– Средняя длина очереди: , p k - вероятность того, что в системе находится k требований.

– Среднее число заявок, находящихся в сфере обслуживания: .

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

Кроме перечисленных критериев при оценке эффективности СМО могут быть использованы стоимостные показатели:

q об – стоимость обслуживания каждого требования в системе;

q ож – стоимость потерь, связанных с простаиванием заявок в очереди в единицу времени;

q у – убытки, связанные с уходом из системы заявки;

q k – стоимость эксплуатации каждого прибора в единицу времени;

q k пр – стоимость простоя единицы времени k -го прибора системы.

При выборе оптимальных параметров СМО по экономическим показателям можно использовать функцию стоимости потерь в системе (для СМО с ожиданием): T – интервал времени.

Для СМО с отказами: .

Для смешанных: .

Критерий экономической эффективности СМО: , с – экономический эффект, получаемый при обслуживании каждой заявки.

СМО замкнутого типа

Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.

Интенсивность обслуживания станков определяется как , – среднее время обслуживания станка, которое вычисляется как , где n – число заявок. Интенсивность подачи станком заявки на обслуживание определяется как (где – среднеее время обработки детали станком).

Станочная система с однозахватным манипулятором представляет собой СМО с ожиданием с внутренней организацией FIFO : каждая заявка станка на обслуживание удовлетворяется, в случае когда манипулятор занят, заявка становится в очередь и станок ожидает когда манипулятор освободится. Данный процесс марковский, т.е. случайная выдача заявки на обслуживание в определенный момент времени t 0 не зависит от предыдущих заявок, т.е. от течения процесса в предшествующий период. Продолжительность исполнения заявки может быть различной и является случайной величиной, не зависящей от числа поданных заявок. Весь процесс не зависит от того, что произошло ранее момента времени t 0 .

В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:

S 0 – все станки работают, манипулятор стоит.

S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.

S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.

S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.

S m – все станки стоят, один обслуживается манипулятором, остальные ожидают очереди исполнения заказа.

Рис.4.6.

Вероятность перехода в состояние S k из одного из возможных состояний S 1 , S 2 , ... S m зависит от случайного поступления заявок на обслуживание и вычисляется как:

p 0 – вероятность того, что все станки работают.

Манипулятор работает при состояниях системы от S 1 до S m . Тогда вероятность его загрузки равна: .

Число станков, находящихся в очереди связано с состояниями S 2 , – S m , при этом один станок обслуживается, а (k -1) – ожидают. Тогда, среднее число станков в очереди: .

Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): .

Среднее использование одного станка:

Применение метода Монте-Карло для решения задач,

связанных с теорией массового обслуживания

Для того, чтобы описать поток однородных событий, достаточно знать закон распределения моментов времени t 1 , t 2 , ..., t k , ..., в которые поступают события.

Для удобства дальнейших рассмотрений целесообразно от величин t 1 , t 2 , ..., перейти к случайным величинам z 1 , z 2 , ..., z m , ... , таким образом, что:

Случайные величины z k являются длинами интервалов времени между последовательными моментами t k .

Совокупность случайных величин z i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины z k , поэтому часто пользуются соответствующей функцией плотности f ( z 1 , z 2 ,..., z k ) .

Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины z k независимы. Поэтому . Функции f i ( z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала z k ( i >1) поступила заявка. В отличие от этого функция f 1 ( z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.

Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:

где l – плотность стационарного потока.

Поступившая в систему заявка может занимать только свободные линии. Относительно порядка занятия линий могут быть сделаны различные предположения:

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

б) линии занимаются в порядке очереди. Освободившаяся линия поступает в очередь и не начинает обслуживания заявок до израсходования всех ранее освободившихся линий;

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

Аналогичные предположения можно сделать и относительно порядка принятия заявок к обслуживанию в том случае, когда в системе образуется очередь заявок:

а) заявки принимаются к обслуживанию в порядке очереди. Освободившаяся линия приступает к обслуживанию той заявки, которая ранее другой поступила в систему;

б) заявки принимаются к обслуживанию по минимальному времени получения отказа. Освободившаяся линия приступает к обслуживанию той заявки, которая в кратчайшее время может получить отказ;

в) заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется m заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной q =1/ m . В более сложных случаях вероятности q 1 , q 2 ,..., q m считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа и других параметров.

· Для решения ряда прикладных задач оказывается необходимым учитывать такой важный фактор, как надежность элементов обслуживающей системы. Будем предполагать, что с точки зрения надежности каждая линия в данный момент времени может быть либо исправной, либо неисправной. Надежность линии определяется вероятностью безотказной работы R = R ( t ) , задаваемой как функция времени. Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время t p . Величину t p будем считать случайной величиной с заданным законом распределения.

Относительно судьбы заявки, при обслуживании которой линия выходит из строя, могут быть сделаны различные предположения: заявка получает отказ; заявка остается в системе (с общим временем пребывания в системе не более t n ) как претендент на обслуживание вне очереди; заявка поступает в очередь и обслуживается на общих основаниях и т.д.

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

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

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

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

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

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

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

· Структура алгоритма, моделирующего

процесс обслуживания заявок

Рассмотрим однофазную СМО, имеющую n линий, на которые поступают заявки в случайные моменты времени t i . Если вмомент поступления заявки оказываются в наличии свободные линии (их число n св ), заявка занимает одну из них на время t p . В противном случае заявка находится в системе до момента t n , ожидая обслудивания. В т t чение времени ожидания некоторые линии могут освободиться (их число m ), и в этом случае будет возможность обслужить заявку. Если до момента времени t n ни одна из линий не освобождается (m =0 ), заявка получает отказ.

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

Для исследования качества обслуживания заявок предусматривается N * кратное моделирование процесса функционирования системы в интервале (0, T ) . В процессе моделирования число обследованных реализаций обозначим через N .

Алгоритм:

1. Определяется момент t i поступления очередной заявки в систему.

2. Если t i < T , то переход на шаг 3, иначе – на шаг 11.

3. Проверка возможности обслужить поступившую заявку: если n св >0 , то переход на шаг 4, иначе – на шаг 12. (Значение времени поступления заявки t i сравнивается с t осв для всех линий, т.о. выявляются свободные линии.)

4.Если n св >1 , то переход на шаг 5, иначе – на шаг 6.

5. Выбирается номер свободной линии по специальным правилам.

6. Назначается выбранная линия.

7. Проверка: имеет ли место срыв обслуживания по причине недостаточной надежности? Если да, то переход на шаг 8, иначе – на шаг 10.

8. Определение времени t рем ремонта линии, вышедшей из строя (t рем имеет определенный закон распределения).

9. N отк = N отк +1 . Переход на шаг 1.

10. Определение времени занятости t з линии, которая назначена обслуживать заявку (некая случайная величина с определенным законом распределения) и времени освобождения линии: t осв = t i + t з . Переход к очередной заявке (шаг 1).

11. Проверка: если N < N * , то N = N +1 и переход на шаг 1, иначе – обработка результатов опыта и конец.

12. Определить:

А) времени t n пребывания заявки в системе;

Б) число освободившихся каналов m за время t n .

13. Если m >0 , то переход на шаг 14, иначе – на шаг 9.

14. Если m >1 , то переход на шаг 15, иначе – на шаг 6.

15. Выбирается определенная линия в соответствии с принятыми правилами и переход на шаг 6.

ЛЕКЦИЯ 2 (4 часа). МОДЕЛИРОВАНИЕ ВС НА ОСНОВЕ СИСТЕМ И СЕТЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ.

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

Система массового обслуживания (СМО) – это объект, в котором выполняется последовательность операций. Система может осуществлять конечное число операций различного типа. Элемент системы, в котором происходят операции, называется обслуживающим прибором. Физическая и алгоритмическая сущность операций игнорируется.

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

По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные (рис. 2.1.).

DIV_ADBLOCK33">

Сеть массового обслуживания задается следующим набором параметров:

Параметрами источника заявок;

Структурой, определяющей конфигурацию связей и вероятности передачи заявок между узлами сети;

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

Функционирование сети массового обслуживания определяется совокупностью узловых и сетевых характеристик. Узловые характеристики оценивают функционирование каждой СМО и включают в себя характеристики потока заявок, поступающего на вход узла, и весь набор характеристик, присущих СМО. Сетевые характеристики оценивают функционирование сети в целом и включают в себя:

Загрузку – среднее по времени число заявок, обслуживаемых сетью, и одновременно среднее число каналов, занятых обслуживанием;

Число заявок, ожидающих обслуживания в сети;

Число заявок, находящихся в сети (в состоянии ожидания и обслуживания);

Суммарное время ожидания заявки в сети;

Суммарное время пребывания заявки в сети.

Определение стохастических сетей

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

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

Для описания ВС используются разомкнутые и замкнутые стохастические сети. В разомкнутой (открытой) сети интенсивность входного потока заявок https://pandia.ru/text/78/299/images/image004_1.gif" width="614" height="134 src=">.gif" width="16" height="19 src=">

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

В замкнутой сети интенсивность поступления заявок зависит от состояния сети: очередная заявка поступает в сеть только после завершения полного обслуживания одной из предыдущих заявок. Поэтому в замкнутой сети количество заявок постоянно и равно тому числу, которое может одновременно обслуживаться сетью. В данном случае можно говорить о фиктивном источнике DIV_ADBLOCK34">

Если в стохастической сети есть СМО с двумя и более выходами, т. е. такие СМО, после обслуживания которыми поток заявок разветвляется, то задаются правила разветвления потока. В этом случае обычно указывают вероятности передачи заявки по тому или иному пути.

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

2.2. Детерминированные сети очередей.

Рассмотрим систему, которая характеризуется наличием каналов прямого доступа в память со стороны накопителей на лентах (НМЛ) и дисках (НМД), а также со стороны терминалов объекта управления. Схема системы представлена на рис. 2.3.(а)..gif" width="19" height="17 src=">, каналам, каждому из НМД и НМЛ. Современные мультипрограммные ОС поддерживают одновременную обработку заданий путем разделения между ними системных ресурсов. При этом достигается максимальное совмещение прикладных задач пользователей при чередовании обработки на центральном процессоре и периферийных средствах.

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

На рис. 2.3 (б) изображена схема действия процесса, рассматриваемая с позиций проблемного программиста. Операции прикладной программы расположены в порядке их выполнения и включают: 1 – работа прикладной программы (счет 1); 2 – печать данных; 3 – обмен с НМД; 4 – работа прикладной программы (счет 2); 5 – выдача информации на объект управления. Макрокоманды запроса к печати, обмена с НМД и объектом управления интерпретируются управляющими программами ОС и инициируют работу соответствующих каналов. Эти операции пронумерованы следующими цифрами: 6 – выполнение программы управления печатью; 7 – выполнение программы управления НМД; 8 – управляющие действия на терминале объекта. Из рис. 2.3.(б) видно, что выполнение операций прикладной программы и ОС чередуется и в очереди к процессору размещаются запросы на обслуживание различного типа.

https://pandia.ru/text/78/299/images/image009_1.gif" width="13" height="15 src=">.gif" width="12" height="15 src="> - НМД..gif" width="15" height="19 src=">, у которого очередь не возникает, так как число терминалов равно числу процессов в системе. Совокупность узлов и очередей соединена дугами, каждая из которых указывает возможные пути движения процессов. Процесс может занимать ресурс узла или находиться в очереди к нему..gif" width="15" height="19 src=">.gif" width="13" height="19 src=">, являющийся источником заявок. На дуге, соединяющей узлы и https://pandia.ru/text/78/299/images/image017_0.gif" width="40" height="19 src=">, которая указывает на формирование начального значения атрибута-операции, которая становится равной 1..gif" width="13" height="15 src=">.gif" width="41" height="19 src=">. Эта запись указывает как дальнейший путь процесса после операции 1, так и новое значение его атрибута-операции..gif" width="13" height="19 src=">..gif" width="13" height="15 src=">.gif" width="12" height="13 src=">.gif" width="13" height="15 src=">, 6.gif" width="13" height="15 src=">, 7.gif" width="13" height="15 src=">.gif" width="15" height="19 src=">.gif" width="13" height="13 src=">.gif" width="57" height="27 src=">.gif" height="17 src=">-м узле.

2.3. Стохастические сети очередей

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

Сетевая модель с элементами случайности представлена на рис. 2.4. Модель процессора представлена узлом Ввод данных" href="/text/category/vvod_dannih/" rel="bookmark">ввода-вывода данных с НМД описаны двумя последовательными этапами: подвод головки дисковода и поиск информации представлены узлами https://pandia.ru/text/78/299/images/image011_0.gif" width="12" height="15 src=">, а обмен через канал узлом.gif" width="15" height="19 src=">.gif" width="15" height="17 src=">.gif" width="15 height=17 src=" height="17">.gif" width="19" height="17 src=">.gif" width="21" height="24 src="> создается процесс..gif" width="19" height="17 src=">. Если при выполнении программы (операция 1) возникает запрос к базе данных , то процесс переходит к операции 2 (переход 1https://pandia.ru/text/78/299/images/image007_1.gif" width="19" height="17 src="> может быть направлен к одному из накопителей информации..gif" width="13" height="19 src=">,.gif" width="15" height="19 src=">.gif" width="13" height="19 src=">), он получит обслуживание, связанное с позиционированием головок чтения-записи на необходимые цилиндр и сектор..gif" width="13" height="15 src="> обеспечивает создание данных, передаваемых канальной программе..gif" width="19" height="17 src=">, где получает обслуживание, необходимое для выхода из прерывания по обращению к канальной программе и планирования возврата к проблемной программе..gif" width="20" height="15 src=">1). Таким образом, завершается цикл выполнения системных операций по организации обмена данными между основной памятью и диском.

https://pandia.ru/text/78/299/images/image027_0.gif" width="15" height="17 src=">.gif" width="20" height="15 src=">.gif" width="13" height="15 src=">.gif" width="20" height="15 src=">.gif" width="20" height="2 src=">Рассмотрим сети с активными ресурсами (узлами), трудоёмкость выполнения заявки в которых характеризуется временем vir, где r = 1,R - тип заявки и её цепь. Если r-заявки поступают в сеть из внешнего источника и после обслуживания покидают её, сеть называется открытой (разомкнутой) по отношению к цепи r. Сеть, не имеющая внешних источников, называется замкнутой. В смешанных сетях существуют как открытые, так и замкнутые цепи заявок.

В зависимости от области приложений сети с несколькими типами заявок называют либо многоцепными, либо многопродуктовыми. В замкнутых цепях назначают узел, возможно даже фиктивный, который принимают за начало и конец маршрута. Некоторые из узлов могут повторятся в маршрутной цепи несколько раз. Число αir, характеризующее число визитов в узел i заявок маршрута r, называют коэффициентом посещения (передачи).

Коэффициент посещения в стационарном режиме обслуживания можно определить из отношения:

αir = λir / λ0r, (2.1)

где λ0r - интенсивность потока r-заявок из начального узла маршрутной цепи заявок.

λir - интенсивность потока заявок в узел i.

Для разомкнутой цепи величину λ0r задают. Для замкнутой цепи величина λ0r определяется множеством параметров сети и характеризует её производительность (пропускную способность).

В стохастической сети движение r-заявок описывают маршрутной матрицей вероятностей переходов Pr = | pijr |, где pijr - вероятность того, что r-заявка после обслуживания в узле i переходит к узлу j.

В стационарном режиме обслуживания для каждого из узлов записывают следующее условие баланса потоков:

λir = ∑λjir (2.2)

Здесь https://pandia.ru/text/78/299/images/image035_0.gif" width="308" height="138 src=">.gif" width="25" height="2 src=">λir = ∑ pjir λjr, i =0,N. (2.4)

Поскольку для разомкнутой цепи задают поток из внешнего источника λ0r и маршрутную матрицу Pr, то из уравнений (2.1) и (2.4) можно найти λir и αir.

Для замкнутой цепи уравнение балансов потоков (2.4) представляется однородной системой с бесконечным множеством решений. Поэтому для расчёта процессов в замкнутых цепях в качестве исходных данных берут величины λir. Поскольку за полный цикл заявка посещает начальный узел трассы один раз, коэффициент посещения нулевого узла равен единице. Учитывая, что λ0r=1 и подставляя λir = αir λ0r (из (2.1)) в левую и правую части системы уравнений (2.4), получаем уравнения для расчёта коэффициентов посещения замкнутой цепи:

https://pandia.ru/text/78/299/images/image039_0.gif" width="132" height="49 src="> i =0,N, т. е. имеем систему уравнение аналогичную (2.4) для расчёта αir,

https://pandia.ru/text/78/299/images/image041_0.gif" width="90" height="45 src="> i =0,N.

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

Мультиклассовая сеть

https://pandia.ru/text/78/299/images/image042_0.gif" width="29" height="26 src="> |. Элементы DIV_ADBLOCK37">

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

Интенсивность потока заявок в классе s системы i из других систем сети обозначим λis. Уравнения баланса потоков стационарного режима сети имеют вид:

https://pandia.ru/text/78/299/images/image044_0.gif" width="144" height="49 src="> (2.6)

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

· обслуживание в порядке поступления (FiFo);

· разделение времени (PS), предполагающее, что если в узле находится n запросов, то в единицу времени каждому из них будет представлен квант обслуживания длиною 1/n;

· прерывание на основе абсолютных приоритетов с дообслуживанием в обратном порядке(P);

· обслуживание без ожидания (Д)

Первые три способа представляют узлы, обслуживающие с ожиданием (узлы первого типа). Узлы второго типа, представляют индивидуальные ресурсы, закреплённые за процессом.

Введём обозначения:

niq - среднее число заявок класса q в узле i;

ni = ∑q niq - среднее число заявок в узле i;

Kr = ∑i ni - среднее число заявок цепи r;

K = ∑r Kr - число заявок в сети.

Gif" width="14" height="2 src=">.gif" width="14" height="2 src=">.gif" width="14" height="2 src=">Состояние сети описывается вектором n = (n1 ,n2 ,…,ni,…,nN), где ni - состояние узла i .

Gif" width="14" height="2 src=">.gif" width="10" height="2 src=">.gif" width="19" height="26 src="> ,…,SN) = (P1(S1), P2(S2),…,Декомпозиция" href="/text/category/dekompozitciya/" rel="bookmark">декомпозиции (структурирования). Основой классических алгоритмов вычисления G(K) является операция свертки нескольких векторов, которая представима в виде рекуррентных выражений по многомерной схеме Горнера.

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

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

· интенсивность внешних источников пуассоновских потоков – λ0r;

· экспоненциально распределённой трудоёмкостью обслуживания в i-ом узле– vi = 1/μ, где μ - интенсивность обслуживания;

· коэффициентами посещения в i –e узлы - αir.

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

Характеристики сети рассчитывают следующим образом. Загрузка узла i со стороны потока заявок типа r:

https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi , vi = 1/μi, https://pandia.ru/text/78/299/images/image052.gif" width="20 height=26 src=" height="26"> =https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> vi/(1-https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> ).

Воспользовавшись формулой Литла (ni = λiVi), найдём число заявок каждого типа в узле i:

nir = λir Vir = https://pandia.ru/text/78/299/images/image055.gif" width="67" height="39 src="> .

Замкнутые сети. Алгоритм расчёта сети через вероятности состояний.

Для замкнутых марковских сетей вероятности состояний определяются из решений, представимых в форме произведения (2.7). Если сеть состоит из FiFo-узлов, то вероятности состояний:

P(n1 n2…nN) =1/G(K) * Π https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi - загрузка i-ой системы, равная отношению интенсивности потока к интенсивности обслуживания в i-й системе: m =1,K1; n = 1,K2; i = 1,N.Vi2(K1,K2) = vi2. (2.13)

Приведённые зависимости верны, если в FIFO-узлах время обслуживания не зависит от цепи, т. е. vi1 =vi2. В PS-узлах оно может различаться. При необходимости через G можно найти вероятности состояний и другие характеристики.

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

Метод анализа средних (МАС)

МАС может быть легко получен из алгоритма свертки и формул (ni = λiVi) Литла для цепи и узлов сети. Так, в случае одноцепной сети при K1 = K из выражения (2.13) имеем:

Vi(K) = vi. (2.14)

tпреб. tобсл. tожид. vi

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

C(K) = ∑i αiVi(K), (2.15)

получаем:

λ0(K) = K/C, (2.16)

а из формулы Литла для узла находим:

ni(K) = αiλ0(K)Vi(K). (2.17)

Заметим, что ni(0) =0. Рекуррентные вычисления по формулам (2.13) – (2.16) сразу дают искомые характеристики процессов и узлов сети. Загрузку находят из соотношения:

https://pandia.ru/text/78/299/images/image067.gif" width="88" height="39 src="> (2.15)

Рассмотрим более общий случай обслуживания в узлах. Введём величину bi(j), характеризующую ёмкость узла i, когда в нём находится j заявок. Для одноканальных обслуживающих приборов с постоянной скоростью обслуживания bi(j) =1. Для Д-узлов bi(j) =j. Для узлов, скорость обслуживания в которых зависит от нагрузки, имеем 0 < bi(j)<∞. Обычно bi(j) - монотонная неубывающая функция j, т. е.

bi(j) > bi(j-1) и bi(j+1) - bi(j) ≤ bi(j) - bi(j-1).

Например, если в узле находится двухканальный обслуживающий прибор, то bi(1) =1, bi(j) =2 для всех j ≥2.

Ёмкость узла (нагрузочная способность) определяется отношением:

bi(j) = μi(j)/μi(1), (2.19)

где μi(j) - интенсивность обслуживания в узле i, если в нём находится j заявок, а μi(1) - если одна заявка.

Если скорость обслуживания в узле зависит от нагрузки, как это описано формулой (2.19), то время пребывания можно вычислить по формуле:

Vi(K) = vi , (2.20)

где bm - максимальная нагрузочная способность узла i, bm≤K.

https://pandia.ru/text/78/299/images/image069.gif" width="614" height="87 src=">

https://pandia.ru/text/78/299/images/image071.gif" width="26" height="62 src="> Vir(K) = vir,

1 – для FIFO-, PS-узлов;

0 – для Д-узлов.

3. λ0r(K) = Kr/ ∑i αir left">

Рис. 2.5. Порядок обхода узлов при расчёте двухцепной сети с популяцией К = (2,2). ↓ - направление движения линии фронта.

Изображённый на рисунке граф – это не диаграмма состояний сети, а диаграмма возможных объёмов заявок в сети, содержащая несравнимо меньшее число вершин, чем диаграмма состояний. Число вершин в графе не зависит от числа узлов в сети.

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

Сеть массового обслуживания (СеМО) - сеть, которая производит обслуживание поступающих в неё требований. Обслуживание требований в СМО производится обслуживающими приборами. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на:истемы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются;истемы с ожиданием, в которых имеется накопитель бесконечной ёмкости для буферизации поступивших требований, при этом ожидающие требования образуют очередь;истемы с накопителем конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя; при этом требование, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряется.

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

Таким образом, во всякой СМО можно выделить следующие основные элементы:

) входящий поток заявок;

) очередь;

) каналы обслуживания;

) выходящий поток обслуженных заявок.

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

Предметом изучения теории массового обслуживания являются СМО.

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

Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее организации (параметров): характера потока заявок, числа каналов и их производительности и правил работы СМО.

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

Определение: Случайным процессом (или случайной функцией) называется соответствие, при котором каждому значению аргумента (в данном случае - моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае - состояние СМО). массовое обслуживание

Сети массового обслуживания и их применение. Моделирование вс на основе систем и сетей массового обслуживания

Рекомендованный список диссертаций

Влияние самоподобности речевого трафика на качество обслуживания в телекоммуникационных сетях 2005 год, кандидат технических наук Осин, Андрей Владимирович

Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей 2011 год, доктор технических наук Бахарева, Надежда Федоровна

Разработка модели и анализ характеристик обслуживания видеоинформации в узле сети АТМ 2002 год, кандидат технических наук Молчанов, Дмитрий Александрович