УДК 658.012

В. Т.ЕРЕМЕНКО, Л. В. КУЗЬМИНА

V. T. EREMENKO, L. V. KUZMINA

РАСПРЕДЕЛЕНИЕ ИНФОРМАЦИИ В МУЛЬТИСЕРВИСНЫХ ПРОМЫШЛЕННЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ С УЧЕТОМ НЕОПРЕДЕЛЕННОСТИ ЭЛЕМЕНТОВ

INFORMATION DISTRIBUTION IN MULTISERVICE INDUSTRIAL NETWORKS DATA BASED ELEMENT OF UNCERTAINTY

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

Авторы исследуют алгоритмы распределения информации в сетях передачи данных с учетом неопределенности элементов.

Ключевые слова: сети передачи данных, автоматизированные системы управления (АСУ), маршрутизаторы.

The article is devoted to algorithms in order to minimize total flow at critical sections on the network and on the network parts having a high load due to topological features or characteristics of used routing methods.

The author investigates the algorithms of information distribution in data networks with the uncertainly elements.

Keywords: data networks, automated control systems (ACS), the criterion of minimal total flow, router.

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

НЕ нашли? Не то? Что вы ищете?

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

Алгоритмы распределения информации. Одним из направлений разрешения этой проблемы является устранение априорной неопределенности о состоянии элементов сети, что позволяет снизить ее негативные последствия, связанные с перегрузкой и блокировкой. Это возможно на основе использования алгоритмов прогнозирования и статистического машинного моделирования функционирования средств и каналов передачи данных, входного трафика. К недостаткам данного подхода можно отнести более высокие требования по быстродействию и объему памяти в узлах сети. Использование релаксационных нейронных сетей для решения задачи поиска кратчайших путей в современных маршрутизаторах связано с большей трудоемкостью по сравнению с традиционными алгоритмами. Изменение пропускной способности линий связи приводит к полному перерасчету маршрутной таблицы. С ростом размера составной сети трудоемкость этой операции растет полиномиально, что не может не сказаться на производительности всей сети в целом [2,4,5,8 ].

В процессе работы маршрутизатор СПД АСУ должен поддерживать в актуальном состоянии таблицу распределения информации приходящих пакетов. Данная таблица строится на основании информации о достижимости, полученной от других маршрутизаторов сети. Задержки передачи по линиям связи не являются постоянными и изменяются с течением времени. Это происходит в силу воздействия различных факторов, и маршрутизатор должен обработать эти изменения, пересчитав кратчайшие пути и занеся результаты в маршрутную таблицу. В общем случае приходится полностью перестраивать дерево кратчайших путей, что является достаточно трудоемкой задачей. В ряде случаев удается уменьшить трудоемкость. В некоторых сетях передачи данных используются алгоритмы ускоренной маршрутизации, в которых используется метод поиска оптимальных маршрутов для передачи пакетов данных от узла-отправителя к узлу - получателю через составную вычислительную сеть в условиях динамически меняющихся значений задержек передачи по линиям связи. Такие алгоритмы, позволяют сократить трудоемкость этой операции путем частичного изменения дерева кратчайших путей за счет использования априорно вычисленной информации.

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

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

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

Задача считается хорошо определенной, если выполняются следующие предположения [8]:

1.  Для каждой вершины и существует путь из в .

2.  Никакой путь из в не содержит контур отрицательной длины.

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

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

Таким образом, можно ограничить задачу построения дерева кратчайших путей вычислением весов . Для этого следует рассматривать как решения множества уравнений, известных как уравнения Беллмана:

;

для .

Показано [2,5,6,7,8], что когда G не имеет отрицательных контуров, решение уравнений Беллмана единственно. В противном случае оно будет единственно при дополнительном предположении, что максимальна среди всех решений [1].

Пусть S - такое подмножество V, что . Обозначим через дополнение S до V. Таким образом, .

Пусть Р - путь минимальной длины среди всех ориентированных путей из к вершине в . Длина пути Р называется расстоянием от до .

Пусть . Тогда ясно, что и . Далее, часть пути Р из , в должна быть наикратчайшим - путем, вершины которого принадлежат S. Поэтому . Отсюда видно, что расстояние можно вычислить по формуле;

