7.3. Алгоритмы выбора исходящих линий связи

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

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

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

Выбор линий связи, при котором искомый маршрут формируется и в противоположную сторону от УП, называется диффузным. Таким образом, диффузный выбор исходящих ЛС допускает возможность выбора любой доступной исходящей линии связи (рис. 7.6).

Рис. 7.6. Градиентный и диффузный выбор исходящих линий связи

Градиентно-диффузный метод является комбинацией первых двух.

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

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

Учитывая перечисленные градации, можно указать множество вариантов последовательных алгоритмов выбора исходящих линий связи в УК (например, «Диффузный, вероятностный» или «Градиентно-диффузный, детерминированный»).

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

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

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

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

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

Рис. 7.7. Поиск маршрута локально-волновым методом

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