7.2. Методы формирования плана распределения информации

Метод рельефов. Суть данного метода состоит в следующем. Пусть  - произвольный УК сети связи, из которого по всем исходящим линиям связи передается число 1. Все УК, в которые поступило число 1, передают число 2 по всем исходящим линиям связи, кроме тех по которым поступило число 1. Далее УК, на которые поступило число 2, передают число 3 по линиям связи, по которым не поступало 2 и 1. Данная процедура повторяется до тех пор, пока все линии связи не окажутся пронумерованными. Говорят, что линия связи имеет высоту , если она обозначена числом . В результате формируется рельеф с разными высотами для конкретного узла сети. Подобным образом формируется рельеф из каждого узла сети.

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

В качестве примера рассмотрим построение маршрутов для сети связи, представленной на рис. 7.3 а).

Рис. 7.3. Сеть связи с А-рельефом

Построим рельеф на сети относительно УК А (рис. 7.3 б). Узел А передает число 1 по линиям связи АВ, АС, АD. Узлы B, C и D передают число 2 по линиям связи BG, BC, CI, CK, CD и DK в узлы G, I и K. Данный процесс продолжается пока все линии связи не окажутся пронумерованными.

Чтобы найти кратчайший маршрут от произвольного УК к узлу А достаточно в каждом УК выбирать исходящую линию связи с наименьшим весом. Например, кратчайший маршрут от УК N до УК А будет следующий:

или

, .

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

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

.

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

Таким образом, в процессе эксплуатации сети происходит формирование ПРИ в соответствии со значениями весовых коэффициентов.

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

; ;

; .

Допусти, что необходимо определить маршрут между УИ №2 и УП №1. В УИ №2 из таблицы весовых коэффициентов  выбираем вектор . Исходящей линией связи первого выбора является линия связи №1. Предположим, что данная линия в настоящий момент не доступна. Тогда в соответствии со значениями вектора  выбираем исходящую линию связи №4 второго выбора. Если данная линия связи свободна, то переходим в узел №4. В данном узле выполняем аналогичные действия по определению исходящей линии связи. Выбираем вектор  матрицы  и определяем номер линии связи первого выбора. В данном случае это линия, связывающая узел №4 с УП №1. Если она оказывается свободной, то получаем искомый маршрут , а линии связи, участвующие в организации маршрута поощряются, т.е. увеличиваются весовые коэффициенты  и  (предположим, что на 0,2). После нормировки вектора  и  принимают следующий вид:

; .

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

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

Логический  метод состоит в процедуре, выполняемой в каждом транзитном УК, начиная с УИ, и позволяющей определить исходящую линию связи, максимально близкой к геометрическому направлению на УП. Для этого сеть связи вкладывается в прямоугольную систему координат, в которой каждому узлу сети присваивается координата , называемая адресом узла (рис. 7.4).

Рис. 7.4. Сеть связи в прямоугольной системе координат

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

Рассмотрим пример сети связи, в которой УИ и УП имеют координаты {1, 2} и {10, 2} соответственно (рис. 7.5). Из УИ определяем геометрическое направление на УП (указано пунктиром). С данным направлением совпадает исходящая линия связи к узлу с координатами {4, 2}. В УК {4, 2} выбираем исходящую линию связи к УК с координатами {7, 3}, т.к. она имеет наименьший угол отклонения от геометрического направления на УП. В УК {7, 3} подобным образом выбираем линию связи к УК {8, 2}. В УК {8, 2} выбираем линию связи к УК {10, 2}.

Рис. 7.5. Пример формирования ПРИ логическим методом

Таким образом: . Достоинством данного метода является простота и отсутствие необходимости передачи служебной информации по сети. В то же время логический метод не является динамическим и не решает задачу глобальной оптимизации ПРИ.