Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ALGORITHMS AND SOFTWARE FOR NETWORK SYSTEMS SIMULATION BASED ON (MIN,+) FILTERING

Chubeyko S.V. 1
1 Rostov State Transport University
The article is devoted to the development of a new approach of simulation models of network systems with IP-traffic. Emphasis is placed on methods for assessing the performance and quality of service in IP- based networks, and they distributed network systems. The principles of integrated architectures, IntServ and differential , DiffServ QoS in computer networks is done . A method for calculating the characteristics of the system with a guaranteed service architecture services IntServ is provided. An approach to the development of mathematical models of network systems with guaranteed service on the basis of (min, +) algebraic structures is proposed. Methods of «network calculus», the development of an algebraic approach to the description of service systems to estimate their performance are presented. The characteristics of the algebraic structure dioid is adequate representation of the model (min, +) filtering of network traffic is done. A simulation model of the network system (min, +) filtering is presented. Operators and programming construction on functional programming language for the implementation of the proposed simulation model are described. A software implementation of the network balance equation on functional programming language is implemented.
functional programming
simulation
queueing theory
quality of service

Введение

Под сетевыми системами в рамках данной статьи будем понимать совокупность распределенных программно-управляемых систем обменивающихся информационным трафиком посредством стека IP-протокола. Такие сетевые системы предоставляют основной спектр нынешних Интернет-услуг и предъявляют различные требования к их качеству, которое принято называть QoS (Quality of Service, качество обслуживания). Современные механизмы QoS опираются на принципы либо интегрированной архитектуры обслуживания (Integrated Services, IntServ), которая описана в руководстве IETF RFC1633, либо на принципы архитектуры дифференцированного предоставления обслуживания (Differentiated Services, DiffServ), которая описана в руководстве IETF RFC2474. Архитектура IntServ обеспечивает сетевое обслуживание в двух режимах: 1) контролируемой загрузки (Controlled Load, CL) для обеспечения гарантированного трафика к сетевым адаптивным приложениям «мягкого» реального времени; 2) гарантированного обслуживания (Guaranteed Service, GS) с обеспечением заранее заданной полосы пропускания к сетевым неадаптивным приложениям «жесткого» реального времени.

В случае CL для настройки услуг не используются управляющие параметры QoS, такие как уровень потерь пакетов и время задержки поступления данных. Доставка трафика сетевому приложению зависит лишь от времени задержки ретрансляции данных сетевым оборудованием, а также от всплескового характера самого трафика. Время минимальной задержки в режиме CL, будет стремиться к максимальной величине всплескового (в количественном отношении) объема трафика. В случае обеспечения уровня услуг GS сетевому приложению выделяется гарантированная полоса пропускания трафика и регулируется граничное значение времени задержки обслуживания. Величина максимального времени задержки зависит от параметров канала передачи данных, от дисциплины, интенсивности обслуживания и определена в руководстве IETF RFC2212 и алгоритмом маркерной корзины (Token Bucket):

(1)

где r – интенсивность поступления маркеров в корзину, байтов/c;

p – максимальная интенсивность поступления данных, байтов/с;

R – интенсивность обслуживания, байтов/с;

b – размер маркерной корзины, байтов;

М – максимальный размер поступающего блока данных (IP-дейтаграммы), байтов;

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

D –максимальная девиация времени при обработке данных устройствами обслуживания, с.

В дополнение к рассмотренной, архитектура DiffServ осуществляет разделение трафика на классы и приоритеты. В целом, при управлении качеством обслуживания в IP-сетях основное внимание уделяется обеспечению минимальных (или максимальных) гарантированных значений параметров управления трафиком: полосой пропускания, временной задержкой, девиацией временной задержки и уровнем потерь блоков данных. Поэтому одними из современных адекватных математических моделей сетевых систем с гарантированным обслуживанием являются модели, построенные на (min,+) или (max,+) алгебраических структурах, а развитие такого подхода для оценки производительности сетевых систем, называется «network calculus» [9]. Данное направление базируется на подходах теории алгебраических структур – полуколец с каноническим упорядочиванием (идемпотентных полуколец, диоидов) [8] идемпотентного анализа [3], моделирования дискретных динамических систем [6]. Моделированию и оценке гарантированной производительности и надежности сетевых систем посвящены работы c участием автора [1,2,4,5].

Элементы теории: (min,+) алгебра и network calculus

Основной алгебраической структурой в рассматриваемом подходе является структура, называемая «диоид» [8]. Диоид определяется, как числовое множество , снабженное двумя замкнутыми операциями: «сложение, » и «умножение, », . Операции в диоиде должны подчиняться следующим правилам: 1) ассоциативность по сложению и умножению; 2) коммутативность по сложению; 3) дистрибутивность по умножению, относительно сложения; 4) существование нейтральных элементов для обеих операций: нулевого (по сложению и поглощающего по умножению) и единичного; 5) идемпотентность сложения; 6) отсутствие обратных элементов.

