Ирина Эланс

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

Компьютерное моделирование. 2

Содержание

Задание

Система передачи данных обеспечивает передачу пакетов данных из пункта А в пункт С через транзитный пункт В. В пункт А пакеты поступают по экспоненциальному закону со средним временем 10 мс. Здесь они буферизуются в накопителе емкостью 15 пакетов и передаются по любой из двух линий АВ1 – за время 20±2 мс или АВ2 – по показательному закону со средним временем равным 20 мс. В пункте В они снова буферизуются в накопителе емкостью 20 пакетов и далее передаются по линиям ВС1 (по показательному закону со среднем временем 25 мс) и ВС2 за 25±2 мс. Причем пакеты из АВ1 поступают в ВС1, а из АВ2 – в ВС2. Чтобы не было переполнения накопителя в пункте В вводится пороговое значение его емкости – 20 пакетов. При достижении очередью порогового значения происходит подключение резервной аппаратуры и время передачи снижается для линий ВС1 и ВС2 15 мс

Смоделировать прохождение через систему передачи данных 1000 пакетов.

Определить среднюю загруженность накопителей.

Введение

На примере задания в упрощенном виде показана актуальная
проблема – эффективность использования сетевого оборудования для передачи сетевого трафика (пакетов).

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

Так анализ работающей системы с возникшими проблемами – уже может являться результатом неправильного проектирования и довольно длителен и трудоемок, то выходом является математическое моделирование системы массового обслуживания. Для этого хорошо подходит среда и язык GPSS (General Purpose Simulation System - Система моделирования общего назначения), позволяющая создать адекватную имитационную модель предметной области, смоделировать длительную работу нагруженной системы за несколько минут, а небольших СМО мгновенно. Также блоки моделирования имеют набор стандартных числовых атрибутов, позволяющих получать распространенную информацию, например среднюю загрузку устройства или накопителя, сразу по результат моделирования.

Разработка математической модели системы

Построение концептуальной модели системы

Система СПД относится по характеру протекающих в ней процессов к системам массового обслуживания.

Концептуально схему описанного задания можно представить, как на рисунке 1:

Концептуальная схема системы

