Волновой метод маршрутизации впервые был предложен мною для сети с коммутацией сообщений в заявке в Комитет по делам изобретений и открытий при Совете министров СССР №1515512 с приоритетом от 18.02.70. При этом предполагалось, что атрибуты сети, в частности топология либо начально неизвестны, либо могут существенно изменяться.
В этой заявке мною был предложен способ поиска оптимального пути от узла УИ к одному из узлов УП. При этом в узле УИ формировался запрос о выборе оптимального пути к УП. Этот запрос размножался и передавался в сеть волной по множеству возможных путей к адресату. При этом совокупностью узлов сети решалась задача выбора кратчайшего пути между УИ и УП. Выбранный путь запоминался при передаче по нему ответа от УП к УИ.
Было оформлено (находится в Роспатенте РФ) в закрытом доступе (холодная война однако была!) — авторское свидетельство № 73 730 с приоритетом от 06.09.73 на «способ автоматической коммутации сообщений».
Определимся сначала с терминологией
Термины и определения будут мною использованы из многоязычной интернет-энциклопедии под названием википедия, а именно из следующих материалов:
Краткая история развития электросвязи -> Телекоммуникационные системы и сети -> Часть 1. Способы передачи сообщений, Раздел 9.5 Методы маршрутизации в сетях электросвязи, страница 30.
Делаем выписку из этих материалов:
«Основные определения. Маршрут (Route) - список элементов сети связи УК (узлов коммутации), линий связи, каналов связи), начинающийся с узла-источника (УИ) и заканчивающийся узлом-получателем (УП). Маршрутизация (Routing) - процедура, определяющая оптимальный по заданным параметрам маршрут на сети связи между узлами коммутации».
Далее на стр.30 приводятся известные методы маршрутизации: метод рельефа и волновой метод маршрутизации.
Известные методы маршрутизации
Метод рельефа обычно используется в системах с сервером маршрутов, который согласно семиуровневой модели ВОС (цитата со страницы 31): «собирает и анализирует информацию о топологии сети, а затем по запросам передает её маршрутизаторам, которые освобождены от функций создания ПРИ». (ПРИ- план распределения информации в сети).
Так называемый волновой метод маршрутизации, в котором (цитируем со стр.30) «при поступлении заявки на организацию маршрута между парой узлов в УИ формируется поисковая посылка, которая пересылается ко всем соседним с ним узлам. В соседних УК эта процедура повторяется. Таким образом, поисковая посылка попадает во все узлы сети причем через время, равное времени его передачи по кратчайшему маршруту».
Недостаток волнового метода, локально-волновой метод
Цитирую далее из вышеупомянутых материалов:
«Основным недостатком волнового метода маршрутизации является дополнительная нагрузка, которая создается передачей поисковой посылки во все стороны, в том числе и в противоположную сторону от УП». Поэтому предлагается некий локально-волновой метод маршрутизации, который «состоит в том, что для нахождения кратчайшего маршрута в сети между парой узлов из УИ организуется волновой поиск, но не во всех направлениях, а лишь в сторону УП».
Однако как автор волнового метода маршрутизации выражаю своё несогласие только с такой трактовкой возможностей волнового метода и поэтому предлагаю на конкретных примерах рассмотреть другие варианты.
Во-первых, метод был предложен в качестве альтернативы методу рельефа, как основному методу, использующему знания о топологии сети; во-вторых, нас интересовали прежде всего такие важнейшие характеристики как живучесть сети и время передачи сообщений.
Волновой метод не понимает, что такое противоположная сторона УП. Для него это может просто маршрут, который является кратчайшим с наименьшей вероятностью среди прочих. Но существуют гипотетические случаи, когда такой маршрут может оказаться единственным.
Определяющим параметром волнового метода является ВРЕМЯ доведения сообщений, которое автоматически учитывает и топологию, и пропускную способность, и загрузку рёбер и узлов сети.
Пример: сеть из 13 узлов коммутации
Сущность нашего технического решения поясним на примерах, рассмотрев использование предлагаемого технического решения в динамике создания и эксплуатации сети передачи данных. Граф сети связи, рассматриваемый в качестве примера, приведён на рисунке.
Это, например, сеть из 13 узлов коммутации (УК). Каналы передачи данных в направлениях сети следующие: УК8-УК2, УК2-УК1, УК1-УК3, УК3-УК4, УК3-УК5, УК4-УК9 все на скорости 2400 бод, остальные на скорости 50 бод.
ЗАДАЧА№1
Вводится в эксплуатацию УК13. В нём направление УК13-УК9 на 2400 бод, другие на 50 бод. Необходимо построить списки кратчайших маршрутов между УК13 и всеми остальными УК сети.
Для этого в УК13 формируется многоадресный запрос сл��дующего содержания: адрес УК13 (адрес УИ), приоритет передачи запроса (в данном случае высший), число требуемых маршрутов (например, два), адреса всех УК от (1 до 12), к которым требуется установить списки кратчайших маршрутов.
Этот запрос из УК13 передаётся по всем исходящим направлениям из узла УК13 и поступает в транзитные узлы. Далее на примере транзитного узла, например, УК8 поясним алгоритм обработки запроса.
При получении первой копии запроса УК8 находит среди адресов свой адрес (УК8) и запоминает эту копию запроса вместе с номером входящего направления, из которого она поступила (в нашем случае номер направления УК13-УК9-УК8). В этой копии запроса адрес УК8 помечается как «обслуженный» и он ретранслируется по всем исходящим из УК8 направлениям, кроме естественно УК8-УК13.
В нашем примере вторая копия запроса может поступить из УК4, пройдя длинный по числу транзитов путь УК8-УК2-УК1-УК3-УК4-УК8, однако эта копия запроса будет проигнорирована из-за пометки в нём адреса УК8, т.к. это копия, порождённая самим УК8.
Третья копия запроса поступит от УК9, пройдя путь УК13-УК10-УК9-УК8. Поскольку в ней будет содержаться «необслуженный» адрес УК8, она поступит в обработку, при которой будет запомнено направление связи для пути второго приоритета между УК13 и УК8. Но это копия хранящегося запроса, она будет уничтожена и дальнейшей трансляции не подлежит.
Таким образом, УК13 узнаёт, что у него есть два оптимальных пути к УК8. Отметим только, что УК8 при выборе очередного маршрута передаёт в выбранное направление ответ с номером приоритета этого маршрута в списках.
Отметим ещё одно существенное обстоятельство, что рассматривался гипотетический случай, когда все УК появляются в сети одновременно. На практике это не так: УК13 вводится в строй тогда, когда уже функционируют остальные 12 узлов (или часть их), а это означает, что в них уже есть списки кратчайших путей и ничто не мешает гнать волну локально по ранее выбранным кратчайшим маршрутам.
Таким образом, формируются списки кратчайших маршрутов без учёта очередей в транзитных УК. Заметим, что маршрутов между УИ и УП формируется несколько, что позволяет говорить о появлении в сети передачи данных виртуальной сети кратчайших маршрутов между УИ и УП.
Кстати, в запрос можно включать и другие требования к сети кратчайших маршрутов, например, для выборки кратчайших маршрутов с учётом класса мощности каналов.
ЗАДАЧА №2
Итак, списки кратчайших по скорости каналов маршрутов построены. Создана сеть кратчайших маршрутов от УИ к УП. В этой сети можно вводить различные процедуры по оптимизации управления распределением потока информации, например, широко известную процедуру оценки качества системы по среднему.
Имеется ввиду, что можно проранжировать кратчайшие маршруты по времени доставки сообщений. Снова формируется вышеупомянутый запрос, в котором указываются адреса УП (возможно один, возможно несколько, возможно все) с низшим (как для всех сообщений) приоритетом его передачи.
Этот запрос передаётся в сети локальной волной в каждый адрес по выбранным ранее кратчайшим маршрутам, но уже становясь в конец очереди сообщений. Дальнейшая обработка аналогична вышеизложенной. В конечном счёте производится коррекция списков оптимальных путей с учётом среднего времени доставки сообщений.
При этом используется всё тот же волновой метод маршрутизации, но уже в выделенной области сети с передачей локальной волны. И везде господствует в выборках время, а не топология.
ЗАДАЧА №3
По сети произведено глобальное внешнее воздействие, которое породило значительные изменения в ней, приведшее, в частности, к выходу из строя центров управления. Понятно, что это потребует решений, аналогичных изложенным в задаче №1.
Двухэтапное использование волнового метода
Таким образом с точки зрения минимизации потока служебной информации (т.е. запросов) волновой метод маршрутизации целесообразно использовать двухэтапно:
на первом этапе, в частности при вводе УИ в эксплуатацию, созданием от УИ к УП списков кратчайших маршрутов путём передачи многоадресного запроса по всем возможным маршрутам;
на втором этапе при оптимизации распределения сообщений в сети кратчайших маршрутов путём передачи локальной волны.
Заключение: сравнительный анализ
В заключение небольшой сравнительный анализ метода рельефа и волнового метода маршрутизации.
Вот у Вас есть сеть передачи данных. На листе бумаги Вы изображаете эту сеть в виде графа сети. Первое, что приходит в голову человеку - это топология сети, сетевой администратор задаёт конфигурацию сети.
Далее, понимая, что кроме топологии есть кое-что ещё, администратор навешивает на рёбра графа, как говорится «до кучи», всевозможные атрибуты, например, стоимости рёбер графа или пропускные способности и тому подобное. Есть протоколы, которые обрабатывают атрибуты, их немало, как и разработчиков.
Возможно есть какой-то синтезатор всего в единую политику (тот же сетевой администратор). Но есть и бизнес-политика. Если администратор бизнесмен, то он может, исходя из своей бизнес политики, проигнорировать все эти «до кучи» атрибуты, руководствуясь только стоимостью.
Попутно заметим, что сами узлы вроде бы и вне игры. Существует нечто (или некто), которое всем управляет или нет? И где оно? Это нечто в википедии назвали «сервером маршрутизации». На самом деле за кулисами прячется сетевой администратор (режиссёр, босс).
Система с точки зрения системной идеологии обыкновенный центристский полуавтомат, и этим полуавтоматом в центре управляет сетевой администратор.
Теперь о волновом методе маршрутизации. Необходимо создать АСУ для решения определённых задач. В АСУ в качестве инструмента входит сеть передачи данных. Атрибуты такой сети передачи данных неизвестны, более того они могу существенно изменяться.
Что является важнейшим , основным параметром таких сетей, что синтезирует все атрибуты сети, кроме стоимости?
Отвечаю - время доставки информации из УИ в УП.
Волновой метод в отличие от централизованной полуавтоматической системы позволяет построить простую, децентрализованную, полностью автоматическую систему. Центр должен определять и требовать только следование некоторым целевым параметрам.
Списки кратчайших маршрутов могут использоваться как для режима виртуального канала, так и режима дейтаграмм.
