Методические указания к курсовой работе

2.1 Технология Ethernet

Технология Ethernet была разработана в исследовательском центре компании Xerox в 70-х годах и достигла своего нынешнего лидирующего положения в 80-х. Впервые термин Ethernet был использован Робертом Меткалфом в статье, написанной им в этом исследовательском центре в мае 1973 года.

В соответствии с протоколом CSMA (Carrier-Sense Multiple Access – метод доступа к сети с контролем несущей), рабочая станция вначале слушает сеть, чтобы определить, не передается ли в данный момент какое-либо другое сообщение. Если “слышит­ся” несущий сигнал (carrier tone), значит, в данный момент сеть занята другим сообщением - рабочая станция переходит в режим ожидания и находится в нем до тех пор, пока сеть не освободится. Когда в сети наступает молчание, станция начинает передачу. Collision Detection (метод обнаружения конфликтов) - служит для разре­шения ситуаций, когда две или более рабочие станции пытаются передавать сообщения одновременно. Если две станции начнут передавать свои пакеты одновременно, передаваемые данные наложатся друг на друга и ни одно из со­общений не дойдет до получателя. Такую ситуацию называют конфликтом или коллизией (сигналы одной станции перемешаются с сигналами другой).

Если одна из станций обнаружит коллизию, она посылает специальный сигнал, предупреждающий другие станции о произошедшем конфликте. При коллизии уничтожаются все данные в сети. После коллизии станции пытаются передать свои данные повторно. Для того, чтобы предотвратить одновременную передачу, был разработан специальный механизм прерываний, который предписывает каждой станции выждать случайный промежуток времени перед повторной передачей. Станция, которой достался самый короткий период ожидания, первая из них совершит попытку передать данные. После первого конфликта каждая станция ждет 0 или 1 единицу времени, прежде чем попытается возобновить передачу. Если снова произошел конфликт, что может быть, если две станции выбрали одно и то же число, то каждая из них выбирает одно из четырех случайных чисел: 0, 1, 2, 3. Если и в третий раз произошел конфликт, случайное число выбирается из ин­тервала 0-7 и т. д. После десяти последовательных конфликтов интервал вы­бора случайных чисел фиксируется и становится равным 0-1023. После шестнадцати конфликтов контроллер отказывается от дальнейших попыток передать кадр и сообщает об этом компьютеру. Все дальнейшие действия по выходу из сложившейся ситуации осуществляются под руководством протоко­лов верхнего уровня. Такой алгоритм позволяет разрешить коллизии, когда кон­фликтующих станций немного.

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

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

Данные, передаваемые в сети Ethernet, разбиты на кадры. Практически каждой сетевой технологии (независимо от ее уровня) соответству­ет единица передачи данных: Ethernet-кадр, АТМ-ячейка, IP-дейтаграмма и т. д. Данные по сети в чистом виде не передаются. В сети Ethernet к единице данных «пристраивается» заголовок. В некоторых сетевых технологиях добавляется также окончание. Заголовок и окончание несут служебную информацию и со­стоят из определенных полей.

Следует отметить, что минимальная допустимая длина кадров Ethernet составляет 64 байта, а максимальная — 1518 байт. Так как на служебную информацию в кадре отводится 18 байт, то поле «Данные» может иметь длину от 46 до 1500 байт. Если передаваемые по сети данные мень­ше допустимой минимальной длины, кадр будет автоматически дополняться до 46 байт. Столь жесткие ограничения на минимальную длину кадра введены для обеспечения нормальной работы механизма обнаружения коллизий.

2.2 Аналитическое моделирование сети Ethernet

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

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

Входящий Очередь Устройство Выходящий

поток, λ μ поток

Рисунок 1 – Одноканальная СМО

Отношение ρ = λ/μ называется коэффициентом загрузки, который определяет какую часть времени устройство было занято на протяжении всего времени наблюдения за СМО.

В этом случае формулы Полячека-Хинчина для определения средней длины очереди и среднего времени ожидания имеют вид

(1)

2.3 Имитационное моделирование сети Ethernet

В качестве базовой модели взята модель 10-мегабитной сети Ethernet, разработанной Minuteman Software и представленной в /8/.

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

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