Источник генерирует по экспоненциальному закону каждые 10 мс. Поступающие заявки попадают в очередь в накопитель Н₁ и ожидают в ней, если первый (АВ1) или второй (АВ2) канал заняты. Как только первый или второй канал освобождаются и в накопителе имеются заявки происходит передача пакета в течение 20±2 мс по первому каналу или в течение 20 мс по второму, после чего пакет попадают в накопитель Н₂ и ожидают пока линии не освободятся. Далее из накопителя Н₂ пакеты передаются в канал ВС1 (со временем прохождения 25 мс или ВС2 (25±2), причем пакет, которой прошел через канал АВ1 – передается в канал ВС1, аналогично и с каналами АВ2 и ВС2.

И – источник, формирующий пакеты данных по экспоненциальному закону со средним временем 10 мс, имеющий один выход на накопитель Н₁;

N_п – пакеты, получившие отказ в следствии того, что накопитель Н₁ заполнен;

Н₁ – накопитель емкостью 15 пакетов, из которого происходит выход пакетов на канал К₁₁и К₁₂;

К₁₁ – канал передачи пакетов, по которой передаются пакеты со временем прохождения 20±2 мс, который передает пакеты в накопитель Н₂;

К₁₂ – канал передачи пакетов, по которой передаются пакеты со временем прохождения 20 мс, который передает пакеты в накопитель Н₂;

Н₂ – накопитель емкостью 20 пакетов, из которого происходит выход пакетов на канал К₂₁и К₂₂, причем пакеты из канала К₁₁ поступают в К₂₁, а из К₁₂ в канал К₂₂.

К₂₁ – канал передачи пакетов, по которой передаются пакеты со временем прохождения 25 мс и передаются на выход;

К₂₂ – канал передачи пакетов, по которой передаются пакеты со временем прохождения 25±2 мс и передаются на выход;

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

передача пакета в данной СМО равновероятно происходит по двум маршрутам: А->AВ1->B->ВС1->C или А->AВ2->B->ВС2->C;
время поступления пакетов распределено по экспоненциальному закону с интенсивностью l_В_П=10;
пакеты входного потока при поступлении в СМО направляются на буферизацию в накопитель пункта А, ограниченного емкостью в 15 пакетов;
пакеты из каналов АВ1 и АВ2 направляются в накопитель пункта А, ограниченного емкостью в 20 пакетов;
время ожидания обслуживания пакетов в накопителях пунктов неограниченно;
времена передачи каналов АВ2 и ВС1, а также при заполненном накопителе пункта В и канала ВС2 распределены по экспоненциальному закону с интенсивностями, приведенными в таблице 1.

Формализация концептуальной модели системы

Время передачи по каналу АВ1 20±2 мс, а по каналу ВС2 25±2 мс. Остальные временные показатели элементов СМО распределены по экспоненциальному закону, интенсивности которых приведены в таблице 1.

Таблица 1 – Интенсивности экспоненциального распределения времен поступления и передачи в СМО в мс

Элемент	Входной поток	АВ2	ВС1	Резерв ВС1	Резерв ВС2
Интенсивность	l_ВП=10	l_АВ2=20	l_ВС1=25	l_RBС1=15	l_RBС2=15

В качестве программного обеспечения моделирования заданием на курсовое проектирование задана среда GPSS World, предназначенная для имитационного вероятностного моделирования систем с дискретными и непрерывными процессами. Для моделирования в GPSS World используются динамические и статические объекты. Динамическими объектами являются пакеты, которые создаются в определенных точках модели, продвигаются планировщиком через операторы, а затем уничтожаются. С каждым пакетом связаны параметры, номера или имена которых используются для ссылок на значения, присвоенные параметрам. Пакету может присваиваться приоритет. Приоритет определяет предпочтение, которое получает пакет, когда она и другие пакеты претендуют на один и тот же ресурс. Статические объекты в GPSS World представлены объектами операционной, аппаратной, вычислительной, статистической, запоминающей и группирующей категорий. Каждому объекту соответствуют атрибуты, описывающие его состояние в данный момент времени. Они доступны для использования в процессе моделирования и называются стандартными числовыми атрибутами (СЧА).

В соответствии с заданием на курсовое проектирование с использованием имитационного моделирования в среде GPSS World необходимо смоделировать процесс обработки пакетов в СМО, а также определить среднюю загруженность (коэффициент использования) накопителей, которые являются первичными параметрами имитационного моделирования в среде GPSS World, то есть представляют собой СЧА и определяются автоматически встроенными средствами GPSS. Коэффициент использования накопителя SRj выражается в тысячных долях, его можно получить как элемент стандартного отчета GPSS World Simulation Report. Выводится в графе UTIL раздела информации об устройствах (STORAGE).

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

При детерминированном расчете принимается упрощение, что время поступления пакетов и передачи равно математическому ожиданию их законов распределения. Таким образом для накопителя точки А имеем: заявки в накопитель поступают каждые 10 мс и равновероятно передаются по каналу АВ1 или АВ2, интенсивность передачи каждого из которых в данном случае 20 мс. Таким образом, пакетам не придется ждать передачи в накопителе, а они сразу буду попадать в один из каналов, как только поступят. Значит коэффициент использования накопителя точки А будет равен 0. Стоит отметить, что это верно лишь для детерминированного анализа, а при имитационном моделировании ситуация будет отличаться.

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

Разработка структурной схемы имитационной модели и описание ее функционирования

Разработка моделируемого алгоритма

Укрупненная схема

детальная схема блока обслуживания
заявки каналом 2-ой фазы

детальная схема обслуживания заявки
каналом первой фазой

Моделирование потока требований выполняется с помощью оператора GENERATE:

GENERATE (Exponential(1,0,10))

Затем пакет передается в накопитель nakopA емкостью 20. Пакет там будет находиться до тех пор, пока не поступит сообщение об освобождении канала. Для этого используется оператор SEIZE, который определяет занятость канала, и при освобождении последнего отправляет пакет по каналу:

SEIZE АВ1

Далее должно быть задано время пребывания заявки в устройстве обслуживания. Для этого используется оператор ADVANCE:

ADVANCE 20,2

После обслуживания заявка должна освободить устройство:

RELEASE АВ1.

Аналогично происходит с каналом АВ2 и каналами ВС1 и ВС2 (в канал ВС1 пакет приходит из накопителя 2).

Выход заявки из системы моделируется следующим оператором (в поле операнда задается число удаляемых из системы заявок):

TERMINATE 1

Описание программной реализации имитационной модели

Рассмотрим принципиальные особенности реализации имитационной вероятностной модели СМО в среде GPSS World.

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

Листинг программной реализации имитационной вероятностной модели СМО в среде GPSS World имеет следующий вид (листинг 1).

Оценка адекватности модели

На языке GPSS модель заняла всего 37 блоков. Процесс моделирования происходит мгновенно. Как видно из стандартного отчета GPSS (листинг 2, находится в разделе 3), пакеты попадают в каждый блок модели, что свидетельствует о том, что нет «мертвых участков».

Значение поля ENTRY COUNT блока 37 с меткой OUT, равное 1000 свидетельствует о том, что за время моделирования СМО покидает ровно 1000 переданных пакетов.

Искомые коэффициенты использования накопителей, находятся в блоке отчета STORAGE в поле UTIL. их значения для накопителя А = 0.885 (88.5%) для накопителя В = 0.786 (78.6%). Данные значения подтверждают описанные в пункте 1.2 предположения о том, что коэффициент использования накопителя А не будет равен 0, а коэффициент использования накопителя В будет велик.

Для дополнительной проверки проведем эксперимент с имитационной моделью с изменением интенсивности входного потока.

Эксперимент с имитационной моделью

Результаты эксперимента по моделированию процесса передачи 1000 пакетов в заданной СМО были получены в виде полного стандартного отчета GPSS World Simulation Report, приведенного ниже (листинг 2).

Cтандартный отчет GPSS World Simulation Report

1.Общая информация о результатах работы модели:

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 20333.647 37 2 2

NAME VALUE

AB1 10002.000

AB2 UNSPECIFIED

BC1 10003.000

BC2 UNSPECIFIED

DOPBC1 29.000

DOPBC2 33.000

NAKOPA 10000.000

NAKOPB 10001.000

OUT 37.000

TOAB1 3.000

TOAB2 9.000

TOBC1 15.000

TOBC2 22.000

2. Информация о блоках:

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 1989 0 0

2 TRANSFER 1989 956 0

TOAB1 3 ENTER 1033 15 0

4 SEIZE 1018 0 0

5 LEAVE 1018 0 0

6 ADVANCE 1018 1 0

7 RELEASE 1017 0 0

8 TRANSFER 1017 0 0

TOAB2 9 ENTER 0 0 0

10 SEIZE 0 0 0

11 LEAVE 0 0 0

12 ADVANCE 0 0 0

13 RELEASE 0 0 0

14 TRANSFER 0 0 0

TOBC1 15 ENTER 1017 16 0

16 SEIZE 1001 1 0

17 GATE 1000 0 0

18 LEAVE 588 0 0

19 ADVANCE 588 0 0

20 RELEASE 588 0 0

21 TRANSFER 588 0 0

TOBC2 22 ENTER 0 0 0

23 SEIZE 0 0 0

24 GATE 0 0 0

25 LEAVE 0 0 0

26 ADVANCE 0 0 0

27 RELEASE 0 0 0

28 TRANSFER 0 0 0

DOPBC1 29 LEAVE 412 0 0

30 ADVANCE 412 0 0

31 RELEASE 412 0 0

32 TRANSFER 412 0 0

DOPBC2 33 LEAVE 0 0 0

34 ADVANCE 0 0 0

35 RELEASE 0 0 0

36 TRANSFER 0 0 0

OUT 37 TERMINATE 1000 0 0

3. Информация о блоках типа «канал»:

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

AB2 535 0.985 20.991 1 1018 0 0 0 13

AB1 490 0.861 20.032 1 1034 0 0 0 2

BC2 530 0.929 19.971 1 1004 0 0 0 4

BC1 472 0.997 24.072 1 992 0 0 0 15

4. Информация о блоках типа «накопитель»:

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

NAKOPA 15 0 0 15 1040 1 13.270 0.885 0 76

NAKOPB 20 0 0 20 1021 1 15.711 0.786 0 2

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

Cтандартный отчет GPSS World Simulation Report

1.Общая информация о результатах работы модели:

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 15207.505 37 4 2

NAME VALUE

AB1 10003.000

AB2 10002.000

BC1 10005.000

BC2 10004.000

DOPBC1 29.000

DOPBC2 33.000

NAKOPA 10000.000

NAKOPB 10001.000

OUT 37.000

TOAB1 3.000

TOAB2 9.000

TOBC1 15.000

TOBC2 22.000

2. Информация о блоках:

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 1005 0 0

2 TRANSFER 1005 0 0

TOAB1 3 ENTER 525 0 0

4 SEIZE 525 0 0

5 LEAVE 525 0 0

6 ADVANCE 525 1 0

7 RELEASE 524 0 0

8 TRANSFER 524 0 0

TOAB2 9 ENTER 480 1 0

10 SEIZE 479 0 0

11 LEAVE 479 0 0

12 ADVANCE 479 1 0

13 RELEASE 478 0 0

14 TRANSFER 478 0 0

TOBC1 15 ENTER 524 0 0

16 SEIZE 524 0 0

17 GATE 524 0 0

18 LEAVE 524 0 0

19 ADVANCE 524 0 0

20 RELEASE 524 0 0

21 TRANSFER 524 0 0

TOBC2 22 ENTER 478 1 0

23 SEIZE 477 0 0

24 GATE 477 0 0

25 LEAVE 477 0 0

26 ADVANCE 477 1 0

27 RELEASE 476 0 0

28 TRANSFER 476 0 0

DOPBC1 29 LEAVE 0 0 0

30 ADVANCE 0 0 0

31 RELEASE 0 0 0

32 TRANSFER 0 0 0

DOPBC2 33 LEAVE 0 0 0

34 ADVANCE 0 0 0

35 RELEASE 0 0 0

36 TRANSFER 0 0 0

OUT 37 TERMINATE 1000 0 0

3. Информация о блоках типа «канал»:

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

AB2 479 0.687 21.799 1 1003 0 0 0 1

AB1 525 0.687 19.903 1 1005 0 0 0 0

BC2 477 0.782 24.938 1 1001 0 0 0 1

BC1 524 0.892 25.901 1 0 0 0 0 0

4. Информация о блоках типа «накопитель»:

STORAGE CAP. REM. MIN. MAX. ENTRIES AVL. AVE.C. UTIL. RETRY DELAY

NAKOPA 15 14 0 14 1005 1 2.247 0.150 0 0

NAKOPB 20 19 0 19 1002 1 5.298 0.265 0 0

Как и предполагалось коэффициенты использования снизились для накопителя А = 0.150 (15%) для накопителя В = 0.265 (26.5%).

Также, как видно из отчета в блоках 29-36 за время моделирования не было не одной заявки, в этих блоках находится реализация передачи с помощью резервной аппаратуры. То, что аппаратура не должна была включаться свидетельствует значение стандартного числового атрибута накопителя пункта В – максимальной длины, в отчете оно приведено в поле МАХ. и равно 19 (в отчете листинга 2 атрибут МАХ. имеет значение 20). Таким образом подтверждается и верность проектирования СМО и правильность реализации логики подключения резервного оборудования.

Заключение

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

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

Литература

Советов Б.Я., Яковлев С.А. Моделирование систем. Учебник для вузов. – М.: Высш. шк., 2005. – 343c.

Тарасик В.П. Математическое моделирование технических систем. – Мн.: Дизайн ПРО, 2004. – 640c.

Боев В.Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. – СПБ.: БХВ – Петербург, 2004. – 348c.

Кудрявцев Е.М. GPSS World: основы имитационного моделирования различных систем. – М.: ДМК Пресс, 2004. – 317c.

Соболь И.М. Метод Монте-Карло. – М.: Наука, 1978. – 64с.

Murata T. Petri Nets: Properties, Analysis and Applications // Proceedings of the IEEE. – 1989. –Voll.77. – №4.

Khoromskaia V. Petri Nets Based Modelling of Control Flow // Вестник РУДН, серия «Прикладная и компьютерная математика». – 2004. –№1. – С. 74-84.

O.E. Shestopalova, S.A. Skriplenok Ingproject – Petri Nets Software Tool for Queuing Systems Simulation // Проблемы проектирования и производства РЭС: Сборник материалов Международной научно-технической конференции. Секция «Информатика». - Новополоцк: ПГУ, 2008г. – С. 91-94.

Модель СМО на языке GPSS

;***объявление накопителей***

nakopA STORAGE 15 ;накопитель пункта А

nakopB STORAGE 20 ;накопитель пункта В

;***Генерация пакетов***

GENERATE (Exponential(1,0,10)) ;поступления пакетов в СМО 1 в 10мс

TRANSFER BOTH,toAB1,toAB2 ;переход к линии передачи АВ1 или АВ2

;***линии передачи и накопители***

;***------- Участок А-В ------------***

;---линия АВ1---

toAB1 ENTER nakopA ;пакет буферизуется в накопителе пункта А

SEIZE AB1 ;занимает линию передачи АВ1

LEAVE nakopA ;пакет покидает накопитель пункта А

ADVANCE 20,2 ;задерживается на время передачи

RELEASE AB1 ;освобождает линию передачи АВ1

TRANSFER ,toBC1 ;переход пакета к линии передачи ВС1

;---линия АВ2---

toAB2 ENTER nakopA ;пакет буферизуется в накопителе пункта А

SEIZE AB2 ;занимает линию передачи АВ2

LEAVE nakopA ;пакет покидает накопитель пункта А

ADVANCE (Exponential(1,0,20)) ;задерживается на время передачи

RELEASE AB2 ;освобождает линию передачи АВ2

TRANSFER ,toBC2 ;переход пакета к линии передачи ВС2

;***----------------------------------------***

;***------- Участок В-С ------------***

;***--- Обычное обслуживание В-С ---***

;---линия ВС1---

toBC1 ENTER nakopB ;пакет буферизуется в накопителе пункта B

SEIZE BC1 ;занимает линию передачи ВC1

GATE SNF nakopB,dopBC1 ;если накопитель заполнен, переход по метке

LEAVE nakopB ;пакет покидает накопитель пункта B

ADVANCE (Exponential(1,0,25)) ;задерживается на время передачи

RELEASE BC1 ;освобождает линию передачи ВC1

TRANSFER ,OUT ;переход пакета к выходу из СМО

;---линия ВС2---

toBC2 ENTER nakopB ;пакет буферизуется в накопителе пункта B

SEIZE BC2 ;занимает линию передачи ВC2

GATE SNF nakopB,dopBC2 ;если накопитель заполнен, переход по метке

LEAVE nakopB ;пакет покидает накопитель пункта B

ADVANCE 25,2 ;задерживается на время передачи

RELEASE BC2 ;освобождает линию передачи ВC2

TRANSFER ,OUT ;переход пакета к выходу из СМО

;***--------------------***

;***--- Обслуживание с подключенными резерва В-С ---***

Компьютерное моделирование. 2 📙 Контрольная → 🆔 45516