Модель обработки приоритетных очередей в маршрутизаторах

где

t_j. - j-й разыгранный интервал времени поступления;

1/ λ -средний  интервал времени поступления; 

r_j, -j-e число в последовательности случайных чисел R с равномерным распределением на интервале [0, I].

Разработчиками  GPSS была осуществлена аппроксимация функции F^-1(x), обратной к экспоненциальной функции распределения с параметром λ=1. Таким образом, функция F^-1(x) была заменена 23 отрезками, которые использовались для преобразования значений RNj в значение - ln(RNj).

Функция XPDIS определяет экспоненциальное распределение с интенсивностью λ=1:

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

- в качестве операнда А используют среднее значение интервалов времени 1/λ, где λ - интенсивность пуассоновского потока;

- в качестве операнда В используют СЧА - значение функции XPDIS, операторы определения и описания которой приведены выше.

XPDIS FUNCTION RN1,C24

0,0/.100,.104/.2,.222/.300,.355/.400,.509/.500,.690/.600,.915/.700,1.200

.750,1.380/.800,1.600/.840,1.830/.880,2.120/.900,2.30/.920,2.520/.940,2.810

.950,2.990/.960,3.200/.970,3.500/.980,3.90/.990,4.600/.995,5.300/.998,6.200

.999,7/1,8

Описание  времени в процессе имитации

При имитационном моделировании выделяют три представления  времени: реальное, модельное (системное) и машинное время.

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

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

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

Машинное  время - это время, отражающее затраты времени ЭВМ на проведение имитационного моделирования.

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

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

Описание  требований выходных данных.

Выходными параметрами  являются величины, характеризующие  свойства системы - качество ее функционирования:

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

Описание требований по блокам алгоритма модели (рисунок 2.9)

Модель включает следующие GPSS-блоки:

Создание транзактов:

Generate // вход транзактов в модель

Вход транзактов в очередь:

Queue Joeqv // транзакты занимают очередь высокого приоритета

Queue Joeqs // транзакты занимают очередь среднего приоритета

Queue Joeqn // транзакты занимают очередь низкого приоритета

Занять устройство:

Seize Joe // транзакты занимают устройство

Выход транзактов из очереди:

Depart Joeqv// транзакты освобождают очередь высокого приоритета

Depart Joeqs // транзакты освобождают очередь среднего приоритета

Depart Joeqn // транзакты освобождают очередь низкого приоритета

Задержка транзактов на обслуживание:

Advance  // обслуживание транзакта

Освободить устройство

Освободить устройство:

Release Joe // транзакты освобождают устройство

Уничтожение транзактов:

Terminate // транзакты покидают модель

В качестве транзакта имитируется пакета.

Рисунок 2.9 – Алгоритм программы

Вывод.

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

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

3.1 Планирование эксперимента  и построение гипотез

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

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

При таком  кибернетическом подходе различают  входные и выходные переменные: х1 х2, ... ..., хm; у1 у2,..., уn. Определим требования, которые предъявляются к совокупности факторов: сортировка по Z; расчет требуемой полосы пропускания с учетом коэффициента срочности (принадлежность к диапазону задержки); передача пакета с учетом коэффициента срочности; выделение ОЗУ в зависимости от объема вида трафика.

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

Исходные  данные.

средний интервал между пакетами данных —25 ед. вр.;

емкости накопителей —20;

время передачи пакета данных по ДКС —20 ед. вр.;

время передачи подтверждения по ДКС —1 ед. вр.;

время обработки  пакета в ЦП —2 ед. вр.

Цели  моделирования:

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

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

Эксперимент_1.

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

Эксперимент_2.

Средняя интенсивность входного высокоприоритетного  трафика, при средней интенсивности  среднеприоритетного и низкоприоритетного трафиков.

Эксперимент_3.

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

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

3.2 Описание эксперимента

Результаты Эксперимента_тест.

