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

2.1 Метод рельефов

Метод рельефов [4] предусматривает формирование плана распределения информации на сети по числу транзитных УК. Возможно использование и других параметров [3].

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

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

Рассмотрим метод рельефов только относительно i - рельефа. Тогда ТПС, с минимальной высотой, является исходящим трактом первого выбора. ТПС, с большими высотами, соответственно являются исходящими трактами второго, третьего и т.д. выбора.

Пример 2.1.

Построим рельеф на сети относительно УК A (Рисунок 2.1).

УК А по ИТПС AB, AC, AD передает число 1 и присваивает им это значение. Узлы B, C и D передают по трактам BG, BC, CI, CK, CD и DK в узлы G, I, H и K число 2. В свою очередь, узлы G, I, H и K передают по ТПС GL, GI, IL, IM, IH, HK и KO число 3. Следовательно, перечисленным трактам присваивается число 3. УК L, M, H, O, в свою очередь, передают по ТПС LM, MN, HM, HO и ON число 4 и этим трактам присваивается число 4. Таким образом, на сети строится А - рельеф (Рисунок 2.2).

Чтобы найти кратчайший маршрут от произвольного УК к узлу А достаточно в каждом УК выбирать исходящий ТПС с меньшим весом. Например, кратчайший маршрут от УК N до УК А будет следующий: ¹_N,A = {NO, OK, KD, DA} или ²_N,A = {NM, MI, IC, CA}, ³_N,A = {NO, OK, KC, CA}.

В случае загруженности или неисправности элементов сети необходимо переформировать рельеф. При восстановлении или освобождении элементов сети первоначальный рельеф потребуется восстановить.

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

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

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

Игровой метод [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, что удовлетворяет требованиям. Следовательно, маршрут между УИ и УП _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 уменьшился. Однако он остается максимальным из всех весовых коэффициентов в данном векторе. Следовательно, соответствующий ТПС остается исходящим ТПС первого выбора.

Если ситуация поиска маршрута между заданной парой УК повторится, т.е. повторно будет организован маршрут _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, то можно предположить, что игровой метод формирования ПРИ имеет итеративный характер и решает задачу глобальной оптимизации сети связи по критерию  вероятность установления соединения между парами УИ и УП.

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

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