utf-8Влияние дисциплины обслуживания заявок на производительность коммутатора

ВЛИЯНИЕ ДИСЦИПЛИНЫ ОБСЛУЖИВАНИЯ ЗАЯВОК НА ПРОИЗВОДИТЕЛЬНОСТЬ КОММУТАТОРА

В.А. Гулиус
Харьковский национальный университет радиоэлектроники
пр. Ленина, 14, г. Харьков, 61166, gulius@mail.ru

Актуальность темы. На сегодняшний день в мире существует большое количество самых разнообразных компьютерных систем, которые обеспечивают функционирование всех сфер человеческой деятельности. От эффективного использования таких систем зависит работа как маленьких предприятий, так и больших корпораций. Поэтому основной задачей для проектировщиков и пользователей компьютерных систем и сетей является разработка новых методов обеспечения требуемого качества обслуживания (Quality of Service, QoS). Методы QoS призваны минимизировать уровень задержек для чувствительного к ним трафика.

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

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

Параметры очереди. На рис. 1 представлены параметры, относящиеся к модели очереди. Пакеты прибывают на сервер обслуживания со средней интенсивностью $$. В любой момент времени определенное количество пакетов (ноль или более) будет ждать в очереди.

Рисунок 1 – Модель системы массового обслуживания с одним обслуживающим прибором

Среднее число пакетов, ожидающих обслуживания, обозначим $w$, а среднее время ожидания $T_w$. $T_w$ усредняется для всех пакетов, в том числе для тех, которые вообще не ждали. Сервер обрабатывает поступающие пакеты со средним временем обслуживания $T_s$ – это интервал времени между моментом поступления пакета во входной буфер сервера и завершением обработки его на сервере. Загрузка $$ – есть доля времени, которое сервер занят обслуживанием пакетов, измеряемым в течение некоторого промежутка времени. Среднее время, которое пакет тратит в системе, т.е. время ожидания в очереди плюс время обслуживания сервером, есть $T_r$ и называется временем жизни пакета. Если предположить, что длина очереди бесконечна, то нет никаких пакетов, которые были бы потеряны в системе, они просто задерживаются, пока не будут обслужены.