GPSS World Simulation Report - МОДЕЛЬ2.12.1

 

 

                   Thursday, June 13, 2013 19:01:10 

 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000         500021.319    21        1          0

 

 

              NAME                       VALUE 

          JOE                         10002.000

          LOEQN                       10001.000

          XPDIS                       10000.000

 

 

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE          4932             0       0

                    2    QUEUE             4932          4932       0

                    3    SEIZE                0             0       0

                    4    DEPART               0             0       0

                    5    ADVANCE              0             0       0

                    6    RELEASE              0             0       0

                    7    TERMINATE            0             0       0

                    8    GENERATE          9921             0       0

                    9    QUEUE             9921          9919       0

                   10    SEIZE                2             0       0

                   11    DEPART               2             0       0

                   12    ADVANCE              2             0       0

                   13    RELEASE              2             0       0

                   14    TERMINATE            2             0       0

                   15    GENERATE         10135             0       0

                   16    QUEUE            10135          5136       0

                   17    SEIZE             4999             1       0

                   18    DEPART            4998             0       0

                   19    ADVANCE           4998             0       0

                   20    RELEASE           4998             0       0

                   21    TERMINATE         4998             0       0

 

 

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

JOE               5001    1.000      99.980  1    12253    0    0     0   19987

 

 

QUEUE              MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME   AVE.(-0) RETRY

LOEQN            19988 19988  24988      1  9988.274 199869.935 199877.934   0

 

 

CEC XN   PRI          M1      ASSEM  CURRENT  NEXT  PARAMETER    VALUE

12253    3      245631.945   12253     17     18

 

 

FEC XN   PRI         BDT      ASSEM  CURRENT  NEXT  PARAMETER    VALUE

 24981    1      500028.524   24981      0      1

24991    2      500183.257   24991      0      8

24988    3      500206.722   24988      0     15

Результат работы при максимальной интенсивности  высокоприоритетного трафика без  обработки приоритетной очереди: производительность 1 при не обработанных 19987 пакетов.

 

Результаты Эксперимента_2

GPSS World Simulation Report - МОДЕЛЬ3.11.1

 

 

                   Thursday, June 13, 2013 19:04:28 

 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000         500045.686    21        1          0

 

 

              NAME                       VALUE 

          JOE                         10002.000

          LOEQN                       10001.000

          XPDIS                       10000.000

 

 

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE          9995             0       0

                    2    QUEUE             9995          7978       0

                    3    PREEMPT           2017             0       0

                    4    DEPART            2017             0       0

                    5    ADVANCE           2017             0       0

                    6    RETURN            2017             0       0

                    7    TERMINATE         2017             0       0

                    8    GENERATE          4915             0       0

                    9    QUEUE             4915          3926       0

                   10    PREEMPT            989             0       0

                   11    DEPART             989             0       0

                   12    ADVANCE            989             1       0

                   13    RETURN             988             0       0

                   14    TERMINATE          988             0       0

                   15    GENERATE         10079             0       0

                   16    QUEUE            10079          8083       0

                   17    PREEMPT           1996             0       0

                   18    DEPART            1996             0       0

                   19    ADVANCE           1996             1       0

                   20    RETURN            1995             0       0

                   21    TERMINATE         1995             0       0

 

 

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

JOE               5002    1.000      99.961  1     5002 19987    1     0      0

 

 

QUEUE              MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME   AVE.(-0) RETRY

LOEQN            19988 19987  24989      2  9988.012 199866.426 199882.423   0

 

 

FEC XN   PRI         BDT      ASSEM  CURRENT  NEXT  PARAMETER    VALUE

  5002    3      500145.686   5002     19     20

24991    1      500183.263   24991      0      1

24988    3      500206.738   24988      0     15

24992    2      500252.791   24992      0      8

Результат работы при максимальной интенсивности  среднеприоритетного трафика без  обработки приоритетной очереди: производительность 1 при не обработанных 0.

 

Результаты Эксперимента_3

GPSS World Simulation Report - МОДЕЛЬ3.12.1

 

 

                   Thursday, June 13, 2013 19:05:37 

 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000         500045.686    21        1          0

 

 

              NAME                       VALUE 

          JOE                         10002.000

          LOEQN                       10001.000

          XPDIS                       10000.000

 

 

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE          9884             0       0

                    2    QUEUE             9884          8233       0