Сообщения поступают экспоненциально и бывают двух типов: короткие и длинные. Выбирается узел и удерживается в течение передачи сообщения и всех выдержек времени в случае коллизии. Каждый узел Ethernet может быть занят одним сообщением до тех пор, пока оно не будет отправлено или пока не произойдет некоторое количество коллизий (во время попыток передачи другими узлами), после чего объявляется постоянная ошибка и узел освобождается. Время измеряется в миллисекундах. Подразумевается, что отдельные узлы отстоят друг от друга на 2,5 м. При расчете окна коллизии для определения разделяющего расстояния используется идентификационный номер узла. Задержки распространения между смежными узлами равны 0,01 микросекунды. Каждый бит перемещается за 0,1 микросекунды. Межкадровый интервал моделируется путем задержки сети передающим узлом на некоторое дополнительное время, после того как он передал свое сообщение. Сообщения представлены транзактами GPSS. Узлы и сеть представлены устройствами GPSS. Дополнительное устройство используется во время передачи преднамеренных помех для предотвращения начала передачи нового сообщения. Коллизия возникает из-за нескольких одновременных попыток передачи 2 или более узлов. Задержка распространения сигнала препятствует одновременному распознаванию узлов друг другом, тем самым, приводя к возможности коллизии. Интервал времени, в течение которого сигнал из другого узла может быть обнаружен, называется «окном коллизии». Коллизия представлена лишением передающего транзакта права занимать Ethernet и отправкой его в подпрограмму выдержки времени. Новый занимающий транзакт передает преднамеренные помехи в Ethernet и затем сам выдерживает некоторый временной интервал. Когда отправляется сообщение транзакта, транзакт занимает устройство Ethernet с приоритетом 0 и может быть вытеснен (PREEMPT) только транзактом с приоритетом 1. Когда транзакт передает преднамеренные помехи, он занимает устройство Ethernet с приоритетом 1 и не может быть вытеснен.

2.3.1 Листинг базовой программы

* Аргументы:

* 1. Node__Count - Количество узлов, отстоящих друг от друга на 2.5 м.

* 2. Min_Msg - Минимальное сообщение (бит).

* 3. Max_Msg - Максимальное сообщение (бит).

* 4. Fraction_ Short_ Msgs — Доля коротких сообщений (в долях от тысячи)

* 5. Intermessage_Time - Общий интервал между сообщениями.

* Исходные данные:

* Node_Count = 100 - Общее число узлов Ethernet.

* Intermessage_Time = 1.0 - Среднее значение общего количества сообщений, поступающих каждую миллисекунду.

* Min_Msg = 512 - Минимальное сообщение в битах.

* Max_Msg = 12144 - Максимальное сообщение в битах.

* Fraction Short Msgs = 600 - Короткие сообщения (в долях от тысячи).

* Slot_time = 0.0512 - Время прохождения 512 битов.

* Jam_Time = 0.0032 - Время прохождения 32 битов.

* Backoff_Limit = 10 - Не больше, чем 10 повторов в случае коллизии.

* Interframe_Time = 0.0096 - Время прохождения 96 битов.

*****************************************************************************

Node_Count EQU 100

Intermessage_Time EQU 1.0

Min_Msg EQU 512

Max_Msg EQU 12144

Fraction_Short_Msgs EQU 600

Slot_Time EQU 0.0512

Jam_Time EQU 0.0032

Backoff_Limit EQU 10

Interframe_Time EQU 0.0096

********************************************************************

* Определение функций и переменных GPSS

*

*****************************************************************************

Backoff_Delay VARIABLE Slot_Time#V$Backrandom

Backrandom VARIABLE 1+(RN4@((2AV$Backmin)-1))

