Лабораторная работа №8. Поиск оптимального маршрута по критерию пропускной способности коммуникационной сети

Пример 5.1. Пусть задана топология сети (рис. 5.3):

Рис 5.3. Топология сети

Для реализации маршрутизации сети в каждом транзитном узле коммутации, начиная с узла источника, формируется таблица маршрутизации,которая представляет собой матрицу, размерностью :

(1)

(2)

где U – количество узлов коммутации в сети; L_j – количество исходящих линий связи из j -го узла коммутации.

Матрица определяет, какую исходящую линию связи предпочтительно выбрать из j -го узла коммутации при поиске маршрута к i -му узлу (узлу получателю).

Первый элемент вектор-строки формулы (2) указывает номер исходящей линии связи из j - го узла коммутации к смежному узлу коммутации, которую предпочтительнее выбрать для организации маршрута к i- му узлу коммутации (узлу получателю).

Второй элемент (2) указывает номер следующей исходящей линии связи из j - го узла коммутации к другому смежному узлу коммутации, которая менее предпочтительна для организации искомого маршрута. И так до L_j -го элемента вектор-строки (2).

В данном случае: m_i₁⁽^j⁾ – исходящая линия связи выбора L смежных линий связи из j - го узла.

Пример 5.2. Пусть необходимо построить таблицу маршрутизации для 4-го узла коммутации, если топология сети задана на рис 5.3.

Строки матрицы маршрутизации соответственно будут равны:

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

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

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

Пример 5.3. Создадим план распределения информации для топологии сети, показанной на рисунке 5.4. Критерием выберем максимальную скорость передачи данных.

Рис 5.4.Топология сети

Формирование плана распределения информации может осуществляться и по другим критериям:

1. Количество транзитных узлов

2. Время задержки при передаче данных

3. Безопасность узлов связи

4. Надёжность узлов связи

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

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

Таким образом, анализируя процедуры, участвующие в формировании маршрутов можно заключить, что маршрутизация состоит из двух этапов:

1. Формирование плана распределения информации в сети связи.

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

ЗАДАНИЕ

1. Найти оптимальный маршрут от узла 1 к узлу 5 для заданной топологии, по критерию пропускной способности сети.

а) б)

в) г)

д) е)

2. Сформировать план распределения информации для заданной топологии по следующим критериям:

1) количество транзитных узлов
2) скорость передачи данных.

а) б) в)

г) д) е)

3. Написать программу поиска оптимального маршрута в сети, реализовать поиск по критериям:

1) минимального количества узлов коммутации;
2) максимальной скорости передачи данных.

Содержание отчета

1. Оптимальный маршрут в соответствии с заданием 1.

2. План распределения информации для заданной топологии в соответствии с указанными в задании 2 критериями.

3. Листинг программы.

4. Примеры результатов работы программы для указанных в задании 3 критериев.

5.3. Лабораторная работа №9. Методы формирования плана распределения информации

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

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

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

Пример 5.4. Построим рельеф для топологии заданной на рисунке 5.5, узлом получателем в данном случае выберем узел 1. По исходящим линиям связи 1-2,1-3,1-4 передаётся число 1. Из узлов 2 3 4 по исходящим линиям связи 3-8, 3-4,4-6,4-5,4-2,2-5 передаётся число 2, из узлов 5 6 8 по исходящим линиям связи 6-8, 6-9,5-7 передаётся число 3, из узла 9 по исходящим линиям 9-8,9-7 передаётся число 4.

Для нахождения кротчайшего пути из любого узла к узлу 1 необходимо выбирать линии связи с наименьшим весом. Так, например кротчайший путь из узла 6 к узлу 1 будет 6-4-1. Недостаток метода в том, что для каждого узла получателя необходимо строить рельеф.

Рис 5.5. Топология сети

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

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

Пример 5.5. Составим план распределения информации игровым методом для топологии сети заданной на рисунке 5.6.

Рис 5.6. Топология сети

Пусть изначальный план распределения информации задан в виде таблиц маршрутизации. Весовые коэффициенты будут равны соответственно:

Выберем исходящую линию связи из узла источника 2 к узлу получателю 1 при условии, что число транзитных узлов не должно превышать одного. Для этого из матрицы весовых коэффициентов P²выберем строку

p₁= (0,6 0,1 0,3).

Исходящая линия связи из узла 1 будет являться линией связи первого выбора, так как её весовой коэффициент является наибольшим, если данная линия связи не доступна, то будет выбрана исходящая линия связи второго выбора в данном случае линия связи из узла 4 так как её весовой коэффициент больше чем у узла 3. Предположим, что исходящая линия связи первого выбора была занята, и для организации маршрута была выбрана исходящая линия связи второго выбора. Для дальнейшей организации маршрута из матрицы весовых коэффициентов P⁴выберем строку

p₁⁴=(0,7 0,2 0,1).

Допустим, что исходящая линия связи первого выбора доступна. Следовательно, маршрут из узла 2 к узлу 1 организован и имеет вид {2 4 1}. Линии связи, которые участвуют в маршруте, поощряются, следовательно, их весовые коэффициенты должны быть увеличены, а строки матрицы весовых коэффициентов нормированы. При увеличении весовых коэффициентов необходимо заранее выбрать константу, на которую будем увеличивать весовой коэффициент поощрённых линий. Для данного примера пусть эта константа будет равна 0,2 тогда соответствующие строки матриц весовых коэффициентов примут вид:

p₁²= (0,6 0,1 0,5); p₁⁴=(0,9 0,2 0,1).

Следовательно данные векторы строки необходимо нормировать.
Для нормирования необходимо каждый из коэффициентов разделить на сумму модулей всех коэффициентов вектора.

После нормирования данные строки примут вид:

p₁²=(0,5 0,08 0,42); p₁⁴=(0,75 0,17 0,08).

При повторном поиске маршрута соответствующие коэффициенты строк матриц весовых коэффициентов изменятся и примут вид

p₁²=(0,42 0,07 0,51); p₁⁴=(0,79 0,14 0,07).

Видно, что исходящая линия связи из узла 2 к узлу 4 стала линией связи первого выбора при поиске маршрута к узлу 1, т.к. её коэффициент стал наибольшим.

Следовательно, матрицы весовых коэффициентов примут вид

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

ЗАДАНИЕ

1. Построить рельеф в заданной топологии сети для узла получателя 1.

а) б)

в) г)

д) е)

ж) з)

и) к)

2. Написать программу для построения рельефа в заданной топологии.

3. Составить план распределения информации игровым методом, организовать маршрут между узлом источником 1 и узлом получателем 3 с количеством транзитных узлов не более 2, при условии что линия связи между узлами 4 и 5 не доступна.

а) б) в)