Материал: Телекоммуникационные системы и сети - КНИГА

Игровой метод [15, 16] формирует ПРИ по накопленной ранее статистике установления соединения между заданной парой УК. Перед началом функционирования на сети устанавливается начальный ПРИ в виде набора таблиц маршрутизации (9.3). Каждому значению присваивается некоторый весовой коэффициент . Причем, нормируется

В результате формируется матрица весовых коэффициентов

(9.5)

где (9.6)

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

Таким образом, в процессе эксплуатации сети формируется оптимальный ПРИ. Критерием оптимальности является результат организации маршрутов.

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

Допустим, что необходимо определить маршрут между УИ №2 и УП №1. При условии, что количество транзитных УК не должно превышать одного. В УИ №2 из таблицы весовых коэффициентов P⁽²⁾ выбираем вектор строку Исходящей ЛС первого выбора является ЛС к УК №1. Предположим, что данная ЛС в настоящий момент времени недоступна. Так как , то исходящей ЛС второго выбора является ЛС к УК №4. Допустим, что исходящая ЛС из УК №2 к УК№4 в данный момент времени доступна. Следовательно, данная ЛС участвует в организации искомого маршрута. В УК №4 в соответствии с выбираем исходящую ЛС к УК №1. Допустим, она доступна. Следовательно, маршрут между УИ и УП μ_2,1 = {2,4,1} организован. ЛС, участвующие в данной процедуре, поощряются. Соответствующие весовые коэффициенты увеличиваются (предположим, что на 0.2), а вектора нормируются. В результате получаем новые числовые значения:

Если ситуация поиска маршрута между заданной парой УК повторится, то вектора изменятся и примут следующий вид: Анализируя ситуацию с вектором , видно, что исходящая ЛС к УК №4 из УК №2 при поиске маршрута к УК №1 приняла значение первого выбора, так как ее весовой коэффициент стал максимальным из всех возможных в данном векторе.

Матрицы весовых коэффициентов УК №2 и 4 примут следующий вид:

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

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

Логический метод [17] состоит в процедуре, выполняемой в каждом транзитном УК, начиная от УИ, позволяющей определить исходящую ЛС, максимально близкой к геометрическому направлению на УП.

Сеть связи вкладывается в прямоугольную систему координат. Каждому узлу сети присваивается собственный адрес (X, Y) (рис. 9.20).

Рис. 9.20. Поиск маршрута логическим методом

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

Пример 9.7.

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

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

Таким образом: μ({1, 2}; {10, 2}) = ({1,2}, {4, 2}, {7, 3}, {8, 2}, {10, 2}). Достоинством данного метода является простота и отсутствие необходимости передачи служебной информации по сети. В то же время логический метод не является динамическим и не решает задачу глобальной оптимизации ПРИ.

Логически-игровой метод [17] формирования ПРИ является обобщением логического и игрового методов. По аналогии с логическим методом сеть связи вкладывается в прямоугольную систему координат, в соответствии с которой каждому узлу сети присваивается собственный адрес (X, У). В каждом УК j имеется матрица которая имеет следующий вид:

№ УП	Координаты УП		Значения весовых коэффициентов исходящих ЛС к смежным УК с координатами
№ УП	X	Y	X_Qj	Y_Qj	…	X_Vj	Y_Vj	…	X_Hj	Y_Hj
1					…			…
…	…	…	…	…	…	…	…	…	…	…
i					…			…
…	…	…	…	…	…	…	…	…	…	…
j-1					…			…
j+1					…			…
…	…	…	…	…	…	…	…	…	…	…
S					…			…
…	…	…	…	…	…	…	…	…	…	…
S⁰					…			…

и содержит S⁰ строк. Учитывая, что возможно увеличение числа УК на сети, то S⁰ выбирают таким, чтобы S⁰ > S. Количество столбцов матрицы P⁰⁽^j⁾ для УК под номером j равно: (Н_j + 3), где H_j - число исходящих ЛС из у-го узла; три столбца отводится для номеров УП, представленных в общепризнанной нумерации и прямоугольной системе координат (X, У).

На момент ввода узла в эксплуатацию матрица содержит только информацию о смежных номерах УК с данными выраженных в прямоугольной системе координат: (X_Qj, Y_Qj), ..., (X_vj, Y_vj).....(X_Hj, Y_Hj). По мере функционирования сети связи матрица Р⁰⁽^j⁾ заполняется и корректируется.

Определение исходящих ЛС осуществляется логическим методом, а заполнение и корректировка матрицы P⁰⁽^j⁾ осуществляется игровым методом.

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

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

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

В результате градиентного выбора маршрут будет формироваться вдоль геометрического направления с УИ на УП (рис. 9.22).

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

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

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

Источник: https://tut-files.ru/previewfile/161622

Смотрите также:







Изложение содержания дела, по которому приняты судебные постановления
_-___-~1
_1-тема-СтрМетал
_10_Эмиль Золя для эл версии