Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНОБРНАУКИ
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Нерсесянц А.А.
Методические указания
к выполнению лабораторного практикума
по курсу лекций «Теория построения инфокоммуникационных систем и сетей» для студентов физического факультета ЮФУ
Направление подготовки – инфокоммуникационные технологии и системы связи
Изучение способов анализа структурных элементов
инфокоммуникационных систем методами имитационного моделирования в системе GPSS World
Ростов-на-Дону
2013
Методические указания разработаны профессором кафедры Радиофизики Физического факультета ЮФУ
Нерсесянцем Альфредом Аванесовичем
Ответственный редактор – доктор физико-математических наук, профессор Г.Ф. Заргано
Печатается в соответствии с решением кафедры
Радиофизики Физического факультета ЮФУ,
Протокол № 3 от 28.09.2013 г.
1. Вводные замечания по использованию системы
моделирования GPSS World
Дружественный пользовательский интерфейс системы GPSS World позволяет работать с ней, владея лишь общей компьютерной грамотностью, и во многих случаях рассматривать приведённый ниже набор программ как некоторый чёрный ящик. В то же время необходимо дать хотя бы минимальные сведения о порядке запуска программ, способах изменения параметров и доступа к результатам моделирования.
1.1. Запуск моделирующей программы.
Щёлкнуть на ярлыке GPSSW на рабочем столе и далее по кнопке Открыть (2-я кнопка слева на шкале инструментов). В появившемся перечне выбрать один из модулей по указанию преподавателя и вывести его на рабочий стол.
Для запуска программы нажмите последовательно: Command > Create Simulation > Command > Start. В появившемся окне Start Command установите продолжительность эксперимента в виде числа вызовов (транзактов) вводимых в систему. Учесть, что чем продолжительнее эксперимент, тем точнее результат моделирования (меньше дисперсия). Для целей лабораторной работы можно ограничиться числом транзактов, равным, например, 10000 или 100000. Нажав ОК, Вы запускаете моделирующую программу, а после её завершения и доступ к стандартному отчёту.
1.2. Доступ к результатам моделирования.
Основные результаты моделирования представляются в стандартном отчёте, который автоматически выводится на рабочий стол по окончании прогона. Конкретные значения отчёта рассматриваются последовательно по мере выполнения занятий.
Для доступа к матрицам и гистограммам, при их наличии в данном модуле, необходимо нажать следующие кнопки: Window>Simulation Window и далее Matrix Window или Table Window.
1.3. Внесение изменений в параметры моделируемой системы.
Параметры, подлежащие изменению (интенсивность входного потока, число каналов, канальная скорость и др.), указываются в каждом конкретном задании.
Для внесения изменений в исходный модуль программы нужно вызвать этот модуль, нажав кнопку Window и в открывшемся меню вызвать имя программы под номером 1. Необходимо помнить, что ЭВМ выполняет вычисления не с исходным, а с машинным модулем. Поэтому после любых изменений в исходном модуле необходимо снова запускать программу транслятор запуском : Command > Create Simulation (или Retranslate).
Не забывайте после каждого прогона обнулять предыдущую статистику нажатием кнопок Clear или Reset. При выходе из программы по окончании занятия помните, что все изменения и получаемые результаты сохранению не подлежат.
Для более детального изучения основ компьютерного моделирования можно обратиться к монографии [1], а для овладения навыками моделирования на GPSS World следует обратиться к учебному пособию [2].
В отчёте по практическим занятиям необходимо по каждому пункту представлять программы с комментариями и основные результаты прогонов.
Изучить функции использованных операторов и операндов, а также содержание стандартных отчётов.
2. Практические занятия
Практическое занятие № 1.
Объект исследования. Одноканальное устройство с неограниченной очередью.
Одноканальные устройства широко применяются в современных телекоммуникационных системах. Вся сеть Internet на 3-м уровне семиуровневой модели представляет собой множество маршрутизаторов, связанных между собой одноканальными линиями связи. Основная работа маршрутизатора состоит в следующем:
- получив IP-пакет, маршрутизатор анализирует его адресную часть и определяет направление его дальнейшей передачи;
- если канал в выбранном направлении свободен, то он занимается для передачи этого пакета;
- если канал занят передачей ранее пришедшего пакета, то данный пакет устанавливается в очередь (записывается в буфер ожидания) и будет обслужен по мере освобождения канала.
При анализе работы IP-сетей наибольший интерес представляет время задержки пакета в маршрутизаторе (ожидание в очереди + передача по каналу).
В реальных маршрутизаторах объём буфера (длина очереди), конечно, ограничен. Но в данном занятии мы предварительно рассмотрим теоретическую модель с неограниченной очередью, как более простую.
Строго говоря, поступивший в маршрутизатор пакет не сразу поступает на обработку в одно из исходящих из маршрутизатора направлений. Предварительно пакет должен обработаться в устройстве анализа адреса (обычно специальный микропроцессор) для выбора направления дальнейшей передачи пакета. С точки зрения теории массового обслуживания это типичная двухфазная схема. Однако, пренебрегая временем работы микропроцессора по сравнению с временем передачи пакета по каналу (что как правило соответствует действительности), рассмотрим процесс передачи пакета через маршрутизатор как работу одноканального устройства.
Листинг 1 - Имитационная модель - модуль 1 - Модель одноканального устройства с неограниченной очередью.
; Модель одноканального устройства с неограниченной очередью.
generate 20 ;генерация транзактов (пакетов) с интервалом 20 е.м.в.
queue fff ;установить транзакт в очередь с именем fff
seize kkk ;занять канал с именем kkk
depart fff ;уйти из очереди fff
advance 19 ;задержать транзакт в канале на 19 е.м.в.
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
е.м.в. – единица модельного времени.
Задание. Тщательно изучите каждый оператор и приведенные операнды по комментариям.
Произвести запуск программы (command > start) на длину прогона в 10000 транзактов.
Изучить содержимое стандартного отчета (REPORT), особенно в части характеристик обслуживающего устройства (канала) и очереди.
Обратите внимание на то, что данная модель статистически устойчива только, если длительность задержки транзакта (операнд А оператора advance) меньше интервала между моментами появления транзактов (операнд А оператора generate).
Убедитесь в этом, изменив соотношение операндов на противоположное и проведя два эксперимента с различной длиной прогона. Объясните причину зависимости длины очереди (AVE. CONT) от длины прогона.
В исходном варианте отсутствие в операторах generate и advance операндов В исключает случайность в работе устройства, что, как правило, не соответствует реальной ситуации. Исключение составляют, например, системы наблюдения, в которых различные датчики через равные промежутки времени выдают в центральный пункт сообщения одинаковой длины.
Внесите случайность в работу модели, добавив операнды В:
generate 20,20 - длительность интервала между моментами появления транзактов будет меняться от 0 до 40 .
advance 19,10 - длительность задержки транзакта в канале будет меняться от 9 до 29.
Сравните данные в новом отчёте с предыдущими и объясните произошедшие изменения.
Практическое занятие № 2.
Объект исследования. Одноканальное устройство с ограниченной очередью.
Наиболее типичная ситуация для маршрутизаторов в сетях с коммутацией пакетов. Важно отметить, что ограничение очереди в маршрутизаторах производится не столько с целью экономии буферной памяти (память, как известно, стремительно дешевеет), сколько из необходимости ограничить время пребывания пакетов в узлах сети. Застрявший сверх допустимого времени пакет, во-первых, утрачивает свою актуальность (возможно, что он уже не нужен получателю), а во-вторых, находясь в очереди, этот пакет задерживает тех, которые приходят в узел после него. Выбор наиболее целесообразного ограничения для длины очереди – сложнейшая оптимизационная задача. Слишком длинные очереди в сети приводят, как уже отмечалось, к большим задержкам пакетов в сети, а слишком короткие – увеличивают потери пакетов, т.к. пакет, поступивший в узел при занятости всех мест ожидания в нужном направлении, покидает систему и считается потерянным.
Ограничить очередь в имитирующей программе можно различными способами. Например, можно добавить в предыдущий модуль оператор test:
test L q$fff,10,met ;очередь меньше десяти?
Данный оператор проверяет на «меньшее» текущую длину очереди с именем fff (стандартный числовой атрибут q$fff) с числом 10 и, если оно не меньше (вспомогательный операнд L), то направляет транзакт к метке met.
Таким образом, обслуживание транзакта (пакета) продолжается только в том случае, если в очереди есть свободные места. В противном случае с помощью оператора savevalue к переменной otk прибавляется единица.
Листинг 2 - Имитационная модель - модуль 2 - Модель одноканальной системы с ограниченной очередью.
; Модель одноканальной системы с ограниченной очередью.
generate 20,20 ;генерация транзактов (пакетов) с интервалом 20 е.м.в.
test L Q$fff,10,met ;есть свободные места в очереди?
queue fff ;Да. Установить транзакт в очередь с именем fff
seize kkk ;занять канал с именем kkk
depart fff ;уйти из очереди fff
advance 19,10 ;задержать транзакт в канале на 19 е.м.в. (в среднем)
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
met savevalue otk+,1 ;зафиксировать отказ в переменной otk
terminate 1
Задание. Запустите программу и проанализируйте отчет.
Снимите зависимости:
- Tож (ρ) для 4-х значений ρ в пределах от 0,5 до 1,5;
- P(ρ) – вероятность потери транзакта.
Здесь: Tож – среднее время ожидания в очереди (AVE.TIME в REPORT), а ρ = tзад/tинт – загрузка канала, определяемая как отношение времени задержки транзакта в операторе advance к интервалу между моментами появления транзактов в операторе generate. Вероятность потерь определяется как отношение числа потерянных пакетов (переменная otk) к общему числу вошедших в систему пакетов (устанавливается командой Start).
В теории телетрафика величина ρ является главным параметром, определяющим степень загруженности обслуживающей системы. При этом ρ определяется как ρ = λt, где λ – интенсивность входного потока требований, а t – длительность обслуживания. Значение ρ может меняться от 0 до 1 и при приближении к 1 такие параметры как длительность ожидания или длина очереди резко возрастают (теоретически до бесконечности).
Практическое занятие № 3.
Построение гистограммы распределения времени ожидания в
очереди.
Дополнить программу Модуль 2 оператором:
wtime qtable fff,0,50,40
поставив его перед оператором generate. Операнд А (fff) – имя очереди, операнд В (0) – начало гистограммы по оси абсцисс, операнд С (50) – длина интервала в единицах модельного времени, операнд D (40) – число интервалов. Подобрать операнды B, C, и D для наглядного представления гистограммы на экране монитора.
Листинг 3 - Имитационная модель - модуль 3 - Построение гистограммы
; Пример построение гистограммы
generate wtime qtable fff,0,50,40,
20,20 ;генерация транзактов (пакетов) с интервалом 20 е.м.в.
test L Q$fff,10,met ;есть свободные места в очереди?
queue fff ;Да. Установить транзакт в очередь с именем fff
seize kkk ;занять канал с именем kkk
depart fff ;уйти из очереди fff
advance 19,10 ;задержать транзакт в канале на 19 е.м.в.
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
met savevalue otk+,1 ;зафиксировать отказ в переменной otk
terminate 1
Задание. Зарисовать гистограмму в отчёте. Сопоставить ориентировочные данные, представляемые гистограммой, с точными значениями, приведёнными в отчёте в соответствующей таблице.
Практическое занятие № 4
Объект исследования. Многоканальное устройство с ограниченной очередью.
Многоканальные устройства являются наиболее массовой структурой в телефонных сетях с коммутацией каналов. Узлы коммутации и многочисленные АТС связываются между собой стандартными телефонными каналами, число которых может достигать нескольких тысяч.
Принцип работы многоканального устройства с явными потерями состоит в следующем: поступивший вызов пытается занять свободный канал в некоторой соединительной линии для установления телефонного соединения и, если такой свободный канал находится, то он занимается. Если в многоканальном устройстве (в пучке каналов) все каналы заняты, то вызов получает отказ и считается потерянным. По соотношению числа потерянных вызовов (n) к общему числу вызовов, поступивших за время наблюдения (N), определяется главная характеристика системы с потерями – вероятность потери вызова Р = n/N.
В отличие от предыдущей модели в данную модель внесено изменение, связанное с реализацией многоканальной схемы.
В системе GPSS используются разные операторы для занятия и освобождения каналов в одноканальных и многоканальных устройствах, а именно seize или release для одноканальных систем и enter или leave – для многоканальных. При этом число каналов в многоканальной системе задаётся отдельным оператором storage (см. листинг) с именем МКУ, в котором указывается число каналов (в данном случае определено, что в МКУ с именем ggg имеется 10 каналов). Оператор gate snf передаст транзакт на обслуживание только при не заполненности МКУ (дополнительный операнд snf). В противном случае транзакт будет учтён как потерянный в переменной с именем ot.
Листинг 4 - Имитационная модель - модуль 4 - Потери в многоканальной системе
;Вероятность потерь в многоканальной системе с ограниченной очередью
kan storage 10 ;установка числа каналов
generate 8,8 ;генерация интервалов между вызовами
test l Q$och,7,met ;есть свободные места в очереди?
queue och ;Да.Установить транзакт в очередь
enter kan ;занять канал
depart och ;освободить место в очереди
advance 100,100 ;задержать транзакт на время обслуживания
leave kan ;освободить канал
terminate 1 ;покинуть систему
met savevalue otk+,1 ;увеличить число потерь на единицу
terminate 1 ;покинуть систему
Задание. Запустите программу и проанализируйте отчет.
Снимите зависимости:
- Tож (v) для 4-х значений ρ в пределах от 0,5 до 1,5;
- P(v) – вероятность потери транзакта.
В данном случае ρ =tзад/vtинт , где v – число каналов, задаваемое оператором storage.
Практическое занятие № 5.
Объект исследования. Модель разделения потока транзактов на 3 разно приоритетных потока.
Телекоммуникационные системы, как правило, рассматривают вызовы, обладающие различными приоритетами. Особенно необходимо дифференцировать качество обслуживания вызовов (QoS) в мультисервисных сетях. Известно, что потоковые виды трафика (речь, видео) требуют первоочередного обслуживания, так как допустимое время задержки в сети для них находится в пределах 150 – 250 мс, а файловый обмен данными не критичен к задержкам и их значения могут доходить до нескольких секунд.
Реальные маршрутизаторы анализируют требования по приоритетности передачи (классы обслуживания - CoS), находящиеся в заголовке пакета, и в соответствии с этими требованиями организуют несколько очередей для выдачи пакетов в каждый канал. Наиболее часто реализуется так называемая процедура относительных приоритетов, при которой при каждом освобождении канала выбирается очередной пакет из наиболее приоритетной очереди.
Имитационная модель. В системе GPSS реализовано 128 приоритетов, принимающих номера от нуля до 127. При генерации транзакта оператором generate ему присваивается самый низший приоритет «0», если иное не указано в операнде 5 оператора generate. Этот приоритет может быть при необходимости изменён в любом месте программы с помощью оператора priority конкретным указанием нового приоритета (например, priority 17) или в более сложных случаях с помощью функции как в приведённом ниже примере. Наивысшему приоритету может быть присвоен номер 127.
Листинг 5 - Имитационная модель - модуль 5 - Распределение приоритетов
;Распределение транзактов по приоритетам
sss function rn1,d3 ;аргумент – случайное число (rn1)
.5,1/.8,15/1,7 ;функция – числа 1, 15 или 7
generate 30,20
priority fn$sss ;присвоение приоритетов по функции sss
advance 1000
terminate 1
Операторы priority и function с именем sss разделят общий поток транзактов случайным образом (датчик случайных чисел rn1) на 3 потока. При этом 50% всех транзактов получит приоритет №1, 30% - №15 и 20% - №7. Аргументом функции в данном случае является случайное число, выбираемое в интервале 0 – 1, а функцией – номер нового приоритета для транзакта. Оператор advance с чрезмерно большой задержкой (операнд 1000) позволяет сохранить в отчёте все сгенерированные транзакты и наблюдать присвоенные им приоритеты.
Задание. Объясните структуру оператора priority. Измените операнды оператора function для разделения общего потока транзактов на 2, а потом на 4 приоритета.
Практическое занятие № 6.
Объект исследования. Модель системы с 3-я разно приоритетными очередями транзактов.
Исследуется маршрутизатор IP-пакетов в сети с коммутацией пакетов. Анализируется процедура выдачи пакетов в канал связи с заданной пропускной способностью СМбит/с. Разноприоритетные потоки для выдачи в этот канал поступают из нескольких входящих каналов с суммарной интенсивностью Λ = Σ λi , где λi – интенсивность потока i-го приоритета (i = 0 ÷ 127).
Соотношение между потоками определяется исследователем в зависимости от конкретной ситуации. Основные исследуемые характеристики – длительности задержек пакетов в узле в зависимости от канальной скорости, интенсивности суммарного потока и соотношением между интенсивностями потоков различных приоритетов.
Листинг 6 - Имитационная модель - модуль 6 - Исследование очереди с приоритетами
; Модель очередей с приоритетами
sss function rn1,d3 ;функция случайного распределения приорите
.5,1/.8,2/1,5 тов с вер. 0.5, 0.3 и 0.2
och function pr,d3 ;функция распределения длин очередей по при
1,30/2,15/5,7 оритетам
generate 20,20 ;генерация транзактов с интервалом 20 е.м.в.
priority fn$sss ;выбор номера приоритета
assign ocher,pr ;присвоение имени очереди номера приоритета
test L Q*ocher,fn$och,met ;есть свободные места в очереди?
queue pr ;Да. Установить транзакт в очередь с именем 1,2 или 5
seize kkk ;занять канал с именем kkk
depart pr ;уйти из очереди
advance 19,10 ;задержать транзакт в канале на 19 е.м.в.
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
met savevalue otk+,1 ;зафиксировать отказ в переменной otk
terminate 1
Особенностью данной программы является использование в операторах queue и depart в качестве имени очереди номера приоритета (pr). Это дает возможность использовать одни и те же операторы для транзактов любого приоритета. В данном случае именами очереди будут цифры 1, 2 или 5.
Для этого используется оператор assign, который может вошедшему в него транзакту определить имя параметра и присвоить этому параметру заданное значение. В данном случае параметру с именем ocher присваивается числовое значение по номеру приоритета (1, 2 или 5). В дальнейшем этот параметр будет использоваться как имя очереди в операторе test L.
Оператор test L сравнивает на “меньше” текущую длину очереди под номером приоритета (Q*ocher), хранящегося в параметре транзакта ocher, с числом мест в приоритетных очередях, определяемых функцией с именем och. В исходном варианте данного модуля длины допустимых очередей по приоритетам равны соответственно 30-и, 15-и и 7-и.
Задание. Произведите прогон Модуля 6 и проанализируйте отчёт в части очередей с именами 1,2 и 5. Измените длины очередей в функции с именем och, произведите прогон и объясните изменения в отчёте.
Измените операнды оператора generate так, чтобы суммарный поток был равен 400 пакетов/с. Меняя с помощью оператора advance пропускную способность канала от 200 до 600 пакетов/с, снимите зависимости длительностей задержек пакетов Тожi и вероятностей потерь пакетов Р по каждому приоритету в зависимости от пропускной способности канала.
Измените программу Модуль 6 так, чтобы она имитировала многоканальную систему. Снимите зависимости средней длительности ожидания Тожi (значение AVE.TIME в REPORT) и средней длины очереди Dочi (значение AVE.CONT в REPORT) по каждой категории от числа каналов. Если значения откликов Тожi и Dочi исчезающе малы, измените параметры системы так, чтобы исследуемые зависимости оказались наиболее наглядными.
Практическое занятие № 7.
Объект исследования. Пуассоновское распределения потоков различных событий.
Один из наиболее часто используемых в теории телетрафика простейший поток вызовов описывается пуассоновским распределением:
Рi(t) =
где: λ – интенсивность входящего потока вызовов [выз/ед.вр.],
t – интервал времени [ед.вр],
Рi(t) – вероятность появления ровно i вызовов в интервале t.
Пуассоновский поток вызовов непосредственно связан с экспоненциальным распределением тем, что интервалы (z) между вызовами пуассоновского потока распределены по экспоненте: Р (z < t) = 1 -. А так как в операторе генерации транзактов generate устанавливаются именно интервалы между вызовами, то в модуле 7 реализован экспоненциальный генератор со средним интервалом равным 2 (это означает, что интенсивность вызовов составляет 0,5 выз/ед.вр.).
Программа работает следующим образом. Оператор «generate 100» нарезает временной процесс на равные интервалы времени в 100 е.м.в. (единицы модельного времени). В это время оператор «generate (2#v$eks)» генерирует случайное число транзактов, которое фиксируется в счётчике sch. Содержимое этого счётчика в начале каждого интервала в 100 е.м.в. табулируется и счётчик обнуляется.
Листинг 7 - Имитационная модель - модуль 7 - Построение пуассоновского распределения
;Построение пуассоновского распределения
tab table x$sch,10,2,40 ;построение гистограммы
eks fvariable -log((1+rn8)/1000) ;экспон.распределение
generate (2#v$eks) ;генерация пуассоновского потока
savevalue sch+,1 ;счётчик событий в интервале t
terminate
generate 100 ;генерация интервалов t
tabulate tab ;фиксация числа событий в инт. t
savevalue sch,0 ;обнуление счётчика событий в инт.t
terminate 1 ;общее число интервалов t
Задание. Снять гистограмму пуассоновского распределения. Рассчитать теоретическое распределение по формуле Пуассона. Проверить гипотезу о законе распределения исследуемой случайной величины по критерию согласия χ2 (см. приложение).
Практическое занятие № 8.
Объект исследования. Пуассоновское распределение входящего потока и экспоненциальное распределения длительности обслуживания.
Рассмотренные в предыдущих занятиях объекты функционировали при интервалах между вызовами и длительностях обслуживания распределёнными по закону равномерной плотности. Для этого в операторах generate и advance в качестве операнда В использовалось постоянное число. Однако в реальных телекоммуникационных системах гораздо чаще встречаются интервалы, распределённые по экспоненциальному закону. Это относится как к пуассоновскому входящему потоку, в котором интервалы между вызовами распределены по экспоненте, так и к длительности обслуживания.
Как правило, вызовы подчиняются пуассоновскому закону, если они исходят от большого количества источников (теоретически бесконечного), ни один из которых не является превалирующим. Экспоненциальное распределение длительности занятия каналов характерно для телефонных разговоров. Применительно к передаче данных время передачи пакета по каналу прямо пропорционально его длине, т.е. количеству байт (бит) в нём. И если длину пакета аппроксимировать экспоненциальным распределением (что нередко соответствует действительности), то можно и длительность занятия канала передачей одного пакета считать распределённой по экспоненте.
Реализация экспоненциального распределения для длительностей обслуживания и интервалов между вызовами осуществляется с помощью логарифмической функции t = - ln ξ. В листинге программы эту функцию выполняет оператор fvariable:
fvariable -log((1+rn8)/1000).
При этом среднее значение интервалов между транзактами устанавливается непосредственно в операторе generate (средний интервал между вызовами в данном случае установлен равным 2 емв), а средняя длительность задержки в операторе advance (транзакты задерживаются в среднем на 3 емв).
Листинг 8 - Имитационная модель - модуль 8 - Реализация пуассоновского и экспоненциального распределений
*реализация пуассоновского входного потока и экспоненциального
*распределения длительности обслуживания
tab table m1,0,0.2,100 ;гистограмма задержек
eks fvariable -log((1+rn8)/1000) ;экспоненциальное распределение
generate (2#v$eks) ;генерация потока
advance (3#v$eks) ;задержка транзакта
tabulate tab ;табуляция задержек
terminate 1
В операторе fvariable датчик случайных чисел rn8 при каждом обращении к нему выбирает случайное целое число в диапазоне от 0 до 999. Делением на 1000 эти числа переносятся в диапазон от 0 до 0.999. Чтобы избежать ситуации «log 0» к значению rn8 прибавляется 1 и окончательно диапазон чисел для логарифмирования устанавливается от 0.001 до 1.
Для построения гистограммы задержек в операторе table присутствует операнд m1, являющийся СЧА, определяющим время жизни транзакта. Операнды B, C и D определяют формат гистограммы по оси абсцисс.
Задание. Зафиксировать 3 – 4 гистограммы задержек при различных значениях входящего потока.
Практическое занятие № 9.
Объект исследования. Многоканальное устройство с явными потерями.
В данном занятии проводится анализ многоканального устройства средствами двух методов математического моделирования: аналитического и имитационного. Методы аналитического моделирования многоканальных устройств описаны в многочисленных работах по теории телетрафика. В большинстве случаев эти работы рассматривают системы с пуассоновским входящим потоком вызовов и с экспоненциальным распределением длительности обслуживания. В связи с этим для сопоставительного анализа многоканальной системы двумя методами необходимо использовать модель системы с экспоненциальным распределением как для интервалов между вызовами, так и для длительностей задержек.
Аналитическая модель
Наиболее реальную ситуацию при ограниченном числе каналов (v < ∞) отражает распределение Эрланга (усечённое распределение Пуассона), представленное на рисунке 1:
Рi = i = 0,v (*)
где Рi – вероятность того, что в случайный момент времени в v-канальном устройстве занято i каналов,
У = λt – нагрузка на v-канальную систему, зависящая от интенсивности потока вызовов λ и средней длительности занятия каналов t.
Наиболее важным в распределении Эрланга является состояние i = v, т.е. состояние, когда заняты все каналы. Разумеется, что это то состояние, когда наступают потери (отказы в обслуживании), т.е.
Рi = Рv = Рt = Рв = Рн = Ev (У).
Здесь значения Рt, Рв и Рн являются вероятностями потерь по времени, по вызовам и по нагрузке соответственно.
Последнее обозначение Ev (У) является общепринятым обозначением формулы Эрланга. Наиболее частая практическая задача определения необходимого число линий в пучке для обслуживания поступающей нагрузки при заданной вероятности потерь данной формулой в явном виде не решается, т.к. невозможно выразить число каналов v как функцию от У и Р. В связи с этими трудностями формула Эрланга табулирована в различных справочниках и задачниках. Кроме того в последнее время появилось несколько удобных программ, позволяющих очень легко из трёх величин – нагрузка (У), число каналов (v) и вероятность потерь Р – найти любую при двух других известных.
P(i)
Распределение Эрланга
Распределение. Пуассона
i
0 1 2 3 4 5 v=6 7 8 9
Рисунок 1. Огибающие распределений вероятностей чисел занятых каналов для простейшего входящего потока.
Имитационная модель. В программном модуле, реализованы экспоненциальные распределения для интервалов между вызовами и длительностей задержек. Кроме того, реализован модуль, обеспечивающий построение гистограммы для сопоставления результатов имитационного моделирования с аналитическими результатами по формуле Эрланга.
Листинг 9 - Имитационная модель - модуль 9 - многоканальная система с потерями
*анализ многоканальной системы с потерями
raspr table s$ggg ;гистограмма Рi
ggg storage 10 ;установка числа каналов
eks fvariable -log((1+rn8)/1000) ;экспоненциальное распределение
generate (2#v$eks);генерация вызовов
gate snf ggg,met ;многоканальное устройство не заполнено?
enter ggg ;Да. Занять канал
advance (18#v$eks);задержать транзакт
leave ggg ;освободить канал
terminate ;вывести транзакт из системы
met savevalue ot+,1 ;зафиксировать очередной отказ
terminate ;вывести транзакт из системы
generate 50
tabulate raspr
terminate 1
Задание. Открыть Модуль 9 и запустить модель.
1. Построить распределение Эрланга по формуле (*) при нагрузке У = 9 Эрл и числе каналов v = 10. Нагрузка определяется как У = λt , где λ определяется по операнду А оператора generate (λ = 1/tинтерв) , а t – по операнду А оператора advance (t – длительность задержки).
2. Снять гистограмму для распределения числа занятых каналов при той же нагрузке У = 9 Эрл. для пуассоновского входного потока и экспоненциального обслуживания. В исходном варианте (модуль 9) установлено У = 0.5*18 = 9 Эрл.
3. Снять гистограмму для распределения числа занятых каналов при той же нагрузке У = 9 Эрл. при равномерно распределённом входном потоке и равномерно распределённой длительности обслуживания. Установить для этого generate 2,2 и advance 18,18.
4. Сравнить полученные экспериментальные зависимости (п.2 и п.3) с теоретическим распределением Эрланга по критерию согласия χ2. (См. приложение).
Практическое занятие №10
Объект исследования. Одноканальная система с бесконечной очередью, с пуассоновским входным потоком и экспоненциальным обслуживанием.
Такая чисто теоретическая система является наиболее исследованной в теории массового обслуживания и поэтому в наибольшей степени подходит для сопоставительного изучения методов аналитического и имитационного моделирования.
Аналитическая модель
Основной характеристикой, наиболее часто используемой для практических расчётов, является вероятность ожидания для поступившего вызова Р(γ > 0), где γ – время ожидания. По существу, это вероятность того, что вызов до начала обслуживания будет ожидать освобождения канала. Для простейшего потока вызовов эта вероятность совпадает с вероятностью занятости всех каналов или с вероятностью потерь по времени:
Р(γ > 0) = Р≥v = Pt = = = Dv (У).
В данном случае суммирование проводится по всем состояниям (i), при которых заняты все каналы и имеется очередь любой длины: от нуля до бесконечности. Расчётное соотношение для вероятности ожидания полученное Эрлангом, называется второй формулой Эрланга, обозначается как Dv (У) и табулировано для практического применения. Таблицы, как и в случае первой формулы позволяют по любым двум из трех параметров – У, v, P – определить третий. Здесь Dv (У) является общепринятым обозначением
2-й формулы Эрланга, которая табулирована во многих источниках.
Очень важно отметить, что одноканальная система с неограниченной очередью может быть статистически устойчива только при У < 1. В противном случае очередь к каналу будет расти до бесконечности, в чём можно убедиться, сопоставив результаты прогонов разной длительности (например, в 10000 и 50000 транзактов).
Вышеприведённые соотношения сделаны для произвольного числа каналов v. В данном занятии v = 1, а в следующих занятиях будут рассмотрены системы с v > 1.
Листинг 10 - Имитационная модель - модуль 10 - одноканальная система с бесконечной очередью
*анализ одноканальной системы с бесконечной очередью
eks fvariable -log((1+rn8)/1000) ;экспоненциальное распределение
generate (20#v$eks) ;генерация транзактов (пакетов) с средним интервалом 20 е.м.в.
queue fff ;установить транзакт в очередь с именем fff
seize kkk ;занять канал с именем kkk
depart fff ;уйти из очереди fff
advance (19#v$eks);задержать транзакт в канале в среднем на 19 е.м.в.
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
Данная имитационная модель почти полностью аналогична модели занятия № 1. Исключение составляют операнды в операторах generate и advance, в которых равномерные распределения интервалов заменены на экспоненциальные.
Задание. Открыть Модуль 10 и запустить модель.
1.Построить по таблицам Dv(У) график зависимости вероятности ожидания Р(γ > 0) от нагрузки У при изменении аргумента в пределах
0.2 < У < 0.9.
2. Построить на том же графике эмпирическую зависимость вероятности ожидания (параметр канала UTIL) от тех же аргументов. Напомним, что нагрузка подсчитывается как У = tз / tи, где tз – время задержки транзакта в операторе advance, а tи – длительность интервалов между вызовами в операторе generate.
3. Построить 3 графика по п. 1 и 2, меняя длительность прогона (10000, 100000 и 1000000). Объяснить имеющиеся различия.
Практическое занятие № 11
Объект исследования. Многоканальная система с бесконечной очередью с пуассоновским входным потоком и экспоненциальным обслуживанием. В данном занятии исследуются различные характеристики многоканальных устройств с бесконечной очередью.
а) Средняя длина очереди
Аналитически средняя длина очереди определяется как:
S̅ = = У Dv (У)/(v – У) = Λ Р(γ > 0)/(v – У)
Здесь v – число каналов в системе, а остальные параметры имеют тот же смысл, что и в занятии № 10. Отметим, что в многоканальных системах условием статистической устойчивости является неравенство У < v, т.е. только в этом случае очередь не будет расти до бесконечности.
Экспериментально средняя длина очереди (S̅) по результатам прогона фиксируется непосредственно в стандартном отчёте в параметре AVE.CONT.
Листинг 11 - Имитационная модель - модуль 11 – анализ средней длины очереди
;Определение средней длины очереди
ggg storage 5 ;число каналов в пучке
eks fvariable -log((1+rn8)/1000) ;экспон.распределение
generate (2#v$eks) ;генерация пуассоновского потока
queue fff ;установить транзакт в очередь с именем fff
enter ggg ;Занять канал
depart fff ;уйти из очереди fff
advance (3#v$eks) ;обслуживание с экспон. распределением
leave ggg ;освободить канал
terminate 1
Задание. Исследовать зависимость расхождений результатов аналитической и имитационной моделей от величины Р(γ > 0). Параметры моделей (Λ, v, n) установить идентичными. Результаты представить графически.
б) Вероятность превышения длиной очереди заданной величины n
Аналитически эта вероятность определяется с использованием второй формулы Эрланга:
Р(S > n) = = (У / v)n+1 Dv (У) = (У / v)n+1 Р(γ > 0)
Для получения аналогичной вероятности на имитационной модели необходима достаточно сложная программа. Поэтому ниже приводится программа, позволяющая получить несколько приближённую оценку. Причём разница в результатах аналитической и имитационной моделей будет тем меньше, чем меньше эти вероятности.
Листинг 11а - Имитационная модель - модуль 11а
;Вероятность превышения установленной длины очереди (приблизительно)
ggg storage 5 ;число каналов в пучке
eks fvariable -log((1+rn8)/1000) ;экспон.распределение
generate (2#v$eks) ;генерация пуассоновского потока
test L Q$fff,10,met ;есть свободные места в очереди?
queue fff ;установить транзакт в очередь с именем fff
enter ggg ;Занять канал
depart fff ;уйти из очереди fff
advance (8#v$eks) ;обслуживание с экспон. распределением
leave ggg ;освободить канал
terminate 1
met savevalue otk+,1 ;зафиксировать отказ в переменной otk
terminate 1
Приближённый характер данной модели заключается в том, что реализуется очередь ограниченной длины, равной параметру n, и вместо вероятности превышения длиной очереди заданной величины n, имитационная модель определяет вероятность потери транзакта из-за ограниченной очереди.
Задание. Исследовать зависимость расхождений результатов аналитической и имитационной моделей от величины Р(γ > 0). Параметры моделей (Λ, v, n) установить идентичными. Результаты представить графически.
в) Вероятность ожидания свыше допустимого времени.
Это так называемые условные потери.
Аналитически эта величина получается достаточно просто:
Р(γ > tд) = (γ > tд) Pi = Dv (У) = Р(γ > 0)
Здесь величина tд выражена в условных единицах времени (у.е.в.). Условные единицы времени широко применяются в теории телетрафика, т.к. позволяют абстрагироваться от конкретных астрономических единиц (час, мин, мкс) и получать математические выражения в унифицированном виде. Определяется как 1у.е.в. = tср.обсл. т.е. через среднюю длительность обслуживания.
На имитационной модели вероятность Р(γ > tд) определяется по гистограмме в стандартном отчёте. Точнее по таблице в отчёте, в которой по вертикали откладывается время, а в последнем столбце – накопленные проценты.
Листинг 11б - Имитационная модель - модуль 11б
;Вероятность ожидания свыше допустимого времени t
ggg storage 5 ;число каналов в пучке
wtime qtable fff,0,0.5,40 ;распределение длит. ожидания
eks fvariable -log((1+rn8)/1000) ;экспон.распределение
generate (2#v$eks) ;генерация пуассоновского потока
queue fff ;установить транзакт в очередь с именем fff
enter ggg ;Занять канал
depart fff ;уйти из очереди fff
advance (3#v$eks) ;обслуживание с экспон. распределением
leave ggg ;освободить канал
terminate 1
Задание. Снять зависимость вероятности Р(γ > tд) от допустимого времени tд. Пределы изменения tд подобрать так, чтобы Р(γ > tд) изменялось примерно от 0,001 до 0,1. При этом соответствующим образом нужно подбирать операнды в операторе qtable.
г) Средняя длительность ожидания рассматривается в двух вариантах:
- γ̅з - средняя длительность ожидания для задержанных вызовов, т.е. подсчитанная только среди тех, которые поступили на обслуживание после некоторого ожидания;
- γ̅ - средняя длительность ожидания для всех вызовов, т.е. для любого поступившего независимо от процедуры ожидания.
Аналитически оба параметра подсчитываются по формулам:
γ̅з = 1/(v – У), γ̅ = γ̅з Dv (У) = Dv (У) / (v – У) = Р(γ > 0) / (v – У)
Здесь величины γ̅з и γ̅ выражены в условных единицах времени (у.е.в.).
Эмпирически эти параметры выводятся непосредственно в стандартном отчёте в строке queue:
γ̅з – AVE.(-0), γ̅ - AVE.TIME
Задание. Построить на одном графике зависимости средних длительностей ожидания от степени загрузки канала: γ̅з (ρ) и γ̅ (ρ) для аналитических и эмпирических наблюдений. Объяснить результаты наблюдений.
Практическое занятие № 12.
Модель двухфазной системы с потерями.
Реальные телекоммуникационные системы никогда не состоят из одного обслуживающего устройства. Например, в ЛВС созданный в компьютере пользователя пакет, прежде чем попасть в канал доступа к Internet, в зависимости от конфигурации ЛВС пройдёт через несколько обслуживающих устройств (фаз обслуживания): каналы, коммутаторы, маршрутизатор. Каждое из этих устройств, строго говоря, тоже нельзя рассматривать как отдельное обслуживающее устройство. Например, в коммутаторе мы можем отдельно рассматривать работу входного порта (контроллера), центрального процессора, различных модулей ПО, общей шины, выходного порта. Причём такую детализацию можно продолжить. Например, в работе центрального процессора можно отдельно рассматривать работу АЛУ, управляющего устройства, памяти, интерфейсов.
В данном занятии исследуется система с двухфазным обслуживанием. Каждый транзакт должен обслуживаться вначале каналом с именем rrr , а затем каналом с именем kkk. Если к моменту поступления транзакта к любому из каналов данный канал занят (проверка оператором gate nu), то транзакт фиксируется как потерянный в переменных ot1 или ot2 в зависимости от номера фазы.
Листинг 12 - Имитационная модель - модуль 12
;модель двухфазной системы обслуживания с потерями
;с одним входным потоком
generate 20,20 ;генерация транзактов (пакетов) с интервалом 20 е.м.в.
gate nu rrr,otk1 ;устройство rrr свободно?
seize rrr ;Да. Занять канал с именем rrr
advance 29,20 ;задержать транзакт в канале на 29 е.м.в.
release rrr ;освободить канал с именем rrr
vtor gate nu kkk,otk2 ;Вторая фаза. Устройство kkk свободно?
seize kkk ;Да. Занять канал с именем kkk
advance 19,19 ;задержать транзакт в канале на 19 е.м.в.
release kkk ;освободить канал kkk
terminate 1 ;вычесть 1 из длины прогона
otk1 savevalue ot1+,1 ;Потеря транзакта в 1-й фазе
terminate 1 ;вычесть 1 из длины прогона
otk2 savevalue ot2+,1 ;Потеря транзакта во 2-й фазе
terminate 1 ;вычесть 1 из длины прогона
Задание. Откройте программу Модуль 12 и запустите её. Определите степень загрузки каждого канала и долю потерянных транзактов в каждой фазе. Определите суммарную вероятность потери транзактов в двух фазах.
Приложение
Критерии согласия для проверки гипотез
Критерии согласия применяются для проверки гипотезы о законе распределения исследуемой случайной величины. Во многих практических задачах точный закон распределения неизвестен. Поэтому выдвигается гипотеза о соответствии имеющегося эмпирического закона, построенного по наблюдениям, некоторому теоретическому. Данная гипотеза требует статистической проверки, по результатам которой будет либо подтверждена, либо опровергнута.
Критерий согласия Пирсона - χ2 – один из основных, который можно представить как сумму отношений квадратов расхождений между теоретическими и эмпирическими частотами к теоретическим частотам:
χ2 =
Для распределения χ2 составлены таблицы, где указаны критические значения критерия согласия χ2 для выбранного уровня значимости α и степеней свободы k.
Число степеней свободы k определяется как число групп в ряду распределения (s) минус число связей: k = s – r. Под числом связей понимается число показателей эмпирического ряда, использованных при вычислении теоретических частот, т.е. показателей, связывающих эмпирические и теоретические частоты. Например, при выравнивании по кривой распределения Эрланга или нормального распределения имеется три связи. Поэтому число степеней свободы определяется как k = s – 3. Для распределения Пуассона число k = s – 2.
При полном совпадении теоретического и эмпирического распределений
χ2 = 0, в противном случае χ2 > 0. Если χ2расч > χ2табл, то при заданном уровне значимости и числе степеней свободы гипотезу о несущественности (случайности) расхождений отклоняем. В случае, если χ2расч< χ2табл гипотезу принимаем и с вероятностью Р можно утверждать, что расхождение между теоретическими и эмпирическими частотами случайно.
Пример. Проверим гистограмму, полученную в занятии 9 для 9-и канального устройства, на соответствие распределению Эрланга. В данном случае число групп в ряду распределения (число интервалов гистограммы) равно 10. Поэтому эмпирические и расчётные данные сводим в таблицу 1.
Таблица 1
|
i |
Pi |
ni |
mi |
ni - mi |
(ni - mi)2 |
(ni - mi)2/ni |
|
1 |
||||||
|
2 |
||||||
|
3 |
||||||
|
4 |
||||||
|
5 |
||||||
|
6 |
||||||
|
7 |
||||||
|
8 |
||||||
|
9 |
||||||
|
10 |
||||||
|
χ2 = Σ |
Эмпирические данные для данной таблицы mi берутся непосредственно из отчёта модуля 9. Расчётные значения вычисляются как ni = Pi*N, где Pi определяется по формуле Эрланга (можно воспользоваться программой erlangcalc), а N соответствует длине прогона (число, устанавливаемое при команде Start).
После этого проверяется гипотеза по таблице 2 о соответствии гистограммы распределению Эрланга. В нашем случае число степеней свободы
k = s – 3 =10 – 3 = 7. Пусть в результате расчета по таблице 1 оказалось, что χ2 = 2,5. Тогда по таблице 2 для k = 7 находим, что 2.17< χ2<2.83, и делаем вывод о том, что с вероятностью Р, лежащей между 0.9 и 0.95, гипотеза о соответствии эмпирического распределения распределению Эрланга является правдоподобной.
Таким образом, любой критерий согласия не подтверждает однозначно правильность гипотезы о законе распределения исследуемой случайной величины. Критерий лишь определяет вероятность правильности гипотезы. А при проверке нескольких гипотез (например, соответствие эмпирического распределения нормальному или эрланговскому) можно принять более вероятную.
|
k |
Вероятность P(χ2 > χα2) |
||||||||
|
0.99 |
0.95 |
0.90 |
0.7 |
0.50 |
0.3 |
0.10 |
0.05 |
0.01 |
|
|
1 |
0.00016 |
0.0039 |
0.016 |
0.148 |
0.455 |
1.074 |
2.71 |
3.84 |
6.63 |
|
2 |
0.020 |
0.103 |
0.211 |
0.713 |
1.39 |
2.41 |
4.61 |
5.99 |
9.21 |
|
3 |
0.115 |
0.352 |
0.584 |
1.424 |
2.37 |
3.66 |
6.25 |
7.81 |
11.3 |
|
4 |
0.297 |
0.711 |
1.06 |
2.20 |
3.36 |
4.88 |
7.78 |
9.49 |
13.3 |
|
5 |
0.554 |
1.15 |
1.61 |
3.00 |
4.35 |
6.06 |
9.24 |
11.1 |
15.1 |
|
6 |
0.872 |
1.64 |
2.20 |
3.83 |
5.35 |
7.23 |
10.6 |
12.6 |
16.8 |
|
7 |
1.24 |
2.17 |
2.83 |
4.67 |
6.35 |
8.38 |
12.0 |
14.1 |
18.5 |
|
8 |
1.65 |
2.73 |
3.49 |
5.53 |
7.34 |
9.52 |
13.4 |
15.5 |
20.1 |
|
9 |
2.09 |
3.33 |
4.17 |
6.39 |
8.34 |
10.66 |
14.7 |
16.9 |
21.7 |
|
10 |
2.56 |
3.94 |
4.87 |
7.27 |
9.34 |
11.78 |
16.0 |
18.3 |
23.2 |
|
11 |
3.05 |
4.57 |
5.58 |
8.15 |
10.3 |
12.90 |
17.3 |
19.7 |
24.7 |
|
12 |
3.57 |
5.23 |
6.30 |
9.03 |
11.3 |
14.01 |
18.5 |
21.0 |
26.2 |
|
13 |
4.11 |
5.89 |
7.04 |
9.93 |
12.3 |
15.12 |
19.8 |
22.4 |
27.7 |
|
14 |
4.66 |
6.57 |
7.79 |
10.82 |
13.3 |
16.22 |
21.1 |
23.7 |
29.1 |
|
15 |
5.23 |
7.26 |
8.55 |
11.72 |
14.3 |
17.32 |
22.3 |
25.0 |
30.6 |
|
16 |
5.81 |
7.96 |
9.31 |
12.62 |
15.3 |
18.42 |
23.5 |
26.3 |
32.0 |
|
17 |
6.41 |
8.67 |
10.1 |
13.53 |
16.3 |
19.51 |
24.8 |
27.6 |
33.4 |
|
18 |
7.01 |
9.39 |
10.9 |
14.44 |
17.3 |
20.6 |
26.0 |
28.9 |
34.8 |
|
19 |
7.63 |
10.1 |
11.7 |
15.35 |
18.3 |
21.7 |
27.2 |
30.1 |
36.2 |
|
20 |
8.26 |
10.9 |
12.4 |
16.27 |
19.3 |
22.8 |
28.4 |
31.4 |
37.6 |
Список использованной литературы