Для обозначения основных допущений, применяемых при моделировании СМО, была разработана так называемая нотация Кендалла (Kendall's notation) [2]. Эта нотация имеет вид $X/Y/N$, где

• $X$ – распределение интервалов времени между поступлениями запросов,
• $Y$ – распределение времени обслуживания,
• $N$ – количество серверов.

Основными элементами модели (рис. 1) являются:

• входной поток пакетов, который характеризуется интенсивностью $$, т.е., количеством пакетов, поступающих на вход системы в единицу времени;
• буфер, в котором формируется очередь пакетов, ожидающих обслуживания. В любой момент времени, определенное количество пакетов будет ждать в очереди (ноль или более); среднее число пакетов, ожидающих обслуживания, обозначим $w$, а среднее время ожидания $T_w$. $T_w$ усредняется для всех пакетов, в том числе для тех, которые вообще не стояли в очереди;
• сервер – обслуживающее устройство, загрузка которого обозначается как $$.

Пакеты поступают на вход буфера в случайные моменты времени. Если в момент поступления пакета буфер пуст и сервер свободен, то пакет передается в сервер для обслуживания. Обслуживание пакета выполняется в течение времени $T_s$.

Если поступивший на вход СМО пакет застает буфер не пустым, то пакет становится в очередь и ожидает обслуживания. Пакеты выбираются из очереди и передаются на сервер в соответствии с дисциплиной обслуживания, принятой в системе. В настоящее время по умолчанию в большинстве СМО в качестве дисциплины обслуживания используется FIFO (First-In, First-Out), первым пришел – первым обслужен.

Моделирование. В работе предлагается интеллектуальная модель исследования производительности пакетного коммутатора – сетевого коммуникационного устройства, получившего широкое применение в современных компьютерных сетях. В качестве инструмента моделирования была выбрана среда MatLab+SimEvents, обеспечивающая блочное моделирование и формирование результатов в виде таблиц и графиков.

Основная цель исследования – получение сравнительной оценки влияния дисциплины обслуживания на качество обслуживания (QoS) в пакетном коммутаторе. Для решения этой задачи были применены две дисциплин обслуживания пакетов FIFO и LIFO. В качестве параметра QoS была выбрана полезная пропускная способность пакетного коммутатора. Исследования были проведены в два этапа. На первом этапе была рассмотрена простая модель (рис. 2), приведенная в системе SimEvents.

На рис. 2 представлена система массового обслуживания, в которой пакеты поступают в фиксированные детерминированные моменты времени, ожидают в очереди, а затем поступают на сервер, который обслуживает их за детерминированные отрезки времени. В нотации Кендалла такая модель получила обозначение D/D/1.

Формирование пакетов выполняется в блоке Time-Based Entity Generator. В маске параметров этого блока был установлен период следования пакетов, равный 0.3 сек. Время обслуживания пакетов серверами LIFO и FIFO составляло 1 сек., а время моделирования – 10 сек.

Блок Replicate позволяет размножить пакеты на всех выходах (в нашем случае требуется 2 выхода). Первый выход блока Replicate (Out 1) подсоединен к входу буфера, реализующего дисциплину обслуживания LIFO (LIFO Queue), а второй выход (Out 2) – к входу буфера c дисциплиной FIFO (FIFO Queue).

Рисунок 2 – Модель исследования времени ожидания в СМО

Моделирование выполнялось в течение 10 сек. Емкость буферов была установлена неограниченной. На рис. 3 приведены результаты моделирования СМО с дисциплиной обслуживания LIFO. За время моделирования сервер LIFO обработал 10 пакетов в связи с тем, что время обработки каждого пакета составляло 1 сек. На рисунке отображено среднее время ожидания каждого пакета во входном буфере, которое не превышает 0.1 сек.

Рисунок 3 – Среднее время задержки пакетов в буфере LIFO

Результаты моделирования СМО с дисциплиной обслуживания FIFO представлены на рис. 4. В этом случае среднее время ожидания пакетов линейно возрастет и его значение значительно превышает время ожидания в буфере LIFO.

Рисунок 4 – Среднее время задержки пакетов в FIFO-очереди

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

На втором этапе было выполнено исследование влияния дисциплины обслуживания на производительность пакетного коммутатора. Для проведения исследования была выбрана модель коммутатора A packet switch (рис. 5), приведенная в среде MatLab+SimEvents.

Рисунок 5 – Модель пакетного коммутатора

На схеме показаны три подсистемы Subsystem, Subsystem1 и Subsystem 2, которые моделируют функции рабочих станций в сети. В каждую подсистему (рис. 6) входят следующие блоки:

• Length – блок формирования размера пакета. Поле данных пакетов будет изменяться в пределах 100:200:1500 байт. В табл. 1 во 3-ем столбце представлены минимальное и максимальное время передачи пакетов с учетом служебных данных для каждого диапазона.
• Destination – блок формирования адреса назначения пакета. В блоке формируются псевдослучайные целые числа, распределенные по экспоненциальному закону, от 1 до 3 в соответствии количеством каналов в модели.
• Time-Based Entity Generator – формирует временные интервалы поступления пакетов. Таким образом, совокупность описанных трех блоков моделирует работу рабочей станции.

Рисунок 6 – Подсистема формирования пакетов

С выходов каждой рабочей станции пакеты поступают в буферы коммутатора FIFO Queue, в которых ожидают завершение обслуживания сервером ранее поступивших пакетов. При проведении исследований одним из переменных параметров была емкость буфера, которому присваивались значения 1:5:25.

Трехпортовый пакетный коммутатор находится в центре схемы (рис. 5) в виде совокупности двух блоков Path Combiner и Output Switch. Блок Path Combiner выполняет процедуру мультиплексирования $n1$, подсоединяя три буфера к выходному коммутатору Output Switch. Функция объединителя пути (Path Combiner) состоит в выборе пакетов из очередей и продвижении их на вход бока Output Switch по мере завершения обслуживания пакетов, поступивших в предыдущие моменты времени.

К трем выходным портам коммутатора подсоединены три приемника пакетов Single Server, Single Server1 и Single Server2. В соответствии с адресом, указанным в поле Адрес назначения, пакеты поступают для обработки в серверы.

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

• соединяет три источника пакетов с тремя местами назначения;
• принимает прибывающие пакеты в буфер (то есть, в очередь) от каждого из источников данных;
• в том случае, если два или более пакетов с одинаковым адресом приемника поступили одновременно на вход блока Path Combiner, разрешение конфликтной ситуации выполняется случайным образом путем установки параметра порядка выбора в диалоговом окне этого блока в состояние Randomize.

Исследования были выполнены применительно к сети Fast Ethernet. Весь диапазон размеров пакетов был разделен на 8 частей 100:200:1500. Для каждого поддиапазона были вычислены минимальное и максимальное время передачи пакета с учетом размера поля данных и служебной информации (табл. 1, колонка 2). Эти данные программно загружались в блоки параметров Length, входящих в подсистемы формирования пакетов рабочими станциями.

Таблица 1 – Исходные данные модели коммутатора Размер пакета, байт Время передачи пакета, мкс timespan 1 2 3 100 7-16 731240 300 16-32 733640 500 32-48 772260 700 48-64 782500 900 64-80 792000 1100 80-96 803200 1300 96-112 803300 1500 112-123 803600

На основании данных колонки 2 эмпирическим путем были определены значения необходимого количества итераций при моделировании (timespan), представленные в колонке 3.

Схема модели коммутатора была дополнена двумя подсистемами Discrete Event Subsystem и Discrete Event Subsystem 1 (рис. 7). Основное назначение этих модулей состоит в подсчете количества пакетов на входе и выходе коммутатора.

Рисунок 7 – Подсистемы вычисления количества пакетов на входе и выходе коммутатора

Выполнение эксперимента с моделью пакетного коммутатора. Для проведения исследований о влиянии дисциплины обслуживания заявок на полезную пропускную способность коммутатора была разработана интеллектуальная модель, включающая модель пакетного коммутатора (рис. 5) и программу, обеспечивающую занесение значений входных переменных в блоки параметров подсистем Subsystem, Subsystem 1 и Subsystem 2, а также формирование результатов моделирования в виде графиков и таблиц.

Для исследования были выбраны две дисциплины обслуживания: FIFO (first input first output) и LIFO (last input first output). Первый этап исследования модели коммутатора был выполнен для дисциплины обслуживания FIFO. На рис. 5 представлена модель коммутатора, в котором выбор пакетов из буферов выполнялся по правилу FIFO. Результаты моделирования приведены в табл. 2 и рис. 8.

Таблица 2 – Полезная пропускная способность коммутатора
(дисциплина обслуживания FIFO) Размер пакета,
байт Емкость буфера, пакет 1 5 10 15 20 25 100 102.98 112.26 113.66 114.52 114.44 114.23 300 154.42 168.93 170.95 172.37 172. 29 172.13 500 164.72 179.72 181.83 183.08 183.38 183.08 700 166.72 182.66 184.55 185.51 185.53 185.53 900 168.77 184.57 187.29 188.53 188.13 188.74 1100 171.37 186.92 190.78 191.88 189.29 190.18 1300 172.58 188.21 191.02 191.34 191.87 190.87 1500 171.88 188.21 191.34 190.76 192.23 192.08

Рисунок 8 – Полезная пропускная способность коммутатора с дисциплиной обслуживания FIFO

Следующий этап исследований был выполнен с моделью коммутатора c дисциплиной обслуживания LIFO. В этом случае в схеме модели коммутатора (рис. 5) блоки FIFO Queue были заменены блоками LIFO Queue. Программный код интеллектуальной модели не претерпел никаких изменений. Результаты моделирования для дисциплины обслуживания LIFO представлены в табл. 3 и на рис. 9.

Таблица 3 – Полезная пропускная способность коммутатора
(дисциплина обслуживания LIFO) Размер пакета,
байт Емкость буфера, пакет 1 5 10 15 20 25 100 102.98 119.23 122.17 123.59 123.82 123.99 300 154.41 179.53 183.80 186.16 186.11 186.68 500 164.71 190.89 195.23 196.46 197.38 197.22 700 166.72 193.79 197.97 198.96 200.51 200.31 900 168.76 195.18 200.95 201.61 202.44 202.26 1100 171.37 199.35 203.97 205.07 205.50 206.55 1300 172.57 198.56 203.96 205.89 206.25 204.23 1500 171.87 199.27 204.19 205.05 205.87 205.52

Рисунок 9 – Полезная пропускная способность коммутатора с дисциплиной обслуживания LIFO

На рис. 10 представлена столбиковая диаграмма, отражающая влияние дисциплины обслуживания пакетов на полезную пропускную способность коммутатора. Для построения диаграммы были выбраны данные из колонок 7, соответствующих емкости буферов 25 таблиц 2 и 3.

Рисунок 10 – Сравнительная диаграмма влияния дисциплины обслуживания заявок на полезную пропускную способность коммутатора

Выводы

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

Литература

1. Олифер В.Г., Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. Учебник для вузов. 3-е изд. -СПб.: Питер – 2006, - 958 с.: ил.
2. William Stallings. Queuing Analysis. www.shore.net/~ws/COA5e.

Список статей автора

1. Гулиус В.А. Влияние дисциплины обслуживания заявок на производительность коммутатора. Представлены результаты исследований аналитических моделей и даны рекомендации по выбору дисциплины обслуживания заявок (пакетов LIFO) в буфере коммутатора, позволяющие снизить задержки, повысить полезную пропускную способность и обеспечить требуемое качество обслуживания (Quality of Service, QoS).
2. Гулиус В.А. Исследование динамических характеристик пакетного коммутатора. В статье описано исследование, цель которого состояла в определении средних значений задержек продвижения пакетов в коммутаторе (в зависимости от размера пакета и емкости входного буфера), и в выявлении влияния дисциплины обслуживания заявок FIFO и LIFO на задержки.
3. Гулиус В.А. Имитационная модель коммутатора. Цель данной работы – исследование характеристик коммутатора, и, в первую очередь, его производительности (в среде MatLab+SimEvents).
4. Гулиус В.А. Интеллектуальная модель системы массового обслуживания с очередью типа D/D/1 в среде SimEvents (MATLab/SimuLink).
5. Гулиус В.А. Влияние коллизий на производительность Ethernet. В статье выполнено исследование модели сети Ethernet в среде Simulink. Цель исследования – определение влияния коллизий на полезную пропускную способность.