Backmin VARIABLE (10#(10'L'P$Retries))+(P$Retries#(10'GE'P$Retries))

Node_Select VARIABLE 1+(RN3@Node_Count)

Collide VARIABLE ABS ((X$Xmit_Node-P$Node_ID)/100000)'GE' (ACl-X$Xmit_Begin)

Msgtime VARIABLE (0.0001)#V$Msgrand

Msgrand VARIABLE Min_Msg+(RN1'G'Fraction_Short_Msgs)#(Max_Msg-Min_Ms)

*****************************************************************************

*

* Диаграмма задержки сообщений
*

*****************************************************************************

Msg_Delays QTABLE Global_Delays,1,1,20

*****************************************************************************

*

* Главная часть модели
*

*****************************************************************************

* Генерация сообщений

*****************************************************************************

GENERATE (Exponential(1,0,Intermessage_Time))

ASSIGN Node_ID,V$Node_Select

ASSIGN Message_Time,V$Msgtime

ASSIGN Retries,0

*******************************************************************

*******************************************************************

QUEUE Global_Delays

SEIZE P$Node_ID

Try_To_Send PRIORITY 1

SEIZE Jam;

RELEASE Jam

TEST E F$Ethernet,l,Start_Xmit

*******************************************************************

*

* Ethernet занят. Проверим, находимся ли мы в окне коллизии передающего узла.

* Если это так, данный узел в любом случае начнет передачу, т.к. несущая не

* будет обнаружена. В этом случае мы должны инициировать коллизию.

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

*******************************************************************

TEST E V$Collide,I,Start_Xmit

* * * * * * * * * * * * * * * * Коллизия * * * * * * * * * * * * * * * * * * * * * *
Collision PREEMPT Ethernet,PR,Backoff,,RE

SEIZE Jam

ADVANCE Jam_Time

RELEASE Jam

RELEASE Ethernet

PRIORITY 0

Backoff ASSIGN Retries+,1

TEST LE P$Retries,Backoff_Limit,Xmit_Error

ADVANCE V$Backoff_Delay

TRANSFER,Try_To_Send

*****************************************************************************

* Занятие Ethernet и начало передачи.

*****************************************************************************

Start_ Xmit SEIZE Ethernet

SAVEVALUE Xmit_Node,P$Node_ID

SAVEVALUE Xmit_Begin,AC1

PRIORITY 0

ADVANCE P$Message_Time

ADVANCE Interframe_Time

RELEASE Ethernet

Free_ Node RELEASE P$Node_ID

DEPART Global_Delays

TERMINATE

*****************************************************************************

Xmit_Error SAVEVALUE Error_Count+, 1

TRANSFER,Free_Node

*****************************************************************************

*

* Сегмент таймера

*

*****************************************************************************

GENERATE 1000

TERMINATE 1

*****************************************************************************

2.3.2 Запуск процесса моделирования

Выберите Command / Create Simulation (Команда / Создать процесс моделирования).

Откроем диаграмму задержки сообщений, выберите Window / Simulation Window / Table Window (Окно / Окно процесса моделирования / Окно «Таблица»), в выпадающем списке диалогового окна уже выбрана таблица MSG_DELAYS. Нажмите ОК.

Расположите это окно так, чтобы вы могли одновременно видеть и окно «Journal» («Жур­нал»), и диаграмму в окне «Table» («Таблица»), Теперь запустим процесс моделирования. Выберите Command / START (Команда / START), так как нам нужен счетчик завершения, рав­ный 1, в диалоговом окне нажмите ОК.

Когда сообщения проходят через Ethernet, в Q-таблице Msg_Delays регистрируется продол­жительность их передачи, и мы можем наблюдать их накопление в диаграмме (рисунок 2).

Рисунок 2 – Q-таблица в конце процесса моделирования

Процесс мо­делирования завершится, когда будет смоделирована 1 секунда работы. В окне «Table» («Таб­лица») мы можем видеть, что среднее время задержки сообщений составило немногим меньше одной миллисекунды.

Когда процесс моделирования закончится, GPSS World запишет отчет в файл отчета с име­нем Ethernet. 1.1 (по умолчанию).

2.3.3 Анализ результатов базовой модели

Сейчас взглянем на отчет. Двигайтесь вниз к разделу, посвященному устройству, которое пред­ставляет сеть Ethernet. Оно использовалось в среднем на 48%. Посмотрим на количество входов в блок с меткой Collision. В течение процесса моделирования было 3 коллизии. То есть на одно сообщение приходится 0.003 коллизии. Закройте окно «Report» («Отчет»), при этом вам не нужно сохранять отчет.

Очевидно, что сеть действует удовлетворительно. Теперь посмотрим на эффект добавления N = 100 дополнительных рабочих станций.

Щелкните на окне «Journal» («Журнал»), убедитесь, что оно удобного для просмотра размера. Выберите Command / CLEAR (Команда / CLEAR). Теперь мы изменим некото­рые параметры эксперимента. Мы сделаем это с помощью интерактивной команды. Сначала изменим количество рабочих станций. Выберите Command / Custom... (Команда / Ввести...), наберите Node_Count EQU 100. Нажмите [Enter].

Теперь другой параметр - общий интервал между поступлением сообщений. Во второй стро­ке наберите Intermessage_Time EQU 1.0# (100/200).

Нажмите ОК. Запустим процесс моделирования с новыми условиями. Выберите Command / START (Команда / START). Так как нам нужен счетчик завершения, равный 1, в диалого­вом окне нажмите ОК.

Как вы видите в окне «Table» («Таблица»), большое количество сообщений задерживается из-за временных задержек в случае коллизий. Средняя задержка сообщения увеличивается до 14 миллисекунд.

Рисунок 3 – Q-таблица для 200 рабочих станций в сети

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

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

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

После завершения процесса моделирования GPSS World выводит отчет в файл отчета, за­данного по умолчанию (Ethernet 1.1). Расширения имен файлов отчета будут изменяться в зависимости от сохраненных процессов моделирования и ранее существовавших отчетов. Предположим, что процесс моделирования был создан и запущен в первый раз, поэтому расширение будет равно 1.1.

Этот отчет будет автоматически выведен в окне. Если вы закроете окно, повторно его можно будет открыть с помощью команды главного меню File / Open (Файл / Открыть). Затем в выпадающем списке «Files of type» («Тип файла») надо выбрать Report (Отчет). Отчеты GPSS World записываются в специальном формате. Если вы хотите отредакти­ровать отчет, вам понадобится скопировать его содержимое в буфер обмена, а оттуда - в текстовый редактор. Вы не сможете открыть этот файл непосредственно из текстового редактора.

Посмотрим на статистику нового стандартного отчета. Мы видим, что коэффициент использо­вания устройства Ethernet вырос до 98%, за моделируемое время произошло 413 коллизий. У многих транзактов произошло несколько коллизий.

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

Вся эта информация доступна в окнах «Facilities» («Устройства») и «Blocks» («Блоки»), Вы должны открыть эти окна, чтобы убедиться, что вы можете найти эту информацию. Исполь­зуйте и общий, и подробный обзоры этих окон.

2.3.4 Сведения о некоторых блоках и операторах, используемых в базовой модели.

Оператор EQU вычисляет выражение и присваивает результат величине, указанной как имя.

Формат оператора

Name EQU X

где Name – имя переменной или объекта, которому присваивается значение, Х – выражение.

В выражениях арифметические переменные используют такие арифметические операции:

+ - сложение;

- - вычитание;

# - умножение;

/ - деление (результатом является целая часть частного);

@ - деление по модулю;

^ - возведение в степень;

\ - деление без остатка (перед делением у обоих операндов отбрасываются дробные части).

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

В выражениях могут быть использованы операторы отношения: “G” - >, “L” - <, “E” - =, “GE” - ≥, “LE”- ≤, “NE” - ≠. Есть два булевых оператора: “OR” и “AND”.

В выражениях используются системные числовые атрибуты (СЧА), которые являются параметрами, описывающими состояние объекта. Более подробно о СЧА изложено в /5,6,7,8,9/. Каждый объект GPSS имеет свой набор СЧА. Доступ к СЧА осуществляется при использований специальных обозначений. Имя СЧА состоит из двух частей:

а) групповое имя, идентифицирует тип объекта и тип информации о нем (например, первая буква Q показывает, что это СЧА очереди, F – одноканального устройства, S – многоканального устройства, P - транзакта);

