Игровой метод

Игровой метод [4, 6] предусматривает формирование ПРИ по накопленной ранее статистике установления соединения между заданной парой УК.

Перед началом функционирования на сети устанавливается начальный ПРИ в виде набора таблиц маршрутизации (1.1).

Каждому значению m ^(j) _iv присваивается некоторый весовой коэффициент p ^(j) _i1. Причем, = (p ^(j) _i1, …, p ^(j) _iv,…, p ^(j) _iHj); v = нормируется

.

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

, (2.1)

где = (p ^(j)_i1,…, p ^(j) _iv,…, p ^(j) _iHj); v = . (2.2)

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

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

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

Пример 2.2.

Покажем формирование ПРИ на сети, изображенной на Рисунке 1.3, игровым методом. Будем считать, что начальный ПРИ задан в виде таблиц маршрутизации примера 1.4.

Весовые коэффициенты (2.1) для узлов сети имеют следующий вид

P ⁽¹⁾ P ⁽²⁾

P ⁽³⁾ P⁽⁴⁾

Допустим, что необходимо определить маршрут между УИ под номером 2 и УП № 1. При этом количество транзитных УК не должно превышать одного.

В УИ № 2 из таблицы весовых коэффициентов P ⁽²⁾ выбираем вектор строку = (0,6; 0,1; 0,3). Исходящим ТПС первого выбора является ТПС к УК № 1. Предположим, что данный ИТПС в настоящий момент времени недоступен. Так как, P ⁽²⁾_1,4 P ⁽²⁾_1,3 , то исходящим ТПС второго выбора является ТПС к УК № 4. Допустим, что ИТПС из УК № 2 к УК № 4 в данный момент времени доступен. Следовательно, данный ТПС участвует в организации искомого маршрута.

В УК № 4 в соответствии с = (0,7; 0,2; 0,1) выбираем исходящий ТПС к 1-му УК, так как P ⁽⁴⁾_1,1 P ⁽⁴⁾_1,2 P ⁽⁴⁾_1,3. Допустим, он доступный.

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

= (0,5; 0,08; 0,42); =.(0,75; 0,17; 0,08).

Обратим внимание на вектор = (0,5; 0,08; 0,42). Весовой коэффициент P ⁽²⁾_1,1 уменьшился. Однако он остается максимальным из всех весовых коэффициентов в данном векторе. Следовательно, соответствующий ТПС остается исходящим ТПС первого выбора.

Если ситуация поиска маршрута между заданной парой УК повторится, т.е. повторно будет организован маршрут m_2,1 = {2, 4, 1}, то вектора , изменятся и примут следующий вид: = (0,42; 0,07; 0,51); = (0,79; 0,14; 0,07). Анализируя ситуацию с вектором видно, что исходящий ТПС к УК № 4 из УК № 2 при поиске маршрута к УК № 1 принял значение первого выбора, т.к. его весовой коэффициент P ⁽²⁾_1,4 стал максимальным из всех возможных в данном векторе.

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

Таким образом, по результатам поиска маршрутов в предыдущие моменты времени формируется ПРИ на сети связи.

Если рассматривать весовые коэффициенты p ^(j) _iv как вероятности выбора соответствующих исходящих ТПС m ^(j) _iv, то можно предположить, что игровой метод формирования ПРИ имеет итеративный характер и решает задачу глобальной оптимизации сети связи по критерию ¾ вероятность установления соединения между парами УИ и УП.

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

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

Дата добавления: 2014-11-18