В рамках статьи будем рассматривать операции диоида, следующим образом. Для функций , , а для , , . Рассмотренная алгебраическая структура, диоид позволяет предложить достаточно эффективный подход к аналитическому и имитационному моделированию сетевых систем, наряду с теорией массового обслуживания (ТМО). Существенные отличия подходов, в целом, состоят в том, что в ТМО для расчета числовых характеристик необходимо построить аналитические или адекватные им приближенные модели входных потоков и элементов обслуживания, а в алгебраическом подходе «network calculus» исследуются граничные условия для кумулятивных функций, описывающих как входной поток, так и поток обслуживания. Таким образом, в последнем подходе, элемент обслуживания служит фильтром входного потока, придавая выходному потоку ту, или иную заданную форму. Отметим, что функции, описывающие граничные условия могут быть как детерминированными, так и случайными [9].

Далее рассматриваем детерминированные функции фильтрации входного трафика. На рис. 1 показана иллюстрация к такому подходу, где – входной фильтрованный поток (входная кумулятивная функция), – поток обслуживания (выходная кумулятивная функция), а часть обозначений соответствует формуле (1). Буфер сетевых данных принимает входной поток , который на физическом уровне IP-сети является последовательным байтовым потоком, составляющим накапливаемый (следовательно, кумулятивный) объем данных, и, в целом – входной трафик. Далее поток подвергается - фильтрации, то есть в техническом отношении при информационной перегрузке, переполнении входных буферов, различных неисправностях программно-аппаратного обеспечения, при выполнении функций QoS, разделении и трафика на классы и приоритеты происходит отсекание части трафика, подобно прохождению сигналов через фильтры. Так формируется входной фильтрованный поток , поступающий на устройство обслуживания, которое в свою очередь также имеет - фильтр с характеристиками, зависящими от применяемого в сетевом устройстве алгоритма маркерной корзины (Token Bucket). В итоге формируется выходной поток .

Рис. 1. Имитационная модель сетевой системы с (min,+) фильтрацией

Математической моделью рассматриваемого (min,+) подхода являются уравнения:

для

; (2)

для

. (3)

Поиск решения уравнений (2) и (3) приводит к известной из теории цифровой обработки информации задаче о вычислении интеграла свертки:

, (4)

а в терминах рассматриваемого подхода

. (5)

Метод расчета (min,+) интегральной свертки

В работе автора [5] предложен подход к реализации алгоритмов network calculus на функциональном языке программирования J и были даны необходимы описания входных кумулятивных функций. Рассмотрим дальнейшее описание имитационных алгоритмов расчета (min,+) интегральной свертки на функциональном языке программирования J.

В вышеуказанном языке программирования есть оператор min, обладающая всеми необходимыми для названных ранее операций «сложение, » и «умножение, » свойствами. Оператор min может быть применим, как к скалярным, так и к матричным величинам. Для скалярных величин можно в среде программирования J ввести с клавиатуры, например: 4 min 5, ((35 min 24) min 4). Можно проверить свойство дистрибутивности операции: ((3 min 2) + 4) = (3 + 4) min (2 + 4), результатом будет вывод на экран числа 1, что означает истинность выражения (если результат равен 0, то выражение не является истинным). Матричные операции в (min,+) алгебре

и

в языке программируются соответственно: P min”0 Q и P (min”1 .+) M.

Для расчетов (поточечного) минимума двух функций и их свертки в языке J нужно запрограммировать соответственно: min@(f@t, g@t) и min@(f@s, g@(t-s)).

Теперь опишем главный результат статьи – программную реализацию основного уравнения баланса сетевой модели. Уравнение Линдли [7] (аналогично ТМО):

На функциональном языке J реализовано следующей программой:

cocurrent < ’LINDLEY’

ylist =: rhs0

c =: >@lhs1

xlist =: >@lhs2

ind =: <:@#@ylist

xnext =: ind { xlist

yprev =: {:@ylist

ynext =: max0 @ xnext + yprev + c

cocurrent <’base’

lindley_z_ =: ylist_LINLEY_,ynext_LINDLEY_

Заключение

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

Рецензенты:

Павлов И.В., д.ф.-м.н., профессор, заведующий кафедрой высшей математики Ростовского государственного строительного университета, г. Ростов-на-Дону.

Чернов А.В., д.т.н., профессор, заведующий кафедрой прикладной математики и вычислительной техники Ростовского государственного строительного университета, г. Ростов-на-Дону.