С. Формирование матриц маршрутов Mj.

Матрица маршрутов Mj определяет порядок выбора путей передачи инфор-мации от узла j к любому узлу сети. При этом для связи используются, в нашем случае, кратчайшие по рангу пути.

Матрица Mj формируется на основании матрицы рельефов. Она сдержит n ─ 1 строк и k столбцов. Из нее исключается строка, соответствующая вершину j. Номер столбца определяет порядок выбора путей от вершины j через смежные ей вершины. В нашем случае их k.

Вхождение матрицы Mj представляет номер смежной вершины с вершиной j. Самый короткий по рангу путь является путем первого выбора, а самый длинный – путем k-ого выбора. При равенстве ранга путей, вводится дополнительные условия определения порядка выбора путей. Например, преимущество имеют пути через смежную вершину с меньшим номером. Не заполненная матрица Mj имеет следующий вид:

 

			...	k
			…
			…
.	.	.	.
j ─ 1			…
j +1			…
.			...
n			…

 

Mj =

 

Пример 1

Ниже приведены i - рельефы, матрицы рельефов Rj и матрицы маршрутов Mj для графа сети, представленного на рис. 28.

 

Рис. 31. Исходный граф сети.

 

Для формирования i – рельефов был использован выше приведенный алгоритм. На рис. 32. представлены рельефы для 1, 2, 3 и 4 вершин.

 

Рис. 32. Рельефы для 1, 2, 3 и 4 вершин.

 

Для формирования матрицы рельефов, например R1, т.е. для первой верши-

ны, были определены ее параметры. В соответствии со схемой сети, матрица R1 содержит две строки и четыре столбца. Смежной с вершиной 1 являются вер-шины 2 и 4. Через эти вершины может быть осуществлена связь от вершины 1 к любой вершине сети.

Для определения вхождений матрицы рельефов R1, используем рельефы для 2, 3 и 4 вершин. Обращаясь к рельефу для второй вершины, видим, что от вершины 1 к вершине 2 может быть использованы два пути. Первый путь проходит через узел 2. Второй - через узел 4. Минимальный ранг первого пути равен 1 (r =1), второго – r = 2. Заполняем первый столбец матрицы R1.

Аналогичные рассуждения позволяют заполнить второй, третий и четвер-тый столбцы матрицы R1. Аналогичные рассуждения позволяют сформировать матрицы R2, R3 и R4. На рис. 33. представлены матрицы рельефов R1, R2, R3 и R4.

 

 

Рис. 33. Матрицы рельефов R1, R2, R3 и R4.

 

На основании матриц рельефов, формируются матрицы маршрутов Mj. Рассмотрим формирование матрицы М1. Матрица М1 имеет три строки и два столбца, так как вершина может быть связана со 2 –ой, 3 –ей и четвертой вершинами. Количество столбцов определяется числом смежных вершин с вершиной 1. Это 2 и 4 вершины. Обращаясь к матрицы рельефов для 1-ой вершины, видно, что при связи 1 –ой и 2 –ой вершин через вершину 2 длина кратчайшего по рангу пути будет равна 1 (r = 1), а при связи через 4 – ую вершину длина кратчайшего пути равна 2 (r = 1). Следовательно, путь первого выбора от вершины 1 ко второй вершины пройдет через вершину 2, путь второго выбора через вершину 4.

Аналогичные рассуждения позволяют заполнить до конца матрицу М1, далее М2, М3 и М4. Полученные матрицы приведены на рис.34.

 

 

Рис.34. Матрицы маршрутов М1, М2, М3 и М4.

Пример 2

Построить i – рельефы для графа сети, представленного на рис. 28, при условии, что ребро между узлом 1 и 4удалено ребро b 14. Структура графа сети в данном случае представлена на рис. 35.

 

Рис. 35. Граф сети, в которой ребро b 14 удалено.

 

Для данного случая i – рельефы построены и представлены на рис. 36.

 

Рис. 36. Рельефы для вершин 1, 2, 3 и 4 после удаления ребра b 14.

Используя, представленные на рис. 33 рельефы, построим матрицы рель-ефов R1, R2, R3 и R4. Эти матрицы представлены на рис. 37.

 

Рис. 37. Матрицы рельефов при удалении ребра b 14.

 

Сформируем матрицы маршрутизации при удалении ребра b 14, используя выше представленные матрицы рельефов. На рис. 38 представлены матрицы М1, М2,

М3 и М4.

 

Рис.38. Матрицы маршрутизации для сети при удалении ребра b 14.

Пример 3

 

Для сети, представленной на рис. 31, необходимо:

а) составить рельеф для 1-ого узла;

б) используя полученный рельеф, для узла 4 – ого составить 1-ый столбец матрицы рельефов R4;

в) на основании столбца матрицы R4, дляузла 4 составить 1 –ую строку матрицы маршрутизации М4;

г) переформировать рельеф для 1 – ого узла и составить один столбец матри-цы рельефов R4, а затем составить строку матрицы маршрутизации М4 при удалении ребра b14;

д) сравнить полученные результаты и сделать вывод о возможности исполь-

зовании метода рельефов для управления потоками сообщений на сети связи.

Решение

Для сети, представленной на рис.31, при исправных ребрах, для 1-ого узла был составлен i – рельеф. Он имеет вид

Рис.39. Рельеф для 4 – ого узла.

 

Используя полученный рельеф, заполним 1 – ый столбец для матрицы рельефов R4 и, затем, первую строку матрицы маршрутизации М4. На рис.40. представлен первый столбец матрицы R4, характеризующий длину путей по ран--гу от 4 –ого узла до 1 –ого узла через смежные узлы с 4 –ым узлом. На этом же рисунке представлена первая строка матрицы маршрутизации для 4 –ого узла, характеризующая порядок занятия путей от 4 –ого узла до 1 –ого, которая состав-лена на основании матрицы R4.

Рис.40. Первый столбец матрицы R4 и первая строка матрицы М1.

 

На рис. 41 представлен граф (рис. 31), у которого удалено ребро b14.

Рис. 41. Исходный граф после удаления ребра b14.

Рис. 42. Рельеф для 1 –ой вершины после удаления ребра b14.

Используя рельеф для 1 –ой вершины после удаления ребра b14, заполним 1 –ый столбец для матрицы рельефов R4 и, затем, первую строку матрицы маршрутиза-ции М4. На рис. 43 матрица R4 и М4 для данного случая.

Рис. 43. Матрица R4 и матрица М4 для первой строки и первого столбца в случае удаления ребра.

 

Сравнивая матрицы, изображенные на рис.40 и рис.43, приходим к выводу, что метод рельефов может быть использован для маршрутизации, так как матрицы М4 при наличии ребра b14 существенно отличается от матрицы М4 после удаления ребра b14.

 

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: