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

MODELING OF PROCESS PACKET DATA TRANSITION

Gorbachenko I.M. 1
1 Siberian Technological University
The work presents a model of the process of a packet transmission of data over a computer network in the form of coloured Petri nets. The mathematical description of the model consists of the transfer of the sets of resources and their interaction. In the developed model, the transfer of information from one computer (the source) to the other four computers (receivers) by taking into account the retransmission of the packet from the transmitter to the receiver in the event of failure. If the successful transfer of the package is formed by the «receipt» with indication of the time of delivery of the package. The model assumes that the request the transmitter to the readiness of the receiver accept the information included in the first package, and in the latter delivered package contains the information for the termination of session of transmission. The structure of the package also conditionally simplified. The developed model can be easily modified, that allows to estimate the time spent in the various modes of transmission. The results are presented more than 100 experiments, which allow to estimate the time and reliability of the transmission of packets.
information packet
time transition information
model
Colored Petri Nets

Введение

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

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

Пакеты, относящиеся к одному сообщению, могут передаваться по разным маршрутам в зависимости от того, по какому из них в данный момент они с наименьшей задержкой могут пойти к адресату. В связи с тем, что время прохождения по сети пакетов одного сообщения может быть различным (в зависимости от маршрута и задержки в узлах коммутации), порядок их перехода к получателю может не соответствовать порядку пакетов. Данной проблемой занимался, например, Непомнящий В. А. [1,3] и Саркенов Д. О. [4].

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

Пакетная передача информации

Процесс передачи данных в сети с КП можно представить в виде следующей последовательности операций:

· вводимое в сеть сообщение разбивается на части – пакеты, содержащие адрес конечного пункта получателя;

· в узле КП пакет запоминается в оперативной памяти (ОЗУ) и по адресу определяется канал, по которому он должен быть передан;

· если этот канал связи с соседним узлом свободен, то пакет немедленно передается на соседний узел КП, в котором повторяется та же операция;

· если канал связи с соседним узлом занят, то пакет может какое-то время храниться в ОЗУ до освобождения канала;

· сохраняемые пакеты помещаются в очередь по направлению передачи, причем длина очереди не превышает 3–4 пакета; если длина очереди превышает допустимую, пакеты стираются из ОЗУ, и их передача должна быть повторена.

По результатам успешной передачи данных формируется «квитанция» с указанием времени доставки пакета.

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

Описание раскрашенной сети Петри

Для проведения исследований построена математическая модель передачи информации по компьютерной сети в виде раскрашенной (цветной) сети Петри – ColouredPetriNets (CPN).

Ниже рассмотрено несколько упрощенное и по возможности неформализованное описание CPN. Полное и строгое описание CPN содержится в книгах [2, 4, 5].

раскрашенная сеть Петри CPN – это кортеж

, где

1. – множество дискретных моментов времени (шагов), в которые происходит функционирование сети. Номер шага есть переменная целого типа:

varteta: Integer;

2. – конечное множество непустых типов, называемое цветами.

В предлагаемой модели введены следующие цвета:

- Computer – номер компьютера, которому необходимо передать сообщение, обозначено целым числом от 1 до 4 ( colsetComputer = intwith 1..4; ). Этим цветом обозначена переменная с ( var c: Computer).

- NOMER – номер передаваемого пакета, обозначено целым числом от 1 до 600 (colsetNOMER = intwith 1..600). Этим цветом обозначена переменная nn ( varnn: NOMER).

- times – время передачи информации, обозначено целым числом от 0 до 6000000 (это такты работы компьютера, мкс.) (colsettimes = intwith 1.. 6000000). Этим цветом обозначена переменная t ( vart: times).

- zad – задержка во времени при передаче информации, обозначено целым числом от 0 до 100 (это такты работы компьютера, мкс.) (colsetzad = intwith 0.. 100). Этим цветом обозначены переменные zad1 и zad2 (var zad1, zad2: zad).

- packet – пакет, состоящий из номера компьютера-приемника, номера пакета, передаваемой информации (например, в виде некоторого текста) (colsetpaket = productComputer * NOMER * DATA). Этим цветом обозначена переменная p ( varp: paket).

- sl – информация о пакете с указанием текущего времени (colsetsl = productComputer * NOMER * DATA * times). Этим цветом обозначена переменная p (varsl: sl).

- per – переданные пакеты, содержит номер компьютера-приемника, номер пакета, время передачи пакета (colsetper = productComputer * NOMER * times). Этим цветом обозначена переменная per (varper : per).

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

- p1 – содержит номер компьютера (фишки с цветом Computer);

- p2 – номер пакета (фишки с цветом NOMER);

- p3 – передаваемая информация (например, текст) (фишки с цветом STRING);

- p4 – позиция, содержащая пакет для передачи (фишки с цветом paket);

- p5 – пакет с указанием времени начала передачи (фишки с цветом sl);

- p6 – пакет с указанием времени окончания передачи;

- p7-1, p7-2, p7-3, p7-4 – позиции, обозначающие соответствующие компьютеры, в которые передана информация, содержит информацию о пакете и времени его передачи (фишки с цветом sl);

- p8 – позиция, содержащая информацию о переданных пакетах (номер компьютера, номер пакета, время передачи) (фишки с цветом per);

- z1 и z2 – позиции, содержащие время передачи пакета по компьютерной сети (фишки с цветом zad);

- time – позиция с указанием времени начала очередного пакета (вначале время равно 0), в итоге – время передачи информации (фишки с цветом times).

4. – конечное множество переходов.

В модели это переходы:

- t0 – формирование пакета,

- t1 – начало передачи пакета,

- t2-1 – передача пакета по сети с его потерей (время передачи более 89 нс.),

- t2-2 – нормальная передача пакета по сети (время передачи меньше 90 нс.),

- t3-1, t3-2, t3-3, t3-4 – доставка пакета к конкретному соответствующему компьютеру,

- t4 – сообщение источнику конца передачи пакета.

5. – конечное множество дуг, связывающих между собой позиции и переходы. Элементы этого множества можно определить по рисунку 1.

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

7. – цветовая функция, определяющая множество типов цветов, разрешенных для каждой позиции. В предлагаемой сети Петри:

- C(p1) = Computer,

- C(p2) = NOMER,

- C(p3) = STRING,

- C(p4) = paket и т.д. Эти функции отображены на рисунке 1 в виде подписей к каждой позиции.

8. – блокировочная (спусковая) функция, описывающая дополнительные условия, которые должны быть выполнены для срабатывания перехода .

Для предлагаемой модели:

- G(t2-1) = zad1 > 89,

- G(t2-2) = zad1 < 90,

- G(t3-1) = #1 sl = 1 и т.д. Другие блокировочные функции указаны на рисунке 1 в виде подписей к соответствующим переходам.

9. – функция, задающая выражения на дугах . Эта функция для каждой дуги определяет мультимножество, состоящее из элементов, описанных во множестве цветов . Значение этой функции отображено на рисунке 1 в виде подписей к соответствующим дугам.

9. – функция инициализации сети CPN. Эта функция задает начальную маркировку (разметку) сети , т.е. для каждой позиции указывает цветовое мультимножество, обозначаемое . Начальную разметку рассматриваемой сети Петри можно увидеть на рисунке 1 в виде подписей к соответствующим позициям.

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

Пусть по сети передается сообщение, разбитое на фрагментов, называемых пакетами. В предлагаемом примере – 600 пакетов. Каждый пакет состоит из номера (целое число типа integer) и текстовой части (типа string). Эти пакеты произвольным образом отправляются по 4-м различным компьютерам. При этом порядок их передачи также произвольный.

Первоначально все пакетов находятся (или накапливаются) в позиции p4 (рисунок 1). Целью работы системы является передача всех пакетов другим компьютерам – в позиции p7-1, p7-2, p7-3 и p7-4 соответственно – без учета последовательности их номеров. Кроме того, отправитель должен получить «квитанции» о передаче всех пакетов, и эти «квитанции» с пометкой о времени передачи помещаются в позицию p8.

Рисунок 1. Графическое изображение цветной сети Петри