(1)

Тогда если - такое, что для некоторого , то (2)

Известно, алгоритм Дейкстры порождает последовательность , ... таких подмножеств V, что выполняются следующие условия:

1.  Если - такие вершины из множества V, что

, то для

2.  Когда множество определено, известны и кратчайшие пути из в . Для множеств , определенных выше соотношением (2), справедливо равенство:

(3)

Таким образом, построение 5/+у по включает в себя вычисление Подмножества можно построить в соответствии с выражением (1) следующим образом:

Следовательно, согласно формуле (3), - вершина, для которой выполняется равенство:

Если - кратчайший путь из вершины к вершине то . Предположим, что подмножества и пути , уже известны. Тогда для определения мы вычисляем , используя выражение (1).

Из равенства (3) следует, что - вершина в , обладающая свойством . Из выражения (1) следует, что существует такая вершина , что . Поэтому можно получить , присоединяя ребро к пути .

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

В этой процедуре необходимо вычислять минимум в выражении (1.) на каждом этапе. Если этот минимум действительно вычислялся бы на каждом этапе, то определение , по потребовало бы сложений и сравнений. Общее число операций для выполнения всего алгоритма составило бы в общей сложности 0(п3) шагов. Однако многие из этих сложений и сравнений не обязательно должны каждый раз повторяться.

В алгоритме Дейкстры устранены такие повторения за счет сохранения полученной на одном из этапов информации для последующих этапов. Это достигается процедурой расстановки меток, которая уменьшает сложность алгоритма до 0(п2). Следующие соображения приводят к процедуре расстановки меток Дейкстры [7]. Предположим, что осуществляется расстановка меток так, что для i=0,1,2,… метка вершины v удовлетворяет следующим требованиям:

1.  и для всех

2.  Для для всех , для всех . Ясно, что - вершина, для которой .

Теперь можно определить по :

3.  Для

4.  Для

(4)

Тогда выбирается так, что

(5)

Отметим, что метка v не меняется после определения .Таким образом, алгоритм Дейкстры начинает работу с меток и для всех .По мере выполнения алгоритма метки модифицируются в соответствии с выражением (4). Метки задают расстояние от до .

Определение включает вычисление для всех , и последующее нахождение минимума среди этих меток. Для первое вычисление по формуле (4) требует сложений и сравнений, тогда как последние действия по формуле требуют сравнений [5].

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1.  Введение в разработку и анализ алгоритмов. [Текст] / Хидетниеми С - М.: Мир, 19с.

2.  Еременко и приемы предотвращения блокировок процессов информационного обмена в сетях передачи данных предприятия. [Текст] / , , // «Вестник компьютерных и информационных технологий», №12 - С.

3.  Еременко поведения транспортных протоколов в корпоративных сетях в условиях интенсивного трафика. [Текст] / , , // Известия ОрелГТУ - 2008, №4 - 3/272(550) - С

4.  Еременко управления информационными потоками в сетях передачи данных на основе резервирования ресурсов. [Текст]. / , , // Методы и устройства передачи и обработки информации. Межвузовский сборник научных трудов. Выпуск 11. - М.: «Радиотехника», 2009. - С.

5.  Еременко взаимодействия протокольных реализаций TCP RENO и TCP VEGAS в сети с ограниченной производительностью. [Текст] / , // Информационные системы и технологии - 2010, № 1. - С.

6.  Касьянов в программировании: Обработка, визуализация и применение /, //- СПб.: БХВ-Петербург, 2003.-1104с.

7.  Колосов и методы оптимального размещения информационных ресурсов в научно-образовательных телекоммуникационных сетях. [Текст] / - М.:2005.- С.152.

8.  Алгоритмы: построение и анализ. / // - М.: Центр непрер. матем. Образования, 20с.

Государственный университет – УНПК, г. Орел

Профессор

Доктор технических наук

Зав. кафедрой ЭВТИБ

Тел.419879

E - mail: *****@***ru

Государственный университет – УНПК, г. Орел

Аспирант кафедры ЭВТИБ

537

E - mail: *****@***ru