б) имя конкретного члена группы (например, Q$Wait – текущее значение длины очереди Wait).

Оператор VARIABLE описывает переменную.

Формат оператора

RSL VARIABLE X

где RSL - имя переменной, X - выражение. Далее в программе при любом обращении к переменной RSL, она будет вычисляться как выражение Х.

Пример,

Backrandom VARIABLE 1+ (RN49((2^V$Backmin)-1))

При обращении к переменной Backrandom, её значение будет вычисляться как 1+ (RN49((2^V$Backmin)-1)), где RN49 – датчик случайных чисел от 0 до 999, V$Backmin – значение переменной Backmin.

Блок ASSIGN назначает или изменяет параметр транзакта.

Параметры транзактов – это свойства транзакта, описываемые пользователем. Множество параметров транзакта – набор стандартных числовых атрибутов (СЧА), которые принадлежат транзакту. Доступ к параметрам транзакта осуществляется таким образом

Р< номер > или Р$ < имя >.

Формат блока

ASSIGN A[+,-], B, [C]

где A – номер или имя параметра, B – присваиваемое параметру значение, C – имя функции.

Например,

ASSIGN 3, 25

Параметру транзакта Р3 присваивается значение 25.

ASSIGN 3 -, 25

От значен6ия параметра Р3 вычитается 25.

ASSIGN 3 +, 25

К значению параметра Р3 прибавляется 25. Каждый транзакт может иметь свой приоритет — от 0 до 127. Чем больше номер, тем больше приоритет. Предпочтение в системе отдается транзактам с большим приоритетом, ранее поступившим.