Локально волновой метод маршрутизации

Параллельный выбор исходящих ТПС

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

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

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

Рассмотрим локально волновой метод [1], который является обобщением волнового метода маршрутизации и логического способа получения ПРИ на сети связи. Локально волновой метод маршрутизации в зависимости от организации выбора исходящего ТПС может быть отнесен к параллельным и параллельно последовательным методам. В то же время, способ выбора зоны, в которой осуществляется поиск маршрута, в локально волновом методе может быть вероятностным, детерминированным и комбинированным.

Локально волновой метод маршрутизации состоит в том, что для нахождения кратчайшего маршрута в сети между парой узлов из УИ организуется волновой поиск, но не во всех направлениях, а лишь в сторону УП. Волна поиска при этом распространяется в некоторой зоне в виде полосы, охватывающей пару соединяемых узлов (Рисунок 3.4). Ширина и форма полосы в зависимости от приоритета абонента может устанавливаться в заданных пределах. На рисунке 3.4 показан локально волновой поиск на сети от УИ к УП в некоторый момент времени, соответствующий примерно половине пути между парой узлов. Из рисунка видно, что поисковая волна ¾ это подвижная узкая зона, все узлы в пределах которой охвачены процессом волнового поиска. По мере продвижения к УП волна оставляет за собой ТПС, исходящие из начального узла.

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

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

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

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

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

· В случае занятости УП, невозможности доступа к нему или его повреждения, распространение волны поиска должно быть приостановлено, а все выбранные волной ТПС должны само распадаться.

· Доступ к УП должен быть обеспечен со всех входящих в него ТПС.

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

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

· Набранный таким образом маршрут фиксируется на все время обмена между заданной парой узлов. По окончании обмена маршрут также распадается.

Организация локально-волнового метода маршрутизации может быть следующей.

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

Для данного узла в Т-й строке таблицы содержится следующая информация.

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

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

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

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

Процесс организации в сети локально волнового поиска маршрута инициируется УИ. В УИ, при этом формируется поисковая посылка, в состав которой входят:

· номер УП;

· номер УИ и индекс, отличающий данный поиск от других, одновременно исходящих с одного и того УИ;

· приоритет поиска;

· абсолютное время, до которого разрешается существование данного поиска;

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

Поисковая посылка в УИ подвергается анализу: определяются с учетом приоритета те тракты, по которым должна распространяться данная волна поиска. Если в этих ТПС есть свободные каналы, то они резервируются данным поиском. По этим же каналам (либо по специально выделенным служебным каналам) на инцидентные узлы передается поисковая посылка. На инцидентных узлах данная посылка подвергается такому же анализу, и также резервируются свободные каналы в выбранных ТПС. На всех последующих узлах процесс повторяется аналогично описанному.

Выводы

1. При организации маршрута между заданной парой УК выбор исходящих ТПС в каждом УК сети может быть последовательным и параллельным.

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

3. Реализация градиентных алгоритмов выбора исходящих ТПС позволяет организовать кратчайшие маршруты (по числу транзитных УК).

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

5. Независимо от характера распространения на сети процесса поиска маршрута (градиентный, диффузный и комбинированный) процедура выбора ИТПС в каждом УК может быть детерминированной, вероятностной и вероятностно детерминированной.

6. Локально волновой метод маршрутизации в зависимости от характера организации выбора ИТПС может быть отнесен к параллельным и последовательным методам.

7. Выбор ширины зоны поиска в локально волновом методе может быть вероятностным, детерминированным и вероятностно детерминированным.