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

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

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

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

 

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

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

                     

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

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

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

                                                             (1)

1.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

2.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  - Короткие сообщения (в долях от тысячи).

* Lot_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@((2^V$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, 1 ,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.2 Запуск процесса моделирования

Выбираем Command/Create Simulation.

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

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

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

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

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

ОТЧЕТ

              GPSS World Simulation Report - Untitled.19.1

 

 

                   Tuesday, April 24, 2007 20:04:15 

 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000           1000.000    35      102          0

 

 

              NAME                       VALUE 

          BACKMIN                     10011.000

          BACKOFF                        18.000

          BACKOFF_DELAY               10009.000

          BACKOFF_LIMIT                  10.000

          BACKRANDOM                  10010.000

          COLLIDE                     10013.000

          COLLISION                      12.000

          ERROR_COUNT                 UNSPECIFIED

          ETHERNET                    10022.000

          FRACTION_SHORT_MSGS           600.000

          FREE_NODE                      29.000

          GLOBAL_DELAYS               10017.000

          INTERFRAME_TIME                 0.010

          INTERMESSAGE_TIME               1.000

          JAM                         10021.000

          JAM_TIME                        0.003

          MAX_MSG                     12144.000

          MESSAGE_TIME                10019.000

          MIN_MSG                       512.000

          MSGRAND                     10015.000

          MSGTIME                     10014.000

          MSG_DELAYS                  10016.000

          NODE_COUNT                    100.000

          NODE_ID                     10018.000

          NODE_SELECT                 10012.000

          RETRIES                     10020.000

          SLOT_TIME                       0.051

          START_XMIT                     22.000

          TRY_TO_SEND                     7.000

          XMIT_BEGIN                  10024.000

          XMIT_ERROR                     32.000

          XMIT_NODE                   10023.000

 

 

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE           914             0       0

                    2    ASSIGN             914             0       0

                    3    ASSIGN             914             0       0

                    4    ASSIGN             914             0       0

                    5    QUEUE              914             0       0

                    6    SEIZE              914             0       0

TRY_TO_SEND         7    PRIORITY           920             0       0

                    8    SEIZE              920             0       0

                    9    RELEASE            920             0       0

                   10    TEST               920             0       0

                   11    TEST               440             0       0

COLLISION          12    PREEMPT              3             0       0

                   13    SEIZE                3             0       0

                   14    ADVANCE              3             0       0

                  15    RELEASE              3             0       0

                   16    RELEASE              3             0       0

                   17    PRIORITY             3             0       0

BACKOFF            18    ASSIGN               6             0       0

                   19    TEST                 6             0       0