Проследим передачу одного пакета в системе. Пусть часы глобального времени в момент начала передачи показывают время t0 (начальная фишка в позиции time). В примере задано, что это время равно 0 нс. В позиции p1 находится множество фишек 1’1+1`2+1`3+1`4 (номер компьютера, которому необходимо передать пакет), в позиции p3 – фишка 1`"aaa", т.е. передаваемый текст. Передаваемому пакету присваивается произвольный номер, взятый из позиции p2. Пакет формируется в позиции p4.

При срабатывании перехода t1 из позиции p4 извлекается фишка, обозначающая пакет (например, ) и с задержкой tsp (на время готовности) передается в позицию p5. В примере tsp = 10 нс.

Следующим срабатывает переходt 2-1 или t2-2 в зависимости от случайной задержки zad1 (время прохождения пакета по компьютерной сети от передатчика к приемнику, счетчик времени увеличивается на величину от 1 до 100 нс.). В зависимости от величины задержки фишка попадает в позицию p6 (т.е. пакет успешно передан) или возвращается назад в позицию p4 (если zad1 > 89, т.е. считается, что пакет потерян при передаче и подлежит повторной передаче).

Переходы t3-1, t3-2, t3-3 и t3-4 анализируют пришедшую в p4 информацию, распределяя пакеты по соответствующим компьютерам. В p8 отправляется фишка с номером пакета и временной меткой t0+tsp+zad1, т.е. формируется информация о подтверждении прохождения пакета с указанием номера пришедшего пакета и временем его получения (т.е. формируется «квитанция» о получении пакета).

Передача «квитанции» по обратному каналу происходит следующим образом. Фишка из позиции p8 с накопленной временной задержкой проходит через переход t5, при этом временная метка увеличивается на случайную величину zad2 (время прохождения «квитанции»). Это и служит сигналом для передачи очередного пакета. В рассматриваемом примере это время составляетот 1 до 100 нс. (фишка zad2 из позиции z2).

После этого происходит подготовка системы к передаче очередного пакета, т. е. идет задержка на величину twait (в примере – twait = 10 нс.). Если передача информации с первым пакетом прошла успешно, то идет передача второго информационного пакета. Если же в ходе информационного обмена произошла потеря пакета, то начнется повторная передача первого с текущей временной отметкой.

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

Структура сети Петри из нескольких множеств позволяет легко модифицировать модель. Это позволяет оценить временные затраты при различном числе переданных пакетов. Было проведено более 100 экспериментов, по результатам которых было оценено время и надежность передачи пакетов.

Выводы и результаты

Таким образом, предложена методика оценки передачи данных по компьютерной сети с учетом возможных сбоев, построена сеть Петри, позволяющая моделировать этот процесс. По результатам тестирования модели получилось, что передача 5 пакетов происходит в течение 700 – 1500 нс., при этом потеря одного пакета при передаче может происходить до 3 раз. Это примерно соответствует действительности.

Построенная модель позволяет также оценить время передачи пакетов при различном их количестве и размере вероятной ошибки передаче. Для изменения числа передаваемых пакетов необходимо изменить размерность цвета NOMER (варьируя его от 1 до нужной величины). Вероятность ошибки припередачи информации регулируется блокировочными функциями G(t2-1) и G(t2-2).

По результатам эксперимента получилось, что при увеличении вероятности ошибки на 5 % время передачи пакетов увеличивается примерно на 3 % – 5 %.

Описанная модель протокола передачи данных позволяет исследовать характеристики его работы. Варьируя временные задержки tspи twait, функции скорости передачи пакетов (zad1 и zad2) и «датчиков» потери пакета и «квитанции» можно путем имитационного моделирования (многократного «прогона» пакетов через CPN) подобрать параметры протокола, обеспечивающие его эффективную работу.

При работе на сетевой аппаратуре все указанные задержки можно настроить программными или аппаратными методами.

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

Рисунок 2. Время передачи пакетов

Рецензенты:

Доррер Георгий Алексеевич, д-р техн. наук, профессор, ФГБОУ ВПО «Сибирский государственный технологический университет», г. Красноярск.

Ченцов Сергей Васильевич, д-р техн. наук, проф., зав. кафедрой систем автоматизации автоматизированного управления и проектирования ИКИТ СФУ, г. Красноярск.