Алгоритм анализа топологии сети на совместимость с неблокируемой маршрутизацией

УДК 004.738.5.057.4

В. Т. ЕРЕМЕНКО, А. И. ОФИЦЕРОВ, С. И. АФОНИН

V. T. EREMENKO, A. I. OFICEROV, S. I. AFONIN

АЛГОРИТМ АНАЛИЗА ТОПОЛОГИИ СЕТИ НА СОВМЕСТИМОСТЬ

С НЕБЛОКИРУЕМОЙ МАРШРУТИЗАЦИЕЙ

ALGORITHM OF THE ANALYSIS TO NETWORK TOPOLOGIES ON COMPATIBILITY WITH UNLOCKABLE ROUTING

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

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

The Article is dedicated to description of the algorithm of the analysis to network topologies on compatibility with unlockable routing. This algorithm checks that there is possibility from any node to reach any other node to network two or more independent on nodes and rib fetter that corresponds to the determination unlockable routing. The Result of the functioning the algorithm is a conclusion about combine-bridges to network topologies with unlockable routing.

Key words: data network, unlockable routing, routing graph, algorithm, topology, compatibility.

ВВЕДЕНИЕ

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

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

ПОСТАНОВКА ЗАДАЧИ.

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

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

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

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

1) узел-получатель должен быть достижим всеми остальными узлами, т. е. ;

2) каждый узел, кроме узла-получателя, должен иметь степень выхода не менее чем 2, т. е. ;

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

;

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

;

5) если два узла и взаимно достижимы в , то они являются соседями, а связь между ними – это резервная дуга, т. е. и .

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

1)  если для заданной топологии сети возможно построить граф неблокируемой маршрутизации к заданному адресату, то этот граф используется в качестве графа маршрутизации;

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

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

РЕАЛИЗАЦИЯ АЛГОРИТМА

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

Пусть – неориентированный граф, подлежащий проверке на совместимость с неблокируемой маршрутизацией (рис. 1).

Рис. 1. Исходный неориентированный граф G

Шаг 1. Трансформировать граф в граф следующим образом: для всех пар треугольников и (где , в то же время ) представить узлы и как пары узлов и , соединённые виртуальными рёбрами и , а также рёбрами , . Полученный граф обозначается как (рис. 2).

Рис. 2. Граф – результат работы первого шага алгоритма

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

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

Рис. 3. Граф – результат работы второго шага алгоритма

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

Результатом работы алгоритма является вывод о совместимости топологии сети с неблокируемой маршрутизацией (рис. 4).

Рис. 4. Алгоритм анализа топологии сети на совместимость с неблокируемой

маршрутизацией

ОБОСНОВАНИЕ КОРРЕКТНОСТИ АЛГОРИТМА

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

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

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

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1.  , Константинов процессов анализа реализаций протоколов информационного обмена для решения задач описания их статического и динамического взаимодействия // Вестник компьютерных и информационных технологий – № 4. – 2004. – С. 11 – 15.

2.  Коннов теория графов / , , . – М: Народное образование, 1999. – 240с.

3.  Алгоритмы: построение и анализ: пер. с англ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 2001. – 960 с.

4.  Анализ алгоритмов. Вводный курс: пер. с англ. / Д. Макконнелл. – М: Техносфера, 2002. – 304с.

5.  Офицеров оптимизации мультимедийного трафика в многоприоритетных сетях. [Текст]. / // Известия Орловского государственного технического университета. Серия «Информационные системы и технологии». III Всероссийская научно-практическая Интернет-конференция «Методы прикладной математики и компьютерной обработки данных в технике, экономике, экологии». Труды конференции. – Орел: Изд-во ОрелГТУ, 2006.– № 2 – С.147 – 155.

СВЕДЕНИЯ ОБ АВТОРАХ

Заведующий кафедрой «Электроника, вычислительная техника и информационная безопасность»
Госуниверситет – УНПК (г. Орел)
доктор технических наук, профессор

Тел.: + 7(4862)
E-mail: *****@***ru

Преподаватель кафедры «Сети связи и системы коммутации»
Академия ФСО России, г. Орел
Тел.: + 7(4862)
E-mail: *****@***ru

Афонин Сергей Иванович Докторант кафедры «Информационные системы»
Госуниверситет – УНПК (г. Орел)
Тел.: + 7(4862)
E-mail: *****@***ru