ГЛАВА 2
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СТРУКТУРЫ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ
2.1. Метод двухпутевой маршрутизации на параллельных вычислительных структурах
Распределение больших объемов информации в компьютерной сети требует поиска и выбора маршрутов передачи данных от узла-источника узлу-адресату с минимальной временной задержкой. На стадии проектирования сети передачи данных и в процессе ее развития задача выбора алгоритма маршрутизации является одной из основных.
В настоящее время используется в основном фиксированная (однопутевая) маршрутизация передачи данных от узла-источника узлу-адресату. При однопутевой маршрутизации резко возрастает время задержки передачи данных в случае перегрузки компьютерной сети. С целью снижения перегрузки компьютерной сети применяют альтернативную маршрутизацию, при которой процедура выбора маршрутов использует более одного пути. Реализация альтернативной маршрутизации требует многократного решения задачи о кратчайших путях на графе-сети [1,6,7,36,47,73,84]. Это в свою очередь приводит к существенному увеличению времени решения задачи альтернативной маршрутизации, так как оценка времени решения задачи альтернативной маршрутизации известными алгоритмами на ЭВМ растет пропорционально О(q2), где q - количество узлов компьютерной сети [1]. Эффективным способом снижения времени решения задачи альтернативной маршрутизации является разработка параллельных вычислительных средств для поиска альтернативных маршрутов в компьютерных сетях. В связи с этим актуальной является задача разработки параллельных структур для поиска множества кратчайших путей в компьютерной сети.
Анализ, выполненный в первом разделе, показал, что исследования в этой области ведутся в основном в двух направлениях. Первое направление, связанное с разработкой более эффективных алгоритмов поиска на ЭВМ кратчайших путей в сетях передачи данных, ограничено оценкой вычислительной сложности алгоритмов О(q2) [1]. Второе направление, связанное с построением параллельных аппаратных средств решения задач о кратчайших путях, недостаточно развито для случая альтернативной маршрутизации, когда требуется найти множество альтернативных маршрутов передачи данных [36,48-52]. Это направление перспективно, так как время решения задачи о кратчайших путях на параллельных вычислительных средствах имеет оценку О(q) [36].
Целью раздела является разработка метода двухпутевой маршрутизации, использующего параллельные вычислительные структуры для поиска кратчайших путей.
Метод последовательно использует известные параллельные вычислительные средства решения задачи однопутевой маршрутизации. Последовательный поиск всех кратчайших путей между узлом-источником данных и узлом-адресатом на параллельных вычислительных структурах увеличивает время решения задачи альтернативной маршрутизации в К раз, где К - количество альтернативных маршрутов. Учитывая, что параллельные вычислительные средства решения задачи о кратчайшем пути имеют оценку времени решения О(q), то общее время поиска К маршрутов в компьютерной сети увеличится в К раз, но линейный характер зависимости времени решения задачи маршрутизации от сложности компьютерной сети сохраняется. Если альтернативных маршрутов несколько (К=23), то такой метод достаточно эффективен, так как более чем в два раза увеличивает допустимую нагрузку в компьютерной сети [1].
В первом разделе рассмотрены различные типы цифровых аналогов для решения задачи о кратчайшем пути [36,48-52]. Наиболее просты при реализации цифровые аналоги, в которых длина ветви графа моделируется интервалом времени между моментом прихода информации на вход модели этой ветви и моментом появления сигнала на ее выходе. Если подать в начальный узел электрический сигнал, то он, распространяясь по сети с задержкой пропорциональной весам ветвей графа, первым появится в конечном узле сети. Способ моделирования задачи о кратчайшем пути основан на временной аналогии. Рассмотрим задачу нахождения кратчайшего пути для К-путевой маршрутизации при К=2. Используем метод временной аналогии для задания веса ветви графа. Граф сети моделируем параллельной структурой, состоящей из моделей ветвей (МВ) и моделей узлов (МУ), соединенных согласно топологии сети рис.2.1. Модели узлов соединены парой моделей ветвей, которые направлены на встречу, потому, что передача данных между узлами компьютерной сети может осуществляться в противоположных направлениях с разными характеристиками пропускной способности каналов передачи данных.
Рис. 2.1. Параллельная структура графа сети
Реализуем функцию задержки сигнала на время пропорциональное весу ребра графа в моделях ветвей, в состав которых введем формирователь временного интервала ФВИ. В модели узла выделим первый сигнал, поступивший в данный узел, а в модели ветви зафиксируем с помощью индикатора ветви ИВ факт поступления первого сигнала через данную ветвь в модель узла. Обобщенная модель фрагмента графа, состоящая из пучка m ветвей, входящих в один узел, изображена на рис.2.2.
Рис. 2.2. Обобщенная модель фрагмента графа
Каждая модель ветви содержит информационный вход , информационный выход , индикационные входы , и индикационные выходы , . Модель узла содержит m информационных входов, m индикационных выходов, один информационный выход и два индикационных входа и . На первом этапе находим первый кратчайший путь с корнем в начальной вершине графа. С этой целью в модель начального узла подается электрический сигнал, который распространяется по моделям ветвей и узлов графа-сети с временной задержкой, определяемой весом ветвей. Первый сигнал, поступающий в модель узла, запоминается индикатором ветви для фиксации факта принадлежности этой ветви дереву кратчайших путей. На последующие сигналы, поступающие после первого времени сигнала, модель узла не реагирует и реализует этим функцию блокировки остальных сигналов. Процесс построения дерева кратчайших путей заканчивается после поступления перв